It can be recalled from the Two Mines example that the conditions for a mathematical model to be a linear program (LP) were:
LP's are important - this is because:
We will return later to the simplex algorithm for solving LP's but for the moment we will concentrate upon formulating LP's.
Some of the major application areas to which LP can be applied are:
Note that the key to formulating LP's is practice. However a useful hint is that common objectives for LP's are maximize profit/minimize cost.
There are four basic assumptions in LP:
1st implication: The value of objective function is the sum of the contributions from each decision variables.
2nd implication: LHS of each constraint is the sum of the contributions from each decision variables.
(Winston 3.1, p. 49)
Giapetto's wooden soldiers and trains. Each soldier sells for $27, uses $10 of raw materials and takes $14 of labor & overhead costs. Each train sells for $21, uses $9 of raw materials, and takes $10 of overhead costs. Each soldier needs 2 hours finishing and 1 hour carpentry; each train needs 1 hour finishing and 1 hour carpentry. Raw materials are unlimited, but only 100 hours of finishing and 80 hours of carpentry are available each week. Demand for trains is unlimited; but at most 40 soldiers can be sold each week. How many of each toy should be made each week to maximize profits?
Decision variables completely describe the decisions to be made (in this case, by Giapetto). Giapetto must decide how many soldiers and trains should be manufactured each week. With this in mind, we define:
x1 = the number of soldiers produced per week x2 = the number of trains produced per week
Objective function is the function of the decision variables that the decision maker wants to maximize (revenue or profit) or minimize (costs). Giapetto can concentrate on maximizing the total weekly profit (z).
Here profit equals to (weekly revenues) – (raw material purchase cost) – (other variable costs). Hence Giapetto’s objective function is:
Maximize z = 3x1 + 2x2
Constraints show the restrictions on the values of the decision variables. Without constraints Giapetto could make a large profit by choosing decision variables to be very large.
Here there are three constraints:
Finishing time per week
Carpentry time per week
Weekly demand for soldiers
Sign restrictions are added if the decision variables can only assume nonnegative values (Giapetto can not manufacture negative number of soldiers or trains!)
All these characteristics explored above give the following Linear Programming (LP) model
max z = 3x1 + 2x2
(The Objective function)
s.t. 2x1 + x2 ≤ 100
x1 +x2 ≤ 80
(Constraint on demand for soldiers)
x1, x2 > 0
A value of (x1, x2) is in the feasible region if it satisfies all the constraints and sign restrictions.
Graphically and computationally we see the solution is (x1, x2) = (20, 60) at which z =
180. (Optimal solution)
The maximum profit is $180 by making 20 soldiers and 60 trains each week. Profit is limited by the carpentry and finishing labor available. Profit could be increased by buying more labor.
(Winston 3.2, p.61)
Dorian makes luxury cars and jeeps for high-income men and women. It wishes to advertise with 1 minute spots in comedy shows and football games. Each comedy spot costs $50K and is seen by 7M high-income women and 2M high-income men. Each football spot costs $100K and is seen by 2M high-income women and 12M high-income men. How can Dorian reach 28M high-income women and 24M high-income men at the least cost?
The decision variables are
x1 = the number of comedy spots
x2 = the number of football spots
The model of the problem:
min z = 50x1 + 100x2
st 7x1 + 2x2 ≥ 28
2x1 + 12x2 ≥
x1, x2 ≥ 0
The graphical solution is z = 320 when (x1, x2) = (3.6, 1.4). From the graph, in this problem rounding up to (x1, x2) = (4, 2) gives the best integer solution.
The minimum cost of reaching the target audience is $400K, with 4 comedy spots and 2 football slots. The model is dubious as it does not allow for saturation after repeated viewings.
(Winston 3.4., p. 70)
Ms. Fidan’s diet requires that all the food she eats come from one of the four “basic food groups“. At present, the following four foods are available for consumption: brownies, chocolate ice cream, cola, and pineapple cheesecake. Each brownie costs 0.5$, each scoop of chocolate ice cream costs 0.2$, each bottle of cola costs 0.3$, and each pineapple cheesecake costs 0.8$. Each day, she must ingest at least 500 calories, 6 oz of chocolate, 10 oz of sugar, and 8 oz of fat. The nutritional content per unit of each food is shown in Table. Formulate an LP model that can be used to satisfy her daily nutritional requirements at minimum cost.
The decision variables:
x1: number of brownies eaten daily
x2: number of scoops of chocolate ice cream eaten daily
x3: bottles of cola drunk daily
x4: pieces of pineapple cheesecake eaten daily
The objective function (the total cost of the diet in cents):
min w = 50x1 + 20x2 + 30x3 + 80x4
The minimum cost diet incurs a daily cost of 90 cents by eating 3 scoops of chocolate and drinking 1 bottle of cola (w = 90, x2 = 3, x3 = 1)
Post Office Example
(Winston 3.5, p.74)
A PO requires different numbers of employees on different days of the week. Union rules state each employee must work 5 consecutive days and then receive two days off. Find the minimum number of employees needed.
The decision variables are xi (# of employees starting on day i)
Mathematically we must
The solution is (xi) = (4/3, 10/3, 2, 22/3, 0, 10/3, 5) giving z = 67/3.
We could round this up to (xi) = (2, 4, 2, 8, 0, 4, 5) giving z = 25 (may be wrong!). However restricting the decision var.s to be integers and using Lindo again gives (xi) = (4, 4, 2, 6, 0, 4, 3) giving z = 23.
(Winston 3.10, p. 99)
Sailco must determine how many sailboats to produce in the next 4 quarters. The demand is known to be 40, 60, 75, and 25 boats. Sailco must meet its demands. At the beginning of the 1st quarter Sailco starts with 10 boats in inventory. Sailco can produce up to 40 boats with regular time labor at $400 per boat, or additional boats at $450 with overtime labor. Boats made in a quarter can be used to meet that quarter's demand or held in inventory for the next quarter at an extra cost of $20.00 per boat.
The decision variables are for t = 1,2,3,4
xt = # of boats in quarter t built in regular time yt = # of boats in quarter t built in overtime
For convenience, introduce variables:
it = # of boats in inventory at the end quarter t dt = demand in quarter t
We are given that d1 = 40, d2 = 60, d3 = 75, d4 = 25, i0 = 10
xt ≤ 40, t
By logic it = it-1+ xt + yt - dt, t.
Demand is met iff it ≥ 0, t
(Sign restrictions xt, yt ≥ 0, t)
We need to minimize total cost z subject to these three sets of conditions where z = 400 (x1 + x2 + x3 + x4) + 450 (y1 + y2 + y3 + y4) + 20 (i1 + i2 + i3 + i4)
Lindo reveals the solution to be (x1, x2, x3, x4) = (40, 40, 40, 25) and (y1, y2, y3, y4) = (0, 10, 35, 0) and the minimum cost of $78450.00 is achieved by the schedule
Customer Service Level Example
(Winston 3.12, p. 108)
CSL services computers. Its demand (hours) for the time of skilled technicians in the next 5 months is
It starts with 50 skilled technicians at the beginning of January. Each technician can work 160 hrs/month. To train a new technician they must be supervised for 50 hrs by an experienced technician for a period of one month time. Each experienced technician is paid $2K/mth and a trainee is paid $1K/mth. Each month 5% of the skilled technicians leave. CSL needs to meet demand and minimize costs.
The decision variable is
xt = # to be trained in month t
We must minimize the total cost. For convenience let yt = # experienced tech. at start of tth month dt = demand during month t
Then we must
min z = 2000 (y1+...+ y5) + 1000 (x1 +...+ x5)
160yt - 50xt ≥ dt for t = 1,..., 5
y1 = 50, d1 = 6000, d2 = 7000, d3 = 8000, d4 = 9500, d5 = 11000
yt = .95yt-1 + xt-1 for t = 2,3,4,5
xt, yt ≥0