Question

"Primal"
MAXIMIZE  Z = 12X1 + 18X2 +10X3
S.T.
                             2X1  + 3X2   + 4X3    <= 50
                              -X1  +  X2     +  X3    <= 0
                              0X1  -  X2 + 1.5X3    <= 0
                                 X1, X2, X3 >=0

1.  Write the "Dual" of this problem.
2.  Write the "Dual of the Dual" of this problem.
For steps 3 & 4, use the Generic Linear Programming spreadsheet or the software of your choice.  
(Submit a file pdf, text, xls file, etc., indicating the solution values and objective function value.)
3.  Solve the "Primal" problem.  (Find values of X1, X2, X3 and the Maximum Z)
4.  Solve the "Dual" problem. (Find values of Y1, Y2, Y3 and the Minimum Z*)

Answer 1

1. Given primal can also be written as -

s.t.,

We know that to find the dual of a primal , we -

1. Change maximization to minimization and vice-versa

2. Interchange the role of constraint and cost .

3. Find A' i.e., transpose of A .

4. Reverse inequality sign .

So , we have the dual of the above primal as -

s.t.,

i.e., Required dual of the above primal is -

s.t.,

2. Since ,we know that the ''dual of a dual is the primal itself '' (i.e., (Z*)* = Z) , therefore dual of the above dual is given as -

s.t.

3. Let us now solve the above primal problem using simplex method .

The problem is converted into canverted into canonical form by adding slack variables S1 , S2 , S3 in all the three constraints as all the three constraints are having '' less than equal to '' inequality .

So , we have the problem as -

s.t.

Iteration 1			12	18	10	0	0	0	mIn ratio xB/x2
B									mIn ratio xB/x2
	0	50	2	3	4	1	0	0	50/3 = 16.6667
	0	0	-1		1	0	1	0	0/1 = 0 (min)
	0	0	0	-1	1.5	0	0	1	-
Z=0			0	0	0	0	0	0
			12	18	10	0	0	0

Here , positive 18 is highest positive and it falls in the column index of x2 , therefore the incoming vector is x2 . Also min ratio is 0 , which falls in row index s2 , therefore s2 is the outgoing vector .

And pivot element is 1.

Now , apply elementary row operation to s1 , s2 , and s3 to make elements of column of pivot element 0 , and leaving pivot element as 1 .

ROW 3 : ROW 3 + row 2

Row 1 : row 1 - 3 row 2

Iteration 2		Cj	12	18	10	0	0	0
B	CB	XB	x1	x2	x3	s1	s2	s3	min ratio(XB/x1)
s1	0	50		0	1	1	-3	0	50/5 = 10 (min)
x2	18	0	-1	1	1	0	1	0	-
s3	0	0	-1	0	2.5	0	1	1	-
Z=0		Zj	-18	18	18	0	18	0
		Cj-Zj	30	0	-8	0	-18	0

Maximum positive is 30 in column x1 , therefore , incoming vector is x1 .

Also minimum ratio is 10 in s1 row , therefore outgoing vector is s1 , and pivot element is 5 .

Thus , we will make pivot element as 1 and other elements in that column as zero using elementary row operations.

Row 1 : (1/5)Row 1

Row 2 : Row 2 + Row 1 (new)

Row 3 : Row 2 + row 1 (new)

Iteration 3		Cj	12	18	10	0	0	0
B	CB	XB	x1	x2	x3	s1	s2	s3	min ratio (XB/x3)
x1	12	10	1	0	0.2	0.2	-0.6	0
x2	18	10	0	1	1.2	0.2	0.4	0
s3	0	10	0	0	2.7	0.2	0.4	1
Z = SUM(CB*XB) = 300		Zj	12	18	24	6	0	0
		Cj - Zj	0	0	-14	-6	0	0

Since , all Cj - Zj are negative .

Therefore , this is the solution table , with maximum value of Z = 300 and

x1 = 10 , x2 = 10 , x3 = 0

4. The solution of the dual problem can be obtained from the solution table of primal itself .

We know that ,

Max Z of primal = Min Z* of dual and vice versa .

Also , Value of slack variable with changed sign in the primal solution is the value of corresponding dual variable in the dual problem .

Therefore , we have -

Minimum value of Z* (IN DUAL) = max value of Z ( in primal ) = 300

Values of dual variables w1 , w2 , w3 are -

w1 = -(s1) = -(-6) = 6

w2 = -(s2) = 0

w3 = -(s3) = 0

Since, in the given problem , it was given to use the Y1 , Y2 , Y3 variables for dual lpp , therefore , we can say ,

Y1 = 6 , Y2 = 0 , Y3 = 0

AND Z* = 300 .