LINEAR PROGRAMMING

Model Formulation and Graphical Solution

Linear Programming: An Overview

Linear Programming is a mathematical programming technique to optimize performance (e.g. profit or cost) under a set of resource constraints (e.g. machine-hours, money, materials, etc.) as specified by an organization.

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.

In order to apply Linear Programming, certain requirements have to be met

There should be an objective function which should be clearly identifiable and measureable in quantitative terms. For e.g. maximization of profit, minimization of loss. The activities to be included should be distinctly identifiable and measureable in quantitative terms. For e.g. products included in a production planning problem. The resources of the system, which are to be allocated for the attainment of the goal, should also be identifiable and measurable quantitatively. They must be in a limited supply. The relationships representing the objective as also the resource limitation considerations, represented by the objective function and constraints equations, or inequalities, respectively, must be linear in nature. There should be a series of feasible alternative courses of action available to the decision maker which are determined by resource constraint.

General Statement of LPP

Maximize Subject to c1x1 + c2 x2 + ............. + cn xn objective function

a11x1 + a12 x2 + ........... + a1n xn b1 a21x1 + a22 x2 + ........... + a2n xn b2 ... Constraints ... am1x1 + am2 x2 + ........... + amn xn bm x1, x2 ,............, xn 0 Non-negativity Restriction

Summary of Model Formulation Steps

Step 1 : Clearly define the decision variables Step 2 : Construct the objective function Step 3 : Formulate the constraints

A Maximization Problem

Product mix problem - Beaver Creek Pottery Company

Beaver Creek Pottery Company is a small crafts operation run by tribal council. The company employs skilled artisans to produce clay bowls and mugs with authentic design and colours. The two primary resources of the company are special pottery clay and skilled labour. Given these limited resources, the company desires to know how many bowls and mugs to produce each day in order to maximize profit.

The two products have the following resource requirements for production and profit per item produced (i.e., the model parameters):
Resource Requirements Labor Clay Profit (hr/unit) (lb/unit) ($/unit) 1 2 4 3 40 50

Product Bowl Mug

LP Model Formulation
Resource Availability: Decision Variables: Objective Function: Resource Constraints: Non-Negativity Constraints: 40 hrs of labor per day 120 lbs of clay

x1 = number of bowls to produce per day x2 = number of mugs to produce per day Maximize Z = $40x1 + $50x2 Where Z = profit per day

1x1 + 2x2 40 hours of labor 4x1 + 3x2 120 pounds of clay x1 0; x2 0

Complete Linear Programming Model

M aximize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

Feasible Solutions
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

Infeasible Solutions
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.

Coordinate Axes Graphical Solution of Maximization Model

M axim ize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

M axim ize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

Graph of Labor Constraint

M axim ize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

Clay Constraint Area

M axim ize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

Graph of Both Model Constraints

Extreme (Corner) Point Solutions

M axim ize Z = $ 40 x1 + $ 50 x 2 subject to 4 x1 + 3 x 2 120 x1 , x 2 0 1 x1 + 2 x 2 40

Solutions at All Corner Points

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.

Point

Solution values

Slack

x1 = 0 bowls, x2 = 20 mugs

$ 1,000

s1 = 0 hr; s2 = 60 lb

x1 = 24 bowls, x2 = 8 mugs x1 = 30 bowls, x2 = 0 mugs

$ 1, 360

s1 = 0 hr; s2 = 0 lb

$ 1,200

s1 = 10 hr; s2 = 0 lb

Linear Programming Model: Standard Form

Maximize Z = $40 x1 + $50 x2 + 0s1 + 0s2 subject to 4 x1 + 3x2 + s2 = 120 x1 ,x2 ,s1 ,s2 0 1x1 + 2 x2 + s1 = 40

Solution Points A, B, and C with Slack

A Minimization Problem

Fertilizing Farmers Field

A farmer is preparing to plant a crop in the spring and needs to fertilize a field. There are two brands of fertilizer to choose from, Super-gro and Crop-quick. Each brand yields a specific amount of nitrogen and phosphate per bag, as follows:
Chemical Contribution Brand Super-gro Crop-quick Nitrogen (lb/bag) 2 4 Phosphate (lb/bag) 4 3

LP Model Formulation
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)

LP Model Formulation and Constraint Graph

Minimize Z = $6 x1 + $3x2 subject to 2 x1 + 4 x2 16 lb. of nitrogen x1 ,x2 0

4 x1 + 3x2 24 lb. of phosphate

Graph of Both Model Constraints

Feasible Solution Area

Minimize Z = $6 x1 + $3x2 subject to 2 x1 + 4 x2 16 lb. of nitrogen x1 ,x2 0

4 x1 + 3x2 24 lb. of phosphate

Feasible Solution Area

Optimal Solution Point

Minimize Z = $6 x1 + $3x2 subject to 2 x1 + 4 x2 16 lb. of nitrogen x1 ,x2 0

4 x1 + 3x2 24 lb. of phosphate

Surplus Variables
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)

Linear Programming Model: Standard Form

Minimize Z = $6 x1 + $3 x2 + 0 s1 + 0 s2 subject to 2 x1 + 4 x2 s1 = 16 x1 ,x2 ,s1 ,s2 0 4 x1 + 3 x2 s2 = 24

Par Inc. Ltd. A Maximization Problem

Par, Inc., is a small manufacturer of golf equipment and supplies whose management has decided to move into the market for medium and high priced golf bags. Pars distributor is enthusiastic about the new product line and has agreed to buy all the golf bags Par produces over the next three months. After a thorough investigation of the steps involved in manufacturing a golf bag, management determined that each golf bag produced will require the following operations:

1. 2. 3. 4.

Cutting and dyeing the material Sewing Finishing Inspection and Packaging The director of manufacturing analyzed each of the operations and concluded that if the company produces a medium-priced standard model, each bag will require 7/10 hour in the cutting and dyeing department, in the sewing department, 1 hour in the finishing and 1/10 hour in the inspection and packaging department.

The more expensive deluxe model will require 1 hour for cutting and dyeing, 5/6 hour of sewing, 2/3 hour of finishing, and hour for inspection and packaging.
Production Time (hours)
Standard Bag 7/10 1/2 1

Department Sewing

Cutting and Dyeing Finishing

Deluxe Bag 5/6 1

Inspection and Packaging

1/10

2/3

1/4

Pars Production is constrained by a limited number of hours available in each department. After studying departmental workload projections, the director of manufacturing estimates that 630 hours of cutting and dyeing, 600 hours for sewing, 708 hours of finishing, and 135 hours for inspection and packaging will be available for the production of golf bags during the next three months. The accounting department analyzed the production data, assigned all relevant variable costs, and arrived at prices for both bags that will result in a profit contribution of $10 for every standard bag and $9 for every deluxe bag produced. Let us develop a mathematical model for the same.

Model Formulation
Maximize s. t.

10S +9D

(Total Profit) (Cutting and Dyeing) (Sewing) (Finishing) (Inspection and Packaging)

7 S +1D 630 10 1 5 S + D 600 2 6 2 1S + D 708 3 1 1 S + D 135 10 4

S, D 0

Graphical Solution
CORNER POINTS A (0,0) OBJECTIVE FUNCTION VALUE 0 7080 7668 4860 6780

B (708, 0) C (540, 252) D (300, 420) E (0, 540)

SLACK VARIABLES
In linear programming terminology, any unused capacity for a constraint is referred to as the slack associated with the constraint.
Constraint Hours Required For S = 540 and D = 252 7/10 (540) + 1 (252) = 630 1/2 (540) + 5/6 (252) = 480 1 (540) + 2/3 (252) = 708 1/10 (540) + 1/4 (252) = 117 Hours Available 630 600 708 135 Unused Hours 0 120 0 18

Cutting and dyeing Sewing Finishing Inspection and Packaging

Often variables called slack variables, are added to the formulation of the linear programming problem to represent the slack, or idle capacity. Unused capacity makes no contribution to profit ; thus, slack variables have coefficients of zero in the objective function . After the addition of four slack variables, denoted S1 , S 2 , S 3 andS4 , the mathematical model of Par, Inc., problem becomes.

Standard Form of Maximization Problem

Maximize Z = 10S + 9D + 0S1 + 0S2 + 0S3 + 0S4 s.t. 7 S + 1D + 1S1 = 630 10

1 5 S+ D 2 6 2 1S + D 3 1 1 S+ D 10 4

+1S2 = 600 +1S3 = 708 +1S4 = 135

S, D, S1, S2, S3, S4 0

Referring to the standard form of the Par, Inc., problem, we see that at an optimal solution (S = 540 and D = 252), the values for the slack variables are
Constraint Cutting and dyeing Sewing Finishing Inspection and Packaging Value of Slack Variable 0 120 0 18

A Simple Minimization Problem

44

M&D Chemicals produces two products that are sold as raw materials to companies manufacturing bath soaps and laundry detergents. Based on an analysis of current inventory levels and potential demand for the coming month, M&Ds management specified that the combined production for products A and B must total atleast 350 gallons. Separately, a major customers order for 125 gallons of product A must also be satisfied.

45

Product A requires 2 hours of processing time per gallon and product B requires 1 hour of processing time per gallon. For the coming month, 600 hours of processing time are available. M&Ds objective is to satisfy these requirements at a minimum total production cost. Production cost are Rs. 2 per gallon for product A and Rs.3 gallon for product B.

Minimize s. t.

2A+3B 1A 125 1A+1B 350 2A+1B 600 A, B 0

(Total Cost) (Demand for product A) (Total Production) (Processing Time)

Graphical Solution
CORNER POINTS A (125, 225) B (125, 350) C (250, 100) OBJECTIVE FUNCTION VALUE 925 1300 800

SURPLUS VARIABLES
In linear programming terminology, any excess quantity corresponding to constraint is referred to as the surplus.
Constraint Production For A = 250 and B = 100 1 (250) 1 (250) + 1 (100) 2 (250) + 1 (100) Resource Available 125 350 600 Excess Capacity 125 0 0

Demand for Product A Total production Processing Time

Standard Form Of M&D Chemicals Problem

Minimize 2A+3B + 0S1 + 0S2 + 0S3 s. t.

1A S1 =125 1A+1B 2A+1B A, B, S1, S2, S3 0 S2 = 350 + S3 = 600

Simple Maximization Problem

Max Z = 8 x1 + 5 x2 s.t. 2 x1 + x2 500 x1 150

x1 ,x2 0

x2 250

Simple Minimization Problem

Min Z = 3x1 + 2.5 x2 s.t. 2 x1 + 4 x2 40 3x1+2 x2 50 x1 ,x2 0

Mixed Constraint Problem

Max Z = 9,00,000 x1 + 3,00,000 x2 s.t. 5x1 + 2 x2 20 x2 5 3 x1

x1 ,x2 0

Infeasible Solution
Max Z = 4x1 + 2 x2 s.t. 2 x1 + 3x2 18 x1 + x2 10 x1 ,x2 0

Unbounded Solution
Max Z = 2 x1 + 2 x2 s.t. x1 x2 1 x1 ,x2 0 x1 + x2 3

Multiple Optimal Solution

Max Z = 100 x1 + 40 x2 s.t. 5 x1 + 2 x2 1000 3x1 + 2 x2 900 x1 + 2 x2 500 x1 ,x2 0