Корн Г.А., Корн Т.М. - Справочник по математике для ученых и инженеров (947387), страница 75
Текст из файла (страница 75)
может быть путем введения в случае необходимости вспомогательных переменных сведена к стандартной форме (основная задача линейного программировании): Требуется минимизировать целевую функцию г=) (хт, х,, ..., х„) — = с,х,+с,хэ+...+с„х„ при т (и линейных осраниченпях-равенствах а,!к!+а!зхз+...+а!лхл=д! (1=1, 2, ., т) (11.4-2Щ и и линейны ограничениях-неравенствах хй 0 (2=1, 2, ..., и). (!!А.йос) Допустимое решение (план) задачи линейного программирования, данной в стандартной форме, есть упорядоченное множество чисел (х,, хз, ..., х,,), удовлетворя!ощих ограничениям (2Ь) н (2с); это — точка в и-мерном прострзистзс.
ЗЗВ 4!.4-4, ГЛ. И. МАКСИМ!МЬГ Н МИНИМ1МЫ (1!.4-6) шш «=шах ш. (!1.4.3) Допустимое решение, минимизирующее целевую функцию (2а), называется оп- тимальным решением (оптимальным планом), Чаще всего оптимальное решение, если оно существует, единственно, . однако возможкы случаи, когда оптимальных решений бесчисленное множество. Для существования допустимого решения необходимо (но не достаточно!), чтобы система (2Ь) была совместна. В дальнейшем считается, что это выпол- няется; ранг матрицы системы г(т( п. Тогда г линейно независимых урав.
пений систсмы (2Ь) определяют некоторые г неизвестных как линейные функ- ции остальных и — г неизвестных — свободных неизвестных (см. п. 1,9.4). Фактически выражая все переменные через свободные неизвестные, можно прнйтн к задаче линейного программирования, содержащей и — г переменных и и линейных ограничений-неравенств, выражающих нсотрицательность исход- ных и переменных. Допустимое решение, соответствующее нулевым значениям свободных неизвестных, называется базисным допустимым решением (опорным планом), невырождениым, если все остальные переменные положительны, и выгожден- иым, если среди них есть хоть одно нулевое.
Если существует какое-либо допустил(ое решение для задачи линейного программирования, то существует и базисное допуеогил!ое решение. Если, кроме того, целевая функция имеет нижнюю границу на мнозхестее решений, т. е. существует ошпималькое решение, то существует и отпимальное базисное решение.
Множество всех допустимых решений данной задачи линейного програм- мирования есть выпуклое множество в и-мерном пространстве решений; это значит, что наждая точка ($„$„..., $я) прямолинейного отрезка, соединяю- щего два допустимых решения (х, х„..., х„) и (х'и х,,',, х„)! $» = сьх»+(1 — сь) х' (О ( а ( 1; й = 1, 2, ..., и) см.
также п. 3.1-7), есть также допустимое решение. Более точно, мнолсеетво допустимых решений есть выпуклый многоугольник илн многогранник в плоскости или гиперплоскости, определяемыи 1! звнениямн (2Ь) с граничными линиями, плоскостями илн гиперплоскостямн (2с), как это указано в простом примере на рис. 11.4-1, Ь. Если существует конечное оптимальное решение, то задача линеиного программирования либо имеет единственное оптимальное решение в одной из в ршин многогранника решений, либо минимальное значение г достигается ни всем выпуклом л(ножестее, порождаемом двумя или более вершинами (вырожденное решение).
(с) Двойственность. Задача минимизации «4 Е(Хг, Ха, ...„Хе) = С(Х4+СгХг+...+С,Х,=ш!п с ограничениями А;4Х4+А(аХе+...+АГ»Х,— В! ~ О (4=1, 2, ..., и!), Х»~0 (й=1, 2..., г) и соответствующая задача максимизации ш=б(уз, Уы ..., Ум) = Вхг'4+В!уз+...+Етую=шах с ограничениями А!»У!+Аз»уг+ ° ..+Ат»ут — С»(0 (у=1, 2,..., г), у! )0 (4=1, 2, ..., т) называются двойственными задачамн линейного программирования.
Если одна из задач (3) или (4) имеет конечное оптимальное решение, то то же имеет место для второй задачи, причем !4,4.2, и 4, линейное пРОГРАммиРОВ„игры и смен((лые ВОпРОсы 339 Если одна из задач имеет неограниченное решение, то вторая задача не иметп допусишл(ьт решений. Теорема двойственности позволяет заменить данную задачу линейного программирования другой, имеющей меньшее количешзо неизвестных нлн меньшее количество ограничений.нерав нств, и поэтому вспользуется в некоторых численных методах решений. 11А-2. И Симплекс-метод. (а) Задачи линейного программирования могут быть решены численными не!одами наискорейшего спуска, указанными в п. 20.2-6, однако сиыплексыезод извлекает выгоду из линейности выражений (1) и (2). В дальнейшем предполагается, что система уравнений (2Ь) линейно независима, г.
е. что г=т. Если решение задачи линейного программирования существует, то опо достигается в одной нз вершин многогранника решении; послсдш(е могут быть найдены совместньш решением т линейных уравнений (2Ь) и канпх-то и — т уравнений х»=0. Очевидно, что при большом числе переменных и ограничений этот процесс практически неосуществим ввиду крайне большого числа возможных вершин многогранника решений; симплекс- метод доставляет вычислительную схему перехода от вершины к вершине (от одного базисного решения к другому) в направлении наименьшего значения г.
(Ь) Применение симплекс-метода яачинается с выбора какого-либо допустимого базисного решения, В принципе это моткно сделать так: выбираются и — гп свободных переменных (свободных неизвестных), а остальные т переменных (базисные переменные) с помощью последовательного исключения переменнык (п. 1.9-1 и 20.3-1) выражаются через них. Если базисные переменные обозначены через х„ха, ..., хпь то уравнения (2а) и (2Ь) в результате исключения могут быть записаны в следующей канонической форме: «4+(ач, т»4«»4ы + ° ° + ("!»хо) =()!.
ха+ (аь т+гхты + ... + иаох„) = ()г, х +(а, е,х ы+...+и „х„)=~~, г = (у т»4«т»! + ° + Тех л) + го Если все ()! неоеприцап(елены, то х! = 1=1, 2, ..., т, (11.4-7) О, 1=и!+1, т+2, ..., и образ!рот бсзисное допустимое решение. Произведенный выбор свободных и базисных переменных далеко не очевиден; процедура, облегчающая выбор начгльного решения, будет описана в (й). Если в выражении для целевой функции г е (6) все у; неотрицаьпельиы. то решение (7) есть оптимальное ранение (никакое допусп(мое изменение свободных переменнык не ыожет !меньшить г). Это оптимальное решение единственно, если все у» положительны.
(с) Рассмотрим теперь случай, когда решение (7) является невырожденным базисным допустимым решением (т. е. ()„()г, ..., 3 ) О, см. и. 11.4.1), которое не оптимально, т. е. среди у» есть отрицательные. Пусть, для определенности, ук — наибольшее по абсолютной величине из отрицательных у„. Для получения улучшенного базисного допустимого решения в следующий итерационный цикл в качестве базисной переменной вводится х, заменяющее предшествующую базисную переменную хг, которая в соответствии с уравнениями х! — — р! — Гкхк ((=1 2 " * т) первой убывает до нуля, когда х возрастает от нулевого значения (это ! 1.4" 2.
ГЛ. Н, МАКСИМУМЫ И МИНИМУМЫ х,>о, х,>о х =х При этом р! г=г -(-у х =г+у„.— ж г. о КК а а)К О Теперь введение л р! ' )' ч-э х = — — — х + 7 а х К а!! а!К1 I .74 77 ! =- и -1- 1 ! э'=К (11.4-9) хор (11.4-100) воз!южно тогда, когда среди ащ есть положительные). Значит, индекс 7 асса. шшруется с наименьшей возможной величаной (обязательно положительно!!) х (11,4-8а) К а!К' Улучшенное базисное решение дается равенством (8а) и ()! — а!кхк- 0 ((=1, 2, ..., ап заметим, что х =0), х = ' !К К ', ! ' (11.4-8Ь) 0 (в=т+1, т+2, ..., и, ! ~ К). в систему (6) приводит ее к канонической форме относительно новых базисных переменных. 3 а м е ч а н и е. Симплекс-метод ие реализуем, если все и лелоложиьчельмэн тогда целевая функция г не имеет нижней границы на множестве решений.
Полный симплекс-алгоритм можно удобным образом табулировать в виде симплекс-таблицы и осуществить с помощью электронных вычислительных Мчщнп; ООЬ)ЧНО ОПтИМаЛЬНОЕ РЕШЕНИЕ даетнтастея Ча КОНЕЧНОЕ ЧИСЛО ШаГОВ. Квл мээыэе Еуэв!игалов рвишэе 2 д 4 5 5 7 5 Х, г =д Рис. 11.4-2. Множество решений в прострэнстве (Х„Х,). Если в процессе вычислений базисные переменные соответству!от еь!Ро- ждающемуся базисному допустимому решению (т. е. одна из базисных перемен- ных возвращается к нулевому значению, см.
и. 11.4-1, Ь), дальнейшее уточнение значения целевой функции, в принципе, прекращается; однако в практических задачах это встречается редко. Можно распространить симплекс-метод на случаи вырождения посредством малых изменений данных каэффициеятоа (метод возму!цепий), П р н м е р (рис, Н.4-2), Звдьчэ мнннмнэвцни функции г= — Х,т- Х, 4 3 11,4-2. Пл. л!п!ейное пРОГРАммиРОВ., Игры и смежные ВОпрасы 34! с ограничениями-иерввенстнэмн 5Хв+ Х, — 5) О, 2Хв -в-5Хв — 10 О, путем введены» вспомогетельныв переменнык х,= Хи кв=-бХ, + Хв — 5, х, =2хв+5Х,— 10, преобразуется к стандартной форме 1 1 г= — хв (- — хв=-впво, 4 ' 3 5хв — «в+ х,=5, йх, — х, + бх. =- (О, кв, х, х, хв>0, Опврввляясь от хв и к, квк базисных переменнык (перввя нержине справа эв рнс, 11 4-2), получаем каноническую форму ээдэчв: 1 5 х,— —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
