Question

Situation:

Construct the Dual and solve the Dual by the graphical and simplex method. The values of the variables are in the table.

Minimize     Z = Ax1 + Bx2 + Cx3

Subject to:     Dx1 + Ex2 + Fx3 >= J

                        Gx1 + Hx3 + Ix3 >= K

x1, x2, and x3 >= 0

Student

Coefficients

Numbers

A

B

C

D

E

F

G

H

I

J

K

Objective Function

Equations

Constant recursor

1

2

1

1

3

5

2

3

5

19

15

Answer 1

Primal:

Min Z = 1x1 + 2x2 + 1x3
s.t.
1x1 + 3x2 + 5x3 >= 19
2x1 + 3x3 + 5x3 >= 15
x1, x2, x3 >= 0

Dual:

Max W = 19y1 + 15y2
s.t.
1y1 + 2y2 <= 1
3y1 + 3y2 <= 2
5y1 + 5y2 <= 1
y1, y2 >= 0

Graphical solution:

As we can see the first two constraints are redundant and the feasibility region is formed only by the third constraint with three corner points - the origin, (0, 0.2), and (0.2, 0).

Corner point	y1	y2	W = 19y1 + 15y2
(0, 0)	0	0	0
(0, 0.2)	0	0.2	3
(0.2, 0)	0.2	0	3.8 (max)

So,

the optimal solution of the dual is y1=0.2, y2=0, and max W = 3.8

Simplex method:

Standard form:

Max W   =       19   y1   +   15   y2   +   0   S1   +   0   S2   +   0   S3
subject to
y1   +   2   y2   +       S1                           =   1
3   y1   +   3   y2               +       S2               =   2
5   y1   +   5   y2                           +       S3   =   1
y1,y2,S1,S2,S3 ≥ 0

Iteration-1		Cj	19	15	0	0	0
B	CB	RHS	y1	y2	S1	S2	S3	Min Ratio RHS / y1
S1	0	1	1	2	1	0	0	1 / 1=1
S2	0	2	3	3	0	1	0	2 / 3=0.667
S3	0	1	(5)	5	0	0	1	1 / 5=0.2→
W = 0		Zj	0	0	0	0	0
		Zj-Cj	-19↑	-15	0	0	0

Negative minimum Zj-Cj is -19 and its column index is 1. So, the entering variable is y1.

The minimum ratio is 0.2 and its row index is 3. So, the leaving basis variable is S3.

So, the pivot element is 5.

Entering =y1, Departing =S3, Key Element =5

Row operations:

• R3(new)=R3(old) / 5
• R1(new)=R1(old) - R3(new)
• R2(new)=R2(old) - 3 * R3(new)

Iteration-2		Cj	19	15	0	0	0
B	CB	RHS	y1	y2	S1	S2	S3
S1	0	0.8	0	1	1	0	-0.2
S2	0	1.4	0	0	0	1	-0.6
y1	19	0.2	1	1	0	0	0.2
W = 3.8		Zj	19	19	0	0	3.8
		Zj-Cj	0	4	0	0	3.8

Since all Zj-Cj ≥ 0, we have reached the optimal solution which is as follows:

y1 = 0.2
y2 = 0
max W = 3.8