(EE3006/3006A)
Unit 5. Linear and Integer Programming
1. Introduction
• Operation research
• Mathematical programming
2. Linear Programming
• Basic concepts
• Graphical method of LPs
• Some special cases of LPs
(EE3006/3006A)
1. Introduction
What is Operation Research?
• Operations
The activities carried out in an organization.
• Research
The process of testing and observation by using scientific methods,
such as problem statement, model construction, validation,
experimentations, candidate solutions.
• Operation Research
=> Concern with the efficient allocation of scarce resources;
=> The derivation of computational methods for solving the well-
defined model of a given situation or problem.
1
(EE3006/3006A)
1.1 Operation Research
Example: Optimizing harbor operations
• Containers are transported
between vessels and storage areas
by e.g., automated guided vehicles
(AGVs).
• Compute AGV routes that are
free of conflicts and jams.
• Objective is to minimize vessels
waiting time so as to maximize
Picture of Hong Kong Harbor container throughput.
(EE3006/3006A)
1.2 Mathematical Programming
Optimization problem
=> Seeks to maximize or minimize a specific quantity, called the
objective, which depends on a finite number of input variables. These
variables are related through one or more constraints.
Example: The problem
minimize: z = x12+x22
subject to: x1-x2=3,
x2 ≥ 2.
is an optimization problem for the objective z.
It is desired to find the values of the input variables which minimize the
sum of the limitations imposed by the constraints.
3
2
(EE3006/3006A)
Mathematical programming
=> An optimization problem whose objective and constraints are given
by using mathematical functions and functional relationship.
optimize: z = f (x1, x2, …, xn)
subject to: g1(x1, x2, …, xn) b1
g2(x1, x2, …, xn) ≤ b2
……………….. …
=
≥
gm(x1, x2, …, xn) bm
Unconstrained mathematical programs are covered if each function gi
is chosen as zero and each constant bi is chosen as zero.
4
(EE3006/3006A)
Problem formulation
Step 1:
Determine the quantity to be optimized and express it as a mathematical
function. Doing so serves to define the input variables and the objective;
Step 2:
Identify all stipulated requirements, restrictions and limitations and
express them mathematically. These requirements constitute the
constraints;
Step 3:
Express any hidden conditions. Such conditions are not stipulated explicitly
in the problem but are apparent from the physical situation being modeled.
Generally, they involve non-negativity or integer requirements on the input
variable;
3
(EE3006/3006A)
Classification of mathematical programs
Integer Programs (IP)
Linear Programs (LP) if the input variables xi are integers.
if f(.) and each gi(.) are linear:
f(x1, x2,…,xm)=c1x1+c2x2+… cnxn (…)
gi(x1, x2,…,xm)=ai1x1+ai2x2+… ainxn
Quadratic Programs (QP)
Each constraint is linear, but the
objective is of the form:
Nonlinear Programs (NLP) f ( x1,... ..., xm ) i 1 j 1 cij xi x j i 1 d i xi
n n n
(…)
(EE3006/3006A)
Comparison of mathematical programs
LP IP NLP
Continuous Discrete Continuous or
Variables (e.g., 0 x1) (e.g., x=0 or 1) Discrete
Linear Linear Nonlinear/Linear
Constraints (e.g., 3x+2y 7) (e.g., 4x-y 5) (e.g.,14x2 y3 3)
Linear Linear Nonlinear
Objective (e.g., maximize (e.g., maximize (e.g., maximize
2x+5y) –3x-2y) 17xy)
4
(EE3006/3006A)
2. Linear Programming
2.1 Basic Concepts
optimize: z = f (x1, x2, …, xn)
n
subject to: a xj
j 1 1 j b1
≤
n
j 1
a2 j x j b2
=
…………. …
≥
n
j 1
amj x j bm
Decision variables: Variables that represent the decision that can be made.
Objective function: Each optimization problem is trying to optimize
(maximize/minimize) some goal such as costs, profits, revenue.
Constraints: A set of real restricting parameters that are imposed in real life or by
the structure of the problem.
8
(EE3006/3006A)
Assumptions of LPs:
– Linearity implies that the objective function and all of the
constraints are in linear relationship.
( Proportionality and additivity are consequences of the linear
assumption. )
– Nonnegativity simply means that all decision variables must take
positive or zero values.
– Divisibility means that the optimal values of decision variables may
be fractional depending upon the application.
– Certainty requires that the parameters of LP model are known or
can be accurately estimates.
5
(EE3006/3006A)
Slack variables
̶ A linear constraint of the form j 1 aij x j bi can be converted into an
n
equality by adding a new nonnegative variable to the left-hand side of
the inequality. Such a variable is known as slack variable.
̶ Slack variable equals to the difference between the right and left-hand
sides of the inequality constraint.
10
(EE3006/3006A)
Surplus variables
̶ A linear constraint of the form j 1 aij x j bi can be converted into an
n
equality by subtracting a new nonnegative variable to the left-hand side
of the inequality. Such a variable is known as surplus variable.
̶ Surplus variable equals to the difference between the right and left-hand
sides of the inequality constraint.
11
6
(EE3006/3006A)
2.2 Graphical Method of Linear Programs
Solution procedure:
1) Prepare a graph of the feasible solutions for each of the constraints;
2) Determine the feasible region that satisfies all the constraints
simultaneously;
（Feasible region: the set of all points that satisfy all the constraints of the model. ）
3) Draw an objective function line;
4) Move parallelly objective function lines toward larger/smaller
objective function values without entirely leaving the feasible region;
5) Any feasible solution on the objective function line with the
largest/smallest value is an optimal solution.
12
(EE3006/3006A)
Example 1:
A furniture maker has 6 units of wood and 28 h of free time, in which he
will make decorative screens. Two models have been sold well in the
past, so he will restrict himself to those two. He estimates that model-I
requires 2 units of wood and 7 h of time, whereas mode-II requires 1 unit
of wood and 8 h of time. The prices of the two models are $120 and $80,
respectively. How many screens of each model should the furniture
maker assemble if he wishes to maximize his sales revenue?
• Decision variables:
– x1 = the number of model-I screens to be produced
– x2 = the number of model-II screens to be produced
• Objective function:
– sales revenue, z=120x1+80x2, to be maximized
13
7
(EE3006/3006A)
Further combining the wood and time constraints, one can obtain the
mathematical program:
maximize: z = 120x1+80x2
subject to: 2x1 + x2 ≤ 6
7x1 + 8x2 ≤ 28
and all variables are nonnegative and integers.
Integer Program
14
(EE3006/3006A)
x2
The non-negativity constraint
x1
15
8
(EE3006/3006A)
X2
5 The wood constraint:
2x1+x2 ≤ 6
4
2 Infeasible
The time 1
Feasible
constraint :
7x1+8x2 ≤ 28 X1
1 2 3 4
16
(EE3006/3006A)
There are three types of feasible points:
x2
5
The wood constraint:
2x1+x2 ≤ 6
4
2 Infeasible
The time 1
constraint : Feasible
7x1+8x2 ≤ 28
1 2 3 4
x1
Interior points. Extreme points. Boundary points. 17
9
(EE3006/3006A)
objective: z = 120x1+80x2 => x2=-2x1/3+z/80
z = 391 x2
z = 360 5
z = 240
4
2 Infeasible
1 Feasible
1 2 3 4
x1
The maximum revenue is: z*=120×3+80×0=$360. 18
(EE3006/3006A)
* Example 2:
Use graphic method to solve a minimization problem:
minimize: z= 5x1 + 2x2
subject to: 2x1 + 5x2 > 10
4x1 - x2 > 12
x1 + x2 > 4
and all variables x1, x2 are nonnegative.
Linear Program
19
10
(EE3006/3006A)
Solution:
1) Graph the constraints:
x2 Feasible Region
6
5
4x1 - x2 > 12
4
x1 + x2 > 4
3
2 2x1 + 5x2 > 10
x1 20
1 2 3 4 5 6
(EE3006/3006A)
2) Graph the objective function, and move toward optimality
x2 x2 =-2.5x1 +0.5z
Min 5x1+2x2
6
5
4x1 - x2 > 12
4
x1 + x2 > 4
3
2 2x1 + 5x2 > 10
x1
1 2 3 4 5 6 21
11
(EE3006/3006A)
3) Optimal solution
x2
6
5
4x1 - x2 > 12
4 x1 + x2 > 4
3 Optimal Solution:
x1 = 16/5, x2 = 4/5,
2 5x1 + 2x2 = 17.6
1 2x1 + 5x2 > 10
x1
1 2 3 4 5 6 22
(EE3006/3006A)
2.3 Some Special Cases of Linear Programs
=> Four special cases and difficulties arise at times in linear
programming:
i) Redundant constraints
ii) Infeasibility
iii) Unboundness
iv) Alternate optimal solutions
23
12
(EE3006/3006A)
i. Redundant constraints
- a constraint that does not affect the feasible region
x2
30 –
25 –
2x1 + x2 ≤ 30
20 –
Redundant
constraint
15 –
x1 ≤ 25
10 –
x1 + x2 ≤ 20
5– Feasible
region
0– | | | | | | 24
5 10 15 20 25 30 x1
(EE3006/3006A)
ii. Infeasibility
– there is no feasible region
x2
8–
6–
Region satisfying
4– the third
constraint
2–
0– | | | | | | | | | |
2 4 6 8 x1
Region satisfying the first two constraints
25
13
(EE3006/3006A)
iii. Unboundness
– nothing prevents the solution from becoming infinitely large
x2
max : z=2x1 + 2x2
subject to: 2x1 + 3x2 > 6 2
x1, x2 > 0
0
0 1 2 3 x1
26
(EE3006/3006A)
iv. Alternate optimal solutions
– there are more than one optimal solutions
x2
10
max: z=2 x1 + 2x2
subject to: x1 + x2 < 10 All points on
x1 < 5 red segment are
x2 < 6 6
optimal
x1, x2 > 0
0
0 5 10 x1
27
14
(EE3006/3006A)
Tutorial:
t
Q1. Let f (t ) x sin (4 x) dx . Using the trapezoidal rule, find the approximation of f (1.2)-f (1.0) with 5
2 3
0
subintervals. (x is a radian; Round your answer to 4 decimal places.)
Q2. Starting from the guess value of x =1.2, apply the Newton-Raphson method for two iterations to find a
root of
f ( x) e-2 x sin(8x).
Q3. The van der Pol equation is a model of an electric circuit that arose back in the days of vacuum tubes:
d2y dy
- (1 - y 2 ) y 0
dt 2 dt
Given the initial conditions y=2.0 and dy/dt=1.5 when t=0, solve the equation from t=0 to 0.1 using the
fourth order Runge-Kutta method with the step size of 0.1. (Round your answer to 3 decimal places)
Q4. The Apex Television Company wants to decide the number of 27- and 20-inch TV sets to be produced at
one of its factories. Market research indicates that at most 40 of the 27-inch TV sets and 10 of the 20-
inch TV sets can be sold per month. The maximum number of work-hours available is 500 per month. A
27-inch TV set requires 20 work-hours and a 20-inch TV set requires 10 work-hours. Each 27-inch TV
set sold produces a profit of $120 and each 20-inch TV set produces a profit of $80. A wholesaler has
agreed to purchase all the television sets produced if the numbers do not exceed the maxima indicated by
the market research. Formulate a linear programming model for this problem, and then solve this model
using graphical method.
28
(EE3006/3006A)
Reference:
(R. Bronson and G. Naadimuthu,
Schaum's outline of theory and problems of Operations
Research, McGraw Hill, 1997)
1. Mathematical Programming, pp. 1 ~ 7.
2. Linear Programming: Basic Concepts, pp. 18 ~ 20.
29
15
