ORMS 1020
Operations Research
with GNU Linear Programming Kit
Tommi Sottinen
tommi.sottinen@uwasa.fi
www.uwasa.fi/tsottine/orms1020
August 27, 2009

---

Contents
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*
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65

---

CONTENTS
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 . 199

---

Preface
These lecture notes are for the course ORMS 1020 "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
Introduction

---

Chapter 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
The terms OR and Management Science (MS) are often used synonymously.
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 +.
* The unit price of gavagais may go up as they become scarce. So, buying
950,000 gavagais might be considerably more expensive than =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).
* Buying -10 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 naive 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 statistical

---

Document Outline

• I Introduction
  • On Operations Research
    • What is Operations Research
    • History of Operations Research*
    • Phases of Operations Research Study
  • On Linear Programming
    • Example towards Linear Programming
    • Solving Linear Programs Graphically
  • Linear Programming with GNU Linear Programming Kit
    • Overview of GNU Linear Programming Kit
    • Getting and Installing GNU Linear Programming Kit
    • Using glpsol with GNU MathProg
    • Advanced MathProg and glpsol*
• II Theory of Linear Programming
  • Linear Algebra and Linear Systems
    • Matrix Algebra
    • Solving Linear Systems
    • Matrices as Linear Functions*
  • Linear Programs and Their Optima
    • Form of Linear Program
    • Location of Linear Programs' Optima
    • Karush--Kuhn--Tucker Conditions*
    • Proofs*
  • Simplex Method
    • Towards Simplex Algorithm
    • Simplex Algorithm
  • More on Simplex Method
    • Big M Algorithm
    • Simplex Algorithm with Non-Unique Optima
    • Simplex/Big M Checklist
  • Sensitivity and Duality
    • Sensitivity Analysis
    • Dual Problem
    • Primal and Dual Sensitivity
• III Applications of Linear Programming
  • Data Envelopment Analysis
    • Graphical Introduction to Data Envelopment Analysis
    • Charnes--Cooper--Rhodes Model
    • Charnes--Cooper--Rhodes Model's Dual
    • Strengths and Weaknesses of Data Envelopment Analysis
  • Transportation Problems
    • Transportation Algorithm
    • Assignment Problem
    • Transshipment Problem
• IV Non-Linear Programming
  • Integer Programming
    • Integer Programming Terminology
    • Branch-And-Bound Method
    • Solving Integer Programs with GNU Linear Programming Kit

---