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

Материал из Циклопедии
Перейти к: навигация, поиск
Видео-урок от Alixander1990

Решение транспортной задачи в Excel — условное название для методов нахождения решения транспортной задачи с применением электронных таблиц Microsoft Excel.

Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи. В MS Excel также можно организовать поиск начального допустимого плана и пошаговое решение транспортной задачи симплеккс-методом.

Содержание

[править] Рабочий лист

При решении в качестве начального этапа можно подготовить рабочий лист как показано на рисунке:

A B C D E F G
1
2
3 Цены перевозки, руб./кг Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4
4 Поставщик 1 2 3 2 4
5 Поставщик 2 3 2 5 1
6 Поставщик 3 4 3 2 6
7
8 Объёмы перевозки, кг: Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Запасы
9 Поставщик 1 20 - 10 - 30 30
10 Поставщик 2 0 30 - 10 40 40
11 Поставщик 3 - - 20 - 20 20
12 20 30 30 10 90
13 Спрос: 20 30 30 10 90
14 Целевая функция: 170

Можно, в частности, взять готовый пример здесь:[1]

[править] Формулы в таблице

Ячейки рядом с серыми (на изображении — строка 12 и столбец F) содержат формулы суммирования по строке и столбцу.

  • F9: =СУММ(B9:E9)
  • F10: =СУММ(B10:E10)
  • F11: =СУММ(B11:E11)
  • B12: =СУММ(B9:B11)
  • C12: =СУММ(C9:C11)
  • D12: =СУММ(D9:D11)
  • E12: =СУММ(E9:E11)

В отмеченной красным цветом итоговой ячейке использована формула =СУММПРОИЗВ(B4:E6;B9:E11), которая вычисляет сумму произведений цены на объем для каждого из путей перевозки груза. Другие ячейки на этом рабочем листе формул не содержат.

[править] Изменение числа поставщиков и потребителей

Если число строк и столбцов (поставщиков и потребителей) не совпадает с примером, их добавляют, "не задевая" первую и последнюю колонку из диапазона, чтобы не испортились настройки. Например, чтобы добавить еще одну колонку, добавляйте ее после столбца B, а нового поставщика — после строки Поставщик 1 в двух местах), после чего нужно «размножить» соответствующие формулы и оформление из имеющихся ячеек на вновь вставленные.

[править] Ввод исходных данных

В отмеченные зеленым цветом клетки затем надо ввести цены, в отмеченные серым — объем спроса и предложения. Желтые ячейки (объемы перевозки) при вызове надстройки «Поиск решения» программа посчитает сама.

[править] Сбалансированность задачи

Сумма спроса и сумма запасов (в этом примере = 90) должны совпадать, в противном случае требуется ввести фиктивного отправителя или поставщика с нулевыми ценами доставки (см. Транспортная задача#Балансировка задачи).

[править] Установка надстройки

Чтобы начать расчет, нужно убедиться, что в меню Сервис есть пункт меню «Поиск решения»:

Транспортная задача Excel Меню.png

Если его там нет, то нужно зайти в пункт «Надстройки» и установить соответствующую надстройку:

Транспортная задача Excel Надстр.png

[править] Выполнение вычислений

Затем необходимо вызвать пункт меню «Сервис — Поиск решения»:

Транспортная задача Excel Настройки.png

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

Для начала поиска решения нужно нажать кнопку «Выполнить», затем в появившемся окне — «Сохранить найденное решение».

[править] Округление

В итоговом решении могут оказаться числа наподобие 19.99999 или 1E-6 — для их форматирования до чисел с нужной разрядностью следует использовать кнопку «Формат с разделителями» на панели инструментов.

[править] Настройки для предотвращения зацикливания

По нажатию кнопки Параметры доступно окно с параметрами поиска решения:

Транспортная задача Excel Параметры.png

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

[править] Итоговое решение

Общая стоимость транспортировки содержится в отмеченной красным цветом ячейке «Целевая функция». Чем меньше это значение, тем меньше будет затрачено денег на перевозку всего груза.

[править] Ограничение на величину таблиц

Excel 2003 выдает ошибку на таблицах определенной величины (из 2-3 десятков потребителей и поставщиков).

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

  1. http://x-romix.narod.ru/transp-excel.xls (сделано на основе ссылок [1] и [2])


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты