Транспортная задача с избытком

 

Решение

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

• cij – удельная стоимость перевозки 1 тонны груза от склада № i к

потребителю Пj

С₁₁        С₁₂        С₁₃            2     5     2         

С₂₁        С₂₂        С₂₃    =    4     1      5

С₃₁        С₃₂        С₃₃            3     6      8

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

X₁₁     X₁₂     X₁₃

X₂₁     X₂₂     X₂₃

X₃₁     X₃₂     X₃₃

• Запасы товара на складах обозначим через a i , а потребности (заявки) потребителей через b j , тогда

     a₁            90           b₁          140

     а₂     =    400   ,     b₂  =    300     .

     а₃           110         b₃        160

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

Z = c11 ⋅ x11 + c12 ⋅ x12 + c13 ⋅ x13 + c 21 ⋅ x 21 + c 22 ⋅ x 22 + c 23 ⋅ x 23 +

+ c31 ⋅ x 31 + c32 ⋅ x 32 + c33 ⋅ x 33

или

Z = 2 ⋅ x11 + 5 ⋅ x12 + 2 ⋅ x13 + 4 ⋅ x 21 + 1 ⋅ x 22 + 5 ⋅ x 23 + 3 ⋅ x 31 + 6 ⋅ x 32 + 8 ⋅ x 33

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

 x₁₁+ x₁₂+ x₁₃= a₁,                                            x₁₁+ x₁₂+ x₁₃= 90,                     

x₂₁+ x₂₂+ x₂₃= a₂ ,          или                                    x₂₁+ x₂₂ + x₂₃= 400,

 x₃₁+ x₃₂+ x₃₃=a₃,                                              x₃₁+ x₃₂+ x₃₃=110.

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

x₁₁+ x₂₁+ x₃₁=b₁,                               x₁₁+x₂₁+x₃₁=140,                 

x₁₂+ x₂₂+ x₃₂=b₂  ,         или              x₁₂+x₂₂+x₃₂=300,

x₁₃+ x₂₃+ x₃₃=b₃,                               x₁₃+x₂₃+x₃₃=160.

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

x ij ≥ 0 (i = 1,2,3; j = 1,2,3) .

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

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

    Для решения транспортных задач используют как стандартные методы линейного программирования (симплекс метод), так и специальные вычислительные алгоритмы – [1, 4, 5, 10]. Последние более эффективны с вычислительной точки зрения. [6]

2.6.4 Пример решения в Excel

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

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

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

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

2. Ниже основной размещают  аналогичную таблицу (№ 2), но с пустыми ячейками C12:E14, в которых будут вычисляться значения x ij .

3. Вычисление целевой  функции проводят в два этапа.  Вначале в ячейках H4:H6 с помощью стандартной функции СУММПРОИЗВ из категории Математические вычисляют сумму попарных произведений цены перевозки единицы груза cij от i-го склада на количество груза x ij , поставляемого j-му потребителю. Затем в ячейке H7 вычисляют сумму этих промежуточных расходов, т.е. значение целевой функции, которую необходимо минимизировать.

Рис. 1.1. Табличное представление задачи в Excel.

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

x i1 + x i2 + x i3 = a i ⇒ x i1 + x i2 + x i3 − a i = 0

x1 j + x 2 j + x 3 j = b j ⇒ x1 j + x 2 j + x 3 j − b j = 0

На рабочем листе Excel в  ячейках H12:H14 записывают ограничения на количество груза, вывозимого из каждого склада. В ячейках C17:E17 - ограничения на количество груза, поставляемого каждому потребителю.

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

6. Результаты найденного  оптимального плана перевозок получают в ячейках C12:E14, а соответствующие ему минимальные транспортные издержки в ячейке H7.

Рис. 1.2. Окно «Поиска решения».

Рис. 1.3. Найденное оптимальное решение.

 

Склады	Потребители
	П1	П2	П3
Склад№1	0	0	90
Склад№2	30	300	70
Склад №3	110	0	0

                                     Таблица 1.2.  Оптимальный план перевозок –       объемы груза, вывозимого из i-го склада и доставляемого j-му потребителю, представлен в табл. 7.2. Минимальные транспортные издержки составят 1280 у.д.е. [1]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Практическая часть

3.1 Незамкнутая транспортная задача с избытком

Компания, занимающаяся добычей  песка и доставкой его собственным  транспортом к потребителям, разрабатывает 4 песчаных карьера. Недельная производительность карьера 210, 170, 270 и 360 тонн. Песок направляется на три завода железобетонных изделий (ЖБИ). Недельные потребности заводов в песке составляют 300, 290 и 320 тонн. Транспортные затраты, связанные с доставкой 1 тонн песка от карьеров до заводов, известны и приведены в таблице.

Песчаные карьеры	Заводы ЖБИ			Производительность карьеров (предложение)
	№1	№2	№3
1	9	5	7	210
2	7	6	8	170
3	6	7	8	270
4	5	4	7	360
Потребности заводов (спрос)	300	290	320	Предложение превышает спрос  на 100 т: 1010>910

Требуется:

1. Составить такой план перевозок песка из карьеров на заводы, при котором совокупные транспортные издержки будут минимальны;
2. Выяснить, какое количество песка и на каких карьерах окажется невостребованным;
3. Установить размер минимальных транспортных издержек.

 

Решение:

Потребности заводов в  песке (спрос) составляют 300+290+320=910 т, в  то время как мощности карьеров позволяют  добывать 210+170+270+360=1010 т. Предложение  превышает спрос на 100 т. Следовательно, эта задача незамкнутая.

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

Таблица №1

Песчаные карьеры Предложение	Заводы ЖБИ Потребности заводов (спрос)				Vi
	№1 300	№2 290	№3 320	№4 100
210	9  -      210	5  +	7	0	-2
170	7 +       90	6     -      80	8	0	0
270	6	7      210	8       60	0	-1
360	5	4	7       260	0                    100	0
Vj	7	6	7	0

 

Обозначим через x ij – количество песка (тонн), которое будет вывезено из карьера i (i= 1,2,3,4) и доставлено на завод j (j=1,2,3,4). Тогда искомый план перевозок, представленный в табл. №1, состоит из 16 управляемых переменных.

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

После заполнения таблицы проверяем правило «количество сплошных линий равно количество поставщиков + количество потребителей - 1», т.е 4+4-1=7.

Проверяем план на оптимальность для этого вводим потенциалы Vi,Vj и рассчитываем:

           (-2+9-7) (-2+5-6) (-2+7-7) (-2+0-0)

dij=  (0+7-7) (0+6-6) (0+8-7) (0+0-0)

          (-1+6-7) (-1+7-6) (-1+8-7) (-1+0-0)

           (0+5-7) (0+4-6) (0+7-7) (0+0-0)

          0   -3   -2   -2

dig=   0    0    1    0

          -2    0   0    -1

          -2   -2    0     0

Т.к матрица содержит отрицательные  числа (выбираем самое минимальное  число), то распределение не оптимально, тогда строим контур перераспределения  для клетки с наименьшей отрицательной  оценкой 

Min(210;80)=80

Совокупные транспортные издержки на перевозку составят:

Fmin= 9*210+7*90+6*80+7*210+8*60+7*260+0*100=6770

Заметим, что введение фиктивного потребителя с нулевыми стоимостями  перевозок никак не влияет на целевую  функцию в силу того, что коэффициенты при x14 , x 24 , x 34 , x 44 равны нулю.

Таблица 2

Песчаные карьеры Предложение	Заводы ЖБИ Потребности заводов (спрос)				Vi
	№1 300	№2 290	№3 320	№4 100
210	9   _      130	5    +         80	7	0	0
170	7       170	6	8	0	2
270	6       +	7     _      210	8       60	0	-2
360	5	4	7 260	0                         100	-1
Vj	9	5	6	-1