Chapter 2: Linear Programming (LP)

Chapter Topics
•	Model Formulation
•	A Maximization Model Example
•	Graphical Solutions of Linear Programming Models
•	A Minimization Model Example
•	Irregular Types of Linear Programming Models
•	Characteristics of Linear Programming Problems

Linear Programming:  An Overview
•	Objectives of business decisions frequently involve maximizing profit or minimizing costs. 
•	Linear programming is an analytical technique in which linear algebraic relationships represent a firm’s decisions, given a business objective, and resource constraints.
•	Steps in application:
•	Identify problem as solvable by linear programming.
•	Formulate a mathematical model of the unstructured problem.
•	Solve the model.
•	Implementation

Model Components
•	Decision variables - mathematical symbols representing levels of activity of a firm.
•	Objective function - a linear mathematical relationship describing an objective of the firm, in terms of decision variables - this function is to be maximized or minimized.
•	Constraints – requirements or restrictions placed on the firm by the operating environment, stated in linear relationships of the decision variables.
•	Parameters - numerical coefficients and constants used in the objective function and constraints.

Linear Programming (LP) Problem
•	The maximization or minimization of some quantity is the objective in all linear programming problems.
•	All LP problems have constraints that limit the degree to which the objective can be pursued.
•	A feasible solution satisfies all the problem's constraints.
•	An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing).
•	A graphical solution method can be used to solve a linear program with two variables.
•	If both the objective function and the constraints are linear, the problem is referred to as a linear programming problem.
•	Linear functions are functions in which each variable appears in a separate term raised to the first power and is multiplied by a constant (which could be 0).
•	Linear constraints are linear functions that are restricted to be "less than or equal to", "equal to", or "greater than or equal to" a constant.

Problem Formulation
•	Problem formulation or modeling is the process of translating a verbal statement of a problem into a mathematical statement.

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.

LP Formulation                  
			    Max       5x1 + 7x2

                            s.t.            x1            <   6
                                           2x1 + 3x2  <  19
                                             x1 +   x2  <   8
                                     	  x1, x2 > 0
LP Model Formulation - A Maximization Example
•	Product mix problem - Beaver Creek Pottery Company
•	How many bowls and mugs should be produced to maximize profits given labor and materials constraints?
•	Product resource requirements and unit profit:

Resource Requirements	
Product	Labor
(hr/unit)	Clay
(lb/unit)	Profit
($/unit)	
Bowl	1	4	40	
Mug	2	3	50	

Resource Availability: 40 hrs of labor per day; 	120 lbs of clay
Decision Variables:      x1 = number of bowls to produce per day
x2 = number of mugs to produce per day 
Objective Function: Maximize Z = $40x1 + $50x2; Where Z = profit per day
Resource Constraints: 	1x1 + 2x2  40 hours of labor
4x1 + 3x2  120 pounds of clay
Non-Negativity Constraints:   	x1  0; x2  0 

Complete Linear Programming Model:
Maximize  Z  =  $40x1 + $50x2
subject to:     	     1x1 + 2x2    40
                    	     4x2 + 3x2    120
                             x1, x2    0

A Feasible Solution:
•	A feasible solution does not violate any of the constraints:
        Example  x1 = 5 bowls
                        x2 = 10 mugs
                        Z = $40x1 + $50x2 = $700
        Labor constraint check:
            1(5) + 2(10) = 25 < 40 hours, within constraint
        Clay constraint check:
            4(5) + 3(10) = 70 < 120 pounds, within constraint
•	An infeasible solution violates at least one of the constraints:
    Example x1 = 10 bowls
                   x2 = 20 mugs
                    Z = $1400
    Labor constraint check:
            1(10) + 2(20) = 50 > 40 hours, violates constraint

Graphical Solution of LP Models
•	Graphical solution is limited to linear programming models containing only two decision variables (can be used with three variables but only with great difficulty).

•	Graphical methods provide visualization of how a solution for a linear programming problem is obtained.

Example 1:  Graphical Solution

Slack Variables
•	Standard form requires that all constraints be in the form of equations  (equalities).
•	A slack variable is added to a  constraint  (weak  inequality) to convert it to an equation (=).
•	A slack variable typically represents an unused resource.
•	A slack variable contributes nothing to the objective function value.

Summary of the Graphical Solution Procedure for Maximization Problems
•	Prepare a graph of the feasible solutions for each of the constraints.
•	Determine the feasible region that satisfies all the constraints simultaneously..
•	Draw an objective function line.
•	Move parallel objective function lines toward larger objective function values without entirely leaving the feasible region.
•	Any feasible solution on the objective function line with the largest value is an optimal solution.

Extreme Points and the Optimal Solution
•	The corners or vertices of the feasible region are referred to as the extreme points.
•	An optimal solution to an LP problem can be found at an extreme point of the feasible region.
•	When looking for the optimal solution, you do not have to evaluate all feasible solution points.
•	You have to consider only the extreme points of the feasible region.
•	The Five Extreme Points

LP Model Formulation A Minimization Example
•	Two brands of fertilizer available - Super-Gro, Crop-Quick.
•	Field requires at least 16 pounds of nitrogen and 24 pounds of phosphate.
•	Super-Gro costs $6 per bag, Crop-Quick $3 per bag.
•	Problem: How much of each brand to purchase to minimize total cost of fertilizer given following data?
	Chemical Contribution	
Brand	Nitrogen
(lb/bag)	Phosphate
(lb/bag)	
Super-gro	2	4	
Crop-quick	4	3	

Decision Variables: x1 = bags of  Super-Gro
	x2 = bags of  Crop-Quick

The Objective Function:
	Minimize Z = $6x1 + 3x2
	Where:   $6x1 = cost of bags of Super-Gro
               	$3x2 = cost of bags of Crop-Quick

Model Constraints:
	2x1 + 4x2  16 lb (nitrogen constraint)
	4x1 + 3x2  24 lb (phosphate constraint)
	x1, x2  0 (non-negativity constraint)

•	A surplus variable is subtracted from a  constraint to convert it to an equation (=).
•	A surplus variable represents an excess above a constraint requirement level.
•	Surplus variables contribute nothing to the calculated value of the objective function.
•	Subtracting slack variables in the farmer problem constraints:
                                2x1 + 4x2 - s1 = 16 (nitrogen)
	                            4x1 + 3x2 - s2 = 24 (phosphate)

Irregular Types of Linear Programming Problems
•	For some linear programming models, the general rules do not apply.

•	Special types of problems include those with:
•	Multiple optimal solutions
•	Infeasible solutions
•	Unbounded solutions
        
Maximize Z=$40x1 + 30x2
subject to:  1x1 + 2x2  40
                   4x2 + 3x2  120
                     x1, x2  0
Where:
x1 = number of bowls
x2 = number of mugs

Multiple Optimal Solutions Beaver Creek Pottery Example

Infeasible Solution

An Unbounded Problem

Characteristics of Linear Programming Problems
•	A linear programming problem requires a decision - a choice amongst alternative courses of action.
•	The decision is represented in the model by decision variables.
•	The problem encompasses a goal, expressed as an objective function, that the decision maker  wants to achieve.
•	Constraints exist that limit the extent of achievement of the objective.
•	The objective and constraints must be definable by linear mathematical functional relationships.  

Properties of Linear Programming Models
•	Proportionality - The rate of change (slope) of the objective function and constraint equations is constant.
•	Additivity - Terms in the objective function and constraint equations must be additive.
•	Divisibility -Decision variables can take on any fractional value and are therefore continuous as opposed to integer  in nature.
•	Certainty - Values of all the model parameters are assumed to be known with certainty (non-probabilistic).

Problem Statement
•	Hot dog mixture in 1000-pound batches.
•	Two ingredients, chicken ($3/lb) and beef ($5/lb).
•	Recipe requirements:
•	at least 500 pounds of chicken
•	at least 200 pounds of beef
•	Ratio of chicken to beef must be at least 2 to 1.
•	Determine optimal mixture of ingredients that will minimize costs.
Step 1:
Identify decision variables.
                          x1 = lb of chicken in mixture (1000 lb.)
                          x2 = lb of beef in mixture (1000 lb.)
Step 2:
Formulate the objective function.
		Minimize Z = $3x1 + $5x2
		where Z = cost per 1,000-lb batch
                      $3x1 = cost of chicken
                      $5x2 = cost of beef
Step 3:
Establish Model Constraints
                    x1 + x2 = 1,000 lb
                    x1  500 lb of chicken
                    x2  200 lb of beef
                x1/x2  2/1 or x1 - 2x2  0
                    x1, x2  0

The Model:  Minimize Z = $3x1 + 5x2
                     subject to:  x1 + x2 = 1,000 lb
                                        x1  50
                                        x2  200 
                                        x1 - 2x2  0
                                        x1,x2  0    

Computer Solutions
•	Computer programs designed to solve LP problems are now widely available.
•	Most large LP problems can be solved with just a few minutes of computer time.
•	Small LP problems usually require only a few seconds.
•	Linear programming solvers are now part of many spreadsheet packages, such as Microsoft Excel.
•	In this chapter we will discuss the following output:
•	objective function value
•	values of the decision variables
•	reduced costs
•	slack/surplus
•	In Chapter 3 we will discuss how an optimal solution is affected by a change in:
•	a coefficient of the objective function
•	the right-hand side value of a constraint
 	A	B	C	D	E	F	
1	 	LHS Coefficients	 	Price	Stock	
2	Constraints	X1	X2	RHS Values	Change	Price	
3	#1	1	0	6	#N/A	#N/A	
4	#2	2	3	19			
5	#3	1	1	8	#N/A	#N/A	
6	Obj.Func.Coeff.	5	7	 	#N/A	#N/A	
	A	B	C	D			

6		Decision Variables		#N/A	#N/A	
7		Deluxe	Professional		#N/A	#N/A	
8	Bikes Made	 	 		#N/A	#N/A	
9					#N/A	#N/A	
10	Maximized Total Profit	=B5*C10+C5*D10		#N/A	#N/A	
11					#N/A	#N/A	
12	Constraints	Amount Used		Amount Avail.	#N/A		
13	Aluminum	=B3*C10+C3*D10	<=	6			
14	Steel	=B4*C10+C4*D10	<=	8			
We see from the previous slide that:

		  Objective Function Value  =  46
		  Decision Variable #1 (x1)   =    5
		  Decision Variable #2 (x2)   =    3
		  Slack in Constraint #1        =    1 (= 6 - 5)
		  Slack in Constraint #2        =    0 (= 19 - 19)
		  Slack in Constraint #3        =    0 (= 8 - 8)

Reduced Cost
•	The reduced cost for a decision variable whose value is 0 in the optimal solution is the amount the variable's objective function coefficient would have to improve (increase for maximization problems, decrease for minimization problems) before this variable could assume a positive value.  
•	The reduced cost for a decision variable with a positive value is 0.

Slack and Surplus Variables
•	A linear program in which all the variables are non-negative and all the constraints are equalities is said to be in standard form.  
•	Standard form is attained by adding slack variables to "less than or equal to" constraints, and by subtracting surplus variables from "greater than or equal to" constraints.  
•	Slack and surplus variables represent the difference between the left and right sides of the constraints.
•	Slack and surplus variables have objective function coefficients= 0.