LP Cheat Sheet
Assumptions of Linear Programming
A.Assumptions dealing with mathematical relationships within the model-implicit in earlier discussion - some caused by linear equation.
1.Proportionality - two components
a. Contribution per unit of each decision variable (activity) to the objective function.
b. Use of each resource per unit of each decision variable must be constant and independent of its level.
2.Additivity - deals with the decision variable/activities - two components
a. Total value of the objective function equals the sum of the contributions of each activity.
b. Total resource use is the sum of the resource use of each activity.
3.Divisibility - decision variables can take on any non-negative value including fractional ones.
4.Certainty - all the parameters of the model (ai, bi, and ci) are known constants.
5.Finiteness - the number of resources restrictions and the number of alternative activities is finite.
B.Assumptions on appropriateness of the formulation - not just LP but in general all model formulations
1.Objective Function Appropriateness - objective function is the sole criterion by which the values of the decision variable should be chosen.
2.Decision Variable Appropriateness - decision variables are appropriately defined, manipulatable within the feasible region, and necessary ones are included in the model.
3.Constraint Appropriateness - constraints are appropriate, resources available and no way, a constraint can be violated.
BasicSolution - in a well-structured LP - any set of values of the variables in which the number of nonzero - valued variables (activities and slack) is equal to the number of constraints.
A.Basic variable - nonzero variable
B.Nonbasic variable - remaining zero variables
Basic theorem of LP - in any LP problem an optimal solution can be found by considering only the basic solutions.
A.There will exist an optimal solution in which the number of nonzero valued variables is exactly equal to the number of constraints in the problem.
Tableau - a convenient way to illustrate constraints and relationships in a LP model.
Transfer Equation - supply/demand balance equation - a procedure to add flexibility to LP models - allows output from one activity to be transferred to another activity
A.Coefficient associated with the supply activity is negative
B.Coefficient associated with the demand activity is positive
C.Inequality is 0
Sensitivity Analysis (SA) - General
A.Rationale - rarely are the parameters cjs, aij, and bis in any LP problem known with certainty - recall this is one of the assumptions.
1.Usually at best, they are estimates of the true values
2.SA a way of relating the certainty assumption of LP
B.Defined
1.Sensitivity analysis - once the problem has been solved using the best guess values, the modeler should ask the question, how will the resultant LP solution change if the parameters took on other values.
2.Insensitive - if the optimal basis (nonzero variables) and the value of the objective function are only slightly affected by significant changes in the parameters.
3.Sensitive - if the basis and/or objective function do vary significantly with rather minor changes in the parameters.
Dual Price - shadow price - is the rate of change in the objective function for a 1-unit increase in the resource.
A.Nonzero only for binding constraints
Range Analysis
A.Corresponds to either the objective function coefficient or the RHS - resource available
B.Ranges tell you how much a coefficient can change before the basis changes
1.Activities in the basic solution change - not absolute levels but changes in the activities in the basic solution.
Reduced Cost
A.Shadow prices for activities - nonzero only those for activities not in the optimal solution.
B.Value refers to the reduction in the objective function value if one unit of the nonbasic activity is forced into the solution.
Types of Problems - know how to do
A.Balanced Transportation Problem
1.Set of m supply points from which the good is shipped.
2.Set of n demand points to which the good is shipped.
3.Each unit shipped from supply point i and shipped to demand point j incurs a variable cost of cij.
4.Objective is usually to minimize cost of shipping the goods from the various supply point to the different demand points.
5.Balanced transportation problem - total supply equals total demand. Must add dummy supply or demand points to make the model balance if the original problem is not balanced.
B.Blending Problems
1.Situation in which various inputs must be blended in some desired proportion to produce goods for sale.
2.Usually requires setting developing a proportional constraint and then algebraically manipulating the constraint to obtain a linear constraint.
3.Constraint example:
C.Sequencing Problems
1.Arises when production (for example) entails multiple processes and requires each process to be completed before the next process is started.
2.Sequencing insures the predecessor processes are completed before the successor processes can begin.
3.Intermediate processes often compete for the same resources.
4.Usually requires a series of constraints, which accomplish the sequencing when all constraints are considered. Usually one constraint cannot provide the proper sequencing.
Integer Programming
A.Relaxation of the divisibility assumption in linear programming.
B.Pure Integer Programming Problem - all variables must be integers.
Mixed Integer Programming Problem - both integer and continuous variables are contained within the problem.
C.LP Relaxation is the linear programming model obtained by omitting all integer constraints on the variables.
1.Less constrained than the original integer program - objective function value of LP relaxation objective function of the integer program problem.
Use of Integer Programming - adds realism to LP models
A.Most obvious use is to make decisions integers, such as the number of tractors to buy.
B.Use to model in fix charges - helps relax proportionality and additivity assumptions.
C.Use in either / or constraints - helps relax proportionality and additivity assumptions.
Integer Programming and Sensitivity Analysis
A.Be careful in using sensitivity analysis printed out by canned programs (EXCEl) when using integer programming.
B.Sensitivity analysis is based on calculus (continuous variables) and not discrete variables.
C.Pure integer program standard printed sensitivity analysis is useless.
D.Mixed integer programming for the continuous constraints/activities, standard printed sensitivity analysis maybe all right if the changes dont move the solution out of the feasible region given by the integer constraints.
E.Safest procedure to do sensitivity analysis in an integer-programming model is to reformulate the model for the sensitivity analysis under question and resolve the integer-programming model. Do the sensitivity analysis by reformulating and resolving the model and comparing the solutions.