Linear Programming
Instructor: Dr. Zuhair Zafar
CS-860: Artificial Intelligence
Lecture # 16
Linear Programming
⚫ aka LP or Linear Optimization
A mathematical method for determining a way to achieve the best
outcome (such as maximum profit or lowest cost) in a given
mathematical model for some list of requirements (constraints)
represented as linear relationships.
2
Linear Programming
⚫ aka LP or Linear Optimization
A mathematical method for determining a way to achieve the best
outcome (such as maximum profit or lowest cost) in a given
mathematical model for some list of requirements (constraints)
represented as linear relationships.
Example??
3
Examples
⚫ Scheduling of crew members on various flights using as
few crew members as possible
⚫ Maximize the amount of oil from new locations, given a
limited budget
⚫ Scheduling of Operating System processes in the best
possible way, given limited memory
⚫ Business and economics, Engineering problems,
Industry (transportation, manufacturing,
telecommunication
⚫ Modeling diverse types of problems in planning, routing,
scheduling, assignment, and design. 4
Definition
⚫ A linear programming problem is the problem of
optimization (either minimizing or maximizing) a linear
objective function subject to a finite set of linear
constraints (linear equality or inequalities).
⚫ E.g. taking the limitations of materials and labor, and
then determining the "best" production levels for
maximal profits under those conditions.
5
Example 1
Find the maximal and minimal value of the objective
function
𝒛 = 𝟑𝒙 + 𝟒𝒚
subject to the following constraints:
𝒙 + 𝟐𝒚 ≤ 𝟏𝟒
𝟑𝒙 − 𝒚 ≥ 𝟎
𝒙−𝒚≤𝟐
6
Solving LP Problems
⚫ General process for solving LP problems is to graph
the inequalities (constraints) to form a walled-off area
on the x-y plane (feasibility region).
7
Solving LP Problems
⚫ Find the (𝑥, 𝑦) corner points of the feasibility region that
return the largest and smallest values of 𝑧.
⚫ First step is to solve each inequality for the more-easily
graphed equivalent forms:
𝑥 + 2𝑦 ≤ 14 𝑦 ≤ − 1ൗ2 𝑥 + 7
3𝑥 − 𝑦 ≥ 0 ⇒ 𝑦 ≤ 3𝑥
𝑥−𝑦 ≤2 𝑦 ≥𝑥−2 8
Solving LP Problems
⚫ Proof: For linear systems, the maximum and minimum
values of the optimization equation will always be on
the corners of the feasibility region.
⚫ To find the corner points -- which aren't always clear
from the graph -- pair the lines (thus forming a system
of linear equations) and solve:
9
Solving LP Problems
⚫ So the corner points are (2, 6), (6, 4), and (– 1, – 3).
⚫ To find the solution plug these three points into
𝑧 = 3𝑥 + 4𝑦
⚫ 2, 6 : 𝑧 = 3 2 + 4 6 = 6 + 24 = 30
6, 4 : 𝑧 = 3 6 + 4 4 = 18 + 16 = 34
(– 1, – 3): 𝑧 = 3(– 1) + 4(– 3) = – 3 – 12 = – 15
⚫ Then the maximum of 𝒛 = 𝟑𝟒 occurs at (𝟔, 𝟒), and
the minimum of 𝒛 = – 𝟏𝟓 occurs at (– 𝟏, – 𝟑).
10
Example 2
⚫ Maximize and minimize the value of 𝒛 = −𝟎. 𝟒𝒙 + 𝟑. 𝟐𝒚
subject to the following constraints:
𝒙+𝒚≤𝟕
𝒙 + 𝟐𝒚 ≥ 𝟒
−𝒙 + 𝒚 ≤ 𝟓
𝒙≥𝟎
𝒚≥𝟎
𝒙≤𝟓
11
Example 2
⚫ Maximize and minimize the value of 𝒛 = −𝟎. 𝟒𝒙 + 𝟑. 𝟐𝒚
subject to the following constraints:
𝒙+𝒚≤𝟕 𝒚 ≤ −𝒙 + 𝟕
𝒙 + 𝟐𝒚 ≥ 𝟒 𝒚 ≥ − 𝟏 Τ𝟐 𝒙 + 𝟐
−𝒙 + 𝒚 ≤ 𝟓 𝒚≤𝒙+𝟓
⇒
𝒙≥𝟎 𝒙≥𝟎
𝒚≥𝟎 𝒚≥𝟎
𝒙≤𝟓 𝒙≤𝟓
12
Example 2
⚫ Feasible Region
𝑦=0
𝑥=0
13
Example 2
⚫ From the graph, look at lines that cross to form the
corners, so you know which lines to pair up in order to
verify the coordinates.
⚫ • Let’s start at the "top" of the shaded area and work
clockwise around the edges.
𝑦=0
𝑥=0
14
Example 2
⚫ Plugging each corner point into the optimization
equation,
𝑧 = −0.4𝑥 + 3.2𝑦
⚫ (1, 6): 𝑧 = – 0.4(1) + 3.2(6) = – 0.4 + 19.2 = 18.8
⚫ (5, 2): 𝑧 = – 0.4(5) + 3.2(2) = – 2.0 + 6.4 = 4.4
⚫ (5, 0): 𝑧 = – 0.4(5) + 3.2(0) = – 2.0 + 0.0 = – 2.0
⚫ (4, 0): 𝑧 = – 0.4(4) + 3.2(0) = – 1.6 + 0.0 = – 1.6
⚫ (0, 2): 𝑧 = – 0.4(0) + 3.2(2) = – 0.0 + 6.4 = 6.4
⚫ 0, 5 : 𝑧 = – 0.4 0 + 3.2 5 = – 0.0 + 16.0 = 16.0
15
Then the maximum is 18.8 at (1, 6) and the minimum is
–2 at (5, 0).
Solving LP Problems
⚫ Given the inequalities, linear-programming
exercise are pretty straightforward.
⚫ The hard part is usually the word problems,
where you have to figure out what the
inequalities are.
16
Example 3
At a certain refinery, the refining process requires the
production of at least two gallons of gasoline for each
gallon of fuel oil. To meet the anticipated demands of
winter, at least three million gallons of fuel oil a day will
need to be produced. The demand for gasoline, on the
other hand, is not more than 6.4 million gallons a day.
If gasoline is selling for $1.90 per gallon and fuel oil sells
for $1.50/gal, how much of each should be produced in
order to maximize revenue?
17
Example 3
At a certain refinery, the refining process requires the
production of at least two gallons of gasoline for each
gallon of fuel oil. To meet the anticipated demands of
winter, at least three million gallons of fuel oil a day will
need to be produced. The demand for gasoline, on the
other hand, is not more than 6.4 million gallons a day.
If gasoline is selling for $1.90 per gallon and fuel oil sells
for $1.50/gal, how much of each should be produced in
order to maximize revenue?
18
Example 3
⚫ The question asks for the number of gallons which
should be produced,
⚫ Let
𝑥: 𝑔𝑎𝑙𝑙𝑜𝑛𝑠 𝑜𝑓 𝑔𝑎𝑠𝑜𝑙𝑖𝑛𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑑
𝑦: 𝑔𝑎𝑙𝑙𝑜𝑛𝑠 𝑜𝑓 𝑓𝑢𝑒𝑙 𝑜𝑖𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑑
⚫ Since this is a "real world" problem, production levels
cannot be negative, so the variables can't be negative.
This gives the first two constraints: namely,
𝑥 ≥ 0 𝑎𝑛𝑑 𝑦 ≥ 0 19
Example 3
⚫ Since we have to have at least two gallons of gas for
every gallon of oil, then
𝑥 ≥ 2𝑦
⚫ For graphing, of course, we'll use the more manageable
form 𝑦 ≤ (1Τ2)𝑥.
⚫ The winter demand says that 𝑦 ≥ 3,000,000; note that
this constraint eliminates the need for the "𝑦 ≥ 0"
constraint.
20
⚫ The gas demand says that 𝑥 ≤ 6,400,000.
Example 3
⚫ To maximize revenue 𝑅
–optimization equation (objective function) becomes
𝑅 = 1.9𝑥 + 1.5𝑦
21
Example 3
⚫ Mathematical Model
Maximize
𝑅 = 1.9𝑥 + 1.5𝑦
Subject to
𝑥 ≥ 0
𝑥 ≤ 6,400,000
𝑦 ≥ 3,000,000
𝑦 ≤ ( 1ൗ2 )𝑥
22
Example 3
⚫ Feasible Area
23
Example 3
⚫ When we test the corner points at (6.4m, 3.2m), (6.4m,
3m), and (6m, 3m), we should get a maximal solution of
R = $16.96m at (x, y) = (6.4m, 3.2m).
24
Practice Problem
⚫ A small factory produces two types of toys: cars and
diggers. In the manufacturing process two machines
are used: the moulder and the colorizer. A digger needs
2 hours on the moulder and 1 hour on the colorizer. A
car needs 1 hour on the moulder and 1 hour on the
colorizer. The moulder can be operated for 16 hours a
day and the colorizer for 9 hours a day. Each digger
gives a profit of £16 and each car gives a profit of £14.
The profit needs to be maximized.
⚫ How do we formulate this problem? 25
Practice Problem
Example: Consider a chocolate manufacturing company that produces
only two types of chocolate – A and B. Both the chocolates require Milk
and Choco only. To manufacture each unit of A and B, the following
quantities are required:
Each unit of A requires 1 unit of Milk and 3 units of Choco
Each unit of B requires 1 unit of Milk and 2 units of Choco
The company kitchen has a total of 5 units of Milk and 12 units of Choco.
On each sale, the company makes a profit of
Rs 6 per unit A sold
Rs 5 per unit B sold.
Now, the company wishes to maximize its profit. How many units of A and
B should it produce respectively? 26
How do we formulate this problem?
Solving LP Problems
⚫ In algebra, we only work with the simple (and
graph-able) two-variable linear case.
⚫ “Real life" systems can have dozens or
hundreds of variables, or more.
27
Simplex Algorithm
⚫ Several algorithms for solving linear programs
⚫ Simplex Algorithm
⚫ Fairly efficient and widely used
⚫ The feasible region represents the simplex.
⚫ The simplex algorithm - takes as input a linear
program and returns an optimal solution.
28
⚫ Simplex Method - Algebraic Iterative method to solve
LP problems.
Logic of the Algorithm
Compute initial
BFS
Current YES
BFS DONE
Optimal
NO
29
Compute a better
adjacent BFS BFS – Basic Feasible Solution
Step-by-Step Guide
1. Formulate the problem
i. Pick out important information
ii. Formulate constraints
iii. Formulate objective function
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
i. Identify pivotal column
ii. Find θ-values
iii. Identify pivotal row
iv. Identify pivot
v. Pivot
30
5. Get the solution