3 часть (1081356), страница 52
Текст из файла (страница 52)
Для определенности будем считать, что этот минор порядка г соответствует первым г столбпам и строкам матрицы А. Если т ( т, то уравнения (4) с номерами 1 = т + 1, ..., ш являются следствиями остальных уравнений и их следует опустить. Поэтому будем считать, что г = пг. Предположим, что и — т = 2 или и — т = 1. Считая переменныс х, у = 1,..., га базисными, а остальные — свободными, решим систему (4), т.е. выразим базисные переменные через свободные, после чего исключим базисные переменные из условия задачи (3)-(5). Для этого полученные соотношения для базисных переменных подставим в выражение (3) целевой функции и запишем условие неотрицательности (5) для всех переменных. В результате полу ~им задачу линейного программирования вида (10)-(12), эквивалентную исходной задаче и содержащую только свободные переменные исходной задачи, а их число не превосходит двух.
Для решения полученной задачи можно использовать графический метод. П ример 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
