/e can also make use of other test points other than the origin but it is more convenient | touseit In cases that the origin ls part ofthe line itself, use other points inthe Cartesian | a! Example 4: Find the solution set of the given inequalities in a graphical method x + 2y 2 4 and 2+yS6. Solution: ‘Step 1: Change the “greater-than-or-equal-to” of the first inequality to equality x + 2y = 4 and the “less-than-or-equal-to” of the first inequality to equality 2x +y= 6. ‘Step2: Solve using intercepts let x and y be equal to zero onx + 2y=4 and 2x+y=6, i when x=0 wheny=0 O+ay=4 + 2( aa4 xt Y=2(0,2) (4,0) when x=0 when y=0 2(0)+ 2x+0=6 2x=6 (0.6) x=3 (3,0) ep 3: Plot the points of the coordinates in a Cartesian coordinate system. Figure 6.5 "Thus, the solution is the common area covered by both x + 2y2 4 and 2x+y <6. | .#° Supplementary Exercise 6.2 _ 1, Sketch the graph of the following inequalities. axt+3ys9 b.4x-y28 ext 3y>12 2. Sketch the graph of the following inequalities by x and y-intercept. a, 3x + Sy 15 and Sx ~3y< 15 b. x+yS6and 2x-y26 Unit 6.3; Geometry of Linear Programming Linear Programming is a method of dealing with decision problems that can be expressed as constrained linear models. The primary objectives of all linear programming models are certainty of ___the parameters and linearity of the objective function and all constraints. Linear Programming is a (Chapter 6: Linear Programming Page 161mathematical technique for finding the best uses of an organization's resources. Linear programmi is initially referred to as “programming ina linear structure.” In 1948 Tjalling Koopmans suggesteq to George Dantzig to shorten it to “Iinear programming.” Linear programming was developed by George Dantzig (1914-2005) in the 1940s. He was ay American mathematical scientist, Linear Programming is a result of an Air Force research projeq, concerned with computing the most efficient and economical way to distribute men, weapons, ang supplies from different fronts during World War Il. The word “programming” means producing , plan or procedure that determines the solution to a problem. The graphical Solution Method is . two-dimensional geometric analysis of Linear Programming problems with two decision vartables, The Theory of Linear Programming states that the optimal solution will lie at a corner point of the feasible region, In large Linear Programming problems, the feasible region cannot be easily grapheq because it has many dimensions (hyperspace), but the concept is the same. Restriction on the Linear Programming Graphical Method Linear programming (LP) graphical solution Is limited to a two-dimensional set of axes meaning if there are more than two variables, we cannot graph the constraints on a two-dimensional set of axes, But with an appropriate tool or graphing software application, the method can be used in three variables corresponding to planes in a coordinate space (three-dimensional) and can be graphed. Itis difficult, but not impossible, to graph the feasible region and determine its vertices of an LP problem with a multiple number of variables. To determine whether a solution on an LP exists it must be simply connected, which means that there are no holes inside the region, Secondly, it must also be convex, which means that there are no dips in the boundary of the region. Solving Linear Programming Problem Graphically Alinear programming problem in two unknowns x and y is one in which we are to determine the ‘maximum and minimum value ofa linear expression. P=axx+ by (for maximization) C= axx + byy (for minimization) called the objective function, subject to several linear constraints of the form ax+ byse or axx+ byy2c or axx+ b= ‘An objective function is an expression that shows the relationship between the variables in the problem and the firms goal. There are two types of constraints: structural and non-negativity. The ‘structural constraint is a limit on the availability of resources; itis also referred to as an explicit constraint. A non-negativity constraint is a constraint that restricts all the variables to zero and positive solutions; itis also referred to as an implicit constraint. Let's take the linear programming model below. Maximize: P= 1,200x+1,600y Objective Function Subject to 3x4 2ys18 2x+4ys20 Structural Constraints xsS x20,y20 Non-negativity Constraints Page 162 Chapter 6: Linear ProgramingThe highest (for maximization problem) or lowest ; value (for minimization problem) of the objective ree function referred to as an optimal value, The optimal | | | T 4H Extreme Point solution is a combination of decision variable amounts that yield the best possible value of the objective function and satisfy all the constraints. There may be multiple combinations of decision variables that yield the same best value of the objective finetion. The feasible region is the set of combinations of values for the decision variables that satisfy the non- negativity conditions and all the _consteaints simultaneously which ts the allowable declsion, ‘The extreme point is the corner of the feasible region; It Is, the location of the maximum and minimum polnts of the feasible region. See Figure 6.6. ‘The Extreme Point Theorem ‘The linear objective function will have its optimal solutions at the extreme points (corner points) of the feasible region whenever the feasible region 1s bounded. If the feasible region is unbounded, there is no optimal solution. In cases, wherein there is an optimal solution even though the feasible region is unbounded, it lies at the extreme (or corner) of the feasible region. Fundamental Theorem of Linear Programming Problem ‘There are two things we need to consider in solving linear programming problem such as. © Ifa Linear Programming (LP) problem has an optimal solution, there is always at least one extreme point (corner point) solution of the feasible region. + A Linear programming (LP) problem with bounded, non-empty feasible regions always contains optimal solutions. lear Programming Graphical Method ! 1. Graph the linear inequalities and determine the feasible region. i 2. Determine the coordinates of the extreme points (corner points). i 3. Substitute the coordinates of the extreme points to the objective function and identify the i highest (for maximization problem) or lowest (for minimization problem) result. | 4, The highest or lowest result obtained in step 3 serves as the optimal solution to the LP Example 1: A local boutique produced two designs of gowns A and B and has the following materials available: 18 square meters of cotton, 20 square meters of silk, and 5 square meters of wool. Design A requires the following: 3 square meters of cotton, 2 square meters of silk, and 1 square meter of wool. Design B requires the following: 2 square meters of cotton, and 4 square meters of silk. If Design A sells for P1,200 and Design B for P1,600, how many of each garment should the boutique produce to obtain the maximum amount of money? Solutios To solve linear programming using the graphical method, It ls necessary to follow the following steps. ‘Step 1: Represent the unknown in the problem, Let x be the number of Design A gowns, and _y be the number of Design B gowns. Step 2: Tabulate the data about the facts (if necessary), ‘Chapter 6: Linear Programming Page 163Materials [Design Ae) | Design Bo) _[__ Available 3 Cotton 2 18 silk 2 4 20 Wool 1 o 5 Profit 1,200 1,600 Step3: Formulate the objective function and constraints by restating the information jy mathematical form (LP model). The objective function is Maximize: ‘The constraints are: : 3x+2ys18= Cotton 2x+4ys20= Silk — | Structural Constraints xs5 => Wool x20,y20 Non-negativity Constraints ,200x + 1,600 Noe: P will denote that the LP model is a maximization problem and C for the minimization | ‘Step 4: Plot the constraints ofthe LP problem on a graph, with Design A(x) shown on the horizontal axis and Design B ()) shown on the vertical axis, using the intercept rule. 3x4 218 2x+4ys20 xs5 3x+2y=18 2x+ dy =20 x25 Letx= Letx=0 3(0) +2y=18 2(0) + 4y=20 0+2y=18 0+4y=20 ay=18 4y=20 ¥=9(0,9) ¥=5(0,5) lety=0 Lety=0 3x+2(0)= 18 2x+ 4(0) =20 3x+0=18 2x+0=20 3x=18 2x=20 x=6 (6,0) x=10(10,0) Figure 6.7 shows the initial graph of the LP model. After which we need to identify the area that satisfies all the constraints, it is known as the feasible region. Consider our example, there are two unknown coordinates that lie in the extreme point of the feasible region. Step 5: After identifying the feasible | yea region of the linear programming problem, we need to trace the extreme points ofthe graph as shown in Figure 67 and solve for the unknown coordinates. In this example, there are two unknown coordinates of the extreme points. Bee 2y=18 Figure 6.7 Page 164 ‘Chapt 6 Linear ProgramtySolve the intersection of the lines, which satisfies the feasible solution simultaneously, using the elimination method. Figure 6.8 shows the intersection of the first and second equations and the intersection of the first and the third equations. step 6: Specifically, we used the elimination method to determine the intersection of two lines. It is illustrated below the procedure for identifying the intersection of the first and second equations. Figure 68 Betas e+ 4ys20 Feasible Regton First equation: 3x + 2) ‘Second equation: 2x + 4y= 20 To eliminate the variable x we will apply the Least Common Multiple (LCM) on both x’s of the two equations. 2Gx+2y=18) > Gx + 4y=36 3(2x+4y=20) => ()6x+12v=60 Ox- 8y=-24 ~ By=-24 y=3 We will substitute the value of yin the first equation to obtain the coordinate of the intersection. 3x4 2(3)=18 Replace y by 3. 3x+6=18 Simplify. 3r= 18-6 Collect like terms. 3x=12 Combine like terms. xe4 Divide both sides by 3. ‘The intersection of the first equation and the second equation is (4, 3). Now we will determine the intersection of the first equation and third equation. First equation: 3x +2y=18 ‘Third equation: x= 5 Notice that the third equation already has x = 5, we will directly substitute the value of x to the first equation. 3(5) + 2y=18 Replace x by 5, 15 +2y=18 Simplify. 2y=18-15 Collect like terms, 2y=3 Combine like terms. yas Divide both sides by 2, The intersection of the first equation and the third equation is (5, 1.5), ‘Chapter 6: Linear Programming Page 165(a) (6,15) (5,0) Ne | | © ‘Step 7: Substitute the coordinates at the extreme points on the feasible region to the objective Step 8: function. Objective Function: P= 1,200x+ 1,600 Extreme points | Values of the objective function (0,5) 1,200(0) + 1,600(5) = 0+8,000= 6,000 5.0) 1,200(5) + 1,600(0) = 6,000+ G3) 1,200(4) + 1,600(3) = 4,800 + 4,800 = 9,600 (5,15) 1,200(5) + 1,600(1.5) = 6,000 + 2,400 = 8400 Formulate the decision. Since the coordinate (4, 3) will give the highest value of P9,600. The decision is to create 4 Design A gowns and 3 Design B gowns in order to maximize sales, Decision Design A gowns, Design B gowns, P=P9,600 To check we substitute the values of x and y in all the constraints, 3x+2ys18 2x+4ys20 xs5 3(4) +2(3)< 18 2(4) + 4(3) < 20 45 1246518 841220 18518 20520 Thus, (4, 3) is correct, since it satisfies all the constraints and the two constraints are being maximized. Example 2: A pharmacist produces a drug from two ingredients. Each ingredient contains the same three antibiotics in different proportions. Each ingredient A produced resulted in P80 in cost; each {ingredient B resulted in P50 in cost. The production of antibiotics is dependent on the availability of limited resources, The resource requirements for production are as follows. Resources Requirement Minimum Antibiotic _|""IngredientA [IngredientB | Requirement “Antibiotic 1 units Tunit 6 Antibiotic 2 unit unit 4 Antibiotic 3 2units 6units 2 Page 166 ‘Chapter 6: Linear Prograrn#¥she company wants to determine the quantity of ingredients A and B that must go into the drug in arder to meet the antibiotics’ minimum requirements at the minimum cost. olution: norder to solve the given linear programming model, itis necessary to formulate first the standard ‘arm of the model, ep 1: Represent the unknown in the problem, Letx be the quantity of ingredient A, and ‘be the quantity of ingredient B. ‘tep2: Tabulate the data about the facts (if necessary), Tngredient AG) _|Ingredient 8) _|_ Requirement 3 1 6 1 1 4 Antibiotic 3 2 6 12 Cost P80 P50 ‘ep3: Formulate the objective function and constraints by restating the information in mathematical form. ‘The objective function is: Minimize: C= 80x + SOy ‘The constraints are: 3x+ y26 = Antibiotic1 x+ y24 => Antibiotic2 2x+ 6y212 = Antibiotic 3 x20,y20 ep4: Plot the constraints of the LP problem on a graph, with ingredient A (x) shown on the horizontal axis and ingredient B (y) shown in the vertical axis, using the intercept rule. Figure 6.10 shows the initial graph of the LP model. 3x+y26 xtyed 2x4 Gy212 3x+y=6 xty=4 2x + 6y=12 Letx=0 2(0) + 6y=12 0+ 6y=12 6y=12 y=2(0,2) Letx=0 Lety=0 2x + 6(0) = 12 2x+0=12 2x= 12 x= 6 (6,0) ®e 6: Linear Programming Page 167Figure 6.10 Step 5: Determine the feasible region. Figure 6.11 shows the area of the feasible region. Figure 6.11 | ‘Step 6: Solve the Intersection of the lines, which satisfies the feasible solution simultaneously, using the elimination method. We will solve the intersection of the first equation and second equation using the elimination method. First equation: 3x + y= 6 Second equation: x+y =4 Find the Least Common Multiple (LCM) of xn order to eliminate the varlable x. 1Qx+y=6) => Bee y=6 Beye) > (-)BeedveI2 Or-2y=-6 -2y=-6 ys3 ‘Substitute the value of y in the first equation to obtain the intersection of the first equatio and second equation. Page 163, (Chaplet 6: Linear Progra?We will now solve the intersection of the second and third equations. Second equation: x+y =4 Third equation: 2x + 6y = 12 Find the Least Common Multiple (LCM) of x to eliminate the variable x. Ax+ yd) => det By=8 Ax + 6y=12) = (-) 2x+6y=12 xn dyed aly= 4 yel Substitute the value of in the second equation to obtain the coordinate of the intersection, xele4 xe4-1 BD ‘Step 7: Substitute the coordinates at the extreme points of the feasible region in the objective function. Objective Function: C= 80x + 50 Extreme points _| Values of the objective function. (0.6) 80(0) +50(6)= 0+ 300= 300 (6,0) 80(6)+50(0)=480+ 0=480 (1,3) 80(1) +50(3)= 80+ 150=230 (3.1) 80(3) +50(1)= 240+ 50=290 Step 8: Formulate the decision. Since the coordinate (1, 3) will give the lowest. value of P230. The decision is to mix 1 unit of ingredient A and 3 units of Ingredient B to minimize the cost. Decision: x= 1 unit of ingredient A ‘y= 3 units of ingredient B ¢=P230 ‘To check we substitute the values of x andy in all the constraints. 3xt+y26 xty24 2x + 6212 3(1) +326 14324 2(1) + 6(3) 212 34326 424 2418212 626 20212 Thus, (1, 3) is correct, since it satisfies all the constraints and two of the constraints are minimized. ‘Chapter 6: Linear Programing Pogo 169Supplementary Exerelse 6.3 i 1, Establish and solve the linear programming model of the following: | | aA souvenir store wishes to produce two models of souvenirs: model A and model B. fivery modlel-A souvenir will result in P14 proft, and every model-B souvenir will result in P23 profit. To manufacture a model-A souvenir requires 3 minutes on stage 1 and 6 minutes on) stage 2. A model-B souvenir requires 5 minutes on stage 1 and 4 minutes on stage 2. There, are 270 minutes on stage 1 and 360 minutes on stage 2 for processing orders. How many| souvenirs of each model should the store make in order to maximize profit? b. Ina certain hospital, a nutritionist prepares a menu for patients on low-fat diets. The! primary ingredients are chicken and rice. The meal must contain enough protein and iron to, meet at least the DOH-tecommencded dally allowance (RDA) for each nutrient. The RDA for! protein is 60 grams and 30 milligrams for iron. Bach 4-ounce serving of chicken contains 69 grams of protein, 15 milligrams of iron, and 6 grams of fat. Each 1-cup serving of rice contains 12 grams of protein, 9 milligrams of iron, and 3 grams of fat. How much chicken ang rice should be included in the meal in order to minimize the amount of fat? 2, Solve the following Linear Programming Models: | a. Maximize: P= 13x+6y —b. Minimize: C= 24x+29y _c. Maximize: P= 16+ I1y Subject to: x+2ys8 Subject to: Sx + 4y220 Subject; xs10 2x+ y2B 2x+5y230 yzit 2x+2ys 16 3x4 5y215 2e+y<30 2020 x20,y20 x+lys34 | x20,y20 © Init 6.4; Simplex Method ‘The simplex method requires that all constraints be expressed as equations. Mathematically, itis easier to solve a system of linear equations than systems of inequalities. Therefore, all the inequalities shall be converted into equations or in the standard form of a linear programming problem. Simplex Method is an iterative technique that begins with a feasible solution that is not optimal but serves as a starting point. With the use of algebraic manipulation, the solution is improved until no further Setup the ial Tableau o improvement is possible. It is (Tie rare negate ones) ‘more convenient to solve linear ~ bea 4 TOW programming models in the simplex method with more than ‘two unknown variables because geometrically it is difficult to graph. The idea of the simplex method fs to start at the corner where all the unknowns are 0 Yos Deterine the pivot t “ro here postive ention intest ratio? and then walk around the region Yes from one corner to another the value of the objective function Doleine tho pivotal row always increases (for >= i maximization) and always v Feeregis decreases (for minimization) Compute a new labeay until the best comer Is determined, Page 170 ‘Chapler 6: Linear Programi™®