Or5 - The Network Simplex Method - New

THE NETWORK SIMPLEX METHOD (for THE MINIMUM COST FLOW PROBLEM) Example Example Due to SM, upper bounds lead to new

Views 111 Downloads 1 File size 744KB

Report DMCA / Copyright

DOWNLOAD FILE

Recommend stories

Citation preview

THE NETWORK SIMPLEX METHOD (for THE MINIMUM COST FLOW PROBLEM)

Example

Example

Due to SM, upper bounds lead to new identity constrains: 𝑥𝐴𝐵 + 𝑦𝐴𝐵 = 10 and 𝑥𝐶𝐸 + 𝑦𝐶𝐸 = 80

Example

General remarks (Upper Bound Technique):

• The number of basic variables is (the number of constraints)-1, because one constraint is redundant. In Example, 0=50+40+0-30-60=0. • Basic variables are 𝑥𝑝𝑞 or 𝑦𝑝𝑞 = 𝑢𝑝𝑞 − 𝑥𝑝𝑞 (if we have non-trivial capacity constraints). Only one of them is appeared explicitly in the key constraints 𝑏𝑝 = 𝑥𝑝𝑞 + ⋯ (see below). • Substituting 𝑦𝑝𝑞 = 𝑢𝑝𝑞 − 𝑥𝑝𝑞 into 𝑍 = ⋯ + 𝑐𝑝𝑞 𝑥𝑝𝑞 + ⋯ leads to 𝑍෨ = ⋯ − −𝑐𝑝𝑞 𝑦𝑝𝑞 + ⋯ with 𝑍෨ = 𝑍 − 𝑐𝑝𝑞 𝑢𝑝𝑞 . Thus we obtain – instead of +. • If 0 ≤ 𝑥𝑝𝑞 ≤ 𝑢𝑝𝑞 then obviously 0 ≤ 𝑦𝑝𝑞 ≤ 𝑢𝑝𝑞 . • Identity 𝑏𝑝 = 𝑥𝑝𝑞 + ⋯ becomes 𝑏෨𝑝 = 𝑏𝑝 − 𝑢𝑝𝑞 = −𝑦𝑝𝑞 + ⋯ • Identity 𝑏𝑞 = −𝑥𝑝𝑞 + ⋯ becomes 𝑏෨𝑞 = 𝑏𝑞 + 𝑢𝑝𝑞 = +𝑦𝑝𝑞 + ⋯

Example

The adjusted network for the example when the upper-bound technique leads to replacing 𝑥𝐴𝐵 = 10 with 𝑥𝐴𝐵 = 10 − 𝑦𝐴𝐵 .

Example Initial feasible solution can be any spanning tree solution. Its links correspond to basic variables, other links correspond to non-basic variables.

Basic variables are bold

Example

The initial feasible spanning tree and its solution for the example.

Example [general remarks on SM] • We apply the simplex method (SM): • We determine the leaving basic variable and swap it with one non-basic variable. • For this, we add one link, say [𝑝𝑞], to the current feasible solution. • This link generates an undirected cycle. • We assign the value 𝜃 to the variable 𝑥𝑝𝑞 . • Due to the key constraints 𝑏𝑝 = 𝑥𝑝𝑞 + ⋯, the value 𝜃 changes other values in the cycle. • If these changes decrease the objective function 𝑍 = ⋯ + 𝑐𝑝𝑞 𝑥𝑝𝑞 + ⋯ then non-basic 𝑥𝑝𝑞 is a candidate for the new basic variable. We compute maximal possible 𝜃 and repeat the procedure with other candidates. Then, we go to the next iteration repeating above mentioned steps.

Example

First iteration

The effect on flows of adding arc 𝐴 → 𝐶 with flow 𝜃 to the initial feasible spanning tree.

Example

First iteration

The incremental effect on costs of adding arc 𝐴 → 𝐶 with flow 𝜃 to the initial feasible spanning tree.

Example The overall increment in 𝑍:

The maximum of 𝜃:

Before computing the maximum check other candidates!

Minimum! 𝑥𝐷𝐸 is the new non-basic variable

Example

First iteration We check other links: The link 𝐴 → 𝐵

Increase 𝑍. Hence, it is not a candidate, because we want to minimize 𝑍.

Example

First iteration We check other links: The link 𝐸 → 𝐷

Increase 𝑍. Hence, it is not a candidate, because we minimize 𝑍.

Example

First iteration

The overall increment in 𝑍:

The maximum of 𝜃:

Before computing the maximum check other candidates! We found only one candidate 𝐴 → 𝐶

New basic variables:

Minimum! 𝑥𝐷𝐸 is the new non-basic variable

Example

First iteration result

Example

Second iteration

Example

Second iteration result

𝑥𝐶𝐸 is the leaving basic variable. 𝑥𝐶𝐸 = 80 = 𝑢𝐶𝐸 , hence 𝑦𝐶𝐸 = 0 is the new non-basic variable. It changes 𝑏𝐶 = −80 and 𝑏𝐸 = 20

Example

Second iteration result (with non-basic links)

The adjusted network with unit costs at the completion of iteration 2.

Example

Third iteration

Example

Third iteration result

𝑦𝐴𝐵 is the leaving basic variable. 𝑦𝐴𝐵 = 10 = 𝑢𝐵𝐴 , hence 𝑥𝐴𝐵 = 0 is the non-basic variable. It changes 𝑏𝐴 = 50 and 𝑏𝐵 = 40

Example

Third iteration result (with non-basic links)

The adjusted network with unit costs at the completion of iteration 3.

Example

Fourth iteration

We can not increase 𝑍. Hence, the solution at the completion of third iteration is optimal!

Problem1