Scribd
Upload
6 views1 page

Dual Simplex Method

The document outlines the dual simplex method for solving linear programming problems, specifically focusing on converting a given problem into a standard form and constructing a simplex table. It provides a step-by-step procedure for applying the dual simplex method when the initial solution is optimal but infeasible. Additionally, it includes examples and instructions for writing MATLAB code to test the method on specified linear programming problems.

Uploaded by

Vikas
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Dual Simplex Method

The document outlines the dual simplex method for solving linear programming problems, specifically focusing on converting a given problem into a standard form and constructing a simplex table. It provides a step-by-step procedure for applying the dual simplex method when the initial solution is optimal but infeasible. Additionally, it includes examples and instructions for writing MATLAB code to test the method on specified linear programming problems.

Uploaded by

Vikas
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Thapar Institute of Engineering and Technology, Patiala

School of Mathematics
Optimization Methods (UMA-034): Mechanical Branch
2020-21 Odd sem
Lab Experiment- 5
————————————————————————————————————————–
The dual simplex method

Convert the given linear programming problem in the following form:


(P ) min / max z = C t X + Ot s
subject to AX + Is = b, X, s ≥ 0
Where s = (s1 , s2 , . . . , sm )t is a vector of slack variables and O = (0, 0 . . . , 0)n×1 is a vector of zeros.
Also Assume that atleast one of the component bi of the RHS vector b = (b1 , b2 , . . . , bm ) is negative
Initially define the following Input paramenters:
1. Enter the Matrix A = [A I], where I is an identity matrix of order m.
2. Entet the the R.H.S. vector b and the cost matrix C = [c O](n+m)×1 .
3. Define [m,n]=size (A)
4. Input the variables s1 , s2 , . . . sm as initial basic variables.
Now construct the simplex table using s1 , s2 , . . . , sm as initial basic variables. If the simplex table
depicts an optimal but Infeasible solution, then dual simplex method is applicable. So apply
the following procedure.
1. Select the leaving variable as XBr = min{XBi | XBi < 0}
i
 
zk − ck |zj − cj |
2. Select the entering variable xk using the formula = minj : yrj < 0
yrk |yrj |
3. Now update the basis as by removing rth basic variable with k th nonbasic variable. Again
construct the simplex table and repeat the above procedure until an optimal basic feasible
soluiton is not obtained.
Write a MATLAB code for the dual simplex method and test your program on the
following examples:
1. M in. z = 3x1 + 5x2 , S.T. x1 + 3x2 ≥ 3, x1 + x2 ≥ 2, x1 , x2 ≥ 0.
2. M in. z = 12x1 + 10x2 , S.T. 5x1 + x2 ≥ 10, 6x1 + 5x2 ≥ 30, x1 + 4x2 ≥ 8, x1 , x2 ≥ 0.
3. min. z = 3x1 + 2x2 , S.T. x1 + x2 ≤ 1, x1 + 2x2 ≥ 3, x1 , x2 ≥ 0.

You might also like