EGR 511



EGR 599 Advanced Engineering Math II _____________________

LAST NAME, FIRST

Problem set #4

1. (P. 15.1 Chapra1) A company makes two types of products, A and B. These products are produced during a 40-hour work week and then shipped out at the end of the week. They require 20 and 5 kg of raw material per kg of product, respectively, and the company has access to 10,000 kg of raw material per week. Only one product can be created at a time with a production times for each of 0.05 and 0.15 hrs, respectively. The plant can only store 550 kg of total product per week. Finally, the company makes profits of $45 and $30 on each unit of A and B, respectively.

(a) Set up the linear programming problem to maximize profit.

(b) Solve the linear programming problem graphically.

(c) Solve the linear programming problem with the simplex method.

(d) Solve the linear programming problem with Matlab.

Solution

(a) Set up the linear programming problem to maximize profit.

Define xa = amount of product A produced, and xb = amount of product B produced. The objective function is to maximize profit,

[pic]

Subject to the following constraints

[pic]

[pic]

[pic]

[pic]

(b) To solve graphically, the constraints can be reformulated as the following straight lines

[pic]

[pic]

[pic]

The objective function can be reformulated as

[pic]

The constraint lines can be plotted on the xb-xa plane to define the feasible space. Then the objective function line can be superimposed for various values of P until it reaches the boundary. The result is P ( 23700 with xa ( 483 and xb ( 67. Notice also that material and storage are the binding constraints and that there is some slack in the time constraint.

[pic]

(c) The simplex tableau for the problem can be set up and solved as

| |Basis |P |xa |xb |S1 |S2 |S3 |Solution |Intercept |

| |P |1 |-45 |-30 |0 |0 |0 |0 | |

|material |S1 |0 |20 |5 |1 |0 |0 |10000 |500 |

|time |S2 |0 |0.05 |0.15 |0 |1 |0 |40 |800 |

|storage |S3 |0 |1 |1 |0 |0 |1 |550 |550 |

| | | | | | | | | | |

| |Basis |P |xa |xb |S1 |S2 |S3 |Solution |Intercept |

| |P |1 |0 |-18.75 |2.25 |0 |0 |22500 | |

|xa |xa |0 |1 |0.25 |0.05 |0 |0 |500 |2000 |

|time |S2 |0 |0 |0.1375 |-0 |1 |0 |15 |109.0909 |

|storage |S3 |0 |0 |0.75 |-0.05 |0 |1 |50 |66.66667 |

| | | | | | | | | | |

| |Basis |P |xa |xb |S1 |S2 |S3 |Solution |Intercept |

| |P |1 |0 |0 |1 |0 |25 |23750 | |

|xa |xa |0 |1 |0 |0.067 |0 |-0.333 |483.33333 | |

|time |S2 |0 |0 |0 |0.007 |1 |-0.183 |5.8333333 | |

|xb |xb |0 |0 |1 |-0.07 |0 |1.333 |66.666667 | |

(d) Solve the linear programming problem with Matlab.

The problem is reformulated using slack variable S1, S2, and S3

Minimize y = ( 45xa ( 30xb

Subject to

20xa + 5xb + S1 = 10000

0.05xa + 0.15xb + S2 = 40

xa + xb + S3 = 550

xa, xb, S1, S2, and S3 ( 0

The arguments for the Matlab command X=LINPROG(f, A, b, Aeq, beq, LB, UB) are given as

f = [pic], A = 0, b = 0, Aeq = [pic], beq = [pic], LB = [pic], UB = [pic]

--------------------------------------------------------------------

% Set 4, Problem 1

f=[-45;-30;0;0;0];

A=zeros(5,5);

b=zeros(5,1);

Aeq=[20 5 1 0 0 ;0.05 0.15 0 1 0;1 1 0 0 1;0 0 0 0 0;0 0 0 0 0];

beq=[10000;40;550;0;0];

LB=[0;0;0;0;0];UB=[inf;inf;inf;inf;inf];

x=linprog(f,A,b,Aeq,beq,LB,UB)

>> s4p1

Optimization terminated successfully.

x =

483.3333

66.6667

0.0000

5.8333

0.0000

------------------------------------------------------

The solution from the Matlab program is

xa = 483.3333

x2 = 66.6667

S1 = 0

S2 = 5.8333

S3 = 0

2. (P. 15.2 Chapra)

A gas processing plant receives a fixed amount of raw gas each week. The raw gas is processed into three grades of heating gas, regular, premium, and supreme quality. Their production involves both time and on-site storage constraints. For example, only one of the grades can be produced at a time, and the facility is open for only 80 hrs/week. There is limited on-site storage for each of the products. All these factors are listed in Table 4-1 with a metric ton denoted tonne equal to 1000 kg.

Table 4-1

| |Product | |

|Resource |Regular |Premium |Supreme |Availability |

|Raw gas |7 m3/tonne |11 m3/tonne |15 m3/tonne |154 m3/week |

|Production time |10 hr/tonne |8 hr/tonne |12 hr/tonne |80 hr/week |

|Storage |9 tonnes |6 tonnes |5 tonnes | |

|Profit |150/tonne |175/tonne |250/tonne | |

(a) Set up the linear programming problem to maximize profit.

(b) Solve the linear programming problem with the simplex method.

(c) Solve the linear programming problem with Matlab.

Solution

(a) Set up the linear programming problem to maximize profit.

The total LP formulation is given by

[pic] {Maximize profit}

subject to

[pic] {Material constraint}

[pic] {Time constraint}

[pic] {“Regular” storage constraint}

[pic] {“Premium” storage constraint}

[pic] {“Supreme” storage constraint}

[pic] {Positivity constraints}

(b) The simplex tableau for the problem can be set up and solved as

Basis |P |x1 |x2 |x3 |S1 |S2 |S3 |S4 |S5 |Solution |Intercept | |P |1 |-150 |-175 |-250 |0 |0 |0 |0 |0 |0 | | |S1 |0 |7 |11 |15 |1 |0 |0 |0 |0 |154 |10.2667 | |S2 |0 |10 |8 |12 |0 |1 |0 |0 |0 |80 |6.66667 | |S3 |0 |1 |0 |0 |0 |0 |1 |0 |0 |9 |( | |S4 |0 |0 |1 |0 |0 |0 |0 |1 |0 |6 |( | |S5 |0 |0 |0 |1 |0 |0 |0 |0 |1 |5 |5 | | | | | | | | | | | | | | |Basis |P |x1 |x2 |x3 |S1 |S2 |S3 |S4 |S5 |Solution |Intercept | |P |1 |-150 |-175 |0 |0 |0 |0 |0 |250 |1250 | | |S1 |0 |7 |11 |0 |1 |0 |0 |0 |-15 |79 |7.18182 | |S2 |0 |10 |8 |0 |0 |1 |0 |0 |-12 |20 |2.5 | |S3 |0 |1 |0 |0 |0 |0 |1 |0 |0 |9 |( | |S4 |0 |0 |1 |0 |0 |0 |0 |1 |0 |6 |6 | |x3 |0 |0 |0 |1 |0 |0 |0 |0 |1 |5 |( | | | | | | | | | | | | | | |Basis |P |x1 |x2 |x3 |S1 |S2 |S3 |S4 |S5 |Solution |Intercept | |P |1 |68.75 |0 |0 |0 |21.88 |0 |0 |-12.5 |1687.5 | | |S1 |0 |-6.75 |0 |0 |1 |-1.375 |0 |0 |1.5 |51.5 |34.3333 | |x2 |0 |1.25 |1 |0 |0 |0.125 |0 |0 |-1.5 |2.5 |-1.66667 | |S3 |0 |1 |0 |0 |0 |0 |1 |0 |0 |9 |( | |S4 |0 |-1.25 |0 |0 |0 |-0.125 |0 |1 |1.5 |3.5 |2.33333 | |x3 |0 |0 |0 |1 |0 |0 |0 |0 |1 |5 |5 | | | | | | | | | | | | | | |Basis |P |x1 |x2 |x3 |S1 |S2 |S3 |S4 |S5 |Solution | | |P |1 |58.3333 |0 |0 |0 |20.83 |0 |8.33 |0 |1716.7 | | |S1 |0 |-5.5 |0 |0 |1 |-1.25 |0 |-1 |0 |48 | | |x2 |0 |0 |1 |0 |0 |0 |0 |1 |0 |6 | | |S3 |0 |1 |0 |0 |0 |0 |1 |0 |0 |9 | | |S5 |0 |-0.8333 |0 |0 |0 |-0.083 |0 |0.67 |1 |2.3333 | | |x3 |0 |0.83333 |0 |1 |0 |0.083 |0 |-0.67 |0 |2.6667 | | |

(c) Solve the linear programming problem with Matlab.

The problem is reformulated as

Minimize y =[pic]

[pic] {Material constraint}

[pic] {Time constraint}

[pic] {“Regular” storage constraint}

[pic] {“Premium” storage constraint}

[pic] {“Supreme” storage constraint}

[pic] {Positivity constraints}

We use the Matlab command X=LINPROG(f, A, b, Aeq, beq, LB, UB)

The coefficient vector f for the objective function is

f = [pic]

The matrix coefficient A for the inequality constraints is

A = [pic]

The right hand vector b for the inequality constraints is

b = [pic]

Since there are no equality constraints in this example, Aeq and beq are zeros.

Aeq = 0 and beq = 0

The lower and upper bounds vectors are given by

LB = [pic] and UB = [pic]

The following Matlab statements are used to solve this linear programming problem.

Matlab Program -----------------------------------------------------

% Set 4, Problem 2

f=[-150;-175;-250];

A=[7 11 15;10 8 12;0 0 0];

b=[154;80;0];

Aeq=zeros(3,3);

beq=zeros(3,1);

LB=[0;0;0];UB=[9;6;5];

x=linprog(f,A,b,Aeq,beq,LB,UB)

>> s4p2

Optimization terminated successfully.

x =

0.0000

6.0000

2.6667

-------------------------------------------------------------------------------------------------------------

The solution from the Matlab program is

x1 = 0

x2 = 6

x3 = 2.6667

3. (P. 15.3 Chapra)

Consider the linear programming problem:

Maximize f(x, y) = [pic]x + y, subject to

x + 2.5y ( 15

x + y ( 7

2x + y ( 9

x ( 0 and y ( 0

(a) Solve the linear programming problem graphically.

(b) Solve the linear programming problem with the simplex method.

(c) Solve the linear programming problem with Matlab.

Solution

(a) Solve the linear programming problem graphically.

To solve graphically, the constraints can be reformulated as the following straight lines

y = 6 ( 0.4x

y = 7 ( x

y = 9 ( 2x

The objective function can be reformulated as

y = ( [pic]x +f(x, y)

The constraint lines can be plotted on the x-y plane to define the feasible space. Then the objective function line can be superimposed for various values of f(x, y) until it reaches the boundary. The result is f(x, y) ( 8.33 with x = 23 and y = 5.

[pic]

(b) Solve the linear programming problem with the simplex method.

Maximize f(x, y) = [pic]x + y, subject to

x + 2.5y + S1 = 15

x + y + S2 = 7

2x + y + S3 = 9

x, y, S1, S2, S3 ( 0

at A, x = 0 y = 0

S1 = 15, S2 = 7, S3 = 9, and f(x, y) = 0

at B, y = 0 S3 = 0

x + S1 = 15

x + S2 = 7

2x = 9

x = 4.5, S1 = 10.5, S2 = 2.5, and f(x, y) = 7.5

at C, S3 = 0 S2 = 0

x + 2.5y + S1 = 15

x + y = 7

2x + y = 9

x = 2, y = 0, S1 = 0.5, and f(x, y) = 8.33

(c) Solve the linear programming problem with Matlab.

The problem is reformulated as

Minimize y = ( [pic]x ( y

x + 2.5y + S = 15

x + y ( 7

2x + y ( 9

x, y, and S ( 0

We use the Matlab command X=LINPROG(f, A, b, Aeq, beq, LB, UB).

The coefficient vector f for the objective function is

f = [pic]

The matrix coefficient A for the inequality constraints is

A = [pic]

The right hand vector b for the inequality constraints is

b = [pic]

The equality constraints Aeq and beq are given as

Aeq = [pic] and beq = [pic]

The lower and upper bounds vectors are given by

LB = [pic] and UB = [pic]

The following Matlab statements are used to solve this linear programming problem.

Matlab Program -----------------------------------------------------

% Set 4, Problem 3

f=[-5/3;-1;0];

A=[1 1 0;2 1 0;0 0 0];

b=[7;9;0];

Aeq=[1 2.5 1; 0 0 0;0 0 0];

beq=[15;0;0];

LB=[0;0;0];UB=[inf;inf;inf];

x=linprog(f,A,b,Aeq,beq,LB,UB)

>> s4p3

Optimization terminated successfully.

x =

2.0000

5.0000

0.5000

-------------------------------------------------------------------------------------------------------------

The solution from the Matlab program is

x1 = 2

x2 = 5

S = 0.5

4. (P. 13.7 Chapra) Employ the following methods to find the maximum of

f(x) = 2x ( 1.75x2 + 1.1x3 ( 0.25x4

a) Quadratic interpolation (x0 = 1.75, x1 = 2, x2 = 2.25, iterations = 5)

b) Newton method (x0 = 2.5, |xi+1 ( xi| < 0.01)

Solution

f(x) = 2x ( 1.75x2 + 1.1x3 ( 0.25x4

f’(x) = 2 ( 3.5x + 3.3x2 ( x3

f”(x) = ( 3.5 + 6.6x ( 3x2

% Set 4, problem 4

fx = '2*x - 1.75*x^2 + 1.1*x^3 - 0.25*x^4';

x0 = 1.75; x = x0; f0 = eval(fx);

x1 = 2; x = x1; f1 = eval(fx);

x2 = 2.25; x = x2; f2 = eval(fx);

f3save=f0;

disp('Quadratic interpolation')

for i=1:5

top = f0*(x1*x1-x2*x2)+f1*(x2*x2-x0*x0)+f2*(x0*x0-x1*x1);

bot = 2*f0*(x1-x2)+2*f1*(x2-x0)+2*f2*(x0-x1);

x3 = top/bot;

x = x3; f3 = eval(fx);

fprintf('x3 = %10.5f, f(x3) = %10.5f\n',x,f3)

% if abs(f3save-f3) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download