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

В процессе поиска оптимального решения задачи линейного программирования осуществляется переразрешение (5.1) так, что некоторые свободные (внебазисные) переменные х_j переходят в разряд базисных, а базисные переменные y_i – в разряд свободных, причем на каждой итерации производится замена одного базисного, а значит, и одного свободного переменного.

Процедура переразрешения модели необходима для того, чтобы осуществить переход от текущего опорного плана к более совершенному и, наконец, к оптимальному плану. Из канонической формы модели (см. пример 5.1) нетрудно видеть, что увеличение свободной переменной x₃ будет благоприятствовать минимизации критериальной функции, так как коэффициент при x₃ положителен. Перевод переменной x₃ в разряд базисных возможен за счет  превращения некоторой базисной переменной, например y₁ в разряд свободных. Процедура обмена местами свободной и базисной переменных в симплекс-таблице производится на основе ряда жестких правил.

Алгоритм обмена свободных и базисных переменных

1. Выделить разрешающий элемент а_ij вычислить его обратную величину l = 1/а_ij и записать в нижней части соответствующей клетки симплекс-таблицы (строка и столбец, которым принадлежит разрешающий элемент, называются разрешающими).

2. Все элементы разрешающей строки (кроме а_ij) умножить на l и результаты записать в нижних частях соответствующих клеток.

3. Все элементы разрешающего столбца (кроме а_ij) умножить на -lи результаты записать в нижних частях клеток.

4. Подчеркнуть в резрешающей строке все верхние (прежние) числа, кроме а_ij, а в разрешающем столбце все нижние (новые) числа, за исключением l.

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

6. Переписать таблицу, заменив базисное и свободное переменные своими местами; элементы разрешающих строки и столбца – числами, стоящими в нижних частях соответствующих клеток; каждый из остальных элементов – суммой чисел, находящихся в верхней и нижней частях тех же клеток.

7. Если в верхней строке нет ни одного положительного элемента с/|/ = 1,2, ... , то «конец»; иначе следует возвратиться к шагу 1.

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

Выделение разрешающего элемента при поиске начального опорного плана

1. Выбрать любое ограничение с отрицательным свободным членом.

2. Выбрать в этом ограничении любой отрицательный элемент и соответствующий ему столбец назвать разрешающим.

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

Выделение разрешающего элемента при наличии опорного плана

1. Выбрать разрешающий столбец путем выявления любого положи тельного элемента первой строки.

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

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

1. Построить математическую модель исследуемой операции в символической форме.

2. Сформировать модель в функциональной форме.

3. Ввести численную информацию и получить формализованную для конкретных условий математическую модель.

4. Выбрать предварительно базисные переменные предполагаемого начального опорного плана и переразрешить целевую функцию и ограничения относительно свободных переменных.

5. Представить математическую модель в канонической форме по Вентцель и заполнить стандартную симплекс-таблицу.

6. Если нет очевидного опорного плана, найти его, применив специальный мини-алгоритм выделения разрешающего элемента при поиске начального опорного плана.

7. Найти оптимальный план, используя основной алгоритм обмена свободных и базисных переменных.