Chapter 2: �Modeling with Linear Programming & sensitivity analysisrt

A lecture by:

Dr. Moayad Tanash

​

​

LINEAR PROGRAMMING (LP)

-In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints.

​

-Linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

​

TWO-VARIABLE LP MODEL�Example 2.1-1 (The Reddy Mikks Company)

Reddy Mikks produces both interior and exterior paints from two raw materials M1 and M2

Tons of raw material per ton of

Exterior paint Interior paint Maximum daily availability (tons)

Raw material M1 6 4 24

Raw material M2 1 2 6________

Profit per ton ($1000) 5 4

-Daily demand for interior paint cannot exceed that of exterior paint by more

than 1 ton

-Maximum daily demand of interior paint is 2 tons

-Reddy Mikks wants to determine the optimum product mix of interior and

exterior paints that maximizes the total daily profit

​

Solution:

Let x1 = tons produced daily of exterior paint

x2 = tons produced daily of interior paint

Let z represent the total daily profit (in thousands of dollars)

​

Objective:

??

​

Solution:

Let x1 = tons produced daily of exterior paint

x2 = tons produced daily of interior paint

Let z represent the total daily profit (in thousands of dollars)

​

Objective:

Maximize z = 5 x1 + 4 x2

​

(Usage of a raw material by both paints) < (Maximum raw material

availability)

Usage of raw material M1 per day = 6x1 + 4x2 tons

Usage of raw material M2 per day = 1x1 + 2x2 tons

- daily availability of raw material M1 is 24 tons

- daily availability of raw material M2 is 6 tons

​

Restrictions:

6x1 + 4x2 < 24 (raw material M1)

​

x1 + 2x2 < 6 (raw material M2)

- Difference between daily demand of interior (x2) and exterior (x1) paints does not exceed 1 ton,

so x2 - x1 < 1

• Maximum daily demand of interior paint is 2 tons,

so x2 < 2

- Variables x1 and x2 cannot assume negative values,

so x1 > 0 , x2 > 0

​

​

Complete Reddy Mikks model:

Maximize z = 5 x1 + 4 x2 (total daily profit)

subject to

6x1 + 4x2 < 24 (raw material M1)

x1 + 2x2 < 6 (raw material M2)

x2 - x1 < 1

x2 < 2

x1 > 0

x2 > 0

- Objective and the constraints are all linear functions in this

example.

​

7

Properties of the LP model:

Linearity implies that the LP must satisfy three basic properties:

​

 1) Proportionality:

- Contribution of each decision variable in both the objective

function and constraints to be directly proportional to the

value of the variable

2) Additivity:

- Total contribution of all the variables in the objective function

and in the constraints to be the direct sum of the individual

contributions of each variable

​

Properties of the LP model:

3) Certainty:

- All the objective and constraint coefficients of the LP model are

deterministic (known constants)

- LP coefficients are average-value approximations of the probabilistic

distributions

- If standard deviations of these distributions are sufficiently small , then the

approximation is acceptable

- Large standard deviations can be accounted for directly by using stochastic LP

algorithms or indirectly by applying sensitivity analysis to the optimum solution

Feasible Solutions for Linear Programs:

​

• The set of all points that satisfy all the constraints of the model is called

​

​

Otherwise, the solution is

​

FEASIBLE SOLUTION

INFEASIBLE SOLUTION

Feasible Solutions for Linear Programs:

​

• The set of all points that satisfy all the constraints of the model is called

​

​

Otherwise, the solution is

​

FEASIBLE SOLUTION

INFEASIBLE SOLUTION

12

Feasible

X2

Infeasible

X1

Type of feasible points

• Interior point: satisfies all constraint but non with equality.
• Boundary points: satisfies all constraints, at least one with equality
• Extreme point: satisfies all constraints, two with equality.

14

X2

Infeasible

X1

*

​

*

*

*

*

*

*

*

*

​

*

​

*

* Extreme point

​

* Boundary point

​

* Interior point

​

Optimal Solution

If a linear programming has a unique optimal solution , then one of the extreme point is optimal.

Summery of graphical solution procedure

1- graph constraint to find the feasible point

2- set objective function equal to an arbitrary value so that line passes through the feasible region.

3- move the objective function line parallel to itself until it touches the last point of the feasible region .

4- solve for X1 and X2 by solving the two equation that intersect to determine this point

5- substitute these value into objective function to determine its optimal solution.

​

​

16

Complete Reddy Mikks model:

Maximize z = 5 x1 + 4 x2 (total daily profit)

​

subject to

6x1 + 4x2 < 24 (raw material M1)

x1 + 2x2 < 6 (raw material M2)

x2 - x1 < 1

x2 < 2

x1 > 0

x2 > 0

​

17

2.2.1 Solution of a Maximization model

Example 2.2-1 (Reddy Mikks model)

Step 1:

1) Determination of the feasible solution space:

      - Find the coordinates for all the 6 equations of the 

restrictions (only take the equality sign)

6x1 + 4x2 < 24

x1 + 2x2 < 6

x2 - x1 < 1

x2 < 2

x1 > 0

x2 > 0

​

​

18

1

2

3

4

5

6

- Change all equations to equality signs

6x1 + 4x2 = 24

x1 + 2x2 = 6

x2 - x1 = 1

x2 = 2

x1 = 0

x2 = 0

​

​

​

19

1

2

3

4

5

6

- Plot graphs of x1 = 0 and x2 = 0

- Plot graph of 6x1 + 4x2 = 24 by using

the coordinates of the equation

Assume x1 =0 🡺 x2 = 6

Assume x2 = 0 🡺 x1 = 4

​

​

- Plot graph of x1 + 2x2 = 6 by using

the coordinates of the equation

Assume x1 =0 🡺 x2 =3

Assume x2=0 x1 = 6

​

​

​

- Plot graph of x2 - x1 = 1 by using

the coordinates of the equation ( x1=-1, x2=0) and (x1=0,x2=1)

- Plot graph of x2 = 2 by using

the coordinates of the equation

​

​

​

​

​

​

- Now include the inequality of all the 6 equations

- Inequality divides the (x1, x2) plane into two half spaces , one on

each side of the graphed line

- Only one of these two halves satisfies the inequality

- To determine the correct side , choose (0,0) as a reference point

- If (0,0) coordinate satisfies the inequality, then the side in which

(0,0) coordinate lies is the feasible half-space , otherwise the

other side is

- If the graph line happens to pass through the origin (0,0) , then

any other point can be used to find the feasible half-space

Step 2:

2) Determination of the optimum solution from among

all the feasible points in the solution space:

- After finding out all the feasible half-spaces of all

the 6 equations, feasible space is obtained by the

line segments joining all the corner points A, B, C,

D ,E and F

- Any point within or on the boundary of the

solution space ABCDEF is feasible as it satisfies all

the constraints

- Feasible space ABCDEF consists of infinite number

of feasible points

- To find optimum solution identify the direction in which the

maximum profit increases , that is z = 5x1 + 4x2

- Assign random increasing values to z , z = 10 and z = 15

5x1 + 4x2 = 10

5x1 + 4x2 = 15

- Plot graphs of above two equations

- Thus in this way the optimum solution occurs at corner point C which is the

point in the solution space

- Any further increase in z that is beyond corner point C will put points

outside the boundaries of ABCDEF feasible space

- Values of x1 and x2 associated with optimum corner point C are

determined by solving the equations and

6x1 + 4x2 = 24

x1 + 2x2 = 6

- x1 = 3 and x2 = 1.5 with z = 5 X 3 + 4 X 1.5 = 21

- So daily product mix of 3 tons of exterior paint and 1.5 tons of interior paint

produces the daily profit of $21,000 .

​

​

- Important characteristic of the optimum LP solution is that it is always associated with a corner point of the solution space (where two lines intersect)

- This is even true if the objective function happens to be

parallel to a constraint

- For example if the objective function is,

z = 6x1 + 4x2

- The above equation is parallel to constraint of equation

- So optimum occurs at either corner point B or corner point

C when parallel

- Actually any point on the line segment BC will be an

alternative optimum

- Line segment BC is totally defined by the corner points

B and C

​

Corner points (x1,x2) z = 600 x1 + 400 x2

A (0, 40) 16000

B (12,4) 8800

C (22,0) 13200

​

• In 12 days all the three types of bottles (Coca-cola, Fanta, Thumps-up) are produced by plant at Coimbatore
• In 4 days all the three types of bottles (Coca-cola, Fanta, Thumps-up) are produced by plant at Chennai
• So minimum production cost is 8800 units to meet the market demand of all the three types of bottles (Coca-cola, Fanta, Thumps-up) to be produced in April

​

​

28

- Since optimum LP solution is always associated with a corner point of

the solution space, so optimum solution can be found by enumerating all

the corner points as below:-

______________Corner point (x1,x2) z_________________

A (0,0) 0

B (4,0) 20

C (3,1.5) 21 (optimum solution)

D (2,2) 18

E (1,2) 13

F (0,1) 4

​

​

- As number of constraints and variables increases , the number of corner

points also increases

2.2.2 Solution of a Minimization model

Example 2.2-3

• Firm or industry has two bottling plants
• One plant located at Coimbatore and other plant located at Chennai
• Each plant produces three types of drinks Coca-cola , Fanta and Thumps-up

​

​

Number of bottles produced per day

by plant at

Coimbatore Chennai______________________

Coca-cola 15,000 15,000

Fanta 30,000 10,000

Thumps-up 20,000 50,000_______________________

Cost per day 600 400

(in any unit)

​

• Market survey indicates that during the month of April there will be a demand of 200,000 bottles of Coca-cola , 400,000 bottles of Fanta , and 440,000 bottles of Thumps-up
• For how many days each plant be run in April so as to minimize the production cost , while still meeting the market demand?

31

Solution:

Let x1 = number of days to produce all the three types of bottles by plant

at Coimbatore

x2 = number of days to produce all the three types of bottles by plant

at Chennai

​

Objective:

Minimize z = 600 x1 + 400 x2

Constraint:

15,000 x1 + 15,000 x2 > 200,000

30,000 x1 + 10,000 x2 > 400,000

20,000 x1 + 50,000 x2 > 440,000

x1 > 0

x2 > 0

​

32

1

2

3

4

5

33