Ch.

8: Linear Programming Methods

Linear Programming (LP) Problem: Optimal design problem in which the cost
and constraint functions are linear in the design variables

Standard LP Problem Form:

Minimize 𝑓 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐 𝑛𝑥 𝑛
𝑛

𝑓 = ෍ 𝑐𝑖 𝑥 𝑖 = 𝑐റ 𝑇 𝑥
𝑖=1
Subject to
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥 𝑛 = 𝑏1
equality
⋮
constraints
𝑎𝑚 1 𝑥1 + 𝑎𝑚 2 𝑥2 + ⋯ + 𝑎𝑚 𝑛 𝑥𝑛 = 𝑏𝑚
𝑏𝑖 ≥ 0, 𝑖 = 1 𝑡𝑜 𝑚
𝑥𝑗 ≥ 0, 𝑗 = 1 𝑡𝑜 𝑛
𝑏𝑖 = resource limits (constants)
1
 Transcription of Other Problems to Standard LP Form
• Negative resource limits
– If 𝑏𝑖 < 0, multiply constraint by -1
𝑥1 + 2𝑥2 ≤ −2 ⟶ −𝑥1 − 2𝑥2 ≥ 2 → −𝑥1 − 2𝑥2 − 𝑠1 = 2
• Inequalities
– Introduce slack or surplus variables (result: additional unknowns)
Treatment of " ≤ 𝑡𝑦𝑝𝑒“ constraints
𝑎𝑖1 𝑥1 + ⋯ + 𝑎𝑖𝑘 𝑥𝑘 + 𝑠𝑖 = 𝑏𝑖 ; 𝑏𝑖 ≥ 0; 𝑠𝑖 ≥ 0
Treatment of " ≥ 𝑡𝑦𝑝𝑒“ constraints
𝑎𝑖1 𝑥1 + ⋯ + 𝑎𝑖𝑘 𝑥𝑘 − 𝑠𝑖 = 𝑏𝑖 ; 𝑏𝑖 ≥ 0; 𝑠𝑖 ≥ 0
• Unrestricted variables
– If a design variable is unrestricted in sign, write it as the difference of two non-negative
variables (result: dimension of design variable vector increases by 1)
𝑥𝑗 = 𝑥𝑗 + − 𝑥𝑗 − ; 𝑥𝑗 + ≥ 0, 𝑥𝑗 − ≥ 0
• Maximization
– Minimize the function’s negative
Maximize
𝑧 = 𝑑1 𝑥1 + ⋯ + 𝑑𝑛 𝑥𝑛 ⇔ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓 = − 𝑑1 𝑥1 + ⋯ + 𝑑𝑛 𝑥𝑛

2
 Properties of LP Problems
1. Feasible set is defined by linear equalities → Feasible set is convex
Cost function is linear → Convex function
Therefore, the LP problem is convex. If an optimum solution exists, it is a
global optimum.

2. The optimum solution always lies on the boundary of the feasible set.
At least one constraint is always active at the solution.

3. There must be more than one solution to the constraint equations (more
than one feasible design).
Number of linearly independent equality constraints, (m) < Number of
design variables, (n)

3
 Arora, Example 8.2

Minimize 𝑓 = −400𝑥1 − 600𝑥2

Subject to
𝑥1 + 𝑥2 ≤16
1 1
𝑥1 + 𝑥2 ≤1
28 14
1 1
𝑥1 + 𝑥2 ≤1
14 24
𝑥1 ≥ 0
𝑥2 ≥ 0

4
Convert to the standard LP form
1- add slack variables to constraints 1,2,&3.

2- Redefine slack variables

Let:
Problem in Standard LP form
Minimize
m=3, number of constraint equations
n=5, number of design variables
n>m, infinite number of possible solution
Rewrite the constraint
𝑥3 , 𝑥4 , 𝑎𝑛𝑑 𝑥5 appear in one and only one equation. The coefficient of each of these
variables is +1 → Dependent variables
𝑥1 , 𝑎𝑛𝑑 𝑥2 → Independent variables
Different values for 𝑥1 , 𝑎𝑛𝑑 𝑥2 generate different values for 𝑥3 , 𝑥4 , 𝑎𝑛𝑑 𝑥5 . Thus,
there are infinite solutions for Ax = b
Can Choose other forms for general solution: choose 𝑥1 , 𝑎𝑛𝑑 𝑥4 as an independent
variables
Basic solution is a solution of particular interest in LP problems is obtained by setting p of
the variables to zero and solving for the rest
 Basic Solution
• Let p = n-m (number of redundant variables)
• Set p variables to zero (nonbasic variables)
• Solve for remaining m variables (basic variables)
• Use Gauss-Jordan elimination to generate
solutions systematically

If an LP problem has a solution, it is at one of the

vertices of the feasible set

1
1
 Arora, Example 8.2
Soln x1 x2 x3 x4 x5 f Vertex
No.
1 0 0 16 1 1 0 A

2 0 14 2 0 5 -8400 E
12
3 0 16 0 1 1 _ F
−
7 3
4 0 24 -8 5 0 _ G
−
7
5 16 0 0 3 1 _ J
−
7 7
6 14 0 2 1 0 -5600 B
2
7 28 0 -12 0 -1 _ H

8 4 12 0 0 3 -8800 D
14
9 11.2 4.8 0 1 0 -7360 C
5
10 140 168 36 0 0 _ I
−
17 17 17
9
Introduction to Optimum Design 3e. Copyright © 2012 Elsevier, Inc. All rights reserved.
 Theorems for LP Problems
Theorem 8.1
The collection of feasible solutions for an LP problem constitutes a convex set
whose extreme points correspond to basic feasible solutions.
Basic feasible solutions are vertices of the convex polyhedron representing
the feasible set.

Theorem 8.2
Let the m x n coefficient matrix A of the constraint equations have rank m (full
row rank). Then
1. If there is a feasible solution, there is a basic feasible solution.
If a solution exists, there must be at least one vertex of the convex feasible set.
2. If there is an optimum feasible solution, there is an optimum basic
feasible solution.
If a solution exists, then it is at one of the vertices of the complex polyhedron.

Note: Multiple optimum solutions may exist if the cost function is parallel to
one of the active constraints.

13
 Number of Basic Solutions

From Theorems 8.1 and 8.2, the task of solving an LP

problem is reduced to searching for an optimum
among only the basic solutions.
For a problem with n design variables and m
constraints, the maximum number of basic solutions is

𝑛 𝑛!
=
𝑚 𝑚! 𝑛 − 𝑚 !

We can search this solution set systematically using the

Simplex method.
14
 Example 8.3
Maximize Minimize
𝑧 = 4𝑥1 + 5𝑥2 𝑓 = −4𝑥1 − 5𝑥2
−𝑥1 + 𝑥2 ≤ 4 −𝑥1 + 𝑥2 + 𝑥3 = 4
𝑥1 + 𝑥2 ≤ 6 𝑥1 + 𝑥2 + 𝑥4 = 6
𝑥1 , 𝑥2 ≥ 0 𝑥3 = 𝑠1 ≥ 0, 𝑥4 = 𝑠2 ≥ 0

𝑛 = 4, 𝑎𝑛𝑑 𝑚 = 2
𝑝 = 𝑛 − 𝑚 = 4 − 2 = 2, the solutions are obtained by choosing two variables as
nonbasic variables ( zero variables)and the remaining as basic variables ( nonzero
variables)
𝑛 𝑛! 4!
#𝑜𝑓 𝑏𝑎𝑠𝑖𝑐 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛𝑠 = = = =6
𝑚 𝑚! 𝑛 − 𝑚 ! 2! 4 − 2 !
the problem has six basic solutions; that is, there are six different ways in which two
of the four variables can be chosen as nonbasic (independent variables).
Soln. 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒇 Vortex
No.

1 0 0 4 6 0 A
2 0 4 0 2 -20 B
3 0 6 -2 0 ___ E( infeasible)
4 -4 0 0 10 ___ Not shown (infeasible)
5 6 0 10 0 -24 D
6 1 5 0 0 -29 C
 Arora, Example A.8
Use Gauss-Jordan elimination to find a general solution to the following system
of equations.

−𝑥1 + 2𝑥2 − 3𝑥3 + 𝑥4 = −1

2𝑥1 + 𝑥2 + 𝑥3 − 2𝑥4 = 2
𝑥1 − 𝑥2 + 2𝑥3 + 𝑥4 = 3
𝑥1 + 3𝑥2 − 2𝑥3 − 𝑥4 = 1

17