On the other hand, the point (x1 15, x2 70) is not in the feasible region, because even though x1 15 and x2 70 satisfy (2), (4), (5), and (6), they fail to satisfy (3): 15 70 is not less than or equal to 80. Any point that is not in an LP's feasible region is said to be an infeasible point. As another example of an infeasible point, consider (x1 40, x2 20). Although this point satises all the constraints and the sign restriction (5), it is infeasible because it fails to satisfy the sign restriction (6), x2 0. The feasible region for the Giapetto problem is the set of possible production plans that Giapetto must consider in searching for the optimal production plan. DEFINITION s For a maximization problem, an optimal solution to an LP is a point in the feasible region with the largest objective function value. Similarly, for a minimization problem, an optimal solution is a point in the feasible region with the smallest objective function value. s Most LPs have only one optimal solution. However, some LPs have no optimal solution, and some LPs have an innite number of solutions (these situations are discussed in Section 3.3). In Section 3.2, we show that the unique optimal solution to the Giapetto problem is (x1 20, x2 60). This solution yields an objective function value of z 3x1 2x2 3(20) 2(60) $180 When we say that (x1 20, x2 60) is the optimal solution to the Giapetto problem, we are saying that no point in the feasible region has an objective function value that exceeds 180. Giapetto can maximize prot by building 20 soldiers and 60 trains each week. If Giapetto were to produce 20 soldiers and 60 trains each week, the weekly prot would be $180 less weekly xed costs. For example, if Giapetto's only xed cost were rent of $100 per week, then weekly prot would be 180 100 $80 per week. PROBLEMS Group A 1 Farmer Jones must determine how many acres of corn and wheat to plant this year. 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. Let x1 number of acres of corn planted, and x2 number of acres of wheat planted. Using these decision variables, formulate an LP whose solution will tell Farmer Jones how to maximize the total revenue from wheat and corn. 2 3 Answer these questions about Problem 1. a Is (x1 2, x2 3) in the feasible region? b Is (x1 4, x2 3) in the feasible region? c Is (x1 2, x2 1) in the feasible region? d Is (x1 3, x2 2) in the feasible region? produced and x2 number of bushels of wheat produced, reformulate Farmer Jones's LP. 4 Truckco manufactures two types of trucks: 1 and 2. Each truck must go through the painting shop and assembly shop. If the painting shop were completely devoted to painting Type 1 trucks, then 800 per day could be painted; if the painting shop were completely devoted to painting Type 2 trucks, then 700 per day could be painted. If the assembly shop were completely devoted to assembling truck 1 engines, then 1,500 per day could be assembled; if the assembly shop were completely devoted to assembling truck 2 engines, then 1,200 per day could be assembled. Each Type 1 truck contributes $300 to prot; each Type 2 truck contributes $500. Formulate an LP that will maximize Truckco's prot. Group B 5 Why don't we allow an LP to have or constraints? Using the variables x1 number of bushels of corn 3 . 1 What Is a Linear Programming Problem? 55 PROBLEMS Group A 1 Graphically solve Problem 1 of Section 3.1. 2 Graphically solve Problem 4 of Section 3.1. 3 Leary Chemical manufactures three chemicals: A, B, and C. These chemicals are produced via two production processes: 1 and 2. Running process 1 for an hour costs $4 and yields 3 units of A, 1 of B, and 1 of C. Running process 2 for an hour costs $1 and produces 1 unit of A and 1 of B. To meet customer demands, at least 10 units of A, 5 of B, and 3 of C must be produced daily. Graphically determine a daily production plan that minimizes the cost of meeting Leary Chemical's daily demands. 4 For each of the following, determine the direction in which the objective function increases: a z 4x1 x2 b z x1 2x2 c z x1 3x2 5 Furnco manufactures desks and chairs. Each desk uses 4 units of wood, and each chair uses 3. A desk contributes 3.3 $40 to prot, and a chair contributes $25. Marketing restrictions require that the number of chairs produced be at least twice the number of desks produced. If 20 units of wood are available, formulate an LP to maximize Furnco's prot. Then graphically solve the LP. 6 Farmer Jane owns 45 acres of land. She is going to plant each with wheat or corn. Each acre planted with wheat yields $200 prot; each with corn yields $300 prot. The labor and fertilizer used for each acre are given in Table 1. One hundred workers and 120 tons of fertilizer are available. Use linear programming to determine how Jane can maximize prots from her land. TA B L E 1 Wheat Labor Fertilizer Corn 3 workers 2 tons 2 workers 4 tons Special Cases The Giapetto and Dorian problems each had a unique optimal solution. In this section, we encounter three types of LPs that do not have unique optimal solutions. 1 Some LPs have an innite number of optimal solutions (alternative or multiple optimal solutions). 2 Some LPs have no feasible solutions (infeasible LPs). Some LPs are unbounded: There are points in the feasible region with arbitrarily large (in a max problem) z-values. 3 Alternative or Multiple Optimal Solutions EXAMPLE 3 Alternative Optimal Solutions An auto company manufactures cars and trucks. Each vehicle must be processed in the paint shop and body assembly shop. If the paint shop were only painting trucks, then 40 per day could be painted. If the paint shop were only painting cars, then 60 per day could be painted. If the body shop were only producing cars, then it could process 50 per day. If the body shop were only producing trucks, then it could process 50 per day. Each truck contributes $300 to prot, and each car contributes $200 to prot. Use linear programming to determine a daily production schedule that will maximize the company's prots. Solution The company must decide how many cars and trucks should be produced daily. This leads us to dene the following decision variables: x1 number of trucks produced daily x2 number of cars produced daily 3 . 3 Special Cases 63