Industrial & Systems Engineering

Operations Research

Chapter 2

LINEAR PROGRAMMING – LP

Assoc. Prof. Hoà Thanh Phong

Operations Research Assoc. Prof. Ho Thanh Phong 1

 LINEAR PROGRAMMING
CONTENTS
❖Introduction about LP
❖Problem Formulation
❖Solve LP using Graphical approach
❖Four Special Cases
❖Sensitivity Analysis
❖Using Lingo
❖The Simplex Method
❖Two-Phase Method
❖Simplex Method in Matrix Form
Operations Research Assoc. Prof. Ho Thanh Phong 2
 INTRODUCTION
❖ Many decisions in management are related with the
best usage resources of organizations.
❖ Manager makes Decisions in order to satisfy
Objectives, Goals of organizations.
❖ Resources: Materials, Machines, Man, Money, Time,
Space.
❖ Linear Programming (LP) is a mathematical method
that helps managers to make decision related with
Resources Allocation. (references about Prof. George
Danzit https://en.wikipedia.org/wiki/George_Dantzig
and Nobel laureate: Kantorovich)
❖ Extensively using computer.
Operations Research Assoc. Prof. Ho Thanh Phong 3
 LP PROBLEM
❖ Objective function: Maximize or Minimize some
variables, usually Profit/ Cost.
❖ Constraints: are functions show resources limitation
of companies/ organizations. The problem is to find s
solution that maximize profits (or minimize lost/cost)
in given constraints.
Form of constraint funcstionc could be:
❖ Inequality (form  or )
❖ Equality

❖ All Objective function and Constraint functions are

linear functions.

Operations Research Assoc. Prof. Ho Thanh Phong 4

Formulating LP Problems - the most important task

Example 1. ABC Furniture Company

❖Products: tables and chairs.
❖The production process for each is similar
(carpentry works, painting and varnishing)
❖ABC Furniture's problem: to determine the best
possible combination of tables chairs to
manufacture in order to reach the maximum profit.
❖The data provided in the following table

Operations Research Assoc. Prof. Ho Thanh Phong 5

 ABC Furniture Company Data

Hours required to produce 1 Available

Department unit Hours
(X1) Tables (X2) Chairs

Carpentry 4 3 240
Painting and varnishing 2 1 100
Profit per unit $7 $5

Operations Research Assoc. Prof. Ho Thanh Phong 6

Formulation
❖X1 = number of tables to be produced
❖X2 = number of chairs to be produced
❖The objective function is
Maximize profit Z = $7X1 + $5X2
Subject to:
4X1 + 3X2  240
2X1 + 1X2  100
X1 0
X2 0

Operations Research Assoc. Prof. Ho Thanh Phong 7

 Graphical Solution
❖The graphical method works only when there
are two decision variables, but it provides
valuable insight into how larger problems are
structured
❖Graphical Representation of Constraints

❖Isoprofit-line method
❖Corner points method

Operations Research Assoc. Prof. Ho Thanh Phong 8

 Graphical Solutions

100

80 A (X1 = 0, X2 = 80)
Number of Chairs - X2

60

4X1+3X2 = 240
40
4X1+3X2 <= 240

20

B (X1 = 60, X2 = 0)

0 20 40 60 80 100 120
Number of Tables - X1

Operations Research Assoc. Prof. Ho Thanh Phong 9

 100 C (X1 = 0, X2 = 100)

80 A (X1 = 0, X2 = 80)
Number of Chairs - X2

2X1+1X2 = 100
60

4X1+3X2 = 240
40

D (X1 = 50, X2 = 0)
20

Feasible B (X1 = 60, X2 = 0)

Region

0 20 40 60 80 100 120
Number of Tables - X1

Operations Research Assoc. Prof. Ho Thanh Phong 10

Solving LP graphically by Isoprofit- line method

100

80 A (X1 = 0, X2 = 80)
Number of Chairs - X2

60 I (X1 = 30, X2 = 40)

40 Max Profit = 7(30)+5(40) = 410

Feasible
Region 20
D (X1 = 50, X2 = 0)

0 20 40 60 80 100 120
Number of Tables - X1

Operations Research Assoc. Prof. Ho Thanh Phong 11

Solving LP problem by Corner-point method
❖Objective: Maximize Profit Z = 7X1 + 5X2
❖ The mathematical theory in LP shows that the
optimal solution must lie at one corner point, or
extreme point, of the feasible region

❖ At the point (0,0): Profit = 0

❖ At the point D(50,0): Profit = 7(50) + 5(0) = 350
❖ At the point A(0,80): Profit = 7(0) + 5(80) = 400
❖ At the point I(30,40):Profit = 7(30) + 5(40) = 410 *
❖ The optimal solution is I(30,40) which obtains
profit of 410
Operations Research Assoc. Prof. Ho Thanh Phong 12
 Case Study

❖All cases in book of Hamdy Taha, page 59 – 73.

❖Student read and make a short report for each
problem.

Operations Research Assoc. Prof. Ho Thanh Phong 13

 Shadow Price
Maximize profit Z = 6X1 + 7X2
Subject to:
2X1 + 3X2  24
The optimal solution is
2X1 + X2  16
X1 = 6, X2 = 4

X2
2X1+X2 <= 16
8
Units product B

6
D (X1 = 6, X2 = 4)

2X1+3X2 <= 24
4

X1

0 2 4 6 8 12
Operations Research Assoc. Prof. Ho Thanh
Units Phong
product A 14
 Shadow Price
❖ On constraint 1:
If we increase RHS by 1: 2X1 + 3X2  25
The new optimal solution is: X1= 5.75, X2 = 4.5 and
the new Z’ = 66 . The net change in profit is is $2.
This is called shadow price (marginal value or dual
price) associated with constraint 1.

• On constraint 2:If we increase RHS by 1: 2X1 + 3X2  17

The net change in profit is is $1. The shadow price
associated with constraint 2 is $1.

Operations Research Assoc. Prof. Ho Thanh Phong 15

 04 SPECIAL CASES
There are 04 special cases in LP:
❖Infeasible solutions
❖Unbounded solutions
❖Redundant constraints
❖Multiple optimal solutions

Operations Research Assoc. Prof. Ho Thanh Phong 16

 04 SPECIAL CASES
❖Case1: Infeasible
❖Infeasible solutions occurred when we have
conflicting constraints ; or
❖No solution satisfy all constraints; or
❖Can not build the feasible solutions region.

Operations Research Assoc. Prof. Ho Thanh Phong 17

 04 SPECIAL CASES
❖Exampleï:
Consider three constraints:
X 2 Regions which
Mieàn thoaû maõn raøng
4X1 + 3X2  240 100 satisfy constraints 3
buoäc thöù ba

2X1 + 1X2  100 80 A (X = 0, X = 80)

1 2

X1  80
60

40
Regions which
satisfy constraints 1 20

and 2
0 20 40 60 80 100 120 X
Operations Research Assoc. Prof. Ho Thanh Phong 18
 04 SPECIAL CASES
Case 2: Unbounded solutions
❖When value of Objective function approached to
infinity we said that the problem is unbounded or
missing one or more constraints; or
❖The LP did not provide a finite solutions, this
implies the objective function approaches to
infinity without violating any constraint. û.
❖→ Open ended problem

Operations Research Assoc. Prof. Ho Thanh Phong 19

 04 SPECIAL CASES
❖Example:
Maximize Z = 3X1 + 5X2
St:
X 2
X1 = 5

X1  5 15

X2  10 X 2 = 10

X1 + 2 X2  10 10
X1, X 2  0 Mieàn lôøi giaûi
5
X1 + 2X2 = 10

0 5 10 15 X1

Operations Research Assoc. Prof. Ho Thanh Phong 20

 04 SPECIAL CASES
Case 3: Redundancy of Constraints
❖A redundant constraint is a constraint that will
not affect to the solution space
❖In reality, this will usually happens when number
of constraints and umber of variables are very
large.

Operations Research Assoc. Prof. Ho Thanh Phong 21

 04 SPECIAL CASES
Example:
Maximize Z = 7X1 + 5X2
X

St:
2

100

4X1 + 3X2  240 80 A (X = 0, X = 80)1 2

2X1 + 1X2  100 Raøng buoäc dö: X 1<= 80

X1  80
60

40

20

0 20 40 60 80 100 X1

Operations Research Assoc. Prof. Ho Thanh Phong 22

 04 SPECIAL CASES
Case : Multiple solutions
❖When objective function and one constraint have
the same slope we will faced with the case
multiple optimal solutions

Operations Research Assoc. Prof. Ho Thanh Phong 23

 04 SPECIAL CASES
X2

❖Ví duï: 100

Maximize Z = 8X1 + 6X2

St: 80 A (X1 = 0, X2 = 80)

4X1 + 3X2  240

60
2X1 + 1X2  100
I (X1 = 30, X2 = 40)
40

20

0 20 40 60 80

Operations Research Assoc. Prof. Ho Thanh Phong 24