Линейная оптимизация в транспортных задачах

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

Вы научитесь:

Мини-кейс: Ремонт дорог.

С восьми асфальтобетонных заводов должен вывозиться асфальт для ремонта пяти больших участков автодорог области. Менеджер подрядной организации хочет минимизировать транспортные расходы для данных условий.
Транспортные издержки перевозок указаны в таблице A:
Участок A Участок B Участок C Участок D Участок E
АБЗ 16 2 860 3 220 3 100 2 275 3 220
АБЗ 17 3 145 2 140 1 900 2 050 2 290
АБЗ 18 2 245 2 050 2 785 2 650 2 365
АБЗ 19 2 815 1 960 2 590 2 080 2 725
АБЗ 20 2 770 3 250 2 635 2 275 3 400
АБЗ 21 2 200 2 590 3 265 2 560 3 250
АБЗ 22 2 110 2 290 3 085 2 110 2 245
АБЗ 23 2 005 2 275 2 500 2 950 2 785
Заказы дорожно-строительных бригад на следующую неделю в таблице B:
Участок A Участок B Участок C Участок D Участок E
Количество машин 160 186 123 165 135
Заводы в состоянии предоставить за это время (таблица С):
Источник АБЗ 16 АБЗ 17 АБЗ 18 АБЗ 19 АБЗ 20 АБЗ 21 АБЗ 22 АБЗ 23
Количество машин 128 104 76 78 60 117 130 56
скрепка
  1. Каковы наименьшие транспортные издержки?
  2. Какие участки недополучат заказанный ими асфальт и в каком количестве?
  3. Найдите разницу между наилучшим и наихудшим планом перевозок.
  4. Выяснилось, что из-за аварийного состояния моста перевозка асфальта с АБЗ 20 на участок D по прямому маршруту невозможна. Объездной маршрут увеличивает стоимость рейса на 1000 рублей. Как из-за этого возрастут транспортные расходы?

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

Перенесем данные на рабочий лист MS Excel и проанализируем задачу.
  • Таблицу, в которой собраны данные о стоимости перевозок с каждого завода на соответствующий участок дороги, называют таблицей издержек. В нашей задаче это таблица A.
  • Менеджеру необходимо найти число машин, которые поедут с каждого асфальтобетонного завода на соответствующий участок дороги. Значит решение должно быть в виде таблицы, в которой на пересечении соответствующего завода и участка будет стоять искомое число машин. Эту таблицу называют диспетчерским планом. Ее удобно располагать под таблицей издержек. Выделим область, в которой будем искать число необходимых машин (область переменных) желтым цветом.
  • Если число машин с каждого завода умножить на соответствующую стоимость перевозки из таблицы издержек и полученные результаты сложить, то получим суммарные издержки всех перевозок. Выделим ячейку, в которой будем вычислять суммарные издержки, зеленым цветом.
  • Менеджер хочет минимизировать транспортные расходы, значит найти минимально возможное значение суммарных издержек, т.е. решить задачу оптимизации.
  • Данные таблицы B из условия задачи перенесем в строку "Заказы", а данные таблицы C перенесем в столбец "Производительность".
  • Внимательно посмотрим на данные задачи. Суммарное число машин, которые могут отправить все асфальтобетонные заводы - 749. Но все участки вместе заказали 769 машин. Таким образом, выполнить заказ всех участков полностью не удастся, и куда-то машин поедет меньше, чем необходимо.
  • Поэтому добавим строку, в которой будем вычислять, сколько машин отправится на каждый участок, и назовем ее "Выполнение заказов". Также необходимо добавить столбец "Контроль запасов", в котором будет суммировать количество машин, выехавших из каждого асфальтобетонного завода.
Сценарий необходимых действий описан ниже (анимация):
Таблица для решения транспортной задачи
  • Откроем поиск решения и введем необходимые данные.
    • Целевая ячейка в нашей таблице находится в зеленом поле по адресу G10. В ней мы вычисляем суммарные издержки.
    • Поскольку издержки должны быть минимальны, то отмечаем поле "Минимум".
    • В поле "Изменяя ячейки переменных" вводим диапазон ячеек переменных, выделены в таблице желтым цветом.
  • Обсудим ограничения задачи:
    • Количество машин, которое получит каждый участок, мы вычисляем в строке "Выполнение заказов". Так как мы выяснили, что не все участки получат требуемое число машин в силу ограниченности мощностей заводов, то первое наше ограничение сформулируем так:
      Количество машин, которое получит каждый участок меньше или равно числу заказанных участком машин.
      Математически это предложение записывается так:
      $B$22:$F$22 <= $B$23:$F$23
    • Второе ограничение касается мощностей асфальтобетонных заводов:
      Все асфальтобетонные заводы отправят плановое число машин .
      Другими словами, значения в ячейках "Производительность" у каждого завода равно значению ячейки "Контроль запасов".
      Математически это предложение записывается так:
      $H$13:$H$20 = $G$13:$G$20
Сценарий необходимых действий описан ниже (анимация):
Панель параметры поиска решений для решения транспортной задачи.
После запуска Поиска решения мы получим следующий результат:
  • Минимальные издержки при данных условиях - около 1.6 млн. рублей
  • Два участка B и Е не получат требуемого числа машин.
Решение, полученное солвером при решении транспортной задачи.
Итак, мы сформулировали конкретную транспортную задачу и решили ее с помощью методов линейной оптимизации, применив штатный инструмент MS Excel "Поиск решения" .

Как с помощью построенной модели отвечать на другие вопросы задачи?

Как модифицировать модель и ответить на другие вопросы задачи?

Найдем разницу между лучшим и худшем планом перевозок.
  • Лучший план мы нашли ранее. Он соответствует перевозкам, при котором суммарные издержки - около 1.6 млн. рублей.
  • Худший план соответствует максимальному значению суммарных издержек. Как его найти?
  • Для этого достаточно на панели "Параметры поиска решения" выбрать не Минимум, а Максимум.
Модификация параметров на панели Поиска решений
В результате получим новое решение с диспетчерским планом, который потребует почти 2.3 миллиона рублей.
Таким образом, оптимизация диспетчерского плана позволит сэкономить порядка 700 тысяч рублей!
Новое решение транспортной задачи после модификации ограничений
Как учесть возникшие осложнения в задаче?
  • Если осложнения связаны с увеличением, или уменьшением издержек на каком либо участке, то поставьте новое значение в соответствующей ячейке таблицы издержек.
  • В на панели "Параметры поиска решений" в этом случае ничего менять не нужно. Просто запустите еще раз поиск и получите новое решение.
  • Если осложнение связано с запретом перевозки с конкретного АБЗ на конкретный участок, то в таблице издержек поставьте очень большое число в соответствующей ячейке, и алгоритм просто не выберет данную перевозку.
Ниже приведено полученное решение при увеличении стоимости перевозки на 1000 рублей с АБЗ 20 на участок D.
Как легко изменить данные в задаче, чтобы учесть возникшие осложнения
блокнот Для решения транспортных задач методом линейной оптимизации необходимо:
  1. Составить таблицу издержек. В ней указать издержки перевозок грузов от каждого поставщика каждому потребителю.
  2. Под таблицей издержек поместить диспетчерский план, в котором в дальнейшем будет найдено решение.
  3. В диспетчерском плане поместить строку "Заказы". В каждую ячейку этой строки внести заказ соответствующего потребителя.
  4. Под строкой "Заказы" создать строку "Контроль выполнения заказов". В каждую ячейку этой строки ввести формулу, суммирующую выполнение заказа потребителя при реализации диспетчерского плана. Другими словами, нужно сложить все значения ячеек в области переменных диспетчерского плана под каждым потребителем.
  5. В диспетчерском плане создать столбец "Мощности поставщика", в который нужно записать максимальные возможности каждого поставщика.
  6. Рядом поместить столбец "Контроль мощностей поставщика". В каждую ячейку этого столбца ввести формулу, суммирующую мощности поставщика при реализации диспетчерского плана.
  7. Задать ограничения:
    • Выполненные заказы не должны превышать заказов потребителей.
    • Использованные мощности производителя не должны превышать номинальной мощности производителя.
  8. Корректно ввести данные в "Параметры поиска решения".
  9. Получить и проанализировать результат.