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

Исходная транспортная таблица:

Построение второй транспортной таблицы

Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 кроватей - доставим их со склада А2.

На складе А2 осталось 8 кроватей. Выделим из них пять для магазина В3. На складе А2 осталось 3 кровати. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять кроватей. Осталось 15 кроватей, столько, сколько требуется в магазин В5.

Построенный план является допустимым, так как все заявки удовлетворены, все запасы израсходованы.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1=7. Является допустимым.

Опорный план: Х11=15, Х21=5, Х22=12, Х23=5, Х24=3, Х34=5, Х35=15 . Все остальные Xij=0.

F=1*15+5*5+1*12+2*5+3*3+4*5+3*15=136

2.12.2. Метод наилучших цен

Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.

Исходная транспортная таблица:

Построение второй транспортной таблицы.

Находим в таблице наименьшую стоимость перевозки - это 0. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу). Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12. Находим следующую наименьшую по стоимости ячейку - их несколько, например,11. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17. Вычеркиваем первую строку. Выбираем ячейку 33, присваиваем ей значение 5. сумма по треьтей строке равна 15 - вычеркиваем третий столбец. Выбираем ячейку 25, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец. Выбираем ячейку 31, присваиваем ей 15. Уменьшаем первый столбец на 5 и вычеркиваем третью строку. Ячейке 21 присваиваем 2.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1=7. Является допустимым.

Опорный план построен.

Х11=3, Х12=12, Х21=2, Х24=8, Х25=15, Х31=15, Х33=5.

Все остальные Хij=0.

F=3*1+0*12+5*2+3*8+3*15+5*1=147

2.12.3. Метод потенциалов решения транспортных задач

Теперь нам надо ответить на вопрос: является ли найденный опорный план оптимальным, и если нет, то «улучшать» его.

Эту задачу решает метод потенциалов, предложенный в 1949 г. советскими учеными и .

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Общая схема отдельной итерации такова.

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

vj[k] – ui[k] Cij, i 1, ..., m; j 1, …, п.

Теоретической основой метода является теорема.

Теорема. Если для некоторого опорного плана Х = { xij} транспортной задачи можно подобрать систему из m + n чисел u1, u2, …, um, v1, v2, … vn, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия:

1. для всех xij > 0      (1)

 для всех xij = 0    (2)

для всех i = 1, …, m, j = 1, …, n

где (cij) – матрица стоимостей перевозок.

Доказательство теоремы опускаем, оно основывается на рассмотрении двойственной задачи к исходной транспортной.

Итерация метода потенциалов состоит из трех шагов.

I шаг (вычисление потенциалов).

Условие (1) представляет собой систему из ( m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.

II шаг (проверка плана на оптимальность).

Для проверки плана на оптимальность необходимо проверить условие (2), т. е. условие оптимальности для свободных клеток таблицы.

Для этого вычисляют оценки для всех свободных клеток по формулt:

Dij = ui +vj - cij

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

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

III шаг (улучшение плана).

Находят клетку таблицы, которой соответствует наибольшая положительная оценка.

max {Dij} = Dik (Dij > 0)

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

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

Перевозка загружается в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.

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

Цикл удовлетворяет следующим условиям:

· Одна ячейка пустая, все остальные занятые.

· Любые две соседние ячейки находятся в одной строке или в одном столбце.

· Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.

· Первая и последняя клетки набора лежат тоже в одной строке или столбце.

Графически цикл можно представить в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену.

Теорема.

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

Улучшение плана производится по следующей схеме. В пустых клетках находим клетку с наибольшей разностью ui + vj – cij, т. е. где условие (2) нарушается максимально.
Затем для этой клетки, согласно теореме, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке.

Затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:

· В плюсовых клетках добавляем Х.

· Из минусовых клеток вычитаем Х.

· Все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающую новое решение Х1, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

2.12.4. Решение транспортной задачи методом потенциалов.

Пример 1. Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Найти оптимальный план перевозок.

В качестве опорного плана возьмем план, полученный с помощью метода "наилучших цен".

Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5.

Все остальные элементы равны 0.

F=3*1+0*12+2*5+3*8+3*15+5*1=147

Склады	Магазины											ЗАПАС
B1	B2	B3	B4	B5
А1	1	0	3	4	2	15
3		12
А2	5	1	2	3	3	25
2			3		8		15
А3	4	8	1	4	3	20
15			5
Потребность	20	12	5	8	15

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

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

Примем u1 = 0.

c11 = u1 + v1 c12 = u1 + v2 c21 = u2 + v1 c24 = u2 + v4 c25 = u2 + v5 c31 = u3 + v1 c33 = u3 + v3

v1 = c11 – u1 = 1 – 0 = 1 v2 = c12 – u1 = 0 – 0 = 0 u2 = c21` – v1 = 5 – 1 = 4 v4 = c24 – u2 = 3 – 4 = – 1 v5 = c25 – u2 = 3 – 4 = – 1 u3 = c31 – v1 = 4 – 1 = 3 v3 = c33 – u3 = 1 – 3 = – 3

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

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

D13 = (u1 + v3) – c13 = (0 – 3) – 3 = – 6

D14 = (u1 + v4) – c14 = (0 – 1) – 4 = – 5

D15 = (u1 + v5) – c15 = (0 – 1) – 2 = – 3

D22 = (u2 + v2) – c22 = (4 + 0) – 1 = 3

D23 = (u2 + v3) – c23 = (4 – 3) – 2 = – 1

D32 = (u3 + v2) – c32 = (3 – 0) – 8 = – 5

D34 = (u3 + v4) – c34 = (3 – 1) – 4 = – 2

D35 = (u3 + v5) – c35 = (3 – 1) – 3 = –1

Среди оценок есть положительные, следовательно, решение не оптимальное.

Положительные оценки записываем в правый нижний угол – красный цвет.

Из положительных оценок выбираем максимальную. Это ячейка А2В2. Ее оценка D22 = 3.

Шаг 3. Улучшение плана.

Склады	Магазины											ЗАПАС
B1	B2	B3	B4	B5
А1	1	0	3	4	2	15
3		12
А2	5	1	2	3	3	25
2			3		8		15
А3	4	8	1	4	3	20
15			5
Потребность	20	12	5	8	15

Затем в минусовых клетках находят число X = min(Xij). = 2 Далее составляют новую таблицу по следующему правилу: