2

Linear programming

Learning objectives
After finishing this chapter, you should be able to:

formulate a linear programming model for a given problem;

solve a linear programming model with two decision variables graphically;

solve linear programming models using Excels Solver;

understand the information provided in a sensitivity analysis; and

understand how primal and dual problems relate to each other.

Theory in action
Since the late 1940s, linear programming models have been used for many
different purposes. Airline companies apply these models to optimise their
use of planes and staff. NASA has been using them for many years to optimise
their use of limited resourses. Oil companies use them to optimise their refinery operations. Small and medium-sized businesses use linear programming
to solve a huge variety of problems, often involving resource allocation.

Typical optimisation problems maximise or minimise the value of a given

variable (such as profit, total costs, etc.) when other specified variables (production capacity, required product quantities, etc.) are constrained. The field of
mathematical programming includes a number of optimisation methods, each
described by a mathematical model. In such a model, there is one expression
the objective function that should be maximised or minimised (or in some
cases set to a desired value). In addition, the model must include constraints that
are described by mathematical expressions.

Chapter 2 Linear programming

The most widely used models include only linear relationships, and belong to
the field of linear programming. In such models both the objective function and
the constraints are linear mathematical expressions. Lets illustrate this with an
example:
Sygitron, a television manufacturer, has decided to produce and sell two different types of TV sets, one small (product 1) and one big (product 2). They
assume that product 1 will give a profit of $300 per unit and product 2 a profit
of $500 per unit. Sygitron has one production plant with four departments:
moulding, soldering, assembly and inspection. Each TV set is processed in
sequence through these four departments. Each department has a limited
capacity given by a maximum number of working hours per year. We assume
Sygitron can sell all the TV sets they are able to produce (the market is not a
restriction).
The problem to be solved is that Sygitron wants to maximise its total profit by
finding the optimal use of its limited production capacity. To find out how this
should be done, we need to know both how many production hours each TV set
uses in each department, and the total capacity of each department. This information is shown in Table 2.1.
Table 2.1 Time consumption and capacity in Sygitron departments
Dept.

Hours used by one unit

of product 1

Hours used by one unit

of product 2

Capacity in hours
per year

Moulding

4 000

Soldering

1 200

Assembly

2 000

Inspection

5 000

At this point, with all necessary information provided, we can formulate the problem as a mathematical model. First, we define the decision variables:
x1  number of product 1 produced per year (small TV sets).
x2  number of product 2 produced per year (big TV sets).
Next, we formulate the objective function, which is given the symbol Z. In this
case, we need an equation for calculating the total profit per year:
Z  300x1  500x2
Total profit per year is (profit per unit of product 1)  (number of product 1 produced per year)  (profit per unit of product 2)  (number of product 2 produced

Graphical solution of a maximisation problem

per year). The objective is to maximise Z without exceeding the capacity of any
of the four departments. These capacities are formulated as mathematical expressions called constraints:
Moulding

x1 + 5x2 4 000

Soldering

x1 + x2 1200

Assembly

2 x1 + x2 2 000

(2.1)

Inspection 2 x1 + 5x2 5000

The last equation for the inspection department says that the time used per
year, which is (2 hours per unit of product 1)  (number of product 1 per year) 
(5 hours per unit of product 2)  (number of product 2 per year), must not exceed
the limit of 5 000 hours. In addition, you must remember that the decision
variables have their own constraints. Since it is impossible to produce a negative
number of products, x1  0 and x2  0 are required. Now the entire mathematical
model can be presented:
Maximise

Z = 300 x1 + 500 x2

Constraints:
Moulding

x1 + 5x2 4 000

Soldering

x1 + x2 1200

Assembly

2 x1 + x2 2 000

(2.2)

Inspection 2 x1 + 5x2 5000

x1 , x2 0
The objective is to find the maximum value of Z, subject to the given constraints.
How should this be done? The answer is by using a computer program. This subject will be discussed in Section 2.3. First, to help you to understand the theory
of linear programming better, we will study a graphical solution of this problem.

2.1

Graphical solution of a maximisation problem

When mathematical programming is used to solve genuine problems, models

usually contain many variables, sometimes more than fifty. Therefore, computer
solutions are the only viable way to go in real life. The problem described by
equation 2.2 contains only two variables, x1 and x2. In such a simple example, it
is possible to show all equations involving x2 as functions of x1 in a coordinate
system. If we rewrite the constraints in equation 2.2 as equations, we obtain the
following capacity lines:

Chapter 2 Linear programming

Moulding

x1 + 5x2 = 4 000

Soldering

x1 + x2 = 1200

Assembly

2 x1 + x2 = 2 000

(2.3)

Inspection 2 x1 + 5x2 = 5000

These equations express the linear combinations of x1 and x2 that occupy the
maximum capacities in each of the four departments. The capacity lines are
shown in Figure 2.1. The constraints in equation 2.2 tell us that the values of
x1 and x2 must lie below all of the capacity lines. These capacity lines, and the
constraints x1, x2  0, define a feasible region shown as the shaded area in Figure
2.2. Combinations of x1 and x2 within the feasible region are the only ones possible. In this case the feasible region is defined by only three capacity lines and
x1, x2  0. Note that the inspection departments capacity is not fully used for any
combination of x1 and x2.
x2

Assembly
Moulding
Inspection
Soldering

1 200
1 000
800
600
400
200

00

12

00

10

80

60

40

20

x1

Figure 2.1 Capacity lines for Sygitron departments

x2
1 200
1 000
800

Moulding
Soldering

600
400

Feasible region

200

Assembly

40
0
60
0
80
0
10
00
12
00

20

x1

Figure 2.2 Feasible region for Sygitron

Now, the challenge is to find the combination of x1 and x2 within the feasible
region that maximises the objective function (maximises total profit):
Z  300x1  500x2

Graphical solution of a maximisation problem

For a given value of Z, this equation expresses linear combinations of x1 and x2.
In our example we may call this a profit line, but the general name is objective
function line. In Figure 2.3 the objective function line for Z  $200 000 is drawn.
The line lies within the feasible region and illustrates all combinations of x1 and
x2 that gives a total profit of $200 000. A higher value of Z gives an objective function line at a higher level as shown for Z  $300 000.
x2
1 200
1 000
800

Optimal solution

600

Z=

Z = $300
0
$2
00 00
00
0

400
200

x1

20

00

80

60

40

20

Figure 2.3 Optimal solution for Sygitron

The figure shows that objective function lines represent higher values for the
objective function as the lines are displaced parallel to each other at higher levels.
But the optimal solution must be a part of the feasible region. Figure 2.3 shows
that as we move the objective function line outwards, the last contact with the
feasible region is the corner point made up between the two capacity lines for
the moulding and the soldering departments. The optimal solution is given by
the two equations:
Moulding

x1 + 5x2 = 4 000

Soldering

x1 + x2 = 1200

x1 = 500

(2.4)

x2 = 700

Optimal total profit is calculated from the objective function:

Z  300 500  500 700  $500 000
At this point we realise that the optimal solution is dependent both on the feasible region and the objective function. If the slope of the objective function line
changes, we may get a new optimal solution. In our example the slope is 3/5:
3
Z
Z = 300 x1 + 500 x2 x2 = x1 +
5
500

(2.5)

If profit changes to $500 per unit for product 1 and to $200 per unit for product
2, the objective function line changes to:
5
Z
Z = 500 x1 + 200 x2 x2 = x1 +
2
200

(2.6)

Chapter 2 Linear programming

With this slope the optimal solution will be x1  1 000 and x2  0, as indicated by
the dotted line in Figure 2.3.
When a computer solves a linear programming problem, it starts somewhere
in the feasible region and searches for the optimal solution. For the straightforward examples in this book, such searches will end up in one of the corner
points of the feasible region. The particular corner chosen depends on whether
the objective function should be maximised or minimised. We can then solve
the problem by calculating Z for the corner points of the feasible region (Figure
2.4). The result will still be corner point 2 with Z  $500 000.
Z1 = $300 0 + $500 800 = $400 000
Z2 = $300 500 + $500 700 = $500 000
Z3 = $300 800 + $500 400 = $440 000
Z4 = $300 1000 + $500 0 = $300 000
Z5 = $300 0 + $500 0 = $0
x2
1 200
1 000
800

600

400
200

4
0
40
0
60
0
80
0
1
00
0
1
20
0

20

x1

Figure 2.4 Corners of the feasible region

2.2

Irregular problems

Linear programming problems can in some cases show discrepancies. Lets take
a look at some of them.

Multiple optimal solutions

In Figure 2.3 we saw that the optimal solution was determined by the slope of the
objective function line. If this slope is identical to the slope of a constraint line,
an interesting situation occurs. Lets assume that profit per unit is $500 for both
products. The objective function line can then be written:
Z = 500 x1 + 500 x2 x2 = x1 +

10

Z
500

(2.7)

Irregular problems

The slope is 1. Figure 2.5 shows that when we move the objective function line
outwards, the last contact between the feasible region and the objective function
line is the line between corner points 2 and 3. This makes sense since the slope
of the capacity line for the soldering department is also 1:
x1 + x2 = 1 200 x2 = x1 + 1 200

(2.8)

x2
1 200
1 000
800

Moulding
2
Soldering

600

400

Assembly

200

0
40
0
60
0
80
0
1
00
0
1
20
0

20

x1

Figure 2.5 Multiple optimal solutions

The conclusion must be that all combinations of x1 and x2 on the line between
corner points 2 and 3 are optimal solutions, and give the same maximum value
of Z. We come to the same conclusion when applying the method illustrated in
Figure 2.4. Corner points 2 and 3 give the same optimal solutions:
Z2  $500  500  $500  700  $600 000
Z3  $500  800  $500  400  $600 000

Redundancy
If you compare Figure 2.1 and Figure 2.2,, you will see that capacity in the inspection department is not a constraint in this problem. As a redundant constraint,
it has no influence on the feasible region and can not be part of an optimal solution. Regardless of the optimal solution, the inspection department will always
have some free capacity.

Infeasibility
Infeasibility occurs when no solution satisfies all of the models constraints. In
other words, no feasible region exists. We get such a situation if we add the constraint x2  1 000 to our Sygitron example. If we look at Figure 2.2, it is obvious
that not all the constraints can be satisfied at the same time.

11

Chapter 2 Linear programming

Unboundedness
Some problems might not have enough constraints to define one specific optimal solution. Assume the following objective function and constraints:
Z = 10 x1 + 10 x2

Maximise
Constraints:

5x1 + 2 x2 2 000

(2.9)

x1 + 2 x2 800
x1 , x2 0
Figure 2.6 illustrates that since the objective function should be maximised, and
the constraints are of the category , Z approaches infinity. This means that no
optimal solution exists for this problem. The solution is unbounded.
x2
1 200
1 000

800

=
10
+
x1

600

10

400

x2

200

0
40
0
60
0
80
0
1
00
0
1
20
0

20

x1

Figure 2.6 Unbounded problem

2.3

Computer solutions

Linear programming problems should generally be solved by a computer (Section

2.1 is included solely for pedagogic reasons). Many software manufacturers offer
linear programming packages, for instance AIMMS, AMPL, GAMS, LINDO, XA
and XPRESS. This book demonstrates examples in Excel only.
Computer software solves problems in mathematical programming by applying different algorithms. For a simple linear programming problem, like the
example in Section 2.1, a computer would use the simplex method. The various
algorithms for mathematical programming problem solving will not be discussed
in this book.
The example in Section 2.1 could be solved by using a graphical method, since
it involved only two decision variables. Imagine a problem with five decision
variables. It would be impossible to solve such a problem graphically since it
would involve drawing a figure in five dimensions! The only practical alternative
is to use a computer.

12

Computer solutions

Let us re-examine the simple example earlier in the chapter and study an
Excel solution. The mathematical model and the Excel spreadsheet are shown
in Figure 2.7. The cells B5 and C5 are reserved for the values of x1 and x2. In
cells B6 and C6 we write the parameters for the objective function (profit per
unit). Cell D6 contains a formula for the objective function, B6*B5 C6*C5.
Linear programming models usually include more than two decision variables.
To avoid unreasonably long formulas, we use the Excel standard function
SUMPRODUCT.

Maximise

Z = 300 x1 + 500 x2

Constraints:
x1 + 5x2 4 000
x1 + x2 1 200
2 x1 + x2 2 000
2 x1 + 5x2 5000
x1 , x2 0

Figure 2.7 Excel spreadsheet for a linear programming model

Our intention is to tell Excel to maximise the value in cell D6 by changing

the values in cells B5 and C5. Before this can be done, however, the constraints
must be included. For the moulding department constraint, we write the parameters for x1 and x2 in cells B9 and C9 respectively. The formula SUMPRODUCT
(B9:C9;$B$5:$C$5) is then written in cell D9. In cell F9 we write 4 000 which is

13

Chapter 2 Linear programming

the right side of the constraint. Constraints for the other three departments are
included in a similar manner. (We use the $-sign in this manner in order to copy
the formula correctly to the cells D10D12.) We are ready to solve the problem.
If you use an old version of Excel, bring down the Tools window from
the toolbar and select Solver. In Excel 2007, choose the Data-flag and select
Solver. The Solver dialogue box will now appear as shown in Figure 2.8. Cell D6,
containing the formula for the objective function, should be defined as the target
cell. Then click Max to indicate that the value of the objective function should
be maximised. You want Excel to do this by changing cells B5:C5. Insert those
references as shown in the figure.

Figure 2.8 Solver Parameters dialogue box

To include the constraints click Add. A new dialogue box for adding constraints appears as shown in Figure 2.9. Insert the cell reference for the left side
of the constraint under Cell Reference, and the cell reference for the right side
of the constraint under Constraint. This can be done one constraint at a time.
In this case, where all constraints are of the same type , all cell references can

Figure 2.9 Add Constraint dialogue box

14

Computer solutions

be put in simultaneously as shown in the figure. Go back to the Solver Parameter

dialogue box by clicking OK.
Before solving the problem we must activate the options dialogue box by clicking Options. An options dialogue box like that in Figure 2.10 appears. Click
Assume Linear Model and Assume Non-Negative. The second action is made
to add the two constraints x1, x2  0. (These constraints can also be added in the
constraint adding dialogue box.) Click OK.

Figure 2.10 Solver Options dialogue box

Solver now has all the necessary information to solve the problem. Click
Solve in the Solver Parameter dialogue box. The Solver Results dialogue box
appears, as shown in Figure 2.11. In this dialogue box you can click and request
three different reports. The sensitivity report is the most essential, and will be
discussed further in Section 2.6. Click OK to activate.

Figure 2.11 Solver Results dialogue box

15

Chapter 2 Linear programming

The solution of the problem results in the return of the value 500 in cell B5
and of 700 in cell C5 (see Figure 2.7). This is consistent with the result from
Section 2.1.

2.4

Graphical solution of a minimisation problem

For some problems the aim is to minimise the value of the objective function.
One example is minimisation of total costs. Lets consider the following problem:
Z = 2 x1 + x2

Minimise
Constraints:
A

x1 + x2 6

x1 + 4 x2 12

x1 + 2 x2 10

(2.10)

x1 , x2 0
The constraints are of the two categories  and . This results in the feasible
region shown in Figure 2.12.

x2
8

6
4
2
0

Feasible region

C
B
0

10 12 x1

Figure 2.12 Feasible region

In a minimisation problem the objective function lines are displaced parallel
to each other at lower levels as Z is minimised. Figure 2.13 shows that as the
objective function line is moved inwards, the last contact with the feasible region
is corner point 1. The optimal solution is given by the intersection between the
constraint lines A and C:
A

x1 + x2 = 6

x1 + 2 x2 = 10

x1 = 2
x2 = 4

(2.11)

The problem can also be solved by calculating Z for the three corner points of
the feasible region. Corner point 1 represents the minimum of the objective
function:

16

Slack variables

Z1  2  2  4  8
Z2  2  4  2  10
Z3  2  8  1  17
x2

16

2
0

12

z=

z=

z=

2
0

x1

Figure 2.13 Optimal solution for a minimisation problem

2.5

Slack variables

The graphical solution in Section 2.1 showed that the optimal solution, x1  500
and x2  700, was given by the capacities in the moulding and soldering departments (see Figure 2.3). These constraints are then said to be binding since their
capacities are fully utilised. The rest of the constraints are not binding, which
means they have unused capacity. Capacity left over in the four departments can
be calculated as the difference between available and used capacity:
Moulding
Soldering
Assembly
Inspection

4 000 ( 500 + 5 700 ) = 0

1 200 ( 500 + 700 ) = 0

2 000 ( 2 500 + 700 ) = 300

(2.12)

5000 ( 2 500 + 5 700 ) = 500

The unused capacity for a particular constraint is often referred to as its slack.
The slack of the four constraints in our example can also be read from the answer
report shown in Figure 2.14.

Figure 2.14 Answer report

17

Chapter 2 Linear programming

The unused capacity in a constraint is often referred to as a slack variable.

When all the slack variables are symbolised with Si, the mathematical model can
be expressed in standard form:
Maximise

300 x1 + 500 x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4

Constraints:
Moulding

x1 + 5x2 + S1 = 4 000

Soldering

x1 + x2 + S2 = 1 200

Assembly

2 x1 + x2 + S3 = 2 000

Inspection

2 x1 + 5x2 + S4 = 5000

(2.13)

x1 , x2 , S1 , S2 , S3 , S4 0
In the objective function all slack variables are given zero as coefficients, since
unused capacity makes no contribution to profit.
In the minimisation problem of Section 2.4 the optimal solution was given by
constraints A and C (equation 2.10). Constraint B was of the  type, a condition
that was more than fulfilled. Such constraints are termed surplus variables and
are defined as the excess above the minimum requirement. At the optimal solution the left side of the constraint is x1  4x2  2  4  4  18, which is 6 more than
the constraint of 12. The value of the surplus variable is then 6. Surplus variables
and slack variables must have opposite signs. The minimisation example (equation 2.10) on a standard form will be:
Minimise

2 x1 + x2 + 0 S1 + 0 S2 + 0 S3

Constraints:
A

x1 + x2 S1 = 6

x1 + 4 x2 S2 = 12

x1 + 2 x2 + S3 = 10

(2.14)

x1 , x2 , S1 , S2 ,S3 0

2.6

Sensitivity analysis

Sensitivity analysis is the study of how changes in model parameters affect the
optimal solution. In Excel this information is provided in the sensitivity report.
Lets take a closer look at some of the effects of various parameter changes.

Objective function coefficient ranges

For our example, we saw in Figure 2.3 that the optimal solution was given by the
slope of the objective function line. With the given slope:

18

Sensitivity analysis

3
Z
Z = 300 x1 + 500 x2 x2 = x1 +
5
500

(2.15)

the solution was determined by the intersection between the two capacity lines
for the moulding and soldering departments:
1
x1 + 5x2 = 4 000 x2 = x1 + 800
5
x1 + x2 = 1 200 x2 = x1 + 1 200

(2.16)

As long as the slope for the objective function line lies between the slopes for
these two capacity lines, the optimal solution will not change (see Figure 2.15).
Assume that the slope of the objective function line is given by the following
coefficients and that the objective function line can be formulated as:
Z = Cx1 x1 + Cx2 x2 x2 =

Cx1
Cx2

x1 +

Z
500

(2.17)

x2
1 200
1 000
800

Mould

ing

ld

So

600

er
g

in

400
200

Feasible region
0

x1

20

00

80

60

40

20

Figure 2.15 Ranges for one objective function coefficient

If we insist that the slope for the objective function line lies between the slopes
for the two capacity lines, the following requirement must be fulfilled:
1

Cx1
Cx2

1
1 Cx1

1
5
5 Cx2

(2.18)

If one coefficient is held constant, lets say Cx  500, the expression can be written:
2

1 Cx1

1 100 Cx1 500
5 500

(2.19)

This means that in the objective function Z  Cx x1  500 x2, the value Cx must
1
1
be kept between 100 and 500 to keep the optimal solution in corner point 2
(Figure 2.15). If Cx moves outside these limits, a new optimal solution will occur.
1

19

Chapter 2 Linear programming

If Cx 100, the optimal solution changes to corner point 1 with x1  0 and x2 

1
800. If Cx  500, the optimal solution changes to corner point 3 with x1  800
1
and x2  400.
If we go through the same procedure for Cx , we find the following limits:
2

300 Cx 1 500
2

In Excel, the sensitivity report tells how much the objective function coefficients
can change without affecting the optimal solution. As shown in Figure 2.16, the
limits for the coefficients are presented as objective coefficients with allowable
increases and decreases. The limits for Cx can be calculated as 500  200  300
2
and 500  1 000  1 500.

Figure 2.16 Sensitivity report

Reduced costs
The sensitivity report in Figure 2.16
.16
16 also includes reduced costs for the two objective function coefficients. A reduced cost tells us how much an objective function
coefficient must be improved before the corresponding decision variable gets a
value different from zero. In our example, x1 and x2 have values different from
zero, and both reduced costs are 0.
If we change the objective function in our example to:
Z  80x1  500x2
then the optimal solution will be x1  0 and x2  800. (Try this yourself.) The
sensitivity analysis will then show a reduced cost  20 for the objective coefficient of x1. The objective coefficient in this example is profit and is shown as a
negative value when presented as a cost. Profit per unit must be increased by $20
for product 1 to make it profitable.

20

Sensitivity analysis

Shadow prices
From Figures 2.12.3,
2.3,
2.3,
.3,
3,, it is obvious that capacity changes in the moulding or soldering department will result in new optimal solutions. We understand that any
increased capacity in one of these departments will increase maximum profit. Let
us assume that capacity in the soldering department is increased by 100 hours
per year to a total of 1 300 hours per year. The new capacity line for this department will be:
x1  x2  1 300
As indicated in Figure 2.17, the feasible region expands. As the objective function
line is moved outwards, a new optimal solution is defined by the two capacity
lines for the moulding and soldering departments:
Moulding

x1 + 5x2 = 4 000

Soldering

x1 + x2 = 1300

x2

x1 = 625
x2 = 675

(2.20)

Objective function line

1 200

New capacity line for

soldering department

1 000
800

New optimal solution

600
400
200

x1

20

00

80

60

40

20

Figure 2.17 New optimal solution for Sygitron

Total profit will be:
Z  $300  625  $500  675  $525 000
This represents an increase of $25 000 compared to a total profit per year of
$500 000 using the old capacity in the soldering department. A capacity increase
of 100 hours per year in the soldering department results in a total profit increase
of $25 000. Profit increase per hour capacity increase is:
$25 000
 $250 hour 1
100 hours

(2.21)

Since one hour capacity increase results in $250 profit increase, we are willing
to pay up to $250 for one hour capacity increase in the soldering department.
The shadow price for the soldering department is then $250.

21

Chapter 2 Linear programming

The sensitivity report in Figure 2.16

.16
16 indicates that shadow prices for the assembly and inspection departments are 0. This is obvious, since these constraints are
not binding, and the departments have unused capacity. Increased capacity has
no value for these departments.
Excel defines a shadow price as the amount by which the objective function
value changes when the corresponding constraints right side increases by one
unit. For the minimisation problem in Section 2.4 shadow prices for the two
binding constraints x1  x2  6 and x1  2x2 10 will be 3 and 1, respectively, in
the Excel sensitivity report. If the right side of the  constraint is increased from
6 to 7, Z moves in the same direction, and increases from 8 to 11. If the right side
of the constraint is increased from 10 to 11, Z moves in the opposite direction,
and is reduced from 8 to 7.
Other software may use other conventions for the signs of shadow prices.
Irrespective of software, the following definition should always lead to a proper
interpretation. The absolute value of a shadow price indicates the amount by
which the objective function will be improved when the corresponding constraint is lessened by one unit. A  constraint is lessened by decreasing its right
side, and a constraint is lessened by increasing its right side.

Constraint quantity value ranges

As capacity in the soldering department is increased, the capacity line is displaced outwards and new optimal solutions occur (Figure 2.17). If this capacity
is increased sufficiently, the soldering department will get free capacity (and
shadow price  0). As illustrated in Figure 2.18, this constraint will no longer be
binding and the optimal solution will be given by the intersection of the capacity
lines for the moulding and assembly departments. Another aspect of the sensitivity analysis is to show precisely how much these constraints can change before
these new situations arise.
The sensitivity report in Figure 2.16 indicates the range for each constraint,
telling how much the constraint can be changed in both directions before its

x2

Objective function line

1 200

Soldering

1 000
800
600

mb
ly

200

ing
e
Ass

400

Mould

0
20
0
40
0
60
0
80
0
1
00
0
1
20
0

x1

Figure 2.18 New optimal solution for Sygitron

22

Duality

shadow price changes. This is presented as Constraint R.H. Side with Allowable
Increase and Allowable Decrease. For the soldering department the range is
defined by the two values:
1 200  400  800

1 200  133  1 333

The two corner points defined by these two limits are illustrated in Figure 2.19.
x2

Objective function line

1 200

Soldering

1 000
800

Mould

ing

600

bly

em

200

Ass

400

0
20
0
40
0
60
0
80
0
1
00
0
1
20
0

x1

Figure 2.19 Constraint quantity value ranges for the soldering department
In the original optimal solution (Figure 2.3) the assembly department is not
binding. It does not define the optimal solution and has a shadow price  0.
The sensitivity report in Figure 2.16 indicates that the range of this constraint is
between 1 700 hours and infinity. This is obvious. An increase in capacity will
never alter the situation because the assembly department is not binding in the
first place. On the other hand, if capacity is reduced to 1 700 hours, the constraint will become binding.

Other forms of sensitivity analysis

Other changes in a model that affect the value of the objective function must
be investigated manually in Excel. These include changes of parameter values on
the left side of a constraint, additional constraints, additional decision variables,
etc. To study these effects, you need to solve the problem again after introducing
any changes.

2.7

Duality

Every linear programming problem, called a primal problem, can be converted

into a dual problem. Lets return to the Sygitron example and denote this as the
primal problem:

23

Chapter 2 Linear programming

Maximise

Z = 300 x1 + 500 x2

Constraints:
Moulding

x1 + 5x2 4 000

Soldering

x1 + x2 1200

Assembly

2 x1 + x2 2 000

Inspection

2 x1 + 5x2 5000

(2.22)

x1 , x2 0
This primal problem can be converted into a dual problem. The dual problem
appears when we rotate the primal problem a half turn around a diagonal and
imaginary axis going upwards to the right. The decision variables in the dual
problem are designated by u1, ..., u4.
Minimise

Z = 4 000u1 + 1 200u2 + 2 000u3 + 5000u4

Constraintss:
Product 1

u1 + u2 + 2u3 + 2u4 300

Product 2

5u1 + u2 + u3 + 5u4 500

(2.23)

u1 , u2 , u3 , u4 0
We notice that the values on the right side of the constraints in the primal
problem 2.22, turn into parameters in the objective function in the dual problem
2.23. The parameters 1, 1, 2 and 2 before x1 at the left side of the constraints in
the primal problem, turns into the left-side parameters for the first constraint in
the dual problem. The second constraint in the dual problem is formulated in a
similar manner from the parameters before x2 at the left side of the constraints
in the primal problem.
Since 2.23 is the dual problem of 2.22, then 2.22 is the dual problem of 2.23.
The number of decision variables in the dual problem is always equal to the
number of constraints in the primal problem, and vice versa. If the primal is a
maximisation problem, the dual will be a minimisation problem, and vice versa.
The primal problem 2.22 is a maximisation problem with constraints of the
type and decision variables that are equal to or greater than zero. Such a
problem is said to be in canonical form (standard form). The corresponding dual
problem 2.23 is also in canonical form, which results in constraints of the type
. We will not explain why this is so, but rather refer to more comprehensive
textbooks such as Dantzig and Thapa.
If the primal problem has a bounded solution, the dual problem will have a
corresponding solution. The value of the objective functions will be the same for
the solutions of the primal and the dual problem. For these solutions, the values
of the decision variables in the dual problem equals the shadow prices in the
primal problem, and vice versa. This means that finding the optimal solution of
the dual problem is the same as finding the optimal use of available resources. In

24

Duality

optimal solutions, slack in constraints in the dual problem equals reduced costs
in the decision variables of the primal problem, and vice versa.
Sensitivity reports for the primal problem 2.22 and the dual problem 2.23 are
given in Figure 2.16 and Figure 2.20 respectively. The two reports are summarised
in Table 2.2. In optimal solutions, the decision variables in the dual problem
have the same values as the shadow prices in the primal problem, and vice versa.
In Figure 2.20, the slack for a constraint is calculated as Constraint R.H. Side
minus Final Value. Table 2.2 also shows that slack for constraints in the primal
problem equals reduced costs in the dual problem, and vice versa.

Figure 2.20 Sensitivity report for the Sygitron dual problem

Table 2.2 Results for the primal and dual problem of the Sygitron example
Primal problem

Dual problem

Solutions

x1  500, x2  700

u1  50, u2  250,
u3  0, u4  0

Shadow prices

Moulding  50, Soldering  250,

Assembly  0, Inspection  0

Product 1  500, product 2  700

Slack

Moulding  0, Soldering  0,
Assembly  300, Inspection  500

Product 1  0, product 2  0

Reduced costs

For x1  0, for x2  0

For u1  0, for u2  0,
for u3  300, for u4  500

The solution of the primal problem can also be found from the solution and
the sensitivity analysis of the dual problem. For the Sygitron example, we see
in Figure 2.20 that for the dual problem, only u1 and u2 have values different
from zero. This means that the only constraints with shadow prices different

25

Chapter 2 Linear programming

from zero, is moulding and soldering. These two constraints define the optimal
solution:
Moulding

x1 + 5x2 = 4 000

Soldering

x1 + x2 = 1200

x1 = 500
x2 = 700

(2.24)

The same values can also be found directly from the shadow prices for the two
constraints in the dual problem.

The dual problem minimises alternative cost

The values of the decision variables in an optimal solution for a dual problem
will always be equal to the shadow prices for the primal problem. In the optimal
solution for the Sygitron example, a shadow price equals the reduction of total
profit per year when capacity is reduced by one hour per year in a department.
If capacity in the soldering department is reduced by one hour, total profit is
reduced by $250. In the moulding department, one hour reduced capacity results
in $50 of reduced profit. In the assembly department one hour reduced capacity doesnt influence profit, since the shadow price is 0. A shadow price can be
interpreted as the alternative cost of using one hour of capacity, i.e. the cost of
using a limited resource. Minimising the objective function in a dual problem
means minimising the total alternative cost of using the limited resources. Thus
the available resources are used in an optimal way.
The primal problem 2.22 tells us that product 1 contributes with a profit of
$300 per unit. In the dual problem 2.23, this value appears as the right side of the
first constraint. The parameters before u1, ..., u4 on the left side of the same constraint, are the same as the parameters before x1 in the constraints for the primal
problem. Then the left side of the first constraint in the dual problem represents
the value of using the resources to produce something other than product 1. In
this case the only alternative is product 2. If the value of this left side exceeds
the right side in the optimal solution, the resources should not be applied for
producing product 1, since alternative applications result in higher profit. Such
an incident, with left side  right side for the first constraint in the dual problem,
means slack for the constraint. This slack represents reduced cost for product 1.
In the Sygitron example, the left side equals the right side in the constraint. Then
the resources are used in an optimal way, reduced cost equals 0, and product 1
should be produced.
Lets illustrate the same points again by changing the Sygitron example so that
product 1 contributes only $80 per unit. The constraints are unchanged, but the
objective function changes to:
Maximise

Z  80x1  500x2

The optimal solution of this primal problem is x1  0 and x2  800, illustrated by

point B in Figure 2.21. The sensitivity analysis in Excel shows that reduced costs
for x1 and x2 are 20 and 0 respectively.

26

Conclusions
x2
1 200
1 000
800
600

B Moulding
A
Soldering

400
200

Assembly
0
20
0
40
0
60
0
80
0
1
00
0
1
20
0

x1

Figure 2.21 Feasible region for the Sygitron example

The corresponding solution of the dual problem is u1  100 and u2  u3  u4 

0. In this optimal solution, the two constraints in the dual problem show that:
Product 1

u1 + u2 + 2u3 + 2u4 80

100 80

Product 2

5u1 + u2 + u3 + 5u4 500 500 500

(2.25)

The first constraint has a slack  100  80  20, equal to minus reduced cost for x1.
Lets take a closer look at this point by studying alternative cost. If a product is
produced, it is required that revenues  costs when we use the resources on this
product instead of the alternatives. The optimal solution of the primal problem
is point B in Figure 2.21 with x1  0 and x2  800. Here, only the capacity of the
moulding department is fully utilised, with a shadow price of $100 per hour. The
cost of using the moulding department time resources for producing one unit of
product 1, is the time consumed by one unit multiplied by the shadow price: 1
hour  $100 hour1  $100. This is more than the profit of $80 per unit. Then the
resources should not be used for producing product 1. We see that profit per unit
of product 1 must increase by $20 before product 1 should be set into production. This makes perfect sense since the shadow price of product 1 is $20 in this
optimal solution.

Conclusions

A problem where all decision variables are linearly related can be solved using
linear programming.

A linear programming model with two decision variables can be solved graphically.

Excels Solver is an appropriate tool to solve small linear programming models.

In addition to an optimal solution, Solver can produce a sensitivity report with

valuable information about a linear programming model.

The dual problem in linear programming gives a deeper understanding of the

primal problem.

27

Chapter 2 Linear programming

Problems
2.1 A manufacturer produces product 1 and 2 giving a profit per unit of $80 and $60
respectively. Both products are processed by the two machines A and B. Each machine
has a capacity of 1 200 hours per year. Each unit of product 1 needs 1 hour at machine
A and 3 hours at machine B. Each unit of product 2 needs 2 hours at machine A and
1 hour at machine B.
(a) How many units should the manufacturer produce of product 1 and 2 per year?
Solve the problem using both the graphical method and Excel.
(b) What is the value of increasing the capacity for machine B with one extra hour
per year?
(c) Assume now that the production of each unit of product 2 consumes 3 lbs of
a special alloy, and that supply of this alloy is limited to 600 lbs per year. How
many units should the manufacturer produce of product 1 and 2 per year?
(d) Assume that profit of product 2 is reduced by $40 per unit. How many units
should the manufacturer produce of product 1 and 2 per year?
(e) The answer in (d) should be 0 units of product 2. How much must the profit
per unit of product 2 increase (from $20) to make it profitable to produce this
product?
2.2 Consider the following linear programming model:
Maximise Z  20x1  15x2
Constraints:
A

3x1  4x2 1 200

x1  5x2 1 100

3x1  x2 900
x1, x2  0

(a) Solve the problem graphically.

(b) Find the shadow price for constraint A.
(c) By how much must the parameter before x2 in the objective function increase to
give a new optimal solution? (Note: the parameter 20 before x1 is constant.)
2.3 Consider the following linear programming model:
Maximise Z  5x1  7x2
Constraints:
A

2x1  3x2  6

x1  6x2  4

3x1  4x2  6

3x1  2x2 30
x1, x2  0

28

Problems

(a) Solve the problem graphically.

(b) How much can the parameter 7 before x2 in the objective function be reduced
without changing the optimal solution?
(c) Find the shadow price for constraint A.
(d) Find the shadow price for constraint D.
2.4 A company manufactures products X, Y and Z, and all of them are processed on
machines A, B and C. Profit per unit (in $), time consumption (in hours) for different
products on different machines and machine capacities are given below.

Capacity (hours)

Machine A

12 000

Machine B

12 000
12 000

Machine C
Profit per unit (in $)

10

10

10

The company wants to maximise profit. Solve the problem without using a computer.
2.5 A food supplement is made by mixing two ingredients called 1 and 2. One batch
of the supplement should contain a minimum amount of vitamin A, B, C and D
according to the table below. Amounts of vitamins in the two ingredients are also
given. All amounts are in milligrams:
A

Required amount in one batch of

supplement

0.14

18.0

500

0.30

Amount in one kg of ingredient 1

0.70

0.0

50

0.08

Amount in one kg of ingredient 2

0.00

6.0

100

0.02

The cost of ingredient 1 is twice the cost of ingredient 2. How many kilograms of the
two ingredients should be mixed together in each batch to obtain minimum cost?
There are 1 000 milligrams in one gram, and 1 000 grams in one kilogram.
2.6 An investor wants to invest $15 000 000 in a portfolio that may include bonds,
certificates, treasury bills and stocks. The expected annual returns are given in the
table below. The investor also wants to diversify the investments, and has decided
maximum amounts for each security.

29

Chapter 2 Linear programming

Expected annual
return
Bonds
Certificates

Maximum
amount

5%

$3 000 000

8%

$7 000 000

Treasury bills

13%

$6 000 000

Stocks

16%

$5 000 000

In addition, the investor has decided that at least 60% of the investments should be
in treasury bills and stocks, and at least 10% in bonds. He has also decided that the
sum invested in bonds and certificates must exceed the amount invested in treasury
bills. The investor wants a maximum return on his investments. Find the optimal
composition of the portfolio.
2.7 A bank may employ people on a full-time or part-time basis. The opening hours
are from 09:00 to 19:00. After some research the bank has found the following need
for employees during the day:
Time period

Number of employees

09:0010:00

10:0011:00

11:0012:00

12:0013:00

10

13:0014:00

11

14:0015:00

15:0016:00

16:0017:00

17:0018:00

18:0019:00

The employees may start their working day at 09:00, 10:00, etc., but they must finish
by 19:00. Full-time employees work 4 hours, have 1 hour lunch, and work 3 hours.
They do not get paid for the lunch hour. Part-time employees work 4 hours continuously. A full-time employee gets paid
18 per hour, and a part-time employee
17 per
hour. The bank wants to minimise total cost, and needs to find out how many fulltime and part-time employees they should hire. They also want to know how many
of them should start at 09:00, at 10:00, etc. Solve the problem using an LP model.
2.8 We want to carry out a survey and interview at least 5 000 respondents. In addition, the following requirements must also be met:
At least 2 000 respondents must 30 years old or younger.
At least 1 200 respondents must be between 31 and 50 years old.

30

Problems

At least 12% of the respondents must live in Norwich.

Less than 20% of the respondents who are above 51 years old, must live in Norwich.
Costs associated with interviewing respondents of different ages in Norwich and
outside is (in ):

Age 30 years

31 years Age
50 years

Age  51 years

Living in Norwich

1.53

1.38

1.12

Living outside Norwich

1.40

1.47

1.29

The survey should be completed at minimum cost. Solve the problem using Excel.
2.9 Bestvold Ltd manufactures small electrical motorbikes for children. Each bike
is assembled from one motor, two wheels, one frame and one battery. The batteries
are bought from an external supplier. The other components can either be bought
externally or produced by the company itself. For the next year Bestvold Ltd plans to
produce 10 000 bikes.
Components produced by the company itself will be processed in departments A, B
and C. Time consumption (in minutes) for the various components in the different
departments and machine capacities per year (in hours) are given below.
Time consumption (in minutes)

One motor

7.8

5.3

8.1

One wheel

3.8

4.9

7.6

One frame

2.0

4.2

1 200

1 300

2 200

Capacity per year (in hours)

Costs per unit (in $) when buying or producing are:

Buy

Produce

One motor

15.5

7.35

One wheel

9.8

2.2

One frame

5.7

1.15

(a) The company wants to minimise costs. Solve the problem and find the optimal
number of motors, wheels and frames that should be bought and that should be
produced by the company itself.

31

Chapter 2 Linear programming

(b) Find the time consumption per year in department A, B and C, respectively.
(c) What is the maximum price the company should pay for one hour increased
capacity in department C?
(d) What is the maximum price the company should pay for one hour increased
capacity in department B?
2.10 ProCruiser Inc. is planning next years production of their LuxCruiser. At the
beginning of the first quarter they have an inventory of 70 boats. Expected sales and
production capacities are as indicated below.

Expected sales
(number)

Capacity
(number)

1st quarter

1 200

2 200

2nd quarter

2 000

1 600

3rd quarter

1 600

1 200

4th quarter

800

2 100

Production costs are expected to be $80 000 per boat for the 1st quarter, and will
increase with 10% every quarter. Inventory costs are estimated to be $2 000 per boat
for the 1st and 2nd quarter, and $2 400 per boat for the 3rd and 4th quarter respectively. (Relate these costs to the inventory at the end of each quarter.) ProCruiser has
decided to have an inventory of at least 300 boats at the end of quarter 4. Find an
optimal production plan for quarters 1 to 4.
The sensitivity report gives the following information about the capacity constraint
limiting production to 1 200 boats for the 3rd quarter:

Explain these values.

32

Final
value

Shadow
price

Constraints
r.h. side

Allowable
increase

Allowable
decrease

1 200

7 280

1 200

830

270

Problems

2.11 Which of the following problems can be solved?

(a)

Maximise

Z = x1 + 2x2

Constraints:
A

3x1 + x2 30

x1 2x2 20

x1 + x2 20
x1 , x2 0

(b)

Maximise

Z = x1 + x2

Constraints:
A

x1 100

x1 300

x2 300

x1 + 2 x2 400
x1 , x2 0

(c)

Maximise

Z = 4 x1 + x2

Constraints:
A

3x1 + 2 x2 6

x1 + x2 4

3x1 x2 8

x1 x2 0
x1 , x2 0

(d)

Maximise

Z = 6 x1 + 2 x2

Constraints:
2 x1 + 3x2 120
x1 , x2 0

2.12 Examine (a)(d) in problem 2.11. If dual problems can be solved, formulate the
dual problems. Find the optimal solutions, and verify that these solutions correspond
to the shadow prices for the primal problem.

33

Chapter 2 Linear programming

Further reading
Bazaraa, M. S., Jarvis, J. J. and Sherali, H. D., Linear Programming and Network Flows,
Wiley, 2009.
Dantzig, G. B. and Thapa, M. N., Linear Programming; 1: Introduction, Springer, 1997.
Dantzig, G. B. and Thapa, M. N., Linear Programming; 2: Theory and Extensions,
Springer, 2003.
Vaserstein, L. N., Introduction to Linear Programming, Prentice Hall, 2003.

34