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

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

Имеется пунктов отправления (ПО)

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

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

Имеется пунктов назначения (ПН)

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

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

Заданы транспортные издержки (расходы) связанные с перевозкой единицы продукта из ПО в ПН

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

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

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

Таблица 10.1

ПО	ПН	Запасы
		…
					…
					…
…	…	…	…	…	…
					…
Потребности			…

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

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

(10.1)

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

(10.2)

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

(10.3)

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

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

Если то вводят фиктивный -й пункт потребления с потребностью

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

Если то вводят фиктивный -й пункт отправления с запасами груза

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для того чтобы некоторый опорный план транспортной задачи был оптимальным, необходимо и достаточно того, чтобы ему соответствовала система из чисел ( ), удовлетворяющих условиям:

, (10.4)

для базисных клеток ( и

, (10.5)

для пустых клеток ( .

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

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