F(X), Gives the Direction of the Largest Increase (Improving If Max Problem)

HW#2 Solution

IE312 Fall 07

1of 10

Problem 1.

Gradient

f(x), gives the direction of the largest increase (improving if max problem).

-f(x) gives the direction of the largest decrease (improving if min problem).

Solution :

a. Max 3w1-2w2+w4at w = (2,0,5,1)

At w = (2,0,5,1), the improving direction is f(2,0,5,1) = (3,-2,0,1).

b. Min 4w1+w3-5w4at w = (1,1,7,-1)

At w = (1,1,7,-1), the improving direction is -f(1,1,7,-1) = (-4,0,-1,5).

c. Min (w1+2)2-w1w2 at w = (3,2)

At w = (3,2), the improving direction is -f(3,2) = -(2*(3+2)-2,3) = (-8,3).

d. Max (w1)3-4w1+6w2 at w = (2,5)

At w = (2,5), the improving direction is f(2,5) = (3*(22)-4,6) = (8,6).

Problem 2.

Max 4z1+7z2 Objective Function

s.t.

2z1+z2≤9,Constraint 1 (C1)

0≤z1≤4,Constraint 2 (C2)

0≤z2≤3Constraint 3 (C3)

a. For max problem, the objective function is increased if f(x).x>0.

From objective function, we get.

The direction z (1) = (2,0) is an improving directions for this model at every z since

f(z). z (1) = (4,7)’ . (2,0) = 8 > 0.

The direction z (2) = (-2,4) is an improving directions for this model at every z since

f(z). z (2) = (4,7) ’. (-2,4) = -8+28=20 > 0.

b. Improving search algorithm from PPT slide:

0 Choose initial solution

1 If no improving direction z STOP

2 Find improving direction z  from a. we have 2 improving direction z (1) = (2,0) and z (2) = (-2,4).

3 Choose the largest step size t+1 that remains feasible and improves performance

4 Update  z(t+1)=z(t)+ t+1z (t+1)

Let t=t+1 and return to step 1

At t=0, initial solution is z (0) = (0,0).

We have two improving direction from a. which are z (1) and z (2).

Let start improving with z (1)

Find the largest step size 1

We have z(1)=z(0)+ 1z (1) = (0,0)+ 1.(2,0)= (21,0)

Substitute z(1) into C1, C2,C3 to find 1

C1: 2z1+z2≤9 2(21)+0=41≤91≤9/4

C2: 0≤z1≤4,0≤21≤40≤1≤2

C3: 0≤z2≤3,0≤0≤31R

To remain feasible and improves performance, the largest 1 is 2, hence z(1)=(4,0).

Since we cannot improve more performance from z(1) using z (1), we start moving in z (2) direction.

At t=1, new initial solution is z(1)=(4,0).

Start improving with z (2)

Find the largest step size 2

We have z(2)=z(1)+ 2z (2) = (4,0)+ 2.(-2,4)= (4-22,42)

Substitute z(2) into C1, C2,C3 to find 2

C1: 2z1+z2≤9 2(4-22)+ 42=8≤92R

C2: 0≤z1≤4,0≤4-22≤40≤2≤2

C3: 0≤z2≤3,0≤42≤30≤2≤3/4

To remain feasible and improves performance, the largest 2 is 3/4, hence z(2)=(5/2,3).

Since we cannot improve more performance from z(2) using z (2), we try improving with z (1) direction again.

At t=2, new initial solution is z(2)=(5/2,3).

Start improving with z (3) , which is equal to z (1)

Find the largest step size 3

We have z(3)=z(2)+ 3z (3) = (5/2,3)+ 3.(2,0)= (5/2+23,3)

Substitute z(3) into C1, C2,C3 to find 3

C1: 2z1+z2≤9 2(5/2+23)+3≤92≤1/4

C2: 0≤z1≤4,0≤5/2+23≤4-5/4≤3≤3/4

C3: 0≤z2≤3,0≤3≤33R

To remain feasible and improves performance, the largest 3 is 1/4, hence z(3)=(3,3).

Since we cannot improve more performance from z(3) using z(3) (orz (1)), we try improving with z (2) direction again.

At t=3, new initial solution is z(3)=(3,3).

Start improving with z (4) , which is equal to z (2)

Find the largest step size 4

We have z(4)=z(3)+ 4z (4) = (3,3)+ 4.(-2,4)= (3-24,3+44)

Substitute z(4) into C1, C2,C3 to find 4

C1: 2z1+z2≤9 2(3-24)+(3+44)=9≤94R

C2: 0≤z1≤4,0≤3-24≤4-1/2≤4≤3/2

C3: 0≤z2≤3,0≤3+44≤3-3/4≤4≤0

To remain feasible and improves performance, the largest 4 is 0, which mean we cannot improve from z(3) or “no improving direction z”STOP searching

And we get the optimal solution at z(3,3) with the objective value of 33.

IF we start the search algorithm with direction z (2) instead of z (1), the solution may different.

At t=0, initial solution is z (0) = (0,0).

We have two improving direction from a. which are z (1) and z (2).

Let start improving with z (2)

Find the largest step size 

We have z(1)=z(0)+ z (2) = (0,0)+ .(-2,4)= (-2, 4)

Substitute z(1) into C1, C2,C3 to find 

C1: 2z1+z2≤9 2(-2)+4=0≤9R

C2: 0≤z1≤4,0≤-2≤4-2≤≤0

C3: 0≤z2≤3,0≤4≤30≤≤3/4

To remain feasible and improves performance, the largest is 0, which mean we cannot improve from z(0) or “no improving direction z”STOP searching

We might think that the optimal solution is at z(0,0) with the objective value of 0. However, with the previous search method (start searching with z (1) direction) we can get the better solution. We can see that using different search methods may result in the different solutions.

Problem 1 P.92

Notation:

xij = Amount of ingredient j use to produce product i

Product (i) where i = 1 for Slugger Candy and =2 for Easy Out Candy

Ingredient (j) where j = 1 for Sugar, =2 for Nuts, and =3 for Chocolate

Decision Variable:

x11: Amount of Sugar in Slugger Candy

x12: Amount of Nuts in Slugger Candy

x13: Amount of Chocolate in Slugger Candy

x21: Amount of Sugar in Easy Out Candy

x22: Amount of Nuts in Easy Out Candy

x23: Amount of Chocolate in Easy Out Candy

Max z= 20(x11+ x12+x13) + 25(x21+x22+x23)

st.

x11 + x21≤100 SugarConstraints

x12 + x22≤20Nut Constraints

x13 + x23≤30Chocolate Constraints

x12≥ 0.1(x11 + x12 + x13) or10% Chocolate ration in Slugger Candy

-0.1x11 +0.9x12-0.1x13) ≥0

x13≥ 0.1(x11 + x12 + x13) or

-0.1x11 -0.1x12+0.9x13) ≥010% nuts ration in Slugger Candy

x22≥ 0.2(x21 + x22 + x23) or

-0.2x21 +0.8x22-0.2x23) ≥0 20% nuts ration in Easy Out Candy

xij≥ 0 i=1,2; j=1,2,3Sign Constraints

Problem 9 P.93

Notation:

zi = Amount of investment on bond i.

Bond (i) where i = 1, 2, 3, 4

Decision Variable:

z1, z2, z3, z4

Max Expected Return = 13z1 + 8z2 + 12z3 + 14z4

st.

z1 +z2 + z3 + z4≤1000000Budget Constraints

6z1 + 8z2 + 10z3 + 9z4≥0.08(z1 +z2 + z3 + z4) or Worst-Case Return Constraints

5.92z1 + 7.92z2 + 9.92z3 + 8.92z4≥0

3z1 + 4z2 + 7z3 + 9z4≤6(z1 +z2 + z3 + z4) orAvg. Duration Constraints

-3z1 -2z2 + z3 + 3z4≤0

zi≤0.4(z1 +z2 + z3 + z4), i=1, 2, 3, 4 or Diversification Requirements

0.6z1 – 0.4z2 – 0.4z3 – 0.4z4≤0

– 0.4z1 + 0.6z2 – 0.4z3 – 0.4z4≤0

– 0.4z1 – 0.4z2 + 0.6z3 – 0.4z4≤0

– 0.4z1 – 0.4z2 – 0.4z3 + 0.6z4≤0

z1≥0, z2≥0, z3≥0, z4≥0Sign Constraints:

Problem 14 P.92

Notation:

xij = Amount of input j use to produce product i

Product (i) where i = 1 for Regular Gasoline and =2 for Premium Gasoline

Input (j) where j = 1 for Reformate, =2 for FCG, =3 for ISO, =4 for POL, =5 for MTB, =6 for BUT

Decision Variable:

x11, x12, x13, x14, x15, x16, x21, x22, x23, x24, x25, x26

Objective Function:

Max Profit = 29.49(x11+x12+x13+x14+x15+x16) + 31.43(x21+x22+x23+x24+x25+x26) – 12.75(x11+x12+x13+x14+x15+x16)– 12.75(x21+x22+x23+x24+x25+x26)

st.

Demand Constraints:
Regular Gasoline
Premium Gasoline / x11+x12+x13+x14+x15+x16≥9800
x21+x22+x23+x24+x25+x26≥30000
Ration Constraints:
FCG in Regular Gasoline
FCG in Premium Gasoline / x12≤0.38(x11+x12+x13+x14+x15+x16) or
0.62x12-0.38x11-0.38x13-0.38x14-0.38x15-0.38x16≤0
x22≤0.38 (x21+x22+x23+x24+x25+x26) or
-0.38x21+0.62x22-0.38x23-0.38x24-0.38x25-0.38x26) ≤0
Attribute requirements
RON in Regular Gasoline
RON in Premium Gasoline
RVP in Regular Gasoline
RVP in Premium Gasoline
ASTM(70) in Regular Gasoline
ASTM(70) in Premium Gasoline
ASTM(130) in Regular Gasoline
ASTM(130) in Premium Gasoline / 98.9x11+93.2x12+86.1x13+97x14+117x15+98x16≥
90(x11+x12+x13+x14+x15+x16)
or 8.9x11+3.2x12-3.9x13+7x14+27x15+8x16≥0
98.9x21+93.2x22+86.1x23+97x24+117x25+98x26≥
96(x21+x22+x23+x24+x25+x26)
or 2.9x21-2.8x22-9.9x23+x24+21x25+2x26≥0
7.66x11+9.78x12+29.52x13+14.51x14+13.45x15+166.99x16=
21.18(x11+x12+x13+x14+x15+x16) or
-13.52x11-11.40x12+8.34x13-6.67x14-7.73x15+145.81x16=0
7.66x21+9.78x22+29.52x23+14.51x24+13.45x25+166.99x26=
21.18(x21+x22+x23+x24+x25+x26) or
-13.52x21-11.40x22+8.34x23-6.67x24-7.73x25+145.81x26=0
-5x11+57x12+107x13+7x14+98x15+130x16≥
10(x11+x12+x13+x14+x15+x16)
or -15x11+47x12+97x13-3x14+88x15+120x16≥0
-5x21+57x22+107x23+7x24+98x25+130x26≥
10(x21+x22+x23+x24+x25+x26)
or -15x21+47x22+97x23-3x24+88x25+120x26≥0
46x11+103x12+100x13+73x14+100x15+100x16≥
50(x11+x12+x13+x14+x15+x16)
or -4x11+53x12+50x13+23x14+50x15+50x16≥0
46x21+103x22+100x23+73x24+100x25+100x26
≥50(x21+x22+x23+x24+x25+x26)
or -4x21+53x22+50x23+23x24+50x25+50x26≥0
Input Availability Constraints:
Reformate
FCG
ISO
POL
MTB / x11+x21≤15572
x12+x22≤15434
x13+x23≤6709
x14+x24≤1190
x15+x25≤748
Sign Constraints: / x11≥0, x12≥0, x13≥0, x14≥0, x15≥0, x16≥0,
x21≥0, x22≥0, x23≥0, x24≥0, x25≥0, x26≥0

Problem 4 P.98

Notation:

R0 = Amount of raw material purchased

xij = Amount of product i produced from input j

xi = Amount produced and sold of product i

Product (I) where i = 1, 2, 3

Input (J) where j =1 for product 1, and =2 for product 2

Decision Variable:

R0, x1, x2, x3, x21, x31, x32

Objective Function:

Max Profit = Revenue – Raw material Cost – Processing Cost

10(x1) + 20(x2) + 30(x3) – 25R0 – (R0+x21+2x31+6x32)

Constraints:

Balance Constraints: / 3R0 =x1+x21 +x31
R0+x21=x2 +x32
x3=x31 +x32
Maximum Demand Constraints:
Product 1
Product 2
Product 3 / x1≤5000
x2≤5000
x3≤3000
Labor Constraint: / 2R0+2x21+3x31+x32≤25000
Sign Constraints: / R0≥0, x1≥0, x2≥0, x3≥0, x21≥0, x31≥0, x32≥0

Problem 6 P.97

Notation:

T1 = Times running process 1 (a 1-hr process 1 running requires 3 oz of raw material)

T2 = Times running process 2 (a 1-hr process 2 running requires 3 oz of raw material)

xij = Amount of chemical j used to produce drug i

Drug (i) where i = 1, 2

Chemical (j) where j = 1, 2

Decision Variable:

T1, T2, x11, x12, x21, x22

Objective Function:

Max Sale Revenue = 6(x11+ x12) + 4(x21+ x22)

Constraints:

Balance Constraints: / x11+x21≤3T1+3T2
x12+x22≤3T1+T2
Ration Constraints:
Chem 1 in Drug 1
Chem 1 in Drug 2 / x11≥0.65(x11+x12) or 0.35x11-0.65x12 ≥0
x21≥0.55(x21+x22) or 0.45x21-0.55x21-0.55x22 ≥0
Labor Constraint: / 2T1+3T2 ≤120
Raw Material Availability Constraint: / 3T1+2T2 ≤100
Sign Constraints: / T1≥0, T2≥0,x11≥0, x12≥0, x21≥0, x22≥0

Problem 10 P.97

Notation:

K0 = Amount of Kiln used in production

xij = Amount of product i produced from input j

xi = Amount of product i produced

Lime Grade (i) where i = 1, 2, 3, 4, 5, 6

Input (j) where j =1 for lime grade 1, =2 for lime grade 2, =3 for lime grade 3, =4 for lime grade 4,

and =5 for lime grade 5

yj=Amount of product i sold

Decision Variable:

K0, x1, x2, x3, x4, x5, x6, x31, x41, x43, x51, x54, x61, x62, x64, x65, y1, y2, y3, y4, y5, y6.

Objective Function:

Max Profit = Revenue – Raw Material Cost – Processing Cost –Disposal Cost

Where

Revenue = 12y1+14y2+10y3+18y4+20y+25y6

Raw Material Cost = 150K0

Processing Cost = 2(x31/0.3)+(x62)+(x43/0.8)+(x54/0.5)+2(x65/0.9)

= 6.67x31+x62+1.25x43+2x54+2.22x65

x1≥ y1, x2≥ y2, x3≥ y3, x4≥ y4, x5≥ y5, x6≥ y6 (Produced lime is greater than those sold)

x1- y1 is the disposal part for grade 1.

Disposal Cost = 3(x1- y1)+2(x2- y2)+3( x3- y3)+2( x4- y4) +4( x5- y5)+2( x6- y6)

Max Z = 12y1+14y2+10y3+18y4+20y+25y6_ - 150K0 – (6.67x31+x62+1.25x43+2x54+2.22x65) - 3(x1-y1)+2 (x2 -y2)+3 ( x3- y3)+2( x4-y4) +4( x5-y5)+2( x6-y6)

Constraints:

Balance Constraints / x31=0.3(2K0-x1) or x31-0.6K0+0.3x1=0
x41=0.2(2K0-x1) or x41-0.4K0+0.2x1=0
x51=0.3(2K0-x1) or x51-0.6K0+0.3x1=0
x61=0.2(2K0-x1) or x61-0.4K0+0.2x1=0
x62=(3K0-x2) or x62-3K0+x2=0
x43=0.8(K0+x31-x3) or x43-0.8K0-0.8x31+0.8x3=0
x54=0.5(1.5K0+x41+x43-x4)
or x54-0.75K0-0.5x41-0.5x43+0.5x4=0
x64=0.5(1.5K0+x41+x43-x4)
or x64-0.75K0-0.5x41-0.5x43+0.5x4=0
x65=0.9(2K0+x51+x54-x5)
or x65-1.8K0-0.9x51-0.9x54+0.9x5=0
3K0+x61+x62+x63+x64+x65-x6=0
Demand constraints / y1 ≤ 20
y2 ≤ 30
y3≤ 40
y4≤35
y5≤25
y6 ≤ 50
Demand and supply constraints / x1≥ y1, x2≥ y2, x3≥ y3, x4≥ y4, x5≥ y5, x6≥ y6
Sign Constraints: / K0≥0, x1≥0, x2≥0, x3≥0, x4≥0, x5≥0, x6≥0,
x31≥0, x41≥0, x43≥0, x51≥0, x54≥0, x61≥0,
x62≥0, x64≥0, x65≥0, y1≥0, y2≥0, y3≥0, y4≥0, y5≥0, y6≥0