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

Это один из наиболее эффективных методов нахождения оптимального плана транспортной задачи. Рассмотрим суть метода.

Поставим в соответствие каждому поставщику (т.е. каждой строке транспортной задачи) некоторое число U_i. х (i= 1…m), а потребителю (т.е. каждому столбцу таблицы) — число V_j х (j=1…n). Эти числа называются соответственно потенциалом поставщика U_i. и потенциалом потребителя V_j.

Для того чтобы некоторый план х=(х_ij), где i= 1. ,m; j=1.,n транспортной задачи был оптимален, необходимо и достаточно, чтобы ему отвечала такая система из (m+n) чисел U_i и V_j, для которых выполняются условия

U_i + V_j ≤ C_ij , где i= 1,… ,m; j=1,…,n

из максимизации линейной формы

F(U,V) =∑ a_iU_i+∑b_jV_j

Запишем эквивалентную систему условию.

Для базисных перевозок (заполненных клеток транспортной таблицы) условие имеет вид:

U_i+V_j=C_ij

Для небазисных перевозок введем обозначение

U_i+V_j=C_ij^*

где C_ij^* — величины, которые называются непрямыми тарифами.

Тогда условия оптимума допустимого базисного решения запишутся в виде:

а) для базисных перевозок:

∆_ij = C_ij^* - C_ij = 0

б) для небазисных перевозок:

∆_ij = C_ij^* - C_ij ≤ 0

Эти условия называют еще условиями потенциальности.

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

Рассмотрим алгоритм метода потенциалов.

Шаг 1. Для каждой заполненной клетки транспортной таблицы, т.е. для каждой базисной переменной х_ij соответствующего допустимого плана, строятся уравнения-соотношения U_i+V_j=C_ij

Количество таких уравнений будет (т+п-1), так как этому числу отвечает количество базисных пере­менных. Поскольку неизвестных в задаче (т+п), система уравнений имеет множество решений. Чтобы найти одно из этих решений, значение одного из потенциалов задается произвольно: обычно принимают U₁=0 и находят значения других потенциалов.

Значения U_i и V_j. записываются справа и снизу исходной таблицы.

Шаг 2. Для каждой незаполненной клетки, т.е. для каждой небазисной переменной, рассчитывают непрямые тарифы с_ij. Результаты расчетов заносят в нижний левый угол незаполненной клетки.

Шаг 3. Полученный план проверяется на оптимальность.

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

а) вычеркиваем все строки и столбцы, которые имеют ровно одну заполненную клетку (выбранная клетка считается заполненной); все другие заполненные клетки составляют цикл и лежат в его углах;

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

в) в любом столбце или строке, где имеют место клетки циклов, должны быть ровно две вершины цикла;

г) исходная клетка цикла помечается знаком «+», а другие клетки — поочередно знаками «-» и «+».

Шаг 5. После построения цикла в клетках со знаком «-» выбирается минимальное значение х_ij. Новый базисный план получается из суммирования выбранной величины с величинами в клетках цикла со знаком «+» и вычитанием этой величины из величины в клетках со знаком «-».

Рис.1.

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

Значения переменных, которые включены в цикл, после описанной корректировки записываются в новую таблицу. Другие переменные записываются в новую таблицу без изменений.

Осуществляется переход к шагу 1.

Метод потенциалов обеспечивает монотонноеуменьшение значения целевой функции и позволяет по конечному числу шагов найти ее минимум.

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

1

U1=0

–

+

U2=-1

+

–

V1=8

V2=6

V3=8

Строкам отвечают потенциалы U _1; и U₂, а столбцам — потенциалы V₁, V₂, V_3.

Шаг 1. Для каждой заполненной клетки таблицы строим зависимости:

U ₁ + V₁ =С₁₁=8 U ₁ = 0; V₁= 8

U ₂ + V₂ =С₁₂=6 V₂ = 6

U ₂ + V₂ =С₂₂=5 U ₂ = 5-6=-1

U ₂ + V₂ =С₂₃=7 V₃ =7+1=8

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

Шаг 2. Для каждой незаполненной клетки рассчитываем непрямые тарифы и записываем их в левый нижний угол незаполненной клеточки:

С^*₁₃ = U ₁ + V₂ =0+8=8

С^*₂₁= U ₂ + V₁ =-1+8=7

Шаг 3. Проверяем полученный план на оптимальность по формуле

∆₁₃ = C₁₃^* - C₁₃= 8-5=3>0

∆₂₁ = C₂₁^* - C₂₁= 7-4 = 3>0

Критерий оптимальности нарушается в обеих незаполненных клетках. Поэтому нужно перейти к новому базисному плану путем перемещения перевозки в клетку из тах∆_ij. Так как клеток с одинаковыми разностями две (клетки с переменными х₁₃ и х₂₁), то будем перемещать перевозку в первую по порядку клетку, т.е. в клетку х₁₃. Отметим точкой эту клетку в таблице.

Шаг 4. Для правильного перемещения перевозок строим цикл. Вычеркиваем в таблице первый столбец, который имеет ровно одну незаполненную клетку. Четыре заполненные клетки, которые остались, со­ставляют цикл (клетка, в которую перемещается перевозка, считается заполненной). В каждой клетке цикла, начиная с отмеченной, ставим по очереди знаки «+» и «—».

Шаг 5. В клеточках со знаком «-» выбираем минимальную величину min(x₁₂,x₂₃)=min(1,7)=1. Составляем новый базисный план в следующую таблицу.

		10								U1=0
	–			+
										U2=2
	+				–
	V1=8	V2=3	V3=5

Значение базисной переменной x₁₁=10, которое не включено в предыдущий цикл, остается без изменения. Переменные, которые включены в цикл, корректируются на выбранную величину x_l2=1 в зависимости от знаков «+» и «-» в клетках цикла. Проверка плана на вырожденность: количество базисных переменных (заполненных клеток) равняется: т+п- 1=2+3-1=4; поэтому план невырожденный. Значение ба­зисных переменных в новом плане: x₁₁=10; х₁₃= 1; x₂₂ =8; x₂₃=6. Транспортные расходы: Z=8*10+5*l+5*8+7*6=167 д.е. (раньше было 170).

Шаг 1а. Строим соотношение по заполненным клеточкам:

U ₁ + V₁ =8 U ₁ = 0; V₁= 8

U ₁ + V₃ =5 V₃ =5

U ₂ + V₂ =5 U ₂= 5-2=3

U ₂ + V₃ =7 V₂ =7-5=2

Шаг 2а. Рассчитываем косвенные тарифы для незаполненных клеток:

С^*₁₂= U ₁ + V₂ =0+3=3

С^*₂₁= U ₂ + V₂ =2+8=10

Шаг 3а. Проверка плана на оптимальность:

∆₁₂= C₁₂^* - C₁₂= 3 -6=-3<0

∆₂₁ = C₂₁^* - C₂₁= 10 -4 = 6>0

План не оптимальный, потому как нарушено условие. Перемещаем перевозку в клеточку х₂₁ (замечается точкой в центре клетки и считается заполненной).

Шаг 4а. Вычеркиваем второй столбец, так как он имеет ровно одну заполненную клетку. Строится цикл.

Шаг 5а. В клетках со знаком «-» избираем минимальную величину: min(x₁₁,x₂₃)=min(10,6)=6. Составляем новый базисный план в таблице:

		4								U1=0
			+
	–
										U2=-4
	+		–
	V1=8	V2=9	V3=5

Базисная переменная х₂₂=8, которая не включена в цикл, переносится без изменения. Переменные в цикле корректируются на выбранную величину х₂₃ =6 в зависимости от знаков «+» и «-». Новый план не вырожден: он включает 4 заполненных клеточки и m+n-l=2+3-l=4. Базисные переменные: х₁₁=4; х₁₃=7;x₂₁=6; x₂₂=8.

Транспортные расходы: Z=8*4+5*7+4*6+5*8=131 д.е. (раньше было 167).

Шаг 1б. Строим соотношение по заполненным клеткам:

U ₁ + V₁ =8 U ₁ = 0; V₁= 8

U ₁ + V₃ =5 V₃ =5

U ₂ + V₁ =4 U ₂= 4-8=-4

U ₂ + V₂ =5 V₂ =5+4=9

Шаг 2 б. Рассчитаем косвенные тарифы для незаполненных клеток:

С^*₁₂= U ₁ + V₂ =0+9=9

С^*₂₃= U ₂ + V₃ =-4+5=1

Шаг 3 б. Проверяем план на оптимальность:

∆₁₂= C₁₂^* - C₁₂= 9 -6=3>0

∆₂₃ = C₂₃^* - C₂₃= 1 -7 = -6<0

План не оптимален, потому перемещаем перевозку в клетку х₂₃ (помечается точкой).

Шаг 4б. Вычеркиваем третий столбец, так как он имеет одну заполненную клетку. Строится цикл.

Шаг 5б. В клеточках со знаком «-» выбираем минимальную величину: min(x₁₁,x₂₂)^:min(4_:,8)=4. Составляем новый базисный план в таблице.

										U1=0
										U2=-1
	V1=5	V2=6	V3=5

Базисная переменная х₁₃, которая не включается в цикл, переносится без изменения. Переменные в цикле корректируются на выбранную величину х₁₁ с учетом правила знаков в клетках. Новый план не вы­рожден, потому что имеет 4 заполненных клетки и т+п- 1=4.

Базисные переменные: x ₁₂ =4; x_l3=7; х₂₁=10; х₂₂=4.

Транспортные расходы: Z=6*4+6*7+4*10+5*4=119 д.е.

Шаг 1в. Строим соотношение по заполненным клеткам:

U ₁ + V₁ =6 U ₁ = 0; V₁= 6

U ₁ + V₃ =5 V₃ =5

U ₂ + V₁ =4 U ₂= 4+1=5

U ₂ + V₂ =5 V₂ =5-6=-1

Шаг 2в. Рассчитываем косвенные тарифы длянезаполненных клеток:

С^*₁₁= U ₁ + V₁ =0+5=5

С^*₂₃= U ₂ + V₃ =-1+5=4

Шаг Зв. Проверяем план на оптимальность:

∆₁₁= C₁₁^* - C₁₁= 5 -8=-3<0

∆₂₃ = C₂₃^* - C₂₃= 4-7 = -3<0

Разности отрицательны, следовательно, условия оптимальности плана выполняются.

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

- базисные переменные: х₁₂=4; х₁₃=7; x ₂₁ =10, x ₂₂ =4;

- транспортные расходы: Z_min=119 д.е. Полученный ранее исходный план по методу минимального элемента является также оптимальным:

- значение потенциалов: U₁=0, U₂=-1, V₁=5, V₂=6,V₃=5;

- линейная форма

F(U,V) = a₁U₁+ a₁U₂+b₁V₁₊ b₂V₂ + b₃V₃ = 11*0+11+10*5+8*6+7*5=119 д.е.

В данной задаче F_max(U,V)=119 д.е. и Z_min=119 д.е. совпадают, т.е. совпадают линейные формы исходной и двойственной задач.

Вопросы для самоконтроля

1.Каково практическое использование транспортных задач?

2.Принципиальная суть транспортной задачи и её особенности.

3.Какая экономико-математическая модель транспортной задачи называется открытой закрытой? Структура экономико-математической модели транспортной задачи.

4.Какие специальные методы используются для получения допустимого базисного и оптимального решений транспортной задачи?

5.Охарактеризовать суть и алгоритм метода северо-западного угла. Почему он так называется?

6.В чем состоит проверка исходного плана транспортной задачи на вырожденность?

7.Пояснить суть и алгоритм метода минимального элемента.

8.Охарактеризовать суть и алгоритм метода потенциалов.

9.Что называется потенциалом строки (столбца) транспортной таблицы?

10.Пояснить понятие цикла в транспортной таблице метода потенциалов.

11.Правила построения цикла транспортной таблицы.

12.Каковы условия оптимальности допустимого базисного решения?

13.Какие условия оптимальности являются двойственными в транспортной задаче?