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

Пусть имеется матрица перевозок, соответствующая начальному решению х_ij= (распределенные ресурсы), x_ij = 0 для свободных переменных (ресурсы не рас-пределены). Клетки, соответствующие свободным ресурсам, помечены звездочками.

В крайний правый столбец матрицы введем неизвестные u_i, а в нижнюю строку – неизвестные v_j. Эти n и m неизвестных должны для всех i, j, соответствующих базисным переменным, удовлетворять линейной системе уравнений

u_i + v_j = c_ij,(1)

Можно доказать, что эта система для всех базисных решений имеет треугольный вид. Её ранг равен n+m-1, и, следовательно, систему всегда можно решить следующим способом. На первом шаге полагают v_n = 0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения (1), так как значение другой неизвестной в этом уравнении уже известно. Это верно до тех пор, пока не найдены все неизвестные. То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные u_i и v_j называются потенциалами.

1.Составим и решим систему уравнений (1).

Как было отмечено, уравнения составляются для клеток, в которые распределены ресурсы.

2. Определим расчетные значения затрат z_ij для клеток, в которые ресурсы не распределены (со свободными переменными):

z_ij = u_i + v_j;

3. Вычислим разность заданных и расчетных затрат d_ij = c_ij - z_ij и проверим условие оптимальности d_ij > 0.

Если все d_i > 0, то исходный план является оптимальным, и переходят к пункту 5, в противном случае переходят к построению нового плана.

4. Построим новый план (уточним опорный план).

Выберем d_ab< 0,равное максимальному по модулю d_ij из состава отрицательных d_ij, т.е.

d_ab = - max êd_i ê, d_ij > 0.

Индексом a, bпомечена свободная переменная x_ab, которая соответствует d_ab. Соответствующую клетку транспортной таблицы отметим знаком “+”.

Кроме клетки a, bтранспортной таблицы, пометим знаками «–» и «+» другие клетки, в которые ресурсы распределены таким образом, что в каждой строке и столбце транспортной таблицы число знаков «+» будет равно числу знаков «–». Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце содержится максимум по одному «+» и «–».

Проставленные в таблице знаки «+» и «–» образуют прямоугольник, в углах которого расположены соответствующие знаки. Указанный прямоугольник далее представляется в виде фрагмента матрицы, который состоит из четырех клеток. В этих клетках производят перераспределение ресурсов (рис. 6).

Рис. 6. Фрагмент матрицы

Затем определяем минимум M из всех элементов, помеченных знаками «–», и выбираем одну клетку g,d где этот минимум достигается. При этом g,d обозначает клетку, в которую ресурсы далее распределяться не будут, а все ее содержимое будет распределено между остальными тремя клетками по следующему правилу:

а) в клетку, соседнюю клетке g,d новой таблицы записывается число M;

б) клетка g,d остается пустой;

г) в остальных клетках, помеченных знаками «+» и «–», число M вычитается из стоящего в клетке числа или складывается с ним, в соответствии со знаками;

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

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

5. Определим значение целевой функции, с учетом перераспределения в мат-рице (уточнение матрицы проводится до тех пор, пока хотя бы одно значение d_i <0).

Улучшим опорный план, который был получен ранее.

1. Составим и решим систему уравнений (1).

u₁ + v₃ = 24 = c₁₃;

u₂ + v₂ = 18 = c₂₂;

u₃ + v₁ = 19 = c₃₁;

u₃ + v₂ = 10 = c₃₂;

u₃ + v₃ = 100 = c₃₃;

u₄ + v₁ = 3 = c₄₁;

u₄ + v₄ = 8 = c₄₄.

Таким образом, имеется семь уравнений и восемь неизвестных, поэтому одному из неизвестных дается произвольное значение, как правило, для облегчения расчетов рекомендуется задаваться нулевым значением. Например u₃ = 0, тогда, решая последовательно соответствующие уравнения, получаем v₁=19; v₂=10; v₃=100; v₄=24; u₁=-76; u₂=8; u₃=0; u₄=-16.

2. Определим значения z_ij для клеток, в которые ресурсы не распределены.

z₁₁ = u₁ + v₁ = –76 + 19 = –57;

z₁₂ = u₁ + v₂ = –76 + 10 = –66;

z₁₄ = u₁ + v₄ = –76 + 24 = –52;

z₂₁ = u₂ + v₁ = 8 + 19 = 27;

z₂₃ = u₂ + v₃ = 8 + 100 = 108;

z₂₄ = u₂ + v₄ = 8 + 24 = 32;

z₃₄ = u₃ + v₄ = 0 + 24 = 24;

z₄₂ = u₄ + v₂ = –16 + 10 = –6;

z₄₃ = u₄ + v₃ = –16 + 100 = 84.

Определим значения d_ij и проверим условия оптимальности d_αβ> 0

δ₁₁ = с₁₁ – z₁₁ = 70 – (–57) = 127 > 0;

δ₁₂ = с₁₂ – z₁₂ = 38 – (–66) = 104 > 0;

δ₁₄ = с₁₄ – z₁₄ = 92 – (–52) = 144 > 0;

δ₂₃ = с₂₃ – z₂₃ = 56 – 108 = –52 < 0;

δ₂₄ = с₂₄ – z₂₄ = 72 – 32 = 40 > 0;

δ₃₄ = с₃₄ – z₃₄ = 30 – 24 = 6 > 0;

δ₄₂ = с₄₂ – z₄₂ = 36 – (–6) = 42 > 0;

δ₄₃ = с₄₃ – z₄₃ = 121 – 84 = 37 > 0.

Так как d₂₃ < 0, то переходим к формированию нового плана.

3.Построим новый опорный план.

Для его построения строится фрагмент опорного плана (рис. 7) относительно клетки 2, 3 = α, β, т.к. потенциал в ней отрицательный δ₂₃ = δ_αβ < 0.

Рис. 7. Фрагменты плана:

а – фрагмент опорного плана; б – фрагмент нового плана

4. Определим значение целевой функции по новому плану (рис. 8).

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

Суммарные затраты по новому плану:

Y₁ = 14·24+19·18+1·56+23·19+3·10+7·3+34·8=1494 (усл. ед.).

Прежнее значение суммарных затрат составляло 1546 (усл. ед.).

Рассчитаем процент улучшения опорного плана:

D = 100%= 100 % = 3,36 %.

Проведем второй шаг оптимизации.

1. Составим и решим систему уравнений (1)

u₁ + v₃ = 24 = c₁₃;

u₂ + v₂ = 18 = c₂₂;

u₂ + v₃ = 56 = c₂₃;

u₃ + v₁ = 19 = c₃₁;

u₃ + v₂ = 10 = c₃₂;

u₄ + v₁ = 3 = c₄₁;

u₄ + v₄ = 8 = c₄₄.

При u₂ = 0, получим решение v₁= 27; v₂= 18; v₃= 57; v₄= 32; u₁= –32; u₂ = 0; u₃ = –8; u₄= –24.

2. Определим значения z_ij для клеток, в которые ресурсы не распределены.

z₁₁ = u₁ + v₁ = –32 + 27 = –5;

z₁₂ = u₁ + v₂ = –32 + 18 = –14;

z₁₄ = u₁ + v₄ = –32 + 32 = 0;

z₂₁ = u₂ + v₁ = 0 + 27 = 27;

z₂₄ = u₂ + v₄ = 0 + 32 = 32;

z₃₃ = u₃ + v₃ = –8 + 56 = 48;

z₃₄ = u₃ + v₄ = –8 + 32 = 24;

z₄₂ = u₄ + v₂ = –24 + 18 = –6;

z₄₃ = u₄ + v₃ = –24 + 56 = 32.

3. Определим значения d_ij и проверим условие оптимальности d_ij> 0.

δ₁₁ = с₁₁ – z₁₁ = 70 – (–5) = 75 > 0;

δ₁₂ = с₁₂ – z₁₂ = 38 – (–14) = 52 > 0;

δ₁₄ = с₁₄ – z₁₄ = 92 – 0 = 92 > 0;

δ₂₁ = с₂₁ – z₂₁ = 58 – 27 = 31 > 0;

δ₂₄ = с₂₄ – z₂₄ = 72 – 32 = 40 > 0;

δ₃₃ = с₃₃ – z₃₃ = 100 – 48 = 52 > 0;

δ₃₄ = с₃₄ – z₃₄ = 30 – 24 = 6 > 0;

δ₄₂ = с₄₂ – z₄₂ = 36 – (–6) = 42 > 0;

δ₄₃ = с₄₃ – z₄₃ = 121 – 32 = 89 > 0.

Так как все d_ij > 0, то данный план является оптимальным.

Окончательно представим оптимальный план перевозок (рис. 9, 10).

Рис. 9. Оптимальный план перевозок в форме графа

Рис. 10. Оптимальный план перевозок в форме матрицы

Таким образом, в пояснительную записку к расчетному заданию по теме: «Имитационные математические модели» должны входить следующие пункты.