MA3231-Homework 1 Solved

Content: up to Section 1

1.    A steel company must decide how to allocate next week’s time on a rolling mill. The rolling mill 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. Find the optimal solution to this problem. (hint: you should be able to find the optimal solution using just “common sense”, but you can also use the graphical method if you

prefer)

2.    A small airline flies between three cities: Ithaca, Newark, and Boston. They offer several 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:

1.    Those traveling from Ithaca to Newark.

2.    Those traveling from Newark to Boston.

3.    Those traveling from Ithaca to Boston.

The aircraft is a small commuter plane that seats 30 passengers. The airline offers three fare classes:

1.    Y class: full coach.

2.    B class: nonrefundable.

3.    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:

minz = 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.

4.    Consider the following linear programming problem:

maxz = 2x1 + 3x2

subject to

x1 + 3x2 ≤ 4 2x1 + 2x2 ≤ 2

3x1 + 3x2 ≤ 2 2x1 + x2 ≤ 3

x1,x2 ≥ 0

Draw the set of feasible solutions given the constraints. By drawing the level set line of the objective function for a particular value and then shifting it, determine approximately the optimal solution to this problem.