with GNU Linear Programming Kit - Vaasan yliopisto

1 ORMS 1020 operations Researchwith GNU Linear Programming KitTommi tsottine/orms1020 August 27, 2009 ContentsI Introduction51 On operations What is operations research .. History of operations research * .. Phases of operations research Study .. 102 On Linear Example towards Linear Programming .. Solving Linear Programs Graphically .. 153 Linear Programming with GNU Linear Programming Overview of GNU Linear Programming Kit .. Getting and Installing GNU Linear Programming Kit .. Usingglpsolwith GNU MathProg .. Advanced MathProg andglpsol* .. 32II Theory of Linear Programming394 Linear Algebra and Linear Matrix Algebra .. Solving Linear Systems .. Matrices as Linear Functions* .. 505 Linear Programs and Their Form of Linear Program .. Location of Linear Programs Optima .. Karush Kuhn Tucker Conditions* .. Proofs* .. 65 CONTENTS26 Simplex Towards Simplex Algorithm .. Simplex Algorithm.

2 757 More on Simplex Big M Algorithm .. Simplex Algorithm with Non-Unique Optima .. Simplex/Big M Checklist .. 1028 Sensitivity and Sensitivity Analysis .. Dual Problem .. Primal and Dual Sensitivity .. 136 III Applications of Linear Programming1379 Data Envelopment Graphical introduction to Data Envelopment Analysis .. Charnes Cooper Rhodes Model .. Charnes Cooper Rhodes Model s Dual .. Strengths and Weaknesses of Data Envelopment Analysis .. 16710 Transportation Transportation Algorithm .. Assignment Problem .. Transshipment Problem .. 184IV Non- Linear Programming19011 Integer Integer Programming Terminology .. Branch-And-Bound Method .. Solving Integer Programs with GNU Linear Programming Kit . 199 PrefaceThese lecture notes are for the course ORMS1020 operations research forfall2009in the University of Vaasa. The notes are a slightly modified versionof the notes for the fall2008course ORMS1020in the University of chapters, or sections of chapters, marked with an asterisk (*) may beomitted or left for the students to read on their own time if time is author wishes to acknowledge that these lecture notes are collectedfrom the references listed in Bibliography, and from many other sources theauthor has author claims no originality, and hopes not to besued for plagiarizing or for violating the sacredc August 27, 2009T.

3 [1] Rodrigo Ceron:The GNU Linear Programming Kit, Part 1: Introductionto Linear optimization, Web Notes, [2] Matti Operaatioanalyysi, Lecture Notes, mla/orms1020 [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, IIntroductionChapter 1On operations ResearchThis chapter is adapted from Wikipedia articleOperations Researchand [4,Ch. 1]. What is operations ResearchDefinitionsTo define anything non-trivial like beauty or mathematics is very difficultindeed. Here is a reasonably good definition of operations research (OR) is an interdisciplinary branch ofapplied mathematics and formal science that uses methods like mathemati-cal modeling, statistics, and algorithms to arrive at optimal or near optimalsolutions to complex is problematic: to grasp it we already have to know, ,what is formal science or near a practical point of view, OR can be defined as an art of optimization, , an art of finding minima or maxima of some objective function, and tosome extend an art of defining the objective functions.

4 Typical objectivefunctions are profit, assembly line performance, crop yield, bandwidth, loss, waiting time in queue, an organizational point of view, OR is something that helps manage-ment achieve its goals using the scientific is operations Research7 The terms OR and Management Science (MS) are often used a distinction is drawn, management science generally implies a closerrelationship to Business Management. OR also closely relates to IndustrialEngineering. Industrial engineering takes more of an engineering point of view,and industrial engineers typically consider OR techniques to be a major partof their tool set. Recently, the term Decision Science (DS) has also be coinedto information on OR can be found from the INFORMS web (If OR is the Science of Better the OR ists should have figured out a bettername for it.)OR ToolsSome of the primary tools used in OR are statistics, optimization, probability theory, queuing theory, game theory, graph theory, decision analysis, of the computational nature of these fields, OR also has ties to com-puter science, and operations researchers regularly use custom-written this course we will concentrate on optimization, especially Linear Motto and Linear ProgrammingThe most common OR tool is Linear Optimization, or Linear Programming (LP).

5 Programming in Linear Programming is synonym for optimization . It has at least historically nothing to do with 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: perfectfor nothing, but good enough for , almost no real-world problem is really a Linear one thus LP is perfect for nothing. However, most real-world problems are closeenough to Linear problems thus LP is good enough for everything. below elaborates this Quine sells gavagais. He will sell one gavagaifor10 Euros. So, one might expect that buyingxgavagais from would cost according to the Linear rule Linear rule in Example may well hold for buying2,3, or5, oreven50gavagais. But: One may get a discount if one buys500gavagais. There are only1,000,000gavagais in the world. So, the price for1,000,001gavagais is+.

6 The unit price of gavagais may go up as they become scarce. So, buying950,000gavagais might be considerably more expensive than=C9,500,000. It might be pretty hard to , since half a gavagai is nolonger a gavagai (gavagais are bought for pets, and not for food). Buying 10gavagais is in principle all right. That would simply meanselling10gavagais. However, Mr. Quine would most likely not buygavagais with the same price he is selling may think of a curve that would represent the price ofgavagais better than the Linear straight line or you may even think as aradical philosopher and argue that there is no the problems and limitations mentioned above, lineartools are widely used in OR according to the following motto that should as all mottoes be taken with a grain of salt:OR s better to be quantitative and na ve than qualitative and History of operations research *This section is most likely omitted in the lectures. Nevertheless, you shouldread it history gives perspective, and thinking is nothing but an exercise of operations research *9 PrehistorySome say that Charles Babbage (1791 1871) who is arguably the father ofcomputers is also the father of operations research because his researchinto the cost of transportation and sorting of mail led to England s universal Penny Post in During World War IIThe modern field of OR arose during World War II.

7 Scientists in the UnitedKingdom including Patrick Blackett, Cecil Gordon, C. H. Waddington, OwenWansbrough-Jones and Frank Yates, and in the United States with GeorgeDantzig looked for ways to make better decisions in such areas as logistics andtraining are examples of OR studies done during World War II: Britain introduced the convoy system to reduce shipping losses, but whilethe principle of using warships to accompany merchant ships was gen-erally accepted, it was unclear whether it was better for convoys to besmall or large. Convoys travel at the speed of the slowest member, sosmall convoys can travel faster. It was also argued that small convoyswould be harder for German U-boats to detect. On the other hand, largeconvoys could deploy more warships against an attacker. It turned outin OR analysis that the losses suffered by convoys depended largely onthe number of escort vessels present, rather than on the overall size ofthe convoy. The conclusion, therefore, was that a few large convoys aremore defensible than many small ones.

8 In another OR study a survey carried out by RAF Bomber Commandwas analyzed. For the survey, Bomber Command inspected all bombersreturning from bombing raids over Germany over a particular damage inflicted by German air defenses was noted and the recom-mendation was given that armor be added in the most heavily damagedareas. OR team instead made the surprising and counter-intuitive recom-mendation that the armor be placed in the areas which were completelyuntouched by damage. They reasoned that the survey was biased, sinceit only included aircraft that successfully came back from Germany. Theuntouched areas were probably vital areas, which, if hit, would result inthe loss of the aircraft. When the Germans organized their air defenses into the KammhuberLine, it was realized that if the RAF bombers were to fly in a bomberstream they could overwhelm the night fighters who flew in individualcells directed to their targets by ground controllers. It was then a matterof calculating the statistical loss from collisions against the statisticalPhases of operations research Study10loss from night fighters to calculate how close the bombers should fly tominimize RAF Phases of operations research StudySeven Steps of OR StudyAn OR project can be split in the following seven steps:Step 1: Formulate the problemThe OR analyst first defines the organi-zation s problem.

9 This includes specifying the organization s objectivesand the parts of the organization (or system) that must be studied beforethe problem can be 2: Observe the systemNext, the OR analyst collects data to esti-mate the values of the parameters that affect the organization s estimates are used to develop (in Step 3) and to evaluate (in Step4) a mathematical model of the organization s 3: Formulate a mathematical model of the problemThe OR an-alyst develops an idealized representation a mathematical model of the 4: Verify the model and use it for predictionThe OR analysttries to determine if the mathematical model developed in Step 3 is anaccurate representation of the reality. The verification typically includesobserving the system to check if the parameters are correct. If the modeldoes not represent the reality well enough then the OR analyst goesback either to Step 3 or Step 5: Select a suitable alternativeGiven a model and a set of alterna-tives, the analyst now chooses the alternative that best meets the or-ganization s objectives.

10 Sometimes there are many best alternatives, inwhich case the OR analyst should present them all to the organization sdecision-makers, or ask for more objectives or 6: Present the results and conclusionsThe OR analyst presentsthe model and recommendations from Step 5 to the organization sdecision-makers. At this point the OR analyst may find that the decision-makers do not approve of the recommendations. This may result fromincorrect definition of the organization s problems or decision-makersmay disagree with the parameters or the mathematical model. The ORanalyst goes back to Step 1, Step 2, or Step 3, depending on where thedisagreement of operations research Study11 Step 7: Implement and evaluate recommendationFinally, when theorganization has accepted the study, the OR analyst helps in implement-ing the recommendations. The system must be constantly monitoredand updated dynamically as the environment changes. This means goingback to Step 1, Step 2, or Step 3, from time to this course we shall concentrate on Step 3 and Step 5, , we shallconcentrate on mathematical modeling and finding the optimum of a math-ematical model.