Решение транспортных задач
Определить план доставки грузов от поставщиков потребителям при условии минимальной стоимости всех перевозок. Данные приведены в таблице.
Тарифы на перевозку | Ресурсы поставщиков | |||||
Потребители | ||||||
Поставщик 1 | ||||||
Поставщик 2 | ||||||
Поставщик 3 | ||||||
Потребность потребителей | 850/840 |
В выделенной области таблицы указаны тарифы (транспортные расходы) на перевозку от данного поставщика к каждому потребителю. Транспортные расходы здесь являются условным понятием. В различных задачах в роли их могут выступать также расстояние, время и т.п. В последнем столбце указаны ресурсы поставщиков. Если перевозки осуществляются однотипным транспортом, то это может быть просто число перевозок. Иначе это может быть объем груза, штуки или тонны. В нижней строке указаны потребности потребителей.
В транспортных задачах с закрытой моделью запасы поставщиков совпадают с потребностями потребителей. В данной постановке задачи отражена ситуация, когда предложение (850 перевозок) превышает спрос (840 перевозок). Часто в таких случаях ограничения для пунктов отправления записывают в виде неравенств, а ограничения для пунктов назначения — в виде равенств.
|
|
Нарисуем ментальную карту для данной задачи.
На рисунке введены следующие обозначения:
- — ресурс поставщика ;
- — ресурс склада потребителя ;
- — число перевозок от поставщика к потребителю (целые числа);
- — стоимость одной перевозки от поставщика к потребителю;
- — число перевозок от поставщика всем потребителям (суммируем по );
- — число перевозок для потребителя от всех поставщиков (суммируем по ).
Математическая модель транспортной задачи сводится к заданию двух матриц — число перевозок и — стоимость перевозок и двух векторов — ресурс поставщика и — ресурс потребителя. Целевая функция определяет транспортные издержки потребителей, которые должны быть минимальными
Множество допустимых решений ограничивается ресурсами поставщиков и ресурсами потребителей:
— число перевозок от поставщика всем потребителям не может превышать производственных возможностей завода;
- число перевозок для потребителя от всех поставщиков не может превышать возможностей потребителя складировать привезенные товары.
Для решения задачи средствами MS Excel нам нужно на листе книги представить дополнительно к матрице нормированных тарифов матрицу числа перевозок и сформировать целевую функцию в виде суммарных издержек потребителей. Подготовленные таблицы будут выглядеть следующим образом:
|
|
В качестве начальных значений элементов матрицы выбрано число 1. Целевая функция помещена в ячейку G16. В ячейки второй таблицы вставлены следующие формулы:
В ячейки D15:F16 вставлены формулы, аналогичные формулам В15:С16.
Заполнив данными поля диалогового окна "Параметры поиска решения" и введя ограничения, получим оптимальное решение транспортной задачи:
Из таблицы видно, что у поставщика 3 остаются возможности еще для 10 перевозок. Чтобы наглядно представить себе распределение перевозок между поставщиками и потребителями, построим диаграмму плана перевозок:
Оптимальность решения математической модели достигается по совокупным издержкам всех потребителей. Однако при принятии по данным результатам управленческого решения стоит обратить внимание на непропорциональность издержек полученному товару для разных потребителей. В самом деле, потребитель 1 получил 180 единиц товара и заплатил 3800 руб., а потребитель 5 получил больше — 220 единиц товара, а заплатил меньше — 2900 руб. Потребитель 2 получил товара вдвое меньше, чем потребитель 4, а заплатили одинаково — по 1600 руб.
Если потребители относятся к разным фирмам, то они могут не согласиться на такую схему оплаты. Поэтому введем в параметры поиска решения дополнительные ограничения, отсортировав затраты в соответствии с количеством полученного товара. В результате поиска программа выдает такие результаты:
Заданные ограничения выполняются, но общие издержки возрастают на 990 руб.
К классу транспортных задач относятся также задачи о назначениях. Такие задачи возникают при определении маршрутов, при распределении людей на работы и должности, при распределении групп по аудиториям и пр.