# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**132**> 133 134 135 136 137 138 .. 156 >> Next

4. Add arcs of cost 0 from x'0 to every x, e X, and from every x e X, U Xh U Xk to xg.

Set the capacity of every arc and vertex of G equal to 1, and solve the maximum flow maximum cost problem for graph G (Christofides, 1975). The maximum amount by which liquid of type i could be further increased is at least as large as the cost A" of this flow and the total maximum increase without changing the value of the solution is therefore at least as large as:

This follows from the fact that every feasible flow pattern in G corresponds to a feasible exchange (one-for-one) of tanks containing liquid i with tanks containing other liquids. The cost of this flow corresponds to the feasible increment in q, produced by the tank exchange. Thus, a flow of one unit from x', to x, to xh to xk to x involves the exchange of tank t with tank h and the subsequent exchange of tank h with tank k. (Note that it is unnecessary to add arcs from vertices in Xk to those in Xh).

It is possible to account for many-for-one and one-for-many tank exchanges in very much the same way but at the cost of a vastly increased size of network flow problem and computation times which may be unjustified for sensitivity purposes.

Removal of Tanks

Consider tank r e S* and assume r e Ft. The least amount of liquid of type k in tank r is W, given by equation (12.11). If tank r is removed from the set E0 of available tanks, then the solution S* will no longer be valid. Once more we have to generate approximate sensitivity results from the single solution S*. Form a graph G as follows:

1. Add a vertex for tank r (the tank which is to be removed from the solution) and a vertex for every other tank j with VVj < Wr.

2. Add an arc (xj|5 xh) between any two vertices /, and j2 if

and if and j2 are not in the same set Ff. Set the length chh of this arc to W(i - W)V

The above graph G is acyclic because of conditions (12.12). A path ( jq, xh, xh...., x(i) in G represents the exchange of tank r with followed by the exchange of tank r with /2, etc., until finally tank r is exchanged with tank Thus, finally tank j1 contains an amount Wr of liquid, j2 contains an amount Wh, etc., and tank r contains an amount Wit. The net amount by

Aj = + A".

(12.12)

Loading Problems

353

which the contents of tank r is reduced is therefore Wr Wjt which is the sum of the lengths of the arcs of this path as defined earlier. Thus, using the set S* of tanks only, the smallest amount or liquid that tank r must hold is at least as low as Wr = Wr L where Lr is the length of the longest path in G from vertex x,. This longest path problem is very simple and can for example be solved as a cpm problem.

If tank r is removed, it must be replaced by one or more tanks from S = E0 S*. Let Xj = 1 if j e S is one of the tanks used to replace tank r and x, = 0 otherwise.

A knapsack problem can now be defined as:

min z =

ieS

s.t. (12.13)

jeS

x,e{0, 1}.

The reduction in the value of the optimal solution caused by the removal of tank r is therefore at most (z* ur) where z* is the solution to the above knapsack problem.

12.1.6 Unloading Only

Consider the problem of unloading q', i = 1,.... N from M tanks of capacity Qj, Q2,. .., QM. Once more we will denote by E0 the set of empty tanks and by V) the set of tanks containing crude i, with a, the amount of crude contained in tank j.

There is a fundamental difference between the loading and unloading problems becausecontrary to the loading casethe unloading problem is a totally uncoupled N-stage problem which can, therefore, be decomposed into N separate one-stage problems. This is so because quantity q' must be unloaded from the tanks of V* and therefore can only change the state of these tanks which are not involved in the unloading of any other crude fc ^ i. Thus, we can consider N separate problems, the ith one being: unload q' from the set of tanks V, to maximize the value of tanks left totally empty.

Let fj(x) be the value of tanks emptied by unloading amount x from tanks 1We can then write:

fi(x)= max [/j_^(x Aaf) +AUj] (12.14)

1e(0. n

and fiv/q!) is the required maximum value of emptied tanks.

Equation (12.14) is the usual dynamic programming formulation of the one-dimensional knapsack problem (Gilmore and Gomory, 1966), and

354

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

needs no further explanation except to note that for objective (i) the recursion simplifies to the rule: unload tanks in increasing order of the amount they hold.

PART 2 DYNAMIC LOADING AND UNLOADING

12.2.1 General

A typical problem involving loading and unloading is shown diagrammati-cally in Figure 12.5. This figure will be used to explain the problem and introduce the terminology.

Crude 1

Crude 2-

Crude 3

I load;

] unload1

load1 unload1

f\ L*\

load1 L

I

unload1 !

<7)-30

?=3

10

1-2

20

I =4

40

1= 5

15

L-- 6

20

20

? =8 r 1

15 ? = 7

25

I =10

25

HO ? = 11

30

Tanks available 1

initial -

Tank / 1 12345678

**132**> 133 134 135 136 137 138 .. 156 >> Next