Chapter 3

Properties of Linear Programs

Prof. Hai Yang

Department of Civil and Environmental Engineering
HKUST

1
 Outline

• Linear programs
– General form of linear programs
– Standard form of linear programs
– Underlying assumptions of linear programs
• Properties of solutions of linear programs
– Computer solutions
– Graphical illustration of solutions
– Possibilities of feasible regions
– Algebraic meaning of linear programs
• Summary
2
 Linear Programs: An Illustrative Example –
Mixing Gravels to Produce Aggregate

Objective Function Decision Variables

Minimize 𝑍=0.20𝑥1 + 0.30𝑥2 + 0.45𝑥3 + 0.65𝑥4

Constraint Functions

Subject to: 𝑥1 +𝑥2 + 𝑥3 + 𝑥4 = 1000

0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 ≥ 480
0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 ≤ 550
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 ≥ 300
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 ≤ 350
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 ≥ 150
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 ≤ 200
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
3
 Linear Programs

• If both the objective functions and the constraint

functions are linear with respect to decision
variables, the problem is referred to as a linear
programming problem

• Linear constraints are linear functions that are

restricted to be “less than or equal to”, “equal to”,
or “greater than or equal to” a constant.

4
 General Form of Linear Programs(LP)

Objective Function Decision Variables

Maximize(Minimize) 𝑍=𝑐1 𝑥1 + ⋯ + 𝑐𝑛 𝑥𝑛
Constraint Functions

Subject to:
𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ (=, ≥)𝑏1
…
𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ (=, ≥)𝑏𝑚
Nonnegativity

𝑥1 , … , 𝑥𝑛 ≥ 0
5
 Definition of Standard Form of LP

• An LP is in standard
form when:
– All variables are
non-negative Minimize 𝑍=0.20𝑥1 + 0.30𝑥2 + 0.45𝑥3 + 0.65𝑥4
– All constraints are
equalities
Subject to: 𝑥1 +𝑥2 + 𝑥3 + 𝑥4 = 1000
0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 ≥ 480
0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 ≤ 550
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 ≥ 300
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 ≤ 350
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 ≥ 150
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 ≤ 200
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

6
 Conversion from General to Standard LPs

• Case I: “less than or equal 0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 ≤ 550

to” constraints
– Slack variables represent
the difference between the 0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 + 𝑠2 = 550
right-hand and left-hand
sides of the constraints s2  0

• Case II: “greater than or 0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 ≥ 300

equal to” constraints
– Surplus variables represent
the difference between the 0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 − 𝑠3 = 300
left-hand and right-hand
sides of the constraints s3  0

7
 Conversion from General to Standard LPs

All variables are non-negative

𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

If a variable, say 𝑥5 , is
𝑥5 , free
unrestricted variables
(unrestricted in sign), then two
non-negative variables are 𝑥5 = 𝑥6 − 𝑥7
introduced to avoid unrestricted 𝑥6 , 𝑥7 ≥ 0
variables

𝑥8 ≤ 0
If a variable, say 𝑥8 , is a
negative, then a non-negative
variable is instead introduced 𝑥9 = −𝑥8
𝑥9 ≥ 0

8
 Standard Form of Linear Programs

Objective Function Decision Variables

Maximize(Minimize) 𝑍=𝑐1 𝑥1 + ⋯ + 𝑐𝑛 𝑥𝑛
Constraint Functions

Subject to:
𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
…
𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚
Nonnegativity

𝑥1 , … , 𝑥𝑛 ≥ 0
9
 Example of Slack and Surplus Variables

Objective
Decision Variables
Function Surplus Variables

Minimize 𝑍=0.20𝑥1 + 0.30𝑥2 + 0.45𝑥3 + 0.65𝑥4 +

0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4 + 0𝑠5 + 0𝑠6
Subject to: 𝑥1 +𝑥2 + 𝑥3 + 𝑥4 = 1000
0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 − 𝑠1 = 480
0.35𝑥1 + 0.10𝑥2 + 0.60𝑥3 + 0.50𝑥4 + 𝑠2 = 550
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 − 𝑠3 = 300
0.30𝑥1 + 0.50𝑥2 + 0.30𝑥3 + 0.35𝑥4 + 𝑠4 = 350
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 − 𝑠5 = 150
0.35𝑥1 + 0.40𝑥2 + 0.10𝑥3 + 0.15𝑥4 + 𝑠6 = 200
Constraint Slack Variables
Functions 𝑥1 , … , 𝑥4 ≥ 0; 𝑠1 , … , 𝑠6 ≥ 0;
10
 Binding & Non-binding Constraints

• A constraint is binding at a point (e.g., the optimal

point), if the equality holds at that point.

• A constraint is non-binding at a point (e.g., the

optimal point), if the strict inequality holds at that
point.

11
Question: Why setting 0 coefficient for slack/surplus
variables in the objective function?

Answer: Setting the coefficient of for slack/surplus variable s to be zero,

because they are slack/surplus nonnegative variables and their values
may be positive (zero only when the corresponding constraints are
binding or taking equality). With zero coefficients, the objective function
values are not affected even when s takes a non-zero positive value.
Consider Consider
max 𝑍 = 2𝑥1 − 𝑥2 max 𝑍 = 2𝑥1 − 𝑥2 + 0𝑠1 + 0𝑠2
subject to 𝑥1 + 𝑥2 ≤ 10 subject to 𝑥1 + 𝑥2 + 𝑠1 = 10
𝑥1 + 2𝑥2 ≤ 15 𝑥1 + 2𝑥2 + 𝑠2 = 15
𝑥1 ≥ 0; 𝑥2 ≥ 0 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑠1 ≥ 0, 𝑠2 ≥ 0

Clearly, 𝑥1∗ = 10; 𝑥2∗ = 0; 𝑍 ∗ = 20 Clearly, 𝑥1∗ = 10; 𝑥2∗ = 0; 𝑠1∗ = 0; 𝑠2∗ = 5; 𝑍 ∗ = 20

Clearly, the constraint 𝑥1 + 2𝑥2 ≤ 15 is non-binding at optimum, 𝑠2∗ = 5 (a positive

value). We still have the same optimal solution 𝑥1∗ = 10; 𝑥2∗ = 0; 𝑍 ∗ = 20.

12
 Properties of Linear Programs:
Properties of Solutions of Linear Programs

13
 Properties of Solutions of Linear Programs
Computer Solution

• With the development of computational technology,

many software can solve linear programs, i.e., Matlab,
Excel solver, etc.

• Most large LP problems can be solved within minutes

using high-performance computer, even seconds if the
number of decision variables is small

14
 Properties of Solutions of Linear Programs
Illustration of Installing Microsoft Excel Add-ins

15
 Properties of Solutions of Linear Programs
An Illustrative Example – Mixing Gravels to Produce an Aggregate

• An aggregate mixture of a defined composition (ranges for

different materials) is needed for a construction project
Material Coarse Fine Sand
Name Material Material
Range 48%-55% 30%-35% 15-20%

• Two sources are available for the project with different

compositions
% Coarse % Fine % Sand Cost($/pound)
Source 1 35 30 35 0.20
Source 2 60 30 10 0.45

16
 Properties of Solutions of Linear Programs
Problem Statement

• Assume that the project

manager wants to order from
the two sources to make 1000 Source Source
pounds of the aggregate 1 2

• Also the project manager

wants to spend the least
1000
money to make the amount of pounds
aggregate aggregate

17
 Properties of Solutions of Linear Programs
System Analysis
• Decision Variables: amount of aggregate ordered from
two sources
– 𝑥𝑗 is the amount of aggregate from the j-th source
• Objective Function: the least money spend on the
aggregate
– Minimize 0.20𝑥1 + 0.45𝑥2
• Constraint Functions
– 1000 pounds aggregates: 𝑥1 + 𝑥2 = 1000
– Composition requirement of coarse material
(example)
0.35𝑥1 + 0.60𝑥2 ≥ 480
0.35𝑥1 + 0.60𝑥2 ≤ 550 18
 Properties of Solutions of Linear Programs
Mathematical Representation of the Linear Program

Decision Variables
Objective Function

Minimize 𝑍=0.20𝑥1 + 0.45𝑥2

Constraint Functions

Subject to: 𝑥1 +𝑥2 = 1000

0.35𝑥1 + 0.60𝑥2 ≥ 480
0.35𝑥1 + 0.60𝑥2 ≤ 550
0.30𝑥1 + 0.30𝑥2 ≥ 300
0.30𝑥1 + 0.30𝑥2 ≤ 350
0.35𝑥1 + 0.10𝑥2 ≥ 150
0.35𝑥1 + 0.10𝑥2 ≤ 200
𝑥1 , 𝑥2 ≥ 0
19
 Properties of Solutions of Linear Programs
Solving the Mixing Problem using Microsoft Excel

X1 X2 Product B
0.00 0.00 0
Minimize 0.20 0.45
Subject to 1.00 1.00 0 1000
0.35 0.60 0 480
0.35 0.60 0 550
0.30 0.30 0 300
0.30 0.30 0 350
0.35 0.10 0 150
0.35 0.10 0 200

Optimal Solution

X1 X2 Product B
400.00 600.00 350
Minimize 0.20 0.45
Subject to 1.00 1.00 1000 1000
0.35 0.60 500 480
0.35 0.60 500 550
0.30 0.30 300 300
0.30 0.30 300 350
0.35 0.10 200 150
0.35 0.10 200 200

20
Graphical Solution Procedure

21
 Graphical Solution Procedure for Linear
Programming Problems

• A graphical solution method can be used to solve a linear

program with two variables:
– Prepare a graph of the feasible solutions for each of the
constraints.
– Determine the feasible region that satisfies all the
constraints simultaneously.
– Draw an objective function line.
– Move parallel objective function lines toward larger
(smaller) objective function values without entirely
leaving the feasible region.
– Any feasible solution on the objective function line with
the largest (smallest) value is an optimal solution.
22
 Example 1: A Product-mix Problem

Max 2x1 + 3x2

s.t. x1 < 3
x1 + 4x2 < 12
3x1 + 2x2 < 12
x1, x2 > 0

23
 Example 1: Constraint (1)

x2
7

5 x1 ≤ 3
4

3 x1 = 3 (critical boundary)

1
(3, 0)

0 x1
0 1 2 3 4 5 6 7 8
24
 Example 1: Constraint (2)

x2
7

6
x1 + 4x2 < 12
5
(0, 3)
4

3 (4, 2)
x1 + 4x2 = 12
2 Critical boundary

0
x1
0 1 2 3 4 5 6 7 8
25
 Example 1: Constraint (3)

x2
7 (0, 6)
6

4
3x1 + 2x2 ≤ 12
3

1 (4, 0)
0 x1
0 1 2 3 4 5 6 7 8
26
Example 1: Combined-Constraint Graph

x2
7

6 x1 ≤ 3

4 3x1 + 2x2 ≤ 12
3
x1 + 4x2 ≤ 12
2

0 x1
0 1 2 3 4 5 6 7 8
27
 Example 1: Objective Function Line

x2
7

6 Objective function
2x1 + 3x2 = 6
5

4
(0, 2)
3
Move Direction (max)
2
(3, 0)
1

0 x1
0 1 2 3 4 5 6 7 8
28
 Example 1: Objective Function Line

x2
7 Objective function
6 2x1 + 3x2 = 12

4
Optimal solution
(𝑥1∗ =2.4, 𝑥2∗ = 2.4)
3

0 x1
0 1 2 3 4 5 6 7 8
29
Example 2: A Minimization LP Formulation

Min Z = 4x1 + x2

s.t. 2x1 + 5x2 > 10 (1)

4x1 - x2 > 8 (2)

x1 + x2 > 4 (3)
x1, x2 > 0

30
 Example 2: Constraints

x2
Feasible region
6

4x1 - x2 > 8 (2)

5

4 x1 + x2 > 4 (3)

2 2x1 + 5x2 > 10 (1)

0 x1
0 1 2 3 4 5 6 7

31
 Example 2: Objective Function

x2
Min Z = 4x1 + x2
6

5 4x1 - x2 > 8

4 x1 + x2 > 4
3 2x1 + 5x2 > 10
2

0 x1
0 1 2 3 4 5 6 7

32
 Example 2: Objective Function

x2
Min Z = 4x1 + x2
6

5 4x1 - x2 > 8

4 x1 + x2 > 4
3 2x1 + 5x2 > 10
2

1
Optimal: 𝑥1∗ = 12Τ5
𝑥2∗ = 8Τ5
0 x1
0 1 2 3 4 5 6 7
𝑍 ∗ = 56Τ5

33
 Feasible Region

• The feasible region for a two-variable linear programming

problem can be nonexistent, a single point, a line, a polygon,
or an unbounded area.
• Any linear program falls in one of three categories:
– is infeasible
– has a unique optimal solution or alternate optimal
solutions
– has an objective function that can be increased/
decreased without bound
• A feasible region may be unbounded and yet there may be
optimal solutions. This is common in minimization
problems and is possible in maximization problems.
34
 Special Cases

• Alternate optimal solutions

– In the graphical method, if the objective function line is
parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions,
with all points on this line segment being optimal.

• Infeasibility
– A linear program which is over-constrained so that no
point satisfies all the constraints is said to be infeasible.

• Unboundedness

35
 Example: Alternate Optima

𝑥2

𝑥1 ≤ 4
Max 𝑍 = 𝑥1 +2𝑥2
s.t.
𝑥1 + 2𝑥2 ≤ 10 𝑥1 + 2𝑥2 ≤ 10

𝑥1 ≤4 𝑍 = 𝑥1 + 2𝑥2

0
0 𝑥1

• The objective function line is parallel to a

boundary constraint

36
 Example: Infeasible Problem

x2
12
Max 2x1 + 6x2
2x1 + x2 ≥ 8
s.t. 4x1 + 3x2 < 12 8

2x1 + x2 > 8 4x1 + 3x2 ≤ 12

x1, x2 > 0 4

0 x1
0 1 2 3 4 5

• There are no points that satisfy both constraints, hence this

problem has no feasible region, and no optimal solution
37
 Example: Unbounded Problem

x2
10
Max Z = 3x1 + 4x2 3𝑥1 + 𝑥2 ≥ 8
8
s.t. x1 + x2 > 5 Max 3𝑥1 + 4𝑥2
3x1 + x2 > 8
5 𝑥1 + 𝑥2 ≥ 5
x1, x2 > 0

0 x1
0 8/3 5 6

• The feasible region is unbounded and the objective

function line can be moved parallel to itself without
bound so that z can be increased infinitely
38
Basic Concepts of Solution

39
 Basic Concepts of Solution

• A feasible solution satisfies all the problem’s

constraints.
• An optimal solution is a feasible solution that results
in the largest possible objective function value when
maximizing (or smallest when minimizing).
• Given a linear program in standard form, with n
variables and m constraints, a basic solution is a
unique solution obtained by setting n - m of the
variables equal to zero and solving the constraint
equations for the values of the other m variables.

40
 Basic Concepts of Solution

• Basis: The mm nonsingular sub-matrix, which

corresponds to the m basic variables, within the mn
coefficient matrix

• Basic variable: The m variables not required to be zero in

a basic solution.

• Non-basic variable: The n – m variables set to zero in a

basic solution

• Basic feasible solution: A basic solution that is also

feasible

41
 Example of Basic Concepts of Solution

min 4 x1 + x2 min 4x1 + x2 + 0 s1 + 0 s2 + 0 s3

s.t. 2 x1 + 5 x2  10 s.t. 2 x1 + 5 x2 − s1 = 10
4 x1 − x2  8 4 x1 − x2 − s2 = 8
x1 + x2  4 x1 + x2 − s3 = 4
x1 , x2  0 x1 , x2 , s1 , s2 , s3  0

n = 5, m = 3

Basic variable = 3
Non-basic variable =2

42
Example of Basic Variables, Basis and Basic Solution

min 4x1 + x2 + 0s1 + 0s2 + 0s3

s.t. 2 x1 + 5 x2 − s1 = 10
4 x1 − x2 − s2 = 8
x1 + x2 − s3 = 4
x1 , x2 , s1 , s2 , s3  0 𝑥1 = 5, 𝑠2 = 12, 𝑠3 = 1
If 𝑥2 & 𝑠1 are non-basic Non-singular, so it is basis
𝑥1 𝑥2 𝑠1 𝑠2 𝑠3
2 0 0   x1   10 
 2 5 −1 0 0   4 −1 0  s  =  8 
 4 −1 0 −1 0     2  
   1 0 −1 s   4 
 1 1 0 0 −1  3  

set 𝑥2 = 0 & 𝑠1 = 0 43
Example of Basic Variables, Basis and Basic Solution

Feasible region
x2 Not basic, infeasible
6
(1,5,17,-9,2) 4x1 - x2 > 8
5 (5,4,20,8,5) Not basic, but feasible
(0,4,10,-12,0) (1,5) (5,4)
Basic but infeasible 4 x1 + x2 > 4
3
(0,2,0,-10,-2)
2x1 + 5x2 > 10
Basic but infeasible 2 (12/5,8/5,14/5,0,0) Basic, feasible, and optimal
1
0 x1
0 1 2 3 4 5 6 7
(2,0,-6,0,-2) (5,0,0,12,1)
Basic, infeasible Basic and feasible

44
 Basic Concepts of Solution

• Feasible basis: A basis corresponding to a basic

feasible solution

Feasible
Solutions Basic Basic
Feasible
(Feasible Solutions
Solutions
Region)

45
Algebraic Meaning of Linear Program

46
 Extreme Points and the Optimal Solution
(for reference only)

• A set in Euclidean space is a convex set if it contains

all the line segments connecting any pair of its points

Convex Non-convex

X(1)
X(2) X(1)
X(2)

• Suppose K is convex, XK; if X cannot be represented

by a linear combination of two different points X(1) K
and X(2) K, i.e. X =  X(1) +(1- ) X(2) (0<<1), then X
is a vertex or extreme point

47
 Extreme Points and the Optimal Solution

• Theorem 1. If an LP problem has a nonempty feasible

region, then the feasible region is a convex set

• Theorem 2. A basic feasible solution of an LP problem

corresponds to an extreme point of the feasible region

• Theorem 3. If the feasible region of a LP problem is

bounded, then an optimal solution can be found at an
extreme point of the feasible region; if the feasible
region is unbounded and an optimal solution exists,
then it should also be found at an extreme point of the
feasible region

48
 Example 1: Five Extreme Points

4
5
3
4
2
3
1
1 2
0 x1
0 1 2 3 4 5 6 7 8
49
Properties of Linear Programs:
Summary

50
 Summary

• Different Forms of Linear Programs

– General form and standard form
– Conversions from general form to standard form

51
 Summary

• Properties of Solution
– Linear programs generally can be solved by computer software;
LP with two decision variables can be solved by graphical
methods
– The feasible region of a LP problem is convex, which could be
unbounded. It has a limited number of extreme points and each
feasible basic solution corresponding to an extreme point
– If the LP has an optimal solution, it must be found at an extreme
point of the feasible region; i.e. only need to consider the extreme
points for solution
– Though the number of extreme point is limited, it is inefficient or
impossible to enumerate all the feasible basic solutions
– The solution can be infeasible, unique, alternate/multiple, or
unbounded
52