презентация_Л2-3

ЭТАП 2

Оптимальное решение ищется последовательным преобразованием симплексной таблицы в соответствии с алгоритмом (9).

В качестве исходной берется таблица, соответствующая опорному решению, полученному на Этапе 1 (в такой таблице si0 0, i 1, m).

Для отыскания разрешающей строки и разрешающего столбца проводится анализ строки таблицы (m+1), соответствующей ЦФ F:

Если в этой строке есть положительные элементы, то решение может быть улучшено (значение F может быть уменьшено), если сделать положительной (ввести в число базисных) ту переменную, у которой положительный элемент в строке (см. последнее уравнение (8)). Вместо нее следует ввести в число свободных ту переменную, которая первой обратится в нуль при увеличении новой базисной переменной.

Если в строке m+1 таблицы, соответствующей ЦФ F, нет ни одного положительного элемента (не считая свободного члена), т.е. sm 1 , j 0, j 1, n m, то получаемое из этой таблицы решение оптимально.

Если в строке m+1 есть положительный элемент sm 1, k 0, а в столбце k нет ни одного положительного

элемента sik 0, i 1, m, то функция F не ограничена снизу и оптимального решения не существует.

Если в столбце k , определяемом условием sm 1, k 0,

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

ние si0 / sik , т.е. 0 sr 0 / srk si0 / sik , i 1, m, sik 0.

Переменная, соответствующая строке r, переводится из базисных в свободные, а переменная, соответствующая столбцу k , из свободных – в базисные. После преобразования симплексной таблицы анализ строки F повторяется.

Для контроля правильности вычисления можно подставить решение, получаемое из таблицы (свободные переменные, соответствующие столбцам таблицы, равны нулю, а базисные, соответствующие строкам – свободным членам, т.е. элементам нулевого столбца si 0 , i 1, m), в исходные уравнения задачи ЛП.

После каждого преобразования симплекс-таблицы значение ЦФ не должно возрастать, а базисные переменные должны оставаться неотрицательными.

Пример 1

F x2 x1 min

x1 2x2 x3 22x1 x2 2

x1 x2 5 x1, x2 , x3 0

Каноническая форма задачи ЛП Введем фиктивные переменные x4, x5:

Пусть

x3, x4, x5 – базисные переменные x1, x2 – свободные переменные (=0) Тогда

F (x1 x2 ) min

x3 2 (x1 2x2 )

x4 2 ( 2x1 x2 )x5 5 (x1 x2 )

x1, x2 , x3 0

Исходная симплекс-таблица

В столбце свободных членов есть отрицательный (–2), т.е. недопустимое решение:

x1 = x2 = 0, x3 = 2, x4 = –2, x5 = 5

В строке x4 ищем первый отрицательный элемент: –2 (столбец x1):

x1 – разрешающий столбец