21 Linear Programming 2: Basic Concepts The baste concepts needed to develop the simpler methed for eolving Linear program- ning probleme are presented. PREREQUISITES: Linear Systens Matrices Linear independence Euclidean space 2” Chapter 20: Linear Programing 1 INTRODUCTION In the last chapter we presented a geometric technique for solving linear programing problens in two variables. However, this technique is not practical for the solution of linear programming problems in three or more variables. In this chapter we develop the fundamental ideas behind an algebraic technique, called the si) rethod, for solving linear programing problens in any munber of fariables. The simplex method itself is presented in Chapter 22. ‘The general Linear programming problen inn variables, describ- sd below, is analogous to Problem 20.1 in the last chapter les 303304/ Basic Concerts PROBLEM 24.1 Find values of ay, #y»+++4, vhioh either tegen tag, aye, (S)(2)(4) by Tay, (S1C2)(4) by FG (LZ) By As in Chapter 20, the linear function z in (21.1) is called the ob- dective function’ and conditions (21.2) and (21.3) are called the ‘conetraince of the problem. For our purposes, it is necessary that we first convert our general Linear programming problen to the following etandand form: PROBLEM 24.2 Find valuee of ayy 250+. 2, viich mavinize reggie tee 2.4) ayy aygty tty Dy See 27 ati. us) Sm * Smz*2* Any linear programming problem can always be put in this standard form using the following three steps:Linear Programing 11 / 305 Step 1, Convert a minimization problem to a maximization pro- lon by defining 2 new objective function For example, the problen of minimizing the objective function 2 + Sey Sey is equivalent to the problem of maximizing the objective function 2ey- Sey+ Ses. Stes 2. Convert a > constraint to a < constraint by multiply- ing the inequality by -I- Thus, the constraint “+ 2e, 26 is the same as the constraint Stes 3. Convert a < constraint to an equality constraint by adding @ nonnegative eiaak variable to the 1efthand side of the in- equality. For example, if the original problem contains three var- ables, and one of the constraints is “jo 2+ hrs < -6, we add a new variable «, > 0 to the lefthand side to obtain a7 2eytdagte, = 6. The variable cq takes up the slack between the two sides of the in- equality. In this way, a new yarlable is added to the problem for each < constraint, We assign each slack variable introduced a co- efficient oz =0 in the objective function, so thet the objective function 1s not affected by the values of the Slack variables, EXAMPLE 21.1 convert the following Hnear programing problem to one in standard fort306 / Basic Concerts Subject to 2a + Say - 6 21> Tey Sry 254 > 6 Bay - Bry - Bry + 624 = 5 and Bys os Bye By > 0. SOLUTION te sizse step is to multiply the objective function by =1 to convert the problem to a maximization problen. The second Step is to multiply the second constraint by -1 to convert it to a < inequality. The third step is to add slack variables 25 and 2¢ ¥o the first and second constraints to convert them to equalities. ‘The final problem in standard form is who, + 20, -2, +2, + 0c, + Org subject to and 190 5) Bye Bey Be > 0 It will be convenient to use matrix notation to express Problen 21.2 in 8 more compact fom as follows (the expression X 0 below denotes that each entry of the vector x is nomogative): PROBLEM 21.2 (in matrix notation? Maximize scx subject to andLinear Programming 11 / 307 where or 1 1 42" * Ay 422° xelr | yD ae Hl * 2, " In this formulation, the problem is to find a nonnegative vector x in the vector space R” which satisfies the constraint condition Ax=b and which makes the objective function z= cx as large as possible. Analogous to the terminology in Chapter 20, any nonnege- tive vector x which satisfies the constraint Ax=b is called a feasible solution to the linear programming problem. The set of all feasible solutions in A" is called the feasibie set or the feasible region of the problen. A feasible solution which maximizes the ob- jective function is called an optimal eolwtion. As in Chapter 20, there are three possible outcones to a Linear programming problen: (4). The constraints are inconsistent so that there are no feasible solutions. (i) The feasible set is unbounded and the objective function can be nade arbitrarily large. (id) There is at least one optinal solution. Im most realistic applications only case (iii) arises: Ke nox examine the nature of the feasible set of a linear pré gramming problem. To begin, let us introduce tho following defini- tion: DEFINITION 21.1 4 set of vectors in R” ie called convex 4f whenever x, and x, belong to the set, so does the vee~ tor xe txt = Oxy for any munber t in the interval [0, 1] -308 / Basic Concer Geometrically, the vector x= éxy + (1- #)xp Lies’ on the Line segnent connecting the tips of the vec tors xy and x2 (Fig. 21.1). Thus, a convex sot can be Viewed as one in which the Line segment connect~ ing any two points in the set also belongs to the set. Figures 21.2(a), (®), and (c) illustrate three convex sets in R?. Figure 2j-1(@) is an example of a set in ‘Re which is not convex. In Exer- cise 21.7, we ask the reader to prove the following theorem: THEOREM 21.1 The feasible set of 2 standard Linear programing problen is con thy — %a Keay + 60K - Xp) t+ = 2x, Figure 21.4 Figure 24.2Linear Progranmine TI / 309 ExanpLe 21.2 pox the following Linear programing problen: Maximize = 3r, +2, subject to and the feasible set consists of the portion of the intersection of the two planes (0, 10/3, 20/3) which lies in the first octant of Pieges-space. As we ask the (5/2, 0, 5/5 reader to show in Exercise 21.8, (5/20. 5/2) this intersection consists of the Tine seguent connecting the points = (5/2, 0, 5/2) and (0, 10/3, 20/3) “1 (Fig. 21.5), which is clearly Figure 21.3 ExamPLe 21.3 rox the following Linear progransing problem: Maximize 222, -32)+225 subject to and the feasible set consists of the portion of the plane 2x, + dey Ses = 12310 / Basic Concerts which lies in the first octant of ayozes-space. The reader can easily verify that Fig. 21.4 is a diagram of this feasible set and that it is convex. In Chapter 20, we introduced the concept of an extreme point of a feasible set in xyx2-space. (0,4) For an arbitrary convex set in BT, the corresponding definition is the following: DEFINITION 24.2 A vector x in a conven set to an extreme point of the convex set tf x FOG +x.) Figure 21.4 for any to vestore x, and x, ‘in the vet. In other words, the extreme points of a convex set are those points which do not Lie midway between any two points in the set. For ex- ample, the extrene points of the convex set illustrated in Fig. 21.2 are the two endpoints (5/2, 0, 8/2) and (0, 10/3, 20/3) of the straight-Line segaent, For the convex set illustrated in Fig. 21.4, the extreme points are the three comer points (6.0, 0}, (©, 3, 0), and (0, 0, 4) of the triangular-shaped region. iB Recall that in the last chapter we called a set in 22 bounded if it can be enclosed in a sufficiently large circles that is, if there is sone positive radius 7 such that each point x= (@,,2)) in the set satisfies 3 IIxil-yeteaz 0 For the following linear progranming problen in standard form Maximize subject to and (a) show that the feasible set is bounded, (b) find a11 basic solutions of the linear system Ax=b, (ec) find all basic feasible solutions of the probien, (@ find an optimat solution and the maximum value of the objective function, (e) draw a graph of the basic feasible solutions, as in Fig. 21.5, in which adjacent basic feasible solutions are Linked with a single line. For the following Linear programming problem in standard form: Maximize 22x, - 62, + 325 subject to yt Sy 430522 ny ¢ dey + tug = 3 and (a) find a11 basic solutions of the linear systen Ax=b, (D) show that the problem has no basic feasible solutions. (From this it follows that the feasible set of this problem is eapty.)215 24.6 2aeT 21.8 Linear Progranminé 11 / 321 For the folloving linear programing problen: Maximize 2 5t, ¢22)- 25 subject to and (a) convert the problem to one in standard forn, (b) find ali basic solutions of the Linear system 4) the standard problem, (c) find all basic feasible solutions of the standard problen, (@) find an optimal solution of the standard problem and the maxinur value of the objective function, (0) éray a graph of the basic feasible sofutions of the standard problem, 2s in Fig. 21.5, in which adjacent basic feasible Solutions are linked with a single line. (f) find an optimal solution of the original problem. in Repeat the instructions in Exercise 21.5 for the Linear pro- granning problen: Mininize a= 22, - 32,¢25 subject to and Prove theorem 21.1 as follows: (a) Show that if Ax, «b and Ax, «by X= 0x, + (1- #)x, for any # in the interval [0, 1]. (©) Show that if x20 and xp20) then x20 58 x= tx, + (1- 9x, for any t in the interval [0,1] jen Ax=b if Show that the feasible set of the linear programming problen in Example 21.2 is the set illustrated in Fig. 21.5.322 / Basic Concerts 24.9 Show that the feasible set of the linear programming problem in Example 21.5 is bounded. Proceed as follows: (a) From the constraint de, t+ dey Qe, = 20 and the nonnegativity conditions 2;>0 (i= glude that =; <20 for i= 1,3,4,5 12,3,4,5) com (b) Add the two constraints together and conclude that 2, < 50, Ce) Fron (a) and (6), conchuie that [fx] < » for sone positive 24.40 Show that the linear system (21.7) can be written in the vee- tor form (21.8).