Основы математического программирования (стр. 17 )

Получаем новую таблицу.

Поставщик	Потребитель																ЗАПАС
B1	B2	B3	B4	B5
А1	7	3	5	4	2	40
		0						40
А2	6	2	3	1	7	150
		80		10		60
А3	3	5	2	6	4	100
20				80
Потребность	20	80	90	60	40

Шаг 1. Нахождение потенциалов.

Найдем потенциалы поставщиков ui и потребителей vJ,

Примем u1 = 0.

c12 = u1 + v2 c15 = u1 + v5 c22 = u2 + v2 c23 = u2 + v3 c24 = u2 + v4 c31 = u3 + v1 c33 = u3 + v3

v2 = c12 – u1 = 3 – 0 = 3 v5 = c15 – u1 = 2 – 0 = 2 u2 = c22 – v2 = 2 – 3 = –1 v3 = c23 – u2 = 3 + 1 = 4 v4 = c24 – u2 = 1 + 1 = 2 v1 = c31 – u3 = 3 + 2 = 5 u3 = c33 – v3 = 2 – 4 = –2

Шаг. 2. Проверка оптимальности.

Найдем оценки свободных ячеек следующим образом:

D11 = (u1 + v1) – c11 = (0 + 5) – 7 = – 2

D13 = (u1 + v3) – c13 = (0 + 4) – 5 = – 1

D14 = (u1 + v4) – c14 = (0 + 2) – 4 = – 2

D21 = (u2 + v1) – c21 = (– 1 + 5) – 6 = – 2

D25 = (u2 + v5) – c25 = (– 1 + 2) – 2 = – 1

D32 = (u3 + v2) – c32 = (– 2 + 3) – 5 = – 4

D34 = (u3 + v4) – c34 = (– 2 + 2) – 6 = – 6

D35 = (u3 + v5) – c35 = (– 2 + 2) – 4 = – 4

Нет положительных оценок. Найдено оптимальное решение.

X опт =		0	0	0	0	40
0	80	10	60	0
20	0	80	0	0

Smin = 2 * 40 + 2 * 80 + 3 * 10 + 1 * 60 + 3 * 20 + 2 * 80 = 550 Общие затраты на доставку всей продукции, для оптимального решения составляют 550 единиц.

2.12.5.

2.12.5.Метод распределения грузов

Один из наиболее простых способов решения транспортных задач.

Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции Z(X1).

Ранее проходили теорему о существовании и единственности цикла.

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

Согласно теореме для каждой свободной клетки можно построить единственный цикл.

Обозначив этот цикл и осуществив перераспределение грузов по циклу на величину

Q = min {xij)

«-»

получаем новое опорное решение Х2.

При переходе к новому опорному решению целевая функция изменяется следующим образом: приращение целевой функции D равно разности двух сумм:

D = ∑Сij - ∑Cij

«+» «-»

где ∑Сij - сумма стоимостей перевозок единицы груза в нечетных клетках,

«+» отмеченных знаком «+»

∑Сij - сумма стоимостей перевозок единицы груза в нечетных клетках,

«-» отмеченных знаком «-»

В клетках, отмеченных знаком «+», величины груза прибавляются, что ведет к увеличению значения целевой функции Z(X), а в клетках, отмеченных знаком «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т. е. Dlk< 0, то перераспределение величины Q по соответствующему циклу приведет к уменьшению значения Z(X), т. е. опорное решение можно улучшить.

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

Следовательно, признаком оптимальности распределительного метода является условие:

Dlk ≥ 0, " xlk = 0

Для решения транспортной задачи распределительным методом необходимо:

1. Найти начальное опорное решение.

2. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку Dlk.

3. Если оценка неотрицательна, перейти к следующей свободной клетке.

Если оценка отрицательная, то необходимо осуществить сдвиг по циклу на величину Q = min {xij). В результате получим новое опорное решение.

«-»

4. Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки.

5. Очередность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимости перевозок сij, так как решается задача на нахождение минимума.

Задача. Решить распределительным методом транспортную задачу, данные которой представлены в таблице.

bj ai	20	40	40
20	1	3	2
30	4	5	7
50	6	8	15

Решение.

1. Строим начальное опорное решение методом минимальной стоимости.

bj ai	20	40	40
20	20 1	3	2
30	4	30 5	7
50	6	10 8	40 15

2. Вычисляем значение целевой функции:

Z(X1) = 20*1 + 30*5 + 10*8 + 40*15 = 850

3. Находим цикл для свободной ячейки (1,2).

bj ai	20	40	40
20	20 1	3	0 2
30	4	30 5	7
50	6	10 8	40 15

4. Вычисляем оценку D12 = (3 + 15) – (2 + 8) == 8 > 0