«решение транспортных задач в электронных таблицах excel»

Методы оптимальных решений. Транспортная задача в MS Excel

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

Есть некие предприятия и склады с грузом. Каждое предприятие, нуждается в определённом объёме нашего груза. Каждый склад доставляет тонну груза по собственному тарифу. Таким образом, нужно составить маршрут, по которому мы развезём объём груза, удовлетворяющий каждое предприятие, и при этом затратим меньше всего средств.

Так транспортная задача выглядит в своём наиболее общем и типовом виде.

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

Предприятия А1, А2, А3 и А4 производят однородную продукцию а1, а2, а3 и а4, соответственно. В условных единицах – 246, 186, 196 и 197. Затем товар поступает в пять пунктов назначения: В1, В2, В3, В4 и В5. Это потребители продукции. Они готовы ежедневно принимать 136, 171, 71, 261 и 186 единиц товара.

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

Производители Потребители Объем производства
В1 В2 В3 В4 В5
А1 4,2 4 3,35 5 4,65 246
А2 4 3,85 3,5 4,9 4,55 186
А3 4,75 3,5 3,4 4,5 4,4 196
А4 5 3 3,1 5,1 4,4 197
Объем потребления 136 171 71 261 186

Задача: минимизировать транспортные расходы по перевозке продукции.

  1. Проверим, является ли модель транспортной задачи сбалансированной. Для этого все количество производимого товара сравним с суммарным объемом потребности в продукции: 246 + 186 + 196 + 197 = 136 + 171 + 71 + 261 + 186. Вывод – модель сбалансированная.
  2. Сформулируем ограничения: объем перевозимой продукции не может быть отрицательным и весь товар должен быть доставлен к пунктам назначения (т.к. модель сбалансированная).
  3. Введем стоимость перевозки единицы продукции в рабочие ячейки Excel.
  4. Введем формулы для расчета суммарной потребности в товаре. Это будет первое ограничение.
  5. Введем формулы для расчета суммарного объема производства. Это будет второе ограничение.
  6. Вносим известные значения потребности в товаре и объема производства.
  7. Вводим формулу целевой функции СУММПРОИЗВ(B3:F6; B9:F12), где первый массив (B3:F6) – стоимость единицы перевозки товаров. Второй (B9:F12) – искомые значения транспортных расходов.
  8. Вызываем команду «Поиск решения» на закладке «Данные» (если там нет данного инструмента, то его нужно подключить в настройках Excel, а как это сделать описано в статье: ). Заполняем диалоговое окно. В графе «Установить целевую ячейку» — ссылка на целевую функцию. Ставим галочку «Равной минимальному значению». В поле «Изменяя ячейки» — массив искомых критериев. В поле «Ограничения»: искомый массив >=0, целые числа; «ограничение 1» = объему потребностей; «ограничение 2» = объему производства.
  9. Нажимаем «Выполнить». Команда подберет оптимальные переменные при заданных ограничениях.

Так выглядит «сырой» вариант работы инструмента. Экспериментируя с полученными данными, находим подходящие значения.

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

Теперь давайте разберем конкретный пример решения транспортной задачи.

Условия задачи

Имеем 5 поставщиков и 6 покупателей. Объёмы производства этих поставщиков составляют 48, 65, 51, 61, 53 единиц. Потребность покупателей: 43, 47, 42, 46, 41, 59 единиц. Таким образом, общий объем предложения равен величине спроса, то есть, мы имеем дело с закрытой транспортной задачей.

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

Решение задачи

Перед нами стоит задача при условиях, о которых было сказано выше, свести транспортные расходы к минимуму.

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

Выделяем любую пустую ячейку на листе. Кликаем по значку «Вставить функцию», размещенному слева от строки формул.

Открывается «Мастер функций». В списке, который предлагает он, нам следует отыскать функцию СУММПРОИЗВ. Выделяем её и жмем на кнопку «OK».

Открывается окно ввода аргументов функции СУММПРОИЗВ. В качестве первого аргумента внесем диапазон ячеек матрицы затрат. Для этого достаточно выделить курсором данные ячейки. Вторым аргументом выступит диапазон ячеек таблицы, которая была приготовлена для расчетов. Затем, жмем на кнопку «OK».

Кликаем по ячейке, которая расположена слева от верхней левой ячейки таблицы для расчетов. Как и в прошлый раз вызываем Мастер функций, открываем в нём аргументы функции СУММ. Кликнув по полю первого аргумента, выделяем весь верхний ряд ячеек таблицы для расчетов. После того, как их координаты занесены в соответствующее поле, кликаем по кнопке «OK».

Становимся в нижний правый угол ячейки с функцией СУММ. Появляется маркер заполнения. Жмем на левую кнопку мыши и тянем маркер заполнения вниз до конца таблицы для расчета. Таким образом мы скопировали формулу.

Кликаем по ячейке размещенной сверху от верхней левой ячейки таблицы для расчетов. Как и в предыдущий раз вызываем функцию СУММ, но на этот раз в качестве аргумента используем первый столбец таблицы для расчетов. Жмем на кнопку «OK».

Копируем маркером заполнения формулу на всю строку.

Переходим во вкладку «Данные». Там в блоке инструментов «Анализ» кликаем по кнопке «Поиск решения».

Открываются параметры поиска решения. В поле «Оптимизировать целевую функцию» указываем ячейку, содержащую функцию СУММПРОИЗВ. В блоке «До» устанавливаем значение «Минимум». В поле «Изменяя ячейки переменных» указываем весь диапазон таблицы для расчета. В блоке настроек «В соответствии с ограничениями» жмем на кнопку «Добавить», чтобы добавить несколько важных ограничений.

Запускается окно добавления ограничения. Прежде всего, нам нужно добавить условие того, что сумма данных в строках таблицы для расчетов должна быть равна сумме данных в строках таблицы с условием. В поле «Ссылка на ячейки» указываем диапазон суммы в строках таблицы расчетов. Затем выставляем знак равно (=). В поле «Ограничение» указываем диапазон сумм в строках таблицы с условием. После этого, жмем на кнопку «OK».

Аналогичным образом добавляем условие, что столбцы двух таблиц должны быть равны между собой. Добавляем ограничение, что сумма диапазона всех ячеек в таблице для расчета должна быть большей или равной 0, а также условие, что она должна быть целым числом. Общий вид ограничений должен быть таким, как представлен на изображении ниже. Обязательно проследите, чтобы около пункта «Сделать переменные без ограничений неотрицательными» стояла галочка, а методом решения был выбран «Поиск решения нелинейных задач методом ОПГ». После того, как все настройки указаны, жмем на кнопку «Найти решение».

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

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

Опишите, что у вас не получилось.
Наши специалисты постараются ответить максимально быстро.

[править] Источники

  1. ↑ Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
  2. ↑ С.Гасс. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961 (djvu)
  3. ↑ Лунгу К. Н. Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.(djvu)
  4. ↑ Alexander Schrijver. Combinatorial optimization. Springer-Verlag, 2003, ISBN 3-540-44389-4
  5. G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666—704, 1781.
  6. Hitchcock F. L, Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematical Physics 20, 1941.
  7. Koopmans T. С. Optimum Utilization of the Transportation System, Econometrica 17, Supplement, 1949.
  8. ↑ Dantzig, G. В., Application of the Simplex Method to a Transportation Problem, chap. XXIII of // Koopmans T.C. (ed.), Activity Analysis of Production and Allocation, Cowles Commission Monograph 13, John Wiley & Sons, Inc., New York, 1951.
  9. Fоrd L. R., Jr., and D. R. Fullkerson, Solving the Transportation Problem, RAND Report RM-1736, The RAND Corporation, Santa Monica, Calif., 1956.
  10. ↑ Канторович Л. В., Гавурин М. К., Применение математических методов в вопросах анализа грузопотоков, Сб. ст. Проблемы повышения эффективности работы транспорта, АН СССР, 1949, стр. 110—138.
  11. Канторович Л. В. Математические методы организации и планирования производства. //Применение математики в экономических исследованиях, том 2 (под ред. В. С. Немчинова), М., Соцэкгиз, 1961, 535 стр., 251—309.
  12. Канторович Л. В. О перемещении масс, Докл. АН СССР 37, № 3 (1942), 227—229.
  13. Dantzig G.B. Application of the simplex method to a transportation problem. // Купманс, ред. (Кооpmans Т. С., еd), Activity analysis of production and allocation. (Cowles Commission Monograph № 13), New York, Wiley, 1951, 404 pp., 359—373.
  14. \sum^{m}_{i=1}{a_i} = \sum^{n}_{j=1}{b_j}, где a_i — запас i-го поставщика, а b_j — потребность j-го потребителя.
  15. ↑ К. Л. Самаров. Учебное пособие для студентов. Транспортная задача. Москва, СВАО, Учебный центр «Резольвента»
  16. ↑ А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
  17. ↑ Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
  18. Charnes A. and W. W. Cooper, The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems, Management Science 1, 1954—1955.
  19. Окраска ячеек применена в настоящей статье для целей наглядности и рекомендована, например, Лунгу на с.91.
  20. Уравнение по строкам: \sum^{n}_{j=1}{X_{ij}}=a_i ~ (i=1,2,…m); Уравнение по столбцам: \sum^{m}_{i=1}{X_{ij}}=b_j ~ (j=1,2,…n).
  21. Хотя этот случай интуитивно понятен, тем не менее, формальная математическая запись выглядит так: L(X)=\sum^{n}_{j=1}{ \sum^{m}_{i=1}{ C_{ij}X_{ij} } }
  22. При компьютерной реализации под словом «любое» полезно подразумевать выбор из равноценных вариантов при помощи генератора случайных чисел.
  23. ↑ Ф. Е. Карпелевич и Л. Е. Садовский. Элементы линейной алгебры и линейного программирования. Физматгиз, 1963. (djvu)
  24. ↑ Stepping stone algorithum for solving the transhipment problem (Python recipe). Created by James Coliins on Sat, 29 Nov 2008 (MIT). копия http://www.peeep.us/5a45cffc
  25. http://jean-pierre.moreau.pagesperso-orange.fr/Basic/transpor_bas.txt Modèles pratiques de décision Tome 2, By Jean-Pierre Blanger, PSI Editions, France, 1982
  26. http://jean-pierre.moreau.pagesperso-orange.fr/Pascal/transpor_pas.txt Modèles pratiques de décision Tome 2, By Jean-Pierre Blanger, PSI Editions, France, 1982. Pascal Release 1.0 By J-P Moreau, Paris.
  27. http://infostart.ru/public/89917/
  28. Б.Банди «Основы линейного программирования» М:Радио и связь, 1989 (djvu)
  29. http://kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2

Транспортная задача

Транспортная задача Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача 
Начальное решение Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля‎ 
Вырожденные случаи Вырожденность в ТЗ • Ацикличность в ТЗ

Рисунок 3 – Представление транспортной задачи в виде сети

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

1.2 Решение задачи в среде Excel

Данную задачу можно решить симплекс-методом или с помощью, так называемой, транспортной таблицы. Исходные данные для решения классической транспортной задачи целесообразно представить в виде двух таблиц, в первой из которых представлены значения стоимости перевозок единицы товара cij от i-го поставщика к j-му потребителю. Во второй таблице представлены: значения Si предложения каждого i-го поставщика; значения Dj спроса каждого j-го потребителя; переменные xij, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец «Сумма». Целевая ячейка D24 должна содержать формулу, выражающую целевую функцию:

=СУММПРОИЗВ(B12:C13;C20:D21)

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

В Excel несбалансированная транспортная задача решается путем изменения ограничений по спросу (если спрос превышает предложение) или по предложению (если предложение превышает спрос).

Таблица 9 – План оптимального закрепления

Потребительский спрос бассейна и школы удовлетворены полностью. На складе Волжского района остается не вывезенным 300 мешков, на Ленинском складе – 250 мешков.

Общая стоимость перевозки составляет 53500 условных единств.

Задача 2.

Виды транспортных задач

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

Условия транспортной задачи можно представить двумя способами:

  • в виде схемы;
  • в виде матрицы.

В процессе решения могут быть ограничения (либо задача решается без них).

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

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

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

Метод минимального элемента

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

Рассмотрим метод минимального элемента на примере.

Пример 2. Найти опорный план транспортной задачи представленной в таблице условий ниже методом минимального элемента:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно: .

Общая потребность в грузе в пунктах назначения равна: .

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Минимальный тариф равный 1 находится в клетке (A1, B3). Поэтому заполняем эту клетку.

A1>B3. Следовательно в клетку (A1, B3) помещаем число 70. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A1 равными 150−70=80.

Минимальный тариф равный 1 находится в клетке (A2, B4). Поэтому заполняем эту клетку.

A2>B4. Следовательно в клетку (A2, B4) помещаем число 40. Потребности пункта B4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B4 и будем считать запасы пункта A2 равными 100−40=60.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

Ссылка на основную публикацию