Linear Optimization in Applications

1. INTRODUCTION

INTRODUCTION 1.1 Formulation of a Li near Programming Problem Linear programming îs a powe血1 mathematical 1001 for the optimization of an objcctive under a numbcr of constraints in any given situation. Its application C曲 be in maximizing profils or minimizing costs whlle making the best use of the limited resources avaîlable. B目ause it is a malhematical t∞1 ， it is best explained using a prac!ical example Example 1.1 A pipe manufacluring company produces tWQ types of pipes, type I 叩d Iype n The storage space, raw material requirement 胡d production rale are given as below: 且==目 b且i 工站直且 (&固 paoy Ay晶ilallili!)! Storage space 5m月p'pe 3 m2 /pipe 750 m2 Raw materials 6 kglpipe 4 kglpipe 8∞ kglday Production rate 30 pipesthour 20 pipeslhour 8 hourslday S J H O 也 d u tctnu 阱 呵 1 耐 心 h m 心 帥 叫 8 U 尸 坤 扭 曲 si-oco 的 月 A M h 川 1 日 肘 。 恤 詢 問 廿 s w 心 何 v m m M 叫 巾 帥 的 叫 仙 伽 叫 岫 咕 則 叫 自 問 宙 間 血 M 叫 m m 肌 川 ω 叩 M V m M h 吶 仰 」 聞 仲 叫 叫 間 耐 iy s uh l b 戶 l s 呻 師 叫 叭 咖 m t zmvhd μ 帥 M m 間 m memcdm ddhM3a ihk-Rm H : 叫 h 帥 吋 h 7 世 叫 別 叫 心 向 明 叫 咱 們 m N 叫 T F 山 h k m v Solution 1.1 LetZ = X) = 100al profit number of Iype I pipes produced each day number of type n pipcs pr'吋uced each day '‘, = Sînce our obj且llve IS lO maxlmlze pro缸 ， we write 曲。bj配tive function, equation (0)、 whîch wîll calculale lhe IOlal profil MaximizeZ= 10xI +8X2 (0) 2 Linear Optimization 的 Applications Xl and X2 in equation (0) are called decision variables. There are three constraints which govem the number of type 1 and type 11 pipes produced. These constraints are: (1) the availability of storage space, (2) the raw materials available, and (3) the working hours of labourers. Constraints (1), (2) and (3) are written as below: Storage space: 5Xl + 3X2 三 750 、 ‘ ' ， .E.A / ， . ‘ 、 、 、 Raw material 6x1 + 4X2 三 800 一一一一一一一一一一一一一一-一一-一一 (2) x x Working hours :一土+一土豆 8 一一一一一一一一一一一一一… (3) 30 20 When constraint (3) is multiplied by 60, the unit of hours will be changed to the unit of minutes (ie. 8 hours to 480 minutes). Constraint (3) can be written as : 2Xl + 3X2 三 480 (3) Lastly, there are two more constraints which are not numbered. They are Xl 三 O and X2 三 0， simply because the quantities Xl and X2 cannot be negative. We can now summarize the problem as a linear programming model as follows: 勻 ， 旬 x nxu + xm nununuAU E 』 《 J n u n δ = 弓 I O O A 『 Z < 一 歪 歪 咒 。 2 2 2 utxxx n1343 . m ﹒ 戶 + + + a b ! l l l AUXXX E W S ζ J f O 司 4 、 ‘ . ， / nU J ' .‘ 、 、 (1) (2) (3) Xl ~O X2~ 0 1.2 Solving a Linear Programming Problem There are two methods in solving linear prograrnming models, namely, the graphical method and the simplex method. The graphical method can only solve linear programming problems with two decision variables, while the simplex method can solve problems with any number of decision variables. Since this book will only concentrate on the applications of linear prograrnming, Introduction 3 the rnathernatical details for solving the rnodels will not be thoroughly treated. In this section, the graphical method and the simplex method will only be briefly described. 1.2.1 Graphical Method Let us look at the linear prograrnrning rnodel for Exarnple 1.1: Max Z = 10Xl + 8X2 “…一 subject to 5Xl + 3 X2 至 750..._..... 的 自…"“…“…叮叮………“凹，叫“_........ (1) 、 ‘ ， / AU / E E ‘ 、 6Xl + 4X2 至 800 ...叮叮叮叮“ “一 …......................_.......呵 呵 ω 叮叮叮叮一 "曰 “ … (2) 2Xl + 3X2 歪 480 山_..……"叮叮叮………… 一。" “ _.......“…… 一 " “ … (3) Xl ~O X2~ 0 The area bounded by (1) : 5Xl + 3X2 = 750, (2) : 6Xl + 4X2 = 800, (3) : 2Xl + 3X2 = 480, (4) : Xl =0 and (5) : X2 =0 is called the feasible space, which is the shaded area shown in Fig. 1.1. Any point that lies within this feasible space wi11 satisfy all the constraints and is called a feasible solution. X2 Note: the x) and X2 axes are not drawn on the same scale. X) Fig. 1.1 Graphical Method The optirnal solution is a feasible solution which, on top of satisfying all constraints, also optirnizes the objective function, that is, rnaxirnizes profit in this case. By using the slope of the objective function, -(10/8) in our case, a line can be drawn with such a slope which touches a point within the feasible space 4 Linear Optimization 的 Applications and is as f;缸 away as possible from the point of origin O. This point is represented by A in Fig. 1.1 and is the optima1 solution. From the graph, it can be seen that at optimum, Xl = 48 (type 1pipes) 也= 128 (type 11 pipes) max Z = 1504 (profit in $), ca1culated from 10(48) + 8(128) From Fig. 1.1, one can also see whether or not the resources (i.e. storage space, raw materials, working time) are fully utilized. Consider the storage space constraint (1). The optima1 point A does not lie on line (1) and therefore does not satisfy the equation 5Xl + 3X2 = 750. If we substitute Xl = 48 and X2 = 128 into this equation, we obtain: 5(48) + 3(128) = 624 < 750 Therefore, at optimum, only 624 m2 of storage space are used and 126 m2 (i.e. 750 - 624) are not used. By similar reasoning, we can see that the other two resources (raw materia1s and working time) are fully utilized. If constraint (1) of the above problem is changed to 5Xl + 3X2 三 624， that is, the available storage space is 624 m2instead of 750 m2, then line (1) will a1so touch the feasible space at point A. In this case, lines (1), (2) and (3) are concurrent at point A and a11the three resources are fully utilized when the maximum profit is attained. There is a technical term ca11ed “optima1 degenerate solution" used for such a situation. 1.2.2 Simplex Method When there are three or more decision variables in a linear programming model, the graphica1 method is no more suitable for solving the model. Instead of the graphical method, the simplex method will be used. 5 Introduction As mentioned earlier, the main theme of this book is applications of linear Therefore, programming, not mathematical theory behind linear programming. no detail description of the mathematics of linear programming will be presented here. There are many well developed computer programs available in the market for solving linear programming models using the simplex method. One of them is QSB+ (Quantitative Systems for Business Plus) written by Y.L. Chang and R.S. Sullivan and can be obtained in any large bookshop world-wide. The author will use the QSB+ software to solve all the problems contained in the later chapters of this book. Examples of the techniques employed in the simplex method wi1l be illustrated in Appendix A at the end of this book. Some salient points of the method are summarized below. First of all we introduce slack variables S I，也 and S3 (S1, S2, S3 ~ 0) for Example 1.1 to change the constraints from inequalities to equalities such that the model becomes: (Oa) Z - 10Xl - 8X2 = 0 subject to (1a) 5Xl + 3X2 + SI = 750 (2a) 6Xl + 4X2 + S2 = 800 (3a) 2Xl + 3X2 + S3 = 480 The initial tableau of the simplex method is shown in Table 1.1. It is in fact a rewrite of equations (Oa), (la), (2a) and (3a) in a tableau format. 品 一 o o o l 已 一 o o l o 趴 一 0 1 0 0 也 A 3 4 3 h ﹒ 一 心 5 6 2 Z 一 1 0 0 0 Basic Variable (Oa) Z (1a) SI (2a) S2 (3a) S3 Initial Simplex Tableau for Example 1.1 Table 1.1 Linear Optimization 的 Applications 6 After two iterations (see Appendix A), the final tableau will be obtained and is shown in Table 1.2 below. Basic Variable (Oc) Z (1c) Sl (2c) Xl (3c) X2 3-82A6 s-aooa 2-4932 s l o a n 吋 趴 一 0 1 0 0 也 一 o o o l 叫 一 o o l o z-1000 Table 1.2 Final Simplex Tableau for Example 1.1 To obtain a solution from a simplex tableau, the basic variables are equal to the values in the RHS column. The non-basic variables (i.e. the decision variables or slack variables which are not in the basic variable column) are assigned the Therefore, from the final tableau, we can see that the optimal value zero. solution is: Z = 1504 Xl = 48 X2 = 128 Sl = 126 S2 = 0 } non 仔.枷i 比 cvar 缸 ri 昀岫 a 油 bl臼叫 a 缸 re 叩a 叫 l ω It can be seen that this result is the same as that found by the graphica1 method. S1 here is 126, which means that the slack variable for storage space is 126 and therefore 126 m2 of storage space is not utilized. Sl and S2 are slack variables S3 = 0 for the other two resources and are equa1 to O. This means that the raw materia1s and the working time are fully utilized. Revised Simplex Method The revised simplex method is a1so ca11ed the modified simplex method. In this method, the objective function is usually written in the last row instead of 1.2.3 the first. Ex剖nples of the technique are illustrated in Appendix B. QSB+ uses the revised simplex method in solving linear programming models. The initial tableau for Example 1.1 is shown in Table 1.3. Introduct的n Basic X) X2 S) S2 S3 Variable Q 10 8 。 。 。 RHS S) 。 5 3 。 。 750 S2 。 6 4 。 。 800 S3 。 2 3 。 。 480 L 。 。 。 。 。 。 Cj-Zj 10 8 。 。 。 Table 1.3 Initial Simplex Tableau for Example 1.1 (Revised Simplex Method) After two iterations (see Appendix B), the final tableau will be obtained. It is shown in Table 1.4. Basic x) X2 S) S2 S3 Variable Q 10 8 。 。 。 RHS S) 。 。 。 -0.9 0.2 126 x) 10 。 。 0.3 -0.4 48 X2 8 。 。 -0.2 0.6 128 L 10 8 。 1.4 0.8 1504 Cj -Zj 。 。 。 -1.4 -0.8 Table 1.4 Fínal Símplex Tableau for Example 1.1 (Revísed Símplex Method) 7 ...