Xreferat.com » Рефераты по информатике и программированию » Модели и методы принятия решения

Модели и методы принятия решения

Задача 1


Решить графоаналитическим методом:


min j (X) = - 2x1 - x2 + x3 (1)

при

2x1 - x2 + 6x3 Ј 12 (2)

3x1 + 5x2 - 12x3 = 14 (3)

3x1 + 6x2 + 4x3 Ј 18 (4)

X і 0 (5)


Решение:

Этап 1. Построение пространства допустимых решений

Выбираем прямоугольную систему координат: по горизонтальной оси указываем значения переменной х1, по вертикальной - х2.

Далее рассмотрим условие неотрицательности переменных (5):


х1 і 0; х2 і 0 и х3 і 0. (6)


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

Из ограничения (3) можно получить:


3x1 + 5x2 - 12x3 = 14®Модели и методы принятия решения, (7)


с учётом условия неотрицательности третьей переменной (6) получаем новое ограничение:


Модели и методы принятия решения. (8)


Подставляем в ограничение (2) найденное значение (7):


2x1 - x2 + 6x3 Ј 12®Модели и методы принятия решения®

®Модели и методы принятия решения (9)


Подставляем в ограничение (4) найденное значение (7):


3x1 + 6x2 + 4x3 Ј 18®Модели и методы принятия решения®

®Модели и методы принятия решения (10)


Чтобы учесть получившиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых:


Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения.


Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость (х1, х2) на два полупространства, которые располагаются по обе стороны прямой, которая соответствует данному неравенству.

Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую сторону - нет.

На рис.1 допустимые полупространства показаны стрелками.


Модели и методы принятия решения

Рис.1. Нахождение оптимального решения


Ограничения:


Модели и методы принятия решения (А)

Модели и методы принятия решения (В)

Модели и методы принятия решения (С)

х2 і 0 (D)

х1 і 0 (E)


Этап 2. Нахождение оптимального решения

Точки пространства допустимых решений, показанного на рис.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках F, G, H, J и K.

Любая точка, расположенная внутри или на границе области, ограниченной ломаной FGHJK, является допустимым решением, т.к удовлетворяет всем ограничениям.

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

Нахождение оптимального решения требует определения направления убывания целевой функции (1):


min j (X) = - 2x1 - x2 + x3.


Подставляем в целевую функцию найденное значение (7):


Модели и методы принятия решения.


Мы приравниваем j (X) к нескольким убывающим значениям, например, (- 5) и (- 8). Эти значения, подставленные вместо j (X) в выражение целевой функции, порождают уравнения прямых; для значений (- 5) и (- 8) получаем уравнения прямых:


Модели и методы принятия решения

и

Модели и методы принятия решения.


На рис.2 эти прямые показаны штрих-пунктирными линиями, а направление убывания целевой функции - толстой стрелкой.

Целевая функция может убывать до тех пор, пока прямые, соответствующие убывающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей минимально возможному значению целевой функции, и будет точкой оптимума.

Из рис.2 видно, что оптимальное решение соответствует точке Н. Эта точка является местом пересечения прямых (В) и (С), поэтому её координаты х1 и х2 находятся как решение системы уравнений, задающих эти прямые:


Модели и методы принятия решения

Модели и методы принятия решения


Решением этой системы будет:


х1 = 5,36

х2 = 0,16


при этом значение целевой функции равно:


Модели и методы принятия решения.


Ответ:

Оптимальное решение:


х1 = 5,36

х2 = 0,16


при этом значение целевой функции равно:


j (X) = - 10,621.


Модели и методы принятия решения

Рис.2. Нахождение оптимальной точки


Задача 2


Найти экстремумы методом множителей Лагранжа.

Решение проиллюстрировать графически.


extr j (X) = 3x12 + 2x1 + 2x22 + 4x2x3

при

x1 + 2x2 = 19

x1 + 2x3 = 11.


Решение:

Обозначим:


g1 (X) = x1 + 2x2 - 19 = 0,g2 (X) = x1 + 2x3 - 11 = 0.


Функция Лагранжа имеет вид:


Модели и методы принятия решения


Отсюда получаем необходимые условия экстремума в виде системы уравнений:


Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения.


Решаем систему уравнений через определители.

Главный определитель:


Модели и методы принятия решения.


Матрица - столбец левой части системы (свободных членов):


Модели и методы принятия решения.


Находим остальные определители:


Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения.


Находим решение системы уравнений:


Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения.


Таким образом, получили одну экстремальную точку.

Определяем матрицу Гессе:


Модели и методы принятия решения


Матрица Гессе положительно определена, поэтому в найденной точке


Модели и методы принятия решения


функция Лагранжа L (X, l) выпуклая и, следовательно, имеется минимум.

Для графической иллюстрации решения выразим координату х3 из функции ограничения g2 (X):


g2 (X) = x1 + 2x3 - 11 = 0®Модели и методы принятия решения.


Подставим полученное значение в целевую функцию:


j (X) = 3x12 + 2x1 + 2x22 + 4x2x3 = 3х12 + 2х1 +2х22 + 4х2 (5,5 - 0,5х1) =

j (X) = 3х12 + 2х1 +2х22 + 22х2 - 2х1х2.


Получили общее уравнение кривой второго порядка.

Для получения канонического вида уравнения производим поворот системы координат, освобождаясь от члена, содержащего произведение координат.

Угол поворота j определяется формулой:


Модели и методы принятия решения®Модели и методы принятия решения радиан.


При этом получаем новые координаты y и z:


Модели и методы принятия решения,

Модели и методы принятия решения.


Подставляем полученные выражения в целевую функцию:


j (y, z) = 3х12 + 2х1 +2х22 + 22х2 - 2х1х2 =

Модели и методы принятия решения

Модели и методы принятия решения,

Модели и методы принятия решенияМодели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения

Модели и методы принятия решения


Получили уравнение эллипса с центром в точке (y = 1,3633; z = - 7,1513), причём линии симметрии эллипса наклонены на угол j = - 0,55375 радиан относительно начальной системы координат х1х2.

Пересчитаем координаты центра эллипса:


Модели и методы принятия решения,

Модели и методы принятия решения.


На рис.3 представлено графическое решение.

Из рисунка видно, что график уравнения ограничения g1 (X) (сплошная линия) пересекается с графиком целевой функции (пунктирная линия) в точке А.

В точке А с координатами (5,2222; 6,8889) имеется минимум целевой функции:


j (X) = 3х12 + 2х1 +2х22 + 22х2 - 2х1х2 = 3 * 5,22222 + 2 * 5,2222 + 2 * 6,88892 + 22 * 6,8889 - 2 * 5,2222 * 6,8889 = 266,78.


На рис.3 представлена также целевая функция с большим значением:

j (X) = 350.

Центр эллипсов обозначен точкой N (-2,6; -6,8).

Ответ:

Имеется одна точка экстремума - точка минимума (5,2222; 6,8889), при этом целевая функция равна:


j (X) = 266,78.


Модели и методы принятия решения

Рис.3. Графическое решение


Задача 3


Решить на основе условий Куна-Таккера.

Решение проиллюстрировать графически.


extr j (X) = (x1 - 4) 2 + (x2 - 3) 2

при

3x1 - 2x2 Ј 18

x1 + 2x2 Ј 8


Решение:

Обозначим:


g1 (X) = 3x1 - 2x2 - 18 Ј 0,g2 (X) = - x1 + 2x2 - 8 Ј 0.


Записываем функцию Лагранжа:


L (X, S, l) = j (X) - l1 (g1 (X) + S12) - l2 (g2 (X) + S22)

L (X, S, l) = (x1 - 4) 2 + (x2 - 3) 2 - l1 (3x1 - 2x2 - 18 + S12) - l2 (- x1 + 2x2 - 8 + S22)

Отсюда получаем необходимые и достаточные условия экстремума (условия Куна-Таккера) в виде системы уравнений:


Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения,

Модели и методы принятия решения.


Принимаем (из третьего и четвёртого уравнений системы):


Модели и методы принятия решения.


Из первого и второго уравнений системы находим:


Модели и методы принятия решения®Модели и методы принятия решения,

Модели и методы принятия решения®Модели и методы принятия решения,


из пятого уравнения системы:


Модели и методы принятия решения®Модели и методы принятия решения,


из шестого уравнения системы:


Модели и методы принятия решения®Модели и методы принятия решения.


Таким образом, нашли первую точку:


Модели и методы принятия решения.


Принимаем (из третьего и четвёртого уравнений системы):


Модели и методы принятия решения.


Из первого и второго уравнений системы находим:


Модели и методы принятия решения®Модели и методы принятия решения,

Модели и методы принятия решения®Модели и методы принятия решения,


подставляем в пятое уравнение системы:


Модели и методы принятия решения®Модели и методы принятия решения ® Модели и методы принятия решения.


определяем координаты точки экстремума:


Модели и методы принятия решения,

Модели и методы принятия решения,


из шестого уравнения системы:


Модели и методы принятия решения®Модели и методы принятия решения.


Таким образом, нашли вторую точку:


Модели и методы принятия решения.


Принимаем (из третьего и четвёртого уравнений системы):


Модели и методы принятия решения.


Из шестого уравнения системы находим:


Модели и методы принятия решения®Модели и методы принятия решения.


Подставляем полученное значение в первое и второе уравнения системы:


Модели и методы принятия решения®Модели и методы принятия решения,

Модели и методы принятия решения®Модели и методы принятия решения®Модели и методы принятия решения®

Модели и методы принятия решения,

Модели и методы принятия решения.


Подставляем также полученные значения в пятое уравнение системы:


Модели и методы принятия решения®

Модели и методы принятия решения.


Таким образом, нашли третью точку:


Модели и методы принятия решения.


В результате решения системы получаем векторы:


Модели и методы принятия решения.


В точке


Модели и методы принятия решения


имеем глобальный минимум целевой функции:


j (X) = (x1 - 4) 2 + (x2 - 3) 2 = (4 - 4) 2 + (3 - 3) 2 = 0.


В точке


Модели и методы принятия решения


имеем седловую точку целевой функции:


j (X) = (x1 - 4) 2 + (x2 - 3) 2 = (6,7692 - 4) 2 + (1,1538 - 3) 2 = 11,077.


В точке


Модели и методы принятия решения


имеем седловую точку целевой функции:


j (X) = (x1 - 4) 2 + (x2 - 3) 2 = (2,8 - 4) 2 + (5,4 - 3) 2 = 7,2.


Для графической иллюстрации решения строим графики уравнений ограничений:


g1 (X) = 3x1 - 2x2 - 18 Ј 0®Модели и методы принятия решения,

g2 (X) = - x1 + 2x2 - 8 Ј 0®Модели и методы принятия решения


сплошные линии на рис.4 (графики прямых).

Также строим графики целевой функции для седловых точек (проходящих через точки А и В)


j (X) = (x1 - 4) 2 + (x2 - 3) 2 = 11,077®Модели и методы принятия решения,

j (X) = (x1 - 4) 2 + (x2 - 3) 2 = 7,2®Модели и методы принятия решения,


и минимума (проходящий через точку С) - центр окружности:


j (X) = (x1 - 4) 2 + (x2 - 3) 2 = 0®Модели и методы принятия решения


пунктирные линии на рис.4 (графики окружностей с центром в точке Модели и методы принятия решения).

Из графика также видно, что глобального максимума целевой функции достичь невозможно!


Модели и методы принятия решения

Рис.4. Графическое решение

Ответ:

В точке С


Модели и методы принятия решения


имеем глобальный минимум целевой функции:

j (X) = 0.

В точке В


Модели и методы принятия решения


имеем седловую точку целевой функции:

j (X) = 11,077.

В точке А


Модели и методы принятия решения

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: