341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 52
Текст из файла (страница 52)
Таблица 3.5 2. На место опорного элемента поставить 1. 3. На остальных местах разрешаюшей стропи записать соответствующие элементы исходной таблицы. 4. На свободные места разрешаюшсго столбца поставить соответствуюшие элементы исходной таблицы, взятые со знаком минус. 5. На оставшиеся свободные места элементов с<~ ), >3~, р( в новой симплекс-таблице записать числа ц;, >э„р„найденные следуюшим образом: <тм =ям .ои -ць .цл А=жы А — ж( А — (о> (о> (о> (о> — (о> (о> (о> (о) Для упрошения вычислений по этим формулам их можно сформулировать в виде <правила прямоугольника<; с<„(, аа,, г<;,, г<,( (или оь(, ()ь, ()<, с<ц, или с<м, оьу, р, р ) перемножзются (причем (а) (о) (о> (о> (о) (о) (о> (а> 3 3. Линейное программирование 369 дроизведсние,не содержащее опорного элемента ам, берется со знаком 00 минус) и полученные произведения складываются.
6. Все полученные элементы новой таблицы разделить на опорный 00 элемент ом (это можно делать и непосредственно после выполнения операций каждого из п. 2-5). Пример 6. Решить задачу линейного программирования из примера 5 симплекс-методом, используя в качестве начальной угловой точки и1ч1 базисное решение, соответствующее свободным переменным х~ и хэ. а Столбцы с номерами 2, 4, 5 и 6 матрицы А системы ограниченийравснств данной задачи обраауют базисный минор (проверьте!). С помощью эквивалентных преобразований приводим эту систему к виду (16), где базисными являются переменные хэ, хэ, хэ и хв.
хэ +х~ +ха =40 хэ + х~ —— 20 хэ — х, — хэ = 10 хв + хэ = 30. (23) Дх) = 880 — 7х, — 14хэ. (24) С помощью равенств (23) и (24) составляем симплекс-таблицу, соответствующую угловой точке х~о~: Среди коэффициентов р, у ф О, из (19) есть отрицательные — это <о) элементы — 7 и — 14 последней строки симплекс-таблицы. Следовательно, угловая точка к~о~ не является решением задачи. Полагая в равенствах (23) свободные переменные х~ и хэ равными нулю, находим хэ = 40, хэ = 20, хэ = 30, т.е, базисное решение и~о> = (О, 40, О, 20, 10, 30). Так как все базисные переменные в к~о~ положительны, данное базисное решение является допустимым (т. е.
угловой точной) и невырожденным. Исключив с помощью (23) базисные переменные в выражении для деленой функции, получим Гл. 17. Методы оптимизации 370 00 Для каждого из отрицательных элементов р,. среди соответствующих коэффициентов аб из (16) (т. е. элементов симплекс-таблицы, сто- 00 00 яших в том же столбце, что и р ) есть положитсльные, значит, возможен переход к новой угловой точке хО~ с меньшим значением /(х). Найдсм разрешаюший элемент. В качестве опорного можно взять любой из столбцов таблицы, соответствующих свободным переменным хд и хз. Выбсрем, например, столбец при свободной переменной хз. Разрешающую строку находим в соответствии с (20): так как пнп(40/1, 30/1) = 30/1, то разрешаюшей является строка, соответствующая базисной переменной хэ.
Итак, опорный элемент найден, в симплекс-таблице он обведен рамкой. Заполнив новую симплекс-таблицу по правилам, описанным вышс, получим Отметим, что значение /(х) в новой угловой точке умсньшилось по сравнению со значением в исходной: 460 вместо 880 (см. элементы в правых нижних углах симплекс-таблиц). В нижней строке последней таблицы есть отрицательный элемент — 7, стояший в столбце при свободной переменной хс.
Кромс того, в этом столбце имеются положительные элементы, поэтому возможно дальнейшее уменьшение /(х) с помощью очередного шага симплекс-метода, На данном шаге выбор опорного столбца однозначсн и определяется отрицательным элементом — 7 последней строки. Разрешающая строка находится из условия (20): так как оп(10/1, 20/1) = 10/1, то это строка при базисной переменной хэ.
Опорный элемент в последней таблице обведен рамкой. Как и на предыдушем шаге, находим очередную симплекс-таблицу по обшим правилам: 3 3. Линейное программирование 371 В этой гимплскс-таблнцс оба коэффнци< нта р,, у ф О. в поглслш й (2! строке положптсльны. Поэтому углован точка х(2<, соотвстстэунш!ан свободным псрсмснным т2 и хэ, пвлястсл точкой мшшмума цслевой функции Дх): х" = к(~! = (10; 0; 30; 10; 50; 0).
1(шшь<альнос значение у(х) со знаком минус записано в правом нижнем углу симплекс-таблицы, поэтОМу !* = 390, Сравните эти результаты с рсшснисм той <ко Зада ш, получснным графическим методам, см. пример 5. > Замечанис. Если задача линсйного программировании (3)-(5) выроа<дона, то возможны холос<лые шаги симплекс-метода, т.с. шаги, в результате которых значсние целсвой функции нг измсннстса. При атом теоретически возможно и зацикливание, т.с. бссконсчнос повторение холостых шагов. Для того чтобы избсжать зацикливания, разработаны специальные алгоритмы (антицикликь<). Однако на практике зацикливание происходит крайне редко, поэтому антициклины мы здесь не рассматривасм.
Решить задачи линейного программирования 17.207 17.212 симплскс-мвтодом, используя х ° в качсствс начальной угловой (о< точки: 17.207. Дх) = — 5Х< + 4хэ — хэ — Зхз — бхэ — ! пцп, ЗХ! — хз + 2х,< + хэ = 5, 2Х< — Зхз+ха+ 2х4+ ха = 6, Зх.< — хэ + тз + Зх,< + 2хэ = 9, х . > О, у = 1, ..., 5; х(о) = (О, О, 1, 2, 1). 17.208. Дх) = — х< — хэ — хз — х4 + 4хэ — <шш, Зх< + хг + тз — бхэ = 7; 2Х< + хэ + Зхэ + Зх4 — 7хэ = 10, — Зх! + хэ + хз — бх4 = 1, х,>0, у'=1,...,5; х(о)=(1 2 2 0 0) 17.209.
~(х) = 2х<+ Х2+ ха + 7х4 — 2хэ — э пнп, .Х!+Хэ ХЗ+Х4 = 1< 2Х! + хг+ ха — хэ = 7, х.< + 2хэ + хз — 7х4+ хэ = 6 х >О,у=1,...,5;х(о)=(2;1;2;0;0). 17.210. у(х) = х< — Зхг — Зхз+ бх4+ Зхэ — у шш — 2х< + Зхг — 4хэ + Зх4 + 2хэ = 1, — 8х! + 2хэ + Зхс< — 4т4 — 4хэ = 1, — х! — 4хэ+ 2тэ — Зх,< + Зхэ = 1, х, > О, у' = 1, ..., 5; х(о) .= (О 1 1. 0 1) 17.211. у'(х) = — 2х<+ хэ + 4хз — Х4 — хэ — ь шш хэ+ 2х4 — хэ = 1, Х! 24 ХЭ 2хз+ ха+ 2хэ = 4, г, .(О) (1.
1. 2. О. 0) Гл. 17. Методы оптимизации 372 ,1(х) = ~ х„4.; — г пнп, (25) Е а,х +х„,,=6о 4=1,...,т, (26) 1=1 хь > О, Й = 1, ...,н + гл. (27) Одной из угловых точек допустимого множества 0 этой задачи, очевидно, является точка хйй = (О; ...: О; 61, ...,. 6 ). Поэтому для решения задачи (25)-(27) можно использовать симплекс-меток со слецуюгцей начальной симплекс-таблицей: гле р. = — ~ аси у = 1, ..., и; — ро = — ~ 6,. з=1 1=1 Отметим, гго решение задачи (25)-(27) всегла сушествует, так как ее цопустимое множество 0 непусто (х~о~ е 17), а целевая функция (25) ограничена снизу на 0 (у(х) > 0). Пусть у' = ш1п у'(х). Рассмотрим возможные случаи.
й 17.212. Дх) = хг — хз — хз — х4 — Зхз -+ ш)п, 2хг + 2хз+ х4+ ха = 3, Зхг — хз+ 2хз — 2хз = 1, — Зхг + 2хз — х4 + 2хз = 1, х >О, у'=1,...,5; х(а)=(0 1 1 1 0) Решение задачи линейного программирования симплекс-методом на- чинается с поиска какой-либо угловой точки х~о~ допустимого мноа~ества У этой задачи. Метод искусственного базиса нахо кдения начальной угловой точ- ки хрй состоит в следующем.
Пусть в ограничениях задачи линейного программирования (3) — (5) все 6; > О, 1 = 1, ..., т. Если это не так, то умножим соответствующие уравнения (4) на -1. Введем т дополни- тельных переменных х„4и 1 = 1, ..., т, и рассмотрим вспомогательную задачу линейного программирования 'Э 3, Линейное програыдгированне 373 1. г"' > О, Тогда допустимое множество (7 исходной задачи линейного программирования (3) — (5) пусто, т.е.
эта залача нс имеет решений. 2. Г"' = 0 и ыиних1уы целевой фуш ции у(х) достигается в угловой точке Х = (Х1; ..; Хл; Хл-11~ .; Хп.~-щ) (28) допустимого мно1кества О вспомогательной задачи. Тогда (29) 101 с х = (х1, хэ, ...', х„) есть угловая точка допустимого множества У исходной задачи (3)-(5) и ее можно использовать в качестве начальной угловой точки при решении этой задачи симплекс-методом. Из (25) видно, что равенство г'(х) = г"' = 0 возможно только тогла, когда все координаты х„.д;, 1 = 1, ..., гл, в (28) равны нулю. Если задача (25)-(27) невырождсна, то это означает, что все переменные х„.ь, длл угловой точки (28) являются свободными. Опустим стодбцы, соответствующие этим персмсннь1м в окончательной симплекс- таблице, составленной при решении задачи (25)-(27). Полученнал в результате этого таблица будет соответствовать системе уравнений (4), разрешенной относительно т переменных х„являющихся базисными длл угловой точки (28). Поэтому остается заменить в этой таблице последнюю строку на слроку коэффициентов целевой функции (3) исходной задачи и продолжить ее решение симплекс-методом из начадьной угловой точки (29).
Если вспомогательная залача (25)-'(27) выро1кдсна, то в угловой точке (28) некоторые из переменных Х„.11, 1 = 1,, тя, могут оказаться базисными. Тогда эти переменные следует перевести в свободные с помощью холостых шагов симплекс-метода, выбирал в качестве разрешающих произвольные элементы симплекс-таблиц, отличимо от нуля. После этого исходная задача (3)-(5) решается симплекс-методом так, как описано выше.
П р и м с р 7. Методом искусственного базиса найти какую-либо угловую точку допустимого мно1ьества задачи линейного программирования, рассмотренной в примере б, и записать соответствующий этой угловой точке симплекс-таблицу, О Введем дополнитсльныс переменные хг, ..., х1о и запишем условие вспомогательной задачи линейного программированил (25)-(27) для рассматриваемого случая; ,У(х) = хт + хэ + хд + х1о — 1 пцп, Х1 + хд + хт = 20, хе + хд+ хв = 50, хэ + хд + хд = 30, хд + хд + хд + х10 = 60, хь>0, 1=1,...,10.
374 Гл. 17. Методы оптимизации Считая дополнительные персменые хг, .... х1 о базисными. запиш< и симплекс-табдицу этой задачи, соответствующую угловой точке х~о~ = = (О; 0; 0; 0; 0; 0; 20; 50; ЗО; 60): Любой столбец этой симплекс-таблицы может быть выбран в качестве разрешающего, так как элементы ес последней строки отрицательны. Выберем, например, столбец, соответствующий свободной переменной хж Тогда разрешающим будет элемент этого столбца, стоящий в первой строке, так как пцп(20/1, 60/1) = 20/1. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц (рамками обведены разрешавшие элементы)'): В нижней строке последней симплекс-таблицы нет отрицатсльныт элементов, а в правом нижнем углу стоит нуль.
Следовательно, л~иниыум з ) Столбец симпдекс-таблнцы, соответствующий вспомогательной переменной х„ен вводимой в свободные на каждом шаге метода искусственного базиса, удобнее вычеркивать на данном шаге вместо того, чтобы исалючить такие столбцы одновременно в окончательной симппекс-таблице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
