Правило прямоугольника

Правило прямоугольника применяется в методе Жордана-Гаусса.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Назначение сервиса. Онлайн-калькулятор Правило прямоугольника предназначен для пересчета таблиц методом жордановских преобразований.

Выберите размерность таблицы. x

Правило прямоугольника

Примечание. Данный метод не стоит путать с формулой прямоугольников.

Пример №1. Производится пересчет элементов новой симплекс-таблицы. Каким будет значение элемента x25 в новой симплекс-таблице, если до пересчета x25 = -3 , x27 =5 , х45 = -8 , х47 =2

Решение.
x25 =x25 - x45*x27/x47 = -3 - (-8)*5/2 = -3+20 = 17

Пример №2. По приведенной ниже симплекс-таблице определите, является ли соответствующее ей базисное решение оптимальным. Если решение не является оптимальным, осуществите пересчет таблицы.

  ПЧ X3 X4
F -5 2 -1
X1 4 2 1
X2 3 1 2

Решение.
Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Поскольку X1 = 4 > 0, X2 = 3 > 0, то это допустимое базисное решение. Определим, является ли оно оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить. В индексной строке X4 = -1 < 0, поэтому план не является оптимальным. Осуществим пересчет таблицы.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:  min (4:1 , 3:2 ) = 11/2
Следовательно, 2-ая строка является ведущей. Вместо переменной x4 в план войдет переменная x2.
Таблица 1

  ПЧ X3 X4
F -5 2 -1
X1 4 2 1
X2 3 1 2

Разрешающий элемент РЭ=2. Строка, соответствующая переменной x2 , получена в результате деления всех элементов строки x на разрешающий элемент РЭ=2 (см. табл.2) . На месте разрешающего элемента получаем 1. В остальных клетках столбца x2  записываем нули. Все остальные элементы, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ (см. табл.2).
Формируем таблицу.

Таблица 2

4-(3 • 1):2 2-(1 • 1):2 1-(2 • 1):2
3 : 2 1 : 2 2 : 2
-5-(3 • -1):2 2-(1 • -1):2 -1-(2 • -1):2

Получаем новую таблицу:

Таблица 3

  ПЧ X3 X2
F -31/2 21/2 0
X1 21/2 11/2 0
X4 11/2 1/2 1

Поскольку X3≥0, X2≥0, то получили оптимальный план.

Пример №3. Решить задачу линейного программирования симплекс-методом, используя в качестве начальной угловой точки:
f(x) = -2x1 + x2 + 4x3 – x4 – x5 → min
x2 + 2x4 – x5 = 1
x1 - x4 – x5 = 1
2x2 + x3 + 2x5 = 4
xj ≥ 0, j=1,..,5, x0 = (1;1;2;0;0)

Решение.
Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1).
0x1-1x2 + 0x3-2x4 + 1x5 = -1
-1x1 + 0x2 + 0x3 + 1x4 + 1x5 = -1
0x1-2x2-1x3 + 0x4-2x5 = -4
F(x) = 2x1 - x2 - 4x3 + x4 + x5

Затем систему ограничений преобразуем методом Гаусса-Жордана к такой форме, чтобы базисными стали переменные x1, x2, x3, а вектор b = (1, 1, 2)T


-1
0 -1 0 -2 1
-1 -1 0 0 1 1
-4 0 -2 -1 0 -2
0 -2 1 4 -1 -1

Итерация №1. Разрешающий элемент РЭ=-1.
Формируем таблицу.
Строка, соответствующая переменной x2 , получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2  записываем нули. Все остальные элементы, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую таблицу:
-1 0 -1 0 -2 1
1 1 0 0 -1 -1
-4 0 -2 -1 0 -2
2 0 1 4 -3 -3

Итерация №2. Разрешающий элемент РЭ=-1.
Строка, соответствующая переменной x4, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x4  записываем нули.
Все остальные элементы, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую таблицу:

-1 0 -1 0 -2 1
1 1 0 0 -1 -1
4 0 2 1 0 2
-14 0 -7 0 -3 -11

Итерация №3. Разрешающий элемент РЭ=-1. Строка, соответствующая переменной x3 , получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=-1. На месте разрешающего элемента получаем 1.  В остальных клетках столбца x3  записываем нули. Все остальные элементы, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую таблицу:

1 0 1 0 2 -1
1 1 0 0 -1 -1
2 0 0 1 -4 4
-7 0 0 0 11 -18

Далее необходимо переназначить переменные и решать симплекс-методом.

загрузка...