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

У двух поставщиков А 1, А 2 имеется однородный груз в количествах, соответственно равных 10 и 15 единиц. Этот груз требуется перевезти трем потребителям В1, В2 и В3 соответственно в количествах 5, 10 и 15 единиц. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана таблицей 7.2 тарифов (тысяч рублей за единицу груза). Найти решение транспортной задачи зерна из условия минимизации транс­портных расходов при дополнительных условиях: из А1 в В2 должно быть перевезено не более 2 единиц груза, из А2 в В3 – не менее 5 ед. груза, из А2 в В1 груз доставить невозможно.

Таблица 7.2 – Таблица тарифов

Пункт отправления (поставщики)	Пункт назначения (потребители)	Запасы
В 1	В 2	В 3
А1
А2
Спрос (потребности)

Решение.Данная транспортная задача открытого типа, причем запас груза у поставщиков меньше суммарного спроса потребителей. Суммарный объем запасов составляет 10 + 15 = 25 единиц, а суммарный спрос – 5 + 10 + 15 = 30 единиц, т. е. кто-то из потребителей недополучит требуемый объем груза, что учтено в ограничении на потребителей знаком ≤. Поскольку запас будет использован полностью, это учтено в ограничении на поставщиков знаком =. Через обозначено количество груза, перевозимое от i -го поставщика j -ому потребителю, , .

Математическая модель задачи содержит ограничения

и целевую функцию

.

Полученную математическую модель можно решить методом потенциалов. Поскольку данная транспортная задача открытого типа и суммарный объем запасов меньше суммарного спроса, то, чтобы свести задачу к закрытой модели, необходимо ввести фиктивного поставщика А 3. Однако данную математическую модель можно, не выполняя вручную никаких математических преобразований и не добавляя фиктивных поставщиков, решить более простым способом – с помощью надстройки Поиск решения в среде MS Excel. При этом запрет на перевозку груза из пункта А 2 в В 1 может достигаться двумя путями: 1) за счет введения стоимости перевозки единицы груза намного большей, чем стоимости остальных перевозок, например, тыс. р.; 2) за счет введения в математическую модель задачи дополнительного ограничения, устанавливающего количество перевозимого груза равным нулю: единиц. Оформление задачи на листе Excel представлено на рисунке 7.1.

В параметрах поиска решения задачи необходимо указать «Линейная модель» и «Неотрицательные значения». После нажатия кнопки «Выполнить» в окне Поиск решения будетполучен ответ (рисунок 7.2).

Рисунок 7.1 – Оформление задачи на рабочем листе Excel

Рисунок 7.2 – Решение транспортной задачи

Оптимальный план перевозки продукции с минимальными расходами по ее доставке следующий:

Таким образом, из пункта А1 в В1 перевозится 5 единиц груза, в В2 – 0 единиц, в В3 – 5 единиц; из А2 в В1 – 0 единиц, в В2 – 10 единиц, в В3 – 5 единиц. Общие минимальные транспортные расходы составят 120 тыс. р.