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

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

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

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

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

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

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

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

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

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

— число перевозок от поставщика всем потребителям не может превышать производственных возможностей завода;

- число перевозок для потребителя от всех поставщиков не может превышать возможностей потребителя складировать привезенные товары.

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

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

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

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

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

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

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

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

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