Modelling with Linear programming MOT 3 | PDF | Equations | Variable (Mathematics)
Scribd
Upload
7 views22 pages

Modelling with Linear programming MOT 3

The document discusses a linear programming model for Reddy Mikks Company to determine the optimal product mix of interior and exterior paints to maximize daily profit. It outlines the constraints based on raw material availability and market demand, formulates the objective function, and describes the graphical and simplex methods for solving the LP problem. The goal is to find the best feasible solution that maximizes profit while adhering to the defined constraints.

Uploaded by

kv23csb0a35
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
Download as pdf or txt
7 views22 pages

Modelling with Linear programming MOT 3

The document discusses a linear programming model for Reddy Mikks Company to determine the optimal product mix of interior and exterior paints to maximize daily profit. It outlines the constraints based on raw material availability and market demand, formulates the objective function, and describes the graphical and simplex methods for solving the LP problem. The goal is to find the best feasible solution that maximizes profit while adhering to the defined constraints.

Uploaded by

kv23csb0a35
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
Download as pdf or txt
Download as pdf or txt
You are on page 1/ 22

Modelling with Linear

programming
Dr. Manjubala Bisi
The Reddy Mikks Company
Reddy Mikks produces both exterior and interior paints from two raw
materials M1 and M2. A market survey indicates that the daily
demand for interior paint can not exceed that for exterior paint by
more than 1 Ton. Also, the maximum daily demand for interior paint is
2 Ton.
Reddy Mikks wants to determine the optimum (best) product mix of
interior and exterior paints that maximizes the total daily profit.
Two-variable LP Model
Exterior Paint Interior Paint Maximum daily
(Tons of raw (Tons of raw availability
material per material per
Ton of) Ton of)

x1 6 4 24

x2 1 2 6

Profit per Ton 5 4


($)
Two-variable LP Model
Let x1 = Tons demand/ produced of exterior paint
x2 = Tons demand/produced of interior paint
Total profit = 5x1 + 4x2
Objective function is Maximize Z = 5x1 + 4x2
Two-variable LP Model
Restrictions:
(Usage of raw material by both paints) <= (Maximum raw material
availability)
Usage of raw material M1 by both paints = 6x1 + 4x2
Usage of raw material M2 by both paints = x1 + 2x2
6x1+4x2 <= 24
X1+2x2<= 6
Two-variable LP Model
From market survey:
x2- x1 <= 1
X2<=2
An implicit restriction, x1>= 0 and x2>=0
The mathematical model is:
Maximize Z = 5x1 + 4x2
Subject to
6x1+4x2 <= 24
x1+2x2 <= 6
x2- x1 <= 1
x2 <= 2
x1, x2 >= 0
Two-variable LP Model
• Any value of x1 and x2 that satisfy all five constraints constitute a
feasible solution
• Otherwise the solution is infeasible
• (x1 = 3 and x2 =1) feasible solution
• (x1 = -3 and x2 =1) infeasible solution
• The goal of the problem is to find the optimum solution (best feasible
solution that maximizes the total profit Z)
Graphical LP Solution
Two steps
• Determination of feasible solution space
• Determination of optimum solution from among all the points in the
solution space
Step 1:
First consider nonnegative constraints, x1, x2 >= 0
The solution lies in the first quadrant (above x1 axis and right of x2
axis)
Graphical LP Solution
• Replace each inequality with an equation
L1: 6x1 + 4x2 <= 24 with 6x1 + 4x2 = 24

Two distinct points are determined by setting x1 and x2 = 0


If x1 = 0, x2 = 6
If x2 =0 , x1 = 4
So the line passes through two points (0,6) and (4,0)
Graphical LP Solution
• Now due to inequality, the line divided the plane into two half spaces.
• L2: x1 + 2x2 = 6
Two distinct points are determined by setting x1 and x2 = 0
If x1 = 0, x2 = 3
If x2 =0 , x1 = 6
So the line passes through two points (0,3) and (6,0)
Graphical LP Solution
• L3: -x1 + x2 = 1
Two distinct points are determined by setting x1 and x2 = 0
If x1 = 0, x2 = 1
If x2 =0 , x1 = -1 (Infeasible solution)
• L4: x2 <= 2
• Common area is the feasible solution space.
• All points outside this area are infeasible.
Simplex Method
There are two requirements on the LP constraints
1) All the constraints are equations with non negative right hand side
2) All variables are nonnegative
Converting inequalities into equations with nonnegative RHS
• In LP model, the RHS represents the availability of a resource and the
LHS represents the usage of the resources by all the model activities
(variables)
• The excess amount of the RHS over the LHS then yields the unused
amount of resources
Simplex Method
1. 6x1 + 4x2 <= 24
<= inequality is converted to an equation as
6x1 + 4x2 + s1 = 24 , s1>= 0
The nonnegative variable s1 is the slack (unused amount) of resources
2. x1 + x2 >= 800
>= inequality is converted to an equation as
x1 + x2 - S1 = 800, S1 >= 0
The nonnegative variable S1 is the surplus (excess amount) of resources
Simplex Method
The algebraic model of LP problem with “n” variables and “m”
constraints is in the following format:

Maximize / Minimize
Z: = σ𝑛𝑗=1 𝑐𝑗𝑥𝑗
Subject to restriction : σ𝑛𝑗=1 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖, 𝑖 = 1,2, … … 𝑚.
xj >=0, j = 1,2, ----,n
Enumeration method to solve LP model
Consider the following LP model:
Maximize Z = 2x1 + 3x2
subject to 2x1 + x2 <= 4
x1 + 2x2 <= 5
x1, x2 >= 0
How many variables (n) and how many equations(m) ?
Enumeration method to solve LP model
• The LP model is represented by following m =2 equations and n = 4
variables:
2x1 + x2 + s1 = 4
x1 + 2x2 + s2 = 5
x1, x2, s1, s2 >= 0
• The basic solutions are determined by setting (n – m = 4-2 ) 2
variables equal to zero and solving for the remaining (m) 2-variable.
• If we set x1 = 0 and x2 =0, , the equation provides unique basic
solution s1 = 4 and s2 =5
Enumeration method to solve LP model
• The LP model is represented by following m =2 equations and n = 4
variables:
2x1 + x2 + s1 = 4
x1 + 2x2 + s2 = 5
x1, x2, s1, s2 >= 0
• The basic solutions are determined by setting (n – m = 4-2 ) 2 variables
equal to zero and solving for the remaining (m) 2-variable.
• If we set x1 = 0 and x2 =0, , the equation provides unique basic solution s1
= 4 and s2 =5 [corner point A (0,0)]
• If we set s1 = 0 and s2 =0, , the equation provides unique basic solution x1
= 1 and x2 =2 [corner point E (1,2)]
Enumeration method to solve LP model
• Which (n-m) variables should be set equal to zero to target a specific
corner point
• Simply consider all combinations, in which (n-m) variables equal zero
and solve the resulting equations
• Once done, the optimum solution is the feasible basic solution (
corner point) with best objective value
• To complete the transition from the graphical to algebraic solution,
the zero (n-m) variables are known as non-basic variables and the
remaining m variables are called basic variables and their solution
(obtained by solving m equations) is referred as feasible solution
Enumeration method to solve LP model
[Here we are enumerating all the basic solutions(corner points of the LP problem)]

Zero (Non- Basic variables Basic solution Associated Feasible Objective


basic corner value of Z
variables) point

(x1,x2) (s1,s2) (4, 5) A Yes 0


(x1=0,x2=0)
(x1,s1) (x2,s2) (4, -3) F No --
(x1=0,x2=4)
(x1,s2) (x2,s1) (2.5, 1.5) B Yes 7.5
(x1=0, x2=2.5)
(x2,s1) (x1,s2) (2, 3) D Yes 4
(x1=2, x2=0)
(x2,s2) (x1,s1) (5, -6) E No --
(x1=5, x2=0)

(s1,s2) (x1,x2) (1 , 2) C Yes 8


(x1=1, x2=2) (Optimum)

You might also like