All questions are required. Question 1: 24 Points, Question 3: 20 Points, Questions 2, 4, 5, and 6: 14 Points each 1. (a) What are the two different types of sensitivity ranges? Describe each type briefly and give a real world example for each type. (b) What is a transportation problem? Briefly discuss the decision variables, the objective function and constraint requirements in a transportation problem. Give a real world example of the transportation problem. (c) What is a marketing problem in applications of linear programming? Briefly discuss the decision variables, the objective function and constraint requirements in a marketing problem. Give a real world example of a marketing problem. (d) What is the required format of a linear programming problem needed if we want to solve it by using QM for Windows? What information about the solution can you collect from the results provided by QM for Windows? Discuss briefly. Answer Questions 2 and 3 based on the following LP problem. Maximize 6X1 + 5X2 + 4X3 Total Profit Subject to X1 + X2 + X3 > 220 At least a total of 220 units of all three products needed X1 + 3X2 + 2X3 500 Resource 1 2X1 + X2 + 2X3 350 Resource 2 3X1 + 2X2 + 3X3 600 Resource 3 And X1, X2, X3 0 Where X1, X2, and X3 represent the number of units of Product 1, Product 2, and Product 3 to be manufactured. The QM for Windows output for this problem is given below. Original problem with Answers: X1 X2 Maximize 6 5 Constraint 1 1 1 Constraint 2 1 3 Constraint 3 2 1 Constraint 4 3 2 Solution-> 110 130 X3 4 1 2 2 3 0 RHS Dual >= 220 <= 500 <= 350 <= 600 Optimal Z-> 0 0.8 2.6 0 1310 Linear Programming Results: Variable Status Value X1 Basic 110 X2 Basic 130 X3 NONBasic 0 surplus 1 Basic 20 slack 2 NONBasic 0 slack 3 NONBasic 0 slack 4 Basic 10 Optimal Value (Z) 1310 Ranging Results: Variable Value Reduced Cost Original Val Lower Bound 1 Upper Bound X1 X2 X3 110 130 0 Constraint Constraint 1 Constraint 2 Constraint 3 Constraint 4 0 0 2.8 6 5 4 Dual Value 0 20 .8 0 2.6 0 0 10 2.5 10 3 18 -Infinity 6.8 Slack/Surplus Original Val 220 -Infinity 240 500 400 550 350 300 357.1429 600 590 Infinity Lower Bound Upper Bound 2. (a) Determine the optimal solution and optimal value and interpret their meanings. (b) Determine the slack (or surplus) value for each constraint and interpret its meaning. 3. (a) What are the ranges of optimality for the profit of Product 1, Product 2, and Product 3? (b) Find the dual prices of the four constraints and interpret their meanings. What are the ranges in which each of these dual prices is valid? (c) If the profit contribution of Product 2 changes from $5 per unit to $8 per unit, what will be the optimal solution? What will be the new total profit? (Note: Answer this question by using the ranging results. Do not solve the problem again). (d) Which resource should be obtained in larger quantity to increase the profit most? (Note: Answer this question using the ranging results given above. Do not solve the problem again). 4. A campus dietitian for a college wants to formulate a nutritious meal plan for students. She wants to satisfy the following requirements: - at least 2250 calories - at most 2750 calories - no more than 65 grams of fat - at least 30 grams of protein - no more than 80 grams of carbohydrates. On a particular day, her food stock includes five items that can be prepared and served to meet these requirements. The cost per pound for each food item and the contribution to each of the four nutritional requirements are given in the table below. Food Chicken Fish Lentils Kale Potatoes Calories /pound 380 350 115 110 320 Fat GM/pound 10.2 1.5 1.2 1.1 0.8 Protein GM/pound 70 80 12 12 6 Carbohydrates GM/pound 0 0 35 22 75 Cost Dollars/pound 1.60 3.50 0.75 2.20 0.50 Formulate a linear programming model that meets these restrictions and minimizes the total cost of the meal by determining (a) The decision variables. (Hint: There are 5 decision variables) (b) The objective function. What does it represent? (c) All the constraints. Briefly describe what each constraint represents.(Hint: There are 5 constraints in addition to non-negativity constraints) Note: Do NOT solve the problem after formulating. 5. The Charm City Oil Company wants to decide how to allocate its budget. The government grants certain 2 tax breaks if the company invests funds in research concerned with energy conservation. However, the government stipulates that at least 40 percent of the funds must be funneled into research for automobile efficiency (methanol fuel research and emission reduction). The company has a budget of $2 million for investment. The research proposal data are shown in the following table. Maximum Investment Annual Return Project Allowed on Investment ______________________________________________________________ Methanol fuel research $600,000 2.0% Emission reduction $450,000 2.3% Solar cells $650,000 2.6% Windmills $420,000 2.9% ______________________________________________________________ The company wants to receive the government tax break. How much money should be invested in each project if the company wants to maximize total annual return on its investments? Formulate a linear programming model for the above situation. (a) Define the decision variables. (b) Determine the objective function. What does it represent? (c) Determine all the constraints. Briefly describe what each constraint represents. Note: Do NOT solve the problem after formulating. 6. A software development company wants to assign 4 software engineers to four projects. The estimated time of completion (in days) of each project by each software engineer is given in the following table. Project 1 Project 2 Project 3 Project 4 ___________________________________________________________ Software Engineer A 28 25 20 18 Software Engineer B 40 32 44 Software Engineer C 36 27 19 25 Software Engineer D 30 25 15 22 ___________________________________________________________ Software engineer B cannot be assigned to project 3 because he does not have enough training to do that project. The company wants project 1 to be assigned to software engineer C or software engineer D. The objective is to minimize the total time of completion of all four projects. For this assignment problem: (a) Define the decision variables. (b) Determine the objective function. What does it represent? (c) Determine all the constraints. Briefly describe what each constraint represents. Note: Do NOT solve the problem after formulating. 3 All questions are required. Question 1: 24 Points, Question 3: 20 Points, Questions 2, 4, 5, and 6: 14 Points each 1. (a) What are the two different types of sensitivity ranges? Describe each type briefly and give a real world example for each type. Solution: Two types of sensitivity ranges are Constraint: This gives the range of Right Hand Side of each constraint in order for the solution to be optimal Example: In production planning problem, this gives the range of total availability or constraint of machine hours or labor hours, so that the given solution remains optimal. In short it tells the range beyond which the given production plan is no longer optimal Objective function coefficient: This gives the range of the coefficient of each variable of objective function for the solution to be optimal. Example: In investment problem, it gives the range of rate of return for any investment, in which the current solution is optimal. (b) What is a transportation problem? Briefly discuss the decision variables, the objective function and constraint requirements in a transportation problem. Give a real world example of the transportation problem. Solution: A transportation problem is aimed at identifying the optimal quantity to be shipped between two stations, so the total cost is minimized or profit is maximized. There are more than one number of distributors and more than one number of receivers. The decision variables are quantity shipped between each pair of stations The objective function is to maximize the profit or minimize the cost. The constraints are, in terms of total availability at each distributor and total demand at each receiver. Example: Shipment of goods from 2 warehouses to 4 retailers. (c) What is a marketing problem in applications of linear programming? Briefly discuss the decision variables, the objective function and constraint requirements in a marketing problem. Give a real world example of a marketing problem. Solution: A marketing problem is a problem which aims at maximizing the customer exposure or sales, given the advertisement budget and other constraint in terms of media vehicles and customer reach. The decision variables in this case would be the quantity of each type or media vehicle or number of customer surveyed from each category. The objective function would be to maximize number of sales or customer exposure. The constraint would be budget constraint, constraint on type of vehicle, minimum number of each customer group to be surveyed, etc. Example: An example of a marketing problem is to do a customer survey to get insights into the new product. The aim is to maximize the customer exposure and the constraints are budget, minimum number surveyed from each group, etc. (d) What is the required format of a linear programming problem needed if we want to solve it by using QM for Windows? What information about the solution can you collect from the results provided by QM for Windows? Discuss briefly. Solution: The required format of a linear program to be solved by QM for windows is 1 First the objective function coefficient needs to be entered. Then the coefficients in the constraint equations are entered along with the Right hand side and constraint inequality sign. Then these are entered in the solver window QM for windows gives the optimal values of all the variables, optimal value of the objective function and the sensitivity ranges Answer Questions 2 and 3 based on the following LP problem. Maximize 6X1 + 5X2 + 4X3 Total Profit Subject to X1 + X2 + X3 > 220 At least a total of 220 units of all three products needed X1 + 3X2 + 2X3 500 Resource 1 2X1 + X2 + 2X3 350 Resource 2 3X1 + 2X2 + 3X3 600 Resource 3 And X1, X2, X3 0 Where X1, X2, and X3 represent the number of units of Product 1, Product 2, and Product 3 to be manufactured. The QM for Windows output for this problem is given below. Original problem with Answers: X1 X2 Maximize 6 5 Constraint 1 1 1 Constraint 2 1 3 Constraint 3 2 1 Constraint 4 3 2 Solution-> 110 130 X3 4 1 2 2 3 0 RHS Dual >= 220 <= 500 <= 350 <= 600 Optimal Z-> 0 0.8 2.6 0 1310 Linear Programming Results: Variable Status Value X1 Basic 110 X2 Basic 130 X3 NONBasic 0 surplus 1 Basic 20 slack 2 NONBasic 0 slack 3 NONBasic 0 slack 4 Basic 10 Optimal Value (Z) 1310 Ranging Results: Variable Value X1 110 0 X2 130 0 X3 0 2.8 Constraint Constraint 1 Constraint 2 Reduced Cost Original Val 6 2.5 10 5 3 18 4 -Infinity 6.8 Dual Value 0 20 .8 0 Lower Bound Slack/Surplus Original Val 220 -Infinity 240 500 400 550 2 Upper Bound Lower Bound Upper Bound Constraint 3 Constraint 4 2.6 0 0 10 350 600 300 590 357.1429 Infinity 2. (a) Determine the optimal solution and optimal value and interpret their meanings. Solution: The optimal solution is X1 110 X2 130 X3 0 Optimal Value (Z) 1310 This means that given the constraints we can get a maximum profit of 1310, by producing 110 units of Product 1, 130 units of Product 2 (b) Determine the slack (or surplus) value for each constraint and interpret its meaning. Solution: The slack for production budget constraint is 0. This means that product budget is a binding constraint. surplus 1 slack 2 slack 3 slack 4 Basic 20 NONBasic NONBasic Basic 10 0 0 The slack for labor hours constraint is 20, which means that this is a non-binding constraint and we have an excess of 20 units available with us The slack for product 2 constraint and product 3 constraints are 0, which means that they are binding constraints. 3. (a) What are the ranges of optimality for the profit of Product 1, Product 2, and Product 3? Solution X1 X2 X3 10 18 Infinity to 6.8 (b) Find the dual prices of the four constraints and interpret their meanings. What are the ranges in which each of these dual prices is valid? Solution: The dual price of budget constraint is 0 and its range is Infinity to 240 The dual price of labor hour constraint is 0.8 and its range is upto 550 The dual price of product 1 constraint is 2.6 and its range is upto 357.1429 The dual price of product 2 constraint is 0 and its range is 590 to Infinity 3 (c) If the profit contribution of Product 2 changes from $5 per unit to $8 per unit, what will be the optimal solution? What will be the new total profit? (Note: Answer this question by using the ranging results. Do not solve the problem again). Solution: X1 X2 X3 110 130 0 0 0 2.8 6 5 4 2.5 10 3 18 -Infinity 6.8 The total profit would be 110 * 6 + 130 * 5 + 0 = 660 + 650 = 1310 (d) Which resource should be obtained in larger quantity to increase the profit most? (Note: Answer this question using the ranging results given above. Do not solve the problem again). Solution: In order to increase the profit most, budget should be more as the dual price of budget is maximum 4. A campus dietitian for a college wants to formulate a nutritious meal plan for students. She wants to satisfy the following requirements: - at least 2250 calories - at most 2750 calories - no more than 65 grams of fat - at least 30 grams of protein - no more than 80 grams of carbohydrates. On a particular day, her food stock includes five items that can be prepared and served to meet these requirements. The cost per pound for each food item and the contribution to each of the four nutritional requirements are given in the table below. Food Chicken Fish Lentils Kale Potatoes Calories /pound 380 350 115 110 320 Fat GM/pound 10.2 1.5 1.2 1.1 0.8 Protein GM/pound 70 80 12 12 6 Carbohydrates GM/pound 0 0 35 22 75 Cost Dollars/pound 1.60 3.50 0.75 2.20 0.50 Formulate a linear programming model that meets these restrictions and minimizes the total cost of the meal by determining (a) The decision variables. (Hint: There are 5 decision variables) (b) The objective function. What does it represent? (c) All the constraints. Briefly describe what each constraint represents.(Hint: There are 5 constraints in addition to non-negativity constraints) Note: Do NOT solve the problem after formulating. 5. The Charm City Oil Company wants to decide how to allocate its budget. The government grants certain tax breaks if the company invests funds in research concerned with energy conservation. However, the government stipulates that at least 40 percent of the funds must be funneled into research for automobile 4 efficiency (methanol fuel research and emission reduction). The company has a budget of $2 million for investment. The research proposal data are shown in the following table. Maximum Investment Annual Return Project Allowed on Investment ______________________________________________________________ Methanol fuel research $600,000 2.0% Emission reduction $450,000 2.3% Solar cells $650,000 2.6% Windmills $420,000 2.9% ______________________________________________________________ The company wants to receive the government tax break. How much money should be invested in each project if the company wants to maximize total annual return on its investments? Formulate a linear programming model for the above situation. (a) Define the decision variables. (b) Determine the objective function. What does it represent? (c) Determine all the constraints. Briefly describe what each constraint represents. Note: Do NOT solve the problem after formulating. 6. A software development company wants to assign 4 software engineers to four projects. The estimated time of completion (in days) of each project by each software engineer is given in the following table. Project 1 Project 2 Project 3 Project 4 ___________________________________________________________ Software Engineer A 28 25 20 18 Software Engineer B 40 32 44 Software Engineer C 36 27 19 25 Software Engineer D 30 25 15 22 ___________________________________________________________ Software engineer B cannot be assigned to project 3 because he does not have enough training to do that project. The company wants project 1 to be assigned to software engineer C or software engineer D. The objective is to minimize the total time of completion of all four projects. For this assignment problem: (a) Define the decision variables. (b) Determine the objective function. What does it represent? (c) Determine all the constraints. Briefly describe what each constraint represents. Note: Do NOT solve the problem after formulating. 5