4. Нахождение оптимального решения методом потенциалов

Потенциалы для загруженных (базисных) клеток равны нулю.

1. Составляем и решаем систему уравнений V_j - U_i = C_ij (смотреть рисунок 8).

	36		49	7	32		45	15	28	U1
4	29		37	5	50		33	16	41	U2
	42	1	30	12	38		46		34	U3
	35		43	1	26		39		47	U4
	48	11	31		44	8	27		40	U5
V1		V2		V3		V4		V5

Рисунок 8 – Исходная таблица для нахождения оптимального решения методом потенциалов

i, j - номера тех строк и столбцов, в которых стоят нагруженные опорным планом клетки;

C_ij - удельная стоимость перевозок для этих клеток;

V_j - потенциал j-того потребителя;

U_i - потенциал i-того отправителя.

При этом (m + n) - количество неизвестных; (m + n - 1) - количество уравнений.

Для того, чтобы уравнять количество уравнений неизвестным, один из потенциалов в уравнении v_j - u_i = c_ij, , полагают равным нулю.

Определим значения (оценки для небазисных переменных) x_ij по формуле x_ij = Ui+Vj-С_ij (i и j для ненагруженных клеток).

Условие оптимальности:

Если все x_ij ≤ 0, то план оптимальный.

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

x₁₁ = U₁+V₁ – C₁₁ = 0 + 11 – 36 = - 25; x₁₂ = 0 + 24 – 49 = – 25;

x₁₄ = 0 + 20 – 45 = – 25; x₁₅ = 0 + 23 – 28 = – 3;

x₂₂ = 24 +18 – 37 = 5; x₂₄ = 20 + 18 – 33 = 5;

x₃₁ = 11+ 6 – 42= – 25; x₃₄ = 20 + 6 – 46= – 20;

x₃₅ = 23 + 6 – 34 = – 5; x₄₁ = 11 – 6 – 35= – 30;

x₄₂ = 24 – 6 – 43= – 25; x₄₄ = 20 – 6 – 39 = –25;

x₄₅ = –6 + 23 – 47 = – 30; x₅₁ = 7 + 11 – 48= – 30;

x₅₃= 7 + 32 – 44= – 5; x₅₅ = 7 + 23 – 40= – 10;

Из положительности некоторых оценок можно сделать вывод о том, что данное решение не является оптимальным. Получим оптимальное решение.

x₂₂- включаемая в базис переменная.

x₃₂- исключаемая из базиса переменная.

	36		49	7	32		45		28	U1
4	29	1	37	4	50		33	16	41	U2
	42		30	13	38		46		34	U3
	35		43	1	26		39		47	U4
	48	11	31		44	8	27		40	U5
V1		V2		V3		V4		V5

Рисунок 9 – Таблица для нахождения оптимального решения методом потенциалов после включения/исключения переменных

Для того, чтобы уравнять количество уравнений неизвестным, один из потенциалов в уравнении v_j - u_i = c_ij, , полагают равным нулю.

Произведем повторное вычисления оценок.

x₁₁ = 0 + 11 – 36 = – 25; x₁₂ = 0 + 19 – 49 = – 30;

x₁₄ = 0 +15 – 45 = – 30; x₁₅ = 0 + 23 – 28 = – 5;

x₂₃ = 15 + 18 – 33= 0; x₃₁ = 11 + 6 – 42= – 25;

x₃₂ = 6 + 19 – 30= – 5; x₃₄ = 15 + 6 – 46= – 25;

x₃₅ = 23 + 6 – 34 = –5; x₄₁ = 11 – 6 – 35= – 30;

x₄₂ = 19 – 6 – 43= – 30; x₄₄ = 15 – 6 – 39 = – 30;

x₄₅ = – 6 + 23 – 47 = – 30; x₅₁ = 12 + 11 – 48= – 25;

x₅₃= 12 + 32 – 44= 0; x₅₅ = 12 + 23 – 40= – 5;

Из не положительности всех этих оценок можно сделать вывод о том, что данное решение является оптимальным.

Следовательно, пересылка пачек информации занимает 2310 миллисекунд.

И пересылка распределяется следующим образом:

• Пересылка из модуля А1 в В3 информации объемом 7 байт за время передачи одного байта 32 миллисекунды.

• Пересылка из модуля А2 в В1 информации объемом 4 байта за время передачи одного байта 29 миллисекунд.

• Пересылка из модуля А2 в В2 информации объемом 1 байт за время передачи одного байта 37 миллисекунд.

• Пересылка из модуля А2 в В3 информации объемом 4 байта за время передачи одного байта 50 миллисекунд.

• Пересылка из модуля А3 в В5 информации объемом 16 байт за время передачи одного байта 41 миллисекунду.

• Пересылка из модуля А3 в В3 информации объемом 13 байт за время передачи одного байта 38 миллисекунд.

• Пересылка из модуля А4 в В3 информации объемом 1 байт за время передачи одного байта 26 миллисекунд.

• Пересылка из модуля А4 в В2 информации объемом 11 байт за время передачи одного байта 31 миллисекунду.

• Пересылка из модуля А5 в В4 информации объемом 8 байт за время передачи одного байта 27 миллисекунд.