Материал: конспект 2

3. Разрешающий элемент всегда положительный.

4.Преобразование симплексных таблиц проводится в условиях прямодопустимости решений.

Решение прямодопустимо, если среди базисных переменных нет отрицательных.

5. Преобразование симплексных таблиц проводится до тех пор, пока в строке линейной формы F все коэффициенты станут неположительными (за исключением, быть может, самого значения линейной формы).

Определение opt max линейной формы

Необходимо определить max следующей линейной формы:

Первоначальное значение линейной формы F₀ = 3, .

На основе последней формы записи ЗЛП составим первоначальную жордановую таблицу

Новое значение линейной формы , новый план Этот план является отрицательным, так как в строке линейной формы F все элементы положительны и дальнейшее увеличение значения функции цепи невозможно. Таким образом,

Алгебра симплексного процесса при определении opt max

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

2. Разрешающая строка выбирается по минимальному симплексному отношению.

3. Разрешающий элемент всегда положительный.

4. Преобразование симплексных таблиц осуществляется в условиях прямодопустимости решений.

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

Условия сходимости симплексного процесса

Определение. ЗЛП называется невырожденной, если ни в одном из ее опорных планов среди базисных коэффициентов нет нулевых значений.

С точки зрения геометрии вырожденность ЗЛП можно трактовать как стягивание 2-х вершин многогранника в одну (рис. 5). Вырожденность, как правило, приводит к процедуре зацикливания процесса итераций.

Рисунок 5

Теорема (о сходимости симплексного процесса)

Пусть выполняются следующие условия:

1. ЗЛП невырождена.

2. Система ограничений ЗЛП имеет, по крайней мере, одно опорное решение.

3. Линейная форма F ограничена снизу при определении opt min и сверху при определении opt max.

Тогда симплексный процесс сходится за конечное число итераций.

Обычно при решении ЗЛП симплексными процедурами количество итераций R < 2 r (r – ранг системы ограничений ЗЛП).

Комментарий к теореме о сходимости симплексного процесса

1. Признак неограниченности целевой функции.

П усть при рассмотрении функции F на экстримум типа максимум на некотором шаге симплексная таблица имеет вид:

Из анализа таблицы видно, что есть возможность увеличить значение целевой функции за счет увеличения значения свободной переменной х₄. Однако в соответствующем столбце нет положительных элементов, то есть рост переменной х₄ не сдерживается базисными переменными. Так как х₄ можно увеличивать неограниченно, то .

2. Признак наличия бесчисленного множества оптимальных планов

Пусть при исследовании функции F на экстримум типа максимум на некотором шаге симплексная таблица приобрела вид:

Из анализа таблицы следует

Пример. Следующую задачу линейного программирования решить прямым симплексным методом. Решение проиллюстрировать графически.

Система ограничений данной ЗЛП совместна, Ω – область допустимых планов (рис. 6).

Рисунок 6

Преобразуем ограничения-неравенства исходной ЗЛП в ограничения-равенства путем введения балансовых переменных х₃, х₄ ≥ 0:

Выделим базис неизвестных (х₃, х₄ – базисные, х₁, х₂ – свободные):

Составим первоначальную симплексную таблицу:

В данной таблице записан первоначальный опорный план:

Геометрически этот план соответствует вершине многоугольника Ω.

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

Будем увеличивать свободную переменную х₁ (тем самым определяем разрешающий столбец). Так как в разрешающем столбце есть положительные элементы, то рост переменной х₁ будет сдерживаться базисными переменными, в выражения для которых х₁ входит со знаком «минус» .

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

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

Новая симплексная таблица имеет вид:

В последней таблице записан улучшенный план:

Геометрически этот план соответствует вершине многоугольника Ω.

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

После одного шага Жордановых исключений получим новую симплексную таблицу

и новый опорный план

который геометрически соответствует вершине многоугольника Ω.

Последний опорный план является оптимальным, так в строке линейной формы нет отрицательных элементов и дальнейшее увеличение значения целевой функции невозможно: