OPERATIONS RESEARCH
PART 2: LINEAR PROGRAMMING
TRUNG-HIEP BUI
scv.udn.vn/buitrunghiep | [email protected] | 0935-743-555
LINEAR PROGRAMMING
CONTENT
Introduction to Linear Programming
General Linear Programming Notations
A Simple Maximization Problem
Graphical Solution Procedure
Extreme Points and the Optimal Solutions
Computer application for solving Linear problems
LEARNING OUTCOMES
LINEAR PROGRAMMING
SOME LINEAR PROGRAMMING PROBLEMS
1. A manufacturer wants to develop a production schedule and an inventory policy that will satisfy sales
demand in future periods. Ideally, the schedule and policy will enable the company to satisfy demand and at the
same time minimize the total production and inventory costs.
2. A financial analyst must select an investment portfolio from a variety of stock and bond investment
alternatives. The analyst would like to establish a portfolio that maximizes the return on investment.
3. A marketing manager wants to determine how best to allocate a fixed advertising budget among
alternative advertising media such as radio, television, online, and magazines. The manager would like to
determine the media mix that maximizes advertising effectiveness.
4. A company has warehouses in a number of locations. For a set of customer demands, the company would
like to determine how much each warehouse should ship to each customer so that total transportation costs are
minimized.
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM
A manufacturer of golf equipment produces 02 types of golf bag (Standard | Deluxe).
A profit contribution of $10 for every standard bag and $9 for every deluxe bag produced.
CONSTRAINTS
Nonnegativity constraints: nonnegative values for the decision variables.
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: PROBLEM FORMULATION
A manufacturer of golf equipment produces 02 types of golf bag (Standard | Deluxe).
A profit contribution of $10 for every standard bag and $9 for every deluxe bag produced.
Define the Decision Variables
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
Solution points for the Two-Variable Problem
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
The Cutting and Dyeing Constraint Line
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
The Cutting and Dyeing Constraint Line
Infeasible solution
Infeasible region
Feasible solution
Feasible region
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
Other Constraint Lines
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
Combined-constraint graph showing the Feasible region
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
1800$ Profit Line: 10S + 19D = 1800 $
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
1800$ | 3600$ | 5400$ Profit Lines
Let P represent Total Profit Contribution
The slope-intercept form
of the linear equation relating S and D.
LINEAR PROGRAMMING
A SIMPLE MAXIMIZATION PROBLEM: GRAPHICAL SOLUTION PROCEDURE
Optimal Solution
Optimal solution point is on both:
The Cutting and Dying constraint line
The Finishing constraint line
The slope-intercept form
of the linear equation relating S and D.
LINEAR PROGRAMMING
SLACK VARIABLE
Optimal Solution: S = 540 and D =252
The 120 hours of unused sewing time and 18 hours of unused inspection and packaging time
are referred to as slack for the two departments.
LINEAR PROGRAMMING
SLACK VARIABLE
Whenever a linear program is written in a form with all constraints expressed as equalities,
it is said to be written in STANDARD FORM.
SLACK VARIABLES are added to the formulation of a linear
programming problem to represent the slack, or idle capacity.
Unused ((idle) capacity makes no contribution to profit;
thus, slack variables have coefficients of zero in the objective function.
Adding 4 slack variables, denoted as S1, S2, S3, and S4.
Binding constraint
Non-binding constraint
LINEAR PROGRAMMING
EXTREME POINTS AND THE OPTIMAL SOLUTION
Suppose that the profit contribution for standard golf bag is reduced from $10 to $5 per bag,
while the profit contribution for the deluxe golf bag and all the constraints remain unchanged.
The revised objective function: Max (5S + 9D)
Without any change in the constraints, the feasible region does not change.
However, the profit lines have been altered to reflect the new objective function.
The reduced profit contribution
for the standard bag caused a
change in the optimal solution.
LINEAR PROGRAMMING
EXTREME POINTS AND THE OPTIMAL SOLUTION
The optimal solution to a linear program can be found at an extreme point of the feasible region.
We can find the optimal solution by evaluating the 5 extreme-point solutions
and selecting the one that provides the largest profit contribution.
LINEAR PROGRAMMING
COMPUTER SOLUTION
.
LINEAR PROGRAMMING
COMPUTER SOLUTION: SOLVER ADD-IN
.
LINEAR PROGRAMMING
COMPUTER SOLUTION: SOLVER ADD-IN
.
LINEAR PROGRAMMING
COMPUTER SOLUTION: SOLVER ADD-IN
.
LINEAR PROGRAMMING
A SIMPLE MINIMIZATION PROBLEM
A manufacturer needs 02 types of products (A | B).
Demand Processing time Production cost
per gallon per gallons
Product A ≥ 125 gallons 2 hours 2$
Product B 1 hours 3$
Total ≥ 350 gallons ≤ 600 hours
VARIABLES
MATHEMATICAL MODEL
LINEAR PROGRAMMING
A SIMPLE MINIMIZATION PROBLEM
LINEAR PROGRAMMING
A SIMPLE MINIMIZATION PROBLEM
LINEAR PROGRAMMING
SURPLUS VARIABLE
Optimal Solution: A = 250 and B = 100
The production of product A exceeds its minimum level by 250 - 125 = 125 gallons.
This excess production for product A is referred to as SURPLUS.
In linear programming terminology, any excess quantity corresponding to
a ≥ constraint is referred to as SURPLUS.
LINEAR PROGRAMMING
SLACK VARIABLE & SURPLUS VARIABLE
With a ≤ constraint,
a SLACK variable can be added to the left-hand side of the inequality
to convert the constraint to equality form.
With a ≥ constraint,
a SURPLUS variable can be subtracted from the left-hand side of the inequality
to convert the constraint to equality form.
LINEAR PROGRAMMING
SLACK VARIABLE & SURPLUS VARIABLE
SURPLUS variables are given a coefficient of zero in the objective function because they have no effect on its value.
Adding 02 SURPLUS variables, denoted as S1, S2 (≥ constraint) and 01 SLACK variable, denoted as S3 (≤
constraint)
Whenever a linear program is written in a form with all constraints expressed as equalities, it has STANDARD
FORM.
LINEAR PROGRAMMING
OTHER EXAMPLE: SLACK VARIABLE & SURPLUS VARIABLE
All three constraint forms The standard-form
LINEAR PROGRAMMING
COMPUTER SOLUTION
.
LINEAR PROGRAMMING
COMPUTER SOLUTION
.
LINEAR PROGRAMMING
ALTERNATIVE OPTIMAL SOLUTIONS
.
Optimal objective function line coincides with one of the binding constraint lines
on the boundary of the feasible region.
Alternative optimal solutions
