CH4003D
PROCESS OPTIMIZATION
Linear Programming (LP) – 1
Introduction
• Linear Programming Problem (LPP) – Problem of minimizing (or maximizing) a
linear objective (cost) function subject to linear equality and/or inequality
constraints.
• Examples in plant management
– Assign employees to schedules so that the workforce is adequate each day of the week
and worker satisfaction and productivity are as high as possible.
– Select products to manufacture in the upcoming period, taking best advantage of existing
resources and current prices to yield maximum profit.
– Find a pattern of distribution from plants to warehouses that will minimize costs within the
capacity limitations.
– Submit bids on procurement contracts to take into account profit, competitors' bids, and
operating constraints.
Diet Problem – An Example Problem
• Assume that there are 𝑛 different food types available. The 𝑗th food sells at a price 𝑐𝑗 per
unit. There are 𝑚 basic nutrients. Assume that each unit of food 𝑗 contains 𝑎𝑖𝑗 units of the
𝑖th nutrient. To achieve a balanced diet, you must receive atleast 𝑏𝑖 units of the 𝑖th
nutrient per day. Determine the number of units of the various food types to be included
in the diet to minimize the total cost of the diet.
• Decision variables?
• No of units of the various food types to be included in the diet
• Let 𝑥𝑗 be the no of units of food 𝑗 to be included in the diet
• Objective function?
• 𝑓(𝑥1 , 𝑥2 , … 𝑥𝑛 ) = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
• Constraints?
• Minimum nutritional requirements
Diet Problem – An Example Problem
• Minimum nutritional requirements
• Inequality constraints
• 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1
• 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2
• ⋮
• 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≥ 𝑏𝑚
• Non-negativity constraints
• 𝑥1 ≥ 0
• 𝑥2 ≥ 0
• ⋮
• 𝑥𝑛 ≥ 0
Standard Form of LPP
Standard Form of LPP
Standard Form of LPP
• Constraints: 𝐴𝑥 = 𝑏
– If any of the above equations were redundant, that is, linear combinations of the
others, they could be deleted without changing any solutions of the system.
i.e. 𝑅𝑎𝑛𝑘 𝐴 = 𝑚
– If there is no solution there can be no optimization.
i.e. when 𝑚 > 𝑛
– If there is only one solution, there can be no optimization.
i.e. when 𝑚 = 𝑛
– Optimization is required for getting the solution when there are more decision
variables than the number of independent equations.
i.e. when there are infinite solutions for 𝐴𝑥 = 𝑏
i.e. when 𝑚 < 𝑛
Transformation of LPP to Standard Form
• Maximization problem
– Maximization of an objective function, 𝑓(𝑥) is equivalent to minimization of −𝑓(𝑥)
• Inequality constraints
– If the inequality is ≤, a slack variable (non-negative) can be added to L.H.S. to make it an
equality.
– If the inequality is ≥, a surplus variable (non-negative) can be deducted from L.H.S. to
make it an equality.
• Unconstrained decision variables
– When the decision variable is unrestricted (not restricted to be non-negative)
– An unrestricted variable can be expressed as the difference between two non-negative
variables.
Graphical Solution of LPP
• For two-dimensional problems
• Plot all the constraints and shade the infeasible regions.
– For inequality constraints, plot the line for the equality constraint and check which half
of the plane is feasible/infeasible.
• Plot two contours of constant value of the objective function
– Equate the objective function to a constant and plot the line
– The second line will be parallel to the first line
• Move the contour in the desired direction to hit the maximum/minimum of
the objective function value in the feasible region.
Graphical Solution of LPP – An Example
• Maximize: 𝑓 𝑥 = 𝑥1 + 3𝑥2
• Subject to: 𝑥1 − 𝑥2 ≥ −1
• 𝑥1 + 𝑥2 ≤ 2
• 𝑥1 ≥ 0, 𝑥2 ≥ 0
• Extreme points, corner
points, or vertices
• For contours of 𝑓 𝑥
• 𝑥1 + 3𝑥2 = 𝑐
Graphical Solution of LPP – An Example
• Maximize: 𝑓 𝑥 = 𝑥1 + 3𝑥2
• Subject to: 𝑥1 − 𝑥2 ≥ −1
• 𝑥1 + 𝑥2 ≤ 2
• 𝑥1 ≥ 0, 𝑥2 ≥ 0
• Extreme points, corner
points, or vertices
• For contours of 𝑓 𝑥
• 𝑥1 + 3𝑥2 = 𝑐
