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

 

Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.

Предварительный этап.

1. Каким-либо способом ищется допустимый план (методом северо-западного угла или минимального элемента).

2. Для полученного плана строится система m+n чисел , , таких, что , .

3. Построенная система и исследуется на потенциальность (то есть план исследуется на оптимальность). Для этого проверяется , .

Если система непотенциальна, то переходят к основному этапу (т.к. план не оптимален), иначе оптимальный план найден.

Основной этап.

1. Улучшаем план, то есть от плана переходим к плану такому, что .

2. Для плана строим новую систему , , , такую, что , .

3. Исследуем систему на потенциальность. Если система непотенциальна, то переходим на п.1. Иначе найден оптимальный план.

Если система непотенциальна.

Переходим к общему этапу.

1. Выбираем клетку, для которой неравенство вида наруша­ется в наибольшей степени, то есть, находится число

среди тех клеток, для которых условие (1) не выполняется: .

Начиная с клетки в направлении против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем клетки, начиная с , попеременно знаками + и –. Клетки со знаками + образуют положительную полуцепь, а со знаками – отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку

.

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

 

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

Определение 5. Если допустимый опорный план содержит менее элементов , то он называется вырожденным, а транспортная задача называется вырожденной транспортной задачей.

Следующая теорема позволяет определить вырожденность задачи до ее решения.

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

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

 

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

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

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

Пример выполнения работы:

Условие: Имеется три пункта производства однородного продукта A1, A2, A3, мощности которых составляют соответственно 200, 300 и 400 единиц. Этот продукт востребован в трех пунктах потребления B1, B2, B3, потребности которых составляют 350, 300, 250 единиц.

Затраты на поставку единицы продукта от пунктов производства до пунктов назначения заданы матрицей

.

Составить математическую модель транспортной задачи и решить ее с помощью программы Excel.Найти оптимальный план перевозок, минимизирующий общие затраты на перевозки.

Решение: Обозначим через xij величину поставки от i-го поставщика

j-му потребителю.

Тогда – план перевозок.

Общая стоимость перевозок выразится функцией

,

которую необходимо минимизировать.

Система ограничений примет вид:

.

 

Решим задачу с помощью программы Excel. Выполним следующие действия:

1. Создадим форму для исходных данных:

 

Рис.1. Исходные данные

Для целевой функции зарезервирована ячейка А12, для переменных xij – ячейки B4:B6, D4:D6, F4:F6, в них будут занесены результаты решения задачи.

2.В ячейки B8, D8, F8 введем формулы для вычисления левых частей уравнений-ограничений по потребностям.

Для потребителя B1 ограничение имеет вид уравнения

Следовательно, в ячейку B8 нужно записать формулу:=СУММ (В4:В6).

Формулы в ячейках D8 и F8 задаются аналогично (можно получить копированием из ячейки В8).

3. В ячейки I4:I6 введем формулы для вычисления левых частей уравнений-ограничений по запасам.

Для поставщика A1 уравнение-ограничение имеет следующий вид:

что соответствует формуле в ячейке I4: = B4 + D4 + F4.

Аналогично задаются формулы для ячеек I5 и I6.

4. Для вычисления значения целевой функции ,минимизирующей стоимость всех перевозок, в ячейку A12 запишем формулу:

= СУММПРОИЗВ (C4:C6; B4:B6) + СУММПРОИЗВ (E4:E6; D4:D6) + СУММПРОИЗВ (G4:G6; F4:F6)

5. Выберем команду: Сервис→ Поиск решения.

6. В диалоговом окне Поиск решения введем:

a) Адрес ячейки А12целевой функции;

b) Переключатель в группе Равной поставим на минимизацию;

c) Укажем диапазоны изменяемых ячеек: B4:B6; D4:D6; F4:F6;

d) Укажем уравнения-ограничения по потребностям: B8=B7; D8=D7; F8=F7;

e) Укажем уравнения-ограничения по запасам: I4:I6=H4:H6;

f) Укажем требования неотрицательности переменных:

В4:B6>=0;

D4:D6>=0;

F4:F6>=0.

7. Нажмем кнопку Выполнить.

8. В результате выполнения программы Поиск решения получим на экране в ячейках B4:B6; D4:D6; F4:F6 оптимальный план перевозок, а в ячейке А12 – минимальную общую стоимость за все перевозки:

 

Рис.2. Результат вычисления

Таким образом получаем, оптимальный план перевозок:

Минимальная общая стоимость всех перевозок составляет:

Вариантызаданий

Номер варианта	а	b	D
	а1 = 200 а2 = 175 а3 = 225	b1 = 100 b2 = 130 b3 = 80 b4 = 190 b5 = 100
	а1 = 200 а2 = 450 а3 = 250	b1 = 100 b2 = 125 b3 = 325 b4 = 250 b5 = 100
	а1 = 250 а2 = 200 а3 = 200	b1 = 120 b2 = 130 b3 = 100 b4 = 160 b5 = 140
	а1 = 350 а2 = 330 а3 = 270	b1 = 210 b2 = 170 b3 = 220 b4 = 150 b5 = 200
	а1 = 300 а2 = 250 а3 = 200	b1 = 210 b2 = 150 b3 = 120 b4 = 135 b5 = 135
	а1 = 350 а2 = 200 а3 = 300	b1 = 170 b2 = 140 b3 = 200 b4 = 195 b5 = 145
	а1 = 200 а2 = 250 а3 = 200	b1 = 190 b2 = 100 b3 = 120 b4 = 110 b5 = 130
	а1 = 230 а2 = 250 а3 = 170	b1 = 140 b2 = 90 b3 = 160 b4 = 110 b5 = 150
	а1 = 200 а2 = 300 а3 = 250	b1 = 210 b2 = 150 b3 = 120 b4 = 135 b5 = 135
	а1 = 200 а2 = 350 а3 = 300	b1 = 270 b2 = 130 b3 = 190 b4 = 150 b5 = 110
	а1 = 150 а2 = 150 а3 = 200	b1 = 100 b2 = 70 b3 = 130 b4 = 110 b5 = 90
	а1 = 330 а2 = 270 а3 = 350	b1 = 220 b2 = 170 b3 = 210 b4 = 150 b5 = 200
	а1 = 150 а2 = 200 а3 = 100	b1 = 90 b2 = 150 b3 = 75 b4 = 60 b5 = 75
	а1 = 300 а2 = 350 а3 = 200	b1 = 145 b2 = 195 b3 = 200 b4 = 140 b5 = 170
	а1 = 300 а2 = 300 а3 = 250	b1 = 150 b2 = 140 b3 = 115 b4 = 225 b5 = 220
	а1 = 300 а2 = 230 а3 = 320	b1 = 190 b2 = 150 b3 = 130 b4 = 180 b5 = 200
	а1 = 300 а2 = 250 а3 = 300	b1 = 130 b2 = 130 b3 = 150 b4 = 190 b5 = 250
	а1 = 200 а2 = 300 а3 = 250	b1 = 120 b2 = 140 b3 = 160 b4 = 180 b5 = 150
	а1 = 270 а2 = 450 а3 = 330	b1 = 190 b2 = 210 b3 = 200 b4 = 230 b5 = 220
	а1 = 210 а2 = 450 а3 = 290	b1 = 200 b2 = 220 b3 = 170 b4 = 210 b5 = 150

КОНТРОЛЬНЫЕ ВОПРОСЫ:

1. В чем состоит общая постановка транспортной задачи?

2. В каком случае транспортная задача является открытой и закрытой?

3. Как необходимо поступить в решении транспортной задачи, если она является открытой?

4. Дайте определение невырожденного и вырожденного опорного плана.

2. Какие существуют методы для нахождения опорного плана?

3. Сформулируйте принцип построения опорного плана задачи методом северо-западного угла.

4. Какое условие построения опорного плана является очень важным?

5. Сформулируете алгоритм нахождения начального опорного плана методом минимального элемента.

6. Сформулируете алгоритм нахождения начального опорного плана методом северо-западного угла.

7. Сформулируете алгоритм нахождения начального опорного плана методом Фогеля.

8. С помощью какого метода опорный план задачи исследуется на оптимальность? Опишите алгоритм решения транспортной задачи этим методом.