Транспортная задача закрытого типа

ТРАНСПОРТНАЯ ЗАДАЧА Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.Ни автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным: прикрепление потребителей ресурса к производителям; привязка пунктов отправления к пунктам назначения; взаимная привязка грузопотоков прямого и обратного направлений; отдельные задачи оптимальной загрузки промышленного оборудования; оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др. Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.

Имеются m пунктов отправления груза А1, А2, Аm и объемы отправления по каждому пункту a1, a2, am. Известна потребность в грузах b1, b2 bn по каждому из n пунктов назначения B1, B2 Bn. Задана также матрица стоимостей сij, (i=1,2 m, j=1,2 n) доставки груза из пункта i в пункт j. Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза xij должно быть отправлено из каждого пункта отправления (от поставщика) в каждый пункт назначения (до потребителя) с минимальными суммарными транспортными издержками. В общем виде исходные данные представлены в табл. 1. Таблица 1. Исходные данные Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения (1) Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

Для написания математической модели закрытой транспортной задачи необходимо все условия (ограничения) и целевую функцию представить в виде математических соотношений.

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

В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы.

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

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

Транспортные задачи могут решаться симплексным методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые распределительные методы решения. ПОСТРОЕНИЕ НАЧАЛЬНОГО ПЛАНА Наиболее распространенным методом решения транспортных задач является метод потенциалов.Решение задачи методом потенциалов включает следующие этапы: разработку начального плана (опорного решения); расчет потенциалов; проверку плана на оптимальность; поиск максимального звена неоптимальности (если условие п. 3 не было достигнуто); составление контура перераспределения ресурсов; определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру; получение нового плана.

Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения): метод северо-западного угла; метод минимальной стоимости; метод двойного предпочтения и т. д. Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов отправления А1, А2, А3 к пунктам назначения В1, В2, В3. В соответствии с принятыми в п. 1 обозначениями исходные данные задачи приведены в таблице 2. Таблица 2. Исходные данные Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом - методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки ("северо-западная" часть таблицы) и продолжается вниз и вправо (по диагонали). По указанному правилу загружаем первую клетку (1, 1) на основании следующего условия: min {60; 40} = 40 Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза 60 - 40 = 20, которые и распределяем на второй пункт назначения: min {20; 60} = 20 Продолжая преобразования аналогичным образом, приходим к следующей таблице: Таблица 3. Начальный план перевозок РЕШЕНИЕ С ПОМОЩЬЮ ТАБЛИЦЫ На практике подобные задачи решаются, конечно же, при помощи различного программного обеспечения, что позволяет значительно упростить работу и сэкономить время.

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

ЗАДАЧА: В пунктах A и B находятся соответственно 150 и 190 т горючего.

Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т. горючего Стоимость перевозки 1 т горючего из пункта A в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта B в пункты 1, 2, 3 - 120, 20, 80 тыс. руб. за 1 т соответственно. Составьте план перевозок горючего, минимизирующий общую сумму транспортных расходов.

Составим для наглядности таблицу исходных данных.

Поставщики Потребители Запасы 1 2 3 A 60 10 40 150 B 120 20 80 190 Потребность 60 70 110 Важно отметить, что данная задача сбалансирована, то есть запасы горючего и потребность в нем равны. В этом случае не нужно учитывать издержки, связанные как со складированием, так и с недопоставками.В противном случае в модель нужно ввести: • в случае превышения объема запасов - фиктивного потребителя; стоимость перевозок единицы продукции этому фиктивному потребителю полагается равной стоимости складирования, а объемы перевозок этому потребителю равны объемам складирования излишек продукции у поставщиков; • в случае дефицита - фиктивного поставщика; стоимость перевозок единицы продукции от фиктивного поставщика полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок от этого поставщика равны объемам недопоставок продукции потребителям.

Для решения данной задачи построим ее математическую модель.Неизвестными здесь являются объемы перевозок.

Пусть xij - объем перевозок от i-того поставщика j-тому потребителю. Функцией цели являются суммарные транспортные расходы, т.е. где cij - стоимость перевозки единицы продукции от i-того поставщика j-тому потребителю. Кроме того, неизвестные должны удовлетворять следующим ограничениям: • неотрицательность объема перевозок; • в силу сбалансированности задачи, вся продукция должна быть вывезена от поставщиков и потребности всех потребителей должны быть удовлетворены.Таким образом, мы имеем следующую модель: где ai - запасы горючего у i- того поставщика; bj - спрос у j-того потребителя.

В табличном процессоре Microsoft Excel для решения подобных задач предусмотрена надстройка Поиск решения.Если в меню Сервис отсутствует команда Поиск решения, для ее установки нужно выбрать команду Сервис | Надстройки, в появившемся диалоговом окне выбрать Поиск решения и нажать кнопку Ok. Выполните следующую подготовительную работу для решения транспортной задачи с помощью средства Поиск решения в табличном процессоре Microsoft Excel. 1. Введите в ячейки диапазона B4:D5 стоимости перевозок. 2. Отведите ячейки диапазона B8:D9 под значения неизвестных (объемов перевозок). Ячейки должны быть пустыми! 3. Введите в ячейки диапазона F8:F9 объемы запасов горючего у поставщиков. 4. Введите в ячейки диапазона B11:D11 потребность в горючем у потребителей. 5. В ячейку B14 введите функцию цели: =СУММПРОИЗВ(B4:D5;B8:D9). Сделать это можно при помощи мастера функций выбрав в разделе Математические функцию СУММПРОИЗВ и указав необходимый диапазон. 6. В ячейки диапазонов E8:E9 введите формулы вычисляющие объемы запасов у поставщиков, в ячейки диапазона B10:D10 - формулы расчета объемов доставляемого топлива к потребителям. А именно: Ячейка Формула Ячейка Формула E8 =СУММ(B8:D8) C10 =СУММ(C8:C9) E9 =СУММ(B9:D9) D10 =СУММ(D8:D9) B10 =СУММ(B8:B9) При этом на экране должно отображаться следующее: 7. Выберите в меню Сервис команду Поиск решения и заполните диалоговое окно Поиск решения, как показано на рисунке.

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

Средство Поиск решения найдет оптимальный план поставок горючего и соответствующие ему транспортные расходы В результате получаем следующее распределение горючего между поставщиками и потребителями: Поставщики Потребители 1 2 3 A 60 0 90 B 0 70 20 Значение целевой функции составило 10200 денежных единиц.

При этом, экономическая интерпретация результатов будет следующая. Поставщик A перевозит потребителям 1 и 3 - 60 и 90 т горючего соответственно, поставщик В - потребителям 2 и 3 - 70 и 20 т горючего соответственно.

При этом затраты на перевозку продукции будут минимальными и составят 10200 денежных единиц.