3 часть (1081356), страница 53
Текст из файла (страница 53)
Базисное решение х1Ы является допустимым, т.с. угловой точкой множества У, причем у(х1Ц) ( Дх~о1). По знакам коэффициентов в системе (21) и выражении для целевой функции (22) можно сделать одно из трех приведенных выше заключений, как это было сделано для угловой точки х1Ш. В случае в) следует совершить переход к очередной угловой точке х1т>, аналогичный переходу от хбб к х1'1, и т.д. Так как число угловых точек допустимого множества У не превышает С„, то случай в) может повторяться конечное число раз, т.е.
в реаультате конечного числа шагов перехода к новой угловой точке будет либо найдено решение задачи, либо сделано заключение о том, что она не имеет решений. Реализация описанного выше симплекс-метода значительно упрощается при использовании симплекс-таблиц. Записав коэффициенты уравнений (16) и целевой функции (19) соответствующим образом (см.
таблицу ЗА), получим симплекс-таблицу задачи (3)-(5) для угловой точки х1о1 из (18). Таблица 3.4 Рассмотрим переход от симплекс-таблицы, соответствующей угловой точке х1о1, к симплекс-таблице для угловой точки х1И. Пусть номера (с и 1 определены так, как зто сделано выше. Элемент аы, а также строка и столбец таблицы 3.4, на пересечении которых он <о1 стоит, называются разрешаюши.ни или опорными. Из формул (21) и (22) следует, что преобразование исходной симплекс-таблицы с опорным злементом ам (см. таблицу 3.4) приводит к новой симплекс-таблице 1о1 (таблица 3.5), для определения элементов которой необходимо выполнить следующие операции; Гл. 17.
Методы оптимизации 368 1. Поменять местами переменные хь и х(, остальные переменные оставить на прежних местах, см, таблицу 3.5. Таблица 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) Полагая в равенствах (23) свободные переменные х~ и хэ равными нулю, находим хэ = 40, хэ = 20, хэ = 30, т.е, базисное решение и~о> = (О, 40, О, 20, 10, 30). Так как все базисные переменные в к~о~ положительны, данное базисное решение является допустимым (т. е. угловой точной) и невырожденным. Исключив с помощью (23) базисные переменные в выражении для деленой функции, получим Дх) = 880 — 7х, — 14хэ. (24) С помощью равенств (23) и (24) составляем симплекс-таблицу, соответствующую угловой точке х~о~: Среди коэффициентов р, у ф О, из (19) есть отрицательные — это <о) элементы — 7 и — 14 последней строки симплекс-таблицы. Следовательно, угловая точка к~о~ не является решением задачи.
Гл. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
