Решение транспортной задачи с промежуточными пунктами в Excel

Рассмотрим методику решения в Excel транспортной задачи с промежуточными пунктами.

Условие. Найти решение транспортной задачи с промежуточными пунктами, в рассмотренном выше примере, если стоимость перевозки единицы товара составляет: c₁₂ =3 у.е., c₂₃ =7 у.е., c₂₅ =3 у.е., c₄₃ =6 у.е., c₄₅ =4 у.е., c₄₇ =5 у.е., c₅₄ =5 у.е., c₅₆ =3 у.е., c₆₇ =5 у.е., c₇₈ =2 у.е.

На рис. 9 представлены таблицы Стоимость перевозки единицы товара и План перевозок товара между складами, сформированные на рабочем листе Excel. Здесь в таблице Стоимость перевозки единицы товара мы видим, что если между отдельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы (выделенные темным фоном) заносится любое большое число (в данном случае 100). Для того, чтобы найти в таблице Плана перевозок товара между складами объем предложения и объем спроса, определим объем буфера B по следующему правилу:

B = общий объем предложения = S₁+S₄= 10+2 = 12 ед.

или

B = общий объем спроса = D₃+D₆+D₈= 3+1+8 = 12 ед.

Для остальных промежуточных пунктов объемы предложения S_i или объемы спроса D_j равны нулю (см. рис. 9).

Рис. 9.

В целевую ячейку, в данном случае C23, необходимо занести формулу: =СУММПРОИЗВ(C4:I9;C15:I20).

Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения (см. рис. 10), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.

Рис. 10

Результат решения данной задачи представлен на рис. 11.

Рис. 11.

Здесь мы видим, что оптимальный план перевозок товара между складами следующий:

- со склада 1 товар в количестве трех единиц транзитом через склад 2 отправлен на склад 3, который является истинным пунктом назначения;

- со склада 1 товар в количестве семи единиц транзитом через склады 2 и 5 отправлен на склад 6, где одна единица товара используется для пополнения запаса на этом складе;

- со склада 6 товар в количестве шести единиц транзитом через склад 7 отправлен на склад 8, который также является истинным пунктом назначения;

- со склада 4 избыток товара в количестве четырех единиц отправлен на склад 8 транзитом через склад 7.

Стоимость перевозок при этом минимальна и составляет 149 условных денежных единиц.

Двойственность в задачах линейного программирования

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой.

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

Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Переменные двойственной задачи у_i называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

1) упорядочивается запись исходной задачи, т. е. если целевая функция задачи максимизируется, то ограничения-неравенства должны быть вида £, если минимизируется, то вида ≥. Выполнение этих условий достигается умножением соответствующих ограничений на -1;

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А^Т в двойственной задаче получаются друг из друга транспонированием.

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

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

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства, соответствует переменная, связанная с условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

Дадим экономическую интерпретацию пары двойственных задач.

Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами , которые могут использоваться для выпуска n видов продукции. Пусть также известны стоимость единицы j-го вида продукции и норма потребления i-го ресурса на производство единицы j-й продукции — а_ij.

Требуется определить объем производства продукции каждого вида , максимизирующий суммарную стоимость

При этом расход ресурсов не должен превышать их наличия:

Все неизвестные по своему экономическому смыслу неотрицательны:

По исходным данным сформулируем другую экономическую задачу (двойственную).

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

Математическая модель задачи имеет вид

Здесь z — общая оценка ресурсов. Каждое j-е ограничение из системы представляет собой неравенство, левая часть которого равна оценке всех ресурсов, расходуемых на производство единицы j-го вида продукции, а правая — стоимости единицы этой продукции.

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