Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Этапы симплекс-метода




1. Проверка признака оптимальности ( )

2. Если есть , то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.

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

4. Текущая симплекс-таблица преобразуется по следующему правилу:

· разрешающая строка делится на разрешающий элемент:

· разрешающий столбец заменяется единичным.

· все остальные элементы симплекс-таблицы могут быть пересчитаны по правилу четырехугольника:

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

Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.

Замечание: Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.

Варианты разрешимости задачи линейного программирования

Теорема 5: “О возможности увеличения критерия”.

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

Для построения такого плана положим , тогда

(15)

Существует такое малое , что все базисные компоненты неотрицательны, то есть решение допустимое.

 

Теорема 6: “О возможности построения нового опорного плана”.

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

,

Действительно, построив план вида (15) и увеличивая , заметим, что по крайней мере одна базисная переменная уменьшается. Когда одна из уменьшающихся базисных переменных обратится в 0, получим новый опорный план с лучшим значением критерия.

 

Теорема 7: “Условие неограниченности критерия”.

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

Действительно, решение вида (15) остается допустимым при любом :

, а критерий неограниченно растет



 

Теорема 8: “Признак альтернативного оптимального решения”.

Пусть – невырожденный оптимальный план (выполняется признак оптимальности , ), и существует оценка свободной переменной . Тогда оптимальный план не единственный и существует другой план с таким же значением критерия , .

Действительно, на планах вида (15) критерий не изменяется, значит, все эти планы оптимальны.

В таком случае оптимальные решения находятся на отрезке , .

 


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал