Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 8

Найдем решення данной системы уравнений и неравеыстз. Пусть г,з в О, тогда согласно (2.17) имеем х1+ 2хг.-- 4. откуда получаем х1= 4 в 2хг. (2,21) Тогда возможны следующие три случая: 1. Пусть ) 1= О. Из (2.13) следует 2х ~ — - — "ьз. Тогда по (2.21) имеем ьз= 4хг- 8. (2.22) Из (2.16) прн 1г и 0 следует х г= О. Тогда согласно (2.22) имеем л.з — — — 8. Отсюда иэ (2.14) получаем 2, г — — — 16. Согласно (221) пры хг-— О имеем х ~ = 4. Поэтому Хг — — (4;О), Аг — — (О; — 16; — 8), ДХг) = 16. Анализируя по рнс. 2.11 принадлежащего ХО е-окрестность точки Хг, получаем, что для любой точки Х данной окрестноств выполыяется условие У(Х) > У(Хг), поэтому Хг= Хг является локальным максимумом функции У(Х).

2. ПУсть Х1в О, Хг = О, тогда по (2Л4) имеем хг= — ).э, а из (2.15) следует х 1 = О, Поэтому согласно (2ЛЗ) имеем 2,1 = г, э, а по (2.21) получаем х г = 2. Тогда имеем 2,1 — — Хз= — 2. Следовательно, Хз = (О; 2), АЗ= (- 2; 0; — 2), г(Х5) = 4. Исследуя принадлежащую Хб е-окрестность точки ХЭ, получаем, что для любой точки 54 Х даыной окрестности выполняется условие г'(Х) >,г(Хз), поэтому Хз= Хз является локальным максимумом функции )(Х). 3. Пусть Л з —— ) г— - О, тогда по (2.13) — (2Л4) имеем 2х1= — г,.з, хг= — ) з. Тогда согласно (2.21) получаем ).з= — 1,6, х1 — — 0,8, хг= 1,6.

Поэтому Х4 — — (08;1,6), А4 — — (О;0; — 1,6), ~(Х4)= 32. Анализируя принадлежащую ХВ е-окрестность точки Х4, получаем, что для некоторых точек Х данной окрестности выполняется условие у(Х) < )(Х4), а для других точек Х данной окрестности выполняется условие )(Х ) > ~(Х4), поэтому Х4 является точкой перегиба (только стационарной точкой функции ~(Х), но не локальным максимумом). Таким образом, функцвя ~(Х) нмеет глобальный миннмум в точке Х~, глобальный максимум в Хг (так кзк ((Хг) > ~(Хз) ), локальыый максимум в Хз н только стационарную точку, но не экстремум, в Х4.

Геометрическая интерпретация применения метода, основанного ыа теореме Куна — Такера, к решению второй задачи условной оптимизации функции у'(Х) при ограничениях типа неравенств представлена на рис. 2.11. Отметим, что функция г(Х) — строго выпуклая, так как соблюдается положительная определенность ее матрицы Гессе; 2 0 Ь1 — — 2> О, Ьг — — 0 2 = 4> О. Область ХВ, заданная ограничениями, является выпуклой.

Поэтому задача ш!и /(Х) — заХе ХВ дача выпуклого программирования, а задача шах г(Х) — нет. Хе ХВ Следовательно, необходимое условие минимума является также и достаточным, и имеется один локальный минимум Х ~, совпадающий с глобальным. На этом заканчивается решение второй задачи условной оптимизации для варианта заданыя Ж= 20. Дополнительно найдем экстремум той же функции г г )'(Х) = х1+ хг при другом ограничении: х ~+ 2х г~ 4, используя метод, основанный на теореме Куыа — Такера. 55 (2.23) 2хз — )=О, 2хз- 2А= О, (2.24) А( — х1 — 2 ха+ 4) = О, — х1 — 2хз+ 4< О, (2.25) (2.26) (2.27) Ряс. 2яз СОДЕРЖАНИЕ ОТЧЕТА (2.28) 2х1= хз= Х Приведем ограничеяие к виду у(Х) < О, умножив обе части заданного неравенства на — 1, .тогда получим у(Х) = — х ~— — 2хз+ 4> О.

По теореме Куна — Такера имеем следующее необходимое условие экстремума фуякции ~(Х): А> 0 для нахождения минимума ~(Х) и ХЕ О для максимума. Решим данную систему уравнений и неравенств, Из (2.23)— (2.24) имеем Тогда при х1= хз= 0 не выполняется (2.26). Поэтому х1х 0 и хам О. Отсюда согласно (2.28) 7 х О. Поэтому из (2.25) следует х1+ 2 х з — — 4. Тогда по (2.28) получаем х1 — — 0,8, х з = 7 = 1,6. Следовательно, Х" = (0,8;1,6), Х= 1,6> О, ('(Х') = 3,2. Геометрическая интерпретация применения метода, основанного на теореме Куна — Такера, к решению данной задачи условной оптимизации функции 7'(Х) прн ограничениях типа неравенств представлеяа ва рис.

2.12. Исследуя принадлежащую ХР~ е-окрестность точки Х*, получаем, что для любой точки Х данной окрестности выполняется условие г(Х) >г(Х ), поэтому Х является локальным минимумом функции 7(Х) . Других точек, удовлетворяющих системе уравненнв и неравенств (2.23)— (2.27), не существует, следовательно, Х" — также глобальный минимум фуякцяи У(Х). Отметим, что функция 7(Х) — строго выпуклая, область ХР ~ — выпуклая.

Поэтому задача шш 7(Х) — задача выпуклого Ха ХО, программирования, а задача птах У(Х) — вет. Следовательно, не- Х ХО, обходнмое условие минимума является также н достаточным, и имеется один локальный минимум Х, совпадающий с глобальным.

1, Навменозание работы. 2, Цель работы. 3, Решаемые задачи согласно Вашему варианту задания. 4. Решенве первой задачи условной оптимвзации функции при ограничениях типа равенств с помощью метода множителев Лагранжа и геометрическая интерпретация применения метода к решению данной задачи. 5. Решение второй задачи условной оптимизации функции при ограничениях типа неравенств согласно методу, основанному на теореме Куна — Такера„и геометрическая интерпретация применения метода к решению данной задачи.

6. Полученные на ЭВМ результаты решения каждой вз двух задач условной оптимизации функции. 7. Выводы. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАЧИ 1. Перечислите методы решения задач условной оптимизации при ограничениях тапа равенств и сравните их между собой. 2. В чем состоят методы множителей Лагранжа и поиска седловой точки функции Лаграяжа7 3.

Перечислите методы решения задач условной оптимизации при ограничениях типа неравенств и сравните нх между собой. Опишите классвческнй метод решения таких задач и метод, основанный на теореме Куна — Такера. 4. В чем состоит задача выпуклого программврованвя и ее решение? 5. Найдите решение заданной преподавателем задачи условной оптимизации функции с помощью выбранных Ванн трех методов. Работа 3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ От основной формы записи ЗЛП можно перейти к канонвческой. Для этого вводятся дополнятельные переменные л у = ар — ~~! а,хс> 0 (1= 1,т). (34) 1=1 Тогда каноническая форма ЗЛП будет иметь вид (31), (3.3) и ", а,хс+ и.= ао, ру> 0 О= 1,т и г' Общая форма записи ЗЛП имеет ввд ехьг г'(Х), Х Цель работы; изучить н практически овладеть методами решения задач линейного программирования. ОБЩИБ СВЕДЕНИЯ Задачи линейного программирования н их геометрическая интерпретация ,г (Х ) = е о + х~~ е где е; (1= О, п ) — константы.

В литературе существуют различные формы записи ЗЛП. Основная форма запвсн нмеет вид: шах ~ е!х,. Х (3.1) прн ограничениях п ~~! а !х,.ь а о (/= 1,т), 1=1 (3.2) х;> 0 (1= 1,и). (3.3) Задачи линейного программирования (ЗЛП) — зто задачи математического программирования прн условии, что линейнымв являются как целевая функция, так и все функции в ограничениях. Линейной называется функция вида где У(Х) = е„+ Ч', е,,х! 1=1 прн ограничениях: л ~', а)! х ! ь а о (! = 1, т ), 1=1 и ч~, а, х,, > а ! (1 = т + 1, т + й ), !=1 (1= т+ ?с+ 1,т+ й+ и), а о> 0 (1= 1,т+ ?с+ и), х!> 0 (1= 1,и).

Рассмотрим геометрическую интерпретацию ЗЛП. Вначале дадим некоторые определения. Точка Х1, принадлежащая выпуклому множеству, называесся его крайней точкой, если в данном мнохсестве не существует двух других )(1 точек Х и Х таких, что точка Х! Х можег .быть выражена их линейндй комбинацией Х! = иХ+ (1 — а) Х, Х4 где 0< и< 1.

На рнс. 3 1 приведен пример четырех крайних точек х, Х, (1= 1,4). О Рис. зл Крайней точкой множества может быть лишь его граничная точка, но не все гранвчные точки являются крайними. Всякое непустое, выпуклое, замкнутое, ограниченное множество имеет хотя бы одну крайнюю точку. Выпуклая, замкнутая область (множество), имеющая конечное число крайних точек, называется выпуклым многогранником (при я= 2 многоугольянком), если данная область ограничена.

Если она не ограничена, то это выпуклая многогранная (многоугольная) область. Крайние точки такой области н выпуклого многогранника (многоугольпнка) называют вершинами. Каждое ограничение типа неравенства (например, р > 0 или х,к О) выделяет в пространстве координат полупространство, которому принадлежат все точки, лежащие по одну сторону от гнперплоскости (у = 0 или х,= О) н на самой этой гиперплоскости. Данное полупространство (при и= 2 полуплоскость) является выпуклым мяожеством. Ограничение типа равенства выделяет в пространстве координат гвперплоскость (при п= 2 плоскость), являющуюся тоже выпуклым множеством.

Пересечение всех полупространств и гиперплоскостей, задаваемых всеми ограничениями, если они не противоречивы, будет областью ХР допустимых решений ЗЛП. Область ХР является выпуклой многогранной (прн и = 2 многоугольной) областью яли выпуклым многограяником (многоугольником илв в частном случае отрезком прямой илв точной).

Если существует конечное оптимальное решеяие ЗЛП (минимум и/илв максимум), то оно достигается либо в одной из вершин выпуклого многогранника вли многогранной области ХР, либо на выпуклом множестве, порождаемом двумя или более вершинами (на граяи многогранника или многогранной области, стороне многоугольника нлн многоугольной области), Возможны следующие случаи областен ХР допустимых значений Х и соответствуюгцих им оптимальных решений ЗЛП. Система уравнений н неравенств, задаваемая ограничениями, несовместна. Тогда области ХР не существует н нет решений ЗЛП. Прямер отсутствия области ХР при я= 2 изображен на рис. 3.2. 2.

Область ХР яе является ограниченной. 2.$. Область ХР но ограничена в направлении возрастания функции /(Х), тогда при поиске максимума этой функции ре- 60 щенке ЗЛП не ограничено,,т.е. нет конечного решения ЗЛП, а прн поиске минимума функцнв /(Х) оптимальное решение ЗЛП находится в точке Х' (точках) области ХР, ближайшей к линии постоянного уровня функция /(Х) = со, Рис. 3.2 Ряс.

3.3 Пример даяной областн ХР и решения ЗЛП при я= 2 приведен на рис. 3.3. Стрелкой на линии постоянного уровня функции /(Х) = со будем показывать направление ее возрастания. 2.2. Аналогично, если ХР не ограничена в направлении убыва- ссз ння функции /(Х), тогда при по- й иске минимума этой функции решение ЗЛП не ограничена, т,е. нет конечного решения ЗЛП, а при Х" поиске максимума функции /(Х) й~ оптимальное решение ЗЛП находится в точке Х" (точках) области 8Х) Сс ХР, ближайшей к ливии постоян- Рэс. З.с ного уровня функции /(Х) = со. Пример даннов области и решения ЗЛП при л = 2 н целевой функции /~ (Х) приведен ва рнс.