Проверка плана на оптимальность. Метод потенциалов

Определение первоначального опорного плана фактически соответствует выбору начального базисного решения задачи линейного программирования при использовании симплексного метода. Количество заполненных клеток равно n+m-1.

После определения первоначального опорного плана выполняем следующий этап решения транспортной задачи. Каждой строке матрицы поставок назначим потенциал U_i (i=1…m), каждому столбцу матрицы поставок назначим потенциал V_j (j=1…n). Потенциалы назначаются таким образом, чтобы для заполненных клеток таблицы выполнялись равенства:

(3.5)

В теории исследования операций показано, что суммы соответствует коэффициентам при переменных x_ij в выражении целевой функции. Эти суммы также называют оценками клеток.

Система (3.5) является системой из (n+m-1) линейно независимых уравнений относительно (n+m) неизвестных потенциалов. Значение одного из потенциалов может быть выбрано произвольным образом, тогда остальные будут определены однозначно. Можно показать, что оценки клеток не зависят от произвола в выборе первого потенциала.

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

Для нового опорного плана вновь вычисляются оценки клеток и, при необходимости выполняется новая передача поставки. Критерием оптимальности полученного решения является неотрицательность оценок всех клеток таблицы поставок.

Пример 14. Пусть имеется первоначальный опорный план, полученный методом наименьших затрат:

	Потребители	МЗ 1	МЗ 2	МЗ 3
Поставщики	Мощности
Ферма 1
Ферма 2
Ферма 3

Составим систему уравнений, соответствующую системе (3.5):

(3.6)

Пусть U₁=0. Из первого уравнения системы (3.6) следует, что V₃= – 4. Следовательно, из последнего уравнения системы получим U₃=0. Далее из четвертого уравнения следует, что V₂= – 6. Решая третье уравнение, получаем V₁= – 5. И, наконец, из второго уравнения определяем, что U₂=2.

Удобно записывать потенциалы строк и столбцов непосредственно в таблице (в дополнительном столбце и дополнительной строке), указывая в скобках номер шага в решении системы:

	Потребители	МЗ 1	МЗ 2	МЗ 3	Потенциалы строк
Поставщики	Мощности				Ui (i=1, 2, 3)
Ферма 1					0 (1)
Ферма 2					2 (6)
Ферма 3					0 (3)
Потенциалы столбцов Vj (j=1, 2, 3)	-5 (5)	-6 (4)	-4 (2)

Вычислим оценки клеток, запишем их во вспомогательную таблицу:

	-1

Клетка (1,2) имеет отрицательную оценку -1. Следовательно, включив в план поставок клетку (1,2) и организовав перевозку x₁₂ единиц продукции по соответствующему маршруту, получим изменение значения целевой функции на величину (-1)× x_{1 2}. Определим величину передаваемой поставки. Введем следующие понятия.

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

Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, остальные – в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «–» так, что в свободной клетке стоит «+», а любые две соседние вершины имеют разные знаки.

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

Поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком «–». Для перехода к новому базисному решению в клетках со знаком «+» следует увеличить значения поставок на величину поставки, передаваемой по циклу, а в клетках со знаком «–» уменьшить на ту же величину.

Для нашего примера в цикл пересчета будут включены клетки (1,2), (1,3), (3,2), (3,3). Расставим знаки в клетках-вершинах цикла:

	Потребители	МЗ 1	МЗ 2	МЗ
Поставщики	Мощности
Ферма 1			5 +	4 –
Ферма 2
Ферма 3			6 –	4 +

Величина поставки, передаваемой по циклу, равна min(80, 100) = 80. Определяем новое базисное распределение поставок и определяем потенциалы строк и столбцов:

	Потребители	МЗ 1	МЗ 2	МЗ 3	Потенциалы строк
Поставщики	Мощности				Ui (i=1, 2, 3)
Ферма 1					0 (1)
Ферма 2					2 (5)
Ферма 3					0 (3)
Потенциалы столбцов Vj (j=1, 2, 3)	-5 (4)	-5 (6)	-4 (2)

Вычислим оценки клеток, запишем их во вспомогательную таблицу:

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

F=1300+(–1)∙80=1220.

Замечание 1. Поставка, передаваемая по циклу, не может быть меньше минимума поставок в клетках цикла со знаком «–». Если она будет меньше указанного минимума, то ни одна из клеток цикла не будет иметь нулевой поставки, а, следовательно, число заполненных клеток станет равным n+m и решение не будет базисным.

Замечание 2. Поставка, передаваемая по циклу, не может быть больше минимума поставок в клетках цикла со знаком «–». Если она будет больше указанного минимума, то решение становится недопустимым.

Замечание 3. Если минимум поставок клеток цикла со знаком «–» одновременно достигается в нескольких клетках, то после передачи поставки по циклу сразу в нескольких клетках получаем нулевую поставку. Для того чтобы решение оставалось базисным, число заполненных клеток должно оставаться равным n+m –1. Поэтому только одну из освободившихся клеток считаем свободной, а в остальных необходимо поставить нулевые поставки, т.е. считать эти клетки заполненными значением 0. Подобное решение является вырожденным, оно уже рассматривалось в задачах линейного программирования.

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

Тема 4. Задачи динамического программирования

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