PROBLEM 1: Farmer Jones's Planting Problem
Farmer Jones must determine how many acres of corn and how many acres of wheat to plant this year to maximize his revenues. An acre of wheat yields 25 bushels of wheat and requires 10 hours of labor per week. An acre of corn yields 10 bushels of corn and requires 4 hours of labor per week. All wheat can be sold at $4 a bushel, and all corn can be sold at $3 a bushel. Seven acres of land and 40 hours per week of labor are available. Government regulations require that at least 30 bushels of corn be produced during the current year.
a) Mathematically formulate a linear programming model for this problem. Define decision variables, and then define your constraints and objective function accordingly. Combine everything to get the final model.
b) Formulate and solve this problem on a spreadsheet using Excel.
PROBLEM 2 Outsourcing Decisions
Suppose that you are the Manager of the Purchasing Department in a manufacturing company. Currently, you are trying to outsource one of the raw materials (a steel pipe) required for manufacturing your product. Specifically, you know that you need to purchase and ship exactly 5,000 units of steel pipe each week to the manufacturing plant. There are four possible suppliers that you can purchase and ship the steel pipes from. Each supplier has different purchase costs per unit of steel pipe and different shipping costs due to their distances. Furthermore, each supplier has limited weekly supply of steel pipes. The table below summarizes the following data:
- The distance of each supplier to the manufacturing plant (in miles)
- The purchase cost charged by each supplier per steel pipe ($ per unit of steel pipe)
- The weekly supply capacity of each supplier (units of steel pipe)
- The transportation cost charged by the supplier for shipping one unit of steel pipe per mile ($ per steel pipe per mile)
As the purchasing manager, you want to minimize the total cost of weekly steel pipe supply to the manufacturing plant, which includes weekly purchase costs and weekly transportation costs. To do so, you need to determine how many units of steel pipe to ship weekly from each supplier (assume that you can purchase and ship fractional number of steel pipes from the suppliers). While doing so, you need to consider the following:
- Weekly transportation cost should not exceed 80% of the total weekly cost
- Since suppliers 3 and 4 are closer to the manufacturing plant, you want the total steel pipes purchased and shipped weekly from suppliers 3 and 4 to be more than or equal the total steel pipes purchased and supplied weekly from suppliers 1 and 2
- Since you want to build good relations with your suppliers, you want to purchase and ship at least 250 units of steel pipe from each supplier each week
- You want to purchase and ship at least 2 units of steel pipe from supplier 1 for each unit of steel pipe you purchase and ship from supplier 4
In this problem, you are asked to formulate the above outsourcing problem mathematically as a linear model. To do so, define your decision variables, objective and express your objective function and constraints in terms of your decision variables, and combine everything to get the final formulation.
PROBLEM 3: Operator Assignment
Oxford University maintains a powerful mainframe computer research use by its faculty, Ph.D. students, and research associates. During all working hours, an operator must be available to operate and maintain the computer, as well as to perform some programming services. Beryl Ingram, the director of the computer facility, oversees the operation.
It is now the beginning of the fall semester and Beryl is confronted with the problem of assigning different working hours to her operators. Because all the operators are currently enrolled in the university, they are available to work only a limited number of hours each day.
There are six operators (four undergraduate students and two graduate students). They all have different wage rates because of differences in their experience with computers and in their programming ability. The following table shows their wage rates, along with the maximum number of hours that each can work each day.
Each operator is guaranteed a certain minimum number of hours per week that will maintain an adequate knowledge of the operation. This level is set arbitrarily at 8 hours per week for the undergraduate students (KC, DH, HB, and SC) and 7 hours per week for the graduate students (KS and NK).
The computer facility is to be open for operation from 8am to 10pm Monday through Friday with exactly one operator on duty during these hours. Therefore, for each weekday, the total number of operator hours available should be exactly equal to 14 hours. On Saturdays and Sundays, the computer is to be operated by other stuff. It is assumed that operators can work their hours during any period of time in a given day (that is, for instance, Beryl decides to have KC work 6 hours on Monday and HB for 3.2 hours on Monday and SC for 4.8 hours on Monday, scheduling them is not of interest because they can work anytime during 8am-10pm on Monday given that their time is not exceeding their available time on Monday).
Because of a tight budget, Beryl has to minimize the total operating cost. She wishes to determine the number of hours she should assign to each operator on each day.
a) Mathematically formulate a linear programming model for this problem. Define decision variables, and then define your constraints and objective function accordingly. Combine everything to get the final model.
b) Formulate and solve this problem on a spreadsheet using Excel.
PROBLEM 4: Leasing Optimization
Web Mercantile sells many household products through online catalog. The company needs substantial warehouse space for storing its goods. Plans are now being made for leasing warehouse storage space over the next three months. Just how much space will be required in each of these months is known.
However, since these space requirements are quite different, it may be more economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount needed for the entire three months. Another option is the intermediate approach of changing the total amount of space leased (by adding a new lease and/or having an old lease expire) at least once but not every month. For instance, it may be more beneficial to lease some space for a leasing period of three months and some space for a leasing period of one month in month
1, lease some space for a leasing period of two months in month 2, and lease some space for a leasing period of one month in month 4.
The space requirement and the leasing costs for the various leasing periods are as follows:
The objective is to minimize the total leasing cost for meeting the space requirements by determining how much space to lease for how many months for each possible leasing period in each month. For instance, in month 2, you have two possible leasing periods: 1 month or 2 months, because if you lease for 3 months in month 2, you will be leasing some space for the fourth month, which is not needed.
a) Mathematically formulate a linear programming model for the problem.
b) Formulate and solve a spreadsheet model for the problem.
PROBLEM 5
Graphical solution and linear programming (from Midterm 1 of Fall 2012) Suppose that you are given the following linear programming problem.
Please answer the following questions based on the mathematical formulation and the feasible region representation given above.
a) Draw the feasible region of the LP and determine whether it has infeasibility, unique optimum, alternative optima, or unboundedness? Explain your answer.
b) Now suppose that X1≤2 constraint is removed from the above LP. How does the feasible region change? Will your answer to part a) change? Explain your answer.
c) Now, addition to removing X1≤2, suppose that X2≤2 is also removed. How does the feasible region change? Will your answer to part a) change? Explain your answer.