Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 16
Текст из файла (страница 16)
Выпуклый компакт в К" лаляетсл выпуклой оболочкой свош кройнш тонга'. Бесяопечппмерпый апаэлг этой теоремы: выпуялый алм пает в нлрмпрлвапнлм (и даже локально-выпуклом линейном голллогпческпм) пространстве лвляегся выпуялай Глана 2. Линейное программирование Число крайних точек множества 21, заааваемого в виде конечного числа линейных равенств и неравенств, является конечным. Таким образом, для решения задачи линейного программирования (если оно существует), достаточно перебрать значения функции (с,х) во всех крайних точках множества В.
Но нахождение всех этих крайних точек и перебор значений функции (с,х) — операция довольно трудоемкая. Описываемый ниже симплексчмешод решения задачи линейного программирования позволяет, начиная с некоторой исходной крайней точки, переходить к другой по направлению наибольшего возрастания функции (с,х). Свое название симплекс-метод получил из-за вида множества допустимых элементов, которое в простейших задачах имеет вид симплексов (отрезка, треугольника и т.д.) Задача (Ра) называется нелыролгденной, если любая крайняя точка множества .0(Рь) содержит ровно т положительных координат.
Пусть х — крайняя точка в невырожденной задаче с положительньймн координатами (для определенности первыми) хм..., х,„. Тогда вектор х можно представить в виде х = (хьн х„), где хь = (х„..., хм) — базисный вектор, х; ) О, ь = 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). Матрица Аз 0 0 0 1 не является единичной, поэтому найдем для нее обратную матрицу. Для этого записываем рядом две матрицы: нашу матрицу Аз и ЕДиничную. Далее сводим матрицу Аз к единичной путем элементарных преобразоааний строк.
Полученная в результате преобразований матрица на месте единичной матрицы и является обратной к нашей матрице Аз. Напомним, что элементарными преобрам»ваннами матрицы являются: а) перестановка двух строк; Ь) умножение строки на число отличное от нуля и с) прибавление к одной строке другой строки, умноженной на любое число. На первом этапе мы умножили третью строку на -1, из первой строки вычли вторую. На втором этапе из первой строки вычли четвертую, умноженную на 5.
На третьем этапе из второй строки вычли четвертую, а к третьей строке прибавили удвоенную четвертую. /1 — ! 0 -53 !о ! о Таким образом, получили, что Аз ' —— 0 0 0 1 3 4 Далее находим разложения векторов а,а по базису а,а,а,а: 94 95 9 ! Симплекс-метод 1.4. Эйдачи Задачи линейного программирования в канонической форме с за- данной первоначальной крайней точкой. ХЗ>0, 5=1,2,3, хб (О~ ! 1). х7+ х2+ хэ шах; 1.1. -х, + х2+ хз = 2, Зх, — ХЗ+ хз = О, 2Х~ + хг + Зхз+ хб — шах; 1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
