ИТЕРАЦИЯ 2

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х₁ Х₂ Х₃ Х₄ Х₅

Х₂ =

2000 0 0 20000 5000

и соответствующее ему значение целевой функции:

Z₂ = 1500 * 2000 + 500 * 0 + 0 * 0 + 0 * 20000 + 0 * 5000 = 3000000

ШАГ 2. Проверяем оптимальность полученного решения.

Примечание 6. Можно сформулировать следующее правило, упрощающее расчеты на шаге 2: “Изменения базисных переменных равны соответствующим коэффициентам из столбца испытуемой небазисной переменной, взятым с противоположными знаками”.

Пусть Δ Х₂ = 1

Тогда Δ Х₁ = - 1

Δ Х₄ = -36

Δ Х₅ = - 7

Δ Z₂ = 1500 * (-1) + 5000 * 1 + 0 * 0 + 0 * (-36) + 0 * (-7) = 3500 > 0

Вывод: Решение Х₂ неоптимальное. Переменную Х₂ целесообразно ввести в базис, поскольку от этого значение целевой функции Z увеличится

ШАГ 3.Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Значение переменной Х₂ нельзя увеличивать до бесконечности, а только до такой величины, которая будет удовлетворять условиям неотрицательности переменных:

Х₁ > 0 , Х₄ > 0 , Х₅ > 0 (5)

Определим значение Х₂ из следующих соотношений, полученных на основе системы уравнений (4), при условии, что Х₃ = 0:

Х₁ = 2000 - Х₂ 2000 - Х₂ > 0 Х₂ < 2000

Х₄ = 20000 - 36Х₂ => 20000 - 36Х₂ > 0 => Х₂ < 555 -- (*)

Х₅ = 5000 - 7Х₂ 5000 - 7Х₂ > 0 Х₂ < 714 –

Для выполнения условий (5) необходимо, чтобы выполнялось условие:

Х₂ = 555 --

Данное значение Х₂ получилось во втором уравнении. Это означает, что замена базисной переменной должна произойти во втором уравнении задачи (4), т.е. Х₂ станет базисной, а Х₄ выйдет из базиса.

Окончательно делаем вывод: в новом базисе будут находиться переменные:

Х₁, Х₂, Х₅.

Примечание 7.Для простоты расчетов можно на третьем шаге выполнить более простые преобразования. Для этого правые части уравнений разделить на коэффициенты при вновь вводимой в базис переменной и выбрать меньшее отношение.

Так, Шаг 3 (Итерации2) можно записать более компактно, т.е.:

Определяем, какая из прежних базисных переменных должна быть выведена из базиса. Для этого найдем отношения:

2000 : 1 = 2000

20000 : 36 = 555--- (*)

5000 : 7 = 714---

Меньшее значение получилось во втором уравнении. Это означает, что замена базисной переменной должна произойти во втором уравнении задачи (4), т.е. Х₂ станет базисной, а Х₄ выйдет из базиса.

Окончательно делаем вывод: в новом базисе будут находиться переменные:

Х₁, Х₂, Х₅.

ШАГ 4.Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Преобразуем систему уравнений (4) так, чтобы во второе уравнение новой системы (6) переменная Х₂ вошла с коэффициентом +1, и отсутствовала бы в двух других.

Для этого:

1. Получим второе уравнение новой системы (6). Для этого второе уравнение системы (4) почленно разделим на 36 и коэффициент при Х₂ станет равным +1:

1 1 5

X₂ -- -- Х₃ + -- Х₄ = 555 --

9 36 9

2. Исключим переменную Х₂ из первого уравнения системы (4).

Для этого вычтем из первого уравнения системы (4) второе уравнение системы (6):

Х₁ + Х₂ + Х₃ = 2000

1 1 5

Х₂ - -- Х₃ + --- Х₄ = 555—

9 36 9

10 1 4

Х₁ + ---Х₃ - --- Х₄ = 1444---

9 36 9

Это будет первое уравнение новой системы (6).

3. Исключим переменную Х₂ из третьего уравнения системы (4).

Для этого вычтем из третьего уравнения системы (4) второе уравнение системы (6), умноженное почленно на 7:

7Х₂ - 2Х₃ + Х₅ = 5000

--

7 7 35000

7Х₂ - -- Х₃ + --- Х₄ = ----------

9 36 9

11 7 1

- -- Х₃ - --- Х₄ + Х₅ = 1111----

9 36 9

Это будет третьеуравнение новой системы (6).

После преобразований новая система уравнений будет иметь вид:

10 1 4

Х₁ + -- Х₃ - -- Х₄ = 1444--

9 36 9

1 1 5

Х₂ -- -- Х₃ + -- Х₄ = 555-- (6)

9 36 9

11 7 1

-- --Х₃ - -- Х₄ + Х₅ = 1111--

9 36 9