WIXLIB

Linear Programming: ModelFormulation and SolutionMBA 8104: Quantative Analysis2-1

Chapter Topics Model Formulation A Maximization Model Example Graphical Solutions of Linear Programming Models A Minimization Model Example Characteristics of Linear Programming Problems Solving Linear Programming Problems with TORApresentation notes

Introduction Objectives of business decisions frequently involvemaximizing profit or minimizing costs. Linear programming uses linear algebraic relationshipsto represent a firm’s decisions, given a businessobjective, and resource constraints. Steps in application:1. Identify problem as solvable by linearprogramming.2. Formulate a mathematical model of theunstructured problem.3. Solve the model.4. Implementation presentation notes

Model Components Decision variables - mathematical symbols representing levelsof activity of a firm. Objective function - a linear mathematical relationshipdescribing an objective of the firm, in terms of decisionvariables - this function is to be maximized or minimized. Constraints – requirements or restrictions placed on the firmby the operating environment, stated in linear relationships ofthe decision variables. Parameters - numerical coefficients and constants used in theobjective function and constraints.presentation notes

Summary of Model Formulation StepsStep 1 : Clearly define the decision variablesStep 2 : Construct the objective functionStep 3 : Formulate the constraintspresentation notes

LP Model FormulationIllustration 1: A Maximization Example (1 of 4) Product mix problem - Beaver Creek Pottery Company How many bowls and mugs should be produced to maximizeprofits given labor and materials constraints? Product resource requirements and unit profit:Resource ./Unit)43presentation notesProfit( /Unit)4050

LP Model FormulationA Maximization Example (2 of 4)presentation notes

LP Model FormulationA Maximization Example (3 of 4)ResourceAvailability:40 hrs of labor per day120 lbs of clayDecisionVariables:x1 number of bowls to produce per dayx2 number of mugs to produce per dayObjectiveFunction:Maximize Z 40x1 50x2Where Z profit per dayResourceConstraints:1x1 2x2 40 hours of labor4x1 3x2 120 pounds of clayNon-Negativity x1 0; x2 0Constraints:presentation notes

LP Model FormulationA Maximization Example (4 of 4)Complete Linear Programming Model:MaximizeZ 40x1 50x2subject to: 1x1 2x2 404x2 3x2 120x1 , x2 0presentation notes

Feasible SolutionsA feasible solution does not violate any of the constraints:Example:x1 5 bowlsx2 10 mugsZ 40x1 50x2 700Labor constraint check: 1(5) 2(10) 25 40 hoursClay constraint check:4(5) 3(10) 70 120 poundspresentation notes

Infeasible SolutionsAn infeasible solution violates at least one of theconstraints:Example:x1 10 bowlsx2 20 mugsZ 40x1 50x2 1400Labor constraint check: 1(10) 2(20) 50 40 hourspresentation notes

Graphical Solution of LP Models Graphical solution is limited to linear programming modelscontaining only two decision variables (can be used withthree variables but only with great difficulty). Graphical methods provide visualization of how a solution fora linear programming problem is obtained.presentation notes

Coordinate AxesGraphical Solution of Maximization Model(1 of 12)X2 is mugsMaximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0X1 is bowlsFigure 2.2 Coordinates for Graphical Analysispresentation notes

Labor ConstraintGraphical Solution of Maximization Model (2 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.3 Graph of Labor Constraintpresentation notes

Labor Constraint AreaGraphical Solution of Maximization Model (3 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.4 Labor Constraint Areapresentation notes

Clay Constraint AreaGraphical Solution of Maximization Model (4 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.5 Clay Constraint Areapresentation notes

Both ConstraintsGraphical Solution of Maximization Model (5 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.6 Graph of Both Model Constraintspresentation notes

Feasible Solution AreaGraphical Solution of Maximization Model (6 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.7 Feasible Solution Areapresentation notes

Objective Function Solution 800Graphical Solution of Maximization Model (7 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.8 Objection Function Line for Z 800presentation notes

Alternative Objective Function Solution LinesGraphical Solution of Maximization Model (8 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.9 Alternative Objective Function Linespresentation notes

Optimal SolutionGraphical Solution of Maximization Model (9 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.10 Identification of Optimal Solution Pointpresentation notes

Optimal Solution CoordinatesGraphical Solution of Maximization Model (10 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.11 Optimal Solution Coordinatespresentation notes

Extreme (Corner) Point SolutionsGraphical Solution of Maximization Model (11 of 12)Maximize Z 40x1 50x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.12 Solutions at All Corner Pointspresentation notes

Optimal Solution for New Objective FunctionGraphical Solution of Maximization Model (12 of 12)Maximize Z 70x1 20x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Figure 2.13 Optimal Solution with Z 70x1 20x2presentation notes

Slack Variables Standard form requires that all constraints be in theform of equations (equalities). A slack variable is added to a constraint (weakinequality) to convert it to an equation ( ). A slack variable typically represents an unusedresource. A slack variable contributes nothing to the objectivefunction value.presentation notes

Linear Programming Model: Standard FormMax Z 40x1 50x2 s1 s2subject to:1x1 2x2 s1 404x2 3x2 s2 120x1, x2, s1, s2 0Where:x1 number of bowlsx2 number of mugss1, s2 are slack variablesFigure 2.14 Solution Points A, B, and C with Slackpresentation notes

Illustration 2: LP Model Formulation – Minimization (1 of 8) Two brands of fertilizer available - Super-gro, Crop-quick. Field requires at least 16 pounds of nitrogen and 24 pounds ofphosphate. Super-gro costs 6 per bag, Crop-quick 3 per bag. Problem: How much of each brand to purchase to minimize total costof fertilizer given following data ?Chemical -gro24Crop-quick43Brandpresentation notes

LP Model Formulation – Minimization (2 of 8)Figure 2.15 Fertilizingfarmer’s fieldpresentation notes

LP Model Formulation – Minimization (3 of 8)Decision Variables:x1 bags of Super-grox2 bags of Crop-quickThe Objective Function:Minimize Z 6x1 3x2Where: 6x1 cost of bags of Super-Gro 3x2 cost of bags of Crop-QuickModel Constraints:2x1 4x2 16 lb (nitrogen constraint)4x1 3x2 24 lb (phosphate constraint)x1, x2 0 (non-negativity constraint)presentation notes

Constraint Graph – Minimization (4 of 8)Minimize Z 6x1 3x2subject to:2x1 4x2 164x2 3x2 24x1, x2 0Figure 2.16 Graph of Both Model Constraintspresentation notes

Feasible Region– Minimization (5 of 8)Minimize Z 6x1 3x2subject to:2x1 4x2 164x2 3x2 24x1, x2 0Figure 2.17 Feasible Solution Areapresentation notes

Optimal Solution Point – Minimization (6 of 8)Minimize Z 6x1 3x2subject to:2x1 4x2 164x2 3x2 24x1, x2 0Figure 2.18 Optimum Solution Pointpresentation notes

Surplus Variables – Minimization (7 of 8) A surplus variable is subtracted from a constraint toconvert it to an equation ( ). A surplus variable represents an excess above aconstraint requirement level. A surplus variable contributes nothing to the calculatedvalue of the objective function. Subtracting surplus variables in the farmer problemconstraints:2x1 4x2 - s1 16 (nitrogen)4x1 3x2 - s2 24 (phosphate)presentation notes

Graphical Solutions – Minimization (8 of 8)Minimize Z 6x1 3x2 0s1 0s2subject to:2x1 4x2 – s1 164x2 3x2 – s2 24x1, x2, s1, s2 0Figure 2.19 Graph of Fertilizer Examplepresentation notes

Irregular Types of Linear Programming ProblemsFor some linear programming models, the generalrules do not apply. Special types of problems include those with: Multiple optimal solutions Infeasible solutions Unbounded solutionspresentation notes

Multiple Optimal Solutions Beaver Creek PotteryThe objective function isparallel to a constraint line.Maximize Z 40x1 30x2subject to:1x1 2x2 404x2 3x2 120x1, x2 0Where:x1 number of bowlsx2 number of mugsFigure 2.20 Example with Multiple Optimal Solutionspresentation notes

An Infeasible ProblemEvery possible solutionviolates at least one constraint:Maximize Z 5x1 3x2subject to:4x1 2x2 8x1 4x2 6x1, x2 0Figure 2.21 Graph of an Infeasible Problempresentation notes

An Unbounded ProblemValue of the objectivefunction increases indefinitely:Maximize Z 4x1 2x2subject to: x1 4x2 2x1, x2 0Figure 2.22 Graph of an Unbounded Problempresentation notes

Characteristics of Linear Programming Problems A decision amongst alternative courses of action is required. The decision is represented in the model by decisionvariables. The problem encompasses a goal, expressed as an objectivefunction, that the decision maker wants to achieve. Restrictions (represented by constraints) exist that limit theextent of achievement of the objective. The objective and constraints must be definable by linearmathematical functional relationships.presentation notes

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

Problem Statement: Example (1 of 3) Hot dog mixture in 1000-pound batches. Two ingredients, chicken ( 3/g) and beef ( 5/g). 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 minimizecosts.presentation notes

Solution: Example Problem No. 1 (2 of 3)Step 1:Identify decision variables.x1 Quantity in grams of chicken in mixturex2 Quantity in grams of beef in mixtureStep 2:Formulate the objective function.Minimize Z 3x1 5x2where Z cost per 1,000-lb batch 3x1 cost of chicken 5x2 cost of beefpresentation notes

Solution: Example Problem No. 1 (3 of 3)Step 3:Establish Model Constraintsx1 x2 1,000 lbx1 500 g of chickenx2 200 g of beefx1/x2 2/1 or x1 - 2x2 0x1, x2 0The Model: Minimize Z 3x1 5x2subject to: x1 x2 1,000 gx1 50x2 200x1 - 2x2 0x1,x2 0presentation notes

Example Problem No. 2 (1 of 3)Solve the following modelgraphically:Maximize Z 4x1 5x2subject to: x1 2x2 106x1 6x2 36x1 4x1, x2 0Step 1: Plot the constraintsas equationsFigure 2.23 Constraint Equationspresentation notes

Example Problem No. 2 (2 of 3)Maximize Z 4x1 5x2subject to: x1 2x2 106x1 6x2 36x1 4x1, x2 0Step 2: Determine the feasiblesolution spaceFigure 2.24 Feasible Solution Space and Extreme Pointspresentation notes

Example Problem No. 2 (3 of 3)Maximize Z 4x1 5x2subject to: x1 2x2 106x1 6x2 36x1 4x1, x2 0Step 3 and 4: Determine thesolution points and optimalsolutionFigure 2.25 Optimal Solution Pointpresentation notes