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

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

width="90" height="53" align="BOTTOM" border="0" />


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

j (X) = 7,2.

Глобального максимума целевой функции достичь невозможно.


Задача 4


Получить выражение расширенной целевой функции (РЦФ) и составить блок-схему алгоритма численного решения задачи методом штрафных функций в сочетании с одним из методов безусловной минимизации.

Решить задачу средствами MS Excel.

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


max j (X) = - 2x1 + 8x2 - x12 - x22 (11)

при

x1 + 2x2 Ј 12

x1 + x2 і - 8

X і 0


Решение:

Обозначим ограничения:


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

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


Расширенная целевая функция образуется суммой целевой функции Модели и методы принятия решения и штрафной функции Модели и методы принятия решения:


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


Штрафную функцию можно построить различными способами. Однако, наиболее часто она имеет вид:


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


Где


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

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


Модели и методы принятия решения, Модели и методы принятия решения - некоторые константы, представляющие собой весовые коэффициенты.

Используя штрафную функцию, последовательно переходим от одной расчётной точки к другой до тех пор, пока не получим приемлемое решение. При этом координаты последующей точки находим по формуле:


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


где Модели и методы принятия решения - шаг вычислений.

Чем меньше Модели и методы принятия решения и Модели и методы принятия решения, тем быстрее находится приемлемое решение, однако точность определения его снижается. Поэтому итерационный процесс обычно начинают при сравнительно малых значениях Модели и методы принятия решения и Модели и методы принятия решения но, продолжая его, эти значения постепенно увеличивают.

Итак, процесс нахождения решения задачи включает следующие этапы:

1. Определение исходного допустимого решения.

2. Выбор шага вычислений.

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

4. По указанной ранее формуле (12) нахождение координаты точки, определяющей возможное новое решение.

5. Проверка, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переход к следующему этапу. Если координаты найденной точки определяют допустимое решение, то исследование необходимости перехода к последующему допустимому решению. В случае такой необходимости переход к этапу 2, в противном случае найдено приемлемое решение задачи.

6. Установка значения весовых коэффициентов и переход к этапу 4.

Построим область допустимых решений задачи (рис.5) и линии уровня, определяемые целевой функцией (11):


j (X) = - 2x1 + 8x2 - x12 - x22

j (X) = - (x12 + 2х1 + 1) + 1 - (x22 - 8х2 + 16) + 16

j (X) = - (x1 + 1) 2 + 1 - (x2 - 4) 2 + 16

j (X) = - (x1 + 1) 2 - (x2 - 4) 2 + 17 (13)


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

Рис.5. Область допустимых решений


Линиями уровня служат окружности с центром в точке (- 1;

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

Из вида целевой функции (11) можно сделать вывод:

чем дальше точка от центра окружности, тем всё меньше целевая функция, максимум целевой функции будет в точке касания окружности вертикальной оси координат (точка А на рис.5), при этом: х1 = 0; х2 = 4

и целевая функция равна:


j (X) = - (x1 + 1) 2 - (x2 - 4) 2 + 17 = - (0 + 1) 2 - (4 - 4) 2 + 17 = 16.


Для решения задачи методом штрафных функций примем начальное значение допустимого решения:


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


Выбираем шаг вычислений и точность вычислений:

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

Принимаем весовые коэффициенты:

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

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

Находим частные производные от целевой функции:


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

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


Определяем частные производные от функций ограничения:


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

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

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

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


Далее вычисления производим в среде MS Excel (см. файл KursR_MMPR. xls) по алгоритму, приведённому на Рис.6.

Результат расчёта в среде MS Excel представлен в таблице 1.

Графически решение представлено на рис.5, где максимальное значение целевой функции достигается в точке А (0;

4) и равно:

j (X) = 16.

Ответ:

В точке


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


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

j (X) = 16.


Модели и методы принятия решенияТаблица 1. Результат расчёта в среде MS Excel

итерации

Текущее

Допустимое

решение?

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

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

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

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

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

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

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

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

Новое

Допустимое

решение?

Конец

расчёта?


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

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










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

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



1 3 2 Да 0 0 -8 4 -1 -2 -1 1 2,2 2,4 Да Нет
2 2,2 2,4 Да 0 0 -6,4 3,2 -1 -2 -1 1 1,56 2,72 Да Нет
3 1,56 2,72 Да 0 0 -5,12 2,56 -1 -2 -1 1 1,048 2,976 Да Нет
4 1,048 2,976 Да 0 0 -4,096 2,048 -1 -2 -1 1 0,6384 3,1808 Да Нет
5 0,6384 3,1808 Да 0 0 -3,2768 1,6384 -1 -2 -1 1 0,31072 3,34464 Да Нет
6 0,31072 3,34464 Да 0 0 -2,62144 1,31072 -1 -2 -1 1 0,048576 3,475712 Да Нет
7 0,048576 3,475712 Да 0 0 -2,09715 1,048576 -1 -2 -1 1 0 3,58057 Да Нет
8 0 3,58057 Да 0 0 -2 0,838861 -1 -2 -1 1 0 3,664456 Да Нет
9 0 3,664456 Да 0 0 -2 0,671089 -1 -2 -1 1 0 3,731565 Да Нет
10 0 3,731565 Да 0 0 -2 0,536871 -1 -2 -1 1 0 3,785252 Да Нет
11 0 3,785252 Да 0 0 -2 0,429497 -1 -2 -1 1 0 3,828201 Да Нет
12 0 3,828201 Да 0 0 -2 0,343597 -1 -2 -1 1 0 3,862561 Да Нет
13 0 3,862561 Да 0 0 -2 0,274878 -1 -2 -1 1 0 3,890049 Да Нет
14 0 3,890049 Да 0 0 -2 0,219902 -1 -2 -1 1 0 3,912039 Да Нет
15 0 3,912039 Да 0 0 -2 0,175922 -1 -2 -1 1 0 3,929631 Да Нет
16 0 3,929631 Да 0 0 -2 0,140737 -1 -2 -1 1 0 3,943705 Да Нет
17 0 3,943705 Да 0 0 -2 0,11259 -1 -2 -1 1 0 3,954964 Да Нет
18 0 3,954964 Да 0 0 -2 0,090072 -1 -2 -1 1 0 3,963971 Да Да

Литература


1. Таха Х. Введение в исследование операций, 7-е издание: Пер с англ. - М.: Изд. дом "Вильямс", 2005.

2. Реклейтис Г., Рэйвиндран А., Рэгсдел К. Оптимизация в технике / Пер. с англ. В 2-х кн. Кн.1 - М: Мир, 1986.; Кн.2 - М: Мир, 1986.

3. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие. - М.: Высшая школа, 1986.

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