7.
LINEAR PROGRAMMING APPLICATIONS
7.1 Employee Scheduling Problem
In the maintenance department of a large plant, the maintenance personnel
work in three shifts as shown in the Table 1 below:
Table 1
Shifts versus time intervals
Shift 8-hour time interval
1 8 a.m. – 4 p.m
2 4 p.m. – 12 midnight
3 12 midnight – 8 a.m.
Past experience indicates that the demand for maintenance in the plant
varies a 4 – hour periods, while the personnel work in 8-hour shifts. Table
2 below depicts the number and times of the 4-hour periods along with the
maintenance personnel requirements
Table 2
Period versus personnel requirements
Period Time Personnel
number requirement
1 8 a.m. – 12 noon 80
2 12 noon – 4 p.m 60
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
3 4 p.m. – 8 p.m. 30
4 8 p.m. – 12 midnight 50
5 12 midnight – 4 a.m. 20
6 4 a.m. – 8 a.m. 20
How can the maintenance personnel be scheduled to work periods so that
the total maintenance personnel required is minimized while each of the
maintenance workers works 8 hours per shift?
Model Building
1. Select and define the decision variables of the problem
X1 = personnel allocated to work periods 1 and 2
X2 = personnel allocated to work periods 2 and 3
X3 = personnel allocated to work periods 3 and 4
X4 = personnel allocated to work periods 4 and 5
X5 = personnel allocated to work periods 5 and 6
X6 = personnel allocated to work periods 6 and 1
2. Select measure of effectiveness and define objective function
Minimize personnel: Z = X1 + X2 + X3 + X4 + X5 + X6
3. Formulate constraints of the problem
X1 + X6 ≥ 80
X1 + X 2 ≥ 60
X2 + X 3 ≥ 30
X3 + X 4 ≥ 50
X4 + X 5 ≥ 20
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
X5 + X 6 ≥ 20
Non negativity
X1 , X2 , X3 , X4 ,X5 ,X6 ≥0
MODEL
Minimize personnel: Z = X1 + X2 + X3 + X4 + X5 + X6
Subject to:
X1 + X6 ≥ 80
X1 + X 2 ≥ 60
X2 + X 3 ≥ 30
X3 + X 4 ≥ 50
X4 + X 5 ≥ 20
X5 + X 6 ≥ 20
X1 , X2 , X3 , X4 ,X5 ,X6 ≥0
7.2 Manufacturing Problem
A manufacturer of electronic equipment items A , B, C , D and E finds out
that there are certain components in inventory that will not be used in the
recently redesigned products to be manufactured next year. The
management therefore desires three components to be used before the end
of the year in the current products to the best profit advantage. The
quantities of the components available in inventory are presented in the
Table 1 below:
Table 1: Quantities of components available in inventory
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
Resistors Capacitors Transformers Speakers Transistors
2000 1800 750 500 2250
Each product uses certain quantities of components left in the inventory as
shown in Table 2 below:
Table 2: Quantities of components used
Product A B C D E
Resistors 1 4 0 3 5
Capacitors 2 3 2 2 6
Transformers 1 1 1 1 2
Speakers 1 1 0 0 2
Transistors 2 3 2 4 8
A consultation with the sales department has indicated that at most 200,
150, 50, 400 and 500 units of products A, B, C, D and E can be sold within
the remaining months of the year; with unit profits as shown in Table 3
below:
Table 3: Unit profits of products
Products A B C D E
Profit contribution per unit($) 3 4 8 6 2
In order to maximize profits, how many of each of the five products should
be manufactured so that as many electronic components as possible can
be used from the inventory for manufacturing?
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
Model Building
1. Select and define the decision variables of the problem
XA = quantity of product A to be manufactured
XB = quantity of product B to be manufactured
XC = quantity of product C to be manufactured
XD = quantity of product D to be manufactured
XE = quantity of product E to be manufactured
2 Select measure of effectiveness and define objective function
Maximize profit: Z = 2XA + 4XB + 8XC + 6XD + 2XE
3. Formulate constraints of the problem
Number of resistors available
3XA + 4XB + 3XD + 5XE ≤ 2000
Number of capacitors available
2XA + 3XB + 2XC + 2XD + 6XE ≤ 1800
Number of transformers available
XA + XB + XC + XD+ 2XE ≤ 750
Number of speakers available
XA + XB + 2XE ≤ 500
Number of transistors available
2XA + 3XB + 2XC + 4XD+ 8XE ≤ 2250
Upper limits of demand for products
X4 ≤ 200
XB ≤ 150
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
XC ≤ 50
XD ≤ 400
XE ≤ 500
Non negativity
X4 , X B , X C , X D , X E ≥ 0
MODEL
Maximize profit: Z = 2XA + 4XB + 8XC + 6XD + 2XE
Subject to:
3XA + 4XB + 3XD + 5XE ≤ 2000
2XA + 3XB + 2XC + 2XD + 6XE ≤ 1800
XA + XB + XC + XD+ 2XE ≤ 750
2XA + 3XB + 2XC + 4XD+ 8XE ≤ 2250
X4 ≤ 200
XB ≤ 150
XD ≤ 400
XE ≤ 500
X4 , X B , X C , X D , X E ≥ 0
7.3 The Blending Problem
A manufacturer of animal feed is producing feed mix for dairy cattle. The
feed mix contains two active ingredients and a filler to produce bulk. One
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
kg of feed mix must contain a minimum quantity of each four nutrients as
below:
Nutrient A B C D
Grams 90 50 20 2
The ingredients have the following nutrient values and cost
A B C D Cost/kg($)
Ingredient 1 (grams/kg) 100 80 40 10 40
Ingredient 2 (grams/kg) 20 150 20 - 60
What should be the amounts of active ingredients and filler in one kg of
feed mix?
Model Building
1. Select and define the decision variables of the problem
X1 = amount (kg) of ingredient 1 in one kg of feed mix
X2 = amount (kg) of ingredient 2 in one kg of feed mix
X3 = amount (kg) of ingredient 3 in one kg of feed mix
2. Select measure of effectiveness and define objective function
Minimize cost: Z = 40X1 + 60X2
3. Formulate constraints of the problem
Nutrients
100X1 + 200X2 ≥ 90 nutrient A
80X1 + 150X2 ≥ 50 nutrient B
40X1 + 20X2 ≥ 20 nutrient C
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
10X1 ≥2 nutrient D
Balancing constraint
X1 + X 2 + X 3 = 1
Non negativity
X1 , X 2 , X 3 ≥ 0
MODEL
Minimize Z = 40X1 + 60X2
Subject to:
100X1 + 200X2 ≥ 90
80X1 + 150X2 ≥ 50
40X1 + 20X2 ≥ 20
10X1 ≥2
X1 + X 2 + X 3 = 1
X1 , X2 , X3 ≥ 0
7.4 Financial Planning Problem
A bank makes four kinds of loans to its personal customers and these loans
yield the following annual interest rates to the bank:
First mortgage 14 % Second mortgage 20 %
Home improvement 20 % Personal overdraft 10%
The bank has a maximum foreseeable lending capability of $250 million
and is further constrained by the following policies:
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
1. Financial mortgages must be at least 55% of all the mortgages used
and at least 25% of all loans issued (in $ terms)
2. Second mortgages cannot exceed 25% of all loans issued (in $
terms)
3. To avoid public displeasure and the introduction of a new tax, the
average interest rate on all loans must not exceed 15%
Formulate the linear programming problem so as to maximize interest
income while satisfying the policy limitations
Model Building
1. Select and define the decision variables of the problem
X1 = amount loaned in first mortgage
X2 = amount loaned in second mortgage
X3 = amount loaned for home improvement
X4 = amount loaned for personal overdraft
2. Select measure of effectiveness and define objective function
Maximize interest income: Z = 0.14X1 + 0.20X2 + 0.20X3 + 0.10X4
3. Formulate constraints of the problem
Limit on amount lent
X1 + X 2 + X 3 + X 4 ≤ 250
Policy condition 1
X1 ≥ 0.55( X1 + X2 )
That is first mortgages ≥ 0.55(total mortgage lending)
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
and X1 ≥ 0.25( X1 + X2 + X3 + X4)
Policy condition 2
X2 ≥ 0.25( X1 + X2 + X3 + X4)
Policy condition 3
The total amount of interest is
( 0.14 X1 + 0.20 X2 + 0.20 X3 + 0.10 X4) on total loans of
(X1 + X2 + X3 + X4 ) and the constraint for policy condition 3 is
0.14 X1 + 0.20 X2 + 0.20 X3 + 0.10 X4 ≤ 0.15( X1 + X2 + X3 + X4 )
Non negativity
X1 , X 2 , X 3 , X 4 ≥ 0
MODEL
Maximize Z = 0.14X1 + 0.20X2 + 0.20X3 + 0.10X4
Subject to:
X1 + X2 + X3 + X4 ≤ 250
X1 ≥ 0.55( X1 + X2 )
X1 ≥ 0.25( X1 + X2 + X3 + X4)
X2 ≥ 0.25( X1 + X2 + X3 + X4)
0.14 X1 + 0.20 X2 + 0.20 X3 + 0.10 X4 ≤ 0.15( X1 + X2 + X3 + X4 )
X1 , X 2 , X 3 , X 4 ≥ 0
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
REFERENCES
[1] Balnaver M, Caputi P Introduction to Quantitative Research Methods,
SAGE Publications Ltd, 2001
[2] Brandimarte P Quantitative Methods: An Introduction for Business
Management, John Wiley and Sons, 2011
[3] Aidley D Introducing Quantitative Methods: A Practical Guide,
Bloomsbury, 2018
[4] Canela M.A., Alegre I, Ibarra A Quantitative Methods for Management A
Practical Approach, Springer International Publishing, 2014
Ad
MME 8201 Industrial Modeling & Algorithms Dr Kizito Paul Mubiru
