Файл: Материалы по курсу (часть 1).docx

7) Элементы разрешающей строки и разрешающего столбца заполнить числами, стоящими в нижних частях ячеек (новыми элементами).

8) Каждый из оставшихся, заменить суммой чисел, стоящих в нижних и верхних частях ячеек.

Пример (из лекции за 10.03)

1) Перепишем систему уравнений

2-3) Введем обозначения (-a_ij = α_ij), и построим таблицу

4) Произведем замену переменных x₁ ↔ у₂

5) Выделим разрешающий элемент α₂₁ и вычислим λ (жирными линиями показан) Элемент выделен красным

6) Все элементы разрешающей строки (кроме α₂₁) умножаем на λ и результат записываем в нижних частях ячеек. Новые элементы выделены желтым.

7) Все элементы разрешающего столбца умножаем на (-λ) и также записываем в нижней части ячеек, также не трогая разрешающий элемент.

8) Выделяем (обводим) в разрешающей строке все верхние числа (прежние элементы), а в разрешающем столбце – нижние (новые), за исключением разрешающего элемента. Ячейки закрашены розовым цветом.

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

10) Переписываем таблицу, заменяя x₁ ↔ у₂. Элементы разрешающей строки и разрешающего столбца заполняем числами, стоящими в нижних частях ячеек (новыми элементами). Каждый из оставшихся, заменяем суммой чисел, стоящих в нижних и верхних частях ячеек

8. Отыскание опорного решения задачи лп на основе табличного алгоритма замены переменных.

Отыскание опорного решения (ОР) – т.е. попутно выясняется, имеет ли вообще данная задача допустимые (неотрицательные) решения.

Пусть имеется ОЗЛП с ограничениями-равенствами, в следующей форме

y₁  b₁  (₁₁x₁ ₁₂x₂  ..._1nx_n );

...

y_m  b_m  (_m1x₁ _m2x₂  ..._mnx_n ).

Первое пробное решение x₁  x₂  ... x_n  0.

Если все b_i  0 , то это допустимое решение. Следовательно, оно опорное.

Если какие-либо b_i  0 , то это решение не допустимое и не опорное.

Для нахождения ОР нужно шаг за шагом обменивать базисные и свободные переменные пока не найдем его, либо убедимся, что система уравнений несовместима с неравенствами x₁  0, x₂  0,..., x_n  0; y₁  0, y₂  0,..., y_m  0.

Очевидно, нужно так обменивать базисные переменные со свободными, чтобы эта

процедура приближала нас к границе ОДР, т.е. чтобы число отрицательных свободных членов уменьшалось или при том же числе убывали их абсолютные величины.

Способ выбора разрешающего элемента для приближения к опорному решению

Пусть имеется одно из уравнений с отрицательным свободным членом.

Ищем в этой строке отрицательный _ij. Если они все положительные

(значит все a_ij 0)), данная базисная никогда не будет положительной.

Выберем столбец, в котором находится отрицательный _ij , в качестве разрешающего столбца.

Рассмотрим только те элементы столбца, которые имеют один знак со свободным членом. Выберем из них тот в качестве разрешающего элемента, для которого отношение к нему свободного члена минимально (свободный член/коэффициент при x).

Пример

Найти опорное решение задачи ЛП

y1 1 (x1  2x2  x3);

y2  5 (2x1  x2  x3);

y3  2  (x1  x2);

y4 1 (x2  x3).

Св. член равен -5 – это плохо!

; - это для строки y₂ - это для строки y₃

2<. Производим замену y₃  x₁ , получаем