Оптимизация при наличии ограничений

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Рязанский государственный радиотехнический университет Кафедра АСУ Контрольная работа По дисциплине: Методы обработки информации Выполнил:

Кабанов А.Н.

Рязань 2012

Имеются три критерия:

y1=1×1+1×2;

y2=2×1+5×2;

y3=4×1+3×2.

Пусть y1 и y2 надо максимизировать, а y3 нужно минимизировать. На х1 и х2, от которых зависят y1, y2 и y3, наложены ограничения:

x1<=3;

x1>=1;

x2<=4;

x2>=1;

Необходимо выполнить оптимизацию с помощью следующих подходов:

критерии различны по значимости;

критерии равнозначны;

метод оптимума номинала.

Критерии, различные по значимости Располагаем критерии по значимости y1>y2>y3. Проводим оптимизацию по самому важному критерию y1, не обращая внимания на другие критерии. Исходная система уравнений:

Решая задачу симплекс-методом, получаем следующую таблицу:

Таким образом, получили, что оптимальная точка для критерия y1:

x1=3, x2=4, y1*=7.

Запишем выражение уступки по первому критерию. В левой части пишется выражение критерия, по которому мы уступаем. В правой части — произведение коэффициента уступки на оптимальное значение критерия. Если критерий максимизируется, то коэффициент уступки ?1, а правая и левая части соединяются знаком ?. Если критерий минимизируется, то коэффициент уступки >1, а правая и левая части соединяются знаком ?.

Уступаем на 10%, т. е. Куст=0.9, получаем следующее выражение уступки:

x1+x2>=6.3.

Решим задачу по второму критерию:

x1<=3;

x1>=1;

x2<=4;

x2>=1;

x1+x2>=6.3.

y2=2×1+5×2>max.

Оптимальное решение по второму критерию получаем путем решения системы уравнений симплекс-методом.

Таким образом, получили, что оптимальная точка для критерия y2:

x1=3, x2=4, y2*=26.

Уступаем на 20%, т. е. Куст=0.8, получаем следующее выражение уступки:

2x1+5×2>=20.8

Решим задачу по третьему критерию:

x1<=3;

x1>=1;

x2<=4;

x2>=1;

x1+x2>=6.3;

2x1+5×2>=20.8.

y3=4×1+3×2>min.

Оптимальное решение по третьему критерию получаем путем решения системы уравнений симплекс-методом.

Таким образом, получили, что оптимальная точка для критерия y3:

x1=2.3, x2=4, y3*=21.2

Критерии равнозначны К исходной системе ограничений добавляем уравнение равнозначности.

;

.

Здесь у1*, у2*, у3* - оптимальные значения критериев при однокритериальной оптимизации (метод рассмотрен выше). y1, y2, y3 — это сами критерии. — относительные потери по каждому критерию Уравнение равнозначности означает, что относительные потери по всем критериям должны быть равны. Знаки модуля вводят нелинейность. Рассуждая логически, знаки модуля можно снять. Если критерий максимизируется, то всегда у1y1*. C учетом вышесказанного для нашего случая снимем знаки модулей с уравнений равнозначности

;

.

оптимизация ограничение задача симплекс Оптимальные значения критериев: y1*=6.3, y2*=20.8, y3*=21.2.

Исходная система ограничений примет вид:

x1<=3;

x1>=1;

x2<=4;

x2>=1;

-((x1+x2−7)/7)=-((2×1+5×2−26)/26)

-((x1+x2−7)/7)=((4×1+3×2−21.2)/21.2)

Преобразуем уравнения равнозначности. Получим систему:

x1<=3;

x1>=1;

x2<=4;

x2>=1;

x1−0.916×2=0

0.165×1+0.142×2=0

Проведем оптимизацию по любому из критериев:

Получим следующее решение:

х1=5.0;

x2=2.1.

Это оптимальная точка, т. е. точка в которой все относительные потери одинаковы.

Метод оптимизации номинала Если критериев много, то ищут точку внутри области примерно на равном расстоянии от границ области. В большинстве случаев применяется квадратичный критерий.

Исходная система ограничений:

Левые части обозначают через y:

Для каждого уi находим максимум и минимум на исходном множестве и находим среднее значение:

.

Тогда система ограничений примет вид:

Это система линейных алгебраических уравнений, она решается следующим образом:

Применим рассмотренный выше метод к нашему случаю.

Исходная система ограничений:

x1<=7;

x1>=2;

x2<=6;

x2>=2;

x1+x2<=10;

2x1+x2>=8.

Найдем средние значения.

Для у1:

Для у2:

Для у3:

В итоге получим:

;

;

.

Получим систему:

4.5=1 +0

6.5=1 +0.5

7.5 =1 +1

Матрица имеет следующий вид:

=

Матрица :

=

Произведение *:

Обратная матрица (АТ*А)-1:

Произведение (АТ*А)-1*АТ:

В результате последнего вычисления найдем, где

= :

=

Или

х1=4.7

х2=3

Таким образом, точка (4.7,3) равноудалена от границ рассматриваемой области.