Question

For each of the following problems, put the problem into canonical form, set up the initial tableau, and solve using the simplex method. At most, two pivots should be required for each. α) minimize 2x1 +4x2-4x3 +7z4 subject to 8x1-2x2 +エ3-T4 50 + 2x4 150 x1 -x2 +2x3-4x4 100 3z1 + 52 b) minimize -51 4z2 +3 subject to23s S8 22-2 s7 -12r2 +43 S6 1, 2, 3 20 C) maximize - 35 subject to 132 2x2 4x4 +37610 X1 , X2, X3, X4, 25, X6 0

Answer 1

question A

MIN Z = 2x_1 + 4x_2 - 4x_3 + 7x_4 subject to 8x_1 - 2x_2 + x_3 - x_4 lessthanorequalto 50 3x_1 + 5x_2 + 2x_4 lessthanorequalto 150 x_1 - x_2 + 2x_3 - 4x_4 lessthanorequalto 100 After introducing slack variables Min Z = 2x_1 + 4x_2 - 4x_3 + 7x_4 + 0S_1 + 0S_2 + 0S_3 subject to 8x_1 - 2x_2 + x_3 - x_4 + S_1 = 50 3x_1 + 5x_2 + 2x_4 + S_2 = 150 x_1 - x_2 + 2x_3 - 4x_4 + S_3 = 100 Positive maximum Zj - Cj is 4 and its column index is 3 Minimum ratio is 50 and its row index is 3. The pivot element is 2. Entering = x3, Departing =S3, R_3 leftarrow R_3 * 1/2 R_1 leftarrow R_1 - R_3 Positive maximum Zj - Cj is 1 and its column index is 4. Minimum ratio is 0 and its row index is 1. The pivot element is 1. Entering = x4, Departing =S1,R_2 leftarrow R_2 - 2R_1

subject to

After introducing slack variables

subject to

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

Positive maximum Zj-Cj is 4 and its column index is 3

Minimum ratio is 50 and its row index is 3.

The pivot element is 2.

Entering =x3, Departing =S3,

Iteration-2		Cj	2	4	-4	7	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x4
S1	0	0	15/2	-3/2	0	(1)	1	0	-1/2	0/1=0→
S2	0	150	3	5	0	2	0	1	0	150/2=75
x3	-4	50	1/2	-1/2	1	-2	0	0	1/2	---
Z=-200		Zj	-2	2	-4	8	0	0	-2
		Zj-Cj	-4	-2	0	1↑	0	0	-2

Positive maximum Zj-Cj is 1 and its column index is 4.

Minimum ratio is 0 and its row index is 1.

The pivot element is 1.

Entering =x4, Departing =S1,

Iteration-3		Cj	2	4	-4	7	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio
x4	7	0	15/2	-3/2	0	1	1	0	-1/2
S2	0	150	-1/2	8	0	0	-2	1	1
x3	-4	50	31/2	-7/2	1	0	2	0	-1/2
Z=-200		Zj	-19/2	7/2	-4	7	-1	0	-3/2
		Zj-Cj	-23/2	-1/2	0	0	-1	0	-3/2

Since all

Hence, optimal solution is arrived

.

.

.

.

.

question B

subject to

After introducing slack variables

subject to

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

Positive maximum Zj-Cj is 5 and its column index is 1

Minimum ratio is 8 and its row index is 1.

he pivot element is 1.

Entering =x1, Departing =S1

Iteration-2		Cj	-5	4	1	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XB/x3
x1	-5	8	1	1	-3	1	0	0	---
S2	0	7	0	2	-2	0	1	0	---
S3	0	14	0	-1	(1)	1	0	1	14/1=14→
Z=-40		Zj	-5	-5	15	-5	0	0
		Zj-Cj	0	-9	14↑	-5	0	0

Positive maximum Zj-Cj is 14 and its column index is 3.

Minimum ratio is 14 and its row index is 3

The pivot element is 1.

Entering =x3, Departing =S3,

Iteration-3		Cj	-5	4	1	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XBx2
x1	-5	50	1	-2	0	4	0	3	---
S2	0	35	0	0	0	2	1	2	---
x3	1	14	0	-1	1	1	0	1	---
Z=-236		Zj	-5	9	1	-19	0	-14
		Zj-Cj	0	5↑	0	-19	0	-14

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

Hence, the solution to the given problem is unbounded.

.

.

.

.

.

question 3

subject to

.

After introducing artificial variables

subject to

Iteration-1		Cj	0	9	2	0	-1	0	-M	-M	-M
B	CB	XB	x1	x2	x3	x4	x5	x6	A1	A2	A3	MinRatio XB/x3
A1	-M	60	1	-3	0	-4	0	2	1	0	0	---
A2	-M	20	0	-2	0	1	1	-4	0	1	0	---
A3	-M	10	0	1	(1)	0	0	3	0	0	1	10/1=10→
Z=-90M		Zj	-M	4M	-M	3M	-M	-M	-M	-M	-M
		Zj-Cj	-M	4M-9	-M-2↑	3M	-M+1	-M	0	0	0

Negative minimum Zj-Cj is -M-2 and its column index is 3.

Minimum ratio is 10 and its row index is 3.

The pivot element is 1.

Entering =x3, Departing =A3,

Iteration-2		Cj	0	9	2	0	-1	0	-M	-M
B	CB	XB	x1	x2	x3	x4	x5	x6	A1	A2	MinRatio XB/x1
A1	-M	60	(1)	-3	0	-4	0	2	1	0	60/1=60→
A2	-M	20	0	-2	0	1	1	-4	0	1	---
x3	2	10	0	1	1	0	0	3	0	0	---
Z=-80M+20		Zj	-M	5M+2	2	3M	-M	2M+6	-M	-M
		Zj-Cj	-M↑	5M-7	0	3M	-M+1	2M+6	0	0

Negative minimum Zj-Cj is -M and its column index is 1.

inimum ratio is 60 and its row index is 1.

The pivot element is 1.

Entering =x1, Departing =A1,

Iteration-3		Cj	0	9	2	0	-1	0	-M
B	CB	XB	x1	x2	x3	x4	x5	x6	A2	MinRatio XB/x4
x1	0	60	1	-3	0	-4	0	2	0	---
A2	-M	20	0	-2	0	(1)	1	-4	1	20/1=20→
x3	2	10	0	1	1	0	0	3	0	---
Z=-20M+20		Zj	0	2M+2	2	-M	-M	4M+6	-M
		Zj-Cj	0	2M-7	0	-M↑	-M+1	4M+6	0

Negative minimum Zj-Cj is -M and its column index is 4.

Minimum ratio is 20 and its row index is 2.

The pivot element is 1.

Entering =x4, Departing =A2

Iteration-4		Cj	0	9	2	0	-1	0
B	CB	XB	x1	x2	x3	x4	x5	x6	MinRatio XB/x2
x1	0	140	1	-11	0	0	4	-14	---
x4	0	20	0	-2	0	1	1	-4	---
x3	2	10	0	(1)	1	0	0	3	10/1=10→
Z=20		Zj	0	2	2	0	0	6
		Zj-Cj	0	-7↑	0	0	1	6

Negative minimum Zj-Cj is -7 and its column index is 2.

Minimum ratio is 10 and its row index is 3

The pivot element is 1.

Entering =x2, Departing =x3,

Iteration-5		Cj	0	9	2	0	-1	0
B	CB	XB	x1	x2	x3	x4	x5	x6	MinRatio
x1	0	250	1	0	11	0	4	19
x4	0	40	0	0	2	1	1	2
x2	9	10	0	1	1	0	0	3
Z=90		Zj	0	9	9	0	0	27
		Zj-Cj	0	0	7	0	1	27

Since all

Hence, optimal solution is arrived