 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
КОММЕНТАРИИ К ТЕОРЕМЕ О СХОДИМОСТИ СИМПЛЕКСНОГО ПРОЦЕССА
1. Признак неограниченности целевой функции.
Пусть при рассмотрении функции F на экстремум типа максимум на некотором шаге симплексная таблица приобрела вид:
| –х4 |  –х5
| ||
| х1 | –1 | ||
| х2 | –1 | ||
| х3 | –3 | ||
| F | –1 |
Из анализа таблицы видно, что есть возможность увеличить значение целевой функции за счет увеличения значения свободной переменной х4. Однако в соответствующем столбце нет положительных элементов, то есть рост переменной х4 не сдерживается базисными переменными. Так как х4 можно увеличивать неограниченно, то 
.
2. Признак наличия бесчисленного множества оптимальных планов
Пусть при исследовании функции F на экстремум типа максимум на некотором шаге симплексная таблица приобрела вид:
| –х4 | –х5 | ||
| х1 | |||
| х2 | –1 | ||
| х3 | |||
| F |
Из анализа таблицы следует 
Пример. Следующую задачулинейного программирования решить прямым симплексным методом. Решение проиллюстрировать графически.
Система ограничений данной ЗЛП совместна, Ω – область допустимых планов (рис. 11).
Рис. 11
Преобразуем ограничения-неравенства исходной ЗЛП в ограничения-равенства путем введения балансовых переменных х3, х4 ≥ 0:
Выделим базис неизвестных (х3, х4 – базисные, х1, х2 – свободные) и выразим базисные неизвестные через свободные:
Составим первоначальную симплексную таблицу:
| –х1 | –х2 | ||
| х3 | |||
| х4 | |||
| F | –2 | –3 |
В данной таблице записан первоначальный опорный план:
Геометрически этот план соответствует вершине 
многоугольника Ω.
Анализ первоначального плана показывает, что есть возможность увеличить значение целевой функции (улучшить план) за счет увеличения значений свободных неизвестных (два отрицательных элемента в строке линейной формы).
Будем увеличивать свободную переменную х1 (тем самым определяем разрешающий столбец). Так как в разрешающем столбце есть положительные элементы, то рост переменной х1 будет сдерживаться базисными переменными, в выражения для которых х1 входит со знаком «минус» 
.
По минимальному симплексному отношению (отношению свободного члена к положительному элементу разрешающего столбца) определим, какая из базисных переменных первой обратится в ноль:
Значит, первой обратится в ноль и перейдет в разряд свободных переменных базисная переменная х3 (этим определяется разрешающая строка на данном шаге жордановых исключений).
Новая симплексная таблица имеет вид:
| –х3 | –х2 | ||
| х1 | |||
| х4 | –1 | ||
| F | –1 |
В последней таблице записан улучшенный план:
Геометрически этот план соответствует вершине 
многоугольника Ω.
Наличие в строке линейной формы отрицательного элемента свидетельствует о том, что значение целевой функции F 1 не является оптимальным и его можно далее увеличить за счет увеличения свободной переменной х 2. Разрешающую строку определяем по минимальному симплексному отношению:
После одного шага Жордановых исключений получим новую симплексную таблицу
| –х3 | –х4 | ||
| х1 | –1 | ||
| х2 | –1 | ||
| F |
и новый опорный план
который геометрически соответствует вершине 
многоугольника Ω.
Последний опорный план является оптимальным, так в строке линейной формы нет отрицательных элементов и дальнейшее увеличение значения целевой функции невозможно:
Поиск по сайту: