MA 3231 Linear Programming Section E162 Assignment 1

MA 3231
Linear Programming
Section E162
Assignment 1
Content: up to Section 2.5
Due: July 16, at noon
1. A steel company must decide how to allocate next week’s time on a rolling mill, which is
a machine that takes unfinished slabs of steel as input and can produce either of two
semi-finished products: bands and coils. The mill’s two products come off the rolling
line at different rates: bands at 200 tons per hour, and coils at 140 tons per hour.
They also produce different profits: Bands at $25 per ton, and coils at $30 per ton.
Based on currently booked orders, the following upper bounds are placed on the amount
of each product to produce: Bands at 6, 000 tons, and coils at 4, 000 tons.
Given that there are 40 hours of production time available this week, the problem is to
decide how many tons of bands and how many tons of coils should be produced to yield
the greatest profit. Formulate this as a linear programming problem in standard form.
Can you solve this problem by inspection?
2. A small airline flies between three cities: Ithaca, Newark, and Boston. They offer seveal
flights but, for this problem, we focus on the Friday afternoon flight that departs from
Ithaca, stops in Newark, and continues to Boston. There are three types of passengers:
(a) Those traveling from Ithaca to Newark.
(b) Those traveling from Newark to Boston.
(c) Those traveling from Ithaca to Boston.
2
The aircraft is a small commuter plane that seats 30 passengers. The airline offers three
fare classes:
(a) Y class: full coach.
(b) B class: nonrefundable.
(c) M class: nonrefundable, 3-week advanced purchase.
Ticket prices have been set and advertised as follows:
Ithaca-Newark Newark-Boston Ithaca-Boston
Y 300 160 360
B 220 130 280
M 100 80 140
Based on past experience, demand forecasters at the airline have determined the
following upper bounds on the number of potential customers in each of the 9 possible
origin-destination/fare-class combinations:
Ithaca-Newark Newark-Boston Ithaca-Boston
Y 4 8 3
B 8 13 10
M 22 20 18
The goal is to decide how many tickets from each of the 9 origin-destination/fare-class
combinations to sell. The constraints are that the plane cannot be overbooked on either
of the two legs of the flight and that the number of tickets made available cannot exceed
the forecasted maximum demand. The objective is to maximize revenue. Formulate this
problem as a linear programming problem in standard form.
3. Consider the following linear programming problem:
min z = x1 − 2x2 − 3x3
subject to
x1 + 2x2 + x3 ≤ 14
x1 + 2x2 + 4x3 ≥ 12
x1 − x2 + x3 = 2
x3 ≥ 3
x1, x2, x3 ≥ 0
Reformulate this program so it is in standard form.
3
4. Consider the following linear programming problem:
max z = 2x1 + 3x2
subject to
x1 + 3x2 ≤ 4
2x1 + 2x2 ≤ 2
3x1 + 3x2 ≤ 2
2x1 + x2 ≤ 3
x1, x2 ≥ 0
Draw the set of feasible solution given the constraints. By drawing the line of the
objective function for a particular value and shifting it parallel, determine
approximately the optimal solution to this problem.
5. Solve the following linear program using the simplex algorithm:
max z = 5x1 + 3x2 + 2x3
subject to
4x1 + 5x2 + 2x3 + x4 ≤ 20
3x1 + 4x2 − x3 + x4 ≤ 30
x1, x2, x3, x4 ≥ 0
6. Solve the following linear program using the simplex algorithm:
max z = 7x1 + 8x2
subject to
4x1 + x2 ≤ 100
x1 + x2 ≤ 80
x1 ≤ 40
x1, x2 ≥ 0
Draw the region of feasible solution to this problem and indicate the solution you get at
each step of the simplex algorithm.
8 points per problems
4
Problems to be discussed in the Office Hours
1. A company is producing three goods: A, B, C. A costs to produce 20$ a piece, and earns
a profit of $ 3 a piece if sold. B costs to produce 50$ a piece, and earns a profit of $ 5 a
piece if sold. C costs to produce 100$ a piece, and earns a profit of $ 1 a piece if sold.
Moreover, for production constraints, there have to be produced at least as double the
amount of goods from good A than from good C. On the other hand, good B cannot be
produced more than the triple number of goods of C. Finally, not more than 100 goods
can be produced overall.
Formulate this problem as a linear programming problem and bring it into standard
form.
2. Consider the following linear programming problem:
max z = 2(x1 − 4x2 + 2x3)
subject to
2x1 + 2x2 − x3 ≥ 12
−x1 + 2x2 − 4x3 ≤ 1
x1 + x3 = 0
x1 ≤ 2
x1, x2, x3 ≥ 0
Reformulate this program so it is in standard form. Can you say if it is feasible? Is it
bounded or unbounded?
3. Consider the following linear programming problem:
max z = 3x1 + x2
subject to
x1 + 2x2 ≤ 2
2x1 + x2 ≤ 3
x1 + x2 ≤ 1
x1, x2 ≥ 0
Draw the set of feasible solution given the constraints. By drawing the line of the
objective function for a particular value and shifting it parallel, determine
approximately the optimal solution to this problem.