Assignment Questions: Integer Programming, Linear Programming, and Optimization

Question 1: Airline Plane Purchases

1. (15 marks) An airline wishes to determine how many small (70 seat) and large (120 seat) planes to buy. Each 70-seat plane costs 50 million dollars and each 120-seat plane costs 80 million dollars. They want the total seat capacity of all planes to be at least 300. A fuel-efficiency (FE) rating measures the consumption of jet fuel in litres per kilometre of flight. The small planes have an FE rating of 5.4 litres/km; the larger planes have an FE rating of 7.8 litres/km. They want the weighted average plane FE rating to be no more than 6 litres/km, where the weighting is based on the number of planes of each size.

(a) Defining variables X1 and X2, formulate this integer model.

(b) On a 6 by 4 graph, plot the constraints, show the feasible region for the constraints, show all the feasible dots for integer solutions, and the trial and optimal isovalue lines. By inspection, state the optimal values for X1, X2, and compute the OFV.

If you wish, print this page to use the graphpaper below.

2. (20 marks) The personnel manager of a small plant has six workers to be assigned to one of two machines (types X and Y). The plant works on four distinct shifts, hence up to four workers can be assigned to either machine. From a series of tests, the ability of the workers to operate these two machines has been determined to be the following (a high score indicates high ability):

The personnel manager wishes to select the workers so as to maximize the overall ability of the workers on the machines, subject to the restriction that at least one female worker be assigned to each machine. Also, the personnel the manager would only consider assigning worker 2 to machine X if worker 5 has been assigned to machine X.

(a) Write the algebraic model for this problem.

(b) Solve the model using LINGO or the Excel Solver.

(c) State the solution in words.

3. (20 marks) A company buys fresh fish for processing. They have an annual contract with their supplier to buy up to 10,000 Tonnes at the following set of incremental prices:

First 4000 Tonnes (or any fraction) may be purchased @ $2.80/kg.

Next 6000 Tonnes (or any fraction) may be purchased @ $3.80/kg.

Their fish processing plant can operate on a one or two shift per day basis. (Shift two operates only if shift one operates.) For each shift there is a fixed cost which exists if the shift operates, but is nil otherwise, and a variable cost per kilogram of fish processed. The costs and shift capacities are:

Question 2: Personnel Assignments

If a shift operates at all, then the minimum amount processed is 2500 Tonnes per annum on that shift (i.e. the amount processed on any shift is either 0 or greater than or equal to 2500 Tonnes).

The company sells processed fish for $5.00 per kg. They wish to know what theyshould do to maximize their annual profit.

(a) Write the algebraic model for this problem.

(b) Solve the model using lingo or the Excel Solver.

(c) State the solution in words.

4. (25 marks) There are eight communities located along the Trans-Canada Highway, with community 1 being the most westerly, and community 8 being the most easterly. Currently, none of the eight communities has a fast-food restaurant. A fast-food restaurant chain is considering opening up to four restaurants in the eight communities (no more than one restaurant per community).

They believe that they will capture 30% of the market in those communities in which a restaurant is constructed. Furthermore, they believe that they will capture 15% of the market in any community which does not have its own restaurant but which is contiguous to a community (on either or both sides) which does have a restaurant. Each restaurant would have an annual overhead cost of $200,000. Each customer would give an annual contribution to profit of $50. The population of each community is:

R = number of restaurants built.
N1 = population (in thousands) of communities with a restaurant.
N2 = population (in thousands) of communities without a restaurant of their own but which are contiguous to a community which does have a restaurant.

(a) Using the variables as defined above, write the objective function and the constraints for this problem.

(b) Solve the model using lingo or the Excel Solver.

(c) State the solution in words.

5. (20 marks) A furniture store at location 0 has deliveries to make to customers at locations 1, 2, 3, and 4. The time in minutes that it would take a truck to travel from one location to another is given in the following table. Because of one-way streets and places where no left-turns are allowed, or are difficult to make, the table is not symmetric.

The objective is to minimize the total travel time.

(a) Give the algebraic model of this situation, omitting the sub-tour constraints.

(b) Use LINGO or the Excel Solver to solve this (partial) model. Show that this solution is not a tour, and state the two sub-tours.

(c) Give a constraint that would, if added to the formulation of (b), prevent this specific situation from arising. Re-solve the computer model, and state whether or not this new solution is a tour