Linear Programming Part 3 PDF

Preview

Summary

The answer of exercise 4. (Linear Programming Part 3)...

Description

Exercise Part 4

Exercise 4.1 The following linear program is given: max s.t.

2x1 −x2 +x3 3x1 −2x2 +2x3 −x1 +x2 +x3 x1 −x2 +x3 x1 x2 x3

≤ 15 ≤3 ≤3 ≥0 ≥0 ≥0

The final system of equations associated with the optimal solution is given as follows, where x4 , x 5 and x6 are slack variables for the constraints.: Z x1

+2x3 +x4 +x5

= 18

+4x3 +x4 +2x5

= 21

x2 +5x3 +x4 +3x5

= 24

2x3

+x5

+x6 = 6

a) Determine the optimal solution of the problem! b) Construct the corresponding final tableau! c) Perform a sensitivity analysis related to the right-hand side of the constraints!

Exercise 4.2 A production planning problem for two products was formulated as a linear program and it was solved using the Simplex algorithm. There were three constraints 1

related to the available machine capacity, the personnel capacity and the available raw material. The solution is presented in the following tableau: x1

x2 s3

s4 s5 (machine capacity)

s3

0 −5.2

1 −0.6

0 1020

x1

1

2.4

0

0.2

0

60

(raw material capacity)

s5

0

0.5

0

0

1

125

(personnel capacity)

0

80

0

15

0 4500

a) What are the optimal values for the decision variables and the objective function? b) Is it reasonable to enlarge the machine capacity? Explain your answer! c) How will the optimal value of the objective function change if there is one more unit of raw material available? What are the production quantities for product one and two in this situation (The solution can also have non-integer values!) Explain your answer! d) Determine the amount by which the profit margin of product two has to be increased such that the optimal production quantities will change. Explain your answer!

2

Exercise 4.3 A company is producing two different products where each product requires three production steps at the same resources. The three steps are preparation, part production and final assembly. The required resources for each production step as well as the available capacities are given in the following table

preparation part production final assembly

Product 1 [hours/unit] 5 2 9

Product 2 [hours/unit] 2 4 3

Available Capacity [hours/unit] 80 100 90

The profit margin for product 1 (2) is given as 15 (9) e. Due to the limited capacity, the production planner has to decide which quantities have to be produced from each product. He uses the following mathematical model for decision support: max 15x1 s.t. 5x1 2x1 9x1 x1 ,

+9x2 +2x2 +4x2 +3x2 x2

≤ 80 ≤ 100 ≤ 90 ≥0

For this linear program exact one optimal solution exists x∗1 = 2, x ∗2 = 24, Z ∗ = 246 Use graphic 1 to answer the questions a) Which of the three production steps does not require the maximum capacity? b) How much capacity must be available at the part production such that it is optimal to produce only product 2? c) Determine all combinations for the profit margins which lead to more than one optimal solution! d) Assume now that in the final assembly the maintenance of the machines requires one time unit of the available capacity. What is the effect on the profit? 3

Figure 1: Graphical solution of the problem

4

Exercise 4.4 A cargo aircraft has two compartments to transport freight: in the front and at the back. For each compartment there exists a maximum allowed volume and a maximum allowed weight: division front back

weight (tons) 22 30

volume (m3 ) 7000 5000

In order not to jeopardize the balance of the aircraft, the loading weight in the individual compartments must be the same percentage of the maximum permissible weight of the compartments. With the next flight the following freight is available for transportation. freight 1 2 3

weight (tons) 20 16 25

volume(m3 /tons) 500 700 600

profit (Euro/ton) 280 360 320

The freight can be divided arbitrarily and the aircraft should be loaded such that the maximum profit can be obtained. Formulate the problem as a linear program to determine the optimal loading of the cargo aircraft. Define the decision variables precisely, determine the objective function and all constraints.

5

Exercise 4.5 Consider the following linear program in tableau format x1 x2 x3

x4 x5

x6

x1

1

0

0

0

1 −2 1

x3

0

0

1 −1

3 −2 3

x2

0

1

0

5

0 −1 β

0

0

0

2

4

β

How do you have to choose the parameter β such that the linear program a) has at least one initial basic feasible solution? b) has at least one optimal solution which is not degenerated? c) has just one optimal solution which is degenerated? d) has several optimal solutions? e) has an unbounded feasible region?

6...