Scribd
Upload
35 views3 pages

Simplex Method Optimization Solution

The document outlines the application of the Simplex method to maximize the objective function Z = 4x1 + 3x2 + 6x3 under given constraints. It details the conversion of the problem into canonical form by adding slack variables and the iterative process of the Simplex algorithm, including pivot operations and updates to the tableau. The final optimal solution is found with x1 = 0, x2 = 380/9, x3 = 470/3, yielding a maximum Z value of 3200/3.

Uploaded by

Angshuman
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
35 views3 pages

Simplex Method Optimization Solution

The document outlines the application of the Simplex method to maximize the objective function Z = 4x1 + 3x2 + 6x3 under given constraints. It details the conversion of the problem into canonical form by adding slack variables and the iterative process of the Simplex algorithm, including pivot operations and updates to the tableau. The final optimal solution is found with x1 = 0, x2 = 380/9, x3 = 470/3, yielding a maximum Z value of 3200/3.

Uploaded by

Angshuman
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

Find solution using Simplex method

MAX Z = 4x1 + 3x2 + 6x3


subject to
2x1 + 3x2 + 2x3 ≤ 440
4x1 + 3x3 ≤ 470
2x1 + 5x2 ≤ 430
and x1,x2,x3 ≥ 0

Solution:
Problem is
Max Z = 4 x1 + 3 x2 + 6 x3
subject to
2 x1 + 3 x2 + 2 x3 ≤ 440
4 x1 + 3 x3 ≤ 470
2 x1 + 5 x2 ≤ 430
and x1,x2,x3≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as
appropriate

1. As the constraint-1 is of type '≤' we should add slack variable S1

2. As the constraint-2 is of type '≤' we should add slack variable S2

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables


Max Z = 4 x1 + 3 x2 + 6 x3 + 0 S1 + 0 S2 + 0 S3
subject to
2 x1 + 3 x2 + 2 x3 + S1 = 440
4 x1 + 3 x3 + S2 = 470
2 x1 + 5 x2 + S3 = 430
and x1,x2,x3,S1,S2,S3≥0

Iteration-1 Cj 4 3 6 0 0 0
Ɵ (MinRatio)
CB x1 x2 x3 S1 S2 S3 RHS
RHS / x3
0 S1 2 3 2 1 0 0 440 440/2=220
0 S2 4 0 (3) 0 1 0 470 470/3=156.6667→
0 S3 2 5 0 0 0 1 430 ---
Zj 0 0 0 0 0 0 Z=0
Cj - Zj 4 3 6↑ 0 0 0
Positive maximum Cj - Zj is 6 and its column index is 3. So, the entering variable is x3.

Minimum ratio is 156.6667 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 3.

Entering =x3, Departing =S2, Key Element =3

R2(new)=R2(old)÷3
R2(old) = 470 4 0 3 0 1 0
R2(new)=R2(old)÷3 470/3 4/3 0 1 0 1/3 0

R1(new)=R1(old) - 2R2(new)
R1(old) = 440 2 3 2 1 0 0
R2(new) = 470/3 4/3 0 1 0 1/3 0
2×R2(new) = 940/3 8/3 0 2 0 2/3 0
R1(new)=R1(old) - 2R2(new) 380/3 -2/3 3 0 1 -2/3 0

R3(new)=R3(old)
R3(old) = 430 2 5 0 0 0 1
R3(new)=R3(old) 430 2 5 0 0 0 1

Iteration-2 Cj 4 3 6 0 0 0
Ɵ (MinRatio)
CB x1 x2 x3 S1 S2 S3 RHS
RHS / x2
0 S1 -2/3 (3) 0 1 -2/3 0 380/3 380/9 = 42.2222→
6 x3 4/3 0 1 0 1/3 0 470/3 ---
0 S3 2 5 0 0 0 1 430 430/5 = 86
Zj 8 0 6 0 2 0 Z=940
Cj - Zj -4 3↑ 0 0 -2 0

Positive maximum Cj - Zj is 3 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 42.2222 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 3.

Entering =x2, Departing =S1, Key Element =3


R1(new)=R1(old)÷3
R1(old) = 380/3 -2/3 3 0 1 -2/3 0
R1(new)=R1(old)÷3 380/9 -2/9 1 0 1/3 -2/9 0

R2(new)=R2(old)
R2(old) = 470/3 4/3 0 1 0 1/3 0
R2(new)=R2(old) 470/3 4/3 0 1 0 1/3 0

R3(new)=R3(old) - 5R1(new)
R3(old) = 430 2 5 0 0 0 1
R1(new) = 380/9 -2/9 1 0 1/3 -2/9 0
5×R1(new) = 1900/9 -10/9 5 0 5/3 -10/9 0
R3(new)=R3(old) - 5R1(new) 1970/9 28/9 0 0 -5/3 10/9 1

Iteration-3 Cj 4 3 6 0 0 0
CB x1 x2 x3 S1 S2 S3 RHS Ɵ (MinRatio)
3 x2 -2/9 1 0 1/3 -2/9 0 380/9
6 x3 4/3 0 1 0 1/3 0 470/3
0 S3 28/9 0 0 -5/3 10/9 1 1970/9
Zj 22/3 3 6 1 4/3 0 Z=3200/3
Cj - Zj -10/3 0 0 -1 -4/3 0

Since all Cj - Zj ≤ 0

Hence, optimal solution is arrived with value of variables as :

x1=0, x2=380/9, x3=470/3


Max Z=3200/3

You might also like