Построение первоначального ОП ЗЛП и проверка на оптимальность

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

Имеется Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru пунктов отправления (ПО)

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

в которых сосредоточены запасы некоторого однородного груза в количестве

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

единиц соответственно.

Имеется Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru пунктов назначения (ПН)

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

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

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

единиц соответственно.

Заданы транспортные издержки (расходы) Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru связанные с перевозкой единицы продукта из ПО Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru в ПН Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

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

Составим математическую модель сформулированной задачи. Обозначим через Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru количество единиц груза, запланированное к перевозке из ПО Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru в ПН Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

Тогда условие задачи можно записать в виде таблицы, которую везде далее будем называть транспортной таблицей (табл. 10.1).

Таблица 10.1

ПО ПН Запасы
Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru
Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru
     
Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru
     
Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru   Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru
     
Потребности Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

Математическая формулировка транспортной задачи сводится к минимизации линейной функции

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

при ограничениях по запасам

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru (10.1)

а также при ограничениях по потребностям

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru (10.2)

и условиях неотрицательности

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru (10.3)

Различают транспортные задачи с закрытой моделью(закрытого типа), когда Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , и открытой моделью(открытого типа), когда Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , т. е. баланс между запасами и потребностями отсутствует.

Необходимым и достаточным условием разрешимости транспортной задачи является равенство суммарных запасов суммарным потребностям, т.е.

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

Если Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru то вводят фиктивный Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru -й пункт потребления с потребностью

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

и для транспортных издержек полагают

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

Если Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru то вводят фиктивный Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru -й пункт отправления с запасами груза

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

и для транспортных издержек полагают

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru

Математическая модель транспортной задачи относится к задачам линейного программирования и может быть решена симплекс-методом. Однако ввиду исключительной практической важности этой задачи и специфики ограничений (10.1)–(10.3):

− ограничения записаны в виде уравнений;

− каждая неизвестная входит лишь в два уравнения;

− коэффициенты при неизвестных равны единице для её решения созданы специальные алгоритмы.

Решение транспортной задачи проводится в два этапа:

1. Определение начального опорного решения – первоначальное распределение поставок.

2. Построение последовательностей итераций, улучшающих опорные планы (каждый новый план перевозок не должен увеличивать суммарные затраты).

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

10.1. Построение начального опорного плана перевозок

Начальный опорный план перевозок составляется последовательным заполнением по одной клетке в транспортной таблице так, что каждый раз либо полностью удовлетворяется потребность одного из пунктов потребления, либо полностью вывозится груз от некоторого поставщика. Доказано, что базисное решение системы ограничений, состоящей из Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru уравнений с Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru неизвестными в условиях транспортной задачи, имеет Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru базисных неизвестных, поэтому совершив Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru указанных шагов, получим первый опорный план.

Существует несколько методов определения начального опорного плана перевозок, среди которых можно выделить метод «северо-западного» угла, метод наименьшей стоимости, метод двойного предпочтения, метод аппроксимаций Фогеля.

Рассмотрим метод «северо-западного» угла (или диагональный метод). При этом методе на каждом шаге построения начального опорного плана заполняется верхняя левая клетка оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестной Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru и заканчивается в клетке неизвестной Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru т.е. идёт как бы по диагонали.

Клетки транспортной таблицы, в которых записаны отличные от нуля перевозки, называются базисными, а остальные – пустыми. Доказано, что базисное решение системы ограничений (10.1)–(10.3) в условиях транспортной задачи должно иметь Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru базисных неизвестных. План перевозок называется вырожденным, если количество базисных клеток в нём меньше, чем Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru . Если на каком-то этапе решения получился вырожденный план, его необходимо пополнить, проставив в недостающем числе клеток нуль и, тем самым, объявив их базисными. Поскольку этим дополнительным клеткам будут отвечать нулевые перевозки, общий баланс и суммарная стоимость перевозок при этом не изменятся. Однако проводить пополнение плана перевозок, выбирая клетки произвольно, нельзя. Приведём условия, которым должен соответствовать пополненный план. Для этого введём следующее понятие.

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

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

10.2. Оптимальность базисного решения. Метод потенциалов

Получив начальный опорный план перевозок, следует проверить его оптимальность и, если требуется, перейти к новому опорному плану с лучшим значением целевой функции. Для этого применяют метод потенциалов. Каждому ПО Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru и каждому ПН Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru сопоставляют соответственно величины Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru и Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru потенциалы этих пунктов ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ).

Для того чтобы некоторый опорный план транспортной задачи был оптимальным, необходимо и достаточно того, чтобы ему соответствовала система из Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru чисел Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ), удовлетворяющих условиям:

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru (10.4)

для базисных клеток ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru и

Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru (10.5)

для пустых клеток ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru .

Условия (10.4) и (10.5) называются условиями потенциальности.

Поскольку число неизвестных потенциалов Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru всегда на единицу больше числа уравнений (числа базисных клеток) Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , то какое–либо одно из системы неизвестных Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ) можно выбрать произвольно, например, равным нулю. Остальные потенциалы последовательно вычисляются из уравнений (10.4). Затем для всех свободных клеток из соотношений (10.5) определяются величины Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ( Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru ) и, если все Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru то полученный план перевозок является оптимальным. Если же имеются отрицательные Построение первоначального ОП ЗЛП и проверка на оптимальность - student2.ru , то план не оптимален и его следует оптимизировать.

Наши рекомендации