Материал: 343

Удалив из первоначального множества выбранное ti, отыски-

индексу k (k =m,1). Просмотр tk следует проводить, начиная с m-й строки матрицы, т.е. k = m.

Вторым шагом является выбор двух ключевых столбцов. Ключевым будем называть столбец, в котором xij >0 или xk1 >0.

В первой выбранной строке (индекс i) в столбцах рассматриваются все значения xij >0, начиная с первого. Выбранному значению соответствует определенный столбец матрицы, который имеет номер. Этот номер присваивается индексу j (j = 1,n).

Во второй выбранной строке (индекс k) в столбцах рассматриваются все значения xkl > 0, начиная с m-го. Выбранному значению соответствует определенный столбец матрицы, который имеет номер. Этот номер присваивается индексу l (l = n,1).

Замечание. Перераспределение элементов в фазе 2 основывается на использовании двух строк и двух столбцов, и следует помнить, что i ≠ k и j ≠ l; выбор строк и столбцов следует делать для каждой новой итерации.

2. Вычисляем t:

р tj g ti , до тех пор, пока не выполняются условия:

×45 = 5 > 0 условия (1) и (2) выполняются. Обмен возможен.

3.Проводим корректировку элементной матрицы, проведя предварительно расчеты:

x11 = x'11 p' = 10 10 = 0; x66 = x'66 g = 5 1 = 4;

t1 = t'1 + t = 3 + 5 = 8;

x16 = x'16 + g = 0 + 1 = 1; x61 = x'61 + p' = 0 + 10 = 10;

t6 = t'6 t = 10 5 = 5.

20

Матрица имеет вид:

После обмена элементами в соответствующих строках и столбцах рассинхронизация t1 увеличилась на 5 единиц, а t6 уменьшилась на столько же единиц.

Затем проверяется возможность помещения элемента из (m + 1)-й строки в первую. Но уже очевидно, что такое помещение невозможно, так как tm+1 > t1 (45 > 8). Проводим следующую итерацию.

4.Выбираем две строки и два столбца, где i = 1, k = 6, j = 2, l = 6.

5.Вычисляем τ:

τ1 = 1 × 7 – 1 × 45 < 0; τ2 = 2 × 7 – 1 × 45 < 0;

…

τ7 = 7 × 7 – 1 × 45 = 4 > 0; τ8 = 8 × 7 – 1 × 45 = 11 > 0 не выполняется условие (2). 11>5.

Возврат к предыдущему шагу.

6. Проводим корректировку элементной матрицы:

t6 = t'6 – t = 5 4 = 1.

Матрица имеет вид:

21

7.Выбираем две строки и два столбца, где i = 1, k = 5, j = 2, l = 5.

8.Вычисляем .

τ1 = 1 × 7 – 1 × 18 < 0; τ2 = 2 × 7 – 1 × 18 < 0;

…

τ5 = 5 × 7 – 1 × 18 > 0; τ6 = 6 × 7 – 1 × 18 = 25 > 0 не выполняется условие (2). Возврат

кпредыдущему шагу.

9.Проводим корректировку элементной матрицы:

22

Так как tm+1 > t1 (45 > 29), продолжается решение задачи.

10.Выбираем две строки и два столбца, где i = 1, k = 3, j = 2, l = 5.

11.Вычисляем τ:

τ1 = 1 × 7 – 1 × 18 < 0; τ2 = 2 × 7 – 1 × 18 < 0; τ3 = 3 × 7 – 1 × 18 = 3 > 0;

τ4 = 4 × 7 – 1 × 18 = 10 > 0 не выполняется условие (2). Возврат

кпредыдущему шагу.

12.Проводим корректировку элементной матрицы:

13.Выбираем две строки и два столбца, где i = 1, k = 3, j = 2, l = 4.

14.Вычисляем τ:

τ1 = 1 × 7 – 1 × 15 < 0; τ2 = 2 × 7 – 1 × 15< 0;

τ3 = 3 × 7 – 1 × 15 = 6 > 0 поскольку τ3 = t3 (6 = 6), процесс вы-

числений завершается.

15. Проводим корректировку элементной матрицы: x12 = x'12 p' = 11 3 = 8; x34 = x'34 g = 8 1 = 7;

23

16.Выбираем две строки и два столбца, где i = 1, k = 2, j = 2, l = 3.

17.Вычисляем τ:

τ1 = 1 × 7 – 1 × 10 < 0; τ2 = 2 × 7 – 1 × 10 = 4 > 0; τ3 = 3 × 7 – 2 × 10 = 1 > 0;

τ4 = 4 × 7 – 2 × 10 = 8 > 0 условие (2) не выполняется; τ5 = 5 × 7 – 3 × 10 = 5 > 0 условия (1) и (2) выполняются. 18. Проводим корректировку элементной матрицы:

24