IE 202 Study Set I Fall 2020

1. Willy Wonka’s Candy Company produces three types of candy: Wonka Bars, Bottle Caps
and Giant Sweet Tarts. In order to produce the different type of candies, Willy can run
three different production processes as described below. Each process involves blending
different types of sugars in the Magical Factories Mixer.

• Process 1: Running Process 1 for one hour:

Costs: $5
Requires: Two barrels of sugar type A and three barrels of sugar type B
Output: Two Wonka Bars and one packet of Bottle Caps.

• Process 2: Running Process 2 for one hour:

Costs: $4
Requires: One barrel of sugar type A and three barrels of sugar type B
Output: Three packets of Bottle Caps.

• Process 3: Running Process 3 for one hour:

Costs: $1
Requires: Two barrels of sugar type B and three packets of Bottle Caps
Output: Two Wonka Bars and one packet of Giant Sweet tarts.

Each week we can purchase 200 barrels of sugar type A at $2 per barrel, and 300 barrels of
sugar type B at $3 per barrel. Assume that they can sell everything that they can produce.
Wonka Bars are sold at $9 per bar, Bottle Caps are sold at $10 per packet, and Giant
Sweet Tarts are sold at $24 per packet. Assume that 100 hours of mixing are available.

(a) Formulate an LP whose solution will maximize Willy Wonka’s profit. Hint: Use
decision variable xi : number of hours process i runs, i = 1, 2, 3.

(b) Assume that instead of having 200 barrels of sugar type A and 300 barrels of sugar
type B available that you can order a total of 500 Barrels. Show how to modify your
LP formulation in part (a) to account for this revised problem.

(c) Suppose that instead of selling the tree candies separately, they can only be sold as
part of a box consisting of one Wonka Bar, two packets of Bottle Caps and one pack
of Giant Sweet Tarts. Each Wonka Box sells for $54. Modify your LP formulation in
part (a) to model this new scenario. (You may need to add another decision variable.)

1
2. Suppose that there are N available currencies, and assume that one unit of currency i
can be exchanged for rij units of currency j. (Naturally, we assume that rij > 0). There
are also certain regulations that impose a limit ui on the amount of currency i that can
be exchanged on any given day. Suppose that we start with B units of currency 1, and
transactions are performed once during a day (say at 9 am with the available amount at
hand from the previous day) and we would like to maximize the number of units of currency
N that we end up with at the end of a planning period of T days, through a sequence of
currency transactions. Provide a linear programming formulation of this problem. Assume
that for any sequence i1 , . . . , ik of currencies, we have ri1 i2 ri2 i3 . . . rik−1 ik rik i1 ≤ 1, which
means that wealth cannot be multiplied by going through a cycle of currencies, i.e., there
is no arbitrage.

Hint: It is helpful to define decision variables so that we can keep track of the amount of
each currency converted to other currencies at each day, and total amount of each currency
at the end of each day.

3. A company wishes to plan its production of two products with seasonal demands over
a 12 month period from the beginning of January. The monthly demand of product 1
is 100,000 kg during the months of October, November and December; 10,000 kg during
the months of January, February, March and April; and 30,000 kg during the remaining
months. The demand of product 2 is 50,000 kg during the months of October through
February and 15,000 kg during the remaining months. Suppose that cost of producing
a kg of product 1 and 2 is $5 and $8, respectively, provided that these were produced
prior to June. After June, the costs are reduced to $4.5/kg and $7/kg because of the
installation of an improved production system. The total amount of products 1 and 2 that
can be produced during any particular month cannot exceed 120,000 kg for Jan-Sept and
150,000 kg for Oct-Dec. Furthermore, at the end of each month products left at the hand
are carried to the inventory space in order to be used in the coming months. Each kg of
product 1 occupies 2 cubic-feet and each kg of product 2, 4 cubic-feet of inventory. Suppose
that the maximum inventory space allocated to these products is 150,000 cubic-feet and
that the holding cost per cubic foot during any month is $0.10. Formulate the production
scheduling problem so that total production and inventory costs are minimized.

4. Ford has four automobile plants. Each is capable of producing the Taurus, Lincoln or
Escort but it can only produce one of these cars. The fixed cost of operating each plant
for a year and the variable cost of producing a car of each type at each plant are given in
the table below. Ford faces the following restrictions:

2
 • Each plant can produce one type of car.

• The total production of each type of car must be at a single plant; that is, for example,
if any Tauruses are made at plant 1, then all Taururses must be made there.

• If plants 3 and 4 are used, then plant 1 must also be used. Formulate the problem in
order to minimize the total cost.

Variable Costs

Fixed Cost Taurus Lincoln Escort

Plant 1 7 billion 12000 16000 9000
Plant 2 6 billion 15000 18000 11000
Plant 3 4 billion 17000 19000 12000
Plant 4 2 billion 19000 22000 14000

5. Kocalar Delivery Company must make deliveries to 10 customers whose respective de-
mands are dj for j = 1, . . . , 10. Each customer can be visited by more than one truck
to satisfy the demands. The company has four trucks available with capacities Lk and
daily operating costs ck for k = 1, . . . , 4. Formulate the model to determine which trucks
to use so as to minimize the cost of delivering to all the customers. Add the following
requirements:

(a) A single truck cannot deliver to more than five customers.

(b) Customer 1 and customer 7 cannot be visited by the same truck.

(c) Additionally, if a truck visits customer 3 then it has to visit customer 4 or customer
5. (Assume demands of these customers do not exceed truck capacities.)

(d) Both customer 2 and customer 6 should be visited by the same truck(s).

(e) Either at least one of the customers 1, 2 and 3 or at most 2 of customers 5, 6, 7

should be visited by truck 4.

6. Assume there are 5 clients that need to be supplied from a warehouse. The following table
lists the location of each of these clients in terms of respective x and y coordinate values.

Client Location in Location in

Number x Coordinate y Coordinate
1 12 11
2 20 15
3 32 24
4 46 42
5 88 65

3
 The distance is defined in terms of the sum of rectilinear movements, in horizontal and
vertical directions. (For instance, if warehouse is located at the point (x, y), then its
distance from the first client is |12 − x| + |11 − y|).

(a) Your job is to come up with a linear programming model to choose the coordinates
of the location of the warehouse such that the sum of the distances to all clients is as
small as possible.

(b) How you modify your model in part a if your objective is to minimize the largest of
the five distance values?

7. I now have $100 and three choices of investment during the next three years. For every
dollar invested: Investment A yields $0.10 a year after the investment and yields $1.30
three years after the investment, Investment B yields $0.20 a year after the investment
and yields $1.10 two years after the investment. Investment C yields $1.50 three years
after the investment. Investments A and C are available in the beginning of year 1 while
B is available in the beginning of years 1 and 2. During each year, uninvested cash can
be placed in money market funds, which yield 6% interest per year. At most $50 may be
placed in each of investments A, B, and C in each year. Formulate an LP to maximize my
cash on hand four years from now.

8. A power plant has three boilers. If a given boiler is operated, it can be used to produce a
quantity of steam (in tons) between the minimum and maximum given in the first table
below. The cost of producing a ton of steam on each boiler is also given. Steam from the
boilers is used to produce power on three turbines. If operated, each turbine can process
an amount of steam (in tons) between the minimum and maximum given in the second
table. The cost of processing a ton of steam and the power produced by each turbine is
also given. Formulate an IP that can be used to minimize the cost of producing 8000 kWh
of power.

Boiler Minimum Maximum

Cost/ton
Number Steam Steam
1 500 1000 10
2 300 900 8
3 400 800 6

4
 Turbine KWh/ton of Processing
Minimum Maximum
Number Steam Cost/ton
1 300 600 4 2
2 500 800 5 3
3 600 900 6 4

9. (Final Scheduling) Bilkent Student Affairs needs your help for the upcoming finals of
the current academic semester. The final exam period is already announced for 14 days
and in each day there are 4 exam slots. Let S = {1, . . . , S} be the set of students,
I = {1, . . . , I} be the set of instructors, and C = {1, . . . , C} be the set of courses. The
following parameters are provided to you by BCC.


1 if student s takes course c,

asc = s∈S c∈C

0 otherwise


1 if instructor i teaches course c,

bic = i∈I c∈C

0 otherwise

You need to formulate an integer programming model that takes care of the following
limitations.

(a) Each course should be scheduled for a time slot.

(b) No student has his/her two courses scheduled at the same time slot (no conflicts).

(c) No student has more than two exams per day.

(d) No instructor has more than one of his/her courses scheduled at the same time slot.

Given a particular schedule, the number of pairs of exams on the same day or on two
consecutive days for a particular student is called the “badness count” of that particular
student. So if a student has two exams on Monday, two on Tuesday, one on Thursday, one
on Friday and one on Sunday his/her badness count is 7. Your objective is to come up
with a schedule such that the total badness count of all the students is minimized.

10. A paper manufacturer produces rolls of standard fixed width w and of standard length l.
Customers order rolls of width w but varying lengths. In particular, dk rolls with length
lk and width w are ordered for customer k = 1, . . . , n (assume lk ≤ l for all k = 1, . . . , n).
What is the minimum number of rolls that should be cut to meet the demand? Hint: Let
M be a large number such that M number of rolls are enough to satisfy all demand (e.g.,

5
 Pn
M= k=1 dk ). Assume the manufacturer has M number of unmanufactured rolls in the
stock. Use the following decision variables:

1 if roll i is used,

xi = i ∈ {1, . . . , M }.

0 otherwise,

yik = number of rolls of type k (of length lk ) cut from roll i, i = {1, . . . , M }, k = {1, . . . , n}.

11. Shiny Crystals is a privately owned company that specializes in producing the finest crystal
glasses and vases in the world. The owner prefers to focus on providing her customers with
signature collections of four different products: Crystal Wine, Crystal Goblets, Champagne
Glasses, Sherry Glasses. Each type of these products requires the appropriate type of
machinery. The machinery needed to produce each product must be rented at a monthly
rate shown in table below. This table also lists the amount of Silica (SiO2), Lead Oxide
(PbO) and labor hours required per unit, as well as the sales price for each type of product.
In a given month, 1500 labor hours, 50000 tons of Silica, and 8,000 tons of Lead Oxide
are available. Assuming you can sell all what you can produce, which product or products
need to be produced (and in what quantities) in order to maximize profits? Provide a
mathematical formulation.

Rental Labor Silica PbO Selling

Product
Cost ($) (Hours/Unit) (Grams/Unit) (Grams/Unit) Price ($)
Crystal Wine 1500 2 120 28.8 35
Crystal Goblets 1200 1.5 190 26.4 40
Champagne Glasses 1600 3.5 180 43.2 41
Sherry Glasses 1500 4 190 45.6 39

How can you model the following additional restrictions? Define new variables if necessary.

(a) The machinery needed for Crystal Goblets and Sherry Glasses cannot be rented at
the same time.

(b) If you produce more than 100 of Champagne Glasses then you need to produce at
least 100 of Crystal Wine.

(c) At least one of the Crystals should be produced or both of the Champagne and Sherry
Glasses should be produced.

(d) You can order more Lead Oxide, up to 500 kg. The unit cost is $2 per kilogram and
the fixed ordering cost is $100.

6
12. CoolBox manufactures packages that are used for biscuits, cookies, chocolates etc. They
want to prepare a production plan for the next m months. The company has n products
and the demand of product i in month j is dij . To be able to produce any product i in any
month the company needs to pay for the necessary setup which cost fi . Unit production
cost of product i in month j is cij while the price of the product i is pi . Also there is penalty
cost si for each unit of unsatisfied demand of product i. The capacity of production for
product i in month j is capij . The inventory of the company is limited by K products but
there is no inventory cost. Provide an integer programming formulation to maximize the
profit of CoolBox for the next m months.

13. Determine whether the statements below are true or false. For each of your answers, you
need to provide a proof or counterexample, whichever is necessary.

(a) Set S = {x : f (x) ≤ 10} is a convex set, where f is a convex and continuous function.

(b) Set S = {x ∈ Rn : Ax ≤ b} is a convex set, where A is m × n and b is m × 1.

(c) Set S = {x ∈ Rn : Ax ≤ b} always has at least one extreme point, where A is m × n

and b is m × 1.

(d) Set S = {x ∈ R : |x| ≥ 4} is convex, where |.| is absolute value sign.

(e) Consider two convex sets S1 and S2 . Set S1 ∩ S2 is also convex.

14. State the set of solutions for the following linear systems and ranks of the coefficient
matrices:

(a)
x1 + x2 =2
x2 + x3 = 3
x1 + 2x2 + x3 = 5

(b)
x1 + x2 =2
x2 + x3 = 3
x1 + 2x2 + x3 = 0

(c)
x1 + x2 =7
x1 + 2x3 = 10
2x1 + 3x2 + 2x3 = 19

7
15. Consider the following two linear programming problems:

LP 1 : min c1 x1 + c2 x2

s.t. x1 − 2x2 ≤ 4

− x1 + x2 ≤ 3

x1 ≥ 0

x2 ≥ 0

LP 2 : max c1 x1 + c2 x2

s.t. x1 − 2x2 ≤ 4

− x1 + x2 ≤ 3

x1 ≥ 0

x2 ≥ 0

(a) Find the optimum solution of LP1 for min 4x1 − 2x2 .

(b) Show all the extreme points for the feasible region.

(c) Find the cone of exit1 at point x = (0, 3) of LP1.

(d) For what range of values of the c vector, will x = (0, 0) be the unique optimal solution
of LP1. Argue in terms of the cone of exit at this point.

(e) For what range of values of the c vector LP2 has alternative optimal solutions includ-
ing only one extreme point optimal solution. Argue using the cone of exit arguments.
Provide the alternative optimal solution set.

(f) Find the coefficients of c1 and c2 such that LP1 is unbounded and LP2 has a unique
optimal solution. Argue using the cone of exit arguments.

(g) Find coefficients c1 and c2 such that both LP1 and LP2 would be unbounded. (Note
that the same coefficients will be used in both models.)

1
The cone of directions that will take you away from the feasible region through this point.