Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 21
Текст из файла (страница 21)
= О, 3 = 1,...,и. Так как хзз — з-я координата разложения вектора аз по базисному вектору а', то тогда все векторы аз, з = 1,...,п, включая вектор Ь, можно разложить по базисным без вектора а . Значит, Зв-я строка исходной системы уравнений является „Л+Во линеЙно зависимой от остальных строк и на егором этапе можем просто вычеркнуть из симплексной таблицы ле-ю строку, содержащую эту искусственную переменную, н начать второй этап с меньшим числом базисных векторов. Таким образом, двуэтапный симплекс-метод позволяет для любой задачи линейного программирования в канонической форме: 1) обнаружить, что исходная задача не имеет допустимых элементов, или 2) найти первоначальную крайнюю точку в задаче (Р) и решить задачу по симплекс-методу, или 3) исключить линейно зависимые равенства и решить задачу по симплекс-методу с найденной крайней точкой, имеюцгей менее га положительных элементов.
Замечание. Вместо такого двузтапнога решения задачи (Рл) можно решать следующую задачу (ее принято называть М-залачей) (с(х х)) — гпах; Ах+2х=Ь, х>0, х>0, где с = (с, — М,..., -М) Е К"""', М вЂ” полозкительное число. Нетрудно показать, что при любом достаточно большом М первые п координат полученного решения определяют решение в (Рл), а искусственные переменные равны нулю. 04.
Методы нахождения начальной крайней точки 115 4.3. Примеры /Зример 1. Решить методом искусственного базиса задачу: х1+ 2хз+ Зхз — хл — гааз; х; ) О, з = 1,2,3,4, Рассмотрим вспомогательную задачу, добавляя искусственные переменные хз,хл. — хз — хл- шах; хг)0, з=1,...,6, Исходная крайняя точка х = (0,0,0,10,20,15). Базисные векторы а = (1, О, 0), аз = (О, 1, 0), а = (О, О, 1).
Составим первую снмплексную таблицу для вспомогательной задачи: Из таблицы видно, что разрешающим столбцом является столбец а, з разрешающая строка аз. Заменяем в базисе вектор а на вектор а и для 5 з нового базиса строим вторую симплексную таблицу: !16 Глава 2. Линейное программирование 5=1,2,3, х1 — 2хг+ тз щах; х; > О, х, + хг +хз=5, 2х1+ хг — — 3, -2х1+ 2хг = 4. 5=1,...,5, -х4 — хз — гпах; х; > О, х~ + хг + хз =5, 2х~+ хг +х4 =3, — 2х~ + 2хг +аз=4.
Из таблицы видно, что разрешающим столбцом является столбец а', разрешающая строка а . Заменяем в базисе вектор а' на вектор а и для нового базиса строим третью симплексную таблицу: Вектор Ь > О, поэтому точка х = (О, г, 55, т, 0,0) является решением вспомогательной задачи и Я,„= О. Перейдем к решению основной задачи. Составим первую симплексную таблицу для начальной крайней точки х=(0,— г',ф,— г). Разложения векторов х,а по базису а,а,а берем из последней симплексной з таблицы: Разрешающим столбцом является столбец а', разрешающая строка а4.
Заменяем в базисе вектор а' на вектор а' и лля нового базиса строим вторую симплексную таблицу: 44. Методы нахождения начальной крайней точки Вектор Ь > О, поэтому точка х = (-, -, 5,0) является решением 5 5 5 исходной залечи и Я„„„= 15. Пример 2. Решить методом искусственного базиса задачу: Решение. Рассмотрим вспомогательную задачу, добавляя искусствен- НЫЕ ПЕРЕМЕННЫЕ Х4, Хз. Исходная крайняя точка й = (О, О, 5, 3, 4). Базисные векторы а = (1,О, 0), ,4 (010) 5 Составим первую симплексную таблицу для вспомогательной задачи: 119 Глава 2. Линейное программирование 2х, + Зхз + хз + 2х4 < 30, 4хз + 2хз + хз + 2х4 ~ (40, хз + 2хз + Зхз + ха < 25.
Разрешающий столбец а, разрешающая строка а'. Заменяем в базисе вектор а на вектор а и лля нового базиса строим вторую 5 з симплексную таблицу: Во второй симплексной таблице разрешающий столбец а', разрешающая строка а . Заменяем в базисе вектор искусственных перемен- 4 ных а на вектор а и для нового базиса строим третью симплексную 4 з таблицу: Вектор гз > О, поэтому точка х = (-',;, -,0,0) является решением вспомогательной задачи с добавленными искусственными переменными, иЯ =О. Перейдем к решению основной задачи. Составим первую симплексную таблицу для начальной крайней точки х = (-,', —, 5).
Разложения вектора х по базису а, а, аз берем из последней симплексной таблицы: з $4. Методы нахождения начальной крайней точки Вектор зЗ > О, поэтому точка й = (з,—,3) является решением IЗ 2 Зз исходной задачи и Я = -2 Заметим, что на самом деле исходная задача тривиально решается, так как мы имеем систему из трех линейных уравнений с тремя /! 2 7ъ неизвестными. И зта система имеет единственное решение х = (-, з, -).
/7ример 3. Решить, вводя искусственные переменные задачу; 2х, + хз + Зхз + 5х4 — гпах; хг > О, з = 1,2, 3,4, добавив неотрицательные переменные хз,хмхг, получим задачу в канонической форме: 2х~+хз+Зхз+5х4- шах; хг >О, з= 1,...,7, 2х~ + Зхз + хз + 2хг+ хз =- 30, 4х~+2хз+ хз +2хз +ха — — 40, хз + 2хз + Зхз + х4 + хз = 25. Исходная крайняя точка х = (0,0,0,0,30,40,25). Базисные векторы а = (1, О, 0), а = (О, 1, 0), аз = (О, О, 1) . Составим первую симплексную таблицу: 121 6 4. Методы накождепня начальной крайней точки 120 Глава ?.
Линейное программирова вне 4.4. Задачи Задачи линейного программирования в канонической форме с не- заданной первоначальной крайней точкой. Решить методом искус- ственного базиса. х,>0, 5=1,2,3, х~ + 4хз + хз -а шах; 4.1. х~ — хз + хз = 3, 2х| — 5хз хз = О.
х,>0, 5=1,2,3, х, — !Охз + хз - гпах; 4.2. х, — 5,5хз — 7хз = — 13, х ~ — 14, 5хз + 7хз = 15. х!+ 2хз + Зхз — 4Х4 -~так; ха>0, 5=1,2,3,4, 4.3. х1+ хз хз + х4 = 2, х~ + 14хз + 10хз — 10х4 = 24. а = 1,2,3,4, ха >О, х, — 5хз — хз + Х4 — шах; 4.4. х~ + Зхз + Зхз + Х4 = 3, 2х1 + хз — Х4 = 4.
= 1,2,3,4, х; ~ ~О, х~ + хз + хз + Х4 — пзах; 4.5. 4х~ + 2хз + 5хз — х4 = 5, 5Х1 + Зх + бхз — 2х4 = 5, Зх~ + 2хз+4хз — х4 = 4. 1,2,3,4, х; > О, х, +10хз — хз +5ха 4.6. х + 2хз — хз — ха -х, + 2хз +Зхз+ ха х| + 5хз + хз — ха 5=1,...,5, з:,>О, х~ + 2хз 4.7 з бх~ Х~ + Хз х, > О, а = 1,..., 5, +хз — хз + ха + а:з+ хз + х4 + хз + 2хз + Зх4 + хз + Зхз + бха ха > О, а = 1, 6, — 4хз + хз + — 14х5 + ! 2хз + хз + 2хз — !бхз + 8хз + В первой симплексной таблице разрешающим столбцом является столбец а, Разрешающая строка аз, ! = 15. Заменяем в базисе вектор а на вектор а и для нового базиса строим вторую симплексную таблицу: Во второй симплексной таблице разрешающий столбец а, разрешающая строка аз, 4 = 4.
Заменяем в базисе вектор а на вектор а и для нового базиса строим третью симплексную таблицу для базиса аа, аа, а: Вектор 45 > О, поэтому крайняя точка х = (0,0,4,13,0,10,0) является решением расширенной задачи, а решением искодной задачи является точка й = (0,0,4,13), Я,„= 77. х~ 48 Зх| бх, 1Ох, х, 14Х~ х~ 16х~ + Зхз+4ха + хз — 2ха + хз — 2ха — 2ха > знал; = 1, =2, = 5. + 5хз - шал; + 7хз — — 2, +7хз =2, + 7х5 — 2хз- шах; — 2хз = 1О, — 4хз = 20, — 7хз = 30.
Ха + Хз + Хб 5Х4 + бхз + Зха + Х5 7х4 + 4хз+ 5ха так; 8, О, 12. !2З б 5. т)увнсввргявя задача Глава 2. Лввейвое программирование 122 5 5. Транспортная задача 5.1. Постановка задачи лу п ~~у а, =,~ 6, =М. у=! хт < ау, Е 1 = 1,...,пу, у=! т л с; хц — пцп; у=! у=! > О, 1= 1,...,пт, (с, х): = 1,...,п, = а„у= 1,...,гп, л ~~У хт у=! лу х, (а) (Ь) =6, 2 =1,...,п. неравенствами имеют вид; *;.
< Ьуэ у' = 1,..., п, Е- х!! хп а! 122 у=! х!л Ху! хп ат ь, х хйВ2 Важный частный случай задач линейного программирования транспортные залачи. Зто математические модели разнообразных прикладных задач по оптимизации перевозок. В этом параграфе мы приведем постановку транспортной задачи, методы отыскания исходной крайней точки, решение залачи методом потенциалов, двойственную к транспортной задаче, обоснование метода потенциалов, задачу о назначении, примеры. Гралслортлой зидочей ло критерию стоимости называется следующая задача о минимизации стоимости перевозок. Пусть в пунктах отправления А1,..., А сосредоточено соответственно а„...,а единиц некоторого однородного груза.
Зтот груз следует перевезти в п пунктов назначения В„...,В„, причем в каждый из них наале:кит завезти соответственно 61,...,Ь„единиц груза. Стоимость перевозки единицы груза из пункта Ат в пункт В равна с;.. Обозначая через х; количество единиц груза, предназначенного к отправке из пункта А, в пункт Ву, получим задачу нахождения плана перевозок, при котором общая стоимость окажется минимальной: В матричном виде ограничения задачи (а) — (Ь) ! ! ... 1 0 0 ... 0 ... 0 0 ..
0 0 0 ... 0 ! 1 ... 1 ... 0 0 ... 0 0 0 ... 0 0 0 ... 0 ... 1 1 ... 1 ! О ... 0 1 0 ... 0 ... 1 0 ... 0 0 ! ... 0 0 1 ... 0 ... 0 1 ... 0 0 0 ... ! 0 О ... 1 ... 0 0 ... 1 План перевозок и стоимость перевозок представляются в виде векторов х = (хб, 1 = 1,...,пу, 1' = 1,...,п), с = (с;у, 1 = 1,...,пт, 2 = 1, ...,п) Стуатястетясииа ИЛН Матрнц Х = (Х!у)и=1,,т, С = (Су)1=1, т. Уравнения (а) означают, что из пункта отправления А1 весь груз вывезен в пункты назначения (потребления). Уравнения (Ь) означают, что количество груза. завезенного в пункт В со всех пунктов отправления, соответствует требуемому. Естественно считать, что общий запас груза на всех пунктах отправления равен суммарной потребности всех пунктов назначения, т,е.
В этом случае говорят, что имеется замклутоя модель транспортной задачи. Если суммарные запасы отправителей больше суммарной потребно- ВВ л сти пунктов назначения, т. е. 2, ат > 2 Ь, то равенства (а) заменяются у=! у=! неравенствами а условие (Ь) остается без изменений. В этом случае вводится фиктивный пг п пункт назначения В„е! с требуемой величиной завоза Ь„е, = 2; ат — 2; Ьу 1=! у=! и нулевыми стоимостями перевозок в этот пункт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
