Решение транспортных задач

Целью лекции является ознакомление учащихся с методикой оптимизации математических моделей транспортных задач. На конкретных примерах разобраны типичные случаи использования программы "Поиск решения".

Задача 3.1

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

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

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

Нарисуем ментальную карту для данной задачи.

На рисунке введены следующие обозначения:

Математическая модель транспортной задачи сводится к заданию двух матриц $$Xik$$ — число перевозок и $$Yik$$ — стоимость перевозок и двух векторов $$(Rz)i$$ — ресурс поставщика и $$(Rs)k$$ — ресурс потребителя. Целевая функция определяет транспортные издержки потребителей, которые должны быть минимальными

$$F=Xik*Yik\Rightarrow min$$

Множество допустимых решений ограничивается ресурсами поставщиков и ресурсами потребителей:

$$\sum kXik <=(Rz)i$$ — число перевозок от $$i\mbox{-ого}$$ поставщика всем потребителям не может превышать производственных возможностей завода;

$$\sum Xiik <=(Rs)k$$ - число перевозок для $$k\mbox{-ого}$$ потребителя от всех поставщиков не может превышать возможностей потребителя складировать привезенные товары.

Для решения задачи средствами MS Excel нам нужно на листе книги представить дополнительно к матрице нормированных тарифов $$Yik$$ матрицу числа перевозок $$Xik$$ и сформировать целевую функцию в виде суммарных издержек потребителей. Подготовленные таблицы будут выглядеть следующим образом:

В качестве начальных значений элементов матрицы $$Xik$$ выбрано число 1. Целевая функция помещена в ячейку G16. В ячейки второй таблицы вставлены следующие формулы:

В ячейки D15:F16 вставлены формулы, аналогичные формулам В15:С16.

Заполнив данными поля диалогового окна "Параметры поиска решения" и введя ограничения, получим оптимальное решение транспортной задачи:

Из таблицы видно, что у поставщика 3 остаются возможности еще для 10 перевозок. Чтобы наглядно представить себе распределение перевозок между поставщиками и потребителями, построим диаграмму плана перевозок:

Оптимальность решения математической модели достигается по совокупным издержкам всех потребителей. Однако при принятии по данным результатам управленческого решения стоит обратить внимание на непропорциональность издержек полученному товару для разных потребителей. В самом деле, потребитель 1 получил 180 единиц товара и заплатил 3800 руб., а потребитель 5 получил больше — 220 единиц товара, а заплатил меньше — 2900 руб. Потребитель 2 получил товара вдвое меньше, чем потребитель 4, а заплатили одинаково — по 1600 руб.

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

Заданные ограничения выполняются, но общие издержки возрастают на 990 руб.

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

Задача 3.2. Назначение бригад на работы

Требуется построить три объекта Oбj $$(j=1,2,3)$$. К работе могут быть привлечены три бригады Брi $$(i=1,2,3)$$. Каждая бригада из-за ограниченности своих ресурсов может одновременно строить только один объект. Каждый объект из-за технологических особенностей может строиться только одной бригадой. Известны сметные стоимости, которые установлены $$i\mbox{–ой}$$ бригадой для $$j\mbox{-ого}$$ объекта. Эти суммы (в тыс. руб.) приведены в матрице затрат $$Yij$$:

Требуется разработать оптимальное по стоимости распределение бригад работников по объектам обслуживания.

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

На связях бригад с объектами указаны нормативные коэффициенты — суммы, запрашиваемые бригадами за строительство объектов. Для удобства сравнения бригад между собой справа приведены суммарные стоимости работ каждой бригады для всех трех объектов. Из рисунка сразу видно, что Бригада 3 имеет наименьшие суммарные затраты. Но мы вынуждены учитывать ограничения по назначениям на работы: одна бригада может строить только один объект.

Математическая модель должна включать в себя три матрицы:

Бинарные элементы матрицы назначений бригад на объекты $$Xij$$ равны 1, если $$i\mbox{-ая}$$ бригада обслуживает $$j\mbox{-ый}$$ объект и равны нулю в противоположном случае. При этом каждая бригада может одновременно обслуживать только один объект, и каждый объект может обслуживаться только одной бригадой. Поэтому сумма чисел по строкам и столбцам матрицы равна 1.

$$Yij$$ — матрица нормативных коэффициентов (тыс. руб.). Это матрица констант — они не меняются в процессе решения задачи.

Матрица затрат должна быть получена перемножением матрицы назначений на матрицу нормативных коэффициентов:

$$Zij=Xij*Yij$$,$$i = 1,2,3$$;$$j = 1,2,3$$.

На листе книги таблицы выглядят следующим образом:

В ячейки матриц X и Z вставлены формулы:

В качестве целевой функции выбираем общие затраты (ячейка Е20). Целью решения является минимизация этой функции.

По команде Данные — Поиск решения вызываем надстройку "Поиск решения". Диалоговое окно вместе с результирующими данными показано на рисунке.

Суммарные затраты 228 тыс. руб. являются оптимальными при таком распределении работ по объектам:

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

Часто оптимальное решение математической модели не может быть воплощено в практику по самым разным причинам. Поэтому необходимо при планировании проводить вариантный анализ задачи, просчитывая возможные осложнения. Предположим, в частности, что самая "дешевая" бригада 3 нашла себе срочную другую работу и пока не может быть назначена на наши объекты. Но бригада 2 и бригада 3 увеличили свои ресурсы и имеют возможность строить по два объекта. Какой же бригаде поручить строить два объекта?

В этом варианте решения изменятся лишь ограничения на сумму бинарных коэффициентов. Для бригады 1 и бригады 2 эта сумма может быть равной 1 или 2, а для бригады 3 эта сумма равна 0:

Решение будет выглядеть следующим образом:

Бригада 1 будет строить объект Об2, а бригада 2 будет строить два объекта: Об1 и Об3. Но наши расходы в этом варианте возрастут на 10 000 руб.

Задача 3.3. Составление расписания занятий учебных групп

По учебному плану недельная нагрузка для учебной группы второго курса должна составлять 36 часов — по шесть учебных часов (или по три "пары") в день:

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

В данной задаче удобно при расчетах за единицу измерения выбрать сдвоенный учебный час, т.е. "пару", как это и делается при составлении расписаний на практике. Математическая модель должна включать в себя бинарную матрицу назначений. Число 1 обозначает, что занятие есть, а число 0 обозначает, что занятия нет.

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

Обе группы рассмотрим в одной таблице, заполнив матрицу нормативных коэффициентов единицами:

В строке 10 суммируем число занятий студентов в день, а в столбцах N и O суммируем число занятий по дисциплинам по Гр.1 и Гр.2 соответственно. Целевую функцию помещаем в ячейку P10 как сумму ячеек N10 и O10.

В таблице присутствуют формулы автосуммы:

Десять столбцов скрыты, формулы в них аналогичны формулам в столбцах В и С.

Далее устанавливаем параметры "Поиска решения":

В результате поиска выдается одно из допустимых решений:

Данный процесс составления расписаний позволяет учитывать отдельные пожелания преподавателей. Например, преподаватель английского языка не может приходить по понедельникам. Тогда в параметры поиска решения вводим новое ограничение: В7:С7=0.

Ключевые термины

Закрытая модель — возможности поставщиков отправлять грузы совпадают с возможностями потребителей принять грузы (ресурсы поставщиков равны ресурсам потребителей).

Матрица назначений — матрица $${Xik}$$ с бинарными коэффициентами. Коэффициент $$Xik$$ равен 1, если субъект $$i$$ назначен на объект $$k$$, и равен 0 в противоположном случае.

Ресурс назначений — предельное число допустимых событий для субъекта или объекта.

Краткие итоги

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

Вопросы

Упражнения

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

Задача 3.4

Коммивояжер должен объехать 7 городов. Выехав из одного города, он должен вернуться в него, заехав в каждый из других городов только один раз. Маршрут коммивояжера должен представлять собой замкнутый цикл без петель. Требуется найти кратчайший замкнутый путь коммивояжера. Карта расположения городов показана на рисунке. Расстояния между городами показаны в таблице.

Математическая модель данной транспортной задачи сводится к заданию двух матриц:

$$\{X_{ik}\}$$ — число прохождений пути из города $$i$$ в город $$k$$. Переменная $$Хij$$ принимает значение 1, если коммивояжер переезжает из города $$i$$ в город $$j$$ и 0 в противном случае.

$$\{Y_{ik}\}$$— расстояния между городами (в общем случае матрица несимметрична, т.е. $$y_{ik}\ne y_{ki}$$.

Кроме того, должны быть заданы два вектора:

$$(R_{in})i$$ — ресурс выезда (число выездов из каждого города);

$$(R_{out})k$$ — ресурс въезда (число въездов в каждый город).

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

$$F=\{X_{ik}\}*\{Y_{ik}\} \Rightarrow min$$

Множество допустимых решений ограничивается ресурсами въезда и ресурсами выезда:

$$\sum kX_{ik} <=(R_{in})_i=1$$ — число прохождений пути из города $$i$$ в город $$k$$ не может превышать заданный ресурс выезда из города $$i$$;

$$\sum X_{ik} <=(R_{out})_k=1$$ — число прохождений пути из города $$i$$ в город $$k$$ не может превышать заданный ресурс въезда в город $$k$$.

Кроме того, для предупреждения петель вводятся дополнительные условия:

$$ui–uj+nxij <=n-1$$$$i,j=1,2,\ldots,n$$

$$xij=0$$ или $$xij=1$$$$i,j=1,2,\ldots,n$$

Для решения задачи средствами MS Excel нам нужно на листе книги представить дополнительно к матрице расстояний между городами $$Yik$$ матрицу числа прохождений пути из города $$i$$ в город $$k$$ $$Xik$$ и сформировать целевую функцию в виде суммы всех маршрутов коммивояжера. Подготовленные таблицы будут выглядеть следующим образом:

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

В диалоговом окне "Параметры поиска решения" вводим ограничения въездов и выездов заданными ресурсами:

В столбце L приведены переходы коммивояжера между городами. Отсутствие петель обеспечивается вторым ограничением.