1.6.2 Метод минимального элемента.

Метод отличается от предыдущего тем, что вместо северо-западной клеточки на каждом шагу выбирается клеточка с наименьшим значением транспортных расходов с_іj.

1.6.3 Метод вычеркивания.

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

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

1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов.

2. В дальнейшем метод потенциалов состоит из однотипных шагов, на каждом из которых:

I) Вычисляются потенциалы строк u_i, i=1...,m, и столбцов v_j, j=1...,n, транспортной таблицы как решение системы v_j–u_i=c_ij, где и и j принимают такие значения, что клеточки (і,j) — базисные.

II) Вычисляются оценки переменных x_ij для всех небазисных клеточек (і,j) за формулой _ij=cij–v_j+u_i (оценки базисных переменных — нулевые).

III) Найденные оценки _ij проверяются на неотъемлемость. Если все _ij0, i=1...,m, j=1...,n, то текущий ДБР оптимальный. Иначе переходят к улучшению ДБР (пункт iv)).

IV) Определяют клеточку (k,l) с минимальной отрицательной оценкой, и присоединяют ее к совокупности базисных. Находят цикл (например, методом вычеркивания). Разделяют цикл на положительный и отрицательный полуциклы, последовательно помечая клеточки  вершины цикла знаками «+» и «–«, начиная с клеточки (k,l), которую первой относят к положительному полцикла, следующую за ней — к отрицательному, третью — к положительному и т.д. Среди клеточек отрицательного полцикла определяют клеточку (s,r) с минимальной величиной перевозки x_ij (если таких клеточек несколько, то выбирают только одну из них). Возлагают =x_sr. Увеличивают на значение  перевозка x_ij в клеточках положительного полцикла и уменьшают их на то же значение в клеточках отрицательного полцикла. В результате осуществления указанных процедур клеточка (k,l) вводится к совокупности базисных, а клеточка (s,r) перестает быть базисной (на ней разрывают цикл). Конец шага.

2. Практическая задача

   1. Постановка задачи

Из трех холодильников A_i, i=1..3, вмещающих мороженую рыбу в количествах a_i т, необходимо последнюю доставить в пять магазинов B_j, j=1..5 в количествах b_j т. Стоимости перевозки 1т рыбы из холодильника A_i в магазин B_j заданы в виде матрицы C_ij, 3x5.  Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

a1 =320,	b2 =140,		20	23	20	15	24
a2 =280,	b3 =110,	С =	29	15	16	19	29
a3 =250,	b4 =230,		6	11	10	9	8
b1 =150,	b5 =220

Склад	Магазин						Запасы груза
	B1	B2	B3	B4	B5
A1	20 0	23 0	20 0	15 0	24 0	320
A2	29 0	15 0	16 0	19 0	29 0	280
A3	6 0	11 0	10 0	9 0	8 0	250
Потребность	150	140	110	230	220