Week 04

IS 231
Operation Research
Dr. Yasser ALHABIBI
E-mail: [email protected]
Misr University for Science and Technology
Faculty of Information Technology
Fall-2023
List of References
Course notes
Available (handed to students' part by part).

Essential books (textbooks)

 Introduction to Operation Research, Frederick S. Hillier, Gerald J.
Lieberman, Tenth Edition McGraw-Hill, 2015.
 Operation Research, An Introduction, Hmdy A. Taha, University
of Arkansas, Fayetteville. USA, Pearson, Prentice Hall, 2007
 Operations Research, A. Somaiah & Vanaja, IARE, USA, Institute
of Aeronautical Engineering Press, 2000

Recommended books
 Other books that are related to Operation Research
 Course Outline
 Introduction to Operation Research
 Linear Programming
 Solving LP Linear Programming using Simplex Method
 The Transportation problem
 The Assignment Problem
 Project Scheduling ( PCM & PERT ).
 Operation Research
WKS
01 Introduction to Operation Research
02 Introduction to Linear Programming
03 The Fundamental Theorem of Linear Programming Geometry in Rn
Basic Linear Algebra, Definitions and theorems
04 Solving Linear Programming Problem (Graphical Solution)
05 Solving Linear Programming Problem ( The Simplex Method)
06 QUIZ 01
07 Solving Linear Programming Problem Two phases of the Simplex Method
08 Duality
09 Complementary Slackness Theorem
10 Application of Linear Programming ( Transportation Problem)
Alternative Criteria for Finding Initial BF Solution
11 Application of Linear Programming ( Transportation Problem) Optimal Solution
12 QUIZ 02
13 Application of Linear Programming (Assignment Problem)
Alternative Criteria for Finding Initial BF Solution
14 4 Project Scheduling ( PCM & PERT ). LAB Final Exam
15 FINAL EXAM
 Course Objectives

 To provide the student (participants) with

the modern concepts and techniques in
Operation Research and Decision Making.
 To train the student on how to use and
apply these techniques in practice.
 Operation Research
Lecture 4

Solving Linear Programming Problem

Graphical Solution
 Graphical Solution
It is possible to solve L.P.P. graphically if it
contains two variables only. For very
small problem (rarely occurred) which has
only two decision variables and therefore
only two dimensions, so a graphical
procedure can be used to solve it.
This procedure involves constructing a
two-dimensional graph with x1 and x2 as
the axes.
7
 Graphical Solution
This is done by drawing each line that
borders the range of permissible values
for one restriction. To begin, note that the
non-negativity restrictions x1 ≥ 0 and x2 ≥ 0
require (x1 , x2) to lie on the positive side
of the axes (including actually on either
axis), i.e., in the first quadrant. The
resulting region of permissible values of
(x1 , x2), called the feasible region.

8
 Graphical Solution
The graphical solution includes two basic
steps:
1.The determination of the solution space
that defines the feasible solutions that
satisfy all the constraints.
2.The determination of the optimum
solution from among all the points in the
feasible solution space.

9
 Terminology for Solutions of the Model
A Solution
Any specification of values for the decision
variables (x1, x2, . . . , x2) is called a solution,
regardless of whether it is a desirable or even an
allowable choice.
Different types of solutions are then identified by
using an appropriate adjective.
Feasible Solution
is a solution for which all the constraints are
satisfied.
Infeasible Solution
is a solution for which at least one constraint is
violated. 1
 Terminology for Solutions of the Model
The Feasible Region (Domain)
is the collection of all feasible solutions.
Optimal Solution
is a feasible solution that has the most favorable
value of the objective function. The most
favorable value is the largest value if the
objective function is to be maximized, whereas it
is the smallest value if the objective function is to
be minimized.
A Corner-Point Feasible (CPF) Solution
(Extreme Points or Vertices)
is a solution that lies at a corner of the feasible
region. 1
 Terminology for Solutions of the Model

Relationship between Optimal Solutions and CPF

solutions
Consider any linear programming problem with feasible
solutions and a bounded feasible region. The problem
must possess CPF solutions and at least one optimal
solution. Furthermore, the best CPF solution must be
an optimal solution. Thus,
If a problem has exactly one optimal solution, it
must be a CPF solution.
If the problem has multiple optimal solutions, at
least two must be adjacent CPF solutions.
Two corner-point feasible solutions are said to be
adjacent if the line segment connecting them lies on
the boundary of the feasible region (one of the
constraints). 1
 Standard Linear Programming Problems

Objective function :
M in Z  c1x 1  c 2 x 2  c 3x 3  ...  c n x n

S ubject to :Constra int s

a11x 1  a12 x 2  a13 x 3  ...  a1n x n  b1
a21x 1  a22 x 2  a23 x 3  ...  a2 n x n  b2
. .
. .
. .
am 1x 1  am 2 x 2  am 3 x 3  ...  amn x n  bm
and x 1 , x 2 , x 3 , ..., x n 0
Or,
Min Z  c T x W here : x  R n , c  R n , b  R m , A  aij 
mn
S .t . Rank (A )  m , m  n
Ax  b and S  x  R n / A x  b , x  0
and x  0 is the set of all feasible solutions .
1
 Example 1
Solve the following LPP
Maximize Z = X1 + X2
subject to
2X1 + X2 ≤4
X1 + 2 X2 ≤4
x2 and
X1 ≥ 0, X2 ≥ 0.
4  1
c  
 1
= direction of
max. increase
2 of objective
Feasible
Domain

0 2 4
x1

14
 Graphical Solution of LPs
Constraints
2X1 + X2 =4
X1 + 2 X2 =4
Objective Function: Max Z = X1 + X2  1
c  
 1

x2 1 1 3 
x *
 ,
1 1 
 3 

4 1 1 3 
z *
c T
x *
 (1 1)    2 23
1 1 3 

Is a feasible
2 * optimal solution
x
Feasible
Domain

0 2 x1
4

15
 Example 2
Solve the following LPP: Max Z = 120 X1 + 100 X2
subject to
X 1 + X2 ≤4
5 X1 + 3 X2 ≤15
x2 and
X1 ≥ 0, X2 ≥ 0.
 2
5    S is " feasible solution "
direction of 1
max. increase
4 of objective 3/ 2
   S is " feasible optimal solution "
 5 / 2 
.
(3\2, 5\2)
3 / 2
Z  c T x  (120 100)    430.
Feasible 5 / 2
Domain

0 3 4
x1

16
 Example 3: Infeasible Solution
Solve the following LPP:
Max Z = 2 X1 + 5 X2
subject to
2 X1 + 3 X2 ≥ 12
3 X1+ 4X2 ≤ 12
x2 and
X1 ≥ 0, X2 ≥ 0.

S=Ф
2

x1
0 2 4 4 6

Infeasible Solution=Ф
17
 Example 4: Non-existing or Infeasible Solution
Solve the following LPP:

Maximize Z= 3 X1 +2 X2
S.T 2 X1 + X2 ≤ 2
3 X1 +4 X2 ≥ 12
and X1, X2 ≥ 0
Non-existing or Infeasible
Solution
If the constraints are not satisfied
simultaneously, the model has no
feasible solution. This situation
can never occur if all the
constraints are of the type ≤
(assuming non-negative R.H.S
constraints) because the slacks
provide a feasible solution.
18
 Example 5: Unbounded Solution
Max Z = 2 X1 + 5 X2
Solve the following LPP: subject to
-3 X1 + 2 X2 ≤ 6
X1 + 2X2 ≥ 2
and
x2 X1 ≥ 0, X2 ≥ 0.

x1
0 2 4 4 6

S is unbounded Solution
19
 Example 6: Unbounded Solution
Solve the following L.P.P.:
Max Z = 2 X1 + X2
subject to
X1 - X2 ≤ 10
2 X1 ≤ 40
and
X1 ≥ 0, X2 ≥ 0.
S is unbounded Solution
In which the objective
function (Z) can be increased
indefinitely without violating
any of the constraints i.e.;
the solution space is
unbounded in at least one
direction.
20
 Example 7: Alternative optima (Infinity of Solution)
Solve the following L.P.P.:
Maximize Z= 2 X1 + 4 X2
subject to
X1 + 2 X2 ≤5
X1 + X2 ≤4
and
X1 , X2 ≥0
When the objective function is
parallel to a binding constraint. So
the objective function (Z) will have
the same optimal value at more
than one solution point. LP Alternative optima
First Optimum Solution: X1=0, X2=5/2, Z=10
Second Optimum Solution: X1=3, X2=1, Z*=10
The general form: X1 = α (0) + (1-α) (3) = 3-3α
X2 = α (5/2) + (1-α) (1) = 1+3/2α
21
 Example 8: The Diet Problem
A nutritionist is planning a menu consisting of two main foods A and B.
Each ounce of A contains 2 units of fat, 1 unit of carbohydrates, and 4
units of protein. Each ounce of B contains 3 units of fat, 3 unit of
carbohydrates, and 3 units of protein. The nutritionist wants the meal to
provide at least 18 units of fat, 12 unit of carbohydrates, and 24 units of
protein. If an ounce of A costs 20 cents and an ounce of B costs 25
cents, how many ounces of each food should be served to minimize the
cost of the meal yet satisfy the nutritionist's requirements?
Solution
Table: Summery Data for the example

Food Type Fat Carbohydrate Protein Costs/ounce

ounce(( units(( s (units) )units( (Cents)
A 2 1 4 20
B 3 3 3 25
Minimum Daily 18 12 24
Requirement

22
The Diet Problem Linear Programming Model
a- Decision Variables:
Let x be the number of ounces of food A,
y be the number of ounces of food B.
b- Objective function:
Cost of menu Z= 20x + 25y
c- Constraints:
Fats: 2x + 3y ≥ 18
Carbohydrates: x + 3y ≥ 12
Proteins: 4x + 3y ≥ 24
Mathematical Model
Minimize Z = 20x + 25y
Subject to 2x + 3y ≥ 18
x + 3y ≥ 12
4x + 3y ≥ 24
and
x, y ≥ 0
23
 Minimize Z = 20x + 25y
Subject to 2x + 3y ≥ 18
x + 3y ≥ 12
4x + 3y ≥ 24
and
x, y ≥ 0

Graphical solution
A
8
6
4 B

2 C

0 2 4 6 8 10 D12

Optimal solution
Minimum Cost = 160 cents at x = 3 Ounces & y = 4 Ounces (point B)
24
 Example 9: The Diet Mix Problem
Farm uses at least 800lb of special feed daily. The special feed is a
mixture of corn and soybean with the following composition.

The food mixture must contain at least 30% protein and at most 5% fiber.
They want to determine the daily minimum cost feed mix.
Problem Formulation
Decision variables
X1= lb of corn in the daily mix.
X2= lb of soybean in the daily mix.
Objective Function
Minimize Z= 0.3 X1 + 0.9 X2
Constraints
X1 + X2 ≥ 800
0.09X1+0.6 X2 ≥ 0.3(X1+X2) = -0.21X1+0.3 X2 ≥0
0.02X1+0.06 X2 ≤ 0.05(X1+X2) = 0.03X1-0.01 X2 ≥ 0
Graphical solution of the diet model
 Example 10: A Blending Problem
A manufacturer of artificial sweetener blends 14 kilograms of saccharin
and 18 kilograms of dextrose to prepare two new products: Sweet and
Low-Sugar. Each kilogram of Sweet contains 0.4 kilograms of dextrose
and 0.2 kilograms of saccharin, while each kilogram of Low-Sugar
contains 0.3 kilograms of dextrose and 0.4 kilograms of saccharin. If the
profit on each kilogram of Sweet is 20 cents and the profit on each
kilogram of Low-Sugar is 30 cents, how many kilograms of each product
should be made to maximize the profit?
Solution
Table: Summery Data for the example

Sweet Type saccharin Dextrose Profit/kg

Kg(( )Kg( )Kg( (cents)
Sweet (Kg) 0.2 0.4 20
Low-Sugar(Kg) 0.4 0.3 30
Available Material (Kg) 14 18

27
 A Blending Problem Linear
Programming Model
a- Variables:
Let x be the number of Kg.’s of Sweet,
y be the number of Kg.’s of Low-sugar
b- Objective function:
Profit of each Kg Z = 20x + 30y
c- Constraints:
Saccharin Qty: 0.2x + 0.4y ≤ 14
Dextrose Qty: 0.4x + 0.3y ≤ 18

Mathematical Model:

Maximize Z = 20x + 30y

Subject to 0.2x + 0.4y ≤ 14
0.4x + 0.3y ≤ 18
and
x, y ≥ 0

28
 Maximize P = 20x + 30y
Subject to 0.2x + 0.4y ≤ 14
0.4x + 0.3y ≤ 18
x, y ≥ 0

Graphical solution:
80
60
40
B
20 C

A 10 20 30 40 D50 60 70

Optimal solution:
Max. Profit = 1200 $ at x = 30 Kg & y = 20 Kg (Point C)
29
 Example 11: The Reddy Mikks Company
Reddy Mikks produces both interior and exterior paints from two raw
materials, M1 & M2. The following table provides the basic data of the
problem.

A market survey indicates that the daily demand for interior paint
cannot exceed that of exterior paint by more than 1 ton. Also, the
maximum daily demand of 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.
30
 Problem Formulation
Decision variables
X1= Tons produced daily of exterior paint.
X2= Tons produced daily of interior paint.
Objective Function
Maximize Z= 5 X1 + 4 X2
Constraints
6 X1 + 4 X2 ≤ 24
X1 + 2 X2 ≤ 6
- X1 + X2 ≤ 1
X2 ≤ 2
and X1, X2 ≥ 0
Any solution that satisfies all the constraints of the model is a feasible
solution. For example, X1=3 tons and X2=1 ton is a feasible solution.
We have an infinite number of feasible solutions, but we are interested
in the optimum feasible solution that yields the maximum total profit.

31
.

Feasible space of the Reddy Mikks model

ABCDEF consists of an infinite number of points; we need a systematic
procedure that identifies the optimum solutions. The optimum solution
is associated with a corner point of the solution space.

32
To determine the direction in which the profit function increases we assign
arbitrary increasing values of 10 and 15
5 X1 + 4 X2=10
and 5 X1 + 4 X2=15

Optimum solution of the Reddy Mikks model.

The optimum solution is mixture of 3 tons of exterior and 1.5 tons of interior
paints will yield a daily profit of 21000$.
33
 Example 12: A small generator
A small generator burns two types of fuel: Low sulfur (L) and High
sulfur (H) to produce electricity. For each hour of use, each gallon of L
emits 3 units of sulfur dioxide, generates 4 Kilowatts and costs 60 cents,
while each gallon of H emits 5 units of sulfur dioxide, generates 4
Kilowatts and costs 50 cents. The environmental protection agency
insists that the maximum amount of sulfur dioxide that can be emitted
per hour is 15 units. Suppose that at least 16 Kilowatts must be
generated per hour.
How many gallons of L and how many gallons of H should be used
hourly to minimize the cost of the fuel used?
Solution
Table: Summery Data for the example
Fuel Type sulfur dioxide Generation Costs
gallon(( units(( (KW) )cents(
Low sulfur (L) 3 4 60
High sulfur (H) 5 4 50
Requirement At most 15 At Least 16
units
34
 A small generator Formulation as a Linear
Programming Model
a. Decision Variables
Let x be the number of gallons of L used hourly,
y be the number of gallons of H used hourly
b. Objective function:
Cost of fuel used
Z = 60x + 50y
c. Constraints
Environment protection: 3x + 5y ≤ 15
Power generated: 4x + 4y ≥ 16

Mathematical Model
Minimize Z = 60x + 50y
Subject to 3x + 5y ≤ 15
4x + 4y ≥ 16
and
x, y ≥ 0

35
 A small generator Graphical solutions
2- Graphical solution
The problem has only 2 decision variables = only two dimensions, so a
graphical procedure can be used to solve it.

4
3
2 A
1
B C
1 2 3 4 5

3- Optimal solution
Minimum Cost = 225 cents at x = 2.5 G and y = 1.5 G (point c)

36
 Example 13: A manufacturing firm
A manufacturing firm produces two machine parts using lathes, milling
machines and grinding machines as given in the following table:
Machining time required for the machine part
(minutes) Maximum time available
Type of machine
per week (minutes)
I II

Lathes 10 5 2500
Milling machines 4 10 2000
Grinding machines 1 1.5 450
Profit per unit 50 100

Determine the number of parts I and II to be manufactured per week to

maximize the profit.
Solution:
Let x, y be the number of machine parts I, II to be manufactured per week
respectively. The problem will have the following mathematical model
Max f(x, y) = 50 x + 100 y
Subject to 10 x + 5 y ≤ 2500 (1)
4 x + 10 y ≤ 2000 (2)
x + 1.5 y ≤ 450 (3)
and x≥0,y ≥0. (4)
37
 A manufacturing firm Graphical Solution

We draw solution set

The function values at corner points of the set of solutions are :
f(0, 0)= 50*(0) + 100*(0) = 0,
f(0, 200)= 50*(0) + 100*(200) =20000,
f(187.5, 125)= 50*(187.5)+100*(125)=21875,
f(250, 0) = 50*(250)+100*(0)=12500,
from which , we obtain
max f(x, y) = f(187.5,125) = 21875.
38
 Example 14: Drug Problem
A company produces drugs I an II using machines M1 and M2. one ton
of drug I requires 1 hour of processing on M1 and 2 hours on M2. one
ton of drug II requires 3 hour of processing on M1 and 1 hours on M2.
9 hours of processing on M1 and 8 hours on M2 are available. Each
ton of drug produced (of either type) yields a profit of 1 million. To
maximize its profit, how much of each drug should the company
produce?
Solution

39
40
 Example 15
Maximize Z= 20 ( x - 50) + 38 ( y – 20)
Solve the following LPP
Subject to x + 2 y ≤ 200
x≥ 50 , 20 ≤ y ≤ 90
and
x, y ≥ 0

- Graphical solution:

150
100 B
50
A C
50 100 150 200
- Optimal solution
X= 160 , y = 20 ---- Z = 2200 at C
41
 Example 16: Product Mix Problem
The N.G. company produces two products: I and II. The Raw material
requirements, space needed for storage, production rates, and selling
prices for these products are given in the following table.

42
43
44
45
46
Example 17: A Transport Company

Min Z= f(x, y) = 30 x + 40 y
Subject to 20x+30y ≥ 3000 (1)
40x+30y ≥ 4000 (2)
and x≥0,y ≥0. (3)

47
48
49
 Example 18: The WYNDOR GLASS CO.
The WYNDOR GLASS CO. produces high-quality glass products, including
windows and glass doors. It has three plants.
Plant 1: Produce Aluminum frames and hardware,
Plant 2: Produce wood frames,
Plant 3: produces the glass and assembles the products.
Because of declining earnings, top management has decided to revise the
company’s product line as following:
Unprofitable products are being discontinued, Saved production capacity will
be used to launch two new products having large sales potential:
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4 6 foot double-hung wood-framed window
Product 1: requires some of the production capacity in Plants 1 and 3, but
none in Plant 2.
Product 2: needs only Plants 2 and 3.
The marketing division has concluded that the company could sell as much of
either product as could be produced by these plants.
However, because both products would be competing for the same
production capacity in Plant 3, it is not clear which mix of the two products
would be most profitable. Therefore, an OR team has been formed to study
this question. 50
 The WYNDOR GLASS CO.
The OR team began by having discussions with upper management to identify
management’s objectives for the study. These discussions led to developing
the following definition of the problem:
Determine what the production rates should be for the two products in order
to maximize their total profit, subject to the restrictions imposed by the
limited production capacities available in the three plants. (Each product will
be produced in batches of 20, so the production rate is defined as the number
of batches produced per week.) Any combination of production rates that
satisfies these restrictions is permitted, including producing none of one
product and as much as possible of the other.
The OR team also identified the data that needed to be gathered:
1. Number of hours of production time available per week in each plant for
these new products. (Most of the time in these plants already is committed to
current products, so the available capacity for the new products is quite
limited.)
2. Number of hours of production time used in each plant for each batch
produced of each new product.
3. Profit per batch produced of each new product.
Table 1 summarizes the data gathered.
51
 Formulation as a Linear Programming
Problem
To formulate the mathematical (linear
programming) model for this problem.
let
X1 Number of batches of product 1 produced
per week
X2 Number of batches of product 2 produced
per week
Z Total profit per week (in thousands of Each product will be produced in batches of
dollars) from producing these two products 20, so the production rate is defined as the
Thus, X1 and X2 are the decision variables for number of batches produced per week.)
the model.
Using the bottom row of Table 1, we obtain
Z = 3 X1 + 5 X2.
In the mathematical language of linear programming, the problem is to choose
values of X1 and X2 so as to
Maximize Z = 3 X1 + 5 X2.
subject to the restrictions
X1 ≤4
2 X2 ≤ 12
3 X1 + 2 X2 ≤18
and
52
53
54
55
56