Student Name: …

Student ID: …

DETERMINISTIC MODELS IN OR
MIDTERM PRACTICE

Question 1
Consider the following problem:

Maximize Z=3 x1 +5 x 2+ 6 x3
Subject to
2 x1 + x 2 + x 3 ≤ 4 (1)
x 1+ 2 x 2 + x 3 ≤ 4 (2)
x 1+ x2 +2 x 3 ≤ 4 (3)
x 1+ x2 + x 3 ≤3 (4)
x1 , x2 , x3 ≥ 0
a. Using the simplex method to solve this problem
b. Find the allowable range for RHS of constraint (1)?
c. Find the allowable range for each coefficient of x 1 and x 3?

Solution:
Student Name: …
Student ID: …

Question 2
PTA’s Company considers their supply chain network including factories and their customers.
Suppose that our company has three factories that produce all 2 types of products. Product 1 can
be manufactured by factory 1 and factory 2 while product 2 is able to produce in factory 2 and
factory 3. We need to satisfy the demand of customers as Table 1. The capacity of factories is
given in Table 2.
Table 1. Demand of customers in the network (Unit:units)

Product 1 Product 2
Customer A 70 50
Customer B 50 80

Table 2. Production capacity of factories (Unit: units)

Product 1 Product 2
Factory 1 100 -
Factory 2 150 100
Factory 3 - 150
After being produced in factories, products will be transported to customers to satisfy their
demand. It costs transportation fee as Table 3.

Table 3. Transportation cost between factories and customers per each unit product (Unit:
$/unit)

Customer A Customer B
Factory 1 100 200
Factory 2 50 80
Student Name: …
Student ID: …
Factory 3 100 20
Formulate the mathematical model for minimizing the total cost subject to satisfy the customer’s
demand and the factory’s capacity.

Solution:
Parameters (demand, capacity, transportation cost)
- F: set of factories i = 1,2,3
- C: set of customers j = 1,2
- P: set of products k = 1, 2
- Djk: demand quantity of product k of customer j
- Kik: capacity of factory i to produce product k
- cij: transportation cost per unit from factory i to customer j
Decision variables (quantity produced of each product at each factory)
- xijk: quantity of product k is produced in factory i and transport to customer j
Objective function (minimize transportation cost)
Minimize ∑ ∑ ∑ c ij x ijk
i j k

Constraints (demand constraints, capacity constraints)

∑ x ijk ≥ D jk forall j ∈C , k ∈ P
i

∑ x ijk ≤ K ik forall i∈ F , k ∈ P
j

x ijk ≥0 forall i∈ F , j ∈C , k ∈ P

Question 3
Consider the following problem:

Maximize Z=500 x1 +300 x 2

Subject to
15 x 1+5 x 2 ≤ 300
10 x 1+6 x 2 ≤240
8 x 1+ 12 x 2 ≤ 450
x1 , x2 ≥ 0
Student Name: …
Student ID: …
Using the graphical method to find all optimal solutions for this model.

Solution:
- Red line: y=60 – 3 x
10
- Green line: y=40 – x
6
2
- Blue line: y=37.5 – x
3
Student Name: …
Student ID: …

Question 4
The Medequip Company produces precision medical diagnostic equipment at two factories.
Three medical centers have placed orders for this month’s production output. The table below
shows what the cost would be for shipping each unit from each factory to each of these
customers. Also shown are the number of units that will be produced at each factory and the
number of units ordered by each customer.

A decision now needs to be made about the shipping plan for how many units to ship from each
factory to each customer. Formulate a linear programming model for this problem.

Solution:
Let x1 and x2 be the number of units to ship to customer 1 by factory 1 and 2, respectively.
Let x3 and x4 be the number of units to ship to customer 2 by factory 1 and 2, respectively.
Let x5 and x6 be the number of units to ship to customer 3 by factory 1 and 2, respectively.

Objective function: Minimize Z = 600x1 + 400x2 + 800x3 + 900x4 + 700x5 + 600x6

Subject to:
(1) x1 + x2 = 300
(2) x3 + x4 = 200
(3) x5 + x6 = 400
(4) x1 + x3 + x5 = 400
(5) x2 + x4 + x6 = 500
(6) x1, x2, x3, x4, x5, x6 ≥ 0
(1), (2), (3) are demand constraints that make sure each customer receives enough units to
Student Name: …
Student ID: …
meet their demand.
(5), (6) are capacity constraints that make sure that the shipping rate does not exceed the
production rate at each factory.

Question 5
This is your lucky day. You have just won a $10,000 prize. You are setting aside $4,000 for
taxes and partying expenses, but you have decided to invest the other $6,000. Upon hearing this
news, two different friends have offered you an opportunity to become a partner in two different
entrepreneurial ventures, one planned by each friend. In both cases, this investment would
involve expending some of your time next summer as well as putting in cash. Becoming a full
partner in the first friend’s venture would require an investment of $5,000 and 400 hours, and
your estimated profit (ignoring the value of your time) would be $4,500. The corresponding
figures for the second friend’s venture are $4,000 and 500 hours, with an estimated profit to you
of $4,500. However, both friends are flexible and would allow you to come in at any fraction of
a full partnership you would like. If you choose a fraction of a full partnership, all the above
figures given for a full partnership (money investment, time investment, and your profit) would
be multiplied by this same fraction. Because you were looking for an interesting summer job
anyway (maximum of 600 hours), you have decided to participate in one or both friends’
ventures in whichever combination would maximize your total estimated profit. You now need
to solve the problem of finding the best combination.

a. Formulate a linear programming model for this problem.

b. Use the graphical method to solve this model. What is your total estimated profit?

Solution:
a. Formulate a LP model:
Let x1 be the fraction of full partnership to the first friend.
Let x2 the fraction of full partnership to the second friend.

Objective function: Maximize Z = 4500x1 + 4500x2

Subject to
Student Name: …
Student ID: …
(1) x1 ≤ 1
(2) x2 ≤ 1
(3) 5000x1 + 4000x2 ≤ 6000
(4) 400x1 + 500x2 ≤ 600
(5) x1, x2 ≥ 0
(1), (2) make sure that the fraction does not exceed full partnership
(3), (4) are the constraint for money and time investment into each friends’ venture
b. Use graphical method:
We draw the graph with
- Red line: x = 1
- Green line: y = 1
- Blue line: 5000x + 4000y = 6000
- Brown line: 400x + 500y = 600
Student Name: …
Student ID: …

Question 6
Consider the following problem:
Maximize Z=2 x 1 + x 2
Subject to
x 1+ x2 ≤ 40
4 x1 + x 2 ≤ 100
x1 , x2 ≥ 0

a. Solve this problem graphically. Also identify all the Corner Point Feasible (CPF)
solutions.
b. Now, solve this problem by the simplex method.

Solution:
a. Formulate a LP model:
Student Name: …
Student ID: …

b. Solve this problem by the simplex method.

All the coefficients in the objective row are nonnegative, so the solution (20, 20, 0, 0) is optimal
with an objective value of 60.

Question 7
Consider the following problem:
Student Name: …
Student ID: …
Maxmize Z=2 x 1−x 2 + x 3
Subject to
3 x 1+ x 2 + x 3 ≤ 6 (resource 1)
x 1−x 2+ 2 x 3 ≤1 (resource 2)
x 1+ x2 −x3 ≤ 2 (resource 3)
x1 , x2 , x3 ≥ 0
a. Work through the simplex method step by step to solve the problem.
b. Identify the shadow prices for the three resources and describe their significance.

Solution:

Question 8
Consider the following problem:

Maximize Z=3 x1 +9 x 2 +6 x 3
Subject to
x 1+ 3 x 2 +2 x3 ≤ 10
Student Name: …
Student ID: …
−3 x 1+ 4 x 2 ≤ 2
2 x1 + x 2 +2 x3 ≤ 8
x1 , x2 , x3 ≥ 0
Let s1 , s 2 , s 3 denote the slack variables for the respective constraints.

Use the revised simplex method step by step to find the optimal solution for this problem.

Solution:

Question 9

Consider the following problem:

Maximize Z=0.5 x 1+1.5 x 2 +0.6 x 3

Subject to
x 1+ 3 x 2 +2 x3 ≤ 10
3 x 1+ 4 x 2+ 2 x 3 ≥−1
2 x1 + x 2 +2 x3 ≤5
x1 , x2 , x3 ≥ 0
Let s1 , s 2 , s 3 denote the slack variables for the respective constraints

BV x1 x2 x3 s1 s2 s3 RHS
Z

Using revised simplex method to complete the final tableau (optimal solution) in Table above.
Given that the basic variables are x 2 , s2 , s 3.
Student Name: …
Student ID: …
Solution:

Question 10
Consider the following problem:

Maximize Z=3 x1 +2 x 2+ 3 x 3
Subject to
2 x1 + x 2 + x 3=4
x 1+ 3 x 2 + x 3=12
3 x 1+ 4 x 2+ 2 x 3=16
x1 , x2 , x3 ≥ 0
a. Using two phase method to solve this problem.
b. Convert this problem to BigM method.

Solution:
a. Using two phase method to solve this problem.
 Phase 1:
Min z = A1 + A2 + A3
St
2x1 + x2 + x3 + A1 = 4
x1 + 3x2 + x3 + A2 = 12
3x1 + 4x2 + 2x3 + A3 = 16
x1,x2,x3,A1,A2,A3 >= 0
 Phase 2:
Max z = 3x1 + 2x2 + 3x3
St
2x1 + x2 + x3 + A1 = 4
x1 + 3x2 + x3 + A2 = 12
Student Name: …
Student ID: …
3x1 + 4x2 + 2x3 + A3 = 16
x1,x2,x3,A1,A2,A3 >= 0
Phase 1
x1 x2 x3 A1 A2 A3 RHS
Z’ 0 0 0 -1 -1 -1 0
A1 2 1 1 1 0 0 4
A2 1 3 1 0 1 0 12
A3 3 4 2 0 0 1 16

x1 x2 x3 A1 A2 A3 RHS
Z’ 6 8 4 0 0 0 32
A1 2 1 1 1 0 0 4
A2 1 3 1 0 1 0 12
A3 3 4 2 0 0 1 16

x1 x2 x3 A1 A2 A3 RHS
Z’ 10/3 0 4/3 0 -8/3 0 0
A1 5/3 0 2/3 1 -1/3 0 0
x2 1/3 1 1/3 0 1/3 0 4
A3 5/3 0 2/3 0 -4/3 1 0

x1 x2 x3 A1 A2 A3 RHS
Z’ 0 0 0 -2 -2 0 0
x1 1 0 2/5 3/5 -1/5 0 0
x2 0 1 1/5 -1/5 2/5 0 4
A3 0 0 0 -1 -1 1 0

Phase 2
x1 x2 x3 RHS
Z’ -3 -2 -3 0
x1 1 0 2/5 0
x2 0 1 1/5 4

x1 x2 x3 RHS
Z’ 0 0 -7/5 8
x1 1 0 2/5 0
x2 0 1 1/5 4
Student Name: …
Student ID: …

x1 x2 x3 RHS
Z’ 7/2 0 0 8
x3 5/2 0 1 0
x2 -1/2 1 0 4

Optimal solution: Z = 8, x2 = 4, x1 = x3 =A1 = A2 = A3 = 0

b. Convert this problem to BigM method.

Max z = 3x1 + 2x2 + 3x3 – MA1 – MA2 – MA3

St
2x1 + x2 + x3 + A1 = 4
x1 + 3x2 + x3 + A2 = 12
3x1 + 4x2 + 2x3 + A3 = 16
x1,x2,x3,A1,A2,A3 >= 0
Transforming Z:
Max Z = (3 + 6M)x1 + (2 + 8M)x2 + (3 + 4M)x3 - 32M