ManSci Topic 6: Linear Programming
Linear Programming
- “programming” refers to “choosing a course of action”
4
- involves choosing a course of action when the mathematical model of the
3
problem contains only linear functions
2
Linear Programming (LP) Problem
1
- LP problem, if both objective function and constraints are linear
Components of a Linear Program
Objective Function Max or min of some quantity
Constraints All LP problems have this, the limit
the degree to which the objective
can be pursued
Decision Variables Unknowns to be determined (ex. #
of units to produce)
Feasible solution Satisfies all the problem’s
constraints
Optimal solution Is a feasible solution that results in
the largest possible objective
function when maximizing (or
smaller when min
Graphical solution method Can be used to solve a linear
program with two variables
Linear Functions
- each variable is raised to the 1st power
- each variable appears in a separate term
- all terms are multiplied by constants
Linear Constraints
- are linear functions that are restricted to be “less than or equal to” or
“greater than or equal to” a constant.
Problem formulation or modeling
- the process of translating a verbal statement of a problem into a
mathematical statement
- an art that can only be mastered with practice and experience
Guidelines for Model Formulation
- understand the problem thoroughly
- describe the objective
- describe each constraint
- define the decision variables
- write the objective in terms of the decision variables
- write the constraints in terms of the decision variables
Summary of the Graphical Solution Procedure for Maximization Problems
. Prepare a graph of the feasible solutions for each of the constrains
. Determine the feasible region that satisfies all the constraints
simultaneously
. Draw an objective function line
. Move parallel objective function lines toward larger objective function
without entirely leaving the feasible region
. Any feasible solution on the objective function line with the largest
value is an optimal solution
5
Slack and Surplus Variables
- Standard Form, a linear program in which all the variables are non-negative
and all the constraints are equalities
- standard form is attained by adding slack variables to “less than or equal
to” constrains, and by subtracting surplus variable from “greater than or equal to”
constraints
- slack and surplus variables represent the difference between the left and
right sides of the constrains
- they have an objective function coefficients equal to 0
Extreme Points and the Optimal Solution
- extreme points, the corners or vertices of the feasible region
- optimal solution, can be found at an extreme point of the feasible region
-
Reduced Cost
- reduced cost for a decision variable whose value is > 0 in the optimal
solution Is 0.
Summary of the Graphical Solution Procedure for Minimization Problems
. Prepare a graph of the feasible solution for each of the constraints
. Determine the feasible region that satisfies all the constrains
simultaneously
. Draw an objective function line
. Move parallel objective function lines toward smaller objective function
values without entirely leaving the feasible region
. Any feasible solution on the objective function line with the smallest
value is an optimal solution
Feasible Region
- the feasible region for a two-variable LP problem can be nonexistent, a
single point, a line, a polygon, or an unbounded area.
- any linear program falls in one of four categories:
- is feasible
- has a unique optical solution
- has alternative optimal solution
- has an objective function that can be increased without bound
- a feasible region may be unbounded and yet there may be optimal solutions
Special Cases
. Alternative 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
- no solution to LP problem satisfies all the constraints, including the
non-negativity conditions.
- graphically, this means a feasible region does not exist
- causes include:
- a formulation error has been made
- management’s expectations are too high
- too many restrictions have been placed on the problem (the
problem is over-constrained)
. Unbounded
- the solution to a maximization LP problem is unbounded if the value of
the solution may be made indefinitely large without violating any constraints
- for real problems, this is the result of improper formulation. (Maybe, a
constraint has been inadvertently omitted)