Занятие 7. Транспортная задача

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

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

Обозначим через количество единиц груза, предназначенного к отправке из пункта в пункт . Получим задачу о нахождении плана перевозок, при котором общая стоимость перевозок окажется минимальной:

; (з)

; (1)

; (2)

.

Условие (1) означает, что из пункта весь груз вывезен в пункты назначения, а условие (2) означает, что количество груза, завезенного в пункт со всех пунктов отправления, соответствует требуемому. Транспортную задачу удобно записывать в виде платежной матрицы:

			…
			…
			…
…	…	…	…	…
			…

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

Если суммарные запасы пунктов отправления больше суммарной потребности пунктов назначения, т.е. , то равенства (1) заменяются неравенствами:

, а условия (2) остаются без изменений. В этом случае для сведения к замкнутой модели следует:

а) ввести фиктивный пункт назначения с требуемой величиной ввоза ;

б) положить ;

в) ввести дополнительные переменные .

Тогда придем к замкнутой модели транспортной задачи.

Если в задаче имеется дополнительное требование, состоящее в том, что из некоторого пункта груз должен быть полностью вывезен, то стоимость перевозки единицы груза из пункта в пункт следует положить равной , где - достаточно большое положительное число, т.е. .

Если суммарные запасы отправителей меньше суммарных запросов пунктов назначения, т.е. , то равенства (2) заменяются неравенствами:

, а условия (1) остаются без изменений. В этом случае для сведения к замкнутой модели следует:

а) вести фиктивный пункт отправления с требуемой величиной вывоза ;

б) положить ;

в) ввести дополнительные переменные .

Тогда придем к замкнутой модели транспортной задачи.

Если в задаче имеется дополнительное требование полностью удовлетворить потребности пункта назначения , то следует положить , где - достаточно большое положительное число.

Пример 1. Привести транспортную задачу, заданную платежной матрицей (табл. 7.1), к замкнутой модели.

Таблица 7.1

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

Таблица 7.2

●

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

Метод «северо-западного угла» нахождения начального плана перевозок.

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

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

Эту процедуру продолжаем до тех пор, пока все пункты отправления и пункты назначения не будут обслужены. Последней перевозкой будет перевозка из пункта отправления в пункт назначения .

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

Первоначальный план перевозок. Таблица 7.3

Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок.

Вычислим значение функционала для найденного плана перевозок:

.

Метод «северо-западного угла» не учитывает стоимости перевозок. Поэтому начальный план может оказаться далеко не оптимальным. Следующий метод стоимости перевозок учитывает.

Метод минимума по матрице нахождения начального плана перевозок.

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

В оставшейся части платежной матрицы вновь ищется минимальный элемент, и процедура повторяется до тех пор, пока первоначальный план перевозок не будет получен. В качестве примера обратимся к платежной матрице, задаваемой таблицей 7.2.

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

Для найденного плана перевозок

.

Первоначальный план перевозок. Таблица 7.4

Перейдем непосредственно к методу потенциалов решения транспортной задачи.