1
Linear Programming
1.1 Introduction
Linear programming (LP) is the problem of optimizing (maximizing or min-
imizing) a linear function subject to linear constraints. A wide variety of
practical problems, from nutrition, transportation, production planning, fi-
nance, and many more areas can be modeled as linear programs. We begin
by introducing one of the earliest examples, the diet problem, and then give
some additional applications in the areas of production management, trans-
portation, finance, and personnel scheduling. Some of these examples are not
initially linear programs, but are amenable to being transformed into LPs and
techniques for conversion are illustrated. The embedded assumptions behind
linear optimization problems are discussed. A definition of a standard form of
a linear optimization problem is given and techniques for converting an LP
into standard form are illustrated.
1.1.1 The Diet Problem
Due to a limited budget you would like to find the most economical mix of
food items subject to providing sufficient daily nutrition. The available food
items are peanut butter, bananas, and chocolate, and the cost per serving
is 20 cents, 10 cents, and 15 cents, respectively. The amount of nutrients of
fat, carbohydrates, and protein per serving of peanut butter is 130 grams,
51.6 grams, and 64.7 grams. For bananas, the amounts of these nutrients per
serving are 1 gram, 51 grams, and 2 grams, whereas for chocolate the amounts
per serving are 12 grams, 22 grams, and 2 grams. Suppose it is decided by
a dietician that you need at least 35 grams of fat, at least 130 grams of
carbohydrate, and at least 76 grams of protein daily. Then, a combination
of these three food items should provide you with sufficient amounts of each
nutrient for the day. The problem of determining the least cost combination of
the food items that provide a sufficient amount of nutrients can be represented
as a problem of the following form:
1
© 2014 by Taylor & Francis Group, LLC
2 Introduction to Linear Optimization and Extensions with MATLAB
R
minimize cost of food items used
subject to food items must provide enough fat
food items provide must enough carbohydrates
food items provide must enough protein
This form of the problem reveals two major components, i.e., (1) there
is a goal or objective (minimize cost of food items used) and (2) a set of
constraints that represent the requirements for the problem (food items must
provide enough nutrition). A linear programming problem will exhibit the
same form, but with mathematical representations of the components of the
problem. In general, a linear program will consist of decision variables, an
objective, and a set of constraints.
To illustrate the formulation of the diet problem as a linear program, let
x
pb
= servings of peanut butter
x
b
= servings of bananas
x
c
= servings of chocolate.
These variables represent the quantities of each food item to be used and
should be non-negative, i.e., x
pb
0, x
b
0, and x
c
0, and are called
decision variables since they must be determined.
The total cost associated with any particular combination of food items
x
pb
, x
b
, and x
c
is
.20x
pb
+ .10x
b
+ .15x
c
, (1.1)
which says that the total cost of food items used is the sum of the costs
incurred from the use of each food item.
To ensure that the mix of the three foods will have enough fat one can
impose the following linear inequality constraint
130x
pb
+ 1x
b
+ 12x
c
35, (1.2)
which expresses that the total amount of fat from the three food items should
be at least the required minimum of 35 grams. Similarly, one can impose the
inequality
51.6x
pb
+ 51x
b
+ 22x
c
130 (1.3)
to ensure that a combination of food items will have enough carbohydrates
and finally impose the constraint
64.7x
pb
+ 2x
b
+ 2x
c
76 (1.4)
to ensure enough protein.
© 2014 by Taylor & Francis Group, LLC

Get Introduction to Linear Optimization and Extensions with MATLAB® now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.