Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 16
Текст из файла (страница 16)
Тогда вектор х можно представить в виде х = (хьн х„), где хь = (х„..., хм) — базисный вектор, х; ) О, ь = 1,...,т, х„= (0,...,0) Е К" ~ — небазисный вектор. Аналогично матрицу А можно представить в виде А = (Аь, А ). Будет доказано в и.3.2, что матрица Аь невырожденная, то есть ее определитель отличен от нуля. 1.2. Правило решения задач по симплекс-методу Для решения невырожденной задачи линейного программирования слелует: 2. Привести задачу к задаче в канонической форме (Рь). 2.
Отыскать крайнюю точку х = (хн...,х,„,0,...,0), х; ) О, а = 1,...,тп, множества допустимых элементов 22(Рь). Методы нахождения начальной крайней точки будут описаны ниже в Ь4. 3. Построить симплексную таблицу для начальной крайней точки х. Пояснения к построению таблицы; В таблице тп + 4 строки и и + 4 столбца. В первом столбце, начиная с третьего по па+2-е место, находятся базисные векторы а',...,а, соответствующие положительным координатам начальной крайней точки х = (хн ...,х,О,...,0). Во втором столбце на аналогичных местах стоят значения с вектора с с теми же номерами, что и столбцы аа, Последний столбец заполняется при исследовании симплексной таблицы.
$1. Симплекс-метод В первой строке, начиная с четвертого столбца, стоят элементы сн...,с„. Вторая строка, начиная с третьего столбца, — векторы Ь,а',...,а". Под ними — разложения этих векторов по базису а,..., а™. Ясно, что Ь = 2 аьх; еь Ах = Ь. То есть разложением вектора Ь ы1 является вектор хь ненулевых координат крайней точки х. Предположим, что вектора ат, а = 1,...,и, имеют следующее разложение по базису а',...,а: ат = 2,'аьх; еь ат = Аьха еь А = АьХ, где Х = (хб)ь=п, — матрица разложений векторов а',...,а" по базису а',...,а, состоящая из столбцов х',...,х".
Тогда Х = А 'А, то есть неизвестные векторы-столбцы хт отыскиваются с помощью обратной матрицы: х' = Аь 'а'. Очевидно, что при а = 1,..., т разложения век- 0 торов а' тривиальны: а' = а', то есть в этом случае ха = 1 = е' (ет — вектор-столбец канонического базиса). В предпоследней строке л в столбце под вектором Ь (хь) запишем ло —— (сь,хь). Тогда лв — значение функционала в начальной крайней точке х. Под векгорами а', ь = 1,...,и, запишем л = (сь,х'), то есть л = (лн..., лл) = сьХ. Очевидно, что лр — — с при ь = 1,..., т.
В последней строке тз, начиная с четвертого столбца, записывается разность межлу элементами предпоследней строки и элементами первой строки: аа = л — сер тз, = л< — с„а = 1,...,и. оболочкой евонх крайних точек был локален Крейном и Мильманом. вот иатываатт теоремой Крейна — Мильмана 9! б 1. Симплекс-метал 90 Глава 2.
Линейное программирование ~(х) — оппп; Ах=Ь, х>О. 4. Исследовать симплексную таблицу. а) Если гз > О, то крайняя точка х — решение задачи (х б Агд Рь). Ь) Если для некоторого ! А < 0 и хг < О, то значение задачи ор, = +ею; с) Пусть в строке Ь имеются отрицательные числа, а соответствующие столбцы х' солержат положительные числа. Предположим, что ппп Ь; = гз,„< О. Ясно, что оп+ ! < !ь < и. Столбец, соответствующий индексу уе называется разреювюи1ии сталбцвм.
Если пцп А достигается на нескольких значениях 1, то в качестве разрешающего столбца выбираем столбец с любым таким индексом. Обог хг значим 1;: = 1 — ~ х», > 0) > О. Эти значения 1, ставим соответственхоуо но в последнем столбце симплексной таблицы. Пусть 1ь = пнп 1, > О. ! Строка вектора а" называется разрешающей. Если ппп1, достигается 0 на нескольких значениях С то в качестве разрешающей строки выбираем любую такую строку. Элемент х„„называется разрегиающим элементам симплексной таблицы. Далее необходимо из числа базисных векторов исключить вектор ач, вместо него взять вектор а'". Значение функционала на новой крайней ТОЧКЕ Х~ С НОВЫМИ баЗИСНЫМИ ВЕКтОраМИ а',...,ай ', ад, аи Ы „,аоо, возрастет на величину — 1ьг!ом.
5. Построить новую симплексную таблицу для нового базиса а',..., ап ',азо,аго"',...,а, т.е. фактически разложить векторы Ь,а,...,а", по новому базису. Укажем без обоснования (оно будет приведено в и. 3.3) способ построения новой симплексной таблицы по предыдущей. Элементы таблицы х,', лежащие под векторами Ь, а',..., а", и не лежащие в разрешающей строке старой симплексной таблицы, вычисляются по нравилу прямоугольника: х„хоуо, хчдхой х; = а; —, х» = х» —, 1ф1ь, Хоо!о хооуо из числа х» вычесть произведение хй. на хг „деленное на х,,;. Ясно, что в разрешающем столбце новой симплексной таблицы х';„; = 1, остальные элементы равны нулю (х,'; = О, 1 ~ 1ь, 1 = 1,...,га).
Элементы разрешающей строки новой таблицы вычисляются путем деления элементов разрешающей строки старой таблицы на величину хь,: Хоо 0 ХВог хь = —, хчу — —, у = 1,...,и. хгого х„;, Далее необходимо вновь исследовать симплексную таблицу, т.е. вернуться к п. 4 н так далее, пока не придем к решению задачи. Отметим, что симплекс-метод позволяет решать точно так же и вырожден жденные задачи линейного программирования. Число положительных коорд динат крайней точки в таких задачах может быть меньше гп, но число базисных векторов всегда равняется рангу матрицы А, величина 1ь может оказаться равной нулю. Теоретически в вырожденных задачах возможно зацикливание, когда через несколько этапов приходим к уже рассмотренной ранее крайней точке и зто возвращение может происходить бесконечное число раз.
При этом значение целевой функции не меняется и, значит, 1й = О. Перейти от вырожденной задачи к невырожденной можно путем сколь угодно малого изменения начальных данных задачи. 1.3. Примеры Приведем задачу, не являющуюся задачей линейного программирования, но путем замены переменных сводящуюся к задаче линейного программирования. Задача на минимакс Пусть 7(х) = шах (10(х),..., 1ь(х) ) — функция и переменных х = (хп...,х„) является максимумом линейных Функций.
Здесь 1(х) = (с',х) — до — линейные Функции, х,с' Е К". до Е К, в = 1,..., Ь, А— матрица гп х и, Ь Е К . Рассмотрим следующую задачу В отличие от задачи линейного программирования функция 3(х) не явля- ется линейной. Покажем, что задача (Р) эквивалентна залаче линейного программирования х„,, — гп!и; 1,(х) < х„ь„в = 1,...,Ь, Ах = Ь, х > О. (Р') Действительно, если х б АхаР, то (х, х„ю. = 1'(х)) б АгйР'. (Если допустить, что вектор (х, 3 (х)) Е Ага Р', то существует вектор й б Р(Р) такой, что /(х) < 1(х) ~ х Е Агй Р— противоречие.) С другой стороны, если (х,хьм) б АгяР', то х б АгяР.
(Если допустить, что х й АгйР, то существует вектор й Е Р(Р) такой, что /(х) < У(х). Значит, векпоР (х,з(х) б Р(Р') и и„.„, < Ео.,о =ь (х, й„.„о) Е Агд Р' — противоречие.) 93 92 9 1. Симплекс-метод Глава 2. Линейное программироааиие х, -1-хг+2хз+Зхз +бх4=9 х» + хз + х4 + хе 3 хз + х4 — хз + 2хе = ! Х4 +Х6=1 Х3 — хг+хз =1, 2Х3 + хг + х4 = 3 4) 0 5 1 — 1 О 1 0 ! -2 О О 0 1 0 0 < 1 ! 0 6 0 1 0 ! 0 0 — ! 2 0 0 О 1 О 0 0 1 — 1 О О О О 1 0 0 0 0 0 1 О 1 0 0 0 0 1 0 1 0 0 1 — 2 0 О О 1 Пример 1. Решить невыролгденную задачу линейного программирования в канонической форме 2х~ + хг+ хз — х4 — »пах; аг > О, г = 1,2,3,4, с заданной начальной крайней точкой х = (0,0, 1,3).
Решение. Базисные векторы аз = (1,0) и а4 = (О,!). Составим первую симплексную таблицу Из таблицы видно, что в качестве разрешающего столбца мозкно взять столбцы а и а . Возьмем для определенности столбец а . Тогда г 1 = 3, разрешающая строка а4. Заменяем в базисе вектор а4 на вектор аг и для нового базиса строим вторую симплексную таблицу; Вектор»5 > О, поэтому точка х = (0,3,4,0) является решением задачи и Я „= 7.
Если бы в качестве разрешающего столбца в первой симплексной таблице взяли столбец а', то пришли бы к той же точке (0,3,4,0), но за большее число шагов. П имер 2 Решить задачу линейного программирования р Х3+хг+хз+х4+хз+хе шах; х, >О, 4=1,...,6, с заданной начальной крайней точкой х = (1,2,0,0,1,!). Решение. Базисные векторы а' = (1,0,0,0), а' = (1,1,0,0), ~г1 1 0 6 0 1 О 1 а =(0,0,— 1,0) и а =(6,1,2,1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
