1) Consider the following LP:
Maximize z=4x1+5x2+3x3
Subject to:
x1+x2+4x3≤6
x1+2x2+x3≤7
x1+4x2+2x3≤12
a) Add slack variables x4, x5 and x6, and perform iterations of the simplex algorithm. Show each completed iteration using tableau. The final (filled) tableau of the primal must be provided.
|
Basis
|
z
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
RHS
|
|
z
|
1
|
0
|
0
|
|
|
|
0
|
|
|
x1
|
0
|
1
|
0
|
|
|
|
0
|
|
|
x2
|
0
|
0
|
1
|
|
|
|
0
|
|
|
x6
|
0
|
0
|
0
|
|
|
|
1
|
|
b) Write the dual of this LP.
2)(a) Sunco Oil produces oil at two wells. Well 1 can produce as many as 150,000 barrels per day, and Well 2 can produce as many as 200,000 barrels per day. It is possible to ship oil directly the wells to Sunco's customers in Los Angeles and New York. Alternatively, Sunco could transport oil to the ports of Mobile and Galveston and then ship it by tank to New York or Los Angeles. Los Angeles requires 160,000 barrels per day, and New York requires 140,000 barrels per day. The cost of shipping 1,000 barrels between two points are shown in the table below. Formulate a transshipment model to minimize the transport costs in meeting the oil demands of Los Angeles and New York.
|
From
|
To ($)
|
|
Well 1
|
Well 2
|
Mobile
|
Galveston
|
N.Y.
|
L.A.
|
|
Well 1
|
0
|
---
|
10
|
13
|
25
|
28
|
|
Well 2
|
---
|
0
|
15
|
12
|
26
|
25
|
|
Mobile
|
---
|
---
|
0
|
6
|
16
|
17
|
|
Galveston
|
---
|
---
|
6
|
0
|
14
|
16
|
|
N.Y.
|
---
|
---
|
---
|
---
|
0
|
15
|
|
L.A.
|
---
|
---
|
---
|
---
|
15
|
0
|
(b) In (a), assume that before being shipped to Los Angeles or New York, all oil produced at the wells must be refined at either Galveston or Mobile. To refine 1,000 barrels of oil costs $12 at Mobile and $10 at Galveston. Assuming that both Mobile and Galveston have infinite capacity, reformulate the problem to minimize the daily cost of transporting and refining the oil requirements of Los Angeles and New York.
3) The Speedem-Feedem Airline must decide how many new flight attendants to hire and train over the next six months. The requirements, expressed in attendant-hours needed, are tabled below:
|
Month
|
Jan
|
Feb
|
March
|
April
|
May
|
June
|
|
Hours
|
8000
|
9000
|
8000
|
10000
|
9000
|
12000
|
It takes a month of training before an attendant may be put on regular flight duty. During that month the trainee requires 100 hours of training by a regular flight attendant so that each trainee reduces the number of regular attendant flight hours by 100. Each regular attendant works up to 150 hours per month and Feedem-Speedem has 60 regular attendants available at the beginning of January. If regular attendant flight hours available exceed the requirements in a given month other duties are assigned and the attendants are not laid off. At the end of each month 10% of the experienced attendants quit or leave to form a start-up. An experienced attendant costs the company $5000 per month in salary and benefits. A trainee costs $2500. Let xt be the number of attendants hired each month where t=1 for January. There are 60 regular attendees and no trainees present at the beginning of January. Formulate and solve the LP to find the least cost values of xt (t=1...6) that satisfy the demand. Don't worry about fractional solutions.
4) The Dewright Company is considering three new products to replace current models that are being discontinued, so their chief systems engineer has been assigned the task of determining which mix of these products should be produced. Management wants primary consideration given to three factors: long-run profit, stability in the work force, and the level of capital investment that would be required now for new equipment. In particular, they have established the goals of (1) achieving a long-run profit (net present value) of at least $125,000,000 from these products, (2) maintaining the current employment level of 4,000 employees, and (3) holding the capital investment to less than $55,000,000. However, management realizes that it probably won't be possible to attain all of these goals simultaneously, so they have discussed their priorities with the chief systems engineer. This discussion has led to setting penalty weights of 5 for missing the profit goal (per million dollars under), 2 for going over the employment goal (per hundred employees) and 4 for going under this same goal, and 3 for exceeding the capital investment goal (per million dollars over). Each new product's contribution to profit, employment level, and capital investment level is proportional to the numbers produced. These contributions per unit rate of production are shown in the table below, along with the goals and penalty weights.
Data for Dewright Company Goal Programming Problem
|
Factor
|
Unit Contribution
Product
1 2 3
|
Goal (Units)
|
Penalty
Weight
|
|
Long-run profit
Employment level
Capital investment
|
12 9 15
5 3 4
5 7 8
|
≥ 125 (millions of dollars)
= 40 (hundreds of employees)
≤ 55 (millions of dollars)
|
5
2(+), 4(-)
3
|
Formulate and solve the Dewright Company's problem.
5) A young couple, Eve and Steven, want to divide their four main household chores so that each is responsible for two of them but the total time spent on housework is kept to a minimum. The table below shows how many hours each partner requires for each task.
|
|
Hours Required for each Task
|
|
Partner
|
Marketing
|
Cooking
|
Cleaning
|
Laundering
|
|
Eve
|
3.2
|
7.4
|
4.1
|
2.5
|
|
Steven
|
4.0
|
6.8
|
4.5
|
2.7
|
i) formulate and solve an integer program to determine who does what.
ii) modify the formulation by adding a constraint that whoever does the cleaning should not also do the marketing. Re-solve the modified formulation.
6) John Fixx, a master plumber, is considering a five year investment plan using the $2200 windfall from his last job in which he was able to parlay a leaky faucet into a major operation by strategically breaking a series of pipes and valves. At the beginning of each year he can invest money in one or two year time deposits. The bank pays 8% interest on one year deposits and 17% (total) on two year deposits. In addition, John has learned that West World Ltd. will be offering three year certificates starting at the beginning of the second year of John's plan. These certificates will return 27% (total). If Fixx reinvests his money every year formulate and solve the LP that will determine the investment strategy that will maximize John's total cash at the end of five years. There is a substantial penalty for early withdrawal from any of the investments so John will not consider any investment that matures beyond the end of the fifth year.