CERTIFICATE

Certified that this is a bona fide report of the project entitled

'Linear Programming Problems' done by Pratik Misra under my
supervision and guidance in the partial fulfillment for the internal
assessment introduced in the degree semester course.

Place : Signature
Date : Name of Guide Designation
 ACKNOWLEDGEMENT

I am deeply grateful to class teacher and other teachers in our Maths

Department from whom I received comments and suggestions which have
helped me to improve the collection of this project. I would like to express
my appreciation to the group members who took my project and helped me
in improving the earlier versions of the manuscript. I would like to place on
record my sincere appreciation to vinod for his painstaking efforts in
typing the manuscript in a record time. Last but not least, I acknowledge
with thanks the sacrifices made by my dear friends and family on account
of my involvement with the task of completing this project work.
 CONTENT
Introduction -------------
Assignment problems --------
Balance assignment problem---
Unba
Principles -------------
Definition of terms -------
Mathematical Formation ------
General form --------
Canonical form -------
Standard form -------
Lpp special cases -----
Unbounded solution ----
Degeneracy ------
Transportation problem -------

Simplex method --------

Big M --------
Duality --------
Duality simplex method ----
 INTRODUCTION

Mathematics is the queen of science. In our daily life, planning is

required on various occasions, especially when the resources are limited.
Any planning is meant for attaining certain objectives. The best strategy is
one that gives a maximum output from a minimum input. The objective
which is in the form of output may be to get the maximum profit, minimum
cost of production or minimum inventory cost with a limited input of raw
material, manpower and machine capacity. Such problems are referred to
as the problems of constrained optimization. Linear programming is a
technique for determining an optimum schedule of interdependent
activities in view of the available resources. Programming is just another
word for 'planning' and refers to the process of determining a particular
plan of action from amongst several alternatives.

Linear programming applies to optimization models in which

objective and constraint functions are strictly linear. The technique is used
in a wide range of applications, including agriculture, industry,
transportation, economics, health systems, behavioral and social sciences
and the military. It also boasts efficient computational algorithms for
problems with thousands of constraints and variables. Indeed, because of
its tremendous computational efficiency, linear programming forms the
backbone of the solution algorithms for other operative research models,
including integer, stochastic and non-linear programming. The graphical
solution provides insight into the development of the general algebraic
simplex method. It also gives concrete ideas for the development and
interpretation of sensitivity analysis in linear programming.
 Linear programming is a major innovation since World War II in the
field of business decision making, particularly under conditions of
certainty. The word 'linear' means the relationships handled are those
represented by straight lines, i.e. the relationships are of the form y = a +
bx and the word 'programming' means taking decisions systematically.
Thus, linear programming is a decision making technique under given
constraints on the assumption that the relationships amongst the variables
representing different phenomena happen to be linear.

A linear programming problem consists of three parts. First, there

objective function which is to be either maximized or minimized. Second,
there is a set of linear constraints which contains thee technical
specifications of the problems in relation to the given resources or
requirements. Third, there is a set of non negativity constraints - since
negative production has no physical counterpart.
 AIM
1. To find and know more about the importance and uses of 'linear
programming'.
2. To formulate a linear programming problem and solve

USES
There are many uses of L.P. It is not possible to list them all here. However
L.P is very useful to find out the following:

Optimum product mix to maximize the profit.

Optimum schedule of orders to minimize the total cost.

Optimum media-mix to get maximum advertisement effect.

Optimum schedule of supplies from warehouses to minimize transportation

costs.

Optimum line balancing to have minimum idling time.

Optimum allocation of capital to obtain maximum R.O.I

Optimum allocation of jobs between machines for maximum utilization of

machines.

Optimum assignments of jobs between workers to have maximum labor

productivity.

Optimum staffing in hotels, police stations and hospitals to maximize efficiency.

Optimum number of crew in buses and trains to have minimum operating costs.

Optimum facilities in telephone exchange to have minimum break downs.

ADVANTAGES
 Provide the best allocation of available resources.
 meet overall objectives of the management.
 Assist management to take proper decisions.
 Provide clarity of thought and better appreciation of problem.
 Improve objectivity of assessment of the situation.
 Put across our view points more successfully by logical argument
supported by scientific methods.

APPLICATION OF LINEAR PROGRAMMING

The primary reason for using linear programming methodology is
to ensure that limited resources are utilized to the fullest extent without any
waste and that utilization is made in such a way that the outcomes are
expected to be the best possible.

Some of the examples of linear programming are:

a) A production manager planning to produce various products with the

given resources of raw materials, man-hours, and machine-time for
each product must determine how many products and quantities of
each product to produce so as to maximize the total profit.
b) An investor has a limited capital to invest in a number of securities
such as stocks and bonds. He can use linear programming approach to
establish a portfolio of stocks and bonds so as to maximize return at a
given level of risk.
c) A marketing manager has at his disposal a budget for advertisement
in such media as newspapers, magazines, radio and television. The
manager would like to determine the extent of media mix which
would maximize the advertising effectiveness.
d) A Farm has inventories of a number of items stored in warehouses
located in different parts of the country that are intended to serve
various markets. Within the constraints of the demand for the
products and location of markets, the company would like to
determine which warehouse should ship which product and how
much of it to each market so that the total cost of shipment is
minimized.
e) Linear programming is also used in production smoothing. A
manufacturer has to determine the best production plan and inventory
policy for future demands which are subject to seasonal and cyclical
fluctuations. The objective here is to minimize the total production
and inventory cost.
f) A marketing manager wants to assign territories to be covered by
salespersons. The objective is to determine the shortest route for each
salesperson starting from his base, visiting clients in various places
and then returning to the original point of departure. Linear
programming can be used to determine the shortest route.
g) In the area of personnel management, similar to the travelling
salesperson problem, the problem of assigning a given number of
personnel to different jobs can be solved by this technique. The
objective here is to minimize the total time taken to complete all jobs.
h) Another problem in the area of personnel management is the problem
of determining the equitable salaries and sales-incentive
compensation. Linear programming has been used successfully in
such problems.
 BASIC REQUIREMENTS OF A LINEAR
PROGRAMMING MODEL
a) The system under consideration can be described in terms of a series of
activities and outcomes. These activities (variables) must be competing
with other variables for limited resources and the relationships among
these variables must be linear and the variables must be quantifiable.
b) The outcomes of all activities are known with certainty.
CHARACTERISTICS

Objectives can be expressed in a standard form viz.

maximize/minimize z = f(x) where z is called the objective function.

Constraints are capable of being expressed in the form of equality or

inequality viz. f(x) = or ≤ or ≥ k, where k = constant and x ≥ 0.

Resources to be optimized are capable of being quantified in

numerical terms.

The variables are linearly related to each other.

More than one solution exist, the objectives being to select the optimum
solution.

The linear programming technique is based on simultaneous solutions of linear

equations
 PRINCIPLES
Following principles are assumed in L.P.P

Proportionality: There exist proportional relationships between

objectives and constraints.

Additivity: Total resources are equal to the sum of the resources used in
individual activities.

Divisibility: Solution need not be a whole number viz decision variable

can be in fractional form.

Certainty: Coefficients of objective function and constraints are known

constants and do not change viz parameters remain unaltered.

Finiteness: Activities and constraints are finite in number.

Optimality: The ultimate objective is to obtain an optimum solution viz

'maximization' or 'minimization'.

DEFINITION OF TERMS

a) Basic solution: There are instances where number of unknowns (p)

are more than the number of linear equations (q) available. In such
cases we assign zero values to all surplus unknowns. There will be (p-
q) such unknowns. With these values we solve 'q' equations and get
values of 'q' unknowns. Such solutions are called Basic Solutions.
b) Basic variables: The variables whose value is obtained from the
basic solution is called basic variables
c) Non-basic variables: The variables whose value are assumed as zero
in basic solutions are called non-basic variables.

d) Solution: A solution to a L.P.P is the set of values of the variables

which satisfies the set of constraints for the problem.
e) Feasible solution: A feasible solution to a L.P.P the set of values of
variables which satisfies the set of constraints as well as the non-
negative constraints of the problem.
f) Basic feasible solution: A feasible solution to a L.P.P in which the
vectors associated with the non-zero variables are linearly
independent is called basic feasible solution
Note: Linearly independent: variables x 1, x2, x3......... are said to be
linearly independent if k1x1+k2x2+.........+knxn=0, implying k1=0,
k2=0,........
g) Optimum (optimal) solution: A feasible solution of a L.P.P is said
to be the optimum solution if it also optimizes the objective function
of the problem.
h) Slack variables: Linear equations are solved through equality form
of equations. Normally, constraints are given in the "less than or
equal" (≤) form. In such cases, we add appropriate variables to make
it an "equality" (=) equation. These variables added to the constraints
to make it an equality equation in L.P.P is called stack variables and
is often denoted by the letter 'S'.
Eg: 2x1 + 3x2 ≤ 500
∴ 2x1 + 3x2 + S1 = 500, where S1 is the slack variable
i) Surplus variables: Sometime, constraints are given in the "more than
or equal" (≥) form. In such cases we subtract an approximate variable
to make it into "equality" (=) form. Hence variables subtracted from
the constraints to make it an equality equation in L.P.P is called
surplus variables and often denoted by the letter 's'.
Eg: 3x1 + 4x2 ≥ 100
3x1 + 4x2 - S2 = 0, where S2 is the surplus variable.
j) Artificial variable : Artificial variables are fictitious variables. These
are introduced to help computation and solution of equations in L.P.P.
There are used when constraints are given in (≥) "greater than equal"
form. As discussed, surplus variables are subtracted in such cases to
convert inequality to equality form . In certain cases, even after
introducing surplus variables, the simplex tableau may not contain an
'Identity matrix' or unit vector. Thus, in a L.P.P artificial variables are
introduced in order to get a unit vector in the simplex tableau to get
feasible solution. Normally, artificial variables are represented by the
letter 'A'.
k) Big-M-method: Problems where artificial variables are introduced
can be solved by two methods .

Big-M-method and
 Two phase method.

Big-M-method is modified simplex method for solving L.P.P when

high penalty cost (or profit) has been assigned to the artificial
variable in the objective function. This method is applicable for
minimizing and maximizing problems.

l) Two Phase method : L.P.P where artificial variables are added

can be solved by two phase method. This is a modified simplex
method. Here the solution takes place in two phases as follows:

Phase I - Basic Feasible solution: Here, simplex method is applied

to a specially constricted L.P.P called Auxiliary L.P.P and obtain
basic feasible solution.

Phase II - Optimum Basic solution: From basic feasible solution,

obtain optimum feasible solution.

m) Simplex Tableau : This is a table prepared to show and enter the

values obtained for basic variables at each stage of Iteration. This is
the derived values at each stage of calculation.

ASSIGNMENT PROBLEM

The Assignment Problem is a special type of linear programming problem that

deals with allocating resources (like people, machines, or tasks) to activities
(like jobs, projects, or locations) on a one-to-one basis, with the goal of
optimizing a specific objective, typically minimizing cost or time, or
maximizing profit.

Aim
The primary aim of the assignment problem is to find an optimal assignment of
n resources to n activities such that:

 Each resource is assigned to exactly one activity.

 Each activity is assigned to exactly one resource.
 The total cost (or time, etc.) of the assignment is minimized, or the total
profit (or efficiency, etc.) is maximized.

This problem arises in various real-world scenarios, such as:

 Assigning employees to jobs.

 Assigning machines to tasks.
 Assigning salespersons to territories.
 Assigning trucks to delivery routes.
 Assigning students to projects.

Mathematical Formulation:

Let x_ij be a binary decision variable such that: x_ij=1 if resource i is assigned
to activity j x_ij=0 otherwise

Let c_ij be the cost (or time, etc.) of assigning resource i to activity j.

The objective function (for minimization) is:

Minimize Z=i=1∑nj=1∑ncijxij

Subject to the constraints:

Method: The Hungarian Algorithm

While the assignment problem can be solved using the general simplex method
for linear programming, it has a highly degenerate structure, making the simplex
method inefficient for larger problems. A more efficient and specialized
algorithm for solving assignment problems is the Hungarian Algorithm. This
algorithm is based on the concept of reducing the cost matrix until an optimal
assignment can be identified.

The Hungarian Algorithm works on the principle that if we add or subtract a

constant from every element of a row or a column in the cost matrix, the optimal
assignment remains the same. This property allows us to create zeros in the
matrix and find an assignment that corresponds to these zeros.

Key Concepts behind the Hungarian Algorithm:

 Opportunity Cost: The algorithm focuses on finding the "opportunity

cost" of not making a particular assignment.
 Zero-Cost Assignment: The goal is to transform the cost matrix into one
where an optimal assignment can be made using only zero-cost elements.

3. Steps of the Hungarian Algorithm (Minimization Problem)

Let's outline the steps for a minimization assignment problem. For maximization
problems, a slight modification is needed .

Step 1: Create the Cost Matrix Represent the problem as a square matrix
where rows represent resources and columns represent activities, and each cell
(i,j) contains the cost c_ij of assigning resource i to activity j. If the number of
resources and activities are not equal (unbalanced problem), add dummy rows or
columns with zero costs to make it a square matrix.

Step 2: Row Reduction For each row, identify the smallest element and
subtract this element from every element in that row. This will create at least
one zero in each row.

Step 3: Column Reduction For each column, identify the smallest element and
subtract this element from every element in that column. This will create at least
one zero in each column. (Note: If a column already contains a zero from the

row reduction step, the smallest element might be zero, in which case no change
occurs in that column.)
Step 4: Cover All Zeros with Minimum Number of Lines Draw the minimum
number of horizontal and/or vertical lines required to cover all the zeros in the
matrix.

 If the minimum number of lines equals the order of the matrix (n), then an
optimal assignment can be made. Proceed to Step 6.
 If the minimum number of lines is less than n, proceed to Step 5.

Draw Minimum Lines (Practical Tip):

1. Identify rows/columns with a single zero. Mark that zero and cross out the
row and column it belongs to.
2. Continue this process until no more single zeros exist.
3. For remaining zeros, try to cover them efficiently. A common strategy is
to cover rows/columns that contain the most zeros.

Step 5: Create Additional Zeros (If Optimal Assignment Not Yet Possible)
If the number of lines is less than n:

1. Find the smallest uncovered element (an element not covered by any
line).
2. Subtract this smallest uncovered element from all uncovered elements.
3. Add this smallest uncovered element to all elements that are at the
intersection of two lines.
4. Elements covered by a single line remain unchanged.
5. Go back to Step 4 and repeat the line drawing process.

Step 6: Make the Optimal Assignment Once the number of lines equals n:

1. Examine rows one by one until a row with exactly one zero is found.
Mark this zero (assign it) and cross out the column containing this zero
(as this activity is now assigned).
2. Continue this process for all rows.
3. If a row has more than one zero, skip it for now and come back to it after
processing rows with single zeros.
4. After processing all rows, examine columns one by one following the
same logic (find columns with exactly one uncovered zero, mark it, and
cross out its row).
5. If there are still unassigned zeros, make arbitrary assignments, ensuring
that each row and column has exactly one assigned zero.

Step 7: Calculate the Total Optimal Cost Sum the original costs (c_ij from the
initial cost matrix) corresponding to the assigned zero.
 Types of assignment problems
This is the most fundamental classification.

Minimization Assignment Problem:

Aim: To assign resources to tasks in such a way that the total cost, total time,
total distance, or any other quantifiable measure to be minimized, is as low as
possible.

Typical Scenarios: Assigning workers to jobs to minimize labor costs,

assigning machines to tasks to minimize production time, assigning vehicles to
routes to minimize fuel consumption.

Method: Directly solved using the Hungarian Algorithm.

Maximization Assignment Problem:

Aim: To assign resources to tasks such that the total profit, total efficiency, total
sales revenue, or any other quantifiable measure to be maximized, is as high as
possible.

Typical Scenarios: Assigning salespersons to territories to maximize sales,

assigning researchers to projects to maximize research output, assigning
advertising slots to products to maximize market reach.

Method: Transformed into a minimization problem by creating an "opportunity

loss" or "regret" matrix. This is done by subtracting all elements of the original
matrix from the largest element in the matrix. Then, the Hungarian Algorithm is
applied to this new matrix.
Based on the Number of Resources vs. Tasks:

This classification addresses whether the assignment matrix is square or

rectangular.

 Balanced Assignment Problem:

o Characteristic: The number of resources (rows) is exactly equal to
the number of tasks (columns).
o Method: The Hungarian Algorithm is directly applicable after setting up the
cost/profit matrix. The examples provided in our previous discussion were
balanced problems.
o Example Matrix: A 4x4 matrix where 4 workers need to be assigned to 4
jobs.
 Unbalanced Assignment Problem:
o Characteristic: The number of resources is not equal to the number of tasks.
This means the assignment matrix is rectangular.
o Method: To solve using the Hungarian Algorithm, the matrix must first be
converted into a balanced (square) matrix by introducing dummy rows or
dummy columns.
 If Number of Resources > Number of Tasks: Add dummy columns
to the cost/profit matrix. The costs associated with dummy columns are
typically zero, representing that there's no actual cost/profit incurred if
a resource is assigned to a dummy task (i.e., that resource remains
unassigned).
 If Number of Tasks > Number of Resources: Add dummy rows to
the cost/profit matrix. Similarly, the costs associated with dummy rows
are zero, implying no cost/profit if a task is assigned to a dummy
resource (i.e., that task is not performed).
o Important Note: When a resource is assigned to a dummy task, it means that
resource will not be assigned to any actual task. Conversely, if a task is
assigned to a dummy resource, that task will not be performed.

3. Special Cases/Variations:

These types introduce additional complexities or constraints.

 Restricted Assignment Problem (Prohibited Assignments):

o Characteristic: Certain assignments are not possible or are explicitly
forbidden due to practical reasons (e.g., a worker lacking the skill for a
particular job, a machine not compatible with a specific task).
o Method: To handle prohibited assignments, the corresponding cell in the cost
matrix is assigned an extremely high cost (for minimization problems,
represented by 'M' or '∞') or an extremely low profit (for maximization
problems, represented by '-M' or '−∞' in the original matrix, which becomes a
very high value after conversion to opportunity loss). This effectively prevents
the algorithm from selecting that particular assignment.
 o Example: If Worker A cannot do Job C, the cost cAC would be set to a very
large number.
 Multiple Assignments (Not a True Assignment Problem, but related):
o Characteristic: In some scenarios, a resource might be able to perform
multiple tasks, or a task might require multiple resources. This deviates from
the strict one-to-one mapping of a standard assignment problem.
o Method: These are typically modeled as more general Linear Programming
problems or Network Flow problems (specifically, minimum cost flow), rather
than being directly solvable by the Hungarian Algorithm. The assignment
problem is a special case of a minimum cost flow problem.
 Traveling Salesperson Problem (TSP) (Related, but Distinct):
o Characteristic: This is often confused with assignment problems but is more
complex. It involves finding the shortest possible route that visits each city
exactly once and returns to the origin city. While it involves assignments (of a
salesperson to the next city to visit), the sequential dependency and cyclical
requirement make it a much harder combinatorial optimization problem.
o Method: Not directly solved by the Hungarian Algorithm. It often uses
specialized heuristics, exact algorithms like Branch and Bound, or
sophisticated LP formulations. However, the assignment problem can
sometimes be a sub-problem or a relaxation in solving the TSP.
 Personnel Scheduling/Rostering (Larger Scale Application):
o Characteristic: Involves assigning employees to shifts or tasks over a period,
considering various constraints like employee availability, skill sets, labor
laws, and demand fluctuations. This is often a large-scale assignment problem.
o Method: Can be formulated as an integer linear program. While the Hungarian
Algorithm might be used for small, daily assignments, complex rostering often
requires more advanced LP solvers or specialized algorithms due to the
temporal and multi-constraint nature.

In summary, while the Hungarian Algorithm is the workhorse for solving the assignment
problem, understanding the specific type of problem—whether it's balanced or unbalanced,
minimization or maximization, or includes restrictions—is crucial for correctly setting up the
problem matrix and applying the algorithm effectively.
Transportation Problem

Transportation problem talks about transporting items from a given set of

supply point to a given set of destinations point. A transportation problem
when expressed in terms of an LP model can also be solved by the simplex
method. The structure of transportation problem involves a large number of
shipping routes from several supply centres to several demand centres.

Thus, objective is to determine shipping routes between supply centres and

demand centres in order to satisfy the required quantity of goods or
services at each destination centre, with available quantity of goods or
services at each supply centre at the minimum transportation.

Mathematical Formulation
Let there be m origins, ith origin possessing 𝑎𝑖 units of certain product.
Let there be n destinations, with destination j requiring 𝑏𝑗 units of a
certain product. Let 𝑐𝑖𝑗 be the cost of shipping one unit from ith source to

let 𝑖𝑗be the amount to be shipped from ith source to jth destination it is
jth destination

assumed that the total availabilities Σai satisfy the total requirements Σbj

determine non-negative of 𝑥𝑖𝑗satisfying both the availability constraints.

i.e. Σai= Σb j(i=1,2,3…m and j=1,2,3..n). The problem now, is to
 ∑ = 𝑛 𝑗𝑖 As well as requirement constraints ∑ = 𝑗𝑖 for i=1,2,….,n for

𝑖=1 ∑ 𝑥𝑖𝑗𝑐𝑖𝑗 𝑗=1 (objective function)

i=1,2,….,m And the minimizing cost of transportation (shipping) Z=∑𝑚

This special type of LPP is called as transportation problem.ion cost and

/time .

Some Basic Definitions.

Feasible solution - A set of non-negative individual allocations (𝑥𝑖𝑗 ≥0)

which simultaneously removes deficiencies is called as feasible solution.

Basic feasible solution - A feasible solution to 'm' origin, 'n' destination

problem is said to be basic if the number of positive allocations are m+n-1.
If the number of allocations is less than m+n-1 then it is called as
degenerate basic feasible solution. Otherwise it is called as non-degenerate
basic feasible solution.

Optimum solution- a feasible solution is said to be optimal if it

minimizes the total transportation cost.

Transportation problem is of two types:

a) Balanced transportation problem: (total demand = total supply)

b) Unbalanced transportation problem: (total demand ≠ total supply)

THE TRANSPORTATION ALGORITHM

The algorithm for solving a transportation problem may be summarized

into the following steps:
Step 1: Formulate the problem and arrange the data in the matrix form The
formulation of the transportation problem is similar to the LP problem
formulation. In transportation problem, the objective function is the total
 transportation cost and the constraints are the amount of supply and
demand available at each source and destination, respectively.
Step 2: Obtain an initial basic feasible solution In this chapter, following
three different methods are discussed to obtain an initial solution:

1. North-West Corner Method,

2- Row minima method

3- Column minima

4. Least Cost Method,

5.Vogel’s Approximation (or Penalty) Method.

The initial solution obtained by any of the five methods must satisfy the
following conditions:

(i) The solution must be feasible, i.e. it must satisfy all the supply and
demand constraints (also called rim conditions).

(ii) The number of positive allocations must be equal to m + n– 1, ,

where m is the number of rows and n is the number of columns. Any

solution that satisfies the above conditions is called non-degenerate
basic feasible solution, otherwise, degenerate solution. Step 3: Test
the initial solution for optimality In this chapter, the Modified
Distribution (MODI) method is discussed to test the optimality of
the solution obtained in Step 2. If the current solution is optimal,
then stop. Otherwise, determine a new improved solution.

FINDING INITIAL BASIC FEASIBLE SOLUTION

North-West Corner Method:
Step 1: Start with the cell at the upper left (north-west) corner of the
transportation table (or matrix) and allocate commodity equal to the minimum
of the rim values for the first row and first column, i.e. min (a1, b1).

Step 2: (a) If allocation made in Step 1 is equal to the supply available at first
source (a1, in first row), then move vertically down to the cell (2, 1), i.e.,
second row and first column.

Apply Step 1 again, for next allocation.

(b) If allocation made in Step 1 is equal to the demand of the first destination
(b1 in first column), then move horizontally to the cell (1, 2), i.e., first roNw
and second column. Apply Step 1 again for next allocation. (c) If a1 = b1,
allocate x11 = a1 or b1 and move diagonally to the cell (2, 2).

Step 3: Continue the procedure step by step till an allocation is made in the
south-east corner celle

4: Updating the solution Repeat Step 3 until an optimal solution is reached.

Least Cost Method (LCM)

The main objective is to minimize the total transportation cost, transport as
much as possible through those routes (cells) where the unit transportation
cost is lowest. This method takes into account the minimum unit cost of
transportation for obtaining the initial solution and can be summarized as
follows:

Step 1: Select the cell with the lowest unit cost in the entire transportation
table and allocate as much as possible to this cell. Then eliminate (line out)
that row or column in which either the supply or demand is fulfilled. If a row
and a column are both satisfied simultaneously, then crossed off either a row
or a column. In case the smallest unit cost cell is not unique, then select the
cell where the maximum allocation can be made.

Step 2: After adjusting the supply and demand for all uncrossed rows and
columns repeat the procedure to select a cell with the next lowest unit cost
among the remaining rows and columns of the transportation table and
allocate as much as possible to this cell. Then crossed off that row and
column in which either supply or demand is exhausted.

Step 3: Repeat the procedure until the available supply at various sources and
demand at various destinations is satisfied. The solution so obtained need not
be non-degenerate.

Vogel’s Approximation Method (VAM)

Vogel’s approximation (penalty or regret) is preferred over NWCR and
LCM methods. In this method, an allocation is made on the basis of the
opportunity (or penalty or extra) cost that would have been incurred if the
allocation in certain cells with minimum unit transportation cost were
missed. Hence, allocations are made in such a way that the penalty cost is
minimized. An initial solution obtained by using this method is nearer to an
optimal solution or is the optimal solution itself. The steps of VAM are as
follows:

Step 1: Calculate the penalties for each row (column) by taking the
difference between the smallest and next smallest unit transportation cost
 in the same row (column). This difference indicates the penalty or extra
cost that has to be paid if decision-maker fails to allocate to the cell with
the minimum unit transportation cost.

Step 2: Select the row or column with the largest penalty and allocate as
much as possible in the cell that has the least cost in the selected row or
column and satisfies the rim conditions. If there is a tie in the values of
penalties, it can be broken by selecting the cell where the maximum
allocation can be made.

Step 3: Adjust the supply and demand and cross out the satisfied row or
column. If a row and a column are satisfied simultaneously, only one of
them is crossed out and the remaining row (column) is assigned a zero
supply (demand). Any row or column with zero supply or demand should
not be used in computing future penalties.

Step 4: Repeat Steps 1 to 3 until the available supply at various sources

and demand at various destinations is satisfied

Maximize, z = 20 x1 + 9 x2 + 10 x3

Subject to 12 x1 + 3 x2 + 4 x3 ≤ 300

6 x1 + 4 x2 + x3 ≤ 225
 3 x1 + x2 + 2 x3 ≤ 100

x1, x2, x3 ≥ 0

By using simplex method

By introducing slack variables, the problem can be restated as :

Maximize 20x1 + 9x2 + 10x3 + 0x4 + 0 x5 + 0 x6

Subject to 12x1 + 3x2 + 4x3 + x4 = 300

6x1 + 4x2 + x3 + x5 = 225

3x1 + x2 + 2x3 +x6 = 100

Where x1, x2 and x3 are structural variable and x4, x5, and x6 are stock variables

In order to simplify handling the educations in the problem, they can be placed
in a tabular form, known as a tableau. The initial tableau is given below

Simplex Tableau I: initial step

Qi =
Ci Basis P1 P2 P3 P4 P5 P6 P0 P oi
x oi
0 x4 1 3 4 1 0 0 300 25
2
0 x5 6 4 1 0 1 0 255 37.5
0 x6 3 1 2 0 0 1 100 33.3
Body Matrix Identity Matrix

cj 20 9 10 0 0 0
zj 0 0 0 0 0 0
∆ j = cj - zj 20 9 10 0 0 0

Starting with the left hand column in the above tableau, the C1 column contains
the contributions per unit for the basic variables x4, x5 and x6. The zero indicates that
the contribution per unit is zero. The reasoning is that no profits are made on unused
raw materials or labour. The second column, the basis, contains the variables in the
solution which are used to determine the total contribution. In the initial solution, no
products are being manufactured. This is represented in the c jth row for the column
under P0. Since no units are manufactured, the first solution is,
 x1 = 0 x4 = 300

x2 = 0 x5 = 225

x3 = 0 x6 = 100

The body matrix consists of the coefficients for the real product (structural)
variables in the first simplex tableau represents the coefficients of the slack variables
that have been included to the original inequalities to make them equations.

The row cj contains coefficients of respective variables in the objective function.

The last two rows of the first simplex tableau are used to determine whether or not the
solution can be improved. The zero values in the x j row are the amounts by which
contribution would be reduced if one unit of the variables x 1, x2, x3, x4, x5 and x6 was
added to the product mix.

Another way of defining the variables of the zj row is the contribution lost per unit
of the variables.

Simplex Tableau II

Qi =
Ci Basis P1 P2 P3 P4 P5 P6 P0 P oi
x oi
1 1
20 x4 1 ¼ /3 /12 0 0 25 100
5 -1
0 x5 0 /2 -1 /2 1 0 75 30
-1
0 x6 0 ¼ 1 /4 0 1 25 100
cj 20 9 10 0 0 0
20 20
zj 20 5 /3 /12 0 0
∆ j = cj - zj 0 4 10
/3 -20
/12 0 0

Simplex Tableau III

Qi =
Ci Basis P1 P2 P3 P4 P5 P6 P0 P oi
x oi
x4 13 7 -1 70 525
20 1 0 /30 /30 /10 0 /4
13
9 x5 0 1 -2
/5 -1
/5 2
/5 0 30 −75
0 11 -1 -1 70 175
0 x6 0 /10 /5 /10 1 /4
11
cj 20 9 10 0 0 0
76 43 8
zj 20 9 /15 /15 /5 0
∆ j = cj - zj 0 0 74
/15 -43
/15 -8
/5 0
Simplex Tableau IV

Qi =
Ci Basis P1 P2 P3 P4 P5 P6 P0 P oi
x oi
x4 103 -2 350
20 1 0 0 /33 0
330 33
x5 -3 4 400
9 0 1 0 /11 /11 0
11
-2 -1 175
0 x6 0 0 1 /11 /11 1
11
cj 20 9 10 0 0 0
65 38 148
zj 20 9 10
33 33 33
∆ j = cj - zj 0 0 0 −65 −38 −148
33 33 33

In tableau IV as all ∆ j ≤ 0, the solution has reached an optimum level. The

computational procedure comes to an end. Hence, the optimal solution is,

350 400 175

x1 = x2 = x3 =
33 11 11

350 400 175

z = 20 × +9× +10 ×
33 11 11

7000 3600 1750

= + +
33 11 11

7000 5350
= +
33 11

77000+176550 253550
= =
363 363

= 698.4848

Z = 698.4848

By using Dual Problem

The dual of the above problem is,

Minimize z* = 300 y1 + 225 y2 + 100 y3

Subject to, 12 y1 + 6 y2 + 3 y3 ≥ 20

3 y1 + 4 y2 + y3 ≥ 9
 4 y1 + y2 + 2 y3 ≥ 10

y1, y2, y3 ≥ 0

Introducing surplus variables and artificial variable, the above problem can be restated
as follows:

Minimize z* = 300 y1 + 225 y2 + 100 y3 + 0 y4 + 0 y5 + 0 y6 + ω y7 + ω y8 + ω y9

Subject to, 12 y1 + 6 y2 + 3 y3 – y4 + y7 ≥ 20

3 y1 + 4 y2 + y3 – y5 + y8 ≥ 9

4 y1 + y2 + 2 y3 – y6 + y9 ≥ 10

y1, y2, y3 …. Y9 ≥ 0

Ci Basis P1 P2 P3 P4 P5 P6 P7 P8 P9 P0 Qi
ω y7 12 6 3 -1 0 0 1 0 0 20 5
/3
ω y8 3 4 1 0 -1 0 0 1 0 9 3
ω y9 4 1 2 0 0 -1 0 0 1 10 5
/2
cj 300 225 100 0 0 0 ω ω ω
zj 19ω 11ω 6ω −ω −ω −ω ω ω ω
19ω - 6ω -
zj-cj 11ω -225 −ω −ω −ω
300 100
300 y1 1 ½ -¼ - 1/12 0 0 1
/12 0 0 5
/3 20
/3
ω y8 0 5
/2 ¼ ¼ -1 0 -¼ 1 0 4 16
ω y9 0 -1 1 1
/3 0 -1 - /31
0 1 10
/3 10
/3→
cj 300 225 100 0 0 0 ω ω ω
75+ 7 7
3 5 ω - −ω −ω 25-
zj 300 150- ω ω 12 2 ω ω
2 4 25 ω
zj-cj 0 3 -25+ 7 −ω −ω 19 0 0
-75- ω 5 ω- 25-
2 ω 12 2
4 25 ω
↑
300 y1 1 ¾ 0 -1/6 0 ¼ 1
/6 0 -¼ 5
/6 10
/9
38
/33
ω y8 0 11
/4 0 1
/6 -1 ¼ -1/6 1 -¼ 19
/6
→
1 1 10
100 y9 0 -1 1 /3 0 -1 - /3 0 1 /3 -10/3
cj 300 225 100 0 0 0 ω ω ω
50 50
125+ - + -25+ + 25-
11 3 ω 6 ω
zj 300
ω 100 −ω ω
ω ω
4 4 4
4 6
 zj-cj 0 -100+ 0 50 −ω -25+ 50 0 25-
11 - + ω - 5ω
ω 3 6
4 ω 4 7ω 4
↑ 4 6
17 3 2 7
3 2 1
300 y1 1 0 0 - /11 /11 /33 - - -
66 11 11 33
-
4 4 1
2 4
1 38
225 y8 0 1 0 /33 /11 - /11 - /33
11 33 11
-
100 y9 0 0 1 15
/33 4 - 10
/11 - 13
/11 4
/11 10
/11 148
/33
11
cj 300 225 100 0 0 0 ω ω ω
- -
300 400 175 350 400 175
zj 300 225 100 -
66 11 11 33 11 11
zj-cj - - 350 - 175 -
300 400 175 400
0 0 0 - 33 −. ω11
66 11 11 11
ω ω

Since all si ≤ 0, the optimal solution has been obtained in the above tableau. The optimal
−1 38 148
solution is y1= , y2 = and y3 =
33 33 33

−1 38 148
Minimize z* = 300 × + 225× +100 ×
33 33 33

8550+14800−300 23350−300 23050

= = =
33 33 33

= 698.4848

Z* = 698.4848

Fields where Linear Programming can be used

The problem for which linear programming provides a solution may be stated as :
Maximize (or Minimize) some dependent variable which is a function of several
independent variables, when the independent variables are subjected to various
restrictions. The dependent variable is usually some economic objective such as profits,
production, costs, workweeks, tonnage to be shipped etc. More profits are generally
preferred to less profits and lower costs are preferred to higher costs. Hence, it is
appropriate to represent either maximization or minimization of the dependent variables
as one of the firm's objective. Linear programming is usually concerned with such
objectives under given constraints with linearity assumptions. In fact, linear
programming is powerful enough to take in its strides a wide range of business
applications. The applications of L.P.P are numerous and are increasing every day. L.P
is extensively used in solving resource allocation problems. Production planning and
scheduling, transportation, sales and advertising, financial planning, portfolio analysis,
corporate planning etc. are some of its most fertile application areas. More specifically,
linear programming has been successfully applied in the following fields:

a) Agricultural applications: Linear programming can be applied in farm

management problems so far as it relates to the allocation of resources such as
acreage, labor, water supply or working capital in such a way as to maximize net
revenue.

b) Contract awards: Evaluation of enders by recourse to linear programming

guarantees that the awards are made in the cheapest way.

c) Industrial applications: Applications of linear programming in business and

industry are of the most diverse kind. Transportation problems concerning cost
minimization can be solved using this technique. Te technique can be adopted in
solving problems of production (product-mix) and inventory control as well.
Thus, Linear Programming is the most widely used technique of decision making
in business and industry in modern times in various fields as stated above.

Limitations
1) There is no guarantee that linear programming will give integer valued equations.
For instance, solution may result in producing 8.291 cars. In such a situation, the
manager will examine the possibility of producing 8 as well as 9 cars and will take
a decision which ensures higher profits subject to given constraints. Thus, rounding
can give reasonably good solutions in many cases but in some situations we will
 get only a poor answer even by rounding. Then, integer programming techniques
alone can handle such cases.
2) Under linear programming approach, uncertainty is not allowed. The linear
programming model operates only when values for costs, constraints etc. are
known but in real life such factors may be unknown.
3) The assumption of linearity is another formidable limitation of linear programming.
The objective functions and the constraint functions in the L.P model are all linear.
We are thus dealing with a system that has constant returns to scale. In many
situations, the input-output rate for an activity varies with the activity level. The
constraints in real life concerning business and industrial problems are not linearly
related to the variables, in most economic situations, sooner or later, the law of
diminishing marginal returns begins to operate. In this context, it can, however be
stated that non-linear programming techniques are available for dealing with such
situations.
4) Linear programming will fail to give a solution if management have conflicting
multiple goals. In L.P model, there is only one goal which is expressed in the
objective function.
Eg. maximizing the value of the profit function or minimizing he cost function, one
should resort to Goal programming in situations involving multiple goals.
All these limitations of linear programming indicate only one thing- that
linear programming cannot be made use of in all business problems. Linear
programming is not a panacea for all management and industrial problems. But for
those problems where it can be applied, the linear programming is considered a ver
useful and powerful tool.

ANALYSIS

Linear programming is a resources allocation model that seeks the best allocation
of limited resources to a number of competing activities. L.P has been applied with
considerable success to a multitude of practical problems.

The suitability of the graphical L.P solution is limited to variable problems.

However, the graphical method reveals the important result that for solving L.P
problems it is only necessary to consider the corner (or extreme) points of the solution
space. This result is the key point in the development of the simplex method, which is
an algebraic procedure designed to solve the general L.P problem.

Sensitivity analysis should be regarded as an integral part of solving any

optimization problem. It gives the L.P solutions dynamic characteristics that are
absolutely necessary for making sound decisions in a constantly changing decision-
making environment.

According to Ferguson and Sargent :

"Linear programming is a technique for specifying how to use limited resources
or capacities of a business to obtain a particular objective such as the least cost, the
highest margin or the least time, when these resources have alternative uses. It is a
technique that systemizes certain conditions, the process of selecting the most desirable
course of action from a number of available courses of action, thereby giving the
management the information for making a more effective decision about the resources
under control."

Since the objective of any organization is to make the best utilization of the given
resources, linear programming provides powerful technique for effective utilization
of these given resources under certain well-defined circumstances. For instance, an
industrial process consists of a number of activities relating to the capital invested and
the capital required for operational activities, products to be produced and marketed,
raw materials to be used, machines to be utilized, products to be stored and consumed
or a combination of the above activities. Some or all of these activities are
interdependent and inter-related so that there are many ways where by these resources
can be allocated to various competing demands. Linear programming helps the decision
maker in arranging for such combination of resources which results in optimization of
objectives.

Linear programming method was first formulated by a Russian mathematician Shri.

L.V. Kantorovich. Today, this method is being used in solving a wide range of practical
business problems. The advent of electronic computers has further increased its
applications to solve many other problems in industry. It is being considered as one of
the most versatile management techniques.

The simplex method shows that a corner point is essentially indentified by a basic
solution of the standard form of linear programming. The optimality and feasibility
conditions of the simplex method that, starting from a feasible corner point (basic
solution), the simplex method will move to an adjacent corner point which has the
potential to improve the value of the objective function. The maximum number of
iterations (basic solutions or corner points) until the optimum is reached is limited by
n!/[(n-m)!m!] in an n-variable m-equation standard L.P model.
 The special case of alternative optima point to the desirable adoption of one
optimum solution over another, even though both may have the same optimum
objective value depending, for example, on the activity "mix" that each solution offers.

An unbounded optimum or a solution space, as well as a non-existing solution,

points to the possibility that some irregularities exist in the original formulation of the
model. As a result, the model must be checked.

The optimum tableau offers more than just the optimum values of the variables.
Additionally, it gives the status and worth (shadow prices) of the different resources.
The sensitivity study shows the resources can be changed within certain limits while
maintaining the same activity mix in the solution. Also, the marginal profits/costs can
be changed within certain ranges without changing the optimum values of the variables.

The Four Steps Involved in the Simplex Method

Step 1: Select the column with the highest plus value

Evaluation of the last row in the initial tableau represents the first step in the
computational procedure for the above maximization problem. The final row is the net
contribution that results firm adding one unit of variable (product) to the production.
The Cj+ Cj row reveals that the largest positive value 20. A plus value indicates that a
greater contribution can be made by the firm by the including this variable (product) in
the production activity. A negative value would indicate the amount at by which
contribution would decrease if one unit of the variable for that column were brought
into the solution. The largest positive amount in the last row (indicated by ↑ as an
inclusion variable) is selected as the optimum column, since we want to maximize the
total contribution. When no more positive values remain in the c j – zj row and the
values are zero or negative in a maximization problem, the total contribution is all its
greatest value.

Step 2 : To determine the replaced (old) row.

Once the first simplex tableau has been constructed and the variable (key column) has
been selected which contributes the most per unit, the second step is to determine which
variable should be replaced. In other words, inspection of the key column indicates that
the variable x1 should be included in the product – mix, replacing one of the variable x 2,
x5 or x6. To determine which variable will be replaced, divide the value in the P 0 column
P oi
by the corresponding coefficient in the optimum column. That is, calculate Qi =
x oi

Select the row with the smallest non – negative quantity ( θ=min θi) as the row to be
replaced (indicated by →)

Having selected the key column and there placed row, we can now work on an
improved solution found in tableau II. The element common to the key column and the
replaced row is said to be pivotal element (indicated by ) and the elements common
to the key column and the remaining row are called intersectional elements.

Step 3: Computation of values for the replacing (new)row.

In the next step, the first row (elements) to determine in the second tableau is the new x 1
(replacing) row for x4 (replaced) row. The elements of the x1 row are computed by
dividing each value in the replaced row(x 4) by the pivotal element. These become the
values for the first row x 1 in tableau  . In our illustration, we divide the elements of x 4
row by 12 to get the new elements of x1 row.

Step 4 : Calculate new values for the remaining (rows)

The fourth and the final step in the computational procedure is to calculate all new
values for the remaining row(s). The formula for calculating these new elements of row
is:

( )
former element
¿ the remaining −¿
row
 = (New Value)

For example, in our illustration, the first element (new) in the x5 row is = 6 - [6 ×1] = o

Similarly, the other elements in the x 5 row are calculated. Having completed the
computation of these values, we proceed to calculate the values for z j and ∆ j = cj – zj.
jn
The formula for calculation of zj is, z j =∑ c i x ij j = 1, 2, ……, n
i=1

Where xij are the elements of the body and the unit matrix for example, in tableau I;

zj = 20 × 1 + 0 + 0 = 20

These steps complete the computations involved for obtain the second tableau from
the first one.

We continue this process, when ∆ j are less than or equal to zero. If all ∆ j are less
than or equal to zero, then the computational procedure has come to an end and the
solution (basis) of the last tableau is the optimal solution. If one of the ∆ j is positive,
we shall have to compute the next tableau (in the same way as before: step 1 to 4) until
all ∆ j ' s are less than or equal to zero in our above example, since c j – zj (=∆ j)
corresponding to P1 column is large positive (4), we shall then compute the third, 4 th
and 5th simplex tableau in the same fashion.

We shall now consider solving a minimization problem using the simplex

procedure. Procedure adopted to solve a minimization problem is the same as that of
maximization, except for the last row. Here ∆ j = zj – cj, instead of cj – zj and the test for
optimality is the same as the one used for a maximization problem.

METHODOLOGY

The method of this project is by collecting data as much as possible and analyzing
it. By this analysis, we can understand that importance and use of Linear Programming
Problem in mathematics. It is decided to observe and collect various books in our
library. Net sources, books and instruments are my teaching aids. We can conclude the
project by knowing the various purposes and brief sketch of linear programming.

CONCLUSION

From this project we came to a conclusion that 'Linear programming' is like a vast
ocean where many methods, advantages, uses, requirements etc. can be seen. Linear
programming can be done in any sectors where there is less waste and more profit. By
this, the production of anything is possible through the new methods of L.P. As we had
collected many datas about L.P, we came to know more about this, their uses,
advantages and requirements. Also, there are many different ways to find out the most
suitable L.P.
Also, we formulate an example for linear programming problem and done using the
two methods simplex method and dual problem. And came to a conclusion that L.P is
not just a technique but a planning the process of determining a particular plan of action
from amongst several alternatives. Even there are limitations, L.P is a good technique,
especially in the business sectors.