Лабораторные работы по Методам Оптимизации

Автор: Пользователь скрыл имя, 13 Декабря 2011 в 08:55, лабораторная работа

Краткое описание

Динамическое программирование – метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).

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

Файлы: 2 файла

Лабараторная работа №2.doc

— 939.50 Кб (Скачать)
 

Введение.

   Динамическое  программирование – метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).

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

   К основным задачам динамического  программирования относятся:

         - оптимальная стратегия  замены оборудования;

         - оптимальное распределение ресурсов;

         - распределение   инвестиций   для   эффективного   использования потенциала предприятия;

         - минимизация затрат  на строительство и эксплуатацию  предприятий; нахождение рациональных  затрат при строительстве трубопроводов  и транспортных артерий и т.д.

Постановка  задачи.

    Совет директоров фирмы рассматривает  предложения по наращиванию производственных мощ –ностей для увеличения выпуска  однородной продукции на четырех  предприятиях, принадлежащих фирме. Для модернизации предприятий совет  директоров инвестирует средства в объеме 250 млн. рублей с дискретностью 50 млн. рублей. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены в таблице. 

Инвестиции, млн р. Прирост выпуска продукции, млн руб.
Предприятие 1 Предприятие 2 Предприятие 3 Предприятие 4
50 25 26 27 28
100 34 33 35 35
150 46 46 45 44
200 57 58 56 55
250 78 77 79 80
 

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

Динамическое  программирование

   В нашем распоряжении имеется какой-то запас средств (или ресурсов) К, который должен быть распределен между предприятиями P1, P2, ..., Pm. Каждое из предприятий Pi при вложении в него каких-то средств x приносит доход, зависящий от x, то есть представляющий собой какую-то функцию fi(x). Все функции fi(x), где i = 1, 2, ..., m, заданы (разумеется, эти функции – неубывающие). Нужно найти, как распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

   Обозначим через xk количество средств, выделенных k-му предприятию. Тогда суммарная прибыль равна

 
 

Переменные x удовлетворяют ограничениям

 
 
xk ≥ 0, k = 1, 2, 3, 4

   Процесс распределения средств рассматриваем как 4-шаговый, номер шага совпадает с номером предприятия. Уравнения состояний в данной задаче имеют вид:

   

=
, k = 1, 2, 3, 4

где sk (параметр состояния) – количество средств, оставшихся после k-го предприятия, то есть средства, которые останется распределить между оставшимися 4-k предприятиями.

   Введем  в рассмотрение функцию ( ) – условную оптимальную прибыль, полученную от k-го, (k + 1)-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства

Sk 1(0 ≤ Sk 1 ≤ 5)

   Допустимые  управления на k-м шаге удовлетворяют: 0 ≤ xk 1 ≤ 5 (либо k-му предприятию ничего не выделяем, xk = 0, либо не больше того, что имеем к k-му щагу, xk Sk 1).

   Уравнения Беллмана имеют вид:

                                                        k = 4, S4 = 0         (s3) =                        , 
 
                                                       (s2) =                         (s3)  

                                                   (s1) =                         (s2)  

                                                 (s0 = 5) =                         (s2)  

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

   Опишем  подробно процесс заполнения данной таблицы. Хотя наша задача в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй – в П2 и так далее.

   Управляемая система S в данном случае – средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства x1, х2, ..., хm,  выделяемые предприятиям. Требуется найти оптимальное управление, то есть такую совокупность чисел x1, х2, ..., хm, при которой суммарный доход максимален:

   Найдем  для каждого k-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш (S), а со –ответствующее ему условное оптимальное управление – средства, вкладываемые в k-e предприятие, – (S). 
 

   Начнем  оптимизацию с последнего, m-го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Pm. Поэтому условное опти –

мальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S, то есть:

(S) = S

а условный оптимальный  выигрыш

(S) =
(S)

   Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать хm(S) и Wm(S). Последний шаг оптимизирован.

   Перейдем  к предпоследнему, (m – 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим через Wm – 1(S) условный оптимальный выигрыш на двух последних шагах: (m – 1)-м и m-м (который уже оптимизирован). Если мы выделим на (m – 1)-м шаге (m – 1)-му предприятию средства х, то на последний шаг останется S – х. Наш выигрыш на двух последних шагах будет равен:

(х) +
(S – х)

и нужно  найти такое х, при котором этот выигрыш максимален: 

                                       (S) =                   (x) + (S – x)

   Знак  max означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть услов –ный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достига –ется – условное оптимальное управление на (m – 1)-м шаге. Далее оптимизируем (m – 2)-й, (m – 3)-й и так далее. Вообще, для любого k-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле

Лабораторная работа № 1.doc

— 160.50 Кб (Открыть, Скачать)

Информация о работе Лабораторные работы по Методам Оптимизации