341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 51
Текст из файла (страница 51)
П ример 5. Используя графический метод, найти решение следующей задачи линейного программирования в каноническом виде: з 3. Линсйнос прог1тмаированис 7(х) = 740 — 7хз+ 7хс. (15) С учетом условия нсотрицательности х, > О, у = 1, ..., 6, и равенств (14), (15) получаем слслующую задачу: Хь 7(х) = 740 — 7хз+ 7хс — л спш ха+ хс ) 40, хл < 50,. ха <30, ха+ ха < 60, ЗО 20 !О Допустимое множество У послелней задачи изображено на рис.
34. Это лсио- Рис. 34 гоугольник АВСРЕ. Перемесцая линию уровня — 7хз + 7хь — — С функции (15) по направлению всвтора е = (7, — 7), находим точку минимума 7(х) — вершину В(50, 0) многоугольника АВСВЕ. Подставив значения ха = 50, ха = 0 в равенства (14), овончатсльно находим х' = (10, О, 30, 10, 50, О), У" = 390, Решить задачи линейного программирования в каноническом виде 17.201-17.206 графическим методом: 17.201. 7(х) = -2х1 + тг -+ шш, 2х1 — 4хг — хз + х4 = -3, 4хЗ вЂ” Зхг — ха+ х4+х = б, х1+ 4хг + хз+ ха = 15, гсу>0, 2=1,...,5. 17.202.
~(х) = 4х1 — Зхг — х4 + ха — л ппп, — хс + Зхг + х4 = 13, 4х1+хг+ха = 26, — 2х1+ тг+ хз = 1, х1 — Зтг+ хь —— О, х > О, г = 1, ..., 6. 17.203. з (х) = х1 + 2хг + хз — х4 — л шш 10хг + хз + 2х4 + Зха = 25, — хЗ + 5хг + хз + х4 + хз — — 10, 2х| — хг + хз — Зх4 = б, х > О, у = 1, ..., 5. 17.204. )'(х) = +4х1 + 2хг — тз + х4 — л ппп, Зхс + 2хг — хз + 4х4 = 3, хл — хг + 4хз — 2х4 = 2, х;>О, 2=1,...,4, Исключая с помошью (14) переменные хы ..., хз из вырван ния для целевой функции, находим Гл. 17. Методы оптимизации 364 17.205. )" (х) = — х! — Зхг — ) шш 2х ! — Хг + хб + хб = 10, 2х!+2хг+х4+ха = 25, — 2Х! + Зхг +:сз тз = 9 622+ хз+х,) = 36, х > О, у = 1, ..., 6.
17.206. зг(х) = — 2Х! + 2хг + ЗХ4 — х — ) пнп, Зх! — 2хг — хз + х4 = 2, х! + хг — хб = 3, 4х! — хг+ х4+хо = 19, 4х! — Хг — х4 + хб = 13, х.>0, 1=1,...,6. 2. Симплекс-метод решения задачи линейного программнрованил. Общим методом решения произвольной задачи линейного программированил является симнлексдкетод, рассматриваемый ниже. Пусть ранг г матрицы А = (а11) системы ограничений-равенств (4) задачи линейного программировайия в каноническом виде совпадает с рангом расширенной матрицы (А)Ь). Выберем какой-нибудь базисный минор матрицы А. Для определенности будем считать, что ои соответствует первым г столбцам и строкам этой матрицы.
Если г < пэ, то уравнения с номерами 1 = г + 1, ..., пт, являющиеся следствиями остальных уравнений системы, отбросим, полагая в дальнейшем г = т. Для решения системы уравнений (4) относительно базисных персменныт х„у = 1, ..., т, с помощью эквивалентных преобразований приведем ее к виду <а) )а) )а) Х1 + 421 т11Х П11 + + с2! дХП = 1П1 )а) )а) <а) Х2 + 1."2, т.1.1 Ха~4.! + ' ' ' + ! "2, пхп Р2 (16) )а) )а) (а) Х~и + Опп ППЫХП14-1 + ' ' ' ! ОПППХП Дт Тогда общее решение системы (4) запишется следующим образом: <а) <а) Х1 = Д1 421 т4.!Хтз-1 (а) (а) 22 62 ~г,т-1-1ХП~~-1 )а) — — С2 Х, 1,д и 4а) С 2, Х )17) )а) (а) )а) Х~п = )1т 41,д П111Хт.1-! ' ' ' — 1тт,дхд, где свободные переменные х„,.ы, ..., хд могут принимать произвольные значения.
З 3. Линсйное программирование 365 Положив их равнымп нулю, получим частное решенно Х! Ьп1 ь Х2 Рпг ь ' ь 2 п Ь и ь Ьпь"Ь-1 Гпь-1-2 ''' эп О или ьоь (8!о! фо) оьоь (18) которое назовем базисным решением системы (4). Каждому выбору базисных переменных соответствует свое базисное решение системы (4).
Если все компоненты базисного решения (18) удовлетворяют условию нсотрицательности, т.с. если;9, > О, 1 = 1, ..., т, то такое (оь решение называют допустимым базисным решением системы (4) или угловой гпо !кой допустимого множества сь задачи линейного программирования (3) — (5). Если среди неотрицательных чисел Д, в (18) есть ьо! равные нулю, то допустимое базисное решение называется вырожденным (вырожденной 1тловойь точкой), а соответствующая задача линейного программирования также называется вырожденной. В основе симплекс-метода лежит слсдуюший факт: Ес 11 задача линейного программирован! (3)-.(5) разрешима, то минимум целевой функции ь"(х) иэ (3) достигаетсл хатах бы в одной иэ угловых точек допустимого множества 51 этой задачи.
Так как различные базисные решения системы (4) соответствуют различным вариантам выбора т базисных из обшего числа и переменных х, то число допустимых базисных решений (угловых точек) не превышает С™. Поэтому задачу линейного программирования можно решать посредством перебора конечного числа угловых точек допустимого множества (ь', сравнивая значения целевой функции в этих точках. Однано при большой размерности и задачи линейного программирования этот подход затруднителен. Иден симплекс-метода состоит в направленном переборе угловых точек допустимого множества (ь' с послсловательным уменьшением целевой функции ь(х). Описание симплекс-мстода .
Предположим, что задача линейного программирования (3)-(5) является невырожденной, а базисное решение (18) — допустимым. Используя соотношение (11), выразим целевую функцию из (3) через свободные переменные х„у = т+1, ..., и: и .г'(х) = ро '+ ~~ р,' (19) э=пьв1 где 11ОЮ =~ сьд,"'; р,'." =с, — ~ сьаьэ', у =и!+1, ..., п. ь=1 ь=! Справедливы следующие утверждения: а) Если в выражении (19) осе коэффиььиекты рь. !,.1' = т+1, ..., и, ьо! неотрицательны, ьпо в угловой то ьке (18) достигастсл минимум целевой функции ь"(х) иэ (3) ка допустимом множестве У задачи (3)— (5) и этот минимум равен р~, ь. Гл.
17. Методы оптимизации 366 б) с'ели среди огприцатсльньлх коэффпцпентоо р, ) ф О, из (19) (о> есп1ь тпакой (например, р, ), чтпо в (16) все коэффициенгпы и, < О, (а) (а) 1 = 1, ..., т, гяо целевая функция э'(х) нс ограничена снизу на допустимом множестве У и задача (3) — (5) нс имеет решений. в) Если хотя бы один из коэффи1(центов р, у' ф О, в (19) отрц(а> цателен (например, р( < 0) и при этом среди коэффициентов оо (а) (а) в (16) есть хотя бы один положительны|1, то сутсствуегя угловая то гка х('> множесгпва () гпакая, что дх( >) < дх(а>). В случаях а) и б) пропесс решения задачи линейного программирования иа этом заканчивается. Рассмотрим подробнее случай в). Пусть в (19) коэффициент р(( > < 0 и в (16) имеются положительные козффицпеиты ов Найдем номер к базисной переменной из условия (а) (20) где минимум берется по всем номерам 1 = 1, ..., т, для которых о(>>0.
й( Найлом решение системы (4), считая свободными псремеииыс хь, ьы ..., х( и хь, хьь>, ..., х„, т.е. помсияв местами свободную переменную х> с базисной переменной х>о Система уравнений вида (16) в атом случае запишется слсдуюшим образолс и у' (а> т, (а) (а) х+ ~ о. — о. х, — — ха=,З. — о ч (а) (а) ь, ~'"о (а) (а) дА 2» ~ и а (а> ) ' э (о> " = » (а) э= +1 ~ь! оь> '"и (21) 1=1, ...,т, (~)ц 60 у(а) х>+ лэ — х + хе=в ч ьэ ь (а) э (а> ' (а) ' '"и ~и ~ь> «м а зависимость целевой функции от новых свободных псремсииых примет вид и )с (а> т (а) (а) = Е ~р> -р> — а) ху- — ахь+Ро +Р, — 'а (22) (а> (а> с"ьу р> (а> (а) )уь сто '"и оь> Компоненты нового базисного решения х' > ыоз ио найти, приравняв (!) нулю свободные персмеииыс х„у = та + 1,..., и, у' ф 1 и хь и найдя 3 3.
Линейное прог аммнрованне 367 при атом условии значения базисных переменных нз (21). Базисное решение х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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
