АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

КОММЕНТАРИИ К ТЕОРЕМЕ О СХОДИМОСТИ СИМПЛЕКСНОГО ПРОЦЕССА

Читайте также:
  1. I. Электрофильтры. Характеристика процесса электрической очистки газов.
  2. А у этого процесса были совершенно иные, политические корни, аналогичные тем, что формируются сегодня.
  3. Адресное пространство процесса в Windows 95/98
  4. Алгебра симплексного процесса при определении opt min
  5. Алюминотермическое восстановление оксидов металлов. Характеристики алюминотермического процесса.
  6. Анализ процесса изготовления рукавных пленок
  7. Анализ процесса рисования.
  8. Анализ эволюционной и революционной форм пол процесса.
  9. Аналитический обзор статей по теме «Социальные представления о субъектах образовательного процесса в условиях модернизации системы общего образования».
  10. Арабо-израильские отношения в 1990-е – начале 2000-х гг.: этапы и особенности переговорного процесса, проблемы урегулирования.
  11. Базовые и модифицированные логистические концепции управления процессами распределения
  12. Безопасность производственного процесса и оборудования

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      

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)