Краткая теория. Симплексный метод для решения задач линейного программирова­ния является универсальным, он позволяет решить любую задачу

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

Классическая транспортная задача - о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов отправления в пункты назначения.

Классическая транспортная задача (сокращенно ТЗ) формулируется следующим образом.

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

Известен транспортный тариф - стоимость перевозки единицы груза из пункта в пункт , . Требуется составить такой план перевозок груза, при котором общая стоимость F всех пе­ревозок была бы наименьшей, при этом все заявки были бы выполнены.

В термин "транспортный тариф" вкладывается условное понимание стоимости единицы груза - это может быть себестоимость, расстояние, тариф,
время, расход топлива или электроэнергии и др.

Пусть суммарные запасы грузов у поставщиков равны суммарным
потребностям потребителей:

Это условие называется условием баланса. Если для ТЗ условие баланса выполняется, то модель ТЗ называется закрытой, если условие баланса не выполнено, то модель ТЗ - открытая. Составим математическую модель ТЗ.

Пусть - количество груза, которое поставщик отправляет по­требителю () со стоимостью перевозок . Данные задачи можно представить в виде таблицы 1.

Таблица 1.

Поставщики	Потребители	Запасы
		…
			…
			…
…	…	…	…	…	…
			…
Потребности			…

По смыслу своему величины и должны удовлетворять следующим ограничениям:

· Из пункта все запасы должны быть вывезены (ограничения по ресурсам): ;

· Заявки потребителей должны быть выполнены (ограничения по потребностям): .

Затраты на перевозку единиц груза из пункта поставки в пункт потребления составляют рублей; общая же стоимость всех перевозок равна сумме всех таких затрат:

Математическая постановка ТЗ состоит в следующем:

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

,

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

Из математической модели видно, что ТЗ является частным случаем общей задачи линейного программирования. В общей теории линейного про­граммирования доказаны следующие теоремы:

Теорема 1. Транспортная задача при выполнении условия баланса всегда имеет решение.

Теорема 2. Система ограничений транспортной задачи содержит т+п-1 линейно-независимых уравнений.

При решении задач практический смысл теоремы 2 заключается в следующем: число назначенных перевозок равно т+п-1.

Процедура решения ТЗ будет состоять в последовательном улучше­нии опорных планов и проверки их на оптимальность.

Методы построения начального плана.

Существует несколько методов построения первоначального опорно­го плана ТЗ (опорный план - план, удовлетворяющий системе ограниче­ний и условию неотрицательности). Рассмотрим только два из них: метод северо-западного угла и метод наименьшей стоимости.

Как уже отмечалось, в опорном плане не более r = m + n - 1 пере­менных ,отличных от нуля. Если таких переменных равно r, то такой план называют невырожденным, в противном случае - вырожденным.

Метод северо-западного угла. Назначение перевозок начинаем с левой верхней клетки (северо-западный угол). Сравнивая ресурсы поставщика и потребности потребителя, назначаем максимально возможную перевозку. Если ресурсов поставщика недостаточно, то переходим к следующему по­ставщику. Если ресурсов у поставщика достаточно, то назначив нужную перевозку первому потребителю, переходим к следующему потребителю. При назначении перевозок для удобства записываем остаток ресурсов (по­требностей); если ресурсы закончились или потребности удовлетворены, то ставим букву "к" (конец). Если при назначении перевозки одновременно закончились запасы ресурсов у поставщика и удовлетворены потребности потребителя, то из "игры" выводим только одного участника, другому ос­тавляем нуль запасов или нуль потребностей.

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

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

Наиболее простым методом решения ТЗ является метод потенциа­лов. Потенциалами называются условные числа приписанные определенным образом каждому поставщику и потребителю.

Теорема 3(условие оптимальности плана). Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых кле­ток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток:

Замечание. Опорный план должен быть невырожденным.

Алгоритм решения транспортной задачи:

1. Строим начальные планы методом северо-западного угла и наи­меньшей стоимости, из них выбираем лучший.

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

3. Проверяем второе условие оптимальности плана для свободных клеток . Если оно выполнено, то план оптимален. Если не выполнено, то улучшаем план.

4. Улучшение плана.

a) при невыполнении второго условия оптимальности плана в клетку заносим нарушение сo знаком "+". Такие клетки называются потенциальными;

b) среди всех потенциальных клеток выбираем клетку с наибольшим нарушением;

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

d) вершины контура поочередно помечаем, знаками "+","-", начиная с клетки, для которой построен контур;

е) среди клеток, помеченных знаком "-", выбираем наименьшую перевозку. На эту величину увеличиваем перевозки в клетках, помеченных знаком "+", и уменьшаем вклетках, помеченных знаком "-". В результате переназначения перевозок освобождается одна клётка.

5.Вновь полученный план проверяем на оптимальность.