Замкнутая транспортная задача ЛП

Транспортные задачи

 

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

Для построения модели необходима следующая информация:

п — число поставщиков;

т — число потребителей;

а_i — запасы продукта (груза), имеющиеся у каждого i -го поставщика (i = 1, 2, …, n);

b_j — потребности каждого j-го потребителя (j = 1, 2, …, т) в продукте (грузе);

c_ij — затраты на транспортировку единицы груза от i-го поставщика к j-му потребителю.

В качестве управляемых переменных (переменных решения) x_ij выбирают объемы груза, доставляемого от i-го поставщика к j-му потребителю.

В зависимости от того, соблюдается условие баланса (равенства) запасов и заявок или нет, транспортные задачи классифицируют следующим образом.

1. Задачи, в которых выполняется условие баланса (предложение равно спросу):

= (7.1)

называют замкнутыми, закрытыми или сбалансированными.

2. Если запасы меньше, чем заказы:

< (7.2)

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

3. Если запасы превышают заявки:

> (7.3)

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

 

Замкнутая транспортная задача ЛП

 

На складах № 1, № 2, № 3 имеются запасы продукции в количествах 90, 400 и 110 тонн соответственно. Продукцию необходимо доставить к потребителям П1, П2, П3, заявки которых составляют 140, 300 и 160 тонн. Склады и потребители расположены в различных районах города, поэтому расстояния между каждой парой из них разные. Соответственно, транспортные расходы по перевозке товара с i-го склада к j-му потребителю также различны. Стоимость доставки единицы товара (одной тонны) от каждого склада к каждому потребителю в условных денежных единицах (у.е.) известна и представлена в табл. 7.1.

Табл. 7.1.

Склады	Потребители
П1	П2	П3
№1
№2
№3

 

Требуется составить план перевозок — определить количество груза x_ij, которое должно быть вывезено с каждого i-го склада и доставлено каждому j-му потребителю. При этом, с одной стороны, необходимо обеспечить доставку грузов всем потребителям в соответствии с их заявками, а с другой стороны, весь товар должен быть полностью вывезен со складов. План перевозок требуется составить так, чтобы совокупная стоимость транспортных издержек была минимальной.

Решение

Для формализации задачи (записи в математической форме) введем следующие обозначения:

• c_ij — удельная стоимость перевозки 1 тонны груза от склада № i к потребителю Пj:

 

=

 

• x_ij — количество груза (в тоннах), которое будет вывезено со склада № i и доставлено потребителю Пj. Тогда план перевозок можно представить в виде матрицы (таблицы) вида

 

 

• Запасы товара на складах обозначим через а_i, а потребности (заявки) потребителей — через b_j, тогда:

 

= , =

 

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

 

Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₁₃ x₁₃ + c₂₁ x₂₁ + c₂₂ x₂₂ +c₂₃ x₂₃ + c₃₁ x₃₁ + c₃₂ x₃₂ + c₃₃ x₃₃

или

Z = 2x₁₁ + 5x₁₂ + 2x₁₃ + 4x₂₁ + 1x₂₂ +5x₂₃ + 3x₃₁ + 6x₃₂ + 8x₃₃ (7.4)

 

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

 

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

 

Очевидно также, что искомые переменные (объемы перевозимого груза) должны удовлетворять условиям неотрицательности

Таким образом, получена задача линейного программирования: необходимо минимизировать целевую функцию (7.4) при условии, что на переменные наложены ограничения (7.5) - (7.7).

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

1) все ограничения заданы в виде равенств;

2) все коэффициенты при неизвестных в уравнениях системы ограничений равны 1;

3) число искомых переменных велико и всегда превышает число уравнений в системе ограничений.

Так, в данной задаче число искомых переменных равно 9 при числе ограничительных уравнений, равном 6. Последнее обстоятельство обуславливает наличие среди плана перевозок части нулевых решений (часть из х_ij всегда будет равна нулю).

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

В данной задаче запасы всех складов в сумме оказались равными заявкам потребителей (спрос равен предложению):

90 + 400 + 110 = 140 + 300 + 160 = 600.

Следовательно, это замкнутая (закрытая, сбалансированная) задача. Рассмотрим особенности ее решения в Excel (с помощью надстройки «Поиск решения»).

 

Рис. 7.1.

 

1. Исходную информацию сводят в единую таблицу № 1 и размещают на рабочем листе (рис. 7.1.).

2. Ниже основной размещают аналогичную таблицу № 2, но с пустыми ячейками С12:Е14, в которых будут вычисляться значения x_ij.

3. Вычисление целевой функции проводят в два этапа. Вначале в ячейках Н4:Н6 с помощью стандартной функции СУММПРОИЗВ из категории «Математические» вычисляют сумму попарных произведений цены перевозки единицы груза с _ij от i-го склада на количество груза x_{ij ,} поставляемого j-му потребителю. Затем в ячейке Н7 вычисляют сумму этих промежуточных расходов (рис. 7.1), т.е. значение целевой функции (7.4), которую необходимо минимизировать.

4. Для удобства записи ограничений в диалоговом окне «Поиск решения» исходные ограничения (7.5) - (7.7) записывают в несколько преобразованном виде, а именно:

 

x_i1 + x_i2 + x_i3 = a_i x_i1 + x_i2 + x_i3 – a_i = 0

x_1j + x_2j + x_3j = b_j x_1j + x_2j + x_3j – b_j = 0

 

На рабочем листе Excel в ячейках H12:H14 записывают ограничения (7.5) на количество груза, вывозимого из каждого склада; в ячейках С17:Е17 — ограничения (7.6) на количество груза, поставляемого каждому потребителю.

5. После вызова из пункта меню «Сервис» надстройки «Поиск решения» в открывшееся диалоговое окно вводят необходимую информацию (рис.7.2.).

 

Рис.7.2.

6. Результаты найденного оптимального плана перевозок получают в ячейках С12:Е14, а соответствующие ему минимальные транспортные издержки — в ячейке Н7.

Табл. 7.2.

Склады	Потребители
П1	П2	П3
№1
№2
№3

 

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