Пример решения канонической транспортной задачи

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

Ставится задача: найти объемы перевозок так, чтобы спрос потребителей по возможности был удовлетворен, мощности поставщиков были реализованы, а суммарные затраты на перевозку были бы минимальными.

Решение

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

Для решения задачи необходимо построить первоначальное базисное решение любым способом, затем попробовать улучшить полученное решение. Построим первоначальное базисное решение методом наименьших затрат, для улучшения решения используем метод потенциалов. Число базисных переменных закрытой транспортной задачи должно быть равно (m + п — 1), где п — число поставщиков; т — число потребителей. Возможно, что число базисных переменных будет меньше, чем (m + п — 1). Мы получим вырожденное решение. В этом случае необходимо использовать искусственный прием ввода в базисное решение клеток с нулевыми поставщиками. В нашей задаче ранг матрицы равен 3 + 4 — -1 = 6.

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

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

В нашей задаче потенциалы клеток не имеют положительных значений, следовательно получено оптимальное решение. Минимальные издержки: 10−7 + 30−2 + 60−3 + 30−1 + 50 • 2 + 80 • 5 = 840. Необходимо заметить, что полученное оптимальное решение в данной задаче не является единственным.

Открытая модель оптимизации потоков

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

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

В этом случае система уравнений (4.1)-(4.2) оказывается несовместной, так как при обеспечении имеющихся потребностей в продукте часть продукта обязательно должна остаться.

в некоторых из пунктов отправления. Поэтому в рассматриваемой задаче следует равенства (4.1) заменить неравенствами.

(4.5).

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

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

Рассмотрим в качестве примера следующую задачу. Пусть имеется п строительных площадок, в каждой из которых задан объем потребностей кирпича ( штук). Для обеспечения этих потребностей следует заранее завезти по железной дороге необходимый кирпич на имеющиеся т железнодорожных станций, откуда он будет доставляться на строительные площадки автотранспортом, причем удельные стоимости перевозки кирпича этим транспортом известны и заданы табл. 4.1. На каждой из упомянутых железнодорожных станций может быть сосредоточено ограниченное количество кирпича — аi штук (в силу, скажем, ограниченности складских помещений). Общее количество необходимого кирпича меньше, чем его количество, которое можно одновременно запасти на всех станциях, т. е. меньше, чем штук. Возникает вопрос: сколько кирпича следует запасти на каждом из складов, чтобы суммарная стоимость перевозок этого кирпича от складов к строительным площадкам была минимальна?

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

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

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

В заключение покажем, что открытую модель транспортной задачи можно свести к обычной транспортной задаче (замкнутой модели). С этой целью применим следующий искусственный прием. Введем еще один (n + 1)-й пункт потребления (фиктивный), для которого положим и поставим дополнительное требование перевозки всего избыточного продукта в этот пункт. Стоимость перевозки из каждого пункта отправления в этот фиктивный пункт потребления положим равной нулю. В результате находим к разобранной транспортной задаче, в которой сбалансировано количество имеющегося продукта количеством необходимого продукта. Установим взаимно-однозначное соответствие между планами исходной задачи и получившейся в результате введения фиктивного пункта замкнутой модели. Любой план первой из них определяет количество продукта, остающееся в каждом пункте отправления. Если считать, что оно вывозится в фиктивный пункт, то приходим к плану второй задачи. Точно так же, любой план замкнутой модели определяет количество продукта, вывозимое в фиктивный пункт из каждого пункта отправления. Если считать, что его следует оставить в этих пунктах, то приходим к плану открытой модели.

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