Лекция 10. Нахождение оптимального решения транспортной задачи

План

1. Метод потенциалов и его алгоритм.

2. Практические способы реализации метода потенциалов.

1. Для решения транспортной задачи удобно использовать метод потенциалов.

Теорема (оптимальности решения транспортной задачи). Решение

u

i

транспортной задачи будет оптимальным, если найдутся такие числа *

v

j

(i =1, m) и

* (j =1, n), называемые соответственно потенциалами поставщи-

ков и потребителей, которые будут удовлетворять условиям:

j

i

u * + v *

* *

= cij

для

xij

*

*

> 0;

ui + v j

≤ cij

для

xij

= 0.

Потенциалы – это двойственные оценки исходной транспортной задачи

(1)-(3) (см. предыдущую лекцию). Здесь ui

(i =1, m) – оценка единицы запаса

(потенциал поставщика), v j

(j =1, n)– оценка единицы спроса (потенциал по-

требителя). Потенциалы могут быть числами любого знака.

Метод потенциалов является разновидностью симплекс-метода. Он при- меним и для решения задач, не являющихся транспортными. Эти задачи долж- ны записываться таблицами транспортного типа. Например, задача о назначе- нии специалистов или задача о закреплении земельных участков под посев.

Приведём алгоритм решения закрытой транспортной задачи методом по-

тенциалов.

1) Составляем начальный опорный план методом минимальной стоимо-

сти. Рассчитываем значение целевой функции.

2) Проверяем опорный план на оптимальность следующими действиями.

2.1) Используя заполненные клетки транспортной таблицы, рассчитаем

потенциалы по формуле ui + v j = cij, полагая u 1 = 0.

2.2) В незаполненные клетки помещаем оценки оптимальности

δ ij = ui + v j − cij. Если для всех незаполненных клеток

δ ij ≤ 0, то опорный план

является оптимальным и алгоритм завершается вычислением минимального значения целевой функции. Если найдётся хотя бы одна незаполненная клетка с

δ ij > 0, то алгоритм продолжается.

2.3) Клетку с наибольшей положительной оценкой

δ ij

считают перспек-

тивной. К перспективной клетке строится цикл. Перспективной клетке соот-

ветствует величина перераспределения груза

+ρ. В остальных вершинах

цикла знаки чередуются

−ρ, +ρ

и т.д. Величину перераспределения вычисля-

ем по формуле

ρ = min xij, где

xij

– объёмы перевозки, записанные в вершинах

цикла и отмеченные

−ρ, т.е. уменьшаемые объёмы перевозок.

2.4) Перераспределяем груз в объёме ρ по циклу. Получаем новый опор-

ный план. Проверяем его на оптимальность, т.е. переходим к пункту 2.1) алго-

ритма.

Замечание. После нахождения оптимального плана рассуждают следую-

щим образом. Если все оценки незаполненных клеток

план единственный. Если же для некоторых из них

δ ij < 0, то оптимальный

δ ij = 0, то оптимальный

план не единственный. Можно найти другие оптимальные планы, перераспре- деляя груз по циклу в эти клетки. При этом общая стоимость перевозки не из- менится и останется минимальной.

Пусть транспортная задача имеет k оптимальных планов

X 1, X 2,..., X k.

Тогда общее оптимальное решение можно записать в виде выпуклой линейной комбинации этих планов, т.е.

*

Х = λ1 Х 1 + λ2 Х 2 +... + λ k Хk,

где

λ1 + λ2 +... + λ k

=1,

λ1 ≥ 0,λ2 ≥ 0,...,λ k

≥ 0.

При наличии двух оптимальных планов пользуются записью:

*

где 0 ≤ λ ≤1.

Х = λ Х 1 + (1− λ) Х 2,

2. Применим описанный алгоритм к решению конкретной транспортной задачи.

Пример 1. Табл. 1 (см. предыдущую лекцию) содержит запасы постав-

щиков (т), потребности потребителей (т) и тарифы перевозок единицы товара

(тыс. грн.). Требуется решить транспортную задачу.

Табл. 1. Условие транспортной задачи

b j 15 15 16 18

ai

4 1 2 1

20

4 6 3 2

5 2 1 4

Решение. Вводим фиктивного поставщика (табл. 2).

Табл. 2. Транспортная таблица с фиктивным поставщиком

b j 15 15 16 18

ai

4 1 2 1

4 6 3 2

5 2 1 4

0 0 0 0

Применим алгоритм метода потенциалов.

1) Составляем начальный опорный план методом минимальной стоимо-

сти (табл. 3). Рассчитываем значение целевой функции.

Табл. 3. Начальный опорный план

b j 15 15 16 18

ai

4 1 2 1

20 15 5

4 6 3 2

30 1 16 13

5 2 1 4

10 10

4 4

0 0 0 0

Итак,

⎛ 0 15 0 5 ⎞

⎜ 1 0 16 13 ⎟

X = ⎜ ⎟

1 ⎜10 0 0 0 ⎟

⎝ ⎠

⎜ 4 0 0 0 ⎟

и Z (X 1) = 148

(тыс. грн.).

2) Проверяем опорный план

X 1 на оптимальность.

2.1) Используя заполненные клетки табл. 3, рассчитываем потенциалы по

формуле ui + v j = cij, полагая u 1 = 0:

⎪

⎧ u 1 + v 2 =1, u 1 = 0 ⇒ v 2 =1

⎪ u 1 + v 4 =1 ⇒ v 4 =1

⎪ u 2+ v 4 = 2 ⇒ u 2 =1

⎪

⎨ u 2+ v 1 = 4 ⇒ v 1 = 3

⎪ u + v = 3 ⇒ v = 2

⎪ 2 3 3

⎩ u 4 1 4

⎪ u 3+ v 1 = 5 ⇒ u 3 = 2

⎪ + v = 0 ⇒ u = −3

Добавляем в табл. 3 строку и столбец, и записываем в них потенциалы

(табл. 4).

2.2) В незаполненные клетки табл. 4 помещаем оценки оптимальности

δ ij = ui + v j − cij, выделяя их квадратными скобками. Т.к. имеются незаполнен-

ные клетки с δ ij > 0, то алгоритм продолжается.

Табл. 4. Начальный опорный план с потенциалами

b j 15 15 16 18

ai

4 1 2 1

ui

u 1 = 0

20 [–1] 15 [0] 5

4 6 3 2

30 1 [–4] 16 13

5 2 1 4

10 10 [1] [3] [–1]

0 0 0 0

4 4 [–2] [–1] [–2]

u 2 =1

u 3 = 2

u 4 = −3

v j v 1 = 3

v 2 =1

v 3 = 2

v 4 =1

2.3) Клетка (3,3) с наибольшей положительной оценкой перспективной. К перспективной клетке строится цикл (рис. 1):

[(3,3); (3,1); (2,1); (2,3); (3,3)].

δ33 = 3

является

1 + ρ

16 − ρ

10 − ρ +ρ

Рис. 1. Цикл перераспределения груза

Циклом, или замкнутым контуром, называется последовательность клеток таблицы, соединённых замкнутой ломаной линией без самопересечений. Количество вершин в цикле всегда чётно и повороты линий производятся толь- ко под прямым углом.

Для нашего цикла

ρ = min{10,16} =10.

2.4) Перераспределяем груз в объёме вый опорный план:

ρ =10

(т) по циклу. Получаем но-

⎛ 0 15 0 5 ⎞

⎜11 0 6 13 ⎟

X = ⎜ ⎟.

2 ⎜ 0 0 10 0 ⎟

⎝ ⎠

⎜ 4 0 0 0 ⎟

Теперь

Z (X 2) =118

(тыс. грн.).

Проверяем опорный план

X 2 на оптимальность, т.е. переходим к пункту

2.1) алгоритма. Считаем потенциалы и заносим в табл. 5. В незаполненные клетки помещаем оценки оптимальности.

Табл. 5. Второй опорный план с потенциалами

b j 15 15 16 18

ai

4 1 2 1

ui

u 1 = 0

20 [–1] 15 [0] 5

4 6 3 2

30 11 [–4] 6 13

5 2 1 4

10 [–3] [–2] 10 [–4]

0 0 0 0

4 4 [–2] [–1] [–2]

u 2 =1

u 3 = −1

u 4 = −3

v j v 1 = 3

v 2 =1

v 3 = 2

v 4 =1

Т.к. для всех незаполненных клеток δ ij ≤ 0, то опорный план

X 2 является

оптимальным и

Z min =118

(тыс. грн.).

Незаполненная клетка (1,3) имеет оценку оптимальности δ ij = 0. Поэтому

оптимальный план

X 2 не единственный. К этой клетке строится цикл: [(1,3); (1,4); (2,4); (2,3); (1,3)].

Перераспределяем груз в объёме

новый оптимальный план

ρ = min{5, 6} = 5

(т) по циклу. Получаем

для которого

Z min =118

⎛ 0 15 5 0 ⎞

⎜11 0 1 18 ⎟

X = ⎜ ⎟,

3 ⎜ 0 0 10 0 ⎟

⎝ ⎠

⎜ 4 0 0 0 ⎟

(тыс. грн.).

на:

Удаляем из задачи фиктивного поставщика. Имеем два оптимальных пла-

⎛ 0 15 0 5 ⎞

X * = ⎜11 0 6 13 ⎟;

⎛ 0 15 5 0 ⎞

X * = ⎜11 0 1 18 ⎟.

⎝ ⎠

1 ⎜ ⎟

⎜ 0 0 10 0 ⎟

2 ⎜ ⎟

⎝ ⎠

⎜ 0 0 10 0 ⎟

Общее оптимальное решение:

⎛ 0 15 5 − 5λ

5λ ⎞

Х * = λ Х * + (1 − λ) Х

* = ⎜11 0 1 + 5λ

18 − 5λ ⎟,

1 2 ⎜ ⎟

⎜ 0 0 10 0 ⎟

где 0 ≤ λ ≤1. Причём

Z min =118

⎝ ⎠

(тыс. грн.).

Дата добавления: 2014-01-07