Открытая транспортная задача

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

Пример 1. Поставщики А_i имеют грузы в 100, 400, 100, 100 единиц. Потребители В_j запрашивают грузы в 50, 100. 150, 200. 250 единиц. Матрица стоимости перевозок имеет вид

Составить оптимальный план перевозок с наименьшей общей стоимостью.

Решение. Найдем суммы грузов у поставщиков и потребителей.

700 ед.; 750 ед. Следовательно, задача открытая. Разность в суммах грузов 50 ед. Вводим ложного поставщика, у которого как бы имеется 50 единиц недостающих грузов, а стоимость перевозок от него предполагаем равной нулю.

Первоначальный опорный план строим по методу двойного предпочтения. Затем находим значения потенциалов и проверяем план на оптимальность.

Оптимальность нарушается в клетке А₃В₅. Строим цикл и «перевозим» 100 единиц груза по данному циклу. Получаем следующий опорный план:

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

К сожалению, пятому потребителю мы пока не имеем возможности доставить 50 единиц груза.

Стоимость перевозок по данному плану 5 450 у.д.е.

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

Пример 2. Поставщики А_i, имеют грузы в 74, 40, 36 единиц. Потребители В_j, запрашивают 20, 45, 30 единиц соответственно. Матрица стоимостей перевозок имеет вид:

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

Решение. 150 ед.; 95. Следовательно, задача является открытой. Вводим «фиктивного потребителя» на лишний груз B₅. Обязательное требование задачи будет учтено, если мы исключим из рассмотрения клетку А₂В₅.

Строим таблицу и проверяем план на оптимальность.

Данный план перевозок является оптимальным. У первого поставщика останется 29 условных единиц груза, у третьего - 26. Стоимость перевозок равна 245 у.д.е.

Пример 3. У поставщиков имеются грузы в объемах 46, 34, 30 ед. Потребители запрашивают 40, 35, 30, 45 единиц соответственно. Найти оптимальный план перевозок при условии, что первый пункт потребления должен быть удовлетворен полностью. Матрица стоимостей перевозок имеет вид

Решение. 120 ед.; 150. Следовательно, задача открытая. Лишние грузы запрашивает потребитель. Поэтому вводим «фиктивного поставщика» с запасом грузов 150 - 120 = 30 и стоимостью перевозок 0.

Строим таблицу, выводя из процесса загрузки клетку А₄B₁ и учитывая, что первый потребитель должен получить весь запрашиваемый груз.

По методу двойного предпочтения строим первоначальный опорный план и систему потенциалов, начиная с U₂. Видим, что условие оптимальности нарушено в клетке А₂В₂. Строим цикл и «перевозим» по нему 19 ед. груза.

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

Данный план оптимален. Стоимость перевозок поэтому плану 277 у.д.е. Недопоставки четвертому потребителю составляют 30 единиц груза.