Linear Programming
1.  OM applications
2.  Problem formulation
3.  Graphical solution method
4.  Corner point solution method
5.  Using excel
6.  Sensitivity analysis

Linear Programming: related mathematical techniques used to allocate limited resources among competing demands in an optimal way

Applications
1.  Resource allocation
2.  Facility location

Problem formulation
1.  problem characteristics
2.  problem formulation guidelines
3.  two types of problems
4.  exercise

Problem characteristics

• Max/Min an objective function
• Subject to a set of constraints in the form of equations/inequalities
• Linear relationships among various elements
• Continuous, non-negative variables

Guidelines on model formulation

• Identify the objective of interests
• Identify the constraints

     Requirements >=
     Limitation <=
     Equal =

• Identify the decision variables
• Express the objective function in terms of the decision variables
• Express the constraints in terms of the decision variables
• Check for consistency of units

Two types of problems

Blending (Minimization problem)

Product mix (Maximization problem)

Blending example:

Feed	Calories per lb	Mineral units per lb	Vitamin units per lb	Cost per lb
Oat	100	200	200	5 cents
Corn	100	400	100	3 cents
Min. Requirement	4000	10000	5000

Question: How many pounds of oat and corn should be fed to each cattle per day to minimize feed cost?

Formulation:

Objective: minimize feed cost

Constraints: calories, mineral, and vitamin requirements

Decision variables:
     Let X1 be the pounds of oat to be used
     Let X2 be the pounds of corn to be used

Minimize C = 5X1 + 3 X2

s.t.

100X1 + 100X2 >= 4000 [calorie requirement]

200X1 + 400X2 >= 10000 [mineral requirement]

200X1 + 100X2 >= 5000 [vitamin requirement]

X1, X2 >= 0 [non-negativity constraint]

Product Mix example:

	BeltA	BeltB	Availability
Buckle A	1		400
Buckle B		1	700
Leather (yd)	1	1	800
Labor (hr)	1	2	1000
Profit ($)	40	30

Question: How many belts of each type should the company make per day in order to maximize profit?

Formulation:

Objective: Maximize profit

Constraints: resource limitation (buckle, leather, and labor)

Decision variables:
     Let X1 be the number of type A belts to be made per day
     Let X2 be the number of type B belts to be made per day

Maximize Z = 40X1 + 30X2

s.t.

X1 <= 400 [buckle A availability]

X2 <= 700 [buckle B availability]

X1 + X2 <= 800 [leather availability]

X1 + 2X2 <= 1000 [labor availability]

X1, X2 >= 0 [non-negativity constraint]

Exercise:
pg.702, problems 4a, 5a, 6a, 7

Graphical solution method
1.  Assign X1 and X2 to the vertical and horizontal axes
2.  Plot constraint equations
3.  Determine the area of feasibility
4.  Plot the objective function
5.  Find the optimum point

Corner point solution method
1.  Find the co-ordinates of each corner point (by simultaneously solving the equations of a pair of intersecting lines)
2.  Substitute the values of the co-ordinates in the objective function

Exercise:
Pg.701, problems 1, 2, 4b, 5b, 6b