Решение транспортной задачи в Excel

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

 

Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

 

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

 

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

 

Для решения таких задач Excel имеет специальный инструмент «Поиск решения». Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи.

 

Для добавления надстройки «Поиск решения», если на вкладке «Данные» этого пункта нет перейдите: Файл — Параметры. Слева выберите меню «Надстройки». В основной части выделите «Поиск решения». Затем ниже, нажмите «Перейти». В открывшемся окне отметьте пункт «Поиск решения» и нажмите «Ok». Во вкладке «Данные» появился соответствующий одноименный пункт.

 

Общее условие транспортной задачи:

 

Найти m*n неотрицательных чисел Xij– объем перевозок от i-ого поставщика к j-ому потребителю, минимизирующих транспортные затраты по перевозке однородных грузов поставщиков с мощностями (запасами) А1,А2…Ам к потребителям с потребностями В12…Вn, если известны матрица издержек Сij – издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

 

Математическая постановка задачи:

 

Целевая функция

Z=\sum_{i=1}^{m}\sum_{j=1}^{n}C_{ij}X_{ij}

 

Ограничения

\sum_{j=1}^{n} X_{ij} = A     для i=1,2….m

 

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

\sum_{i=1}^{m} X_{ij} = Bj    для j=1,2….n

 

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

 

Пример задачи и ее решения в Ms Excel.

 

Условие: 

 

Дано 5 производителей А1, А2, А3, А4, А5, мощность (запасы) которых соответственно равна(равны): 20, 45, 25, 30,20.

И четыре потребителя В1, В2, В3, В4, потребность которых в продукте составляет соответственно: 45, 50, 20, 25.

Также известна матрица издержек  Сij – издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

Ее можно представить таблицей:

12 9 10 4
4 7 7 6
7 11 5 8
9 6 9 9
10 11 6 5

 

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

Ai      Bj 45 50 20 25
 20 12 9 10 4
45 4 7 7 6
25 7 11 5 8
30 9 6 9 9
20 10 11 6 5

 

 

Решение:

 

В интервал ячеек A2:A6  ввести запасы поставщиков — Ai:

tr_ex_z-1

 

В интервал ячеек B1:E1 ввести количество необходимого груза  Bj–го потребителя:

tr_ex_z-2

 

Для дальнейшего удобства выделим ячейки различными цветами и установим жирную границу:

tr_ex_z-3

 

В интервал ячеек B2:E6 ввести матрицу Cij издержек перевозки единицы груза от i-ого поставщика к j-ому потребителю:

tr_ex_z-4

 

В ячейку Н1 введите формулу:     СУММAПРОИЗВ(В2:E6;B9:E13

tr_ex_z-5

 

В ячейку A9 введите формулу СУММ(B9:F9) и растяните её до А13 (как растянуть формулу см. тут —> Тыц) :

tr_ex_z-6

 

В ячейку B8  введите формулу СУММ(B9:B13) и скопируйте ее в диапазон от B8 до E8:

tr_ex_z-7

 

Для решения задачи на панели вкладок выберите вкладку «Данные», а затем «Поиск решения»:

tr_ex_z-8

 

Заполните открывшееся окно в соответствие с рисунком и нажмите Найти решение:

tr_ex_z-9

 

 

В диапазоне B9:E13 Вы получите результат решения транспортной задачи (т.е. значение в ячейке соответствует количеству груза перевезенного от i-ого поставщика к j-ому потребителю).

 

В диапазоне A9:A13 количество груза, которое необходимо вывезти от поставщиков.

 

В диапазоне B8:E8 количество которое будет доставлено потребителям согласно найденному решению.

 

В ячейке H1 значение целевой функции при найденном решении (минимально возможное). Это значение получено в результате умножения стоимости перевозки от от i-ого поставщика к j-ому потребителю на количество единиц груза, которые необходимо перевезти между ними.

 

Оформим  полученный результат и получим следующее:

tr_ex_z-10

 

 

Скачать файл, созданный в процессе прохождения урока Вы можете по тут —> Transportation_problem

 

comments powered by HyperComments