Chapter22 PDF
Chapter22 PDF
Chapter22 PDF
QXD
7/22/10
10:10 PM
Page 22.1
CHAPTER 22
Additional Network
and LP Algorithms
22.1
The new model determines the flows that minimize the total cost while satisfying
the flow restrictions on the arcs and the supply and demand amounts at the nodes.We first
present the capacitated network flow model and its equivalent linear programming formulation. The linear programming formulation is then used as the basis for the development of a special capacitated simplex algorithm for solving the network flow model.
22.1.1 Network Representation
Consider a capacitated network G = (N, A), where N is the set of nodes and A is the
set of arcs and define
xij = amount of flow from node i to node j
uij(lij) = upper (lower) capacity of arc (i, j)
cij = unit flow cost from node i to node j
fi = net flow at node i
Figure 22.1 depicts these definitions on arc (i, j,). The label [fi] assumes a positive
(negative) value when a net supply (demand) is associated with node i.
22.1
M22_TAHA5937_09_SE_C22.QXD
22.2
Chapter 22
7/22/10
10:10 PM
Page 22.2
(lij, uij)
xij
[100]
[200]
[50]
$2
$1
$4
(70, 120)
$5
FIGURE 22.2
[150]
$1
(50, 80)
$3
[ fj]
$ cij
$6
[120]
$4
$2
(100, 120)
5
[80]
Example 22.1-1
GrainCo supplies corn from three silos to three poultry farms. The supply amounts at the three
silos are 100, 200, and 50 thousand bushels and the demands at the three farms are 150, 80, and
120 thousand bushels. GrainCo mostly uses railroads to transport the corn to the farms, with the
exception of three routes where trucks are used.
Figure 22.2 shows the available route between the silos and the farms. The silos are represented by nodes 1, 2, and 3 whose supply amounts are [100], [200], and [50], respectively.The farms
are represented by nodes 4, 5, and 6 whose demand amounts are [ -150], [ -80], and [ -120],
respectively. The routes allow transshipping between the silos. Arcs (1, 4), (3, 4), and (4, 6) are
truck routes. These routes have minimum and maximum capacities. For example, the capacity of
route (1, 4) is between 50 and 80 thousand bushels. All other routes use trainloads, whose
maximum capacity is practically unlimited. The transportation costs per bushel are indicated on
the respective arcs.
Period
Units of demand
Unit production
cost ($)
Unit holding
cost ($)
1
2
3
4
100
110
95
125
24
26
21
24
1
2
1
2
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.3
22.1
22.3
2. In Problem 1, suppose that back-ordering is allowed at a penalty of $1.50 per unit per
period. Formulate the problem as a network model.
3. In Problem 1, suppose that the production capacities of periods 1 to 4 are 110, 95, 125,
and 100 units, respectively, in which case the given demand cannot be satisfied without
back-ordering. Assuming that the penalty cost for back-ordering is $1.5 per unit per
period, formulate the problem as a network model.
4. Daw Chemical owns two plants that manufacture a basic chemical compound for two
customers at the rate of 660 and 800 tons per month. The monthly production capacity
of plant 1 is between 400 and 800 tons and that of plant 2 is between 450 and 900 tons.
The production costs per ton in plants 1 and 2 are $25 and $28, respectively. Raw
material for the plants is provided by two suppliers, who are contracted to ship at least
500 and 700 tons per month for plants 1 and 2 at the costs of $200 and $210 per ton,
respectively. Daw Chemical also pays for the transportation cost of both the raw
material and the final compound. The costs per ton of transporting the raw material
from supplier 1 to plants 1 and 2 are $10 and $12, respectively. Similar costs from
supplier 2 are $9 and $13, respectively. The transportation costs per ton from plant 1 to
clients 1 and 2 are $3 and $4, and from plant 2 are $5 and $2, respectively. Assuming
that 1 ton of raw material produces 1 ton of the final compound, formulate the
problem as a network model.
5. Two nonintegrated public schools are required to change the racial balance of their
enrollments by accepting minority students. Minority enrollment must be between 30%
and 40% in both schools. Nonminority students live in two communities, and minority
students live in three other communities. Traveled distances, in miles, from the five
communities to the two schools are summarized in the following table:
Maximum
enrollment
1500
1
2
2000
Student population
Nonminority areas
20
15
500
12
18
450
10
8
300
4
6
1000
5
5
1000
Month
Purchasing cost
per ton ($)
Selling price
per ton ($)
1
2
3
200
190
195
250
230
240
M22_TAHA5937_09_SE_C22.QXD
22.4
Chapter 22
7/22/10
10:10 PM
Page 22.4
The maximum capacity of the silo is 800 tons. The owner has $100, 000 cash on hand
which can be used to purchase new crops. Also, initially, at the start of month 1, the silo
is half full. It is estimated that the storage cost per ton per month is $10. Surplus cash
earns 1% interest monthly. The objective is to determine the buy/sell policy the owner
must follow to maximize the total cash accumulation at the end of the three-month
season.
Formulate the problem as a network model.
subject to
k
(j, k)HA
i
(i, j)HA
[ fi]
i
$ cij
(lij, uij)
xij
[ fj]
[ fi lij]
$ cij
(uij lij)
xij
[fj lij]
j
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.5
22.1
22.5
The main constraints of the linear program relate the input and output flow for each node,
which yields the following LP:
x12
x13
x14
x23
x25
x34
x35
x46
x56
Minimize
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
1
-1
Lower bounds
Upper bounds
0
q
1
1
-1
-1
1
1
-1
-1
-1
0
q
50
80
0
q
0
q
1
1
-1
1
-1
0
q
100
120
-1
70
120
0
q
= 100
= 200
=
50
= -150
= -80
= -120
Note the arrangement of the constraints coefficients. The column associated with variable
xij has exactly one +1 in row i and one -1 in row j, a typical property of network models. The
rest of the coefficients are all 0. This structure is typical of network flow models.
The optimum solution is z = $1, 870, 000 with x13 = 20 (thousand bushels), x14 = 80 ,
x23 = 20, x25 = 180, x34 = 90, x46 = 20, and x56 = 100. All the remaining variables are zero.
The variables with lower bounds are substituted as
x14 = x14
+ 50
x34 = x34
+ 70
x56 = x56
+ 100
x13
x14
x23
x25
x34
x35
x46
x56
Minimize
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Upper bounds
1
-1
1
-1
-1
1
-1
-1
-1
q
30
1
1
-1
50
-1
q
1
-1
20
=
50
= 200
= -20
= -30
= -180
= -20
The corresponding network after substituting out the lower bounds is shown in
Figure 22.4. Note that the lower-bound substitution can be done directly from Figure 22.2
using the substitution in Figure 22.3 and without the need to express the problem as a linear
program first.
The optimum solution is z = $1, 350 thousand (or z = 1350 + 50 * 1 + 70 * 1 + 100 *
x25 = 180 , x34 = 20 (or x34 = 20 + 70 = 90 ), x46 = 20 , x56 = 0 (or x56 = 0 + 100 = 100 ),
which, of course, is the same solution given by the before-substitution solution.
M22_TAHA5937_09_SE_C22.QXD
22.6
Chapter 22
7/22/10
10:10 PM
Page 22.6
[50]
[30]
$1
(30)
$4
$3
$2
$1
[20]
(50)
$2
$5
FIGURE 22.4
[200]
Example 22.1-3
6
$4
(20)
$6
[20]
5
[180]
(Employment Scheduling)
This example illustrates a network model that initially does not satisfy the node flow requirement
(i.e., node output flow less node input flow equals node net flow), but that can be converted to this
form readily through special manipulation of the constraints of the linear program.
Tempo Employment Agency has a contract to provide workers over the next 4 months
(January to April) according to the following schedule:
Month
No. of workers
January
February
March
April
100
120
80
170
Because of change in demand, it may be economical to retain more workers than needed in
a given month. The cost of recruiting and maintaining a worker depends on the length of the
employment period, as the following table shows:
Employment period (months)
Cost per worker ($)
100
130
180
220
Let
xij = number of workers hired at the start of month i
and terminated at the start of month j
For example, x12 gives the number of workers hired in January for 1 month only. To formulate the
problem as a linear program for the 4-month period, we add May as a dummy month (month 5),
so that x45 defines hiring in April for April.
The constraints recognize that the demand for period k can be satisfied by all xij such that
i k 6 j. Letting si 0 be the surplus number of workers in month i, the linear program is given as
x12
x13
x14
x15
x23
x24
x25
x34
x35
x45
Minimize
100
130
180
220
100
130
180
100
130
100
January
February
March
April
1
1
1
1
1
1
1
1
1
1
1
1
1
1
s1
s2
s3
s4
-1
-1
1
1
1
-1
1
-1
=
=
=
=
100
120
80
170
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.7
22.1
22.7
The preceding LP does not have the ( -1, +1) special structure of the network flow model
(see Example 22.1-2). Nevertheless, the given linear program can be converted into an equivalent network flow model by using the following arithmetic manipulations:
1. In an n-equation linear program, create a new equation, n + 1, by multiplying equation
n by -1.
2. Leave Equation 1 unchanged.
3. For i = 2, 3, . . . , n, replace each equation i with (equation i) - (equation i - 1).
The application of these manipulations to the employment scheduling example yields the
following linear program, whose structure fits the network flow model:
x12
x13
x14
x15
x23
x24
x25
x34
x35
x45
Minimize
100
130
180
220
100
130
180
100
130
100
January
February
March
April
May
1
-1
1
1
-1
-1
-1
s2
-1
1
1
-1
-1
-1
s1
-1
1
-1
-1
1
-1
s3
s4
-1
1
-1
1
= 100
20
=
= -40
90
=
= -170
Using the preceding formulation, the employment scheduling model can be represented
equivalently by the minimum cost flow network shown in Figure 22.5. Actually, because the arcs
have no upper bounds, the problem can be solved also as a transshipment model (see Appendix
to this section).
The optimum solution is x15 = 100, x25 = 20, x45 = 50, and all the remaining variables are
zero. The following table summarizes the hiring and firing activities over the 4-month horizon.
The total cost is $30, 600.
Month
Number of workers
hired
Number of workers
fired
Net number
of workers
100
20
0
50
0
0
0
0
100
120
120
170
January
February
March
April
FIGURE 22.5
x13
x12
1
[100]
s1
2
[20]
s2
x23
x45
x34
3
s3
[40]
s4
[90]
5
[170]
x24
x25
M22_TAHA5937_09_SE_C22.QXD
Chapter 22
10:10 PM
Page 22.8
300
180
90
170
200
200
220
300
50
240
(b)
Month
Number of workers
[20]
3
$6 )
,
(0
(3 $5
0,
40
)
22.8
7/22/10
$4 (10, )
[50]
$1
(0, )
2
[40]
$3
(10, )
[30]
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.9
22.1
[100]
$1
)
(60
$4
(
)
$8
(50
)
4
22.9
[100]
$2 (50)
$1
0)
(9
FIGURE 22.7
3
a fi = 0
i=1
The condition says that the total supply in the network equals the total demand.
We can always satisfy this requirement by adding a balancing dummy source or destination, which we connect to all other nodes in the network by arcs with zero unit cost and
infinite capacity. However, the balancing of the network does not guarantee feasibility,
as this depends on the capacities of the arcs.
We now present the steps of the capacitated algorithm. Familiarity with the simplex method and duality theory (Chapters 3 and 4) is essential. Also, knowledge of the
upper-bounded simplex method (Section 7.3) is helpful.
Step 0.
Step 1.
Step 2.
Determine a starting basic feasible solution (set of arcs) for the network. Go
to step 1.
Determine an entering arc (variable) using the simplex method optimality
condition. If the solution is optimal, stop; otherwise, go to step 2.
Determine the leaving arc (variable) using the simplex method feasibility
condition. Determine the new solution, then go to step 1.
M22_TAHA5937_09_SE_C22.QXD
22.10
Chapter 22
7/22/10
10:10 PM
Page 22.10
Section 22.1.2, let wi be the dual variable associated with the constraint of node i, then
the dual problem (excluding the upper bounds) is given as
n
Maximize z = a fiwi
i=1
subject to
wi - wj cij, (i, j) H A
wi unrestricted in sign, i = 1, 2, , n
From the theory of linear programming, we have
wi - wj = cij, for basic arc (i, j)
Because the original linear program (Section 22.1.2) has one redundant constraint by
definition, we can assign an arbitrary value to one of the dual variables (compare with
the transportation algorithm, Section 5.3). For convenience, we will set w1 = 0. We
then solve the (basic) equations wi - wj = cij to determine the remaining dual values.
From Section 4.2.4, Formula 2, we know that the objective coefficient of nonbasic xij is
the difference between the left-hand side and the right-hand side of the associated dual
constraint, that is, wi - wj - cij. Letting
zij = wi - wj
the objective coefficient of the variable xij is computed as
zij - cij = wi - wj - cij
The only remaining detail is to show how the leaving variable is determined. The
following numeric example provides this detail.
Example 22.1-4
A network of pipelines connects two water desalination plants to two cities. The daily supply
amounts at the two plants are 40 and 50 million gallons, and the daily demand amounts at cities
1 and 2 are 30 and 60 million gallons, respectively. Nodes 1 and 2 represent plants 1 and 2, respectively, and nodes 4 and 5 represent cities 1 and 2, respectively. Node 3 is a booster station between
the plants and the cities. The model is already balanced because the sum of the supply at nodes
1 and 2 equals the sum of the demand at nodes 4 and 5. Figure 22.8 gives the associated network.
Iteration 0
Step 0.
Determination of a Starting Basic Feasible Solution: The starting basic solution must be
a spanning tree. The feasible spanning tree in Figure 22.9 (shown with solid arcs) is
obtained by inspection. Normally, we use an artificial-variable technique to find such a
solution (for details, see Bazaraa et al., 1990, pp. 440446).
In Figure 22.9, the basic feasible solution consists of (solid) arcs (1, 3), (1, 4),
(2, 3), and (3, 5) with the feasible flows of 30, 10, 50, and 60 units, respectively. The
remaining (dashed) arcs (1, 2), (2, 5), and (4, 5) represent the nonbasic variables.
The notation x(c) shown on the arcs indicates that a flow of x units is assigned to an
arc with capacity c. The default values for x and c are 0 and q, respectively.
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.11
22.1
Unit cost
Plant 1 [40]
Arc capacity
$5
4
(35)
22.11
[30] City 1
$7 )
0
(1
$
(6 2
0)
$3 ()
Plant 2 [50]
w1 0
[40]
$8
(
)
$1
(30)
$7 0)
(1
10
$3
50 $2
(6
0)
[30]
w3 7
$
60 8
(
)
$1
(30)
$4 ()
[50] 2
w2 5
FIGURE 22.8
[60] City 2
w4 5
$5
30(35)
$4 ()
FIGURE 22.9
Network for iteration 0
Iteration 1
Step 1.
Determination of the entering arc: We obtain the dual values by solving the current
basic equations
w1 = 0
wi - wj = cij, for basic arc (i, j)
We thus get,
Arc(1, 3): w1 - w3 = 7, hence w3 = -7
Arc(1, 4): w1 - w4 = 5, hence w4 = -5
Arc(2, 3): w2 - w3 = 2, hence w2 = -5
Arc(3, 5): w3 - w5 = 8, hence w5 = -15
Now, we compute zij - cij for the nonbasic arcs as
Arc (1, 2): w1 - w2 - c12 = 0 - ( -5) - 3 = 2
Arc (2, 5): w2 - w5 - c25 = ( -5) - (-15) - 1 = 9
Arc (4, 5): w4 - w5 - c45 = ( -5) - (-15) - 4 = 6
Thus, arc (2, 5) enters the basic solution.
M22_TAHA5937_09_SE_C22.QXD
22.12
Chapter 22
Step 2.
7/22/10
10:10 PM
Page 22.12
Determination of the leaving arc: From Figure 22.9, arc (2, 5) forms a loop with basic
arcs (2, 3) and (3, 5). From the definition of the spanning tree, no other loop can be
formed. Because the flow in the new arc (2, 5) must be increased, we adjust the flow
in the arcs of the loop by an equal amount to maintain the feasibility of the new solution. To achieve this, we identify the positive ( + ) flow in the loop by the direction
of flow of the entering arc (i.e., from 2 to 5). We then assign ( + ) or ( - ) to the
remaining arcs of the loop, depending on whether the flow of each arc is with or
against the direction of flow of the entering arc. These sign conventions are shown in
Figure 22.9.
Determination of the maximum level of flow in the entering arc (2, 5) is based on
two conditions:
1. New flow in the current basic arcs of the loop cannot be negative.
2. New flow in the entering arc cannot exceed its capacity.
The application of condition 1 shows that the flows in arcs (2, 3) and (3, 5) cannot be
decreased by more than min{50, 60} = 50 units. By condition 2, the flow in arc (2, 5) can
be increased to at most the arc capacity ( = 30 units). Thus, the maximum flow change in
the loop is min{30, 50} = 30 units. The new flows in the loop are thus 30 units in arc (2,
5), 50 - 30 = 20 units in arc (2, 3), and 60 - 30 = 30 units in arc (3, 5).
Because none of the current basic arcs leave the basis at zero level, the new arc
(2, 5) must remain nonbasic at upper bound. However, to avoid dealing with nonbasic
arcs that are at capacity (or upper bound) level, we implement the substitution
x25 = 30 - x52, 0 x52 30
This substitution is effected in the flow equations associated with nodes 2 and 5 as
follows. Consider
Current flow equation at node 2: 50 + x12 = x23 + x25
Current flow equation at node 5: x25 + x35 + x45 = 60
Then, the substitution x25 = 30 - x52 gives
New flow equation at node 2: 20 + x12 + x52 = x23
New flow equation at node 5: x35 + x45 = x52 + 30
The results of these changes are shown in Figure 22.10. The direction of flow in
arc (2, 5) is now reversed to 5 : 2 with x52 = 0 , as desired. The substitution also
requires changing the unit cost of arc (5, 2) to - $1. We will indicate this direction
reversal on the network by tagging the arc capacity with an asterisk.
Iteration 2. Figure 22.10 summarizes the new values of zij - cij (verify!) and shows that arc
(4, 5) enters the basic solution. It also defines the loop associated with the new
entering arc and assigns the signs to its arcs.
The flow in arc (4, 5) can be increased by the smallest of
1. Maximum allowable increase in entering arc (4, 5) = q
2. Maximum allowable increase in arc (1, 4) = 35 - 30 = 5 units
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.13
22.1
w1 0
[40]
$5
30(35)
1
$7 0)
(1
10
$3
20 $2
(6
0)
[30]
$4 ()
$
30 8
(
)
$1
(30)*
22.13
w4 5
w 7
3
3
[20] 2
w2 5
5 [30]
w5 15
FIGURE 22.10
Network for iteration 1
$5
(35)*
1
$7 0)
1
5(
20 $2
(6
0)
$3
[20] 2
w2 5
w4 11
4
[5]
w3 7
$4 5()
3
$
25 8
(
)
$1
(30)*
5 [30]
w5 15
M22_TAHA5937_09_SE_C22.QXD
Chapter 22
w1 0
[5]
10:10 PM
Page 22.14
$5
(35)*
1
$7 )
0
(1
$3 5()
25 $2
(6
0)
22.14
7/22/10
[20] 2
w2 3
[5]
w3 5
Optimum solution:
x12 5, x13 0
x14 35 0 35
x23 25
x25 30 0 30
x35 25, x45 5
Total cost $490
$4 5()
3
$
25 8
(
)
$1
(30)*
5 [30]
w5 13
FIGURE 22.12
Network for iteration 3
Solver Moment
The basic idea of the Excel Solver minimum cost capacitated model is similar to the one detailed
in Example 6.3-6 for the shortest-route model. File solverEx22.1-4.xls provides the details.
AMPL Moment
File amplEx22.1-4.txt is a general model that can be used to solve the minimum cost capacitated
problem of any size. The idea of the model is similar to that of the shortest-route AMPL model
for Example 6.3-6.
Supply
$5
$8
$4
$6
$9
$12
10
$3
$1
$5
18
Demand
16
14
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.15
22.1
2
11
2
10
1
4
5
6
4
3
7
1
22.15
FIGURE 22.13
Network for Problem 8, Set 22.1c
8. The network in Figure 22.13 gives the distances among seven cities. Use the capacitated
simplex algorithm to find the shortest distance between nodes 1 and 7. (Hint: Assume
that nodes 1 and 7 have net flows of [ +1] and [ -1], respectively. All the other nodes have
zero net flow.)
9. Show how the capacitated minimum-cost flow model can be specialized to represent
the maximum flow model of Section 6.4. Apply the transformation to the network in
Example 6.4-2. For convenience, assume that the flow capacity from 4 to 3 is zero. All
the remaining data are unchanged.
10. Solve the following problems using Excel Solver and AMPL:
(a) Problem 3, Set 22.1a.
(b) Problem 4, Set 22.1a.
(c) Problem 7, Set 22.1c.
(d) Problem 8, Set 22.1c.
M22_TAHA5937_09_SE_C22.QXD
22.16
Chapter 22
7/22/10
10:10 PM
Page 22.16
800
8
1000
P1
T1
4
7
2
1200
5
D2
900
4
5
P2
T2
FIGURE 22.14
3
D3
500
Transshipment occurs in the network in Figure 5.7 because the entire supply amount of 2200
(= 1000 + 1200) cars at nodes P1 and P2 could conceivably pass through any node of the network before ultimately reaching their destinations at nodes D1, D2, and D3. In this regard, each
node of the network with both input and output arcs (T1, T2, D1, and D2) acts as both a source
and a destination and is referred to as a transshipment node. The remaining nodes are either
pure supply nodes (P1 and P2) or pure demand nodes (D3).
The transshipment model can be converted into a regular transportation model with
6 sources (P1, P2, T1, T2, D1, and D2) and five destinations (T1, T2, D1, D2, and D3). The
amounts of supply and demand at the different nodes are computed as
Supply at a pure supply node = Original supply
Demand at a pure demand node = Original demand
Supply at a transshipment node = Original supply + Buffer amount
Demand at a transshipment node = Original demand + Buffer amount
The buffer amount should be sufficiently large to allow all of the original supply (or
demand) units to pass through any of the transshipment nodes. Let B be the desired buffer
amount; then
B = Total supply (or demand)
= 1000 + 1200 (or 800 + 900 + 500)
= 2200 cars
Using the buffer B and the unit shipping costs given in the network, we construct the equivalent
regular transportation model as in the table below.
T1
T2
D1
D2
D3
P1
1000
P2
1200
T1
T2
D1
D2
800 + B 900 + B
500
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.17
22.1
D1
800
D2
900
22.17
800
1000
P1
T1
10
400
00
00
12
0
100
1200
500
T2
P2
FIGURE 22.15
D3
500
100
150
200
900
3
2
1
4
.8
4.3
5
2
4.6
1000
150
1100
FIGURE 22.17
Network for Problem 3, Set 22.1D
4.5
6
.5
.2
.3
1400
FIGURE 22.16
1000
1200
2.1
1.9
You are encouraged to use TORA, Excel Solver, or AMPL to solve the problems in this set.
M22_TAHA5937_09_SE_C22.QXD
22.18
7/22/10
Chapter 22
10:10 PM
Page 22.18
Formulate the problem as a transshipment model, and find the optimum shipping
schedule.
3. The network in Figure 22.17 shows the routes for shipping cars from three plants
(nodes 1, 2, and 3) to three dealers (nodes 6 to 8) by way of two distribution
centers (nodes 4 and 5). The shipping costs per car (in $100) are shown on
the arcs.
(a) Solve the problem as a transshipment model.
(b) Find the new optimum solution assuming that distribution center 4 can sell 240 cars
directly to customers.
4. Consider the transportation problem in which two factories supply three stores with a
commodity. The numbers of supply units available at sources 1 and 2 are 200 and 300,
respectively; those demanded at stores 1, 2, and 3 are 100, 200, and 50, respectively. Units
may be transshipped among the factories and the stores before reaching their final destination. Find the optimal shipping schedule based on the unit costs in the following table.
Factory
Factory
Store
Store
$0
$6
$7
$8
$9
$6
$0
$5
$4
$3
$7
$2
$0
$5
$1
$1
$5
$1
$0
$4
$8
$9
$7
$6
$0
5. Consider the oil pipeline network shown in Figure 22.18. The different nodes represent
pumping and receiving stations. Distances in miles between the stations are shown on the
network. The transportation cost per gallon between two nodes is directly proportional
to the length of the pipeline. Develop the associated transshipment model, and find the
optimum solution.
6. Shortest-Route Problem. Find the shortest route between nodes 1 and 7 of the network
in Figure 22.19 by formulating the problem as a transshipment model. The distances
between the different nodes are shown on the network. (Hint: Assume that node 1 has
a net supply of 1 unit, and node 7 has a net demand also of 1 unit.)
50,000
60,000 (gallons)
FIGURE 22.18
Network for Problem 5, Set 22.1D
1
20
2
90,000
40
30
4
8
6
20,000
10
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.19
22.1
22.19
4
2
5
1
4
3
7
6
7
3
FIGURE 22.19
Network for Problem 6, Set 22.1D
7. In the transshipment model of Example 5.5-1, define xij as the amount shipped from
node i to node j. The problem can be formulated as a linear program in which each
node produces a constraint equation. Develop the linear program, and show that the
resulting formulation has the characteristic that the constraint coefficients, aij , of the
variable xij are
aij =
1, in constraint i
in constraint j
0, otherwise
-1,
8. An employment agency must provide the following laborers over the next
5 months:
Month
Number of laborers
100
120
80
170
50
Because the cost of labor depends on the length of employment, it may be more
economical to keep more laborers than needed during some months of the 5-month
planning horizon. The following table estimates the labor cost as a function of the length
of employment:
Months of employment
Cost per laborer ($)
100
130
180
220
250
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
22.20
Chapter 22
22.2
DECOMPOSITION ALGORITHM
Page 22.20
Consider the situation of developing a master corporate plan for several production
facilities. Although each facility has its own independent capacity and production
constraints, the different facilities are linked together at the corporate level by
budgetary considerations. The resulting model includes two types of constraints:
common, representing the corporate budgetary constraints, and independent, representing the internal capacity and production restrictions of each facility. Figure 22.20
depicts the layout of the resulting constraints for n activities (facilities). In the absence
of the common constraints, all activities operate independently.
The decomposition algorithm improves the computational efficiency of the
problem depicted in Figure 22.20 by breaking it down into n subproblems that can be
solved almost independently. We point out, however, that the need for the decomposition algorithm was more justifiable in the past when the speed and memory of the
computer were modest. Todays impressive computer capabilities obviate the use of
the decomposition algorithm. Nevertheless, we present the algorithm here because of its
interesting theoretical contribution.
The corresponding mathematical model is given as
Maximize z = C1X1 + C2X2 + + CnXn
subject to
A1X1 + A2X2 + + AnXn b0
D1X1
b1
D2X2
b2
o
o
DnXn bn
Xj 0, j = 1, 2, , n
The slack and surplus variables are added as necessary to convert all the inequalities into equations.
FIGURE 22.20
Common constraints
Activity
2
Activity
n
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.21
22.2
Decomposition Algorithm
22.21
N , j = 1, 2, , n
Xj = a b jkX
jk
k=1
kj
We can reformulate the entire problem in terms of the extreme points to obtain
the following master problem:
K1
K2
Kn
k=1
k=1
k=1
N b +
N
N
+
Maximize = a C1X
1k 1k
a C2X2k b 2k +
a CnXnk b nk
subject to
K1
K2
Kn
k=1
k=1
k=1
N
N
N
+
a A1X1k b 1k + a A2X2k b 2k +
a AnXnk b nk b0
Kj
a b 1k
= 1
k=1
Kj
a b 2k
= 1
k=1
o
Kj
a b nk
= 1
k=1
N ,
Xj = a b jkX
jk
j = 1, 2, , n
k=1
It may appear that the solution of the master problem requires prior determination
N , a difficult task indeed! Fortunately, it is not so.
of all the extreme points X
jk
M22_TAHA5937_09_SE_C22.QXD
22.22
Chapter 22
7/22/10
10:10 PM
Page 22.22
To solve the master problem by the revised simplex method (Section 7.2), we need
to determine the entering and the leaving variables at each iteration. For the entering
variable, given CB and B-1 of the current basis of the master problem, then for nonbasic
b jk, we have
zjk - cjk = CBB-1Pjk - cjk
where
N and P
cjk = CjX
jk
jk
N
AjX
jk
0
o
=
1
o
0
Now, to decide which, if any, of the nonbasic variables b jk should enter the
solution, we need to determine
zj*k* - cj*k* =
all j and k
all j and k
The reason we are able to establish this identity is that each convex set {X|Dj
Xj bj, Xj 0} has its independent set of extreme points. In effect, what the identity
says is that we can determine zj*k* - cj*k* in two steps:
Step 1.
For each convex set {X|DjXj bj, Xj 0}, determine the extreme point
N
Y
jk* that yields the smallest zjk - cjkthat is, zjk* - cjk* = mink{zjk - cjk}.
Step 2.
From LP theory, we know that the optimum solution, when finite, must be associated with an extreme point of the solution space. Because each of the sets
{X|DjXj bj, Xj 0} is bounded by definition, step 1 is mathematically equivalent
to solving n linear programs of the form
Minimize wj = {zj - cj|DjXj bj, Xj 0}
The objective function wj is a linear function in Xj (see Problem 8, Set 22.2a).
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.23
22.2
Decomposition Algorithm
22.23
The determination of the entering variable b j*k* in the master problem reduces
to solving n (smaller) linear programs to determine the entering extreme point
N
Y
j*k*. This approach precludes the need to determine all the extreme points of all n
convex sets. Once the desired extreme point is located, all the elements of the
column vector Pj*k* are defined. We can then determine the leaving variable, and
subsequently compute the next B-1 using the revised simplex method computations.
Example 22.2-1
Solve the following LP by the decomposition algorithm:
Maximize z = 3x1 + 5x2 + x3 + x4
subject to
x1 + x2 + x3 + x4 40
5x1 + x2
12
x3 + x4 5
x3 + 5x4 50
x1, x2, x3, x4 0
The problem has two subproblems that correspond to the following sets of variables:
X1 = (x1, x2)T, X2 = (x3, x4)T
The associated master problem is thus given as:
Subproblem 1
b 11
b 12
b 1K1
b 21
b 22
b 2K2
x5
x6
x7
N
C 2X
2k2
-M
-M
N
A 2X
2K2
0
1
1
0
0
0
1
0
0
0
1
N
C 1X
11
N
C 1X
12
N
C 1X
1K1
N
C 2X
21
N
C 2X
22
N
A 1X
11
1
0
N
A 1X
12
1
0
N
A 1X
1K1
1
0
N
A 2X
21
0
1
N
A 2X
22
0
1
C 1 = (3, 5)
A 1 = (1, 1)
C 2 = (1, 1)
A 2 = (1, 1)
5x1 + x2 12
x1, x2 0
Starting basic
solution
Subproblem 2
= 40
= 1
= 1
x3 + x4 5
x3 + 5x4 50
x3, x4 0
Notice that x5 is the slack variable that converts the common constraint to the following equation:
x1 + x2 + x3 + x4 + x5 = 40
M22_TAHA5937_09_SE_C22.QXD
22.24
Chapter 22
7/22/10
10:10 PM
Page 22.24
Recall that subproblems 1 and 2 account for variables x1, x2, x3, and x4 only. This is the reason x5
must appear explicitly in the master problem. The remaining starting basic variables, x6 and x7,
are artificial.
Iteration 0
XB = (x5, x6, x7)T = (40, 1, 1)T
CB = (0, -M, -M), B = B-1 = I
Iteration 1
Subproblem 1 (j = 1). We have
z1 - c1 = CBB-1
A1X1
1 - C1X1
0
11, 12a
x1
b
x2
1
0
- 13, 52a
x1
b
x2
= - 3x1 - 5x2 - M
Thus, the corresponding LP is
Minimize w1 = -3x1 - 5x2 - M
subject to
5x1 + x2 12
x1, x2 0
The solution of this problem (by the simplex method) yields
N = 10, 122T, z - c = w = -60 - M
X
11
1
1
1
Subproblem 2 (j = 2). The associated linear program is given as
Minimize z2 - c2 = CBB-1
A2X2
0 - C2X2
1
= -x4 - x5 - M
11, 12a
0
1
x3
b
x4
- 11, 12a
x4
b
x5
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.25
22.2
Decomposition Algorithm
22.25
subject to
x3 + x4 5
x3 + 5x4 50
x3, x4 0
The optimal solution of the problem yields
N = 150, 02T, z - c = -50 - M
X
21
2
2
Because the master problem is of the maximization type and z*1 - c*1 6 z*2 - c*2 and z*1 - c*1 6 0,
N enters the solution.
it follows that b 11 associated with extreme point X
11
To determine the leaving variable,
P11
0
11, 12a b
N
A1X
12
12
11
= 1 =
1
= 1
0
0
0
Thus, B-1P11 = (12, 1, 0)T. Given XB = (x5, x6, x7)T = (40, 1, 1)T , it follows that x6 (an artificial
variable) leaves the basic solution (permanently).
The new basis is determined by replacing the vector associated with x6 with the vector P11,
which gives (verify!)
1
B = 0
0
12
1
0
0
1
0 Q B-1 = 0
1
0
-12
1
0
0
0
1
M22_TAHA5937_09_SE_C22.QXD
22.26
Chapter 22
7/22/10
10:10 PM
Page 22.26
P22
N
A2X
22
= 0 =
1
11, 12a
0
1
50
b
0
50
= 0
1
Thus, B-1P22 = (50, 0, 1)T. Because XB = (x5, b 11, x7)T = (28, 1, 1)T, x5 leaves.
The new basis and its inverse are given as (verify!)
50
B = 0
1
1
0
50
-1
0 Q B = 0
1
1
- 50
12
1
0
- 12
50
1
0
0
1
12
50
11 T
A 14
25 , 1, 25 B
N ,C X
N
CB = 1C2 X
22
1 11, -M2 = 150, 60, -M2
Iteration 3
Subproblem 1 (j = 1). You should verify that the associated objective function is
Minimize w1 =
M
AM
50 - 2 B x1 + A 50 - 4 B x2 -
12M
50
+ 48
AM
50 B (x3 + x4) - M
= 1 +
M
50
M
50
, 48 -
12M
50
, - M B (1, 0, 0)T - 0
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.27
22.2
Decomposition Algorithm
22.27
P23
N
A2X
23
= 0 =
1
5
11, 12a b
0
5
0
= 0
1
1
1
9 T
11 T
Thus, B-1P23 = 1 10
, 0, 10
2 . Given that XB = (b 22, b 11, x7)T = 1 14
25 , 1, 25 2 , the artificial
variable x10 leaves the basic solution (permanently).
The new basis and its inverse are thus given as (verify!)
50
B = 0
1
12
1
0
1
5
45
-1
0 Q B = 0
1
1
- 45
- 12
45
1
5
- 45
0
12
45
50
45
23
45
, 1, 22
45
BT
Iteration 4
Subproblem 1 (j = 1). w1 = - 2x1 - 4x2 + 48. It yields z*1 - c*1 = w*1 = 0.
Subproblem 2 (j = 2). w2 = 0x4 + 0x5 + 48 + 48.
Nonbasic Variable x5: z5 - c5 = 1. The preceding information shows that iteration 3 is optimal.
We can compute the optimum solution of the original problem by back-substitution:
N = 110, 122T = 10, 122T
X1 = 1x1, x22T = b 11 X
11
N + b X
N
X2 = 1x4, x52T = b 22 X
22
23 23
=
22
T
T
A 23
45 B A 50, 02 + A 45 B 15, 0 B
= 128, 02T
All the remaining variables are zero. The optimum value of the objective function can be
obtained by direct substitution.
M22_TAHA5937_09_SE_C22.QXD
22.28
7/22/10
Chapter 22
10:10 PM
Page 22.28
(b)
2x1 + x2 2
3x1 + 4x2 12
x1, x2 0
*(c)
x1 - x2 10
2x1
40
x1, x2 0
*2. In Example 22.2-1, the feasible extreme points of subspaces D1X1 = b1, X1 0
and D2X2 = b2, X2 0 can be determined graphically. Use this information to express
the associated master problem explicitly in terms of the feasible extreme points. Then
show that the application of the simplex method to the master problem produces the
same entering variable b jk as that generated by solving subproblems 1 and 2. Hence,
convince yourself that the determination of the entering variable b jk is exactly
equivalent to solving the two minimization subproblems.
3. Consider the following linear program:
Maximize z = x1 + 3x2 + 5x3 + 2x4
subject to
x1 + 4x2
2x1 + x2
10
x3 - 5x4 4
x3 + x4 10
x1, x2, x3, x4 0
Construct the master problem explicitly by using the extreme points of the subspaces,
and then solve the resulting problem directly by the simplex method.
4. Solve Problem 3 using the decomposition algorithm, and compare the two procedures.
5. Apply the decomposition algorithm to the following problem:
Maximize z = 6x1 + 7x2 + 3x3 + 5x4 + x5 + x6
subject to
x1 + x2 +
x3 + x4 + x5 + x6 50
x1 + x2
10
x2
8
5x3 + x4
12
x5 + x6 5
x5 + 5x6 50
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.29
22.3
22.29
*6. Indicate the necessary changes for applying the decomposition algorithm to minimization
LPs. Then solve the following problem:
Minimize z = 5x1 + 3x2 + 8x3 - 5x4
subject to
x1 + x3 + x3 + x4 25
5x1 + x2
20
5x1 - x2
5
x3 + x4 = 20
2y1 + y2 + y3
3y1
+ y4 + y5 4
y1
+ 2y4 - y5 10
y1, y2, y3, y4, y5 0
22.3
M22_TAHA5937_09_SE_C22.QXD
22.30
7/22/10
Chapter 22
10:10 PM
Page 22.30
x2
2
A
Gradient of z
Maximize
z = x1
C
D
E
B
x1
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.31
22.3
22.31
along the projected gradient will not overshoot the optimum point at B, and (2) in the
general n-dimensional case, the direction created by the projected gradient will not
cause an entrapment of the algorithm at a nonoptimum point. This, basically, is what
Karmarkars interior-point algorithm accomplishes.
22.3.2 Interior-Point Algorithm
Several variants of Karmarkars algorithm are available in the literature. Our presentation follows the original algorithm. Karmarkar assumes that the LP is given as
Minimize z = CX
subject to
AX = 0
1X = 1
X 0
All the constraints are homogeneous equations except for the constraint
n
1X = a j = 1xj = 1, which defines an n-dimensional simplex. The validity of Karmarkars
algorithm rests on satisfying two conditions:
1. X = A n1 , n1 , , n1 B satisfies AX = 0.
2. min z = 0.
Karmarkar provides modifications that allow solving the problem when the second
condition is not satisfied. These modifications will not be presented here.
The following example illustrates how a general LP can be made to satisfy the
two stipulated conditions.
Example 22.3-1
Consider the problem.
Maximize z = y1 + y2
subject to
y1 + 2y2 2
y1, y2 0
We start by defining the primal and dual problems of the LP:
Primal
Dual
Maximize y0 = y1 + y2
subject to
Minimize w0 = 2w1
subject to
y1 + 2y2 2
y1, y2 0
w1 1
f Q w1 1
2w1 1
w1 0
M22_TAHA5937_09_SE_C22.QXD
22.32
Chapter 22
7/22/10
10:10 PM
Page 22.32
(1)
(2)
(3)
(4)
Next, define a new variable s2. From (4) the following two equations hold if, and only if, the
condition s2 = 1 holds:
y1 + y2 + y3 + w1 + w2 + s1 - Ms2 = 0
y1 + y2 + y3 + w1 + w2 + s1 +
s2 = M + 1
(5)
Now, given s2 = 1 as stipulated by (5), the primal and dual equations (1) can be written as
y1 + 2y2 + y3 - 2s2 = 0
w1 - w2 - 1s2 = 0
(6)
Now, define
yj = (M + 1)xj, j = 1, 2, 3
wj - 3 = (M + 1)xj, j = 4, 5
s1 = (M + 1)x6
s2 = (M + 1)x7
Substitution in equations (2), (5), and (6) will produce the following equations:
x1 + x2
- 2x4
= 0
x1 + x2 + x3 + x4 + x5 + x6 - Mx7 = 0
x1 + x2 + x3 + x4 + x5 + x6 +
x1 + 2x2 + x3 +
x7 = 1
- 2x7 = 1
x4 - x5
x7 = 0
xj 0, j = 1, 2, , 7
The final step calls for augmenting the artificial variable y8 in the left-hand side of each
equation. The new objective function will call for minimizing y8, whose obvious minimum value
must be zero (assuming the primal is feasible). Note, however, that Karmarkars algorithm
requires the solution
X =
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.33
22.3
22.33
to be feasible for AX = 0. This will be true for the homogeneous equations (with zero righthand side) if the associated coefficient of the artificial x8 equals the (algebraic) sum of all the
coefficients on the left-hand side. It thus follows that the transformed LP is given as
Minimize z = x8
subject to
x1 + x2
- 2x4
0x8 = 0
x1 + x2 + x3 + x4 + x5 + x6 - Mx7 - 16 - M2x8 = 0
x1 + 2x2 + x3
2x7 -
2x8 = 0
x7 +
x8 = 0
x1 + x2 + x3 + x4 + x5 + x6 +
x7 +
x8 = 1
x4 - x5
xj 0, j = 1, 2, , 8
Note that the solution of this problem automatically yields the optimum solutions of the primal
and dual problems through back-substitution.
Figure 22.22 provides a typical illustration of the solution space in three dimensions with the
homogeneous set AX = 0 consisting only of one equation. By definition, the solution space
consisting of the line segment AB lies entirely in the two-dimensional simplex 1X = 1 and
passes through the feasible interior point A 13 , 13 , 13 B .
Steps of the algorithm. Karmarkars algorithm starts from an interior point represented by the center of the simplex and then advances in the direction of the projected
gradient to determine a new solution point. The new point must be strictly interior,
meaning that all its coordinates must be positive. The validity of the algorithm rests on
this condition.
For the new solution point to be strictly interior, it must not lie on the boundaries
of the simplex. (In terms of Figure 22.22, points A and B must be excluded.) To
guarantee this result, a sphere with its center coinciding with that of the simplex is
inscribed tightly inside the simplex. In the n-dimensional case, the radius r of this
sphere equals n(n1 - 1). A smaller sphere with radius ar (0 6 a 6 1) will be a subset
3
of the sphere, and any point in the intersection of the smaller sphere with the homogeneous system AX = 0 will be an interior point, with strictly positive coordinates. Thus,
we can move as far as possible in this restricted space (intersection of AX = 0 and the
ar-sphere) along the projected gradient to determine the new (improved) solution
point.
The new solution point no longer will be at the center of the simplex. For the
procedure to be iterative, we need to find a way to bring the new solution point to the
center of a simplex. Karmarkar satisfies this requirement by proposing the following
intriguing idea, called projective transformation. Let
yi =
xi
xki
n x
j=1
i
xkj
, i = 1, 2, , n
M22_TAHA5937_09_SE_C22.QXD
22.34
Chapter 22
7/22/10
10:10 PM
Page 22.34
(0, 0, 1)
Simplex 1X 1
Intersection of
AX 0 and 1X 1
Center of
simplex
1,1,1
3 3 3
x1
(1, 0, 0)
A
(0, 1, 0)
x2
(a) Three dimensions
(0, 0, 0, 1)
Simplex 1X 1
Intersection of
AX 0 and 1X 1
C
Center of
simplex
1,1,1,1
4 4 4 4
B
(0, 0, 1, 0)
(0, 1, 0, 0)
(b) Four dimensions
FIGURE 22.22
Illustrations of the simplex 1X = 1
(1, 0, 0, 0)
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.35
22.3
22.35
where xki is the i th element of the current solution point Xk . The transformation
n
is valid, because all xki 7 0 by design. You will also notice that a i = 1yi = 1, or
1Y = 1, by definition. This transformation is equivalent to
Y =
Dk-1X
1Dk-1X
where Dk is a diagonal matrix whose ith diagonal elements equal xki. The transformation maps the X-space onto the Y-space uniquely because we can show that the
last equation yields
X =
DkY
1DkY
1 1
1 t
, , , b , and cp is the projected gradient, which can be shown to be
n n
n
cp = [I - PT1PPT2-1P]1cDk2T
where
P = a
ADk
b
1
M22_TAHA5937_09_SE_C22.QXD
22.36
Chapter 22
7/22/10
10:10 PM
Page 22.36
A n1 , n1 , , n1 B , and compute r =
1
1n(n - 1)
Ynew = a
Xk + 1
where
cp = [I - PT(PPT)-1P](cDk)T
Example 22.3-2
Minimize z = 2x1 + 2x2 - 3x3
subject to
-x1 - 2x2 + 3x3 = 0
x1 + x2 + x3 = 1
x1, x2, x3 0
The problem satisfies the two conditions imposed by the interior-point algorithmnamely,
X = (x1, x2, x3)T =
A 13 , 13 , 13 B T,
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.37
22.3
Iteration 0
c = (2, 2, -3), A = (-1, -2, 3)
A 13 , 13 , 13 B T, z0 = 13 , r =
X0 =
1
3
D0 = 0
0
1
26
,a =
2
9
0
0
1
3
1
3
A 13 , 13 , 13 B T
Iteration 1
1
3
0
0 =
1
3
1
3
1
3
-1
= a 3
1
1
I - P 1PP 2 P = 0
0
T
T -1
0
1
3
0
0 = A - 13, - 23, 1 B
1
3
-1
- 13 1
9
1
0
2
b - 3 1 = a 14 1 b
1
0 3
1 1
0
- 13 1
9
0 - 1 - 23
0 - - 23 1 a 14 1 b a 3
0 3
1
1
1
1 1
- 23
1
0
1
0
25
A 23, 23, -1 B
1
42 -20
-5
-20
16
4
1
b
1
-5
4
1
Thus,
cp = 1I - P 1PP 2 P21cD02 =
T
T -1
25
1
42 -20
-5
-20
16
4
2
-5
3
4 23 =
1
-1
cp =
1262
= .257172
25
1
126 -20
-5
22.37
M22_TAHA5937_09_SE_C22.QXD
22.38
Chapter 22
7/22/10
10:10 PM
Page 22.38
Thus,
Ynew =
A 13, 13, 13 B T -
2
9
1
116
1
.257171
1
126
1D0Ynew =
1
3
Now,
X1 =
D0Ynew
=
1D0Ynew
1
3
Ynew
1
3
z1 = .26334
Iteration 2
cD1 = 12, 2, -32
.263340
0
0
0
.389328
0
.263340
0
0
0
0 = 1.526680, .778656, -1.0419962
.347332
0
.389328
0
0
0
.347332
-.26334
= a
1
= a
.567727
0
-.778656
1
-.263340
1.041996
b -.778656
1
1.041996
-1
1
1
1
0
b
.333333
I - PT1PPT2-1P
1
= 0
0
a
0
1
0
0
-.263340
0 - -.778656
1
1.041996
1
.567727
1 a
0
1
-.263340
1
-.778656
1
1.041996
b
1
.627296
= -.449746
-.177550
-.449746
.322451
.127295
-.177550
.127295
.050254
0
b
.333333
M22_TAHA5937_09_SE_C22.QXD
7/22/10
10:10 PM
Page 22.39
22.3
22.39
Thus,
.627296
cp = 1I - PT1PPT2-1P21cD12T = -.449746
-.177550
-.449746
.322451
.127295
-.177550
.127295
.050254
.526680
.778656
-1.041996
.165193
= -.118435
-.046757
It then follows that
||cp|| = 3.1651932 + (-.118435)2 + ( -.046757)2 = .208571
Thus,
Ynew = ( 13 , 13 , 13 )T -
2
9
1
116
1
.208571
D1Ynew =
.263340
0
0
0
.389328
0
0
.261479
.068858
0 .384849 = .149832
.347332
.353671
.122841
1D1Ynew = .341531
Now,
X2 =
D1Ynew
= 1.201616
1D1Ynew
.438707
.3596772T
z2 = .201615
Repeated application of the algorithm will move the solution closer to the optimum point
(0, .6, .4). Karmarkar does provide an additional step for rounding the optimal solution to the
optimum extreme point.
M22_TAHA5937_09_SE_C22.QXD
22.40
7/22/10
Chapter 22
10:10 PM
Page 22.40
BIBLIOGRAPHY
Ahuja, R., T. Magnati, and J. Orlin, Network Flows: Theory, Algorithms, and Applications,
Prentice Hall, Upper Saddle River, NJ, 1993.
Bazaraa, M., J. Jarvis, and H. Sherali, Linear Programming and Network Flow, 4th ed., Wiley,
New York, 2009.
Charnes, A. and W. Cooper, Some Network Characterization for Mathematical Programming
and Accounting Applications to Planning and Control, The Accounting Review, Vol. 42,
No. 3, pp. 2452, 1967.
Hooker, J., Karmarkars Linear Programming Algorithm, Interfaces, Vol. 16, No. 4, pp. 7590,
1986.
Lasdon, L., Optimization for Large Systems, Macmillan, New York, 1970.