Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 130
Текст из файла (страница 130)
Градиент функции О/(х) направлен в сторону дуги АВС, и функция у"(х) будет иметь минимальное значение в точке касания линии уровня к дуге АВС. Так как линии уровня отсекают от осей х, и к я 1 х, равные отрезки, то координаты точки касания равны !.соз-=! мп — = . Решение зааачи 4 4 /2 х! =-2 те='д ' Ум„(х)=у~,~-~=2р — 2~из,б.
Рнс. П2.7. Графическое решение задачи математического программирования нетРУлно видеть, 'по то же Решение бУдсг и в том слУчае, если вместо А(х) тать Яз(х) = хз + хз — 1 < О. Тогда допустимая область 0 будет заключена межау душми АВС и АОС (рис. П2.7). Но минимальное значе- ° 1 ° ! ние функции /(х) в области 0 будегдостигнугов точках х, =-т и к, =-1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ При рассмотрении задач линейного программирования целесообразно их подразделить на отдельные классы (виды) задач.
Для каждого такого класса удается сформулировать алгоритм решения, приемлемый только для данного класса задач. Наиболвв разработанными в математическом программировании являются задачи линейного программирования. В задачах линейного программирования целевая функция линейна, а условия- ограничения содержат линейные равенства и линейные неравенства. Переменные могут быть подчинены или не подчинены требованию неотрицательностн. Одна и та же задача линейного программирования может быть записана в различной форме. Говорят, что задача пикейного программирования записана в канонической форме, если все ев' ограничения, кроме х > О, у = 1,п, представляют собой равенства. Если все ограничения имеют вид неравенств, та задача записана в стандартной форме.
П уложение 2. Математическое и о амму рвание основные положения) Ьаз Для записи задачи линейного программирования в различной форме применяются следуюц1ие приемы: 1) точка минимума функции г"(х) совпадает с точкой максимума функции -г(х); 2) ограничения в виде неравенств и ~~~ а, х >Ь,(! =1,т) 1=1 можно представить в виде равенств, использовав новые переменные х!(! = и+ 1,п+2,...,т), х, > О, называемые слабымю ~азх -х, =Ь, 1 л Для неравенства ) авхз >Ь, можно взять х, >0 и получить равенство т! '! адх +х, =Ь, / 1 л 3) ограничение в виде равенства Ч ~а, х. = Ь, можно заменить двумя неравенст- 1 вами , 'а, х >Ь,, ~! азх <Ь, з=! !=1 Если имеется т равенств , 'а,х~ =Ь, (1=1,т), ихможнозаменить (т+1) з 1 неравенствами а, х > Ь, (1 =1,т) и ~(~аех -Ь) < О; !=1 ~!т! 4) если на переменную х, Ц = 1,п) не наложено условие неотрицательности, еб можно заменить двумя неотрицательными переменными х' и х, положив х =х'-х;х+ >0;х >О ) а;х =Ь(! =1,т),п>т.
!=1 (П2.11) 45 зз, звв Если имеется птаких переменных х (!'=1,п), то их можно заменить (и+!) неотрицательными переменными х и хз, положив х, = х, -хз. 1 1 Система ограничений в виде равенств и неравенств образует выпуклое множество — выпуклый многогранник. Это множество может быть ограниченным и неограниченным. Целевая функция задачи линейного программирования — тоже выпуклая функция. Таким образом, задача линейного программирования является частным случаем задачи выпуклого программирования. Рассмотрим систему ограничений задачи линейного программирования в виде ра- венств 690 П иложения Говорят, что система (П2.11) линейных уравнений совместна, если она имеет, по крайней мере, адно решение.
Система (П2.11) называется избыточной, если одно из уравнений можно выразить в виде линейной комбинации остальных. Сиам«ма (П2.11) несовместна, если ранг матрицы ~1а, ~; ! =1, у =!,п, равен г, ранг расширенной магприцы этой системы (с присоединенным столбцом Ь, ) больше г. В системе (П2.11) число переменных (неизвестных х) п больше, чем число уравнений и! . Будем считать, что ранг этой системы равен т (система неизбыточна) и что система (П2.11) совместна. Тогда !и переменных из общего их числа и образуют базисные переменные, а остальные (п-т) переменных называюм свободными.
Система (П2.11) в этом случае будет иметь бесчисленное множество решений, т.к. свободным переменным можно давать любые значения, для которых находят значения базисных переменных. Решение системы (П2.11) называют базисным, если все свободные переменные равны нулю.
Если система уравнений имеет решение, то она имеет и базисное решение. Решение системы уравнений (П2.11) называют допустимым, если все его компоненты неомрицамельны. Если система линейных уравнений обладает допустимым решением, то она имеет и базисное допустимое решение. Совокупность всех допустимых решений системы (П2.11) есть выпуклое множество, или, другими словами, множество решений задачи линейного программирования выпукло. Так как это множество образовано плоскостями (гиперплоскостями), то оно имеет вид выпуклого многогранника. Базисное допустимое решение соответсп!вувш крайней точке выпуклого многогранника (его грани или вершине). Если существует ошнимальное решение задачи линейного программирования, пю существует базисное опмимальное решение.
Целевая функция задачи линейного программирования есть уравнение плоскости (нли гиперплоскости для числа переменных больше трех). Пусть в вершинах выпуклого многоугольника мы установили «столбы», высота которых определяет значения целевой функции в данной вершине. На эти «столбы» наложим. плоскость (графическое представление целевой функции). Очевидно, что максимальное и минимальное значение целевая функция задачи линейного программирования достигает либо в вершине выпуклого многогранника, либо на одной из его граней.
Таким образом, решение (решения) задачи линейного программирования леисит в вершинах выпуклого многогранника и для его нахождения надо вычислил!ь значение целевой функции в вершинах выпуклого многогранника, определяемых!и условиями-ограничениями задачи. СИМПЛЕКС-МЕТОД вЂ” ОСНОВНОЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Рассмотрим задачу линейного программирования в канонической форме: и найти минимум функции Г'(х) = ,',с,х з=! приусловиях '! а, х =Ь,, 1= 1,м, т<п, х >О,У=-!,п. ! Предполагается, что решение этой задачи существует. Чтобы найти оптимальное решение, надо найти допустимые базисные решения, а из них выбрать оптимальное базисное решение.
Для чего мы должны поочередно из столбцов матрицы ! (а„~~, 1=1,т, у'=1,п выбирать т столбцов и решать систему из м уравнений с и неизвестными. Такой метод тРебУет РешениЯ С" =пгУ(г !( !) УРавнений, что практически невозможно, даже для небольших значений т . П уложение 2. Математическое п о амму рвание основные положения 691 Для решения задач линейного программирования в 1949 г. американским матема- тиком Дж.
Данцигом разработан симплекс-метод, спавший основным для решетт задач линейиого программирования. Разберем главные моменты симплекс-метода на небольшом числовом примере: минимизировать /(х) =3-х4+х, при ограничениях ха+2х4 +Зхз — 7 = О, хз — х4 -Зхз — 2 = О, Х~ +Х4 4.хз — 2 = О, х, >Охз >Охз >Ох4 >Охз >О.
Определитель, составленный из коэффициентов прн неизвестных х,,хз,х,, имеет анд О 1 О О О 1 и не равен нулю. Поэтому ранг матрицы ограничений равен 3, базисные 1 О О 'переменные — х,,хз,хз, а свободные переменные — х4,х,. Выразим базисные пере- менные через свободные: х! = 2 — х4 — хз'! хз =7-2х4-3х,; хз = 2+х4 +Зхз. Базисное решение (при нулевых значениях свободных переменных х4 и хз ) в данном случае х, = 2,хз = 7,хз = 2 и является допустимым (значения хихз,хз положительны). Значение целевой функции при таких значениях переменных /(х) = 3 . Но оно может быть уменьшено, если увеличить значение переменной х4, входяшей с отрицательным коэффициентом. Очевидно, что увеличивать х4 можно до тех пор, пока не будут нарушены условия-ограничения задачи, в частности, пока переменные х,, хз и х, будут неотрнцательны.
Например, если х4 — — 2, х, = О . то х! =О,хз =З,хз =4 — новое допустимое решение. При хз =О переменная х, =О, если х4 =2/1 =2; х, =О, если ха =7/2 =3 5хз =О, если х4 =2/(-1) =-2. Чтобы ни одна из переменных хнхз н хз не стала отрицательной, надо выбрать наименьшее положительное отношение элементов столбца свободных членов к соответствуюшнм коэффициентам при хл. Берем х4 — — 2, х, становится равной нулю, т.е. х, переводим в свободные переменные, а ха = 2 становится базисной переменной. Ограничения и целевую функцию надо выразить теперь через х, н хз: из первого уравнения имеем х4-— 2-х,-х,, из второго — хз =3+2х,-х,; нз третьего — х, =4-х, +2х, н /(х) =3-2+х, +хз ьхз =1+к!+2хз.
В данном случае любое увеличение значений свободных переменных х! и х, ведет к увеличению (но не к уменьшению) значений целевой функции, т.е. получили оптимальное решение: Х4 = О, х, = О, хз = 3, хз = 4, х4 = 2, /,„(х) = 1. Какие выводы можно сделать из этого примера? Во-первых, надо так разделить базисные и свободные переменные, чтобы получить допустимое базисное решение, а затем выразить базисные переменные и целевую функцию через свободные переменные. Во вторых, по знаку коэффициентов при неизвестных в целевой фуикции си дг- 45' 692 П иложения ет определить: а) не достигли лимы уже оптимального решения (нет отрицательных коэффициентов); б) значение какой переменной лучше увеличить, т.е, какую переменную следует перевести в свободные.
Другими словами, определяя минимальное положительное отношение элементов столбца свободных членов к коэффициентам при новой свободной переменной, находим переменную, которую необходимо перевести из базисным в свободные. После чего выражаем условия-ограничения и целевую функцию через новые свободные переменные. Процесс повторяют до тех пор, пока не будет получено оптимальное решение. Если среди коэффициентов при неизвестных в целевой функции есть положительный, а все коэффициенты в условиях-ограничениях при нем неположительны, то задача линейного программирования не имеет оптимального решения, минимальное значение целевой функции равно — о.
Рассмотрим геометрическую интерпретацию симплекс-метода. В условиях одной из первых задач линейного программирования, для которых Данциг разработал вычислительный метод, входили ограничения вида , 'х =1, х >О, /=1,п. ты Эти ограничения в п-мерном пространстве определяют симплекс. Симплекс трехмерного пространства изображен на рис, П2.8. Рассмотрим неравенство х, +хг <Ц при условиях х, >О, хт >О. Область решения этого неравенства показана на рис. П2.9. Данное неравенство можно преобразовать в уравнение введением слабой переменной хз. Тогда получим систему х охг+х, =1ь, х, >О, хг >О, хз > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
