linear programming problems in operations research pdf

operations research linear programming problems and operations research linear programming simplex method
EdenKelly Profile Pic
EdenKelly,United States,Professional
Published Date:12-07-2017
Your Website URL(Optional)
Comment
ORMS1020 Operations Research with GNU Linear Programming Kit Tommi Sottinen tommi.sottinenuwasa.fi www.uwasa.fi/tsottine/orms1020 August 27, 2009Contents I Introduction 5 1 On Operations Research 6 1.1 What is Operations Research . . . . . . . . . . . . . . . . . . . 6 1.2 History of Operations Research . . . . . . . . . . . . . . . . . 8 1.3 Phases of Operations Research Study . . . . . . . . . . . . . . . 10 2 On Linear Programming 13 2.1 Example towards Linear Programming . . . . . . . . . . . . . . 13 2.2 Solving Linear Programs Graphically . . . . . . . . . . . . . . . 15 3 Linear Programming with GNU Linear Programming Kit 21 3.1 Overview of GNU Linear Programming Kit . . . . . . . . . . . 21 3.2 Getting and Installing GNU Linear Programming Kit . . . . . . 23 3.3 Using glpsol with GNU MathProg . . . . . . . . . . . . . . . . 24 3.4 Advanced MathProg and glpsol . . . . . . . . . . . . . . . . . 32 II Theory of Linear Programming 39 4 Linear Algebra and Linear Systems 40 4.1 Matrix Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Solving Linear Systems . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 Matrices as Linear Functions . . . . . . . . . . . . . . . . . . . 50 5 Linear Programs and Their Optima 55 5.1 Form of Linear Program . . . . . . . . . . . . . . . . . . . . . . 55 5.2 Location of Linear Programs’ Optima . . . . . . . . . . . . . . 61 5.3 Karush–Kuhn–Tucker Conditions . . . . . . . . . . . . . . . . 64 5.4 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65CONTENTS 2 6 Simplex Method 68 6.1 Towards Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 68 6.2 Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 75 7 More on Simplex Method 87 7.1 Big M Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.2 Simplex Algorithm with Non-Unique Optima . . . . . . . . . . 94 7.3 Simplex/Big M Checklist . . . . . . . . . . . . . . . . . . . . . 102 8 Sensitivity and Duality 103 8.1 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.2 Dual Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.3 Primal and Dual Sensitivity . . . . . . . . . . . . . . . . . . . . 136 III Applications of Linear Programming 137 9 Data Envelopment Analysis 138 9.1 Graphical Introduction to Data Envelopment Analysis . . . . . 138 9.2 Charnes–Cooper–Rhodes Model . . . . . . . . . . . . . . . . . . 152 9.3 Charnes–Cooper–Rhodes Model’s Dual . . . . . . . . . . . . . . 160 9.4 Strengths and Weaknesses of Data Envelopment Analysis . . . 167 10 Transportation Problems 168 10.1 Transportation Algorithm . . . . . . . . . . . . . . . . . . . . . 168 10.2 Assignment Problem . . . . . . . . . . . . . . . . . . . . . . . . 179 10.3 Transshipment Problem . . . . . . . . . . . . . . . . . . . . . . 184 IV Non-Linear Programming 190 11 Integer Programming 191 11.1 Integer Programming Terminology . . . . . . . . . . . . . . . . 191 11.2 Branch-And-Bound Method . . . . . . . . . . . . . . . . . . . . 192 11.3 Solving Integer Programs with GNU Linear Programming Kit . 199Preface These lecture notes are for the course ORMS1020 “Operations Research” for fall 2009 in the University of Vaasa. The notes are a slightly modified version of the notes for the fall 2008 course ORMS1020 in the University of Vaasa. The chapters, or sections of chapters, marked with an asterisk () may be omitted — or left for the students to read on their own time — if time is scarce. The author wishes to acknowledge that these lecture notes are collected from the references listed in Bibliography, and from many other sources the author has forgotten. The author claims no originality, and hopes not to be sued for plagiarizing or for violating the sacred c laws. Vaasa August 27, 2009 T. S.Bibliography 1 Rodrigo Ceron: The GNU Linear Programming Kit, Part 1: Introduction to linear optimization, Web Notes, 2006. http://www-128.ibm.com/developerworks/linux/library/l-glpk1/. 2 Matti Laaksonen: TMA.101 Operaatioanalyysi, Lecture Notes, 2005. http://lipas.uwasa.fi/mla/orms1020/oa.html. 3 Hamdy Taha: Operations Research: An Introduction (6th Edition), Pren- tice Hall, Inc, 1997. 4 Wayne Winston: Operations Research: Applications and Algorithms, Inter- national ed edition, Brooks Cole, 2004.Part I IntroductionChapter 1 On Operations Research This chapter is adapted from Wikipedia article Operations Research and 4, Ch. 1. 1.1 What is Operations Research Definitions To define anything non-trivial — like beauty or mathematics — is very difficult indeed. Here is a reasonably good definition of Operations Research: 1.1.1 Definition. Operations Research (OR) is an interdisciplinary branch of applied mathematics and formal science that uses methods like mathemati- cal modeling, statistics, and algorithms to arrive at optimal or near optimal solutions to complex problems. Definition 1.1.1 is problematic: to grasp it we already have to know, e.g., what is formal science or near optimality. From a practical point of view, OR can be defined as an art of optimization, i.e., an art of finding minima or maxima of some objective function, and — to some extend — an art of defining the objective functions. Typical objective functions are  profit,  assembly line performance,  crop yield,  bandwidth,  loss,  waiting time in queue,  risk. From an organizational point of view, OR is something that helps manage- ment achieve its goals using the scientific process.What is Operations Research 7 ThetermsORandManagementScience(MS)areoftenusedsynonymously. When a distinction is drawn, management science generally implies a closer relationship to Business Management. OR also closely relates to Industrial Engineering. Industrial engineering takes more of an engineering point of view, and industrial engineers typically consider OR techniques to be a major part of their tool set. Recently, the term Decision Science (DS) has also be coined to OR. More information on OR can be found from the INFORMS web page http://www.thescienceofbetter.org/ (If OR is “the Science of Better” the OR’ists should have figured out a better name for it.) OR Tools Some of the primary tools used in OR are  statistics,  optimization,  probability theory,  queuing theory,  game theory,  graph theory,  decision analysis,  simulation. Because of the computational nature of these fields, OR also has ties to com- puter science, and operations researchers regularly use custom-written soft- ware. In this course we will concentrate on optimization, especially linear opti- mization. OR Motto and Linear Programming The most common OR tool is Linear Optimization, or Linear Programming (LP). 1.1.2 Remark. The “Programming” in Linear Programming is synonym for “optimization”. It has — at least historically — nothing to do with computer- programming. LP is the OR’ists favourite tool because it is  simple,  easy to understand,History of Operations Research 8  robust. “Simple” means easy to implement, “easy to understand” means easy to explain (to you boss), and “robust” means that it’s like the Swiss Army Knife: perfect for nothing, but good enough for everything. Unfortunately, almost no real-world problem is really a linear one — thus LP is perfect for nothing. However, most real-world problems are “close enough” to linear problems — thus LP is good enough for everything. Example 1.1.3 below elaborates this point. 1.1.3 Example. Mr. Quine sells gavagais. He will sell one gavagai for 10 Euros. So, one might expect that buying x gavagais from Mr. Quine would cost — according to the linear rule — 10x Euros. The linear rule in Example 1.1.3 may well hold for buying 2, 3, or 5, or even 50 gavagais. But:  One may get a discount if one buys 500 gavagais.  There are only 1;000;000 gavagais in the world. So, the price for 1;000;001 gavagais is +1.  The unit price of gavagais may go up as they become scarce. So, buying = 950;000 gavagaismightbeconsiderablymoreexpensivethan C9;500;000.  It might be pretty hard to buy 0:5 gavagais, since half a gavagai is no longer a gavagai (gavagais are bought for pets, and not for food).  Buying10 gavagais is in principle all right. That would simply mean selling 10 gavagais. However, Mr. Quine would most likely not buy gavagais with the same price he is selling them. 1.1.4 Remark. You may think of a curve that would represent the price of gavagais better than the linear straight line — or you may even think as a radical philosopher and argue that there is no curve. Notwithstanding the problems and limitations mentioned above, linear tools are widely used in OR according to the following motto that should — as all mottoes — be taken with a grain of salt: OR Motto. It’s better to be quantitative and naïve than qualitative and pro- found. 1.2 History of Operations Research This section is most likely omitted in the lectures. Nevertheless, you should read it — history gives perspective, and thinking is nothing but an exercise of perspective.History of Operations Research 9 Prehistory Some say that Charles Babbage (1791–1871) — who is arguably the “father of computers” — is also the “father of operations research” because his research into the cost of transportation and sorting of mail led to England’s universal “Penny Post” in 1840. OR During World War II The modern field of OR arose during World War II. Scientists in the United Kingdom including Patrick Blackett, Cecil Gordon, C. H. Waddington, Owen Wansbrough-Jones and Frank Yates, and in the United States with George Dantzig looked for ways to make better decisions in such areas as logistics and training schedules. Here are examples of OR studies done during World War II:  Britain introduced the convoy system to reduce shipping losses, but while the principle of using warships to accompany merchant ships was gen- erally accepted, it was unclear whether it was better for convoys to be small or large. Convoys travel at the speed of the slowest member, so small convoys can travel faster. It was also argued that small convoys would be harder for German U-boats to detect. On the other hand, large convoys could deploy more warships against an attacker. It turned out in OR analysis that the losses suffered by convoys depended largely on the number of escort vessels present, rather than on the overall size of the convoy. The conclusion, therefore, was that a few large convoys are more defensible than many small ones.  In another OR study a survey carried out by RAF Bomber Command was analyzed. For the survey, Bomber Command inspected all bombers returning from bombing raids over Germany over a particular period. All damage inflicted by German air defenses was noted and the recom- mendation was given that armor be added in the most heavily damaged areas. OR team instead made the surprising and counter-intuitive recom- mendation that the armor be placed in the areas which were completely untouched by damage. They reasoned that the survey was biased, since it only included aircraft that successfully came back from Germany. The untouched areas were probably vital areas, which, if hit, would result in the loss of the aircraft.  When the Germans organized their air defenses into the Kammhuber Line, it was realized that if the RAF bombers were to fly in a bomber stream they could overwhelm the night fighters who flew in individual cells directed to their targets by ground controllers. It was then a matter of calculating the statistical loss from collisions against the statisticalPhases of Operations Research Study 10 loss from night fighters to calculate how close the bombers should fly to minimize RAF losses. 1.3 Phases of Operations Research Study Seven Steps of OR Study An OR project can be split in the following seven steps: Step 1: Formulate the problem The OR analyst first defines the organi- zation’s problem. This includes specifying the organization’s objectives and the parts of the organization (or system) that must be studied before the problem can be solved. Step 2: Observe the system Next, the OR analyst collects data to esti- mate the values of the parameters that affect the organization’s problem. These estimates are used to develop (in Step 3) and to evaluate (in Step 4) a mathematical model of the organization’s problem. Step 3: Formulate a mathematical model of the problem TheORan- alyst develops an idealized representation — i.e. a mathematical model — of the problem. Step 4: Verify the model and use it for prediction The OR analyst tries to determine if the mathematical model developed in Step 3 is an accurate representation of the reality. The verification typically includes observing the system to check if the parameters are correct. If the model does not represent the reality well enough then the OR analyst goes back either to Step 3 or Step 2. Step 5: Select a suitable alternative Given a model and a set of alterna- tives, the analyst now chooses the alternative that best meets the or- ganization’s objectives. Sometimes there are many best alternatives, in which case the OR analyst should present them all to the organization’s decision-makers, or ask for more objectives or restrictions. Step 6: Present the results and conclusions The OR analyst presents the model and recommendations from Step 5 to the organization’s decision-makers. AtthispointtheORanalystmayfindthatthedecision- makers do not approve of the recommendations. This may result from incorrect definition of the organization’s problems or decision-makers may disagree with the parameters or the mathematical model. The OR analyst goes back to Step 1, Step 2, or Step 3, depending on where the disagreement lies.Phases of Operations Research Study 11 Step 7: Implement and evaluate recommendation Finally, when the organization has accepted the study, the OR analyst helps in implement- ing the recommendations. The system must be constantly monitored and updated dynamically as the environment changes. This means going back to Step 1, Step 2, or Step 3, from time to time. In this course we shall concentrate on Step 3 and Step 5, i.e., we shall concentrate on mathematical modeling and finding the optimum of a math- ematical model. We will completely omit the in-between Step 4. That step belongs to the realm of statistics. The reason for this omission is obvious: The statistics needed in OR is way too important to be included as side notes in this course So, any OR’ist worth her/his salt should study statistics, at least up-to the level of parameter estimization. Example of OR Study Next example elaborates how the seven-step list can be applied to a queueing problem. The example is cursory: we do not investigate all the possible objec- tives or choices there may be, and we do not go into the details of modeling. 1.3.1 Example. A bank manager wants to reduce expenditures on tellers’ salaries while still maintaining an adequate level of customer service. Step1: TheORanalystdescribesbank’sobjectives. Themanager’svaguely stated wish may mean, e.g.,  The bank wants to minimize the weekly salary cost needed to ensure that the average waiting a customer waits in line is at most 3 minutes.  The bank wants to minimize the weekly salary cost required to ensure that only 5% of all customers wait in line more than 3 minutes. The analyst must also identify the aspects of the bank’s operations that affect the achievement of the bank’s objectives, e.g.,  On the average, how many customers arrive at the bank each hour?  On the average, how many customers can a teller serve per hour? Step 2: The OR analyst observes the bank and estimates, among others, the following parameters:  On the average, how many customers arrive each hour? Does the arrival rate depend on the time of day?Phases of Operations Research Study 12  On the average, how many customers can a teller serve each hour? Does the service speed depend on the number of customers waiting in line? Step 3: The OR analyst develops a mathematical model. In this example a queueing model is appropriate. Let W = Average time customer waits in line q  = Average number of customers arriving each hour  = Average number of customers teller can serve each hour A certain mathematical queueing model yields a connection between these parameters:  (1.3.2) W = : q () This model corresponds to the first objective stated in Step 1. Step 4: The analyst tries to verify that the model (1.3.2) represents reality well enough. This means that the OR analyst will estimate the parameter W , q , and  statistically, and then she will check whether the equation (1.3.2) is valid, or close enough. If this is not the case then the OR analyst goes either back to Step 2 or Step 3. Step 5: The OR analyst will optimize the model (1.3.2). This could mean solving how many tellers there must be to make  big enough to make W q small enough, e.g. 3 minutes. We leave it to the students to wonder what may happen in steps 6 and 7.Chapter 2 On Linear Programming This chapter is adapted from 2, Ch. 1. 2.1 Example towards Linear Programming Very Naïve Problem 2.1.1Example. TelaInc. manufacturestwoproduct: 1 and 2. To = manufacture one unit of product 1 costs C40 and to manufacture = one unit of product 2 costs C60. The profit from product 1 is = = C30, and the profit from product 2 is C20. The company wants to maximize its profit. How many products 1 and 2 should it manufacture? The solution is trivial: There is no bound on the amount of units the company can manufacture. So it should manufacture infinite number of either product 1 or 2, or both. If there is a constraint on the number of units manufactured then the company should manufacture only product 1, and not product 2. This constrained case is still rather trivial. Less Naïve Problem Things become more interesting — and certainly more realistic — when there are restrictions in the resources.Example towards Linear Programming 14 = 2.1.2 Example. Tela Inc. in Example 2.1.1 can invest C40; 000 in production and use 85 hours of labor. To manufacture one unit of product 1 requires 15 minutes of labor, and to manufacture one unit of product 2 requires 9 minutes of labor. The company wants to maximize its profit. How many units of product 1 and product 2 should it manufacture? What is the maximized profit? The rather trivial solution of Example 2.1.1 is not applicable now. Indeed, = the company does not have enough labor to put all the C40;000 in product 1. Since the profit to be maximized depend on the number of product 1 and 1, our decision variables are: x = number of product 1 produced; 1 x = number of product 2 produced: 2 So the situation is: We want to maximize (max) profit: 30x + 20x 1 2 subject to (s:t:) the constraints money: 40x + 60x  40;000 1 2 labor: 15x + 9x  5;100 1 2 non-negativity: x ;x  0 1 2 Notethelastconstraint: x ;x  0. Theproblemdoesnotstatethisexplicitly, 1 2 but it’s implied — we are selling products 1 and 2, not buying them. 2.1.3 Remark. Some terminology: The unknowns x and x are called deci- 1 2 sion variables. Thefunction 30x +20x tobemaximizediscalledthe objective 1 2 function. What we have now is a Linear Program (LP), or a Linear Optimization problem, maxz = 30x + 20x 1 2 s:t: 40x + 60x  40;000 1 2 15x + 9x  5;100 1 2 x ;x  0 1 2 We will later see how to solve such LPs. For now we just show the solution. For decision variables it is optimal to produce no product 1 and thus put allSolving Linear Programs Graphically 15 theresourcetoproduct 2 whichmeansproducing 566:667 numberofproduct = 2. The profit will then be C11;333:333. In other words, the optimal solution is x = 0; 1 x = 566:667; 2 z = 11;333:333: 2.1.4 Remark. If it is not possible to manufacture fractional number of prod- ucts, e.g. 0:667 units, then we have to reformulate the LP-problem above to an Integer Program (IP) maxz = 30x + 20x 1 2 s:t: 40x + 60x  40;000 1 2 15x + 9x  5;100 1 2 x ;x  0 1 2 x ;x are integers 1 2 We will later see how to solve such IPs (which is more difficult than solving LPs). For now we just show the solution: x = 1; 1 x = 565; 2 z = 11;330: In Remark 2.1.4 above we see the usefulness of the OR Motto. Indeed, al- though the LP solution is not practical if we cannot produce fractional number of product, the solution it gives is close to the true IP solution: both in terms of the value of the objective function and the location of the optimal point. We shall learn more about this later in Chapter 8. 2.2 Solving Linear Programs Graphically From Minimization to Maximization We shall discuss later in Chapter 5, among other things, how to transform a minimization LP into a maximization LP. So, you should skip this subsection and proceed to the next subsection titled “Linear Programs with Two Decision Variables” — unless you want to know the general, and rather trivial, duality between minimization and maximization. Any minimization problem — linear or not — can be restated as a maxi- mization problem simply by multiplying the objective function by1: n n 2.2.1 Theorem. Let KR , and let g :R R. Suppose  w = ming(x) x2KSolving Linear Programs Graphically 16  n  and x 2R is a point where the minimum w is attained. Then, if f =g   and z =w , we have that  z = maxf(x); x2K   n and the maximum z is attained at the point x 2R . The mathematically oriented should try to prove Theorem 2.2.1. It’s not difficult — all you have to do is to not to think about the constraint-set K or n any other specifics, like the space R , or if there is a unique optimum. Just think about the big picture Indeed, Theorem 2.2.1 is true in the greatest possible generality: It is true whenever it makes sense Linear Programs with Two Decision Variables We shall solve the following LP: 2.2.2 Example. maxz = 4x + 3x 1 2 s:t: 2x + 3x  6 (1) 1 2 3x + 2x  3 (2) 1 2 2x  5 (3) 2 2x + x  4 (4) 1 2 x ;x  0 (5) 1 2 The LP in Example 2.2.2 has only two decision variables: x and x . So, it 1 2 can be solved graphically on a piece of paper like this one. To solve graphically LPs with three decision variables would require three-dimensional paper, for four decision variables one needs four-dimensional paper, and so forth. Four-Step Graphical Algorithm Step 1: Draw coordinate space Tradition is that x is the horizontal axis 1 and x is the vertical axis. Because of the non-negativity constraints on 2 x and x it is enough to draw the 1st quadrant (the NE-quadrant). 1 2 Step 2: Draw constraint-lines Each constraint consists of a line and of in- formation (e.g. arrows) indicating which side of the line is feasible. To draw, e.g., the line (1), one sets the inequality to be the equality 2x + 3x = 6: 1 2Solving Linear Programs Graphically 17 To draw this line we can first set x = 0 and then set x = 0, and we 1 2 see that the line goes through points (0; 2) and (3; 0). Since (1) is a -inequality, the feasible region must be below the line. Step 3: Define feasible region Thisisdonebyselectingtheregionsatisfied by all the constraints including the non-negativity constraints. Step 4: Find the optimum by moving the isoprofit line The isoprofit line is the line where the objective function is constant. In this case the isoprofit lines are the pairs (x ;x ) satisfying 1 2 z = 4x + 3x = const: 1 2 (In the following picture we have drawn the isoprofit line corresponding to const = 2 and const = 4, and the optimal isoprofit line corresponding to const = 9.) The further you move the line from the origin the better value you get (unless the maximization problem is trivial in the objective function, cf. Example 2.2.3 later). You find the best value when the iso- profit line is just about to leave the feasible region completely (unless the maximization problem is trivial in constraints, i.e. it has an unbounded feasible region, cf. Example 2.2.4 later).Solving Linear Programs Graphically 18 x 2 4 (2) (4) Redundant 3 (3) 2 D E Optimum Feasible region C 1 Isoprofit lines (1) B 0 A 0 1 2 3 4 x 1 From the picture we read — by moving the isoprofit line away from the origin — that the optimal point for the decision variables (x ;x ) is 1 2 C = (1:5; 1): Therefore, the optimal value is of the objective is z = 41:5 + 31 = 9: Example with Trivial Optimum Consider the following LP maximization problem, where the objective function z does not grow as its arguments x and x get further away from the origin: 1 2Solving Linear Programs Graphically 19 2.2.3 Example. maxz = 4x 3x 1 2 s:t: 2x + 3x  6 (1) 1 2 3x + 2x  3 (2) 1 2 2x  5 (3) 2 2x + x  4 (4) 1 2 x ;x  0 (5) 1 2 In this case drawing a graph would be an utter waste of time. Indeed, consider the objective function under maximization: z = 4x 3x 1 2 Obviously, given the standard constraints x ;x  0, the optimal solution is 1 2 x = 0; 1 x = 0; 2 z = 0: Whenever you have formulated a problem like this you (or your boss) must have done something wrong Example with Unbounded Feasible Region 2.2.4 Example. maxz = 4x + 3x 1 2 s:t: 3x + 2x  3 (1) 1 2 x ;x  0 (2) 1 2 From the picture below one sees that this LP has unbounded optimum, i.e., the value of objective function z can be made as big as one wishes.