MTH 3107: Linear Programming
J. Kizito
Makerere University
e-mail: john.kizito@mak.ac.ug
www: https://www.socnetsolutions.com/~jona
materials: https://www.socnetsolutions.com/~jona/materials/MTH3107
e-learning environment: http://muele.mak.ac.ug
office: block A, level 3, department of computer science
alt. office: institute of open, distance, and eLearning
Introduction to Linear Programming
Kizito (Makerere University) MTH 3107 Feb, 2022 1 / 23
Overview
1 Foundations of Optimization
2 The LP Structure
3 Examples
4 Algorithmic Solutions
5 Conclusion
Kizito (Makerere University) MTH 3107 Feb, 2022 2 / 23
Foundations of Optimization
Introduction
Optimization and Linear Programming
“Mathematical programming” is a class of methods for solving
problems which ask you to optimize: to maximize, minimize, to find
the best, the worst, the most, the least, the fastest, the shortest, etc.
Linear programming is the simplest form, suitable only for problems
with linear objective functions and constraints
Two of the Basic Linear Programming Problems:
1 The Product Mix Problem
What quantities of products should be produced to maximize profit?
In economics, this is the optimal allocation of scarce resources
2 The Blending Problem
What combination of ingredients minimizes cost?
For example, creating industrial chemical compounds
Kizito (Makerere University) MTH 3107 Feb, 2022 3 / 23
Foundations of Optimization
Introduction
Some Optimization Basics
Unconstrained: max f px q x
Easy: 8
x
Unconstrained: max f px q x p1 x q
x
Still easy: df px q
dx 1 2x 0, x 21
In general, what are we doing?
Set the derivative to zero and solve
Kizito (Makerere University) MTH 3107 Feb, 2022 4 / 23
Foundations of Optimization
Some Optimization Basics
Necessary and Sufficient Conditions for an optimum over
single-peaked functions:
Necessity Sufficiency
Maximum df px q
fx 0 d 2 f px q
dx 0
Minimum df px q
fx 0 d 2 f px q
dx ¡0
Kizito (Makerere University) MTH 3107 Feb, 2022 5 / 23
Foundations of Optimization
Optimization and Linear Programming
Some Complications
What about more complicated functions?
max f px, y , z q x p1 y q y p1 x q z p1 x yq
x,y ,z
Calculus still works, but is cumbersome to do by hand. We turn to
computers and automate the process instead
What about constraints?
max f px q x p1 x q subject to x ¤ 31
x
Again, calculus works (use the Lagrangian) for small problems, but
needs automation for larger problems
Kizito (Makerere University) MTH 3107 Feb, 2022 6 / 23
Foundations of Optimization
Optimization and Linear Programming
More Complications
Kizito (Makerere University) MTH 3107 Feb, 2022 7 / 23
The LP Structure
Optimization and Linear Programming
The LP Structure
Assuming the requirements for LP have been met, what does a LP
look like?
1 Decision Variables
Quantities to be allocated
Number of units to be produced
Time intervals, unit quantities, proportions,...
2 Objective Function
What is being maximized or minimized?
Thought: How do we reduce the world to a set of linear equations?
3 Constraints
(In)equalities specifying limits on the unbounded optimization of a
function
If Z P Q, why not just set Q to 8?
Kizito (Makerere University) MTH 3107 Feb, 2022 8 / 23
The LP Structure
The LP Structure
Solving LP Problems
Often, setting up LPs is the hardest part. This is because the actual
“solving” is usually done by computer
How do computers do it?
We will use a graphical technique to illustrate the intuition behind the
algorithmic methods used in optimization software packages
For any LP, there exists an infinite number of possible solutions
Problem spaces may be vast. Many models have tens of thousands of
variables and constraints
How can we search? How can we limit the number of possibilities we
have to try?
Kizito (Makerere University) MTH 3107 Feb, 2022 9 / 23
Examples
The LP Structure
Example 1
Problem
Fischbeck Electronics makes two models of television sets, A and B. Fischbeck
Electronics’ profit, ZA , on A is $300 per set and its profit on B, ZB , is $250 per
set. Fischbeck Electronics wishes to maximize her profits
Notice that unconstrained optimization would cause them to produce only A!
But, Fischbeck Electronics faces several constraints:
1 A Labor Constraint: They can’t use more than 40 hours of labor per day
(5 employees working regular shifts); A needs 2 hours of labor; B needs only
1 hour
2 A Manufacturing Constraint: They only have 45 hours of machine time
available (9 machines available for 5 hours each); A needs 1 hour of machine
time; B needs 3 hours
3 A Marketing Constraint: They can’t sell more than 12 units of set A per
day
Kizito (Makerere University) MTH 3107 Feb, 2022 10 / 23
Examples
The LP Structure
Example 1 – Formulation
Problem Variables
Decision Variables (What can we vary?):
Let xA be the number of model A television sets
Let xB be the number of model B television sets
xA and xB are the only variables we have direct control over
The Objective Function [What are we maximizing (minimizing)?]
Profit! (Cost!)
Z ZA xA ZB xB , but we know that ZA 300 and ZB 250
So, the objective function is Z 300xA 250xB
the Constraints – 3 primary constraints plus feasibility (@i xi ¥ 0)
1 Labor – Total labor is equal to the number of units produced times the labor
required per unit: 2xA xB ¤ 40
2 Manufacturing: xA 3xB ¤ 45
3 Marketing: xA ¤ 12
Kizito (Makerere University) MTH 3107 Feb, 2022 11 / 23
Examples
Example 1
Formulation
Entire LP
maximize Z 300xA 250xB
subject to
2xA xB ¤ 40
xA 3xB ¤ 45
xA ¤ 12
xA ¥ 0; xA ¥ 0
What if xA or xB 7.4235? What does it mean to produce 0.4235
TV sets?
Can 0.6689 people be employed?
Solution?
Kizito (Makerere University) MTH 3107 Feb, 2022 12 / 23
Examples
Graphical Method
Step 1: Graphing the Constraints
Constraints 4 & 5: xA ¥ 0; xA ¥ 0 Constraint 3: xA ¤ 12
Constraint 1: 2xA xB ¤ 40 Constraint 2: xA 3xB ¤ 45
Kizito (Makerere University) MTH 3107 Feb, 2022 13 / 23
Examples
Graphing the Constraints
Combining the Constraints: The Feasible Set
The intersection of all constraint-feasible sets represents the set of
feasible solutions (if a solution exists). Keep in mind that this is the
feasible set - it says nothing about the optimal set!
Kizito (Makerere University) MTH 3107 Feb, 2022 14 / 23
Examples
Graphical Method
Step 2: Identifying the Optimal Points
Corner-Point Enumeration The Feasible Set
The “mystery” point is the
intersection of the two lines
Two equations, two unknowns:
xA 12 and xA 3xB 45
Therefore xB 11
Thus, the coordinates of the fourth corner are (12, 11)
Kizito (Makerere University) MTH 3107 Feb, 2022 15 / 23
Examples
Graphical Method
Step 3: Choosing a Corner-Point
Each of the corner-points represents a possible optimal solution. To
identify the optimal one, substitute them into the objective function
and see which one maximizes the function
Trial Objective Function Profit
p0, 0q 300 0 250 0 0
p0, 15q 300 0 250 15 3, 750
p12, 0q 300 12 250 0 3, 600
(12,11) 300 12 250 11 6,350
Giving solution: xA 12, xB 11, Z $6, 350
But why limit ourselves to corner-points? Why shouldn’t we choose a
point in the interior of the feasible set?
Kizito (Makerere University) MTH 3107 Feb, 2022 16 / 23
Examples
Graphical Method
Isoprofit (Isocost) Curves
xA and xB can take many values. To identify the optimal values, substitute
arbitrary values in as the objective function and then change them to push the
frontier out towards the boundary of the feasible set
To start, pick a value for the objective
function – say, $1,500. This becomes an
isoprofit curve: 300xA 250xB 1500
When xA 0, xB 6 and when
xB 0, xA 5
Any further advancement of the
isoprofit curve would cause it to leave
the feasible set. Thus, (1) optimal
solutions exist only on boundaries, and
(2) if only one exists, the optimal
solution must always occur at a vertex
Kizito (Makerere University) MTH 3107 Feb, 2022 17 / 23
Algorithmic Solutions
Solving LP Problems
Algorithmic Solutions
The Simplex Algorithm (and variants)
Created by George Dantzig in 1947 for the Air Force Office of Scientific
Research
“If the LP problem has an optimal solution, it will be found in a finite
number of iterations.” (Note: this isn’t always very comforting)
The simplex algorithm finds the solution by making iterated
improvements from an initial position (solution)
The Ellipsoid Algorithms
The best known example is Karmarkar’s Algorithm (created at AT&T
Bell Labs)
Runs in linear time
Faster than simplex for very large problems
We won’t worry about Karmarkar...
Kizito (Makerere University) MTH 3107 Feb, 2022 18 / 23
Algorithmic Solutions
Solving LP Problems
What about the Solver?
Do not use Excel or Solver as a black box! Know what’s going on
underneath the surface. Remember: you will always get an answer
back from Solver. However, knowing whether or not that answer is
relevant requires understanding what Solver is doing. Know its
limitations!
Linear programs: Standard simplex
Quadratic programs: Modified simplex (QP is technically NLP, but
results specific to quadratic forms can be exploited to allow for
significant simplification
Nonlinear Programs: Generalized Reduced Gradient Method. NOTE:
Unless you check Assume linear model, it will automatically use
GRG2. GRG2 may have difficulty with some LP or QP problems that
could have more easily been solved by another method. Beware the
black box!
Integer programs: Branch and Bound
Kizito (Makerere University) MTH 3107 Feb, 2022 19 / 23
Algorithmic Solutions
Graphical Method
Example 2 – Problem
A transport company has two types of trucks. Type A and Type B. Type A has a
refrigerated of 20m3 and a non-refrigerated capacity of 40m3 while Type B has the same
overall volume with equal sections for refrigerated and non-refrigerated stock. A grocer
needs to hire trucks for transpirtation of 3, 000m3 of refrigerated and 4, 000m3 of
non-refrigerated stock. The cost per kilometer of Type A is $30 and $40 for Type B.
How manu trucks of each type should the grocer rent to achieve minimum total cost?
Formulation
1 Let x be the number of Type A trucks, y the number of Type B trucks
2 minimize f px, y q 30x 40y
3 Constraints:
A B Total Inequality
Refrigerated 20 30 3, 000 20x 30y ¥ 3000
Non-refrigerated 40 30 4, 000 40x 30y ¥ 4000
x ¥ 0; y ¥ 0
Kizito (Makerere University) MTH 3107 Feb, 2022 20 / 23
Algorithmic Solutions
Graphical Method
Example 2 – Problem
A transport company has two types of trucks. Type A and Type B. Type A has a
refrigerated of 20m3 and a non-refrigerated capacity of 40m3 while Type B has the same
overall volume with equal sections for refrigerated and non-refrigerated stock. A grocer
needs to hire trucks for transpirtation of 3, 000m3 of refrigerated and 4, 000m3 of
non-refrigerated stock. The cost per kilometer of Type A is $30 and $40 for Type B.
How manu trucks of each type should the grocer rent to achieve minimum total cost?
Formulation
1 Let x be the number of Type A trucks, y the number of Type B trucks
2 minimize f px, y q 30x 40y
3 Constraints:
A B Total Inequality
Refrigerated 20 30 3, 000 20x 30y ¥ 3000
Non-refrigerated 40 30 4, 000 40x 30y ¥ 4000
x ¥ 0; y ¥ 0
Kizito (Makerere University) MTH 3107 Feb, 2022 20 / 23
Algorithmic Solutions
Graphical Method
Example 2 – Solution
Linear Program Constraints graph
min f px, y q 30x 40y
subject to
20x 30y ¥ 3000
40x 30y ¥ 4000
x ¥ 0; y ¥ 0
1 f p0, 133q
30 0 40 133 5, 320
2 f p150, 0q
30 150 40 0 4, 500 4 The minimum cost is $4, 180,
3 f p50, 67q achieved with 50 trucks of Type
30 50 40 67 4, 180 A and 67 of Type B
Kizito (Makerere University) MTH 3107 Feb, 2022 21 / 23
Conclusion
Optimization and Linear Programming
A Quick Review
LPs are good for optimization problems involving maximizing profits
and minimizing costs
LP = Decision Variables, Objective Function, and Constraints
Decision Variables are the quantities of resource being allocated
The Objective Function is whats being optimized
Constraints are resource limitations or requirements
Advantages of Linear Programming:
Relatively quick
Guaranteed to find optimal solution
Provides natural sensitivity analysis (shadow prices)
Kizito (Makerere University) MTH 3107 Feb, 2022 22 / 23
Conclusion
Optimization and Linear Programming
Disadvantages of Linear Programming
Absence of risk (does expectation adequately capture risk?)
Restriction to linear objective functions
No correlation among variables
No positive or negative synergies
Nonlinear programming is very difficult
Graphical Method limited to 2 constraints/variables
Fractional solutions often have no meaning
Reducing the world to a set of linear equations is usually very difficult
Kizito (Makerere University) MTH 3107 Feb, 2022 23 / 23
