Linear Programming Model Two-Variable LP Model
A linear programming problem (LP) is an optimization
problem for which we do the following: · In mathematics, linear programming (LP) is a
1. Attempt to maximize (or minimize) a linear function technique for optimization of a linear objective
(called the objective function) of the decision variables. function, subject to linear equality and linear inequality
2. The values of the decision variables must satisfy a set of constraints.
constraints. · We will study the graphical solution of two-variables
3. Each constraint must be a linear equation or linear LP.
inequality. · The two-variables problem hardly exist in practice.
4. A sign restriction is associated with each variable.
· The study will provide an introduction to the general
simplex algorithm in chapter 3
25 26
Mathematical Formulation of LP Model Example 1: The Reddy Mikks Company
Step 1
• Reddy Mikks produces both interior and exterior paints from two
· Study the given situation
raw materials M1 and M2
· Find the key decision to be made
· Identify the decision variables of the problem
Step 2
· Formulate the objective function to be optimized
Step 3
· Formulate the constraints of the problem
• Daily demand for interior paint cannot exceed that of exterior paint
Step 4
by more than 1 ton
· Add non-negativity restrictions or constraints
• Maximum daily demand of interior paint is 2 tons
The objective function , the set of constraints and the non-negativity • Determine the optimum product mix of interior and exterior paints
restrictions together form an LP model. that maximizes the total daily profit
27 28
Decision Variables The Objective Function
• The first step in the development of the model is the • The company wants to maximize (i.e., increase as
definition of the decision variables. much as possible) the total daily profit of both paints.
• We need to determine the daily amounts to be produced • Given that the profits per ton of exterior and interior
of exterior and interior paints paints are 5 and 4 (thousand), respectively:
• We define the variables as: – Total profit from exterior paint = 5ݔ1
ݔ1 = Tons produced daily of exterior paint – Total profit from interior paint = 4ݔ2
ݔ2 = Tons produced daily of interior paint • Maximize the total profit z = 5ݔ1 + 4ݔ2
• Next, we construct the constraints that restrict raw
material usage and product demand
29 30
Constraints Constraints
• The raw material restrictions are expressed verbally as • The excess of the daily production of interior over
– usage of raw materials ≤ maximum raw material available exterior paint should not exceed 1 ton, hence:
• The usage of raw material M1 by both paints is: 2 - 1 £1
6ݔ1 + 4ݔ2 tons/day • The maximum daily demand of interior paint is limited
to 2 tons, hence:
• The usage of M2 by both is:
2 £ 2
ݔ1 + 2ݔ2 tons/day
• An implicit restriction is that variables cannot assume
• The daily availabilities of raw materials Ml and M2 are negative values:
limited, hence we have to have:
1 , 2 ³0
6 1 +4 2 £ 24 1 +2 2 £6
31 32
Complete Reddy Mikks Model Reddy Mikks Model Solution
· Maximize · Any values of the variables that satisfy all five
=5 1 +4 2 constraints constitute a feasible solution.
· Subject to · The goal is to find the best feasible solution, or the
6 +4 £ 24 optimum, that maximizes the total profit.
1 2
· We need to know how many feasible solution for Reddy
1 +2 2 £6
Mikks model.
2 - 1 £1 · We have a huge number of possibilities we need to try.
2 £2 · Graphical solution may leads us to the best solution.
1 , 2 ³0
33 34
Graphical Solution Graphical Solution
• The graphical procedure includes two steps: Determination of the Feasible Solution Space
• The nonnegativity of the variables restricts the
1. Determination of the feasible solution space.
solution space area to the first quadrant of the x-y
2. Determination of the optimum solution from among plane that lies above the x1-axis and to the right of
all the feasible points in the solution space. the x2-axis:
1, 2 ³ 0
• We will see how to maximize and minimize the
feasible solution. • Replace each inequality with an equation and then
graph the resulting straight line by locating two
distinct points on it
35 36
Graphical Solution Graphical Solution
6 1 +4 2 £ 24 ق6 1 +4 2 = 24 A solution is any
specification of values for
Constraint 2: 2X1 + X2 £ 8 the decision variables.
1 +2 2 £6ق 1 +2 2 =6 Constraint 3: -X1 + X2 £ 1
X2 A feasible Solution is a
2 - 1 £1ق 2 - 1 =1 solution for which all the
constraints are satisfied.
2 £2ق 2 =2 The feasible region is the
set of all feasible solutions.
• Determine the feasible side by choosing (0, 0) point as a Constraint 4: X2 £ 2 Notice that the feasible
region is convex
reference point.
• Draw a line for each equation by taking two values for Constraint 1: X1 + 2X2 £ 6
ݔ1 and ݔ2 Feasible
Region
• Replace each inequality with an equation and then
graph the resulting straight line by locating two distinct 1 2 3 4 5 6 7 X1
0 + 2(0) £ 6
points on it
37 38
Graphical Solution Graphical Solution
Determination of the Optimum Solution
• Identify the direction in which the profit function
z = 5 ݔ1 + 4 ݔ2 increases by assigning arbitrary
increasing values to z.
• Graph the resulting lines.
٣٩
40
Graphical Solution Graphical Solution
• The optimum solution is always associated with a
corner point of the solution space.
• The solution space ABCDEF with infinite numbers
of solution replaced with finite number of solution
points.
• This is the key for the development of general
algebraic algorithm called the Simplex method.
• Will study it in chapter 3
41 42
Example 2: Minimization Model Example 2: Minimization Model
• A farm uses at least 800 kg of feed daily, which is a mixture of • The first step in the development of the model is the
corn and soybean meal with the following composition: definition of the decision variables.
• The decision variables of the model are:
ݔ1 = kg of corn in the daily mix
ݔ2 = kg of soybean meal in the daily mix
• The objective is to minimize the total cost
• The dietary requirements of the feed are at least 30% protein and
at most 5% fiber Minimize
• The farm wants to determine the daily minimum cost feed mix. = 0.3 1 + 0.9 2
43 44
Example 2: Minimization Model
The Model
Constraints · Minimize
• The farm needs 800 kg of feed a day: = 0.3 1 + 0.9 2
· Subject to
+ ³ 800
1 2
1 + 2 ³ 800
• The other restrictions on the mix are:
0.21 1 - 0.3 2 £0
0.09 1 + 0.6 2 ³ 0.3( 1 + 2 ) 0.03 - 0.01 ³0
1 2
0.02 1 + 0.06 2 £ 0.05( 1 +2 2 ) , ³0
1 2
45 46
Special Cases
Graphical Solution
· Alternate Optimal Solutions
In the graphical method, if the objective function line is
parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions, with all
points on this line segment being optimal.
· Infeasibility
A linear program which is over-constrained so that no point
satisfies all the constraints is said to be infeasible.
· Unbounded
For a max (min) problem, a linear programming problem is
said to have unbounded solution if its solution can be made
infinitely large (small) without violating any of its constraints
in the problem.
47 48
Example: Infeasible Problem
Example with Multiple Optimal Solutions
· Solve graphically for the optimal solution:
ݔ2 ݖ1 ݖ2 ݖ3
Maximize z = 3x1 – x2 Max = ݖ2ݔ1 + 6 ݔ2
4
3 subject to 15x1 – 5x2 £ 30 s.t. 4ݔ1 + 3ݔ2 < 12
2
10x1 + 30x2 £ 120 2ݔ1 + ݔ2 > 8
1
x1 ³ 0, x2 ³ 0
ݔ1, ݔ2 > 0
0
0 1 2 3 4 ݔ1
49 50
Example: Infeasible Problem Example: Unbounded Problem
· There are no points that satisfy both constraints, hence
this problem has no feasible region, and no optimal · Solve graphically for the optimal solution:
solution.
x2 Max z = 3 x1 + 4 x2
8 2x1 + x2 > 8 s.t. x1 + x2 > 5
3x1 + x2 > 8
4x1 + 3x2 < 12
4
x 1, x 2 > 0
x1
3 4
51 52
Example: Unbounded Problem Computer Solution of LP Problem
· The feasible region is unbounded and the objective function line
can be moved parallel to itself without bound so that z can be
increased infinitely. · Excel Solver
x2
3x1 + x2 > 8 · Tora
8
5 · Lingo
x1 + x2 > 5
x1
2.67 5
53 54
