noe UU Crate ©) Locating the optimal point Every point in the feasible region satisfies all the const programming problem is, 50 is a potential solution to the linear = To solve a linear programming problem, you need to find the point in the feasible region which ‘maximises or minimises the objective function. ‘There are two methods for finding the optimal solution. The first metho line method or ruler method. ere (>) ETI cecision-aarans JunJie is making ice cream for sale at a charity fair. He makes two flavours of ice cream: vanilla and chocolate. Let the number of litres of vanilla ice cream made be x and the number of litres of chocolate ice cream made be y. JunJie decides to use linear programming to determine the number of litres of each type of ice cream he should make, The constraints and the feasible region, R, are illustrated in the diagram below. ¥ B WZ iB) Bi Al called the objective ol | | Each litre of vanilla ice cream sold will give a profit of 2RMB. Each litre of chocolate ice cream sold will give a profit of IRMB. The profit equation is therefore P= 2x + Each litre of vanilla ice cream made has a production cost of SRMB. Each litre of chocolate ice cream made has a production cost of 2RMB. The production cost equation is therefore C= Sx +aie MWe Determine the optimal solution for this problem, given that the objective is to: a maximise the profit on sales, P = 2x + b minimise the production costs, C= Sx + 2y. D| ee ee Bxey=20 exty=30 Imagine a ruler sliding over the feasible region on page 165 so that it is always parallel to the profit, lines above. The maximum value of P will be in the feasible region at the point furthest from the origin (the last point the ruler touches as it slides out of the feasible region).noe UU R Ty From the diagram, the optimal point is (13, 13), giving an optimal valve for P of 2x19 +13 232, So Jundie should make 13 litres of vanilla ice cream, and 13 litres of chocolate ice cream, and makes a profit of 3RMB. EEEETD You should always make sure you give your answer in the context of the original question. Don't just state the coordinates of the optimal point.ie mur Ualtied ml ’ Draw an objective line with a ruler and label it. The line should be Est accurately plotted and be lang enough for its gradient to be checked. Choose a value of Cand draw the objective line. Fyou choose a muttiple of both and 2 then the objective tne wil pass trough integer wales on the coordinate axis, making t easier to draw Forexample, the line 5x + 29'= 40 8] passes through (0, 20) and @, 0). Then slide the ruler toward the feasible region, keeping it parallel tothe objective line 30 The minimum value will occur at the first point covered by the objective line as it moves into the feasible region. In this case the optimal point is found where the line p= x meets the line 3x + Sy = GO. Solving these equations simultaneously gives x= 75 and y= 75. So at this point C= Sx + 2y=7 x 75 = 525, So Junie should make 75 litres of vanila ice cream and 75 litres of chocolate ice cream, with production costs of 52.5 RMB. = For a maximum point, look for the last point covered by an objective line as it leaves the feasible region. = For a minimum point, look for the first point covered by an objective line as it enters the feasible region. Itis very important, when using the objective line method, that the ruler is ec kept parallel to an objective line. To do this you need two straight edges: Ne either use two rulers, ora ruler and set square. Place the ruler along an objective line, then place the set square (or second ruler) at the base of the ruler. Hold the set square firmly and slide the ruler along the edge of the set square.noe UU Crate EON 6) EXE} ocsor wns Using the feasible region determined by the inequalities xe2 drt3yS12 sx xy find the optimal point and the optimal value when the objective is to: b maximise P =x + 2y Draw an objective line. The diagram shows the feasible region and the objective ine 2x +) = 2, which passes through (1,0) and (0, 2). The final point is point A, where x= 3, y =O. Optimal point is (3, 0) Optimal vabe is P= 2x 3+0=6 The diagram shows the feasible region and the objective line Xx + 2p = 2, which passes through (2, 0) and (0, 1, The final point is point B Bis at the intersection of 2y = x and 4x + 3y = 12, Solving these equations simultaneously gives y Optimal points (22, 14). Optimal vale is P=Smale ml ie GED) ED oe Ina linear programming problem the constraints are given as: Bx ty 90 2Qv+ Ty > 140 x+y = 50 yO ise C= 3x + 2y, is a The objective line has equation 3x + 2y = GO and passes through (20, O) and (0, 30). The first point in the feasible region as the objective line moves away trom the origin is A. Allies at the intersection of Bx+y=90 and xt Solving simultaneously gives x= 20, y= 30 which gives C=3 x 20+2 30noe UU Crate The objective line has equation Bx + 7p = 210 and passes through (70, 0) and (0, 30). The first point in the feasible region is B. Blies at the intersection of 2x+7y= 140 and x+y =50 Solving simultaneously gives x= 42, which gives C=3 x 42 +7 x 6= 182 Fessmne Qi sas Sa Using the same feasible region as in Example 7, find an optimal solution given that the objective is to minimise C =x + y. Een {As the objective line slides into | | the feasible region, it ies along, be the line segment AB, This a means that all points along this part of the line are optimal solutions, Caer A (20, 30) B (42,8) (25, 25) (40,10) C=40+10=50 The optimal solutions are the points on the line x + which 20 < x = 40, 50 forSu alied You may have noticed that the optimal point occurs at one (or more) of the vertices of the feasible region. You can use this fact to find optimal points using the vertex testing method. * To find an optimal point using the vertex method: 1 First find the coordinates of each vertex of the feasible region. 2. Evaluate the objective function at each of these points. 3 Select the vertex that gives the optimal value of the objective function, GEIL?) ED wossame Use the vertex testing method to solve the following linear programming problem: ‘minimise x+y subject to: yee 3x + Sy > 60 yes xe13 wy e0noe UU Crate The feasible region has four vertices, A, B, C and D. Vertex | __ Coordinates Value of s+ 3y A 75 +375 =30 B 1343x1352 © 1345x5725 D igs 5x5 = 265 The minimum valve occurs at D (115, 5) and is 265 amp mp. Team A feasible region is defined by the following constraints: 9x + My <99 dt yp S28 Sx + 3y > 30 x+2y 28 yex Find the optimal point and optimal value given that the objective is to: a maximise x+y" b minimise 3x + 4y Gece) Ifthe points of intersection are not obvious integer values, you should tse simultaneous equations to determine their coordinates. You should always draw a graph to make sure you don't waste time finding points of intersection that lie outside the feasible region.male ne Ey The feasible region has five vertices, A, B, C, Dand E. Use simutaneous equations to find their coordinates, Vertex | Coordinates | Vatie of x+y | Value of 3x4 ay 4 axaBr4axad 2 axstteaxad c 3x6S+4nd= 228 D Bx Sh44ntea oy E 38438 3x 334438 & Maximum value of x + y is at B (534, 42) and has valve of 105 b Minimum value of 3x + 4y Is at D (5: 3) and has value of 214 EID rons soe 1 The diagram shows a feasible region, R. Find the optimal point and the optimal value, using: the objective line method, with the objective ‘maximise M = 2x + »° b the objective line method, with the objective ‘maximise N= x + 4)" © the vertex testing method, with the objective ‘maximise P = x+y" the vertex testing method, with the objective ‘maximise Q = 6x + y’.