Simplex Method HW
polands
P.docx
( 1 ) ( 2 )Problem 1. Determine all the extreme points of the convex set {x ∈ R2 | x2 + x2 ≤ 1, x1 + x2 ≤ 1}.
Problem 2. Using Representation theorem(Carath´eodory 1911), present in a suitable form of the convex polyhedron {x ∈ R2 | x1 + x2 ≥ 1, x1 ≥ 0, x2 ≥ 0}.
Problem 3. Determine the extreme points of the convex hull {(1, 1)T , (2, 3)T , (3, 1)T , (2, 2)T }.
Problem 4. A production manager is planning the scheduling of three products on four machines. Each product can be manufactured on each of the machines. The unit production costs (in $) are summarized below.
Machine
|
|
1 |
2 |
3 |
4 |
|
Product 1 |
4 |
4 |
5 |
7 |
|
Product 2 |
6 |
7 |
5 |
6 |
|
Product 3 |
12 |
10 |
8 |
11 |
The time (in hours) required to produce a unit of each product on each of the machines is summarized below.
Machine
|
|
1 |
2 |
3 |
4 |
|
Product 1 |
0.3 |
0.25 |
0.2 |
0.2 |
|
Product 2 |
0.2 |
0.3 |
0.2 |
0.25 |
|
Product 3 |
0.8 |
0.6 |
0.6 |
0.5 |
Suppose that 3000, 6000 and 4000 units of the products are required, and that the available machine hours are 1500, 1200, 1500, and 2000, respectively. Formulate the scheduling problem as a liner program, and then solve it.
Problem 5. Polly wonders how much money she must spend on food in order to get all the energy (2,000 kcal), protein (55 g), and calcium (800 mg) that she needs every day. She chooses six foods that seem to be cheap sources of the nutrients and collects her data in the following table of nutritive value per serving.
|
Food |
Serving size |
Energy (kcal) |
Protein (g) |
Calcium (mg) |
Price per serving (cents) |
|
Oat meal |
28 g |
110 |
4 |
2 |
3 |
|
Chicken |
100 g |
205 |
32 |
12 |
24 |
|
Eggs |
2 large |
160 |
13 |
54 |
13 |
|
Whole milk |
237 cc |
160 |
8 |
285 |
9 |
|
Cherry pie |
170 g |
420 |
4 |
22 |
20 |
|
Pork withbeans |
260 g |
260 |
14 |
80 |
19 |
She also decides to impose servings-per-day limits on all foods. To design the most economical menu, she speculates about some as yet unspecified menu, consisting of x1 servings of oatmeal, x2 servings of chicken,
|
Food |
Servings at most per day |
|
Oat meal |
4 |
|
Chicken |
3 |
|
Eggs |
2 |
|
Whole milk |
8 |
|
Cherry pie |
2 |
|
Pork withbeans |
2 |
and so on. She wants to find numbers x1, x2, . . . , x6 that satisfy her self-imposed servings-per-day limits, meet the requirements for energy, protein, calcium, and yet minimize the cost. Since the decision variables are already defined, you only need to write a linear programming formulation and then solve it.
Problem 6. Solve the following problem using Simplex Method.
Minimize −2x1 − x2
subject to −x1 − x2 ≤ 0
−3x1 + x2 ≥ −3
x1, x2 ≥ 0.
You need to present the optimal solution and also draw the graph, which must include the cost vector and extreme points. Please explain (illustrate) how BFS moves until the optimal solution is found. Note: the problem might be unbounded or have alternative solutions.
Problem 7. Solve the following problem using Simplex Method.
Minimize −4x1 − 2x2
subject to 2x1 + x2 ≤ 11
x1 − x2 ≤ 4
x1, x2 ≥ 0.
You need to present the optimal solution and also draw the graph, which must include the cost vector and extreme points. Please explain (illustrate) how BFS moves until the optimal solution is found. Note: the problem might be unbounded or have alternative solutions.
Problem 8. Consider the following constraints:
2x1 + 3x2 ≤ 6
−2x1 + x2 ≤ 2 x1 − 2x2 ≤ 0 x1, x2 ≥ 0.
(a) Draw the feasible region.
(b) Identify the extreme points, and at each extreme point identify all possible basic and nonbasic variables.
(c) Suppose that a move is made from the extreme point (0, 2)T to the extreme point (0, 0)T in the (x1, x2) space. Specify the possible entering and leaving variables.
Problem 9. The starting and current tableaux of a given problem are shown below. Find the values of the unknowns a through n.
Table 1: Starting tableau
z x1 x2 x3 x4 x5 RHS
|
1 |
a |
1 |
-3 |
0 |
0 |
0 |
|
0 |
b |
c |
d |
1 |
0 |
6 |
|
0 |
-1 |
2 |
e |
0 |
1 |
1 |
Table 2: Current tableau
z x1 x2 x3 x4 x5 RHS
|
1 |
0 |
-1/3 |
j |
k |
l |
n |
|
0 0 |
g h |
2/3 i |
2/3 -1/3 |
1/3 1/3 |
0 1 |
f m |
Problem 10. While solving a standard form problem, we arrive at the following tableau, with x3, x4 and
x5 being the basic variables:
z x1 x2 x3 x4 x5 RHS
|
1 |
δ |
-2 |
0 |
0 |
0 |
-10 |
|
0 |
-1 |
ν |
1 |
0 |
0 |
4 |
|
0 |
α |
-4 |
0 |
1 |
0 |
1 |
|
0 |
γ |
3 |
0 |
0 |
1 |
β |
The entries α, β, γ, δ, ν in the tableau are unknown parameters. For each one of the following statements, find some parameter values that will make the statement true.
(a) (4 pt) The current solution is optimal and there are multiple optimal solutions.
(b) (4 pt) The optimal cost is −∞.
(c) (4 pt) The current solution is feasible but not optimal.
Problem 11. Consider the following simplex tableau for a minimization problem (the constraints are of the
≤ type and x3, x4 and x5 are the slacks.)
z x1 x2 x3 x4 x5 RHS
|
1 |
0 |
a |
0 |
b |
0 |
f |
|
0 0 0 |
1 0 0 |
−2 −3 0 |
0 1 0 |
1 −2 3 |
0 0 1 |
c d e |
Suppose that a < 0, b ≤ 0, and c, d, e ≥ 0.
(a) Find B−1.
(b) Find B.
(c) Is the tableau optimal?
(d) Give the original tableau (in terms of the unknowns).
(e) From the tableau identify cBB−1 and give its interpretation. Now, suppose that a > 0, b ≤ 0 and c, d, e ≥ 0.
(f) Is the new tableau optimal?
(g) Give an extreme direction.
(h) Let a = 5 and f = −10. Give a feasible solution having z = −150.
Problem 12. The objective is to maximize 2x1 − 4x2, and the slack variables are x3 and x4. The constraints are ≤ type.
z x1 x2 x3 x4 RHS
|
1 |
b |
1 |
f |
g |
8 |
|
0 0 |
c d |
0 e |
1 0 |
1/5 2 |
4 a |
(a) Find the unknowns a through g.
(b) Find B−1.
(c) Find ∂x 3 , ∂z , ∂z , ∂x1 .
∂x2 ∂b1 ∂x4 ∂b2
(d) Is the tableau optimal?
