Методы решения транспортной задачи

 

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

Алгоритм последовательного улучшения плана предусматривает два этапа решения задачи:

· определение исходного опорного решения;

· последовательное улучшение опорного решения и приближение к оптимальному плану.

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

 

Таблица 3. Поиск опорного решения

 

	Строительные объекты
Заводы

 

Заполнение таблицы начинаем с клетки (1,1), которая находится в северо-западном углу таблицы, отсюда и название метода.

и первый столбец закрыт, потребности строительного объекта удовлетворены. Переходим к клетке (1,2).

, закрыта первая строка, исчерпаны мощности завода . Переходим ко второй строке.

, закрыт 2-й столбец, потребности строительного объекта удовлетворены. Переходим к третьему столбцу.

, закрыта вторая строка, мощности завода исчерпаны. Переходим к третьей строке.

, закрыт 3-й столбец, потребности строительного объекта удовлетворены. Переходим к четвертому столбцу.

, закрыты все строки и столбцы.

Получили опорное решение. Этому решению соответствуют затраты:

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

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

В рассматриваемом примере и Опорный план (таблица 3) имеет 6 заполненных клеток, т.е. выполняется условие и опорный план невырожденный.

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

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

Поставим задачу: как можно больше перевозить с минимальной стоимостью. Эта идея заложена в методе минимальной стоимости. В этом случае на каждом шаге заполняют клетку таблицы с наименьшей стоимостью доставки единицы продукции. При этом необходимо учитывать это обстоятельство для всех поставщиков. Расчет выполнен в таблицах 4-6.

Начинаем заполнение таблицы 4 с клетки (1,4), затем переходим к клетке (1,1), потом к клетке (2,1) и т.д., при этом каждый раз фиксируем остатки на заводах и объектах. В итоге такого распределения получим транспортные расходы:

 

 

Таблица 4. Вариант 1 улучшенного плана

 

	Строительные объекты
Заводы						Остаток
						70, 20,0
						120, 0
	Остаток	30, 0		20, 0

 

Таблица 5. Вариант 2 улучшенного плана

 

	Строительные объекты
Заводы						Остаток
		- 2 70- =50		+ 4		70, 0
		+ 3 10+ =30		- 6 20- =0		140, 20 0
	Остаток	10, 0		20, 0

 

 

Таблица 6. Вариант 3 улучшенного плана

 

	Строительные объекты
Заводы						Остаток
						70, 0
						70, 0
						130, 0
	Остаток		50, 0	130, 0

 

Планы, полученные в таблицах 4-6 допустимы, невырождены и ацикличны. Как видим, расходы уменьшаются, но нет уверенности в том, что полученные планы оптимальны.

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

 

Метод потенциалов

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

Существует простая методика проверки планов на оптимальность. В основу ее положен метод потенциалов. Смысл его заключается в следующем. Каждому заводу поставщику присваивают некоторую величину которую называют потенциалом завода, а каждому строительному объекту – величину - потенциал строительного объекта. Эти величины связаны между собой соотношениями:

· для переменных заполненных клеток (базисных переменных) (5)

· для переменных незаполненных клеток (свободных переменных) (6)

Здесь - стоимость доставки единицы продукции от -го завода к - му строительному объекту заполненных клеток, - стоимость доставки для незаполненных клеток.

Алгоритм метода потенциалов

1. Устанавливают вид модели транспортной задачи (открытая или закрытая). При необходимости делают модель закрытой.

2. Определяют первый опорный план с учетом стоимости доставки продукции.

3. Проверяют опорный план на вырожденность. При необходимости вводят нулевые поставки.

4. Проверяют опорный план на оптимальность. Для чего определяют потенциалы поставщиков и потребителей по выражениям (5) для базисных переменных и анализируются неравенства (6) для свободных переменных:

· если хотя бы одно из неравенств не выполняется, то план неоптимальный и для его улучшения изменяют значение свободной переменной невыполняемого неравенства;

· если все неравенства выполняются и среди неравенств имеются равенства, то план оптимальный и не единственный.

Проверим алгоритм метода на примере 1. Исходная модель транспортной задачи является закрытой. В качестве первого опорного плана возьмем вариант 2 (таблица 5).

Вариант 2. Базисные переменные (заполненные клетки):

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

Так как равенств 6, а неизвестных 7, то система является неопределенной. Поэтому для определенности системы считаем значение одного из потенциалов известным, например, , тогда:

Составляем неравенства для незаполненных клеток и анализируем их

Одно из неравенств не выполняется, следовательно, план неоптимальный. Это неравенство соответствует переменной т.е. для улучшения плана необходимо эту переменную ввести в басис, присвоив ей некоторую величину Переход к новому базису осуществляется с помощью построения цикла и перераспределения перевозимой продукции. Строим цикл с вершинами в занятых клетках (1,1), (2,1), (2,3) и незанятой клетки (1,3), в которой не выполняются условия оптимальности. Для определения величины в незанятую клетку (1,3) поставим знак «+», а другие вершины цикла отметим чередованием знаков «-» и «+» (см. таблицу 5). Затем определяем где - количество продукции в клетках вершин цикла, отмеченных знаком «-»:

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

Выполним анализ варианта 3 (таблица 6).

Вариант 3. Базисные переменные:

Опорный план невырожденный. Составляем систему равенств, определяемых базисными переменными:

Так как равенств 6, а неизвестных 7, то полагаем , тогда:

Составляем неравенства для незаполненных клеток

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