PROBLEM 1:
The board of directors of General Wheels Co. is considering seven large capital investments. Each investment can be made only once. The investments differ in the estimated long-run profit (net present value) that they will generate as well as in the amount of capital required, as shown by the following table:
The total amount of capital available for these investments is $100 million. Investment opportunities 1 and 2 are mutually exclusive, and so are 3 and 4.
Mutually exclusive alternatives: A group of alternatives where choosing any one alternative excludes choosing any of the others. For instance, when investment opportunities 1 and 2 are mutually exclusive, it means that if you select 1, you cannot select 2 or if you select 2, you cannot select 1.
Furthermore, neither 3 nor 4 can be undertaken unless one of the first two opportunities is under taken.
There are no such restrictions on investment opportunities 5, 6, and 7. The objective is to select the combination of capital investments that will maximize the total estimated long-run profit (net present value).
a) Formulate the above problem mathematically (in an algebraic form).
b) Formulate and solve the above problem on a spreadsheet using Excel.
c) Now, suppose that the following restrictions are given in addition to the above problem. Formulate each restriction as a constraint mathematically.
i. You cannot spend more than $60 million on first 3 of the opportunities.
ii. You can select at most 5 investment opportunities to invest.
iii. If you have selected both opportunities 5 and 6 to invest, you have to select either opportunity 1 or 2 to invest.
iv. You have to select at least two of the following opportunities: 1, 3, 5, 7.
PROBLEM 2:
An electrical utility needs to generate 6,500 megawatts of electricity today. It has five generators. If any electricity is generated by a given generator, that generated must be started up and a fixed start-up cost is incurred. There is an additional cost for each megawatt generated by a generator. These costs, as well as the maximum capacity of each generator, are shown in the following table. The objective is to determine the minimum cost plan that meets the electrical needs for today.
a) Formulate the above problem mathematically.
b) Formulate and solve the above problem on a spreadsheet using Excel.
PROBLEM 3:
Speedy Delivery provides two-day delivery service of large parcels across the United States. Each morning at each collection center, the parcels that have arrived overnight are loaded onto several trucks for delivery throughout the area. Since the competitive battlefield in this business is speed of delivery, the parcels are divided among the trucks according to their geographical destinations to minimize the average time needed to make the deliveries.
On this particular morning, the dispatcher for the Blue River Valley Collection Center, Sharon Lofton, is hard at work. Her three drivers will be arriving in less than an hour to make the day's deliveries. There are nine parcels to be delivered, all at locations many miles apart. As usual, Sharon has loaded these locations into her computer. She is using her company's special software package, a decision support system called Dispatcher. The first thing Dispatcher does is use these locations to generate a considerable number of attractive possible routes for the individual delivery trucks. These routes are shown in the table below (where the numbers in each column indicate the order of deliveries), along with the estimated time required to traverse the route.
Dispatcher is an interactive system that shows these routes to Sharon for her approval or modification. (For example, the computer may not know that flooding has made a particular route infeasible.) After Sharon approves these routes as attractive possibilities with reasonable time estimates, Dispatcher next formulates and solves a BIP (binary integer programming) model for selecting three routes that minimize their total time while including each delivery location on exactly one route.
a) Formulate the above problem mathematically (i.e, in algebraic form).
b) Formulate and solve the above problem on a spreadsheet using Excel.
PROBLEM 4:
Suppose that your company has finished designing a new product. The company now wants to establish a distribution network for the markets it can sell the product. The product will be sold for $15 per unit in any market. There are 3 potential markets that the company can choose to enter. If the company chooses to enter the market, the demand in that market should be satisfied. That is, the number of products shipped to the market should be exactly equal to the demand of the market. Therefore, the potential revenues that can be gained by entering a market is equal to the demand of the market multiplied by the per unit selling price of the product. The table below specifies the demand for each market.
To manufacture the product, so that the demand in the chosen markets can be satisfied, the company needs to decide on the locations of the manufacturing facilities. There are two possible locations for locating manufacturing facilities. The table below gives the cost of locating a manufacturing facility and the capacity of the located manufacturing facility for each possible location.
The company needs to ship the product to the chosen markets from the located manufacturing facilities. Any market can be supplied by any manufacturing facility. For instance, if the company chooses to enter market 1 and locates manufacturing facilities in locations 1 and 2, the demand for market 1 can be shipped partially from manufacturing facility in location 1 and manufacturing facility location 2. The per unit shipping cost from each facility location to each market is given in the table below.
As the planning manager of the company, you are required to determine which markets to enter, where to locate manufacturing plants, and how much to ship from each located manufacturing plant to each chosen market to maximize the total profit the company makes. The total profit is equal to the revenues gained from selling the product in the chosen markets minus the manufacturing facility location and shipping costs. (The quantities shipped can be continuous, i.e., they do not have to be integer.)
Mathematically formulate a mixed integer linear programming model for the problem stated above. (i) Define your decision variables, (ii) formulate the objective and the objective function in terms of your decision variables, (iii) formulate the constraints and explain why they are needed, and (iv) combine everything to have the final mathematical formulation.
PROBLEM 5:
Dr. Konur has recently started working out and he is working out with a trainer in the Centre (a gym in Rolla, MO). The trainer, Matt the Mean, always come up with a work-out plan for the training sessions and he enjoys making Dr. Konur suffer, moreover, he laughs right at Dr. Konur's face while doing that. For this last session, he is considering activities from different categories. Each activity under each category has a different calorie burning rate for one minute spent doing that activity. Specifically, there are three categories of activities: UPs, Cardio, and Pain-givers. Each category has three activities. The data for each activity under different categories are summarized in the table below.
Dr. Konur and Matt the Mean has a work-out session of 60 plus or minus 5 minutes, that is, the work-out sessions should be between 55 and 65 minutes. Matt the Mean wants to tire Dr. Konur as much as he can during a session, so he wants to prepare a work-out plan to maximize the calories burnt. In preparing a work-out plan, Matt the Mean should determine which categories to include in the plan, and how much time to allocate to each activity under the included categories. Each category has a 3-minute get-ready time, where Matt the Mean, shows how the activities will be executed and Dr. Konur psychologically prepares himself for the upcoming pain. If get-ready-time is not done, activities under that category cannot be done. Matt the Mean has some restrictions above the work-out plan:
- He cannot allocate more than 40 minutes under the same category. That is, the sum of the times allocated to the activities under the same category plus the get-ready time for that catefory cannot be more than 40 minutes.
- He cannot allocate more than 15 minutes to any activity under any category.
- If a category is included in the plan, he should allocate at least 20 minutes, in total, to the activities under that category.
- He has to include at least two categories in the plan. Mathematically formulate Matt the Mean's work-out plan preparation problem as a mixed-integer-linear programming 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 6:
Lipdon is a company that produces tea bags. Specifically, the company has 5 popular flavors that can be produced at the company's manufacturing plant. The company produces boxes of each flavor and each box contains 25 tea bags. The table below gives the estimated annual demand in boxes and the selling price of a box for each flavor.
Since Lipdon's manufacturing plant has limited capacity, the company changes the flavors sold each year. As a company policy, if Lipdon decides to produce a flavor for a year, the number of boxes produced of that flavor should be at most the estimated annual demand and at least 90% of the estimated annual demand for boxes of that flavor.
As the production manager at Lipdon, you need to decide on the production plan for the coming year by determining which flavors to produce and how many boxes to produce for each flavor. As noted previously, the company's manufacturing plant has limited capacity. Specifically, 100,000 boxes in total can be produced (production of a box of any flavor uses the same amount of capacity). To be able to produce a flavor, a one-time setup needs to be executed in the manufacturing plant. The table below
shows the setup cost associated with each flavor's production as well as the production cost per box for each flavor.
If the setup for a flavor is not executed, boxes of that flavor cannot be produced. As the production manager, you want to find the production plan that will maximize the estimated profits for the coming year. It is assumed that you will sell all of the tea boxes produced and the estimated profit is equal to the revenues gained from sales minus the production costs and the setup costs.
In this problem, you are asked to mathematically formulate a mixed-integer (binary) optimization model for the production planning of tea boxes for Lipdon.
a) Mathematically formulate a mixed integer programming model for the above problem by defining your decision variables, and writing your objective functions and constraints (assume you can produce fractional number of tea boxes).
b) Formulate the following constraints mathematically independent of each other. All of the constraints should be linear.
i. If you produce Breakfast Teas, you cannot produce Irish Teas.
ii. If you produce Irish Teas, you have to produce Herbal Teas.
iii. If you produce Green Teas, you have to produce at least 2 other flavors.
iv. If you produce both Breakfast and Earl Grey Teas, you cannot produce Irish Teas.
v. If 4 or more flavors are produced, Herbal Teas should be one of the flavors produced.