Linear Programming
2021-03-08 CSC373 Winter 2021 – Sam Toueg 1
Linear Programming (LP) LP Optimization Problem
• minimize/maximize of some objective function Ø which is a linear function of 𝑥!,…, 𝑥”
Subject to constraints (equalities or inequalities) Ø which are linear combinations of 𝑥!,…, 𝑥”
• Many optimization problems can be formulated as LP problems • There are polynomial-time LP problem solvers
• How can we write some problems as LP problems?
2021-03-08 CSC373 Winter 2021 – Sam Toueg 3
Diet Problem
• 𝑚typesofnutrients:𝑁!,…,𝑁#
• Each unit of food 𝐹$ for 𝑗 ∈ {1,…,𝑛} Ø costs 𝑐$
Ø provides 𝑎%$ units of nutrient 𝑁% for each 𝑖 ∈ {1, … , 𝑚}
• Must obtain at least 𝑏% units of nutrient 𝑁% for each 𝑖 ∈ 1, … , 𝑚
• Goal:Cheapestdietthatprovidestherequiredamountofnutrients
Ø D i e t : a m o u n t o f f o o d 𝐹$ f o r e a c h 𝑗 ∈ { 1 , … , 𝑛 }
Formulate it as an LP problem:
• Variables: 𝑥!,…, 𝑥” where 𝑥$ is the amount of food 𝐹$ in the diet
• Objectivefunction:min𝑐! 1𝑥! + … +𝑐” 1𝑥”
• Constraints:𝑎!! 1𝑥! + … +𝑎!$ 1𝑥$ + … +𝑎!” 1𝑥” ≥𝑏! ⋮⋮
𝑎#!1 𝑥! + … + 𝑎#$ 1 𝑥$ + … + 𝑎#” 1 𝑥” ≥ 𝑏#
𝑥!,𝑥&,….,𝑥” ≥0
2021-03-08 CSC373 Winter 2021 – Sam Toueg 4
• 𝑛typesoffood:𝐹!,…,𝐹”
Profit Maximization Problem
• 𝑛typesofproducts:𝑃!,…,𝑃”
• 𝑚typesofresources:𝑅!,…,𝑅#
• Each unit of 𝑃$ for 𝑗 ∈ {1,…,𝑛}
Ø yields profit 𝑐$
Ø requires 𝑎%$ units of resource 𝑅% for each 𝑖 ∈ {1, … , 𝑚}
• Quantityofresourcesavailable:atmost𝑏%unitsofresource𝑅%foreach𝑖∈ 1,…,𝑚
• Goal:Findmixofproductstomakethatmaximizestotalprofit
ØMix: amount of product 𝑃$ for each 𝑗 ∈ {1, … , 𝑛}
Formulate it as an LP problem:
• Variables: 𝑥!,…, 𝑥” where 𝑥$ is amount of product 𝑃$ to make
• Objectivefunction:max𝑐! 1𝑥! + … +𝑐” 1𝑥”
• Constraints:𝑎!! 1𝑥! + … +𝑎!$ 1𝑥$ + … +𝑎!” 1𝑥” ≤𝑏! ⋮⋮
𝑎#!1𝑥! + …+𝑎#$ 1𝑥$ + … +𝑎#” 1𝑥” ≤𝑏#
𝑥!,𝑥&,….,𝑥” ≥0
2021-03-08 CSC373 Winter 2021 – Sam Toueg 5
Transportation Problem • Factories:𝐹!,…,𝐹'(thatmanufacturethesameproduct)
• Outlets:𝑂!,…,𝑂(
(a)Foreach𝑖∈ 1,…,𝑘 ,factory𝐹% makes𝑠% unitsofproduct
(b)Foreach𝑗∈ 1,…,𝑙,outlet𝑂$requires𝑑$unitsofproduct
• 𝑐%$ = cost to ship one unit of product from factory 𝐹% to outlet 𝑂$
• Goal:Minimizetheshippingcosttosupplyeveryoutlet with the amount of product that it requires
Formulate it as an LP problem:
• Variables: 𝑥%$ = amount of product shipped from factory 𝐹% to outlet 𝑂$ • Objectivefunction:min∑!)%)’𝑐%$1𝑥%$
!)$)(
• Constraints:(a)∑!)$)(𝑥%$ ≤𝑠%, ∀𝑖∈ 1,…,𝑘
(b)∑!)%)’𝑥%$≥𝑑$,∀𝑗∈ 1,…,𝑙 𝑥%$≥0, ∀𝑖∈ 1,…,𝑘,𝑗∈ 1,…,𝑙
2021-03-08 CSC373 Winter 2021 – Sam Toueg 6
General Form of LP
• Objective function: min/max ∑” 𝑐 1 𝑥 for some given 𝑐 ’s ∈ R
• Variables:𝑥!,…,𝑥”∈R
• Constraints:∑” 𝑎 1𝑥 ≤≥ 𝑏 , ∀𝑖∈ 1,…,𝑚 forsomegiven𝑎 ’s∈R,𝑏+s∈R
$*!$ $ $ $*! %$ $ = %
%$ %
𝑥!,𝑥”,….,𝑥# ≥0 Matrix formulation
𝑥!
• Variables: 𝑥 = 𝑥⋮ ∈ R”
• Objective function: min/max 𝑐 ≤
where 𝑐 =
where A= ⋮ ⋱ ⋮ and𝑏= ⋮
“,,
𝑥
𝑐! … 𝑐”
𝑎!! ⋯ 𝑎!”
• Constraints:𝐴1𝑥 ≥ 𝑏 𝑥≥0=
𝑏! 𝑎#! ⋯ 𝑎#” 𝑏#
Input:𝑐$,𝑎%$,𝑏% ∈R ∀𝑖∈ 1,…,𝑚 and∀𝑗∈ 1,…,𝑛
Output: 𝑥!,…, 𝑥” ∈ R that (1) minimizes/maximizes the objective function and 2021-03-08 (2) satisfy all the constraints
7
Farmer Example
• Canplanttwokindsofcorncrop:𝐶!(forhumanconsumption)and𝐶&(foranimalfeed)
Planting Requirements per hectare Available Resources Profit per hectare
𝐶!
3$
𝐶#
2$
Labour (hours)
≤ 40
Seed (kg)
≤ 100
Pesticide (bags)
≤ 10
𝐶!
𝐶𝟐
Labour (hours)
Pesticide (bags)
2
1
1
1
Seed (kg)
3
0
• Goal: Find how many hectares of 𝐶! and 𝐶& to plant to maximize profit under available resource constraints
Formulate it as an LP problem:
• Variables: 𝑥!, 𝑥& amount of hectares of 𝐶! and 𝐶# to plant, respectively • Objective function: max 3 1 𝑥! + 2 1 𝑥& [proMit]
• Constraints: 2 1 𝑥! + 𝑥& ≤ 40 𝑥! + 3 1 𝑥& ≤ 100
𝑥! ≤ 10 𝑥!, 𝑥& ≥ 0
[labour constraint] [seed constraint] [pesticide constraint]
2021-03-08
CSC373 Winter 2021 – Sam Toueg 8
Geometric Interpretation of this LP Problem
𝒙𝟐
40
30
20 10
𝑶𝒑𝒕𝒊𝒎𝒂𝒍 (𝟒, 𝟑𝟐)
• Variables: 𝑥! , 𝑥”
• Objective function: max 3 0 𝑥! + 2 0 𝑥”
• Constraints:
2 0 𝑥!+ 𝑥” ≤ 40 [labour] 𝑥! + 3 0 𝑥” ≤ 100 [seed]
𝑥!≤ 10 𝑥!,𝑥” ≥0
[pesticide]
Region of feasible solutions: all the points (𝑥!, 𝑥”) that satisfy all the constraints
𝟐 * 𝒙𝟏+ 𝒙𝟐 ≤ 𝟒𝟎
𝒙𝟏 + 𝟑 * 𝒙𝟐 ≤ 𝟏𝟎𝟎
𝒙𝟏 ≤ 𝟏𝟎
40 𝒙𝟏 𝟑%𝒙𝟏 +𝟐%𝒙𝟐 =60
𝟑%𝒙𝟏 +𝟐%𝒙𝟐 =40
𝟑 % 𝒙𝟏 + 𝟐 % 𝒙𝟐 = 76
10
20 30
3 % 𝑥! + 2 % 𝑥” = y
obj. function
2021-03-08
𝟑%𝒙𝟏 +𝟐%𝒙𝟐 =20
CSC373 Winter 2021 – Sam Toueg 12