Three Products P1, P2, P3, Two Machines M1M2

2.2 Applications of Linear Programming

2.2.1 Production Planning

Three products P1, P2, P3, two machines M1M2.

Machine capacities: 8 & 9 hours, respectively.

The products sell for $20, $15, and $17, respectively.

Table: Processing times of the products on the machines

P1 / P2 / P3
M1 / 3 / 5 / 4
M2 / 6 / 1 / 3

Production costs: M1: $120 per hour, M2: $90 per hour.

Thus the processing costs of the three products are $6, $10, & $8 on M1 & $9, 1.50, & $4.50 on M2.

The per-unit profit contributions are $5, $3.50, & $4.50.

Variables: xj: number of units of product j made & sold.

Max z = 5x1 + 3.5x2 + 4.5x3

s.t. 3x1 + 5x2 + 4x3 ≤ 540

6x1 + 1x2 + 3x3 ≤ 480

x1, x2, x3 ≥ 0.

Optimal solution: = 20, = 0, & = 120 (both slacks are zero), with = 640.

2.2.2 The Diet Problem

Versions:

(1) minimize the cost, s.t. nutritional requirement

(2) maximize nutritional value, s.t. costs.

Version (2) is problematic: nutritional value is multidimensional.

Example:

Hamburger
3½ oz / Medium fries
4 oz / Cheesecake
2.8 oz / Nutritional requirement
Calories / 250 / 380 / 257 / [1,800; 2,200]
Fat / 13% / 31% / 28% / ≤ 100%
Cost per serving / $1.59 / $2.19 / $2.99

Variables: xj: quantity of food j in the diet.

P: Min z = 1.59x1 + 2.19x2 + 2.99x3

s.t. 250x1 + 380x2 + 257x3 ≥ 1,800

(calories, lower bound)

250x1 + 380x2 + 257x3 ≤ 2,200

(calories, upper bound)

13x1 + 31x2 + 28x3 ≤ 100

(fat, upper bound)

x1, x2, x3 ≥ 0. (nonnegativity constraints)

Optimal solution: Include = 6⅓ hamburgers, = ½ serving of fries, and no cheesecake. This solution provides 100% of the allowable fat intake, generate 1,800 calories, and costs $11.32.

Review: too many hamburgers! Revise the model & re-solve.

Larger example:

The diet should include

between 1,800 and 2,200 calories,
no more than 65g of fat,
no more than 300mg of cholesterol,
no more than 2,400 mg of sodium,
at least 300g of carbohydrates,
at least 25g of fiber,
at least 50g or protein, and
at least 100% of the recommended daily allowance of vitamins A and C, calcium, and iron.

Define variables x1, …, x8 for the number of servings of the eight foods.

P: Min z = .19x1 + .56x2 + .90x3 + .82x4 + .51x5 + .53x6 + .37x7 + .32x8

s.t. 300x1 + 60x2 + 220x3 + 259x4 + 110x5 + 132x6 + 55x7 +

152x8 ≥ 1,800(Calories, lower bound)

300x1 + 60x2 + 220x3 + 259x4 + 110x5 + 132x6 + 55x7 +

152x8 ≤ 2,200(Calories, upper bound)

1x1 + 13x3 + 16.3x4 + 2.5x5 + 0.22x7 + 9.8x8 ≤ 65 (Fat)

5x3 + 89x4 + 10x5 ≤ 300(Cholesterol)

1x1 + 650x2 + 790x3 + 95x4 + 120x5 + 5x6 + 1.1x7 + 168.4x8

≤ 2,400(Sodium)

63x1 + 12x2 + 19x3 + 20x4 + 12x5 + 33.4x6 + 14.6x7 + 15x8

≥ 300(Carbohydrates)

3x1 + 3x2 + 2x3 + 2.5x7 + 1.3x8 ≥ 25 (Fiber)

11x1 + 2x2 + 5x3 + 26.1x4 + 9x5 + 0.5x6 + 0.3x7+ 2x8 ≥ 50 (Protein)

8x2 + 2x3 + 1x4 + 10x5 + 2x6 + 1x7 ≥ 100 (Vitamin A)

30x2 + 2x3 + 62x6 + 8x7 + 15x8 ≥ 100 (Vitamin C)

2x1 + 2x2 +2x3 + 1x4 + 30x5 + 1x7 + 1x8 ≥ 100 (Calcium)

20x1 + 15x2 + 8x3 + 17x4 + 2x6 + 1x7+ 3x8 ≥ 100 (Iron)

x1, x2, …, x8 ≥ 0(Nonnegativity constraints)

Successive changes in the solution to make the diet more palatable:

(1)No more than 4 servings of milk. No feasible solution! Add yoghurt, bread, and margarine.

(2)No more than 6 slices of bread.

(3)No more than four servings of margarine.

(4)Add eggs.

(4a) No more than 2,000 (rather than 2,200) calories.

(4b) Reduce cholesterol from 300 to 250 units.

Original solution “0” / Solution
“1” / Solution “2” / Solution “3” / Solution “4” / Solution “4a” / Solution “4b”
Calories  [1,800;2,200] / 1,800 / 2,200 / 2.200 / 2,200 / 2,200 / 2,000 / 2,000
Fat  65 / 28 / 65 / 65 / 52 / 57 / 58 / 56
Cholesterol  300 / 101 / 39 / 35 / 74 / 300 / 300 / 250
Sodium  2,400 / 2,400 / 2,400 / 2,400 / 1,097 / 1,674 / 1,358 / 1,231
Carbs  300 / 369 / 340 / 340 / 401 / 366 / 324 / 332
Fiber  25 / 25 / 25 / 25 / 25 / 25 / 25 / 25
Protein  50 / 120 / 75 / 74 / 58 / 72 / 67 / 64
Vitamin A  100% / 100 / 100 / 100 / 100 / 100 / 100 / 100
Vitamin C  100% / 100 / 100 / 100 / 409 / 263 / 232 / 264
Calcium 100% / 293 / 118 / 111 / 129 / 130 / 131 / 131
Iron 100% / 100 / 103 / 107 / 100 / 100 / 100 / 100

2.2.3 Allocation Problems

Allocating scarce resources to economic activities.

Investment problems: Allocate money to investments.

Example 1: Invest $300,000. It is possible to borrow up to $100,000 at 6%.

Table 2.2.6: Types of investments and their features

Investment type / Expected annual interest/dividend / Expected annual increase in value / Average risk per dollar
Real estate / 0% / 18% / 20
Silver / 0% / 10% / 12
Savings account / 2% / 0 / 1
Blue chip stocks / 3% / 6% / 7
Bonds / 4% / 0% / 3
Hi-tech stocks / 0% / 20% / 30

Version 1: Maximize the expected value of the assets at the end of the planning period, s.t. highest acceptable risk.

Version 2: Minimize the overall risk of the portfolio, s.t. smallest acceptable return.

The expected value of assets (exclusive interest) at the end of the planning period should be at least 7% higher than at the beginning,
invest at least 50% of all the money invested in stocks and bonds combined,
invest no more than 20% of total amount available (excluding the amount borrowed) in real estate and silver combined, and
the average risk of the portfolio should not exceed 10.

Define variables:xj: the dollar amount invested in the j-th alternative.

P: Max z = 1.18x1 + 1.10x2 + 1.02x3 + 1.09x4 + 1.04x5 +

1.20x6 1.12x7

s.t. x1 + x2 + x3 + x4 + x5 + x6 ≤ 300,000 + x7

x7 ≤ 100,000

1.18x1 + 1.10x2 + 1.00x3 + 1.06x4 + 1.00x5 + 1.20x6

≥ 1.07(x1 + x2 + x3 + x4 + x5 + x6)

x4 + x5+ x6 ≥ 0.5(x1 + x2 + x3 + x4 + x5 +x6)

x1 + x2 ≤ 0.2(300,000)

20x1 + 12x2 + x3 + 7x4 + 3x5 + 30x6

≤ 10(x1 + x2 + x3 + x4 + x5 + x6)

x1, x2, …, x7 ≥ 0

Version 2 (with the same parameters): at least 7% appreciation of theinvestment.

P: Minz = 20x1 + 12x2 + x3 + 7x4 + 3x5 + 30x6

s.t. x1 + x2 + x3 + x4 + x5 + x6 ≤ 300,000 + x7

x7 ≤ 100,000

1.18x1 + 1.10x2 + 1.00x3 + 1.06x4 + 1.00x5 + 1.20x6

≥ 1.07(x1 + x2 + x3 + x4 + x5 + x6)

x4 + x5+ x6 ≥ 0.5(x1 + x2 + x3 + x4 + x5 + x6)

x1 + x2 ≤ 0.2(300,000)

1.18x1 + 1.10x2 + 1.02x3 + 1.09x4 + 1.04x5 +

1.20x6≥ 321,000

x1, x2, …, x7 ≥ 0

Investment type / Version 1 with 12%
interest / Version 1 with 10% interest / Version 2
Real estate / 60,000 / 60,000 / 0
Silver / 0 / 0 / 0
Savings account / 0 / 0 / 160,500
Blue chip stocks / 234,782.61 / 321,739.13 / 0
Bonds / 0 / 0 / 160,500
Hi-tech stocks / 5,217.39 / 18,260.87 / 0
Amount borrowed / 0 / 100,000 / 21,000

Example 2: Allocation of police officers to districts.

67 police officers are to be allocated to five districts.

A / B / C / D / E
Additional marginal protection per officer / 3 / 7 / 10 / 5 / 4
Lowest acceptable protection / 40 / 50 / 70 / 60 / 40

Unused police officers can be hired out for $100 per hour.

It must be ensured that each district has at least the minimum protection as specified in the table,
the average protection is at least 50, and
we have to allocate at least 50% more officers to districts A, B, and C combined than to districts D and E combined.

Define variables xj as the number of police officers allocated to district j.

Maximize the municipality’s income.

P: Max z = 100[67  (xA + xB + xC + xD + xE )]

s.t. xA + xB + xC + xD + xE  67

3xA 40

7xB 50

10xC 70

5xD 60

4xE 40

(3xA + 7xB + 10xC + 5xD + 4xE)/5  50

xA + xB+ xC 1.5(xD + xE)

xA, xB, xC, xD, xE 0

Optimal solution: Allocate 13⅓, 12⅔, 7, 12, and 10, police officers, respectively. → 55 police officers are allocated, and 12 are hired out. The municipality’s income is $1,200.

Protection: 40, 88⅔, 70, 60, and 40: all districts except the second receive the minimal protection required, while district B receives 88⅔/50  1.77 the minimally required protection.

2.2.4: Employee Scheduling.

Allocate employees to shifts. Shifts start every four hours at 0600 hrs, 1000 hrs, 1400 hrs, etc. Minimize the total number of employees required.

Personnel requirements during 4-hour time slots

Shift / 0600
1000 / 1000
1400 / 1400
1800 / 1800
2200 / 2200-0200 / 0200
0600
Required number of employees / 17 / 9 / 19 / 12 / 5 / 8

Define variables x06, x10, x14, x18, x22 and x02 as the number of employees who start their shift at 6 a.m., 10 a.m., 2 p.m., etc.

P: Min z = x06 + x10 + x14 + x18 + x22 + x02

s.t. x06 + x02 ≥ 17

x06 + x10 ≥ 9

x10 + x14 ≥ 19

x14 + x18 ≥ 12

x18 + x22 ≥ 5

x22 + x02 ≥ 8

x06, x10, x14, x18, x22, x02 ≥ 0

Often, multiple solutions exist. Here, 41 employees are required. The solution is:

Starting times of employees in optimal solution for 4-hour time slots

Start of shift / 0600 / 1000 / 1400 / 1800 / 2200 / 0200
Number of employees / 14 / 7 / 12 / 0 / 5 / 3

The same problem with 2-hour time slots:

Shift / 0600
0800 / 0800
1000 / 1000
1200 / 1200
1400 / 1400
-1600 / 1600
1800
Required number of employees / 17 / 11 / 9 / 7 / 13 / 19
Shift / 1800
2000 / 2000
2200 / 2200
2400 / 2400
0200 / 0200
-0400 / 0400
0600
Required number of employees / 12 / 8 / 5 / 3 / 3 / 8

P: Min z = x06 + x08 + x10 + x12 + x14 + x16 + x18 + x20 + x22 +

x24 +x02 + x04

s.t. x06+x24 + x02 + x04 ≥ 17

x06 + x08+x02 + x04 ≥ 11

x06 + x08 + x10+ x04 ≥ 9

x06 + x08 + x10 + x12 ≥ 7

x08 + x10 + x12 + x14 ≥ 13

x10 + x12 + x14 + x16 ≥ 19

x12 + x14 + x16 + x18 ≥ 12

x14 + x16 + x18 + x20 ≥ 8

x16 + x18 + x20 + x22 ≥ 5

x18 + x20 + x22 + x24 ≥ 3

x20 + x22 + x24 + x02 ≥ 3

x22 + x24 + x02 + x04 ≥ 8

x06, x08,x10, x12, x14, x16, x18, x20, x22, x24, x02, x04 ≥ 0

Starting times of employees in optimal solution for 2-hour time slots:

Start of shift / 06 / 08 / 10 / 12 / 14 / 16 / 18 / 20 / 22 / 24 / 02 / 04
Number of employees / 0 / 0 / 7 / 4 / 3 / 5 / 0 / 0 / 0 / 3 / 0 / 14

We now need 36 employees, 12% less than before.

2.2.5 Dynamic Production – Inventory Models

For a single good, schedule the production & the inventory levels for various months. The objective is either cost minimization or profit maximization.

Example: Parameters for the dynamic production–inventory model are shown in the table below:

Month 1
(January) / Month 2
(February) / Month 3
(March) / Month 4
(April)
Estimated demand / 80 / 70 / 130 / 150
Production capacity / 120 / 140 / 150 / 140
Unit production cost / $1.00 / $1.10 / $1.20 / $1.25

Inventory unit carrying costs:

January – February: 5¢

February – March: 15¢

March – April: 15¢

Opening inventory: 20 units, ending inventory: zero.

Define variables x1, x2, x3, and x4as the quantities to be manufactured in months 1, 2, 3, and 4, respectively.

Define inventory variables by I1, I2, I3, I4, and I5as the inventory levels at the beginning of months 1 to 5.

Note that I1 and I5 are not variables, but parameters whose numbers we know: I1 = 20, and I5 = 0.

Minimize the production & inventory costs.

Min z = 1x1 + 1.1x2 + 1.2x3 + 1.25x4 + .05I2 + .15I3 + .15I4

s.t. x1 ≤ 120

x2 ≤ 140

x3 ≤ 150

x4 ≤ 140

I2 = I1 +x1 80 (or, as I1 = 20, x1I2 = 60)

I3 + I2 + x2 = 70

I4 + I3 + x3 = 130

I5 + I4 + x4 = 150 (or, as I5 = 0, x4 + I4 = 150)

x1, x2, x3, x4, I2, I3, I4 ≥ 0.

The optimal solution calls for a production of 120, 10, 140 and 140 units of the product in the four months. The inventory levels are then 60, 0, & 10 units. The total costs are $478.50.

A simple extension: Warehouse capacities. Here:

I2 ≤ 40

I3 ≤ 50

I4 ≤ 50.

New solution: production levels: 100, 30, 140, and 140, inventory levels 40, 0 and 10,costs $479.50 (a $1 increase).

Alternative formulation: Define variables xij:the number of units manufactured in month i for use in month j.

Same example:

P: Min z = 1x11 + 1.05x12 + 1.2x13 + 1.35x14 + 1.1x22

+ 1.25x23 + 1.4x24+ 1.2x33 + 1.35x34 + 1.25x44

s.t. x11 + x12 + x13 + x14 ≤ 120

x22 + x23 + x24 ≤ 140

x33 + x34 ≤ 150

x44 ≤ 140

x11 ≥ 60 (January’s demand is reduced by the

available opening inventory of 20 units)

x12 + x22 ≥ 70

x13 + x23 + x33 ≥ 130

x14 + x24 + x34 + x44 ≥ 150

x11, x12, x13, x14, x22 , x23 , x24, x33 , x34, x44 ≥ 0.

Optimal solution:

Month 1 / Month 2 / Month 3 / Month 4
Month 1 / 60 / 60 / 0 / 0
Month 2 /  / 10 / 0 / 0
Month 3 /  /  / 130 / 10
Month 4 /  /  /  / 140

Period 1 Period 2 Period 3 Period 4

20+12080= 60 0+140 130 = 10

60+1070 = 0 10+ 140150=0

2.2.6 Blending problems

Examples: Wines tea, coffee, tobacco, whiskey, etc.

General idea: Blend different types to achieve a desired taste and constant quality throughout the years.

Define variables xij: quantity of raw material i that goes into product j. (Number of “scoops”).

Example: Blending of wine.

Three grapes:Riesling, Müller-Thurgau, and Silvaner.

Two blends: Filzener HexenhammerLeiwener Hosenscheisser.

Availability of wines: 10,000, 5,000, and 6,000 gallons at a cost of $8, $6, and $5 per gallon.

Estimated demands for blends: 7,000 and 8,000 gallons,

sales prices are $16 and $18 per gallon.

Blending rules:

Blends
Basic wines / Filzener Leiwener
Hexenhammer Hosenscheisser
Riesling
Müller-Thurgau
Silvaner / [.45; .55] [.20; .50]
[.10; .15] [.10; .60]
[.35; .35] [.30; .40]

Given the variable definitions, the quantities of the three basic wines used in the process are x11 + x12, x21 + x22, x31 + x32. The quantities of the two blends are x11 + x21 + x31 (Hexenhammer)x12 + x22 +x32 (Hosenscheisser).

Max z = [16(x11 + x21 + x31) + 18(x12 + x22 + x32)]

 [8(x11 + x12) + 6(x21 + x22) + 5(x31 + x32)]

s.t. (supply constraints)

(demand constraints)

x11 ≥ .45(x11 + x21 + x31)

x21 ≥ .1(x11 + x21 + x31)

x31 ≥ .35(x11 + x21 + x31)

x12 ≥ .2(x12 + x22 + x32)

x22 ≥ .1(x12 + x22 + x32)

x32 ≥ .3(x12 + x22 + x32)

(Blending constraints)

x11, x12, x21, x22, x31, x32 ≥ 0.

Optimal solution: In Hexenhammer, we use

3,850 gallons of Riesling,

700 gallons of Müller-Thurgau,

2,450 gallons of Silvaner

for a total of 7,000 gallons (exactly as much as required).

In Hosenscheisser, we use

3,983.33 gallons of Riesling,

4,300 gallons of Müller-Thurgau,

3,550 gallons of Silvaner

For a total of 11,833.33 gallons (much more than the

lower bound).

Use of resources:

7,833.33 gallons of Riesling (2,166.67 gallons left over),

5,000 gallons of Müller-Thurgau(all used up), &

6,000 gallons of Silvaner(also all used up).

The overall profit is $202,333.33.

2.2.7 Transportation and Assignment Problems

(Hitchcock, 1941).

The same structure as blending problems with originsdestinations.

A single good is available at m origins (e.g., warehouses) in quantities si (supplies) & is required at n destinations (e.g., customers) in quantities dj.

The transportation cost function is linear.

Balanced vs. unbalanced problems. For now, assume that the problems are balanced.

Example: 2 origins with supplies 20 & 30,

3 destinations with demands 15, 25, 10.

Unit transportation cost in matrix

C = .

P: Min z = 1x11 + 7x12 + 4x13 + 2x21 + 3x22 + 5x23

s.t. x11 + x12 + x13 = 30

x21 + x22 + x23 = 20

x11 + x21 = 15

x12 + x22 = 25

x13 + x23 = 10

x11, x12, x13, x21, x22, x23 ≥ 0.

Note the block-angular structure.

The structure allows specialized algorithms: stepping stone methodMODI (Modified DIstribution method).

(m + n – 1) constraints due to linear dependency.

Optimal solution:

T =with costs = 150.

Unbalanced problems:

Case 1: Total supply > total demand.

No more than the total demand can flow through the network → demand constraints remain as “=” & the supply constraints are now of type “≤.” Some supply will be left over at some warehouses.

Case 2: Total supply < total demand.

No more than the total supply can flow through the network → supply constraints remain as “=” & the demand constraints are now of type “≥.” Some unsatisfied demand will be left over at some destinations.

Additional considerations:

Reshipments (allowing back-&-forth shipments), &
Overshipments (allowing shipping too much to customers: the more-for-less paradox).

While the implementation of reshipments is easy, overshipments will require some sharing of savings.

Assignment Problems:

(Employee assignment, “marriage problems”)

Given: n employees, n jobs. (re-)training costs. Allocate employee time to jobs so as to minimize assignment costs.

Define xij as the percentage of worker i’s time that is assigned to task j.

Example:

C = .

P: Min z = 4x11 + 3x12 + 1x13 + 8x21 + 5x22 + 3x23 + 2x31 + 6x32 + 2x33

s.t. x11 + x12 + x13 = 1

x21 + x22 + x23 = 1

x31 + x32 + x33 = 1

x11 + x21 + x31 = 1

x12 + x22 + x32 = 1

x13 + x23 + x33 = 1

x11, x12, x13, x21, x22, x23, x31, x32, x33 ≥ 0.

This is same structure as in transportation problems.

The problem has integer solutions. Due to its special structure, dedicated algorithms are available: Hungarian method (Egerváry).