UNIT 6 LINEAR PROGRAMMING

- SIMPLEX METHOD
Structure
6.1 Introduction
Objectives

6.2 Simplex Method

6.2.1 Mechanics of Simplex Method
6.2.2 Simplex Computation in Tableau Form
6.2.3 Simplex Method with Several Decision Variables

6.3 Formulation of Some Engineering Problems

6.4 Big-M Method and Two Phase Method
6.4.1 Big-M Method
6.4.2 Two Phase Method

6.5 Unbounded Solution, Alternative Optima and Degeneracy

6.5.1 Unbounded Solution
6.5.2 Alternative Optima
6.5.3 Degeneracy

6.6 Dual Simplex Method

6.7 Summary
6.8 Key Words
6.9 Answers to SAQs

6.1 INTRODUCTION
In Unit 5, y o p v e already learnt graphical method for solving linear programming problems.
THO variable problems can be easily solved by graphical method. As the number of decision
variables increase beyond two, the graphical method becomes cumbersome, if not impossible.
Usually engineering and econonlic problems involve several decision variables, therefore, it
becomes necessary to adopt an algebiic method to solve these problems. This is accomplished
by using Simplex Method.
In this unit the basic principles involved in Simplex Method are explaimd. However, two variable
problems are taken only for the purpose of having access to graphs and thereby making it easier to'
grasp the mcepts involved In certain cases where surplus variables are used for changing "greater
than or equal to" type of inequalities into equations, it becow necessary to use artificial variables.
The resulting equations are solved by TWOPhase Method or Big M Method for uptimising the
objective fimction Subsequent to this, fomuhtion of simple enginem@ problems in the area of
conshruction industry and power plants are included. Every linear progtaxmhg problem has a dual
associated with it. The variables used in dual are costs of r e s m and therefore has good
economic mterpxetation Lastly, the degeneracy, alternative optima and unbounded solution are also
explained. Linear programming also lays the basis for the integer progmmmhg.
Objectives
After studying this unit, you should be able to
identify underlying principles of simplex method,
formulate linear programming models for engineering problems,
carry out simplex computation in tableau form,
solve the linear programming problem with reasonable number of decision
variables which can be handled manually,
outline the principles involved in Big-M and Two phase methods,
describe unbounded solution, alternative optima and degeneracy, and
describe dual simplex method.
 -

6.2.1 Mechanics of Simplex Method

For any linear programming problem there are a set of basic feasible solutions. These set of
basic feasible solutions are the extreme points on the feasible region and not the whole
feasible region (which has infmite set of solutions). The general idea of the simplex method
is to move from one basic feasible solution to another basic feasible solution such that the
new basic feasible solution has a better objective function value associated with it. This
process is repeated, till no further improvement in objective function value is obtained. This
extreme point on the basic feasible solution corresponds to optimal solution.
For any given feasible solution, the difference between the L.H.S. and the R.H.S. of a
constraint is called the amount of slack for "<" inequalities and surplus for "2" inequalities.
For the sake of computation, it is necessary to introduce an additional variable into each
constraint. These variables are called slack and surplus variables. The mechanics of simplex
method can the best explained by going through a problem and solving it step by step.
Let us take following maximization problem.
Example 6.1
Maximize z = 4x1 + 5x2
Subject to : 3x1 + 2x2 I 6

Let us change the inequality into equations by using the slack variables.
Constraints are as follows :

z - 4x1 - 5x2 = 0 ( objective function equation )

Initial feasible solution could be XI = 0, x2 = 0, which refers to origin.
Therefore x3 = 6, and m = 5 ,here m & m are the basic variables where xi & x2
are non-basic variables. The value of the objective [unction z = 0, when
XI = 0.12 = 0. Is this solution optimal solution? It is not possible to increase the
value of objective function by changing the basic variables, because the solution in
terms of basic variables is unique. However, by increasing the value of non-basic
variables, the value of objective function will change.
If we set x2 = 1, z increases by 5 and if we set XI = 1, z increases by 4. By
increasing XI or n,we can increase z, therefore, (x3 = 6, m = 5 and xi = x2 = 0) is
not optimal. Thus, there may exist the extreme point with higher value of z. We
cannot jump straight to the optimal solution that is the one with the highest value of
z. Simplex method proceeds in small steps by moving to an extreme point adjacent to
current one but with a higher value of objective function.
Such an adjacent point can be found by replacing one of the basic variables (m or m)
with one non-basic variable (XIor x2); i.e. by changing basis. Therefore, we frrst
choose the non-basic variable to bec new basic variable or to enter the bdSis.
Then we find which of the old basic it replaces or variable which leaves the
basis.
A logical choice for the variable to enter the basis is the one that gives greatest per
unit increase in z, i.e. the variable with the most negative coefficient in the objective
function equation. In this problem, this is x2 with a coefficient of -5 and hence, each
unit of x2 increases z by 5, so we should increase xz as much as possible. The largest
value which x2 can assume depends on what happens to the values of the other
variables.
Now, we can find n in terms of x3 and a, wmrprmning
-
Simplex Methodl

It is evident from above equations, as x2 increases both x3 and x4 decreases. Neither

x3 nor x4 can be permitted to become negative. l'berefoce, x2 must not increase
beyond the value that fust reduces one of them to zero.
If X3=0 If M=O

Thus,the largest value x2 may assume is

x2 = Minimum [ 3, 1.25 ] = 1.25
At this point nq = 0, while x3 = 3.5. So nq leaves the basis to become a non-basic
variable. This solution corresponds to extreme point B in the Figure 6.1 with
x2 = 1.25, x3 = 3.5 and x i = nq = 0. This point is indeed adjacent to point A, by
increasing m from 0 to 1.25, we move along the edge from point A to point B.

Next step iq to find the set of equations in canonical form for this new solution, with
x2, x3as the new basis and x i & x4 as the non-basic variables.

We divide second equation by 4. Then eliminate x2 from the first equation by

substracting 2 times the new second equation from the first equation. The new
objective function is found by substracting -5 times the new second equation from
the old objective function equation.

We can now read the value of basic variables as x3 = 3.5 and x2 = 1.25;
corresponding value of z from above equation is 2514, i.e. an increase in z of 5 for
OptimizatioeTechniques-I each unit increase in x2 gives 5 x 1.25 = 6.25. This completes first cycle of the
Simplex Method.
Here, we see unit increase in xl increipes z by 312 while unit decreases in m
decreases zby 514. Since z can be increased further therefore above solution is not
optimal solution.
Now we have to find which of the current basic variables x2 and x3 is to leave the
basis. Using the same logic as in the first cycleliteration,
XI =(3.5-~3)/2 or Xs=3.5-2~1

xl = Minimum [ 2.50, 1.75 ] = 1.75

When X I = 1.75, = 0, therefore variable leaving the basis is a .The equations in
canonical form are

These equations are obtained by dividing first equation by 2. Then eliminating x i

from 2nd equation by subtracting 0.5 times the new first equation from 2nd equation.
9

New objective function is obtained by subtracting - times the new first equation
2
from objective function.
Here, we see that objective function cannot be increased beyond this as increase in
x3 and m are going to decrease objective function. Therefore, this solution is an
optimal solution, with value of x i = 7/4, x2 = 3A and z = 7Cg.
6.2.2 Simplex Computation in Tableau Form
The computations of the simplex method are most conveniently performed in a tableau
structure known as simplex tableau. The simplex tableau for initial basic solution for slack
variables for Example 6.1 is shown in Table 6.1.
Table 6.1

Variable t xq 5
leaving

? Variable entering

The first two rows are for reference purpose only. The top row has the values of the
coefficient of objectives function for each variables xi. The c, column in the extreme left of
row second is for the objective function coefficient for basic variables. These coefficients
are required to find the z, values. The basic variables are listed in second column of the row
second, i.e. after cj coefficient. 'Ihe column labelled solution contains the values of the basic Linear Progmmmbg
variables. 'Ihe column under the variable names gives the coefficient in the canonical form.
-Simplex Method
The row ( zj - cj ) corresponds to the z row of the Eq. (6.1). Now z, can be calculated by
multiplying each element in the Xj column by corresponding element in the Cj column and
summing over all rows, for example, z l = 3 .x 0 + 2 x 0.
First Iteration of Simplex Method
Non-basic variable x2 enters the basic because it has most negative ( Z, - c, ). The values of
the basic variables are the corresponding elements in the solution column and the aij
coefficients of x2 are the elements in column xz. To find the variable leaving the basis,
compute ratio of these two numbers for all ad > 0.Variable which has lowest value of sh,,
leaves the basis as is shown by an arrow ( t variable leaving basis ). Therefore, here x4
leaves the basis.
The Table 6.1 is transformed into the c anonical form corresponding to new basic variables
as shown in Table 6.2.
Table 63

4 5 0 0 Ratio

Variable t
leaving
basis
2

4 2
t
variable entering

Table 6 3

Therefore, optimal solution is

7
xl = -
4'
x2 =
3
-
8'
with value of z = -.71
8
The pivot column is a column associated with variable entering the basis. The pivot row is a
row of the variable leaving the basis. The pivot element is &fined as the element that is in
both the pivot row and the pivot column. In Tables 6.1 and 6.2, these pivot elements are
encircled.
To get the tableau into the canonical fonn, we transform the pivot column, such that the
pivot element is equal to 1 and all other column elements are zero. n i s is done by
(1) The pivot row is transformed by dividing it by the pivot element.
(2) All other rows, including ( zj - Cj ) row, are transformed as follows :
If ai is the element in both the pivot column and row i then row i is transformed by
subtracting ai times the transformed pivot row from row i.
Tables 6.2 and 6.3 give 2nd and third (final) iteration for the problem. Now, let us look
into the tables afresh.
Step I
To calculate element of row zj - cj. First zj is calculated.
Calculated by multiplying the coefficients of each variable in a column by
conesponding Cj value (i.e., coefficient of objective function)then subtracting the
resulting value from corresponding cj values.

.= z4-c4= 0
Therefore, elements of zj - cj row are 4,
-50.0.
Step I1
Most negative value of elements of ( zj - C j ) is obtained, i.e.

therefore, x2 will be entering variable which is shown by an arrow ( variable

entering ).
Step IU
Ratio of coefficient of variable entering (i.e. the coefficient of variable x;! in the
present problem) to the corresponding solutions (i.e. corresponding elements in
solution column) are calculated $9 and 5A.

Therefore, variable leaving the basis is m . This is shown by an arrow

( t variable leaving the basis )
Step IV
By above two steps the pivot element is 4 which has been encircled.
Divide this pivot row by 4 the resulting elements are as follows :

These elements can be entered in Table 6.2 corresponding to x2 row, cj value for n is
5 which should be entered in column cj .
Step V '

Obtaining elements of x3 row for Table 6.2. Multiply x2 row of Table 6.2 by 2,
resulting elements are

Subtract these elements from the corresponding elements of x3 row of Table 6.1.
6 3 2 1 0

Enter these elements in the x3 ROWof Table 6.2. This completes the first iteration.
 Second Iteration Liear Rognunming
- Simplex Method
step I
Calculate element of row (zj - cj).

Most negative value is - 3 h , therefore xi enters the basis which is shown by an arrow
( variable entering ).
Step I1
Xi
Compute values for the Ratio column (coefficient of - ).
aij

therefore, leaving variable is xs, which is shown by an arrow ( t variable leaving

basis ). Therefore, pivot element is 2 which is encircled.
Elements of Table 6.3 can be obtained by repeating similar procedure.
Step III
I
I Divide x3 row of Table 6.2 by 2. The resulting elements are
I 7 1,o.-1 --1
-
I 4' 2' 4
Enter these elements in xi row of Table 6.3. Note that the cj value corresponding to xi
variable is 4 therefore enter 4 as first element of cj column.
In order to obtain the elements of n Row of Table 6.3, multiply elements of xi Row
1
of Table 6.3 by - and subtract fromn row of Table 6.2.
2

Enter these value of xi row in Table 6.3.

Third Iteration
Value of d l zj - Cj > 0,therefore this is the optimal solution

Now we are in position to write the simplex criterion.

Variable Entering Basis
The v;.iable to enter the basis is one that is the most negative ( zj - cj ).
Optimality Criterion
A basic feasible solution is optimal if at all ( zj - cj ) 2 0 for the non-basic variables.
Variable Leaving the Basis
M i m u m value of the basic variable divided by the corresponding element (greater
than zero) which falls in the colwnn of entering variable.
opiimizdw 6.2.3 Simplex Method with Several Decision Variables
The simplex method explained by taking two decision variable in the previous section can be
readily extended to the linear programming problem with several decision vixiables. This is
illustrated by following example. Let us consider following maximization problem.
Example 6.2
Maximize z = 2x1 + 3x2 + 4x3
Subject to : 2r1+5x2+6~3 8

' X,,X2,X3 2 0
Solution
(1) Firstly, all the inequalities are changed into equations by introducing slack
variables, y,x5 and x6.

5 ~ 1 + 3 ~ 2 + h 3 + ~=6 4

Table 6.4

CJ
2 3 4 0 0 0
Ratio
CJ Ba& Solution xl x2 x3 x4 xS 3%

Leaving t 0 a 8 2 5 1 0 0 -8 -- -4
variable 6 3

0 Xg 6 3 6 4 0 1 0 -6 - -3
4 - 2
0 xg 4 5 3 2 0 0 1 4
- = 2
2

( zj - cj ) -2 -3 -4

? Entering variable

(2) Most negative value of ( zj - cj ) from Table 6.4 is 4 therefore x3 becomes the
entering variable.
(3) Calculate the elements of "Ratio" column. This is done by dividing elements of
the solution column by the corresponding elements of x3 column. The rafio's
are 43,312 and 2
Minimum [ 4/3,3/2,2 ] = 4/3
Therefore, y becomes the leaving variable and 1st element of column x3 is the
pivot element which is encircled.
(4) Elements of first row of Table 6.5 are obtained by dividing each element by 6
which is the pivot element. rn is replaced by x3 in the basis.
(5) Element of Row 2 and Row 3 of Table 6.5 are obtained in the following way.
Elements of 2nd Row
Multiply elements of Row 1of Table 6.5 by 4 and subtract these from corresponding
elements of Row 2 of Table 6.4. Thus, we have,
6 3 6 4 0 1 0 ( Row 2 of Table 6.4)
(- 16# 4/3 20/6 4 4/6 0 0 ( Row 1 of Table 6.5
multiplied by 4)
213 5t3 1616 0 -416 1 0
 After subtracting these two rows above, the resulting elements as shown above are as -proy.mming
follows :
- Shnplex Method
213,513,813,0, -2J3.1,O
These elements become the elements of Row 2 of Table 6.5. Similarly, elements of
Row 3 of Table 6.5 are obtained.
Thus, multiplying elements of Row 1 of Table 6.5 by 2 and subtract these elements
from the corresponding elements of Row 3 of Table 6.4, we have,
4 5 3 2 0 0 1 (Row 3 of Table 6.4)
(-) 8/3 2J3 1016 2 2J6 0 0 (Row 1 of Table 6.5
multiplied by 2)
413 1313 413 0 ;2/6 0 1
Enter these elements as elements of Row 3 of Table 6.5.

Table 6.5

c1 2 3 4 0 0 0

c1 Basis Solution xl x2 x3 x4 xs x6 Ratto

4 X3 4'3 . 1/3 5/6 1 1 / 6 0 0 4

x5 % s/, 44 0 -Y3 1 0 2/5

O
Leaving t 0 xg 4'3 0 - Y3 0 1 4'1 3
variable
( q - cj -Y3 Y6 0 y6 0 0

f Entering variable

(6) Caluculate ( zj- cj ) values for Table 6.5 as usual, the values are -2/3,2/6,0,
416,0,O. Most negative value being -W3, so the entering variable will be XI.
(7) Calculate the elements of Ratio column. These are 4,2/5 and 4113.
Minimum [ 4,2/5,4/13 ] = 4/13
Therefore, leaving variable is XI. This comple'tes the first iteration.

Table 6.6 :0~tIma1Solutlon Table

CJ 2 3 4 0 0 0

CJ Basis Solution xl x2 x3 x4 xs x6 htio

4 X3 1% 0 51/13 1 15h8 0 - 1/13
0 x5 Y13 0 2%3 0 -%3 1 -%3

2 x1 4'13 1 4/13 0 -Yl3 0 %3

(q-cj) 0 19?43 0 4sng 0 %

Xl = 2, x2 = 0, x3 = 4 ; z = 20
Similarly repeat the calculations for second iteration. We see in Table 6.6 that
all ( zj- C, ) values are greater than or euqal to zero. Therefore this is the
optimal solution table.

SAQ 1
Maximize z= 151 + 3 ~ 2 + y ~
Subject to : lOyi+2y2+~3I 100
 Himalayan Orchards have canned apple and bottled juice as its products with profit
margins of Rs. 2 and Re. 1 respectively per unit. The following table indicates the
labour, equipment and material to produce per unit of each product.
Bottled Canned Total
Juice Apple Resources
Labour (manhours) 3.O 2.0 12.0
Equipment (machine hours) 1.0 2.3 6.9
Material (unit) 1.O 1.4 4.9
Find by simplex method the product m i x which will maximise the profit.

SAQ 3
A company manufactures three products using three types of inputs A, B and C in
different proportions. The following table gives the requirements of various inputs
(in kg) per kilogram of the three products.

1 4 8 8
Roducts 2 4 6 4
3 8 4 3
The three profit coefficients are CI = 20, C2 = 40 and C3 = 10. The company has 800
kg of input A, 1800 kg of input B and 500 kg of input C. Find out the product mix
which will maximise the profit. What is the maximum profit ?

6.3 FORMULATION OF SOME ENGINEERING

PROBLEMS
Example 6.3
A construction company requires a large amount of ravel and sand. The
requirements are 1000 m3 of coarse gravel, 2000 m3gof f i e gravel and 1000 m3 of
fine sand. There are two pits P and Q from which the above material can be obtained.
Analysis Shows that material at each pit has following composition :
Material PltP pit Q
Coarse gravel 15% 35%
Fine gravel 20% 40%
Fine sand 30% 15%
Coarse sand 35% 10%
It costs construction company Rs. 10/m3for material and handling from Pit P and
Rs. 15/m3from Pit Q. Formulate the linear programming model.
Solution
Let XI be the unit of material taken from Pit P and m be the unit of material taken
from Pit Q.
From the compasition of the material in the each pit, the coarse gravel contained in
Pit P is 15%. while in Pit Q is 35%. Here, we have taken decision variables as XI and
x2 where XI refers to how much quantity from Pit P will be taken and xz refers to how
much quantity from Pit Q.
Therefore, the L.H.S.of first constraint equation will be,
 This quantity should be greater than or equal to the requirement, which is Linew Pmgrnmming
1000 m3.
- Simplex Metbod

C
Therefore, 0 . 1 5 ~+0.35x2
1 2 1000
Similarly, constraint for fine gravel will be,
0.40~22 2000
0.20~1+
Constraint for fine sand will be,
0 . 3 5 ~+~0 . 1 0 ~r ~I ( K X )
Objective function will be as follows :

Writing the objective function and set bf constraints again as a linear programming
model.
Minimize z = 10x1+ 15x2
Subject to : 0.15~1+ 0.35~22 1000

0.35x1+0.10~22 1000
With non-negativity constraint X I , x2 2 0
Example 6.4
At a particular location, some units of 2,3 and 4 bedroom houses are to be
constructed. A construction company can take its choice on the number of houses of
2,3 and 4 bed rooms to be constructed. One of the construction companies wants to
establish number of each house to be constructed, so as to maximize the profit
subjected to :
( 1 ) Total number of units shall be at least 240.
t2) The total budget is limited to 35 million Rupees (Rs. 35 x lo6).
(3) Building costs and profits by sales are as follows :
UrJIT (TYP) Cost (B.) .Net Profit (Rs.)
2 bed room 100,000 7000
3 bed room 120,000 10,000
4 bed room 150,000 12,000
(4) The maximum type of each unit based on market analysis is as follows :
2 bed room units = 70% of total,
3 bed rmm units = 20% of total,
4 Ikd room units = 10% of total.
Formulate this as a linear programming problem.
Solution
Let xi be the number of 2 bed room units to be constructed,
x2 be the number of 3 bed room units to be constructed, and
x3 be the number of 4 bed room units to be constructed.
Constraintfor total number of units to be constructed
xi + x2 + x3 2 240
Cost constrainr
Maximum money which can be spent on the poject being Rs. 35 x lo6, the total cost
should not exceed Rs. 35 x lo6
Cost of 2 bed room units = 100,000X I
Cost of 3 bed room units = 120,000 x2
Cost of 4 bed room units = 150,000 a
 Therefore,
1 2 0 x 2 + 150@lOx3I 35 x lo6
l~~OOOxl+
Demand constraint
Number of 2 bed room units are 70% of total, so
Xl = 0.7(x1+xz+x3)
Similarly, of 3 bed room, 4 bed room units demand conditions are as follows,

x3 = 0.10 ( X I +x2+x3)
Objectivefunction
Net profits are to be maximized. merefore, z = 7000x1 + 10000x2 + 12000x3
So, formulated linear programming problem is as follows :
Maximize z = 7000x1 + 10000x2 + 12000X3
Subject to : X I + x2 + x3 2 240

10000(2111+1 2 0 x 2 + 150000x3 I 35 x lo6

x2 = 0.20(x1 + ~ 2 + ~ 3 )

X3 =O.~O(X~+X~+X~)
With non-negitivity constraint X I ,x2, m 2 0
Example 6.5
A coal-fed electrical power plant uses two types of coal, i.e. grade A and grade B.
The thermal value in terms of steam produced is higher for Coal A than for Coal B.
Coal A produces 12000 kg of steam per ton while Coal B produces 10,000 kg of
steam per ton. The Coal A is hard Coal. The pulverizer unit can handle at most 12
tons of Coal A per hour whereas it can pulverize upto 20 tons of Coal B per hour.
The conveyor loading system has a capacity of 20 tons per hour regardless of which
coal is loaded. Emission of pollutants from Coal A and Coal B are as follows :
Coal Sulphur oxides Particulate emission
(emkionJton)
A 1700 ppm 0.75 kg
B 3700 ppm 1 .o kg
Safe values of the emission as per the air pollution control laws are as follows :
Sulphur oxide emission 3000 PPm
Particulate emission 12 kgihour
For the given grade of coals, its details, and pollutant emission restrictions from point
of view of pollution of air, formulate this as a linear programming problem, which
could be used to find out the maximum possible output of electricity of the plant.
Solution
Let X I be the amount of Coal A used per hour, and
x2 be the amount of Coal B used per hour.
Objectivefunction
Output, i.e. electricity is to be maximized without violating any of the constraints.
Since the electricity is produced through steam, maximizing electricity output is
equivalent to maximizing steam output.
Steam produced per hour by Coal A = 12,000 xi
Steam produced per hour by Coal B = 10,000 xz
Therefore, objective function will be as follows :
Maximize z = 12000x1+ 10000x2
Constraints
Particulate Emission
The maximum amount of smoke that the plant is allowed to emit per hour is
---
- Simplex Method

restricted to 12 kg. Each ton of Coal A produces 0.75 kg of smoke while each ton of
Coal B produces 1.0 kg of smoke. If plant burq xi tons of Coal A and x2 tons of Coal
B, the total amount of smoke emitted by both the coals is,
0.75x1+ 1.0~2
which should not exceed 12 kg.
Therefore,

Loading
The conveyor system conveying coal to the pulverizer has an hourly capacity of
20 tons. Thus, total coal conveyed per hour is equal to the sum of two decision
variables.
Therefore,

Constraint on pulverizer unit

Pulverizer can handle 12 tons of Coal A per hour while it can handle 20 tons of Coal
B per hour. If the solution demands the-combinationof the both coals which would
mean some fraction of Coal A and Coal B will be used. This can be introduced as a
constraint by translating rates into lengths of time.
1 1
It would take -of an hour to pulverize one ton of Coal A and -of an hour to
12 20
pulverize Coal B. The combinations of xi and x2 which require at the most 1 hour of
time are admissible. Therefore,

Sulphur oxide Emission

Maximum sulphur oxide emission should not exceed 3000 ppm. If X I tons of Coal A
and x2 tons of Coal B are used per hour, then, x i / ( x i + x2 ) of the mixture is Coal A
with sulphur oxide emission rate of 1700 ppm and & ( X I + x2 ) of it is Coal B with
an emission rate of 3700 ppm.
Weighted average emission rate I 3000

Therefore, this linear programming problem can be reduced to,

Maximize z = 12000x1 + 10000x2
Subject to : 0.75x1+ x2 I 12
SAQ 4
A brick company has three plants with capacity of 20 units, 3 0 units and 40 units. It
has to supply bricks to four construction companies at different locations. The
transportation cost and demands are shown in Table 6.7. Formulate the problem as
linear programming model.
Table 6.7

Construction A B C D Capacity
companies of Plants

1 90 130 80 140 20

2 110 105 1 25 80 30

3 1 20 100 110 130 40

Demand from
construction 15 30 20 25
companies

6.4 BIG-M METHOD AND TWO PHASE METHOD

6.4.1 Big-M Method
When the constraints contain "greater-than-or-equal-to" type of inequality, surplus variables
are used to change the inequality into equation. However, the resulting equation may not
lend itself to the easy basic feasible solution, where some of the decision variables are
equated to zero, the other variables which go in basis have non-negative value.
,To avert this difficulty, artificial variables are used and the objective function is augmented
by reducing a big number times the artificial variables. The outstanding feature of the
Big-M Method is that the method itself can be used to generate an initial basic feasible
solution or it can indicate that problem has no feasible solution. This can be illustrated with
help of the following examples.
Example 6.6
Maximize z = 4x1 + 5x2
Subject to :

Solution
Let us change these inequalities into equations as shown below by using the surplus
variables,

where x3 and are slack variable and x5 is surplus variable. Note that the last
constraint can be changed into the less-than-or-equal-to type constraint by
multiplying by -1 throughout. However, this has not been done here.
 Linear Programming
Now, if X I and xz are equated to zero and if the last constraint had any number other
than zero on the R.H.S. this would result in m and x4 with value of 6 and 5
-S i p l e r MeUaod

respectively and x5 with some negative value (if the coefficient on the R.H.S side was
other than zero). So, in general, another variable known as the artificial variable is
added to the last constraint equation.
Therefore, constraints are as follows :

Now, if X I , x2 and x5 are equated to zero, we get initial feasible solution of the
augmented problem where x3 = 6, m = 5 and a = 0 and the new objective
function will be z = 4x1 + 5x2 - 1MX6.
The problem has been solved through Table 6.8 to Table 6.11. First of all, artificial
variable is taken out of basis. The idea of penalising the objective function by
subtracting a big number times the artificial variable is not to allow the artificial
variable to reenter the basis.
The optimal solution to the augmented problem is optimal to the original problem if
there are no artificial variables with non-zero value in the optimal solution. If any
artificial variable is in basis with non-zero value at the optimal solution of the
augmented problem, Ulen the original problem has no feasible solution.
Now the linear programming problem can be rewritten as follows :

I Maximize z = 4x1 + 5x2 - IVh6

Subject to :

4x1-xz-x5+~g = 0
Here, x3 and xll are slack.variables, xs is a surplus variable and a is an artificial
variable.
Table 6.8

Cj Basis Solution x l X2 X3 X4 XS X6

0 X3 6 2 3 1 0 0 0 -6= 3
2

? Variable entering

Table 6.9

Cj Basis Solution XI x2 X3 X4 XS X6

t 0 xg 6 0 I 0 1/2 -112 1m

I (q-cj) 0 -6 0 0 -1 1+M 1
? Variable en&ng
 Table 6.10
- -

Ci 4 5 -M
Cj Basis Solution xl x2 x3 x4 xs X6

5 12 1217 o 1 2n o i n -in -12

x - =7 12
7 1
0 4 5f7 0 0 -517 1 @ -1n -5x - =75
7 1
4 xl 3fl 1 0 1114 0 6
28 28
(Zj-cj) 0 0 1217 0 -117 z7 + M
Variable entering
Table 6.11 :Optimal Solution Table
- -

Ci 4 5
Cj Basis SO~U~~OK
XI I ~2 XJ ~4 ~5 X6

5 x2 1 0 1 1 -1 0 0
0 XS 5 0 0 - 5 7 1 -1
4 XI 312 1 0 -1 312 0 1114
0 0 1
2
( Zj - cj ) 1 0 -+M
7

3
xi = -, x2 = 1 and z = 11.
2
Since the problem involves only two decision variables, it can also be solved by
graphical method. Figure 6.2 shows the graphical solution of the problem Following
table gives the value of objective function at all extreme points on the convex set :

Extreme points on convex set Value of

Point XI value x2value Objective Remarks
Function
A 0 0 0
D 2.5 0 10
C 1.5 1 11 Optimal value
B 0.425 1.7 10.2
 Linear Progmmmhg
6.4.2 Two Phase Method -Simplex Method

In this method, artificial variable are removed in phase-1. In fact, phase-1 is meant to
generate the initial basic feasibk solution This is done in following way.
In the phase-1 of the method, a separate objective.function is derived which assigns each
artificial variable an objective function coefficient of -1 and each true variable, a coefficient
of 0.By optimizing this new problem (i.e. with the changed objective function), we force
the artificial variables to leave the basis.
If for the original problem a basic feasible solution exists, then the phase-1 terminates with
artificial variables having negative or zero value. In phase-11, the original objective function
coefficients are used, however, at this stage there will be no artificial variable in the basis.
Therefore, phase-11 leads to the final optimal solution.
Let us consider following linear programming problem.
Example 6.7

Subject to :

Xl, X2 2 0
Let us change these iriequalities into equations by using the x3, y (slack variables),
xs (surplus variable) and xs ( f l t c i a l variable).
Therefore,

4x1-x2-x5+x6 =0
Objective function for phase-1, will be

Note that coefficient of all true variables in the objective function have been assigned
zero value whereas the -cial variable has been assigned -1.
The first Si~pplextableau, Table 6.12 is same as used earlier with only difference that
two top rows have cj and Fjcoefficient. The upper most, i.e. cj refer the coefficient of
objective function of the original problem while 5 ; i the coefficients of the new
objective function (for phase-1). Accordingly, (zj- cj) is @ - Fj) for the phase-1. It is
worthwhile to carry out the calculations of the row (zj- cj) because once the phase-1
terminates, then these values have to be calculated once again to start the phase-Il
calculations. From the Table 6.12, we note that the x i is the entering variable since
(Zj - Ej) being most negative value (-4),which pushes xs out.
In next iteration, you will find that value of (Zi - F,) for all variables is greater or
equal to zero. Therefore, this terminates the phase-1. Now onwards Cj- Fj) can be
utilized for determiuing the entering variables.
Let us now solve the problem formulated in Example 6.7.
Example 6.8
Maximize 0x1 + + 0 ; r ~+ 0x4 + 0x5 - a
Subject to :
2xl+3x2+~3= 6
2x1+2x2+x4 =5
4x1-xz-xs+&j =0
Ncm-basic variables are xi, x2 and xs whereas m,a,xs are basic variables.
 Leaving
variable
t
1: -1
*
xg

( Zj - Cj )
0
0
A2
4
- 4
-1
-
0
5 0
0
0
-1
0
l;i2.5
0
(3-5) 0 - 4 1 0 0 0
t
Entering variable

Table 6.13

3
' 4 5 0 0 0 0

0 0 0 0 '.O -1
Ci

ci ci Bask Solution xl x2 x3 x4 xs xs

0 0 X3 6 0 712 1 0 Il2 -112

0 0 x4 5 0 5l2 0 1 112 -112

4 0 XI ' 0 1 -114 0 0 -114 114

(q-cj) 0 - 6 0 0 -I 1
(G-3) 0 0 0 0 0 1

If you compare the Table 6.9 of the Example 6.6 solved by Big-M method with the
Table 6.13 of the Two Phase method, you will realise that two tables are similar.
Hence, herea€ter the procedure is same and the final optimal values are as follows :
XI = 3 4 x2 = 1 and z = 11.

6.5 UNBOUNDED SOLUTION, ALTERNATIVE

OPTIMA AND DEGENERACY
6.5.1 Unbounded Solution
In certain linear programming problems if the value of variables is increased indefinitely,
the constraints are not voilated. This mean that the feasible region is unbounded at least in
one direction. Therefore, the objective function value can be increased indefinitely. This
means that problem has been poorly formulated or conceived. This can be explained by
following illustrative example.
Example 6.9
Maximize z = 4x1 + 3x2
Subject to : XI 15

X l , X2 2 0
Let us change the inequalities into'equationsby ushg slack variables,

x l - x 2 + ~ 4 =8
The problem has been solved through Table 6.14 and Table 6.15.
 Y
Table 6.14

4 3 0 0
---
- simples M o d

Bnsls Solutlon XI *Z x3 x4 Ratio

=I

Leaving c
variable 0 x3 5 0 0 1 0 5

0 X4 8 1 -1 0 1 8

( Zj - cj ) -4 -3 0 0

? Entering variable
Table 6.15

'=l 4 3 0 0

=I
Bad8 Solution xi X2 x3 x4 Ratio

4 XI 5 1 0 510 = -
0 n4 3 0 1: 1 31-1 = -3

(zj-q) 0 -3 4 0

7
Entering variable

It can be seen from the Table 6.15, that Ratio column contains w or negative values.
Therefore, it is not pdssible to proceed from this step onwards.
If for one of the non-basic variables, the coefficients in its column are zero or less
than zero, then solution is unbounded. For example, the coefficients of variable x2 are
0 and -1, therefore, the solution is unbounded. The coefficient of variable are shown
by enclosing them in a small rectangle.
SAQ 5
Solve the following linear programming problem by simplex method and give your
comments.
Maximize 3x1 + 2x2
Subject to :

6.5.2 Alternative Optima

When the objective function is parallel to the binding constraint, the alternative optima
exists. As we are aware that in simplex method the extreme points on the feasible region
contains the optimal solution. Therefore, only the extreme points on the feasible region are
searched. In case of alternative optima, by simplex method one would get at least two
solutions with same value of objective function which correspond to the two extreme points
of binding constraints (for two variable problems). This has been explained with the help of
Example 6.10.
Example 6.10
Maximize z = 3x1 + 6x2
 Subject to :
Xl +xz I5
XI + 2x2 < 6
With non-negativity constraint x i , x2 2 0
Solution
Let us change inequalities into equations by using slack variables x3 and x4.

Xl+X2+X3 = 5
xl+2x2+~q= 6
Table 6.16

Ci 3 6 0 0

Basis Solution xl x2 x3 x4 Ratio

0 x3 5 1 1 1 0 511 = 5
#
Leaving
variable c 0 la 6 1 0 0 1 6/2=3

( Zj - cj ) -3 -6 0 0

t
Entering variable

Table 6.17 :Optlmal Solution Table (!)

I

Ci 3 6 0 0

CJ Basis SolutIon xl x2 x3 x4

0 x3 2 1n 0 1 -112

6 x2 3 1n 1 o i n \

(2.i-cj) FI 0 0 3

Here+x i = 0, x2 = 3 and z = 18.

Table 6.18 :Optimal Solution Table (2)

Ci 3 6 0 0

c, Basis SOIUHOII XI x2 x3 xq Ratio

3 XI 4 1 0 2 -1

6 XZ 1 0 1 -1 1

(~j-cj) 0 0 3

Now, x l = 4 , x2= 1, and z = 18.

When the objective function is parallel to the binding constraint, the alternative
optima exists. As we are aware that in simplex method the extreme points on the
feasibleregion contains the optimal solution. Therefore only the extreme points on
the feasible region are searched. In case of alternative optima, by simplex method
one would get at least two solutions with same objective function which correspond
,to the two extreme points of binding constraints (force two variable problems). This
has been explained with the help of Example 6.1 1.
Elgure 6.3 shows the graplhal solution of the above problem. It is evident from the
graph that the objective function line gh is parallel to tbe constraint BFE. 'Ihe
~~-0rdinates of the point B, F and E are as given under :
 variable xi variable x2 objective function (z) Linear Programming
- Simplex Method
point B 0 3 18
point F 4 1
point E 6 0

Therefore, point B, point F and point E which are the extreme points, they yield same
value of objective function. By inspection one can find that all points on line BE give
same value of objective function. Therefore, there are in fact M i t e number of
solutions possible for the above linear programming model. Looking into the Table
6.17 solution being xi = 0, x2 = 3 and z = 18 which corresponds to point B of
the graph, we find that the non-basic variables xi bas ( zj - cj ) value of zero which
would mean that even if it is introduced in basis, it is not going to result in the change
of objective function. This is shown in Table 6.18 where XI has become entering
variable and x3 as legving variable. The solution is x i = 4, x2 = 1 and z = 18, which
corresponds to point F of the graph as shown in Figure 6.3.

6.5.3 Degeneracy
A basic solution is called degenerate if the value of at least one of the basic variables is zero.
Othenvise, the basic solution is called non-degenerate.
After each iteration, the value of the objective function must increase, so that in finite
number of iterations one obtains the optimal value. But when a basic variable enters in
basis at zero value, the value of objective function does not change in that iteration. In
general, when simplex procedures would repeat the same sequence of iterations, never
improving value of objective function, this is called cycling. However, this type of problem
is seldom encountered in practical situation. The cycling can be averted by giving the basic
variable a very small non-zero value. If the value choosen is small, the effect on the
objective function is very small. This may be accounted over many iterations.
Let us consider following example to get an insight into the above mentioned concepts.
Example 6.11
Maximize z = 2x1 + 4x2
Subject to : XI+ 3x2 S 9
Xl+X2 13
With non-negativity constraint xi, x2 2 0
Solutlon
Let us change the inequalities into equations by using the slack variables.

were, x3 and x4 are the slack variables.

 Table 6.19

g 2 4 0 0

q Bat& Solution xl X2 x3 x4 Ratio

Leaving
variable c o rj 9 1 0 1 o 9n=3

0 Xq 3 1 1 0 1 311 = 3

(q-cj) -2 -4 o o
7
Entering variable

Table 6.24

4 2 4 0 0

Cl
Bads Solution XI x2 x3 x4 Ratio

4 m 3 1n 1 1n 0 -- 9
L5-
Leaving
variable c \ 0 Y 0 0 -1n 1 0

(~j-cj) -2/3 O 4/3 O

I'
Entering variable

Value of objective fuoction corresponding to this iteration is z = 12.

Value of non-basic variables of objective function x i = 0, x2 = 3.
Table 631 :Optimal Solution Table
-

Ej 2 4 0 0

CJ Basb Solution xl x2 x3 x4 Ratto

4 m 3 o 1 in -112

2 X1 0 1 0 -112 30

(zi-ci) 0 0 1 1

Table 6.21 is the optimal table with value of objective function z = 12 and the value
of variables arexi = 0 and x2 = 3.
Now, if we go into the details of the solution, following points are revealed :
(1) In Ratio column (extreme right column) of Table 6.19, there is a tie for
minimum ratio.
(2) In next iteration the value of one of the basic variable has become zero.
(3) Comparing Table 6.20 and Table 6.21, we frnd that value of objective function
is constant, i.e. z = 12.
(4) Again from Table 6.20 and Table 6.21, it is evident that variables in the basis
have changed without changing the solution being,
,XI = 0, x2 = 3 and z = 12.

In general, when there is a tie between minimum ratios, one or more basic variable in
next iteration have zero value. The new solulion is called degenerate solution.
This reveals that at least one of the constraints is redundant constraints. Figure 6.4
shows graphical soluticm of the problem. The solution shown in the figure is
X l = 0,X;! = 3, and z = 12.
 --
- simpla Method

The point which gives the optimal value is an extreme point on convex set. In this
case, it is point B. Here, we h o w that a point can be located by intersection of two
lines while at point B there are three distinct lines, viz. AB, BC and BD. Therefore,
the problem is overdetermined and one of the constraints is redundant.

6.6 DUAL SIMPLEX PROBLEM

For every linear programming problem, its dual can be written. This means that every linear
programming problem can be solved by two approaches. One formulating the problem in
same way as has been done in previous sections (which is known as primal), the other is the
concept of duality. These two problems stand as pair or duals. They bear a unique
relationship to each other. The dual simplex is used to solve a linear programming problem
when it reduces the amount of work in solving the problem You will realise that in
formulation of the dual, no artificial variables are required in certain situations. However,
dual has a particular application in the sensitivity analysis or post optimal analysis. The
variables used in the dual are the costs of the resources, therefore, it has a useful economic
interpretation and is widely used in economic theory.
Duality will be bestmrderst~T6rmulatinga linear programming problem, i.e. fust
formulating its primal and then, converting it into its dual. Then, the underlying advantages
of dual variables become clear.
Let us consider following example.
Example 6.12
A comapany wants to produce two products A and B which will be kept in a storage
area whose capacity is 3000 sq.m. Product A requires 3 sq.m of space per unit
whereas product B requires 4 sq.m It takes 5 machine-hours to manufacture a unit of
product A while 8 machine-hms are needed for a unit of product B. There are
available 36000 machine-hms during the production period. Also available are 2400
person-hours for finishing the products and a unit of product A takes 4 pers~n-hours
for finishing while a unit of product B needs 3 person-hours. Profit contributions are
Rs. 3 per unit of product A and Rs. 6 per unit of product B. In order to maximize the
profit for the period, how many &its of each products should company manufacture.
Solution
Let xr be the number of units of product A and x2 be the number of units of product
B which the company should manufacture for its profit maximization.
\

Then, the problem can be formulated as follows :

Maximize z = 3x1 + 6x2
Subject to : 3x1 + 4x2 I 3000 space constraint
5x1 + 8x2 I 3600 Machine hours constraint
4x1+ 3x2 I2400 Person hours finishing constraint
Since the problem involves only two decision variables, it can also be solved by
graphical method. Figure 6.5 shows the graphical solution of the problem. Following .
table gives the value of objective function at all extreme points on the convex set :'

Extreme points on convex set Value of

Objective Remarks
Point xi value xzvalue
Function
P 0 450 2700
Q 600 0 3600 Optimal value
R 490 140 2310

Now, we can see that at the optimal solution, person-hours constraint is the only
resources constraint satisfied with equality. This indicates that there is a value in
extra person-hours, while machine-hour and space are already in excess. If we had
one person-hour extra, then the person-hour constraint becomes 4x1 + 3x3 = 2401.
2401
Therefore, at x;! = 0, xl = -4
G 600.25. The new value of the objective
function corresponding to x2 = 0 and xi = 600.25 is 3601.5. Thus, an addtional
person-hour can contribute Rs. 1.50 more towards profit or in other words, the
implicit value of person-hour is Rs.1.50. The implicit values of an addtional sq. m.
of space or an additional machine-hour are both zero.
However, very few real problems involve only two decision variables. Therefore,
always this type of graphical interpretation will not be possible.
Another approach is to formulate the problem with the decision variables being the
implicit values of resources, which is known as dual.
Let Wi = implicit values of 1 sq.m of storage space,
Wz = implicit value of 1 machine-hour, and
W3 = implicit value of 1 person-hour.
We know the number of units of each resource that ~ompanyhas made available.
Now, we can maximize the profit by minimizing the price paid by allocating these
resources to manufacture product A and product B.
Therefore, the new objective function Zw is as follows :

The value of the resources, i.e. WI, Wz, W3 cannot be unlimited. Here, one must
understand that value of resources used for manufacturing a unit product must be
lower than the profit contribution of a unit product.
We must know the value of all resources required for the manufacture of a unit
products A and B.
 Each unit of product A consumes 3 sq.m. space, 5 machine-hours, and 4 person- Lmear Rogn-&d
hours. Then the total value of the resources used to make a unit of product A is
-Simplex Metbod

3 W I + 5 W2 + 4 W3. The profit contribution for unit product A is Rs. 3.

Therefore, the constraint will be,
~ W+5Wz+4W3
I 2 3 (product A) .
The value of the resources must at.least Rs. 3 because it would be impossible to earn
Rs.3 profit on a unit of product A, otherwise. If the value of resources, i.e. the left
hand side of the above constraint is more than the profit, the resources should be
diverted to more profitable products. The second constraint by similar analysis is as
follows :
4W1+ 8W2 + 3W3 2 6 @roduct B)
Now, let us write the primal and dual side by side.

Primal Dual
Maximize Minimize
z = 3x1 + 6x2 Z, = 3000W1+ 3600Wz + 2400W3

Subject to : Subject to :
3x1+ 4 ~ 2I 3000 (space constraints) 3Wl + 5 W,+ 4 W3 2 3 (product A)

II 5x1+ 8& I 3600 (machine constraints) 4Wl + 8W2 + 3W, 2 6 (product B)

4x1+ 3% 5 2400 (person-hour)
I W,w2w320 I
Formulation of a Dud Problem
If the primal is in the standard form, the dud problem can be formulated by following rules :
(1) The number of constraints in the primal problem is equal to the number of dual
variables. The number of constraints in dual problem is equal to the number of
variables in the primal problem
(2) If the primal problem is a maximization problem, the dual problem will always
be a minimization problem
( 3 ) The profit coefficient of the primal problem appear on the right hand side of the
constraints of the dud problem
(4) The primal problem has been "less-than-orequal-to" type constraints while the
dual problem has "greater-than-or-equal-to" type constraints.
(5) The coefficient of the constraints of the primal problem which appear from left
to right are placed from top to bottom in the constraints of the dual problem and
vice-versa.
Standard primal form requires all constraints to be equations, with all variables on right
hand side to be non-negative, e.g.
Primal

Subject to : xl+4xz+h3 5 7

Xl, xz, X3 2 0
Standard Primal
Maximize z = 4x1 + 10x2 + 3x3 +
Subject to : x l + 4 x z + 2 x 3 + ~ 4= 7
3xl-x2+3~3+aXq ='8
XI* x% x31 a20
 where m is a slack variable in the first constraint therefore it has zero coefficient in
the objective function and second constraint.
Dual
Minimize ZI = 7WI+ 8 W2
Subject to :
Wl + 3% 2 4
4w1- w2 2 10
2W1+3W2 2 3
Wl+ow2 2 0
By fourth constraint of the problem means Wi 2 0 while W2 is unrestricted.
In sum and substance, we can summarise the information as follows :

Standard Primal Dual Type of Constraint

Objective Function Objective Function in case of Dual
Maximization Minimization 2

Minimization Maximization I
L

SAQ 6
A garment manufacturer has a production line making two styles of shirts. Style I
requires 200 gm of cotton thread, 300 grn of dacron thread and 300 gm of linen
thread. Style I1 requires 200 gm of cotton thread, 200 gm of dacron thread and 100
gm of linen thread. The manufacturer makes a net profit of Rs. 19.50on style I and
Rs. 15.90on style 11. He has in hand an inventory of 24 kg of cotton thread, 26 kg of
dacron thread and 22 kg of linen thread. His immediate problem is to determine a
production schedule, with the given current inventory to make a maximum profit.
Then he would like to know at what price it would be profitable to buy thread.
Solve the problem and explain how the concept of duality can be helpful to find out
the right prik for various kinds of thread.

6.7 SUMMARY - - - - - - - - - - - - - -

The simplex method is an appropriate method for solving a linear programming problem
involving more than two decision variables. For "less-than-or-equal-to" type of constraints,
slack variables are introduced to convert the inequalities into equations. A particular type of
solution known as a basic feasible solution is ir@ortant for siniplex computation. Every
basic feasible solution is an extreme point of the convex set of feasible solutions and
vice- versa. We can always find a basic feasible solution with the help of the slack variables.
The objective function is maximized or minimized at one of the basic feasible solutions.
Starting with the initial basic feasible solution obtained from the slack variables, the simplex
method improves the value of the objective function step by step by bringing in a new basic
variable and making one of the present basic variables as non-basic. The selection of the
new basic variable and the.omission of a current basic variable are performed by following
certain rules so that the revised basic feasible solution improves the value of the objective
function. The interactive procedure stops when it is no longer possible to get a better value
of the objective function than the present one. The existing basic feasible solution is the
optimum solution which maximizes or minimizes the objective function as the case may be.
When one or more of the constraints are "greater-than-or-equal-to" type, then the surplus
variables are introduced to convert inequalities into equations. Surplus variables, however,
cannot be used to obtain an initial basic feasible solution. If some of the constraints are W h R M n i r g
"greater-than-orequal-to" type or some are equations, then the artificial variables are used - Simpkx MeUlod
to initiate the simplex computation. WOmethods, namely Big-M method and W o Phase
Method are available to solve linear programming problems in these cases. The simplex
method can also identify unbounded solutions and infeasible problems.
Every linear programming problem has an accompanying linear programming problem,
known as dual problem. The variables of the dual problem are known as dual variables. The
dual variables have an economic interpretation which can be used by management for
planning its resources. The solution of the dual problem can be obtained from the simplex
computation of the original problem. The solution has a number of important properties
which can also be helpful for computational purposes.

6.8 KEY WORDS

Slack Variable A slack variable corresponding to a "less-than-orequal-to"
type of constraint is a non-negative variable introduced to
convert the constraint into an equation.
Basic Solution A basic solution of a system of m equations and n variables
(m < n) is a solution where at least (n - m) variables are zero.
Bas~iFeasible Solution : A basic feasible solution of a system of m equations and n
variables (m < n) is a solution where m variables are non-
negative and (n - m) variables are zero.
Basic Variable A basic variable of a basic feasible solution has a non-negative
value.
Non Basic Variable : A non-basic variable of a basic feasible solution has a value
equal to zero.
Surplus Variable A surplus variable corresponding to a "greater-than-or-equal-
to" type of constraint is a non-negative variable introduced to
convert the constraint into an equation.
Artificial Variable : An artificial variable is a non negative variable introduced to
facilitate the computation of an initial basic feasible solution.
Optimum Solution : The optimum solution of a linear programming problem is the
solution where the objective function is maximized or
minimized, as the case may be.
Dual ~rkblem The dual problem corresponding to a linear programming
problem is another linear programming problem formulated
from the parameters of the original problem.
Primal Problem The primal problem is the original linear programming
problem.
Dual Variables The dual variables are the variables of the dual linear
programming problem.
Shadow Price The shadow price of a resource is the change in the optimum
value of the objective function per unit increase of the resource.

6.9 ANSWERS TO SAOs

SAQ 1

SAQ 2
Canned Apple - 20/9
Bottled Juice - 161/90
Maximum Profit - 187130
 75
= 0 , x2 = 125, x3 = -and Maximum Profit = Rs. 5375.
2
SAQ 4
Let A the material transported from the plant
X ~ be 1 to construction comapny A.
XU be the material transported from the plant 2 to construction comapny A.
m~ be the material transported from the plant 3 to construction comapny A.
Similarly, xi^, x ; ? ~ ,m~ are the values for the construction company B.

, are the values for the cosntruction company C.

xlc, X ~ Cx3c
, ~ DX , ~ are
X I DX D the values for the cosntruction company D.
Capacity conditions

xyl +x3B +X3~+x3D 40

Demand conditions
X ~ A + X ~ ~ +2X15
M
XlB +XU +X3B > 30

Transportation cost condition forms the objective function as

Minimize z = 9 0 x 1 ~+ 1 3 0 . ~ +
1 ~140x1~+ 8 h 1 ~
+ 1 l o r n + 1 0 5 m + 8 0 ~ +2125x2~
~
+ 1 % ~ + 100x3~+ 1 3 0 ~ +3 110mc ~
SAQ S
Unbounded Solutiorl.
SAQ 6
Style I = 20, Style = 100
Maximum Profit = Rs. 1980
Rice per kg of cotton - Rs. 43.50,
Riceperkgofdacron - Rs.36.00, and
Rice per kg of linen - 0.