XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 16
Текст из файла (страница 16)
Рассмотрим задачу линейного программиро- вания или в стандартной форме (у2 — хы у2 — — х2, а уз, у4, уб — новые переменные) В данном случае в качестве начального можно использовать т допустимое базисное решение У = (О 0 4 2 5), которому соответствует значение целевой функции 2 = О. Тогда Уз, У4~ Уб базисные переменные. Мы можем заполнить первую симплекс- таблицу, соответствующую нулевой итерации симплекс-метода (табл. З.З).
3. СИМПЛЕКС-МЕТОД 108 Таблица 3.3 Таблица Я.б (4 2 51 (2' 1' 11 Таблица о4 Рис. 3.4 Наибольшая положительная симплекс-разность равна 3, т.е. новым базисным переменным является у1. А так как все элементы столбца, соответствуюшего переменному уы являются положительными, то Это число соответствует двум базисным переменным: уз и ул. Следовательно, возможны два варианта реализации симплекс- метода. Вариант 1.
Выводим старое базисное переменное уз. Этому варианту соответствуют симплекс-таблицы, представленные в табл. 3.4. з.. .—. Симплекс-метод при известном допустимом овзисном решед 109 Вариант 2. Выводим старое базисное переменное у4. Этому варианту соответствуют симплекс-таблицы, представленные в табл.
3.5. О1 2,—,=4 О2 х~ — 2и =2 Оз,+,=в О4 х1=о Ов я=а Оптимальному решению У = (3 2 0 3 О) соответствует значение целевой функции 1 = 7 (см, рис. 3.4). Заметим что при реализации как первого, так и второго вариантов З.г. Симплекс-метод при известном допустимом базисном решении 111 3, СИМПЛЕКС-МЕТОД 110 при первой итерации (см. табл.
ЗА и 3.5) новое допустимое т базисное решение У = (2 0 0 0 3) является вырожденным н соответствует (см. рис. 3.4) крайней точке (2;0) множества С допустимых решений. Более того, при реализации варианта 2 новые допустимые базисные решения при первой и второй итерациях являются не только вырожденными, но и совпадают (см.
табл. 3.5). Вырожденность является следствием переопределенностн крайней точки (2; 0) множества С допустимых решений, в которой пересекаются три прямые (см. рис. 3.4), соответствующие ограничениям рассматриваемой задачи, в то время как для задания крайней точки множества С на плоскости достаточно двух прямых.
Переопределенной крайней точке множества допустимых решений соответствуют два аспекта: 1) одно или несколько ограничений являются избыточными. Если избыточным является 1-е ограничение, то его можно снять, не изменяя при этом множество допустимых решений.
Это означает, что использование 1-го ресурса для достижения поставленной цели не является обязательным. Подобнзл информация может оказаться весьма полезной при практическом использовании результатов исследований; 2) в общем случае при реализации симплекс-метода возможно циклическое повторение операций, не улучшающих значения целевой функции и не приводящих к завершению вычислений (см. табл. 3.5, итерации 1 и 2). Но при практическом использовании симплекс-метода, как показывает опыт, такое маловероятно. В заключение рассмотрим пример задач линейного программирования, для которых оптимальное решение не является единственным, т.е.
целевая функция достигает своего максимального значения на некотором подмножестве множества допустимых решений. Элементы этого подмножества называют алътпернатпивными оптпимальными решениями. Пример 3.8. Рассмотрим. задачу линейного программиро- вания Дхы хг) = 2хг + 4хг -+ шах; хт+2хг (5, хт+хг < 4, х1 >~ О, хг > О, или в стандартной форме 2У1+ 4уг -+ тпах; Уг + 2уг+ Уз = 5, уь>0, 1с=1,4, ут + уг + У4 = 4, где ут — хг уг = хг, а уз и У4 — новые переменные. В качестве начального базисного решения можно использовать вектор т У = (О 0 5 4), которому соответствуют базисные переменные модели уз, У4 и значение целевой функции у = О. В данном случае оптимальное решение не является единственным (рис. 3.5), так как любая точка отрезка АВ соответствует оптимальному решению.
Выясним, как проявляется специфика рассматриваемой задачи при ее решении симплекс- методом. В табл. З.б приведены симплекс-таблицы двух первых итераций симплекс-метода. Видно, что оптимальному решению Рис. З.б 112 З. СИМПЛЕКС-МЕТОД Таблица 3.6 аслхь Е я=1 и асяхь в=1 Е' асьхя ь=1 < Ь;, еЕ11,' 1 Е 1з, 35, е61з, Таблица Я 7 ~) пряхе я=1 Е а;ьхь я=1 и ~> асвхя +уолл =5;, 1Е 11,' +О д„+;=5;, 1й 1з,' у+'=б, тб 1з. т У" = (О 5/2 0 3/2) соответствует точка А множества С допустимых решений (см. рис. 3.5) и значение целевой функции /= 10. В последней строке табл. 3.6 симплекс-разность, соответствующая свободному переменному модели уы равна нулю. Следовательно, включение у1 в число базисных переменных не может привести к изменению значения целевой функции, но может привести к нахождению нового оптимального решения.
Из соответствующей симплекс-таблицы (табл. 3.7) видно, т что новое оптимальное решение У и = (3 1 0 0) соответствует крайней точке В множества С (см. рис. 3.5) и значению целевой функции /= 10. Таким образом (см. теорему 3.5), /= 10 и ва выпуклой комбинации Хл = ЛХ,*+ (1 — Л)Х* оптимальных решений Х1* —— (О 5/2) и Х~ — — (3 1), 0 < Л < 1, вектор Х~ является оптимальным решением. 4 Информация о наличии альтернативных оптимальных решений является очень полезной при решении практических задач, так как „лицо, принимающее решения", получает возможность З.З.
Нахождение допустимого базисного решения 113 выбора альтернативного варианта, в наибольшей степени отве- чающего сложившейся ситуации, и при этом нет необходимости исследовать изменения целевой функции. 3.3. Нахождение допустимого базисного решения В задаче линейного программирования (2.1) множество допусгпимых решений определяется системой ограничений с дополнительным условием неотрицательности переменных модели. Три множества индексов 1ы 1о, 1з попарно не пересекаются и в совокупности составляют все множество индексов от 1 до тп включительно. Можно считать, что 5; > О, 1= 1, т, так как в противном случае соответствующее неравенство можно умножить на — 1. Переходя к задаче линейного программирования в стандартной форме, полагают иь = хь, Й = 1, и, и в каждое е-е ограничение вводят новое неотрицательное переменное у„+;.
В результате система ограничений преобразуется к следующему виду: 3, СИМПЛЕКС-МЕТОД 114 сьуь -+ шах; Е 1=1 асяул+ у„+1 — Ь;, Е 1=1 1611, л асяуЬ=Ь;, 1Е 12, Ьж1 (3.24) атяуь — У +; — — Ь„еб 73, Е 1с=1 УЬ)0, Й=1тП+т2. ) О, 1672т тл-тлт аыуь+у„ье — — Ь,, 1 Е 71, Е 1=1 (3.25) л — 1 т и+еп2+еп — сп1. уь > О, Если 72 = 6 = О, т.е. 11 — — (1, 2, ..., сп1, то вектор у =(о ... о ь, ... ь )'ек"'" вида (3.10) является допустимым базисным решением рассматриваемой задачи и его можно использовать в симплекс-мсп1оде в качестве начального базисного ресаенил (см. 3.2).
При этом базисным переменным модели у„+1, 1 = 1, 1п, соответствуют столбцы единичной матрицы 7, являющейся одним из блоков матрицы ограничений А. Именно этот прием нахождения начального базисного решения был использован в примерах 3.4, 3.5 и 3.7. Если в задаче (2.1) не является пустым или множество 12, или множество Гз, то новое переменное у„+1 войдет в систему ограничений с коэффициентом (см. пример 3.2), и в этом случае вектор вида (3.10) не приведет к допустимому базисному решению.
Понятно, что прн решении таких задач линейного программирования могут возникнуть значительные трудности, связанные с нахождением начальных базисных решений. Рассмотрим один иэ возможных методов поиска начального базисного решения, основанный на использовании искусспзвеккык переменкык модели, т.е. переменных, которые не имеют отношения к содержательной постановке рассматриваемой задачи.
Идея использования искусственных переменных для нахождения начального базисного решения задачи линейного программирования достаточно проста и заключается в следующем, Пусть в соотношениях (2.1) Ь; > О, 1 = 1, т, и для определен- ности 71 — — (1, ..., т1)т 13=(п11+1,, п221т 12=(™2+1 " сп)т где 1 < т1 < т2 < т. Полагают уь = ге, 1= 1, и, вводят новые пеРеменные Уь, /с = п+1, и+тзт и пеРехоДЯт к слеДУющей заДаче 3.3.
Нахождение допустимого базисного решенив 115 линейного программирования в стандартной форме: Каждое новое переменное у„+1, 1 = 11, спз, входит лишь в одно ограничение После этого вводят т — п11 искусственных переменных у, ,~ = п+т2+1, п+п12+т — т1, и рассматривают вспомогагелег ную задачу линейного программирования: ср(утс+тлт+1т ' ' т Ул+тлз+лт-лтт ) = ~Л~ Ул+тлз+1 1=1 л Е асяуь+ У„+~,+;, = Ь;, 1 Е 72, /сж1 атьУь Уст+с + Уст+ест+т-тл, = Ьтт 1 с 7зт Е л=1 116 3. СИМПЛЕКС-МЕТОД 117 Зу4 + 4уг -4 шах; Уг + Уг + уз = 20, — У4 + 4уг + У4 — — 20, Уг — ув = 10, Уе+шг4- -т — 51, 4 'е 1г 0 13. уе+ — — 5;, 4614, (3.26) Уг Ув = 5, Ул > О, к = 1, 6. ~Р(УО",Ув) = — Уу — Ув 4 шах; У1 + Уг+ Уз = 20, — уг+4уг+У4 = 20, (3.27) У4 — Ув + Уг = 10, Уг — Ув + Ув = 5, уь > О, й= 1,8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
