Замечание

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

 

Для нашего примера построение начального опорного плана методом минимального элемента проиллюстрировано в таблице 4.2.

Таблица 4.2

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности	130 90 60	220	60	70	80

 

Выбираем ячейку с наименьшим тарифом. Это может быть одна из трех ячеек с тарифом 0: А₁В₅, А₂В₅, А₃В₅; например ячейку А₁В₅. Тогда: .

Пересчитываем остатки по формуле (в): b₅' = 0, a₁' = 120 – 80 = 40.

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

Выбираем следующую допустимую ячейку с наименьшим тарифом 1: А₁В₁ или А₃В₃, например А₁В₁: .

Пересчитываем остатки по формуле (а): a₁' = 0, b₁' = 130 – 40 = 90. Оставшиеся ячейки первой строки из рассмотрения исключаются.

Для ячейки А₃В₃: . Пересчет: a₃' = 0, b₃'=160–60=100 (формула (в)). Процесс дальнейшего построения опорного плана представлен в таблице 4.2.

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

Для данного плана перевозок транспортные расходы составят:

F(X₀) = 40*1 + 80*0 + 60*4 + 220*2 + 30*3 + 60*1 + 70*2 = 1010 у.д.е.

Шаг 2 Проверяем построенное начальное допустимое решение Х₀ на оптимальность методом потенциалов.

 

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

1. Построить систему потенциалов - действительные целые числа, сопоставляемые строке i и столбцу j соответственно. Для каждой базисной переменной текущего решения потенциалы u_i и v_j должны удовлетворять уравнению:

(4.5)

Так как базисных переменных m+n-1, то мы получим систему из m+n-1 уравнений вида (4.5) относительно m+n неизвестных. Значения потенциалов можно найти из этой системы, придав одному из них произвольное значение (обычно u_i полагается равным нулю), и затем, решая систему относительно m+n-1, остальных потенциалов.

2. Определить оценки оптимальности для небазисных переменных:

, (4.6)

где c_rk – транспортные расходы по перевозке груза из пункта А_r в пункт В_k.

Рассчитанные значения D_rk заносятся в нижний левый угол ячеек транспортной таблицы.

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

а) если все D_rk£0, то план оптимальный, конец вычислений;

б) если имеется хотя бы одна оценка D_rk>0, то план не является оптимальным и необходимо перейти к лучшему опорному плану.

4. Переход к лучшему опорному плану:

а) Определить переменную, вводимую в базис:

, (4.7)

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

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

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

Из базиса выводится переменная, помеченная и имеющая наименьшее значение X_min.

в) Вычислить новые значения базисных переменных:

- для переменных, не вошедших в цикл, их значения не меняются;

- значение переменной, вошедшей в цикл, увеличивается на величину X_min, если она помечена Å, и уменьшается на величину X_min, если .

5. Переход к шагу 2.

 

Построим систему потенциалов для допустимого решения Х₀ из нашего примера (см. табл. 4.3)

Таблица 4.3

vj ui	v1=1	v2= -1	v3= -1	v4=0	v5=0
u1=0		1
	Å	-8		-10		-5
u2=3
				-4		-5			Å
u3=2
		-7

Уравнения (4.5) для базисных переменных будут иметь вид:

x₁₁: u₁ + v₁ = 1 x₂₂: u₂ + v₂ = 2 x₃₄: u₃ + v₄ = 2

x₁₅: u₁ + v₅ = 0 x₃₁: u₃ + v₁ = 3

x₂₁: u₂ + v₁ = 4 x₃₃: u₃ + v₃ = 1

Полагая u₁=0, находим v₁=1, v₅=0, u₂=3, v₂=-1, u₃=2, v₃=-1, v₄=0.

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

x₁₂: D₁₂=u₁+v₂–с₁₂=0+(-1)–7=-8, x₂₄: D₂₄=u₂+v₄–с₂₄=3+0–8=-5,

x₁₃: D₁₃=u₁+v₃–с₁₃=0+(-1)–9=-10, x₂₅: D₂₅=u₂+v₅–с₂₅=3+0–0=3,

x₁₄: D₁₄=u₁+v₄–с₁₄=0+0–5=-5, x₃₂: D₃₂=u₃+v₂–с₃₂=2+(-1)–8=-7,

x₂₃: D₂₃=u₂+v₃–с₂₃=3+(-1)–6=-4, x₃₅: D₃₅=u₃+v₅–с₃₅=2+0–0=2.

План Х₀ не оптимален, так как D₂₅ =3>0 и D₃₅=2>0. Вводим в новый базис переменную x₂₅, так как .

Строим замкнутый цикл (см. таблицу 4.3): x₂₅ ® x₂₁ ® x₁₁ ® x₁₅ ® x₂₅. (Выбор направления цикла несущественен).

Из базиса выводится переменная x₂₁ = 60, так как .

Определяем новые значения базисных переменных (4в)):

x₁₁ = 40 + 60 = 100, x₂₁ = 60 - 60 = 0,

x₁₅ = 80 – 60 = 20, x₂₅ = 0 + 60 = 60,

x₂₂ = 220, x₃₁ = 30, x₃₃ = 60, x₃₃ = 70,

т.е. их значения не меняются, так как они не входят в цикл.

Новый план транспортной задачи представлен в таблице 4.4.

Таблица 4.4

vj ui	v1=1	v2=2	v3= -1	v4=0	v5=0
u1=0		1
	Å	-5		-10		-5
u2=0
-3				-7		-8
u3=2
		-4							Å

,

F(X₁)=100*1+20*0+220*2+60*0+30*3+60*1+70*2=830 у.д.е.

Строим новую систему потенциалов, вычисляем оценки оптимальности. Так как D₃₅=2>0, то план Х₁ не оптимален.

Определяем переменную, подлежащую введению в базис (x₃₅), строим цикл пересчета и находим переменную, выводимую из базиса (x₁₅). Пересчитываем значения базисных переменных. Результаты пересчета представлены в таблице 4.5.

Таблица 4.5

vj ui	v1=1	v2=0	v3= -1	v4=0	v5= -2
u1=0
		-7		-10		-5		-2
u2=2
-1				-5		-6
u3=2
		-6

 

Новый опорный план: ,

F(X₂)=120*1+220*2+60*0+10*3+60*1+70*2+20*0=790 у.д.е.

Проверяем план Х₂ на оптимальность (см. таблицу 4.5). Так как все D_rk£0, то последний план является оптимальным.

Ответ: Оптимальный план перевозок предусматривает транспортировку из 1^го карьера 120 т гравия для строительства 1^й дороги, из 2^го карьера 220 т для строительства 2^й дороги, из 3^го карьера 10т для строительства 1^й дороги, 60 т для 3^ей дороги, 70 т для 4^й дороги. При этом плане остается неиспользованным 60 т гравия во 2^м карьере и 20 т гравия в 3^м карьере, а общая минимальная стоимость перевозок составляет 790 условных денежных единиц.