Lecture (4)

Quantitative Methods

Miscellaneous examples of using simplex method in solving

linear programming problems
Example (1)
 A company produces two types of products x1 and x2, the linear
programming model for this company is formulated as follow:
Maximize Z = 2 x1+8 x2

Subject to:
2 x1 + x2 ≤ 200
2 x1 ≤ 120
x1 + 3x2 ≤ 300
x1, x2 ≥ 0
By using the simplex method to solve this problem, prepare the initial
simplex table (first table) and then choose the correct answer:

Solution
Adding slack variables:

2 x1 + x2 +s1 = 200
2 x1 + s2 = 120
x1 + 3x2 +s3 = 300

Main x1 x2 s1 s2 s3 Constants
variables
z 2 8 0 0 0 0 profit
s1 2 1 1 0 0 200
s2 2 0 0 1 0 120
s3 1 3 0 0 1 300

1- The value of x1 should be equaled to:

(A) 100 (B) zero (C) 120 (D) 200
2- The value of x2 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
3- The value of s1 should be equaled to:

1
 (A) 100 (B) zero (C) 120 (D) 200
4- The value of s2 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
5- The value of s3 should be equaled to:
(A) 300 (B) zero (C) 120 (D) 200
6- The value of z (profit) should be equaled to:
(A) 300 (B) 200 (C) 800 (D) zero
7- The main column …… x2……..
8- The main row …… s3……..
9- The key number will be ……3……..
Note:
s1 =200 ÷1=200
s2=120 ÷0=∞
s3 =300÷3=100 least number

…………………………………………………………………………
We obtained the second table of simplex (optimal solution) as follow:
Main x1 x2 S1 S2 S3 Constants
variables
z -2/3 -8/3
s1 5/3 -1/3 100
s2 2 0 120
x2 1/3 1/3 100
Solution

Main x1 x2 s1 s2 s3 Constants
variables
z -2/3 0 0 0 -8/3 800
s1 5/3 0 1 0 -1/3 100
s2 2 0 0 1 0 120
x2 1/3 1 0 0 1/3 100
Shadow prices (+) s1=0 s2=0 s3=8/3
Cost of resources=( 0×200 +0×120 +8/3×300 )= 800
Opportunity cost (-) x1=-2/3 x2=0
X1= profit 2 -(2×0 +2× 0 +1× 8/3 ) = 2- 8/3=-2/3

X2= profit 8-(1×0 +0× 0 +3× 8/3 )=8-8=0

Profit Z = 2 x1+8 x2 = 2(0)+8(100)=800

2
 x1= 0 , x2=100 , profit=800

S1=100 , s2=120 , s3=0

Main x1 x2 S1 S2 S3 Constants
variables
z -2/3 0 0 0 -8/3 800
s1 5/3 0 1 0 -1/3 100
s2 2 0 0 1 0 120
x2 1/3 1 0 0 1/3 100
Maximize Z = 2 x1+8 x2

Z = 2 (0) +8 (100) =800

Complete the table, and then choose the correct answer:

10- The value of x1 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
11- The value of x2 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
12- The value of s1 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
13- The value of s2 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
14- The value of s3 should be equaled to:
(A) 100 (B) zero (C) 120 (D) 200
15- The maximum profit should be equaled to:
(A) 300 (B) 400 (C) 800 (D) 500
16- The cost of resources should be equaled to:
(A) 300 (B) 400 (C) 800 (D) 500
17- The shadow price of s3 should be equaled to:
(A) -8/3 (B) zero (C) 8/3 (D) 2/3
18- The shadow price of s1 should be equaled to:
(A) -8/3 (B) zero (C) 8/3 (D) 2/3
19- The shadow price of s2 should be equaled to:
(A) -8/3 (B) zero (C) 8/3 (D) 2/3
20- The opportunity cost of x1 should be equaled to:
(A) -8/3 (B) zero (C) 2/3 (D) -2/3
21- The opportunity cost of x2 should be equaled to:
(A) -8/3 (B) zero (C) 2/3 (D) -2/3

3
Shadow prices :( numbers under s in z row without negative sign)
s1 =0 , s2 =0 , s3 =8/3
Opportunity cost :( numbers under x in z row – with the same sign)

x1 =-2/3 , x2 =0
Cost of resources= Shadow prices× available resources
s1 =0×200=0
s2 =0×120=0
s3 =8/3×300=800
Total profit = 800
…………………………………………………………….
Example (2):
A company produces two types of products. Type 1 requires 3 hours
of labor, and 1 kilogram of material. Type 2 requires 2 hours of
labor, and 2 kilogram of material. 2000 hours are available for
labors, and 1000 kilogram for material. Each unit of Type 1
produces L.E 40 profit, and each unit of Type 2 yields L.E 60 profit.
Find:
1- Formulate the linear programming model.
2- Prepare the initial simplex table (first table) and explain it.
3- We obtained an Optimal table of simplex as follow:
Main x1 x2 s1 s2 Constants
variables
z ? ? -5 -25 ?
x1 ? ? 0.5 -0.5 500
x2 ? ? -0.25 0.75 250
Complete the table and answer the following points:
 Maximum profit=
 Economic value of resources=
 Value of (x1)=
 Value of (x2)=
 Value of (s1)=
 Value of (s2)=
 Shadow Prices:
 Opportunity Cost:

4
 Solution

(1)Formulating the linear programming model:

Type (1) x1 , Type (2) x2
Z=40 x1 + 60x2
x1 x2 Availability
Labor 3 2 2000
Material 1 2 1000

Simplex Model:

Max z=40 x1+60 x2

Subject to:

Labor 3 x1 + 2x2 ≤ 2000

Material x1 +2x2 ≤ 1000

x1, x2 ≥ 0
(2)The initial simplex table (first table):
Transform to equations:
Labor 3 x1 + 2x2 +s1 = 2000

Material x1 +2x2 + s2 = 1000

Main x1 x2 S1 S2 Constants
variables
z 40 60 0 0 0
s1 3 2 1 0 2000
s2 1 2 0 1 1000

x1 = 0 , x2 =0 , profit=0 , s1= 2000 , s2= 1000

Main column: x2
Main row:
s1 =2000 ÷2=1000
s2=1000 ÷2= 500 least number
Key number =2 (intersection).

5
 (3)Completing the table:

Main x1 x2 s1 s2 Constants
variables
z 0 0 -5 -25 35000
x1 1 0 0.5 -0.5 500
x2 0 1 -0.25 0.75 250
Max z=40 x1+60 x2

z=40 (500)+60 (500)=35000

 Maximum profit= 35000

 Economic value of resources= 35000
 Value of (x1)= 500
 Value of (x2)= 250
 Value of (s1)=0
 Value of (s2)= 0
 Shadow Prices: S1= 5 S2=25
 Opportunity Cost: x1=0 x2=0

…………………………………………….

Example (3)
 A company produces three types of products x1 ,x2 ,and x3 .
Their profits are L.E 4, L.E 5, and L.E 3 respectively. the
following table shows the unit needs of each product from raw
materials, labor hours and the available quantities of these
resources:
Resources x1 x2 x3 Availability
Material 1 1 4 6000 kilogram
Cutting 1 2 1 7000 hours
Rolling 1 4 2 12000 hours

Find:
1- Formulate the linear programming model:
Solution

6
 Max z =4 x1 + 5 x2 +3 x3

Material x1 + x2 +4 x3 ≤ 6000
Cutting x1 + 2 x2 + x3 ≤ 7000
Rolling x1 + 4 x2 +2 x3 ≤ 12000
x1, x2 , x3 ≥ 0

2- Prepare the initial simplex table (first table) and explain it:
Solution
Material x1 + x2 +4 x3 + s1 = 6000
Cutting x1 + 2 x2 + x3 + s2 =7000
Rolling x1 + 4 x2 +2 x3 + s3 =12000

Main x1 x2 x3 s1 s2 s3 Constants
variables
z 4 5 3 0 0 0 0

s1 1 1 4 1 0 0 6000

s2 1 2 1 0 1 0 7000

s3 1 4 2 0 0 1 12000

x1 =0 , x2 =0 , x3 =0 , profit=0
s1 =6000, s2 =7000, s3 =12000
Main column: x2
Main row: s3
s1 =6000 ÷1=6000
s2=7000 ÷2=3500
s3 =12000÷4=3000 least number

Key number = 4
……………………………………………………………..
3- We obtained the following table of simplex (optimal solution)
as follow:

7
 Main x1 x2 x3 S1 S2 S3 Constants
variables
z ? ? -10 -3 -1 ? ?
S3 ? ? 7 2 -3 ? 3000

x1 ? ? 7 2 -1 ? 5000

x2 ? ? -3 -1 1 ? 1000

Complete the table, and explain it.

Solution
Main x1 x2 x3 S1 S2 S3 Constants
variables
z 0 0 -10 -3 -1 0 25000
s3 0 0 7 2 -3 1 3000

x1 1 0 7 2 -1 0 5000

x2 0 1 -3 -1 1 0 1000

Max z =4 x1 + 5 x2 +3 x3
Profit =4(5000)+5(1000)+0 = 25000
x1 =5000 , x2 =1000 , x3 =0
s1 =0 , s2 =0 , s3 =3000
Shadow prices:(numbers under s in z row without negative sign)
s1 =3 , s2 =1 , s3 =0
Opportunity cost:(numbers under x in z row – with the same sign)

x1 =0 , x2 =0 , x3 = -10
………………………………………………………..
4- Suppose that the company can manufacture a new
product(x4) with an estimated profit L.E 19, and it needs 2

8
kilograms of raw material, 4 hours of cutting, and 3 hours
of rolling, should this product be produce? Why?

Solution
Opportunity cost =profit – (needs × shadow prices)
Opportunity cost = positive or 0 (accept)
Opportunity cost = negative (reject)
Opportunity cost=19 – (2× 3 +4 ×1 +3× 0) = 19 -10 =+9 (accept)

Yes this product should be produced since the Opportunity

cost = +9

9
 Assignment
Example (1)
 A company produces three types of products x1 ,x2 ,and x3, the linear
programming model for this company is formulated as follow:
Maximize Z = 12 x1+14 x2 +16 x3

Subject to:
Raw Material (by kilogram) 2 x1+4 x2 +2 x3≤ 20
Direct labor hours 6x1+8 x2 +4 x3≤ 24
Hand work (hours) 4 x1+12 x2 +8 x3≤40

x1, x2, x3 ≥ 0
Find:
1- Prepare the initial simplex table (first table) and explain it.
2- We obtained the following table of simplex (optimal
solution) as follow:
Main x1 x2 x3 s1 s2 s3 Constants
variables
z ? -12 ? ? -1 -3/2 ?

s1 ? 1/2 ? ? -1/4 -1/8 9

x1 ? 1/2 ? ? 1/4 -1/8 1

x3 ? 5/4 ? ? -1/8 3/16 9/2

Complete the table, and explain it.

3- Suppose that the company can manufacture a new

product(x4) with an estimated profit L.E 12, and it needs 2
kilograms of raw material, 4 hours of labor, and 6 hours of
handwork, should this product be produce? Why?

10
Example (2)
A company produces three types of products x1 ,x2 ,and x3 . Their
profits are L.E 30, L.E 40, and L.E 15 respectively, Type 1 requires
10 hours of labor, and 15 kilogram of raw material. Type 2 requires
20 hours of labor, and 10 kilogram of raw material. Type 3 requires
5 hours of labor, and 10 kilogram of raw material. 300 hours are
available for labors, and 270 kilogram for raw material.
Find:
1- Formulate the linear programming model.
2- Prepare the initial simplex table (first table) and explain it.

3- We obtained the following table of simplex (optimal solution)

as follow:
Main x1 x2 x3 s1 s2 Constants
variables
z ? ? -5/2 -3/2 -1 ?
x2 ? ? -1/8 3/40 -1/20 9

x1 ? ? 3/4 -1/20 1/10 12

Complete the table, and explain it.

4- Suppose that the company can manufacture a new

product(x4) with an estimated profit L.E 7, and it needs 2
hours of labor and 5 kilograms of raw material, should this
product be produce? Why?

11
Example (3)
A company produces two types of products x1, and x2. Their profits
are L.E 6 and L.E 10, respectively, Type 1 requires 6 kilogram of
Raw material and 2 hours of hand work. Type 2 requires 4 kilogram
of raw material and 2 hours of direct labor hours.36 kilogram are
available for of raw material, 8 hours are available for hand work
and 12 hours are available for direct labor hours.

Find:
1- Formulate the linear programming model.
2- Prepare the initial simplex table (first table) and explain it.
3- We obtained the following table of simplex (optimal solution)
as follow:
Main x1 x2 s1 s2 s3 Constants
variables
z ? ? -1 ? -3 ?
x1 ? ? 1/6 ? -1/3 2

s2 ? ? -1/3 ? 2/3 4

x2 ? ? 0 ? 1/2 6

Complete the table, and explain it.

4- Suppose that the company can manufacture a new
product(x3)with an estimated profit L.E 10, and it needs 2
kilograms of raw material , 2 hours of hand work and 3
hours of direct labor, should this product be produce ?
Why?

12
 Example (4)
 A company produces three types of products x1 ,x2 ,and x3 .The
following table shows their data:
x1 x2 x3 Availability
Material 8 4 2 3200 kilogram
Cutting 5 2 2 2400 hours
Rolling 10 4 2 3200 hours
Selling price(per unit) 200 50 40
Variable cost(per unit) 120 30 28

Find:
1- Formulate the linear programming model.
2- Prepare the initial simplex table (first table) and explain it.

3- We obtained the following table of simplex (optimal solution)

as follow:
Main x1 x2 x3 S1 S2 S3 Constants
variables
Z ? -12 -4 ? ? -8 ?
s1 ? 4/5 2/5 ? ? -4/5 640

s2 ? 0 1 ? ? -1/2 800

x1 ? 2/5 1/5 ? ? 1/10 320

Complete the table, and explain it.

13