بحوث العمليات للسنة الثالثة قسم علوم الحاسوب

13.1 Introduction
Lecture 13
Linear programming :
Computational Procedure of Dual Simplex Method
Any LPP for which it is possible to find infeasible but better than optimal initial basic solution
can be solved by using dual simplex method. Such a situation can be recognized by first
expressing the constraints in ‘?’ form and the objective function in the maximization form. After
adding slack variables, if any right hand side element is negative and the optimality condition is
satisfied then the problem can be solved by dual simplex method.
Negative element on the right hand side suggests that the corresponding slack variable is
negative. This means that the problem starts with optimal but infeasible basic solution and we
proceed towards its feasibility.
The dual simplex method is similar to the standard simplex method except that in the latter the
starting initial basic solution is feasible but not optimum while in the former it is infeasible but
optimum or better than optimum. The dual simplex method works towards feasibility while
simplex method works towards optimality.
13.2 Computational Procedure of Dual Simplex Method
The iterative procedure is as follows
Step 1 - First convert the minimization LPP into maximization form, if it is given in the
minimization form.
Step 2 - Convert the ‘?’ type inequalities of given LPP, if any, into those of ‘?’ type by
multiplying the corresponding constraints by -1.
Step 3 – Introduce slack variables in the constraints of the given problem and obtain an initial
basic solution.
Step 4 – Test the nature of ?j in the starting table
? If all ?j and XB are non-negative, then an optimum basic feasible solution has been
attained.
? If all ?j are non-negative and at least one basic variable XB is negative, then go to step 5.
? If at least ?j one is negative, the method is not appropriate.
Step 5 – Select the most negative XB. The corresponding basis vector then leaves the basis set B.
Let Xr be the most negative basic variable.
Step 6 – Test the nature of Xr
? If all Xr are non-negative, then there does not exist any feasible solution to the given
problem.
? If at least one Xr is negative, then compute Max (?j / Xr ) and determine the least negative
for incoming vector.
Step 7 – Test the new iterated dual simplex table for optimality.
1
Repeat the entire procedure until either an optimum feasible solution has been attained in a finite
number of steps.
13.3 Worked Examples
Example 1
Minimize Z = 2x1 + x2
Subject to
3x1 + x2 ? 3
4x1 + 3x2 ? 6
x1 + 2x2 ? 3
and x1 ? 0, x2 ? 0
Solution
Step 1 – Rewrite the given problem in the form
Maximize Z 2 – = ? x1 – x2
Subject to
–3x1 – x2 ? –3
–4x1 – 3x2 ? –6
–x1 – 2x2 ? –3
x1, x2 ? 0
Step 2 – Adding slack variables to each constraint
Maximize Z 2 – = ? x1 – x2
Subject to
–3x1 – x2 + s1 = –3
–4x1 – 3x2 + s2 = –6
–x1 – 2x2 + s3 = –3
x1, x2, s1,s2, s3 ? 0
Step 3 – Construct the simplex table
Cj ? -2 -1 0 0 0
Basic
variables CB XB X1 X2 S1 S2 S3
s1 0 -3 -3 -1 1 0 0
s2 0 -6 -4 -3 0 1 0 ? outgoing
s3 0 -3 -1 -2 0 0 1
Z 0 = ?
2
?
1
0
0
0
??j
2
Step 4 – To find the leaving vector
Min (-3, -6, -3) = -6. Hence s2 is outgoing vector
Step 5 – To find the incoming vector
Max (?1 / x21, ?2 / x22) = (2/-4, 1/-3) = -1/3. So x2 is incoming vector
Step 6 –The key element is -3. Proceed to next iteration
Cj ? -2 -1 0 0 0
Basic
variables CB XB X1 X2 S1 S2 S3
s1 0 -1 -5/3 0 1 -1/3 0 ? outgoing
x2 -1 2 4/3 1 0 -1/3 0 s 3 0 1 5/3 0 0 -2/3 1
Z -2 = ?
?
2/3
0
0
1/3
0
??j
Step 7 – To find the leaving vector
Min (-1, 2, 1) = -1. Hence s1 is outgoing vector
Step 8 – To find the incoming vector
Max (?1 / x11, ?4 / x14) = (-2/5, -1) = -2/5. So x1 is incoming vector
Step 9 –The key element is -5/3. Proceed to next iteration
Cj ? -2 -1 0 0 0
Basic
variables CB XB X1 X2 S1 S2 S3
x1 -2 3/5 1 0 -3/5 1/5 0
x2 -1 6/5 0 1 4/5 -3/5 0
s3 0 0 0 0 1 -1 1
Z -12/5 = ?
0
0
2/5
1/5
0
??j
Step 10 – ?j ? 0 and XB ? 0, therefore the optimal solution is Max Z -12/5 = ? , Z = 12/5, and
x1=3/5, x2 = 6/5
Example 2
Minimize Z = 3x1 + x2
Subject to
x1 + x2 ? 1
2x1 + 3x2 ? 2
and x1 ? 0, x2 ? 0
3
Solution
Maximize Z 3 – = ? x1 – x2
Subject to
–x1 – x2 ? –1
–2x1 – 3x2 ? –2
x1, x2 ? 0
SLPP
Maximize Z 3 – = ? x1 – x2
Subject to
–x1 – x2 + s1 = –1
–2x1 – 3x2 + s2 = –2
x1, x2, s1,s2 ? 0
Cj ? -3 -1 0 0
Basic
variables CB XB X1 X2 S1 S2
s1 0 -1 -1 -1 1 0
s2 0 -2 -2 -3 0 1 ?
Z 0 = ?
3
?
1
0
0
??j
s1 0 -1/3 -1/3 0 1 -1/3 ?
x2 -1 2/3 2/3 1 0 -1/3
Z -2/3 = ?
7/3
0
0
?
1/3
??j
s2 0 1 1 0 -3 1
x2 -1 1 1 1 -1 0
Z -1 = ?
2
0
1
0
??j
?j ? 0 and XB ? 0, therefore the optimal solution is Max Z -1 = ? , Z = 1, and x1= 0, x2 = 1
4



14.1 Introduction to Transportation Problem
Lecture 14
Transportation Problem :
Introduction ana mathematical formaulation
The Transportation problem is to transport various amounts of a single homogeneous commodity
that are initially stored at various origins, to different destinations in such a way that the total
transportation cost is a minimum.
It can also be defined as to ship goods from various origins to various destinations in such a
manner that the transportation cost is a minimum.
The availability as well as the requirements is finite. It is assumed that the cost of shipping is
linear.
14.2 Mathematical Formulation
Let there be m origins, ith origin possessing ai units of a certain product
Let there be n destinations, with destination j requiring bj units of a certain product
Let cij be the cost of shipping one unit from ith source to jth destination
Let xij be the amount to be shipped from ith source to jth destination
It is assumed that the total availabilities ?ai satisfy the total requirements ?bj i.e.
?ai = ?bj (i = 1, 2, 3 … m and j = 1, 2, 3 …n)
The problem now, is to determine non-negative of xij satisfying both the availability constraints
as well as requirement constraints
and the minimizing cost of transportation (shipping)
This special type of LPP is called as Transportation Problem.
1
14.3 Tabular Representation
Let ‘m’ denote number of factories (F1, F2 … Fm)
Let ‘n’ denote number of warehouse (W1, W2 … Wn)
W?
F
?
W1 W2 … Wn Capacities
(Availability)
F1 c11 c12 … c1n a1
F2 c21 c22 … c2n a2
.
.
.
.
.
.
.
.
.
.
.
.
Fm cm1 cm2 … cmn am
Required b1 b2 … bn ?ai = ?bj
W?
F
?
W1
W2
…
Wn
Capacities
(Availability)
F1 x11 x12 … x1n a1
F2 x21 x22 … x2n a2
.
.
.
.
.
.
.
.
.
.
.
.
Fm xm1 xm2 … xmn am
Required b1 b2 … bn ?ai = ?bj
In general these two tables are combined by inserting each unit cost cij with the corresponding
amount xij in the cell (i, j). The product cij xij gives the net cost of shipping units from the factory
Fi to warehouse Wj.
14.4 Some Basic Definitions
? Feasible Solution
A set of non-negative individual allocations (xij ? 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.
2
15.1 Methods for Initial Basic Feasible Solution
Some simple methods to obtain the initial basic feasible solution are
1. North-West Corner Rule
2. Lowest Cost Entry Method (Matrix Minima Method)
3. Vogel’s Approximation Method (Unit Cost Penalty Method)
North-West Corner Rule
Step 1
? The first assignment is made in the cell occupying the upper left-hand (north-west) corner
of the table.
? The maximum possible amount is allocated here i.e. x11 = min (a1, b1). This value of x11
is then entered in the cell (1,1) of the transportation table.
Step 2
i. If b1 > a1, move vertically downwards to the second row and make the second allocation
of amount x21 = min (a2, b1 - x11) in the cell (2, 1).
ii. If b1 < a1, move horizontally right side to the second column and make the second
allocation of amount x12 = min (a1 - x11, b2) in the cell (1, 2).
iii. If b1 = a1, there is tie for the second allocation. One can make a second allocation of
magnitude x12 = min (a1 - a1, b2) in the cell (1, 2) or x21 = min (a2, b1 - b1) in the cell (2, 1)
Step 3
Start from the new north-west corner of the transportation table and repeat steps 1 and 2 until all
the requirements are satisfied.
1-
Find the initial basic feasible solution by using North-West Corner Rule
1.
W?
F
?
W1
W2
W3
W4
Factory
Capacity
F1 19 30 50 10 7
F2 70 30 40 60 9
F3 40 8 70 20 18
Warehouse
Requirement 5 8 7 14 34
1
Methods for Initial Basic Feasible Solution
Lecture 15
Transportation problem :
( North - West corner rule and matrix minimum method )
Solution
W1 W2 W3 W5 Availability
F1 5 2 (19) (30) 7 2 0
F2 6 (30) 3 (40) 9 3 0
F3 4 (70) 14 (20) 18 14 0
Requirement
5
0
8
6
0
7
4
0
14
0
Initial Basic Feasible Solution
x11 = 5, x12 = 2, x22 = 6, x23 = 3, x33 = 4, x34 = 14
The transportation cost is 5 (19) + 2 (30) + 6 (30) + 3 (40) + 4 (70) + 14 (20) = Rs. 1015
2.
D1 D2 D3 D4 Supply
O1 1 5 3 3 34
O2 3 3 1 2 15
O3 0 2 2 3 12
O4 2 7 2 4 19
Demand 21 25 17 17 80
Solution
D1 D2 D3 D4 Supply
21 13
O1 (1) (5) 34 13 0
12 3
O2 (3) (1) 15 3 0
12
O3 (2) 12 0
2 17
O4 (2) (4) 19 17
Demand
21
0
25
12
0
17
14
2
0
17
0
The transportation cost is 21 (1) + 13 (5) + 12 (3) + 3 (1) + 12 (2) + 2 (2) + 17 (4) = Rs. 221
2
Initial Basic Feasible Solution
x11 = 21, x12 = 13, x22 = 12, x23 = 3, x33 = 12, x43 = 2, x44 = 17
The transportation cost is 21 (1) + 13 (5) + 12 (3) + 3 (1) + 12 (2) + 2 (2) + 17 (4) = Rs. 221
3.
From To Supply
2 11 10 3 7 4
1 4 7 2 1 8
3 1 4 8 12 9
Solution
From To Supply
3 1
(2) (11) 4 1 0
2 4 2
(4) (7) (2) 8 6 2 0
3 6
(8) (12) 9 6 0
Demand
3
0
3
2
0
4
0
5
3
0
6
0
Initial Basic Feasible Solution
x11 = 3, x12 = 1, x22 = 2, x23 = 4, x24 = 2, x34 = 3, x35 = 6
The transportation cost is 3 (2) + 1 (11) + 2 (4) + 4 (7) + 2 (2) + 3 (8) + 6 (12) = Rs. 153
Demand 3 3 4 5 6
3
Lowest Cost Entry Method (Matrix Minima Method)
Step 1
Determine the smallest cost in the cost matrix of the transportation table. Allocate xij = min (ai,
bj) in the cell (i, j)
Step 2
? If xij = ai, cross out the ith row of the table and decrease bj by ai. Go to step 3.
? If xij = bj, cross out the jth column of the table and decrease ai by bj. Go to step 3.
? If xij = ai = bj, cross out the ith row or jth column but not both.
Step 3
Repeat steps 1 and 2 for the resulting reduced transportation table until all the requirements are
satisfied. Whenever the minimum cost is not unique, make an arbitrary choice among the
minima.
Find the initial basic feasible solution using Matrix Minima method
1.
W1 W2 W3 W4 Availability
F1 19 30 50 10 7
F2 70 30 40 60 9
F3 40 8 70 20 18
Requirement 5 8 7 14
2 -
4
Solution
W1 W2 W3 W4
F1 7 X (19) (30) (50) (10)
F2
(70) (30) (40) (60) 9
F3 3 8 7 (40) (8) (70) (20) X
2 X 7 X
W1 W2 W3 W4
F1
(19) (30) (50) (10) 7
F2
(70) (30) (40) (60) 9
F3 8 10
(40) (8) (70) (20)
5 X 7 14
W1 W2 W3 W4
F1 7 X (19) (30) (50) (10)
F2
(70) (30) (40) (60) 9
F3 (40) (88 ) (70) (20) 10
5 X 7 7
W1 W2 W3 W4
F1 7 X (19) (30) (50) (10)
F2
(70) (30) (40) (60) 9
F3 (40) (88 ) (70) (72 0) 3
5 X 7 X
5
Initial Basic Feasible Solution
x14 = 7, x21 = 2, x23 = 7, x31 = 3, x32 = 8, x34 = 7
The transportation cost is 7 (10) + 2 (70) + 7 (40) + 3 (40) + 8 (8) + 7 (20) = Rs. 814
2.
To Availability
From
2 11 10 3 7 4
1 4 7 2 1 8
3 9 4 8 12 9
Requirement 3 3 4 5 6
Solution
To
From
4 (3) 4 0
3 5 8 5 0 (1) (1)
3 4 1 1 9 5 4 1 0 (9) (4) (8) (12)
3
0
3
0
4
0
5
1
0
6
1
0
Initial Basic Feasible Solution
x14 = 4, x21 = 3, x25 = 5, x32 = 3, x33 = 4, x34 = 1, x35 = 1
The transportation cost is 4 (3) + 3 (1) + 5(1) + 3 (9) + 4 (4) + 1 (8) + 1 (12) = Rs. 78
W1 W2 W3 W4
F1 (19) (30) (50) (71 0) X
F2 (27 0) (30) (74 0) (60) X
F3 (34 0) (88 ) (70) (72 0) X
X X X X
6

Methods for Initial Basic Feasible Solution
Lecture 16
Transportation problem :
(Vogal s Approximation method )
For each row of the table, identify the smallest and the next to smallest cost. Determine the
difference between them for each row. These are called penalties. Put them aside by enclosing
them in the parenthesis against the respective rows. Similarly compute penalties for each
column.
Step 2
Identify the row or column with the largest penalty. If a tie occurs then use an arbitrary choice.
Let the largest penalty corresponding to the ith row have the cost cij. Allocate the largest possible
amount xij = min (ai, bj) in the cell (i, j) and cross out either ith row or jth column in the usual
manner.
Step 3
Again compute the row and column penalties for the reduced table and then go to step 2. Repeat
the procedure until all the requirements are satisfied.
Vogel’s Approximation Method (Unit Cost Penalty Method)
Step1
3 -
Find the initial basic feasible solution using vogel’s approximation method
1.
W1 W2 W3 W4 Availability
F1 19 30 50 10 7
F2 70 30 40 60 9
F3 40 8 70 20 18
Requirement 5 8 7 14
Solution
W1 W2 W3 W4 Availability Penalty
F1 19 30 50 10 7 19-10=9
F2 70 30 40 60 9 40-30=10
F3 40 8 70 20 18 20-8=12
Requirement 5 8 7 14
Penalty 40-19=21 30-8=22 50-40=10 20-10=10
W1 W2 W3 W4 Availability Penalty
F1 (19) (30) (50) (10) 7 9
F2 (70) (30) (40) (60) 9 10
F3 (40) 8(8) (70) (20) 18/10 12
Requirement 5 8/0 7 14
Penalty 21 22 10 10
1
W1 W2 W3 W4 Availability Penalty
F1 5(19) (30) (50) (10) 7/2 9
F2 (70) (30) (40) (60) 9 20
F3 (40) 8(8) (70) (20) 18/10 20
Requirement 5/0 X 7 14
Penalty 21 X 10 10
W1 W2 W3 W4 Availability Penalty
F1 5(19) (30) (50) (10) 7/2 40
F2 (70) (30) (40) (60) 9 20
F3 (40) 8(8) (70) 10(20) 18/10/0 50
Requirement X X 7 14/4
Penalty X X 10 10
W1 W2 W3 W4 Availability Penalty
F1 5(19) (30) (50) 2(10) 7/2/0 40
F2 (70) (30) (40) (60) 9 20
F3 (40) 8(8) (70) 10(20) X X
Requirement X X 7 14/4/2
Penalty X X 10 50
W1 W2 W3 W4 Availability Penalty
F1 5(19) (30) (50) 2(10) X X
F2 (70) (30) 7(40) 2(60) X X
F3 (40) 8(8) (70) 10(20) X X
Requirement X X X X
Penalty X X X X
Initial Basic Feasible Solution
x11 = 5, x14 = 2, x23 = 7, x24 = 2, x32 = 8, x34 = 10
The transportation cost is 5 (19) + 2 (10) + 7 (40) + 2 (60) + 8 (8) + 10 (20) = Rs. 779
2.
Stores Availability
I II III IV
Warehouse
A 21 16 15 13 11
B 17 18 14 23 13
C 32 27 18 41 19
Requirement 6 10 12 15
2
Solution
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) (13) 11 2
B (17) (18) (14) (23) 13 3
C (32) (27) (18) (41) 19 9
Requirement 6 10 12 15
Penalty 4 2 1 10
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) 11(13) 11/0 2
B (17) (18) (14) (23) 13 3
C (32) (27) (18) (41) 19 9
Requirement 6 10 12 15/4
Penalty 4 2 1 10
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) 11(13) X X
B (17) (18) (14) 4(23) 13/9 3
C (32) (27) (18) (41) 19 9
Requirement 6 10 12 15/4/0
Penalty 15 9 4 18
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) 11(13) X X
B 6(17) (18) (14) 4(23) 13/9/3 3
C (32) (27) (18) (41) 19 9
Requirement 6/0 10 12 X
Penalty 15 9 4 X
3
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) 11(13) X X
B 6(17) 3(18) (14) 4(23) 13/9/3/0 4
C (32) (27) (18) (41) 19 9
Requirement X 10/7 12 X
Penalty X 9 4 X
Stores Availability Penalty
I II III IV
Warehouse
A (21) (16) (15) 11(13) X X
B 6(17) 3(18) (14) 4(23) X X
C (32) 7(27) 12(18) (41) X X
Requirement X X X X
Penalty X X X X
Initial Basic Feasible Solution
x14 = 11, x21 = 6, x22 = 3, x24 = 4, x32 = 7, x33 = 12
The transportation cost is 11 (13) + 6 (17) + 3 (18) + 4 (23) + 7 (27) + 12 (18) = Rs. 796
4