1

Km. 16, Lokoja Ajaokuta Road, P.M.B 1060, Lokoja, Kogi State, Nigeria


COLLEGE OF INFORMATION and COMMUNICATION TECHNOLOGY
DEPARTMENT OF MATHEMATICS/COMPUTER SCIENCE

B.SC. COMPUTER SCIENCE PROGRAMME

LECTURE NOTES: OPERATION RESEARCH (CSC 313)
SEMESTER: Alpha 2011/2012

Instructor: dr. Akindele michael okedoye
Phone: 08122206784, 08035688453, 08073949577
mail: mcindex@yahoo.com

Office Hours: Visiting Staff Office, New College Building,
Mon. 3:00PM 4:00 PM
Tue. 12:00AM 4:00 PM
Wed. 10:00AM - 12.00noon
And as always, by appointment.

Class Time and Location:
Tue. 10:00 12.00 Noon
Wed. 8:00 - 10:00AM

Textbook:
- 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/.
- Matti Laaksonen: TMA.101 Operaatioanalyysi, Lecture Notes, 2005.
http://lipas.uwasa.fi/_mla/orms1020/oa.html.
- Hamdy Taha: Operations Research: An Introduction (6th Edition), Prentice Hall, Inc,
1997.
- Wayne Winston: Operations Research: Applications and Algorithms, PSW Publishers,
1987.

Course Description: The notes are organized in 11 lectures. One lecture means or is
intended to mean a standard lecture session of 2x45 minutes. It may well turn out that
there is not enough time to go through all the 11 lectures-in-notes in 18 lectures-in-real-time:
Some of the lectures-in-notes may take more than one lecture-in-real-time.
The lectures, or sections of lectures, marked with an asterisk (*) may be omitted or left for
the students to read on their own time if time is scarce. The lectures, or sections of
lectures, marked with a double-asterisk (**) are advanced. They will most likely be
completely omitted in the course. Markings * and ** are recursive: If, say, lecture X is *, then
all its sections X.1, X.2, and so forth are * also, even if they were not marked such
explicitly.

The curious student should read the ** sections at her/his own risk!

University
Salem

2


Prerequisite: some mathematical maturity and an understanding of the basic concepts of
elementary Mathematics and Linear Algebra


Topics:
The nature of operations research, allocation problems, inventory problems, replacement,
maintenance and reliability problems. Dynamics programming, sequencing and co-ordination.
Simplex method. Graphical method of solution. Techniques of operations research viz linear
programming, dynamic programming, quadratic programming etc. Application software for solving
operations research problems e.g. CPLEX solver. Formulation of real-life problems as linear
programming problems.

Rules:
There may be one or two exams, including a final. Exams may be take-home or in-class. Homework
problems will be assigned, but only specifically designated assignments will be graded. Students are
allowed to "consult" (to be defined in class) on homework problems, but not on take-home exams.
Course grades will be based on the exams and the graded home works.

Course Objectives:
The successful student will:
1) exhibit a proficiency in the topics covered in the course;
2) engage in critical thinking and problem solving; and
3) translate, analyze information, formulate appropriate mathematical statements, solve problems
and interpret solutions.

Course Grade: Your final letter grade will be based on the usual grading scale:
A 70-100%, B 60-69%, C 50-59%, D 45-49%, E 40 44%, F < 40

The following items will make up the course grade:
Homework: 20 points
Exam1 (November 16) 10 points
Exam2 (December 14): 10 points
Final Exam (?): 60 points

Homework: Homework will be due by 4pm the day after it is assigned. Homework not turned in at
this time will be considered late. You may turn in homework up to one week after it is assigned for
half credit. If all homework is turned in, and no more than three are late, the lowest regular exam
score will be dropped.

Exams: According to the University regulation.

Registration Information: As required by the School management.

How to Succeed in a Class: I am often asked how to successfully pass a math class, and here is my
advice:
i) Come to every class session. Be prepared, and plan on participating.
ii) Do your homework. Remember that what I assign is what I consider a bare minimum. If you
need more practice, do it.
iii) Read the book. You paid good money for it, so you might as well use it.
iv) Do math every day. Math is just like everything else: if you dont practice, you become rusty.

3

Learning Disabled Students: It is important that students who are identified as being learning
disabled speak to me about their special needs. I am more than willing to grant you reasonable
accommodations.
Academic Dishonesty: Academic dishonesty of any form will not be tolerated. Students caught
cheating on exams or quizzes will be dealt with according to the school regulation. Students may
work together on homework assignments (and, in fact, are encouraged to) as long as all students
understand the material covered.
Final Notes:
Here are my notes for Queuing System course. Despite the fact that these are my class notes they
should be accessible to anyone wanting to learn the rudiment of Queuing theory or needing a
refresher stochastic process. Ive tried to make these notes as self contained as possible and so all
the information needed to read through them is either from a Probability theory or Operations
Research or contained in other sections of the notes.

Warnings to my students who may be here to get a copy of what happened on a day that you
missed.
THESE NOTES ARE NOT A SUBSTITUTE FOR ATTENDING CLASS!! Using these notes as a substitute
for class is liable to get you in trouble. As already noted not everything in these notes is covered in
class and often material or insights not in these notes is covered in class.

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 laws.

Salem October 15, 2011 A. M. O.




4

Part I
Introduction
Lecture 1
On Operations Research
This lecture is adapted from Wikipedia article Operations Research and [4, Ch. 1].

1.1 What is Operations Research

Definitions

To define anything non-triviallike beauty or mathematicsis 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 mathematical 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 management achieve its goals
using the scientific process.1

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 ORists should have figured
out a better name for it.)

Overview
Operational research (OR) encompasses a wide range of problem-solving techniques and
methods applied in the pursuit of improved decision-making and efficiency.
[2]
Some of the
tools used by operational researchers are statistics, optimization, probability theory, queuing
theory, game theory, graph theory, decision analysis, mathematical modeling and simulation.
Because of the computational nature of these fields, OR also has strong ties to computer
science and analytics. Operational researchers faced with a new problem must determine

5

which of these techniques are most appropriate given the nature of the system, the goals for
improvement, and constraints on time and computing power.
Work in operational research and management science may be characterized as one of three
categories:
- Fundamental or foundational work takes place in three mathematical disciplines: probability
theory, mathematical optimization, and dynamical systems theory.
- Modeling work is concerned with the construction of models, analyzing them
mathematically, implementing them on computers, solving them using software tools, and
assessing their effectiveness with data. This level is mainly instrumental, and driven mainly
by statistics and econometrics.
- Application work in operational research, like other engineering and economics' disciplines,
attempts to use models to make a practical impact on real-world problems.

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 computer science, and
operations researchers regularly use custom-written software.
In this course we will concentrate on optimization, especially linear optimization.

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 ORists favourite tool because it is
- simple,
- easy to understand,
- robust.
Simple means easy to implement, easy to understand means easy to explain (to you boss), and
robust means that its 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. Ajanlekoko sells Indomie. He will sell one Indomie for # 10. So, one might expect
that buying x Indomie from Mr. Ajanlekoko would cost according to the linear rule # 10x.


6

The linear rule in Example 1.1.3 may well hold for buying 2, 3, or 5, or even 50 Indomie. But:
- One may get a discount if one buys 500 Indomie.
- There are only 1,000,000 Indomie in the world. So, the price for 1,000,001 Indomie is +.
- The unit price of Indomie may go up as they become scarce. So, buying 950,000 Indomie
might be considerably more expensive than #9,500,000.
- It might be pretty hard to buy 0.5 Indomie, since half a gavagai is no longer a Indomie
(Indomie are bought in sachets).
- Buying -10 Indomie is in principle all right. That would simply mean selling 10 Indomie.
However, Mr. Ajanlekoko would most likely not buy Indomie with the same price he is selling
them.

1.1.4 Remark. You may think of a curve that would represent the price of Indomie 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. Its better to be quantitative and nave than qualitative and profound.

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.

Prehistory
Some say that Charles Babbage (17911871) 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 Englands 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 generally 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 recommendation was given that armor be added in the most heavily damaged

7

areas. OR team instead made the surprising and counter-intuitive recommendation 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 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 organizations problem. This includes
specifying the organizations 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 estimate the values of the
parameters that affect the organizations problem. These estimates are used to develop (in Step
3) and to evaluate (in Step 4) a mathematical model of the organizations problem.

Step 3: Formulate a mathematical model of the problem The OR analyst 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 alternatives, the analyst now chooses
the alternative that best meets the organizations objectives. Sometimes there are many best
alternatives, in which case the OR analyst should present them all to the organizations
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 organizations decision-makers. At this point the OR analyst
may find that the decision-makers do not approve of the recommendations. This may result from
incorrect definition of the organizations 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.

Step 7: Implement and evaluate recommendation Finally, when the organization has accepted the
study, the OR analyst helps in implementing 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.


8

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 mathematical 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 ORist 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 objectives 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.

Step 1: The OR analyst describes banks objectives. The managers vaguely 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 banks operations that affect the achievement of
the banks 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?
- 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

=
q
W Average time customer waits in line
= 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)
) (

=
q
W
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
q
W , , 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.

9

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
q
W small enough, e.g. 3 minutes.
We shall leave it to the students to wonder what may happen in steps 6 and 7.

Problems addressed with operational research
- critical path analysis or project planning: identifying those processes in a complex project
which affect the overall duration of the project
- floorplanning: designing the layout of equipment in a factory or components on a computer
chip to reduce manufacturing time (therefore reducing cost)
- network optimization: for instance, setup of telecommunications networks to maintain
quality of service during outages
- Allocation problems
- Facility location
- Assignment Problems:
o Assignment problem
o Generalized assignment problem
o Quadratic assignment problem
o Weapon target assignment problem
- Bayesian search theory : looking for a target
- optimal search
- routing, such as determining the routes of buses so that as few buses are needed as possible
- supply chain management: managing the flow of raw materials and products based on
uncertain demand for the finished products
- efficient messaging and customer response tactics
- automation: automating or integrating robotic systems in human-driven operations
processes
- globalization: globalizing operations processes in order to take advantage of cheaper
materials, labor, land or other productivity inputs
- transportation: managing freight transportation and delivery systems (Examples: LTL
Shipping, intermodal freight transport)
- scheduling:
o personnel staffing
o manufacturing steps
o project tasks
o network data traffic: these are known as queueing models or queueing systems.
o sports events and their television coverage
- blending of raw materials in oil refineries
- determining optimal prices, in many retail and B2B settings, within the disciplines of pricing
science
Operational research is also used extensively in government where evidence-based policy is
used.
The Nature of Operations Research part 1
Nature of Operations Research. As its name implies, operations research involves research
on operations. Thus, operations research is applied to problems that concern how to conduct

10

and coordinate the operations (i.e., the activities) within an organization. The nature of the
organization is essentially immaterial, and, in fact, OR has been applied extensively in such
diverse areas as manufacturing, transportation, construction, telecommunications, financial
planning, health care, the military, and public services, to name just a few. Therefore, the
breadth of application is unusually wide.
The research part of the name means that operations research uses an approach that
resembles the way research is conducted in established scientific fields. To a considerable
extent, the scientific method is used to investigate the problem of concern. (In fact, the term
management science sometimes is used as a synonym for operations research.) In particular,
the process begins by carefully observing and formulating the problem, including gathering
all relevant data. The next step is to construct a scientific (typically mathematical) model that
attempts to abstract the essence of the real problem. It is then hypothesized that this model is
a sufficiently precise representation of the essential features of the situation that the
conclusions (solutions) obtained from the model are alsovalid for the real problem. Next,
suitable experiments are conducted to test this hypothesis, modify it as needed, and
eventually verify some form of the hypothesis. (This step is frequently referred to as model
validation.) Thus, in a certain sense, operations research involves creative scientific research
into the fundamental properties of operations. However, there is more to it than this.
Specifically, OR is also concerned with the practical management of the organization.
Therefore, to be successful, OR must also provide positive, understandable conclusions to the
decision maker(s) when they are needed.

The Nature of operations research part 2
The Nature of operational research part 2. Still another characteristic of OR is its broad
viewpoint. As implied in the preceding section, OR adopts an organizational point of view.
Thus, it attempts to resolve the conflicts of interest among the components of the
organization in a way that is best for the organization as a whole. This does not imply that the
study of each problem must give explicit consideration to all aspects of the organization;
rather, the objectives being sought must be consistent with those of the overall organization.
An additional characteristic is that OR frequently attempts to find a best solution (referred to
as an optimal solution) for the problem under consideration. (We say a best instead of the
best solution because there may be multiple solutions tied as best.) Rather than simply
improving the status quo, the goal is to identify a best possible course of action. Although it
must be interpreted carefully in terms of the practical needs of management, this search for
optimality is an important theme in OR.

The origins of operation research 1
The origins of operation research. Since the advent of the industrial revolution, the world has
seen a remarkable growth in the size and complexity of organizations. The artisans small
shops of an earlier era have volved into the billion-dollar corporations of today. An integral
part of this revolutionary change has been a tremendous increase in the division of labor and

11

segmentation of management responsibilities in these organizations. The results have been
spectacular. However, along with its blessings, this increasing specialization has created new
problems, problems that are still occurring in many organizations. One problem is a
tendencfor the many components of an organization to grow into relatively autonomous
empires with their own goals and value systems, there by losing sight of how their activities
and objectives mesh with those of the overall organization. What is best for one component
frequently is detrimental to another, so the components may end up working at cross
purposes. A related problem is that as the complexity and specialization in an organization
increase, it becomes more and more difficult to allocate the available resources to the various
activities in a way that is most effective for the organization as a whole. These kinds of
problems and the need to find a better way to solve them provided the environment for the
emergence of operations research (commonly referred to as OR).



12

Lecture 2

On Linear Programming

2.1 Example towards Linear Programming

Very Nave Problem

2.1.1 Example. Tela Inc. manufactures two products: N1 and N2. To manufacture
one unit of product N1 costs #40 and to manufacture one unit of product N2 costs
#60. The profit from product N1 is #30, and the profit from product N2 is #20.

The company wants to maximize its profit. How many products N1 and N2 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 N1 or N2, or both. If there is a constraint on
the number of units manufactured then the company should manufacture only product N1, and not
product N2. This constrained case is still rather trivial.

Less Nave Problem

Things become more interesting and certainly more realistic when there are restrictions in the
resources.

2.1.2 Example. Tela Inc. in Example 2.1.1 can invest #40, 000 in productions and use
85 hours of labor. To manufacture one unit of product N1 requires 15 minutes of
labor, and to manufacture one unit of product N2 requires 9 minutes of labor.

The company wants to maximize its profit. How many units of product N1 and
product N2 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 the entire #40,000 in product N1.
Since the profit to be maximized depends on the number of product N1 and N2, our decision
variables are:


1
x = number of product N1 produced,

2
x = number of product N2 produced.

So the situation is: We want to maximize (max)
profit: 30
1
x + 20
2
x
subject to (s.t.) the constraints
money: 40
1
x + 60
2
x 40,000
labor: 15
1
x + 9
2
x 5,100
non-negativity:
1
x ,
2
x 0
Note the last constraint:
1
x ,
2
x 0. The problem does not state this explicitly, but its implied we
are selling products N1 and N2, not buying them.

13

2.1.3 Remark. Some terminology: The unknowns
1
x and
2
x are called decision variables. The
function 30x1 + 20x2 to be maximized is called the objective function.

What we have now is a Linear Program (LP), or a Linear Optimization problem,
max z = 30
1
x + 20
2
x
s.t. 40
1
x + 60
2
x 40,000
15
1
x + 9
2
x 5,100

1
x ,
2
x 0
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 N1 and thus put all the resource to product N2 which
means producing 566.667 number of products N2. The profit will then be #11,333.333. In other
words, the optimal solution is


1
x = 0

2
x = 566.667,
z = 11,333.333.

2.1.4 Remark. If it is not possible to manufacture fractional number of products, e.g. 0.667 units,
then we have to reformulate the LP-problem above to an Integer Program (IP)
max z = 30
1
x + 20
2
x
s.t. 40
1
x + 60
2
x 40,000
15
1
x + 9
2
x 5,100

1
x ,
2
x 0

1
x ,
2
x are integers
We will later see how to solve such IPs (which is more difficult than solving LPs). For now we just
show the solution:

1
x = 1,

2
x = 565,
z = 11,330.

In Remark 2.1.4 above we see the usefulness of the OR Motto. Indeed, although 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.

2.2 Solving Linear Programs Graphically

From Minimization to Maximization**
We shall discuss later in latter lectures, 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 maximization problem simply
by multiplying the objective function by -1:
2.2.1 Theorem. Let ,
n
K 9 c and let . : 9 9
n
g Suppose
) ( min x g w
K xe
-
=

14

and
n
x 9 e
-
is a point where the minimum
-
w is attained. Then, if g f = and
-
= w z , we have
that
) ( min x f z
K xe
-
=
and the maximum
-
z is attained at the point
n
x 9 e
-
.
The mathematically oriented should try to prove Theorem 2.2.1. Its not difficult all you have
to do is to not to think about the constraint-set K or any other specifics, like the space Rn , 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.
max z =4
1
x + 3
2
x
s.t. 2
1
x + 3
2
x 6 (1)
-3
1
x + 2
2
x 3 (2)
2
2
x 5 (3)
2
1
x +
2
x 4 (4)

1
x ,
2
x 0 (5)

The LP in Example 2.2.2 has only two decision variables:
1
x and
2
x . So, it 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 x1 is the horizontal axis and
2
x is the vertical axis.
Because of the non-negativity constraints on
1
x and
2
x it is enough to draw the 1st quadrant
(the NE-quadrant).

Step 2: Draw constraint-lines Each constraint consists of a line and of information (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
2
1
x + 3
2
x = 6:
To draw this line we can first set
1
x = 0 and then set
2
x = 0, and we 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 This is done by selecting the region satisfied 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 (
1
x ,
2
x ) satisfying
z = 4
1
x + 3
2
x = const:
(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

15

objective function, cf. Example 2.2.3 later). You find the best value when the isoprofit 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).

























From the picture we read by moving the isoprofit line away from the origin that the
optimal point for the decision variables (
1
x ,
2
x ) is
C = (1.5, 1):
Therefore, the optimal value is of the objective is
9 1 3 5 . 1 4 = + = z .

Example with Trivial Optimum
Consider the following LP maximization problem, where the objective function z does not grow as
its arguments
1
x and
2
x get further away from the origin:

2.2.3 Example.
max z = -4
1
x - 3
2
x
s.t. 2
1
x + 3
2
x 6 (1)
-3
1
x + 2
2
x 3 (2)
2
2
x 5 (3)
2
1
x +
2
x 4 (4)

1
x ,
2
x 0 (5)

In this case drawing a graph would be an utter waste of time. Indeed, consider the objective
function under maximization:
z = -4
1
x - 3
2
x
Feasible region
Isoprofit lines
(4)
(3)
(2)
(1)
A
B
C
E
D
4
3
2
1
4 3
2
1
Redundant
Optimum
1
x
2
x


16

Obviously, given the standard constraints
1
x ,
2
x 0, the optimal solution is

1
x = 0,

2
x = 0,
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.
max z = 4
1
x + 3
2
x
s.t. -3
1
x + 2
2
x 3 (1)

1
x ,
2
x 0 (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.


Whenever you have formulated a problem like this you (or your boss) must have done something
wrong or you must be running a sweet business, indeed!