Solve the following problem using two phase method. Maximize: $\\Z = 15x + 20y \\$ Subjected to: $3x + y \ge 120 \\ 3x + 11y \ge 330 \\ x + y \le 80 \\ x, y \ge 0$

25views

written 7.3 years ago by

Introducing slack, surplus & artificial variables in constraints

$3x + y – S_1 + A_1 = 120 \\ 3x + 11y – S_2 + A_2 =330 \\ x + y + S_3 = 80$

So the objective function becomes

$Z = 15x + 20y + 0S_1 + 0S_2 + 0S_3 + A_1 + A_2$

Phase I: Assigning coefficients of ‘-1’ to artificial variables & coefficient of ‘0’ o all other variables in the objective function.

Cj→	0	0	0	0	0	-1	-1
	x	y	$S_1$	$S_2$	$S_3$	$A_1$	$A_2$	RHS	θ
$-1A_1$	3	1	-1	0	0	1	0	120	120
$-1A_2$	3	11	0	-1	0	0	1	330	30←
$0S_3$	1	1	0	0	1	0	0	80	80
Zj	-6	-12	1	1	0	-1	-1	-450
Cj - Zj	6	12↑	-1	-1	0	0	0

Here Pivot point is 11.

Entering variable in basis = y

Leaving variable in basis = $A_2$

| | Cj→ |0| 0| 0| 0| 0| -1| -1| | | |-|-|-|-|-|
|Operations| | x| y| $S_1$| $S_2$| $S_3$| $A_1$| $A_2$| RHS| θ| |$R_2/11$| $-1A_1$| 30/11| 0| -1| 1/11| 0| 1| -1/11| 90| 990| |$R_1 – R_2$| 20y| 3/11| 1| 0| -1/11| 0| 0| 1/11| 30| -330| |$R_3 – R_2$| $0S_3$| 8/11| 0| 0| 1/11| 1| 0| -1/11| 50| 550←| | | Zj| 30/11| 20| 1| -21/11| 0| -1| 21/11| | |
| | Cj - Zj| -30/11| -20| -1| 21/11↑| 0| 0| -32/11| | |

Entering variable = $S_2$

Leaving variable = $S_3$

| | Cj→| 0| 0| 0| 0| 0| -1| -1| | | |-|-|-|-|-|
|operation | | x| y| $S_1$| $S_2$| $S_3$| $A_1$| $A_2$| RHS| θ| |$R_3 * 11$| $-1A_1$| 2| 0| -1| 0| -1| 1| 0| 40| | |$R_2+R_3/11$| 20y| 1| 1| 0| 0| 1| 0| 0| 80| |
|$R_1-R_3/11$| $0S_2$| 8| 0| 0| 1| 11| 0| -1| 550| | | | Zj| 18| 20| 1| 0| 1| -1| 0| 1560| |
| | Cj - Zj| -18| -20| -1| 0| -1| 0| -1| | |

This is the end of Phase I, since all values of Cj – Zj are less than or equal to zero.

But one artificial variable still present in the basis, this indicates that this problem does not have feasible solution.

ADD COMMENT EDIT