9. Симплекс–метод при решении озлп.
Симплекс-метод явл-ся одним из способов решения ЗЛП. Идея последоват.улучшения решения легла в основу универсал.метода решения ЗЛП – с-м. Геометрич.смысл с-м состоит в последоват.переходе от одной вершины (первоначальной) многогранника огранич-й к соседней, в ктр лин.f-я принимает лучшее (не худшее) знач-е (по отношению к цели задачи) до тех пор, пока не будет найдено оптим.реш-е – вершина, где достиг-ся оптим.знач-е f-и цели (если задача имеет конечный оптимум). С-м – это вычислит.процедура, основанная на принципе последоват.улучшения решений при переходе от одной базисной точки (базисного решения) к др. При этом знач-е цел.f-и улучшается. Базисным реш-ем явл-ся одно из допустимых реш-й, нах-щихся в вершинах области допустимых знач-й. Проверяя на оптим-ть вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан с-м. С-м может быть найден на мах и min. 1.MAX. (Задача об использ-и ресурсов): имеются 2вида продукции P1 и P2, использ-ся 4вида ресурсов S1, S2, S3, S4. Необх-мо составить такой план произв-ва продукции, при ктр прибыль от ее реализации будет мах. 1)Необх-мо из сис-мы огранич-й, ктр выглядит в виде сис-мы нерав-в, сделать сис-му ур-ий (если «», то осн.пер-ные со знаком +, если «», то -). Д/этого придется ввести дополнит.неотриц.переменные. Опр-м, какие из переменных явл-ся осн., а какие – неосн. Пр-ло: в кач-ве осн.пер-ных на I шаге следует выбрать (если возможно) такие m-пер-ных, каждая из ктр входит только в 1 из m-ур-ий сис-мы огранич-й, при этом нет таких ур-ий сис-мы, в ктр не входит ни одна из этих пер-ных. Далее выражаем осн.пер-ные через неосн. Положив, неосн.пер-ные = 0, получим I базисное реш-е. 2)Составим сим.таблицу: а)исх.расширен.сис-му (в ктр выражали осн.пер-ные через неосн.) заносим в I сим.таблицу. Послед.строка таблицы, в ктр приведено ур-ие д/лин.f-и цели, наз-ся оценочной. В ней указыв-ся коэф-ты цел.f-и с противополож.знаком. В лев.столбце таблицы записываем осн.пер-ные (базис), в I строке таблицы – все пер-ные (отмечая при этом осн.), во II столбце – свобод.члены расширен.сис-мы
.
Последний столбец – д/оц.отнош-й, необх-мых при расчете наибольшего знач-я пер-ной. В рабоч.часть таблицы занесены коэф-ты
при
пер-ных из расширен.сис-мы. Далее
таблица преобраз-ся по опр.правилам. б)Проверяем выполн-е критерия оптим-ти. При реш-и задачи на мах – наличие в послед.строке отриц.коэф-тов. Если таких коэф-тов нет, то реш-е оптимально, т.е. достигнут мах. При этом
,
осн.пер-ные принимают значение
(II
столбец). Осн.пер-ные = 0, т.е. получено оптим.реш-е. Иначе, переходим к след.шагу. в)Если критерий оптим-ти не выполнен, то наибольший по модулю отриц.коэф-т в послед.строке таблицы опр-ет разрешающий столбец S. Составляем оц.отнош-я
кажд.строки по
след.правилам: а)
если
и
имеют разные знаки; б)
и
;
в)
;
г)0, если
и
;
д)
,
если
и
имеют
одинак.знаки. Опр-ем min
.
Если конечного min нет, то
задача не имеет конечного оптимума,
т.е.
.
Если min конечен, то выбираем
строку q, на ктр он достиг-ся
(если их неск-ко, то выбираем любую) и
назовем ее разрешающей строкой. На
пересечении разреш.столбца и разреш.строки
нах-ся разрешающий элемент
.
г)Переходим к
след.таблице по след.правилам: а)в лев.столбце записываем новый базис: вместо осн.пер-ных хq записываем хs; б)в столбцах, соотв-щих осн.пер-ным, проставляем: 1 – против «своей» осн.пер-ной, 0 – против «чужой» осн.пер-ной, 0 – в послед.строке д/всех осн.пер-ных; в)нов.строку с № q получаем из старой строки делением на разреш.столбец
;
г)все остальные пер-ные пересчитываем по правилу прямоугольника. Далее переходим к пункту 2.
2.MIN. Сначала также преобраз-ся сис-ма нерав-в в сис-му ур-ий, выражаем осн.пер-ные через неосн. Критерий оптим-ти при отыскании min лин.f-и: если в выраж-и лин.f-и через неосн.пер-ные отсутствуют отриц.коэф-ты при неосн.пер-ных, то реш-е оптимально. Смотрим, есть ли в итог.столбце (свобод.членов) отриц.знаки. Если да, то это явл-ся свидетельством того, что дан.план нельзя считать допустимым. Ликвидация отриц.чисел в итог.столбце начин-ся с наибольшего по абсолют.величине (это будет ключевая строка). Найдем ключ.столбец. Д/этого нужно эл-ты цел.строки разделить на эл-ты ключ.строки (оц.отнош-я) д/столбцов. Из получен.отнош-й выбираем наименьшее. На пересеч-и ключ.строки и столбца нах-ся ключ.эл-т. Далее все происходит также.