Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 4

1020 + 800 + 288 + 1440 + 128 = 3676 (ден. единиц). 

                                                        68   50   –    –    –                   

                                                  X₀ =     –    18   0    –    –    ,  S₀ = 3676.

                                                         –     –   90   8    –

                                                         –     –    –   23  87

1.2. Нахождение оптимального плана методом потенциалов

На каждом шаге этого метода выполняются следующие действия:

1)  вычисляются потенциалы, согласованные с построенным опорным планом;

2)  производится проверка оптимальности текущего опорного плана;

3)  если план оказывается неоптимальным, то строится новый опорный план с меньшим или, по крайней мере, таким же значением целевой функции.

Шаг 1. Ниже описывается первый шаг метода потенциалов.

1. Вычисление потенциалов

Вычислим потенциалы поставщиков U_i и потребителей V_j, согласованные с найденным опорным планом. Для этого используем условие (7) (см. стр. 6) критерия оптимальности плана транспортной задачи для задачи (1.1) – (1.11). Потенциалы поставщиков U_i и потребителей V_j находятся путем решения системы уравнений:

                                                              V_j – U_i = C_ij,                                                                   (1.12)

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

Занятая клетка	Уравнение
(1, 1)	V1 – U1 = 15
(1, 2)	V2 – U1 = 16
(2, 2)	V2 – U2 = 16
(2, 3)	V3 – U2 = 13
(3, 3)	V3 – U3 = 16
(3, 4)	V4 – U3 = 16
(4, 4)	V4 – U4 = 0
(4, 5)	V5 – U4 = 0

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

Например, положим U₁ = 10, а затем последовательной подстановкой вычислим значения остальных потенциалов для опорного плана из таблицы 1.1.

V₁ = U₁ + C₁₁ = 10 + 15 = 25,   

V₂ = U₁ + C₁₂ = 10 + 16 = 26,    

U₂ = V₂ – C₂₂ = 26 – 16 = 10,    

V₃ = U₂ + C₃₃ = 10 + 13 = 23,    

U₃ = V₃ – C₃₃ = 23 – 16 = 7,      

V₄ = U₃ + C₃₄ = 7 + 16 = 23,      

U₄ = V₄ – C₄₄ = 23 – 0 = 23,      

V₅ = U₄ + C₄₅ = 23 + 0 = 23.

Итак, найдены потенциалы, согласованные с начальным опорным планом Х₀. Значения потенциалов V_j и U_i представлены соответственно в нижней строке и последнем столбце таблицы 1.2.

Таблица 1.2

bj ai	68	68	90	31	87	Ui
118	15 68	16 50	14	11	17	10
18	15	16       18   –	13        0  +	11	14	10
98	21	22	16       90  –	16        8  +	23	7
110	0	0 +	0	0       23  –	0 87	23
Vj	25	26	23	23	23	S0 = 3891

Расчет потенциалов можно проводить, не решая систему уравнений (1.12), а непосредственно в таблице. Так, если известен потенциал пункта отправления U_i, то для вычисления потенциала пункта назначения V_j, соответствующего занятой клетке (i, j), следует использовать уравнение

V_j = U_i + C_ij.

Таким способом можно определить потенциалы всех пунктов назначения, которым соответствуют занятые клетки в i-й строке. Например, если известно, что U₁ = 10, то можно найти значения потенциалов первого и второго пунктов назначения, которым соответствуют занятые клетки в первой строке:

V₁ = U₁ + C₁₁ = 10 + 15 = 25,   V₂ = U₁ + C₁₂ = 10 + 16 = 26.

Если известен потенциал пункта назначения V_j, то для вычисления потенциала пункта отправления U_i, соответствующего занятой клетке (i, j), следует использовать уравнение

U_i = V_j – C_ij.

Таким способом можно определить потенциалы всех пунктов назначения, которым соответствуют занятые клетки в j-м столбце. Например, если известно, что V₂ = 26, то можно найти значение потенциала второго пункта потребления, которому соответствует занятая клетка (2, 2):

U₂ = V₂ – C₂₂ = 26 – 16 = 10.

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

Условие (7) критерия оптимальности для занятых клеток плана выполнено по построению. Поэтому для проверки оптимальности плана нужно выяснить, выполняется ли условие (6). Это равносильно проверке условий V_j – U_i ≤ С_ij для всех свободных клеток.

Для каждой свободной клетки (i, j) определим число ∆_ij = V_j – U_i – С_ij. Тогда ясно, что если ∆_ij ≤ 0 для всех свободных клеток, то текущий опорный план является оптимальным. В противном случае этот план не оптимален.

По своему экономическому смыслу величина ∆_ij характеризует то изменение в затратах на перевозки, которое произойдет, если будет осуществлена перевозка единицы груза из i-го пункта отправления в j-й пункт назначения. Если ∆_ij > 0, то единичная поставка приведет к экономии транспортных затрат на ∆_ij; если же ∆_ij < 0, то — к их увеличению на -∆_ij. Поэтому, если найдется ∆_ij > 0, то это означает, что существует свободное направление перевозки груза, экономящее затраты, т.е. текущий план перевозок не оптимален. Если же все ∆_ij ≤ 0, то это означает, что нет свободных направлений перевозок, экономящих затраты, т.е. план перевозок оптимален.

Вычислим ∆_ij для всех свободных клеток:

∆₂₁ = V₁ – U₂ – С₂₁ = 25 – 10 – 15 = 0,

∆₃₁ = V₁ – U₃ – С₃₁ = 25 – 7 – 19 = -1,

∆₄₁ = V₁ – U₄ – С₄₁ = 25 – 23 – 0 = +2,

∆₃₂ = V₂ – U₃ – С₃₂ = 26 – 7 – 17 = +2,

 ∆₄₂ = V₂ – U₄ – С₄₂ = 26 – 23 – 0 = +3 ,

∆₁₃ = V₃ – U₁ – С₁₃ = 23 – 10 – 14 = -1,

∆₄₃ = V₃ – U₄ – С₄₃ = 23 – 23 – 0 = 0,