Question

4-Consider the following problem:

max − 3x1 + 2x2 − x3 + x4

s.t.

2x1 − 3x2 − x3 + x4 ≤ 0

− x1 + 2x2 + 2x3 − 3x4 ≤ 1

− x1 + x2 − 4x3 + x4 ≤ 8

x1, x2, x3, x4 ≥ 0

Use the Simplex method to verify that the optimal objective value is unbounded. Make use of the final tableau to construct an unbounded direction..

Answer 1

Solution:
Problem is

Max Z = - 3 x1 + 2 x2 - x3 + x4

subject to

2 x1 - 3 x2 - x3 + x4 ≤ 0 - x1 + 2 x2 + 2 x3 - 3 x4 ≤ 1 - x1 + x2 - 4 x3 + x4 ≤ 8

and x1,x2,x3,x4≥0;

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

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 = - 3 x1 + 2 x2 - x3 + x4 + 0 S1 + 0 S2 + 0 S3

subject to

2 x1 - 3 x2 - x3 + x4 + S1 = 0 - x1 + 2 x2 + 2 x3 - 3 x4 + S2 = 1 - x1 + x2 - 4 x3 + x4 + S3 = 8

and x1,x2,x3,x4,S1,S2,S3≥0

Iteration-1		Cj	-3	2	-1	1	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x2
S1	0	0	2	-3	-1	1	1	0	0	---
S2	0	1	-1	(2)	2	-3	0	1	0	1/2=0.5→
S3	0	8	-1	1	-4	1	0	0	1	8/1=8
Z=0		Zj	0	0	0	0	0	0	0
		Zj-Cj	3	-2↑	1	-1	0	0	0

Negative minimum Zj-Cj is -2 and its column index is 2. So, the entering variable is x2.

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

∴ The pivot element is 2.

Entering =x2, Departing =S2, Key Element =2

R2(new)=R2(old)÷2

R1(new)=R1(old) + 3R2(new)

R3(new)=R3(old) - R2(new)

Iteration-2		Cj	-3	2	-1	1	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x4
S1	0	1.5	0.5	0	2	-3.5	1	1.5	0	---
x2	2	0.5	-0.5	1	1	-1.5	0	0.5	0	---
S3	0	7.5	-0.5	0	-5	(2.5)	0	-0.5	1	7.5/2.5=3→
Z=1		Zj	-1	2	2	-3	0	1	0
		Zj-Cj	2	0	3	-4↑	0	1	0

Negative minimum Zj-Cj is -4 and its column index is 4. So, the entering variable is x4.

Minimum ratio is 3 and its row index is 3. So, the leaving basis variable is S3.

∴ The pivot element is 2.5.

Entering =x4, Departing =S3, Key Element =2.5

R3(new)=R3(old)÷2.5

R1(new)=R1(old) + 3.5R3(new)

R2(new)=R2(old) + 1.5R3(new)

Iteration-3		Cj	-3	2	-1	1	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x3
S1	0	12	-0.2	0	-5	0	1	0.8	1.4	---
x2	2	5	-0.8	1	-2	0	0	0.2	0.6	---
x4	1	3	-0.2	0	-2	1	0	-0.2	0.4	---
Z=13		Zj	-1.8	2	-6	1	0	0.2	1.6
		Zj-Cj	1.2	0	-5↑	0	0	0.2	1.6

Variable x3 should enter into the basis, but all the coefficients in the x3 column are negative or zero. So x3 can not be entered into the basis.

Hence, the problem has an infeasible solution.