Introduction to Linear Optimization and Extensions with MATLAB®

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