Методические указания и задания для лабораторной работы по теме: Динамическое программирование. Одесса 2004 - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Н. Э. Баумана Методические указания для лабораторной работы по курсам... 3 491.09kb.
Линейное программирование 1 1201.82kb.
Методические указания к лабораторной работе 7 для студентов по специальности... 1 280.05kb.
Методические указания Для выполнения лабораторной работы следует... 1 141.04kb.
Методические указания и контрольные задания по дисциплине 2 645.66kb.
Администрирование в информационных сетях: Методические указания к... 1 177.85kb.
Методические указания по выполнению лабораторной работы «Оказание... 1 511.04kb.
Методические указания и задания для выполнения практических и самостоятельных... 1 120.29kb.
Учебно-методические указания к выполнению лабораторной работы по... 1 209.52kb.
Методические указания для выполнения курсовой работы студентами IV-V... 3 703.53kb.
Методические указания по выполнению контрольной работы для направлений... 1 138.13kb.
Актуальность темы. Влияние цвета на нашу жизнь переоценить трудно 3 379.34kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Методические указания и задания для лабораторной работы по теме: Динамическое программирование. - страница №1/1

Одесский национальний университет им. И.И.Мечникова

Институт математики, экономики и механики

Кафедра оптимального управления и

экономической кибернетики

Методические указания

и задания для лабораторной работы по теме:


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

ОДЕССА


2004

Метод динамического программирования

Динамическое программирование — метод оптимиза­ции, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные эта­пы (шаги). Такие операции называются многошаговыми.

В основе метода динамического программирования лежит принцип оптимальности, сформулированный Р.Беллманом. Этот принцип и идея включения конкретной за­дачи оптимизации в семейство аналогичных многошаго­вых задач приводят к рекуррентным соотношениям — функциональным уравнениям — относительно оптималь­ного значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.

Р
ассматривается управляемая система, которая под влиянием управления переходит из начального состояния в конечное состояние .

Предположим, что процесс управления системой можно разбить на n шагов. Пусть ,,…,— состояния системы после первого, второго, ..., n-го шага.

С
остояние системы после k-ro шага (k=1, 2, ... ,n) характеризуется параметрами k(1), k(2),…,k(s) кото­рые называются фазовыми координатами. Состояние , можно изобразить точкой s-мерного пространства, назы­ваемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий которые составляют управление системой

U=()

где — управление на k-м шаге, переводящее систему из состояния в состояние . Управление , на k-м шаге заключается в выборе значений определенных управляющих переменных uk(1), uk(2),…, uk(n).

Предполагаем впредь, что состояние системы в конце k-гo шага зависит только от предшествующего состояния системы и управления на данном шаге . Такое свойство получило название отсутствия последействия. Обозначим эту зависимость в виде

= Fk(,) (1.1)

Равенства (1.1) получили название уравнений состояний. Функции Fk(,) полагаем заданными.

Варьируя управление U, получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы и от выбранного управления U:

Z=Ф(,U) (1.2)

Показатель эффективности k-гo шага процесса управления, который зависит от состояния в начале этого шага и управления , выбранного на этом шаге, обозна­чим через fk(,). В рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.

Z=fk(,) (1.3)

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z — мультипликативная функция, заданная в виде

Z=fk(,)

то можно рассмотреть функцию Z' = logZ, которая является аддитивной.

Обычно условиями процесса на управление на каждом шаге накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.

Задачу пошаговой оптимизации можно сформулиро­вать так: определить совокупность допустимых управле­ний , переводящих систему из начального состояния в конечное состояние и максимизирую­щих или минимизирующих показатель эффективности (1.3).

Начальное состояние и конечное состояние мо­гут быть заданы однозначно или могут быть указаны множество 0 начальных состояний и множество n ко­нечных состояний так, что 0, n. В последнем случае в задаче пошаговой оптимизации требуется опре­делить совокупность допустимых управлений, перево­дящих систему из начального состояния 0 в конеч­ное состояние n и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3), называется оптималь­ным управлением и обозначается через U*=()

Если переменные управления принимают дискрет­ные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляю­щих переменных на каждом шаге (r) различают одно­мерные и многомерные модели ДП . Число шагов в за­даче может быть либо конечным, либо бесконечным.

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



Принцип оптимальности. Уравнение Беллмана

Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управ­ление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом.

Управление на каждом шаге надо выбирать с учетом его последствий на предстоящих шагах. Это основное правило ДП, сформулированное Р. Беллманом, называется принципом оптимальности.

Оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние на любом шаге и управление, выбранное на этом шаге, последую­щие управления должны выбираться оптимальными от­носительно состояния, к которому придет система в кон­це данного шага.

Использование этого принципа гарантирует, что уп­равление, выбранное на любом шаге, является не локаль­но лучшим, а лучшим с точки зрения процесса в целом.

Так, если система в начале k-гo шага находится в состоянии и мы выбираем произвольное управление , то система придет в новое состояние = Fk(,), и дальнейшие управления должны выбирать­ся оптимальными относительно состояния . Последнее означает, что при этих управлениях максимизируется по­казатель эффективности на последующих до конца процесса шагах k+l, ... ,n, т. е. величина fi(,).

Показатель, характеризующий суммарную эффектив­ность от данного k-го до последнего n-го шага, будем обозначать через Zk, т. е.

Zk = fi(,).

Задача оптимизации процесса, начиная с k-го до последнего n-го шага , похожа на исходную при начальном со­стоянии системы , управлении Uk=() и по­казателе эффективности Zk=Ф(,Uk) [аналогично (1.2)]. Выбрав оптимальное управление Uk* на оставших­ся n-k+1 шагах, получим величину Zk* = max Zk, которая зависит только от , т.е.

Zk*()=Ф(,Uk) = Ф(,Uk*) (1.4)

Назовем величину Zk*() условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление , то система придет в состояние . Соглас­но принципу оптимальности, какое бы мы ни выбрали, на последующих шагах управление () долж­но выбираться так, чтобы показатель эффективности Zk+1 достигал максимального значения, равного Zk+1*() . Остается выбрать управление . Его нельзя выбирать из условия локальной максимизации показателя эффек­тивности на данном k-м шаге, лишь бы получить max fk(,). Такой подход был бы недальновидным, поскольку от выбора зависит новое состояние , а от последнего — максимально возможная эффективность, которая может быть достигнута в дальнейшем, т. е. ве­личина Zk+1*() . Поэтому необходимо выбирать управ­ление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)- го) приводило бы к общему максимуму эф­фективности на n-k+1 шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:




Zk*() ={ fk(,) + Zk+1*() } (1.5)

получившего название основного функционального урав­нения ДП, или уравнения Беллмана.

Из уравнения (1.5) может быть получена функция Zn-1*(), если известна функция Zn-1*() ; аналогично можно получить Zn-1*(), если найдена Zn-1*(), и т. д., пока не будет определена величина Z1*(0), пред­ставляющая по определению максимальное значение по­казателя эффективности процесса в целом:

Zk*=Ф(,U) .

Соотношения (1.5) для определения последовательно­сти функций Zk*() через Zk+1*() (k = n, n-1,..., 1) получили название основных рекуррентных уравнений Беллмана.

Решая уравнение (1.5) для определения условного максимума показателя эффективности за n-k+l шагов, начиная с k-гo, мы определяем соответствующее опти­мальное управление , при котором этот максимум до­стигается. Это управление также зависит от . Будем обозначать такое управление через * () и называть условным оптимальным управлением на k-м шаге.

Основное значение уравнения (1.5), в котором реали­зована идея динамического программирования, заклю­чается в том, что решение исходной задачи определения максимума функции (1.2) n переменных сводится к решению последовательности п задач, зада­ваемых соотношениями (1.5), каждое из которых являет­ся задачей максимизации функции одной переменной . Эти задачи оказываются взаимосвязанными так как в соотношении (1.5) при определении Zk*() учитывает­ся найденная при решении предыдущей задачи функция Zk+1*().



Задача распределения ресурсов.

Построение модели ДП и построение вычислительной схемы

Задача 1. Планируется распределение начальной суммы средств 0 между п предприятиями П1, П2, ..., Пn. Предполагается, что выделенные предприятию Пk в на­чале планового периода средства xk приносят доход fk(xk) (k=l, 2, ..., n). Будем считать, что:



  1. доход, полученный от вложения средств в пред­приятие Пk, не зависит от вложения средств в другие предприятия;

2) доход, полученный от разных предприятий, выра­жается в одинаковых единицах;

3) общий доход равен сумме доходов, полученных от распределения всех средств по всем предприятиям.

Определить, какое количество средств нужно выде­лить каждому предприятию, чтобы суммарный доход был максимальным.

Запишем математическую постановку задачи.

Суммарный доход определяется функцией

Z = (*)

Переменные xk должны удовлетворять условиям

x1 + x2 +…+ xn = 0 ; xk  0 (k=1,…,n) (**)

Требуется определить переменные х\, ..., хп, которые удовлетворяют ограничениям (**) и обращают в мак­симум целевую функцию (*).

Аналогичная задача оптимизации решалась в класси­ческом анализе с помощью множителей Лагранжа. В прикладных задачах классический метод Лагранжа, как правило, неприменим по многим причинам и прежде всего — по причине размерности. Искать абсолютный максимум функции п переменных, даже если эта функ­ция дифференцируема, дело

трудоемкое. Если к тому же учесть, что экстремум может достигаться на границе, то к исследованию стационарных точек внутри области при­бавляется исследование стационарных точек на ее гра­нице. В практических задачах переменные xk могут при­нимать дискретные значения (например, средства выде­ляются в размерах, кратных 10 ед.), а функции дохода fk(xk) могут быть недифференцируемыми или даже за­данными таблично. Во всех этих случаях классические методы оптимизации неприменимы. К решению задачи можно применить методы нелинейного программирова­ния. Однако и они оказываются эффективными лишь при ряде дополнительных свойств функций fk(xk), которые на практике часто не выполняются. Наконец, иногда бы­вает важно не только получить решение конкретной зада­чи при определенных 0 и n, но и исследовать чувстви­тельность решения к изменению этих исходных данных, что при использовании классических методов затрудни­тельно.

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

Перейдем к описанию задачи в виде модели ДП. Внутреннее свойство процесса распределения средств между п предприятиями позволяет рассматривать его как n-шаговый процесс. За номер k-гo шага примем но­мер предприятия, которому выделяются средства хk. На 1-м шаге выделяем 1-му предприятию средства х1, на 2-м шаге — 2-му предприятию выделяем средства х2 из оставшихся и т. д. Очевидно, что переменные xk (k=1, ..., n) можно рассматривать как управляющие пе­ременные. Начальное состояние системы характеризуется величиной o средств, подлежащих распределению. Пос­ле выделения х1 остается 1 = 0 –x1 средств и т. д. Вели­чины go, 1,2,…,n характеризующие остаток средств пос­ле распределения на предшествующих шагах, будем рассматривать как параметры состояния. Уравнениями состояния служат равенства

k = k-1 –xk (k=1, ..., n) (1.6)

Суммарный доход за п шагов составляет

Z = Ф (o ,U) = (1.7)

и представляет собой показатель эффективности процес­са, имеющий, как видно из этого равенства, аддитивную форму.

Если к началу k-гo шага остаток средств равен k-1 то доход, который можно получить на оставшихся n-k+1 шагах (т. е. от выделения средств предприятиям Пk, Пk+1, ..., Пn), составит Zk =

Максимальный доход за эти n-k+1 шагов зависит от того, сколько средств осталось от предыдущих k-1 шагов, т. е. от величины k-1. Поэтому будем его обозна­чать через Zk*(k-1). Очевидно, что Z1*(0) =Zmax, т. е. Z1*(0) представляет собой суммарный максимальный до­ход за п шагов (доход, полученный при оптимальном распределении средств 0 между п предприятиями).

Рассмотрим любой k-й шаг. Очевидно, что xk можно выбирать из условия 0  xk  k-1 .Значение xk, удовлет­воряющее этому двойному неравенству, называется до­пустимым. Принцип оптимальности в этом конкретном случае означает, что, выделив величину xk и получив от k-гo предприятия доход fk(xk), мы должны распорядить­ся оставшимися средствами k = k-1 –xk наивыгодней­шим образом и получить от предприятий Пk+1, ..., Пn максимальный доход Zk+1*(k). Ясно, что величину xk следует определять из условия максимизации суммы fk(xk)+ Zk+1*(k).

Таким образом, получаем уравнение Беллмана

Zk*(k-1) = { fk(xk)+ Zk+1*(k)}. (1.8)

Перейдем к схеме вычислений. Нас интересует Z1*(0) , но если начать с 1-го шага, т.е. с решения за­дачи

Z1*(0) = { f1(x1)+ Z2*(1)},

то необходимо знать Z2*(1). В свою очередь, при опре­делении Z2*(1) нужно знать Z3*(2), и т. д. Однако име­ется шаг, за которым нет последующих. Таким является n-й шаг, на котором выделяются средства последнему предприятию Пп. Для него равенство (1.8) имеет вид

Zn-1*(n-1) = { fn(xn)}, (1.9)

Будем считать, что функция дохода fn(xn) монотонно возрастает, поэтому решением этой задачи является ус­ловное оптимальное управление xn*(n-1) при котором достигается условный максимум Zn*(n-1) =fn(xn*). Сле­довательно, предприятию Пп выделяются все оставшиеся средства (n-1) , которые приносят доход fn(n-1). Вернем­ся к предыдущему, (n-1)-му шагу, в начале которого имеется остаток средств n-2 . Уравнение (1.8) в этом случае примет вид

Здесь оптимальный выбор xn-1 не столь очевиден, как при решении предыдущей задачи (1.9). Прежде всего, выразив из уравнения состояния n-1 через n-2- xn-1, получим

Zn-1*(n-2) = {fn-1(xn-1)+ Zn*(n-2- xn-1)} .

Оба слагаемых в фигурных скобках — известные функ­ции, зависящие от управляющей переменной xn-1. Пара­метр n-2 является начальным состоянием для данной задачи. Выполнив исследование на максимум функции Zn-1(xn-1,n-2) = fn-1(xn-1)+ Zn*(n-2- xn-1) от одной переменной xn-1 получим условное оптимальное управ­ление xn-1*(n-2) и соответствующий условный максимум суммарного дохода Zn-1*(n-2). На языке данной зада­чи это решение означает, что если перед выделением средств предприятию Пn-1 в нашем распоряжении имеет­ся остаток n-2, то предприятию Пn-1 необходимо выде­лить xn-1*(n-2) средств. При этом сумма доходов от предприятий Пn и Пn-1 достигает максимума.

Закончив решение задачи (1.10), перейдем к следую­щему с конца (n-2)-му шагу, определим аналогичным образом условное оптимальное управление xn-2*(n-3) и соответствующий остатку n-3 условный максимум Zn-2*(n-3).

В результате, проходя последовательно все шаги с конца процесса распределения к его началу (т. е. к 1-му шагу), получим две последовательности функций:

Zn*(n-1), Zn-1*(n-2),…, Z2*(), Z1*(0)

(условные максимальные доходы) и

xn*(n-1), xn-1*(n-2),…, x2*(1), x1*(0)

(условные оптимальные управления).

Этим завершается первый и основной этап вычисли­тельного процесса, получивший название условной опти­мизации.

Теперь приступаем ко второму этапу вычислительной схемы — безусловной оптимизации. На этом этапе, преж­де всего, зная функцию Z1*(0), по заданному значению 0* определяем Zmax= Z1*(0*). Далее, обращаемся к последовательности xk*(k-1), которую проходим от на­чала к концу процесса. Выделяем x1*= x1*(0*) 1-му пред­приятию; тогда для распределения остается 1*= 0*- x1*. По этой величине определяем оптимальное количество средств х2* = х2*(1*), выделяемых 2-му предприятию. Снова находим 2*= 1*- x2*, после чего определяем х3*, и т. д., пока не будет определено искомое оптимальное управление (х1*, х2*,...,хn*).

Пример. Решим задачу о распределении средств при заданных конкретных условиях. Тем самым на числовом примере продемонстрируем общую вычислительную схему

Задача. Решить задачу 1 по следующим данным:

1) 0 = 200 млн. руб.; 2) п = 4; 3) средства выделяются только в размерах, кратных 40 млн. грн.; 4) функции дохода на каждом из четырех предприятий заданы в табл. 1:

Таблица 1.


f

x


f1(x)

f2(x)

f3(x)

f4(x)

40

80

120



160

200


8

10

11



12

18


6

9

11



13

15


3

4

7



11

18


4

6

8



13

16

Условие 3) определяет дискретность задачи, а нали­чие на каждом шаге только одной переменной управле­ния и одного параметра состояния показывают, что зада­ча является одномерной. Учитывая это условие, можно было бы принять за единицу масштаба 40 млн. грн. Вследствие этого 0 = 5 ед. и возможные значения для управляющих переменных были бы равны 0, 1, 2, 3 и 4. Однако мы сохраним реальные единицы, в которых ука­заны исходные данные.

В соответствии с обозначением § 3 имеем четыре управляющие переменные х1, х2, х3, х4 и пять параметров состояния 0, 1, 2, 3, 4 . Уравнениями состояния служат следующие равенства:

1= - x1, 2= 1- x2, 3= 2- x3, 4= 3- x4 . (1.11)

Уравнение Беллмана запишется в форме (1.8). Дан­ный процесс является четырехшаговым. При этом, так как на последнем шаге (при k=5) процесс завершается и прибыль на «последующих» шагах отсутствует, то и Z5*(4)=0. Запишем уравнение (1.8) для последнего шага:

Z4*(3) = { f4(x4)}, (1.12)

и для всех предыдущих (k = 3, 2, 1) шагов:

Zk*(k-1) = { fk(xk)+ Zk+1*(k)}

Выражение, стоящее в фигурных скобках последнего ра­венства, обозначим через

Zk(k-1,xk) = fk(xk)+ Zk+1*(k) (1.13)

где к = к-1к. тогда уравнение Беллмана для любого шага запишется в виде

Zk*(k-1) = {Zk(k-1,хк)}, (1.14)

Расчеты располагаем в двух таблицах – основной, в которой помещаем результаты условной оптимизации, т.е. последовательность функций Zk*(k-1) и xk*(k-1), и вспомагательной , в которой определяем Zk(k-1,хк) и выполняем условную оптимизацию. В основной таблице входом является параметр , для которого возможны значения 0,40,80,120,160 и 200 (см. табл.2)

Таблица 2.(основная)





4-й шаг

3-й шаг

2-й шаг

1-й шаг



Z4*(3)

x4*(3)

Z3*(2)

x3*(2)

Z2*(1)

x2*(1)

Z1*(0)

x1*(0)

40

80

120



160

200


4

6

8



13

16


40

80

120



160

200


4

7

9



13

18


0

40

40



0

200


6

10

13



16

19


40

40

80(40)



80

40


8

14

18



21

24


40

40

40



40

40


Условную оптимизацию начнем с расчета 4-го шага, для чего используем уравнение (1.12). Так как функция дохода f4(x4) монотонно возрастает (чем больше вкладывается средств, тем больше доход), то ее максимум достигается при наибольшем значении x4(3) = 3. При этом получим

Z4*(3) = f4(3), где 0  3  200. Этот результат условной оптимизации 4-го шага помещаем непосредствено во 2-й и 3-й столбцы таблицы 2, переписав необходимые данные из последнего столбца таблицы 1. Условная оптимизация 3,2, и 1-го шагов выполняется сначала в таблице 3. Расчет ведется по формулам (1.13) и (1.14) при k =3, k =2, k =1.


Так как условная оптимизация ведется на всех шагах по единообразным равенствам (1.13) и (1.14), то первые три столбца табл. 3 являются общими для всех трех шагов. Состояния в начале и в конце k-гo шага и управление на k-м шаге обозначены через k-1, k и xk. Поясним вначале порядок заполнения этих столбцов. Если k-1 = 40, то соответствующие управ­ления могут быть xk = 0 и xk = 40 (2-й столбец). Соответ­ствующие состояния в конце шага определяются по урав­нению состояния к = к-1к и принимают соответствен­но значения 40-0 = 40 и 40-40 = 0 (3-й столбец). Так последовательно заполняются три столбца для k-1 = 40; 80; 120; 160; 200.


Теперь перейдем к выполнению условий оптимизации на 3-м шаге. При этом используются формулы Z3(2, x3) = f3(x3) + Z4*(3) и Z3*(2) =Z3(2,х3), которые в 4, последовательно развернуты по строкам в 4,5 и 6-м столбцах. Если 2 = 40, х3 = 0 и 3 = 40 (1-я строка первых трех столбцов), то получим f3(xз) = f3(0) =0 (из табл. 1), Z4*(3)=Z4*(40)=4 (из табл. 2) и Z3(2,x3)=0 + 4 = 4. Эти числа заносятся в 1-ю строку 4, 5 и 6-го столбцов. Аналогично заполняются все остальные строки этих же столбцов.

Сравнив величины Z3(2,x3) при одном и том же зна­чении 2, выбираем наибольшее число, которое равно величине Z3*(2) . Соответствующие им условные оптимальные управления x3*(2) стоят в той же строке табл. 3 (во 2-м столбце). Выполнив условную оптимизацию 3-го шага, переносим в табл. 2 против соответствующих значений = 2 значения Z3*(2) и соответствующие им x3*(2).

Условная оптимизация 2-го шага выполняется по 7, 8 и 9-й строкам во всех столбцах табл. 3 аналогичным образом.

Приведем в качестве примера подробный расчет для 1 = 160 (четвертая секция табл. 3). При х2 = 0 и 2 = 1-x2=160 получим f2(x2)=f(0)=0, Z3*(2)=Z3*(160) = 13 (из табл. 2), поэтому Z2(1,x2)= =Z2(160, 0) = 13. При x2 = 40 и 2 = 12= 160— 40=120 получим f2(40)=6 (из табл. 1), Z3*(120)=9 (из табл. 2), откуда Z2(160, 40) = 6 + 9=15 и т. д. После заполнения четвертой секции в 9-м столбце получаем пять чисел: 13, 15, 16, 15 и 15, из которых наибольшее Z2*(160) = 16, а соответствующее,x2*(100) =80. Эти числа и занесены в основную таблицу, как результаты выполнения условной оптимизации 2-го шага при 1= 160.

Условную оптимизацию 1-го шага (10, 11 и 12-й столб­цы табл. 3) можно было бы выполнить лишь при задан­ном состоянии о = 200 (последняя секция табл. 3). Од­нако, имея в виду последующий анализ, мы приводим расчеты для всех возможных значений о (т. е. для 40, 80, 120, 160 и 200).

Перейдем ко второму этапу расчета — безусловной оптимизации. Из 1-го (последнего по порядку действий) шага условной оптимизации получаем Z1*(200)=24, т. е. максимальный доход, который может быть достигнут, равен 24. Здесь же получаем x1*(200) = x1* = 40, т. е. предприятию I следует выделить 40 млн. руб.

Дальнейшие (безусловные) оптимальные управления определяем из табл. 2 по следующей цепочке. При х1*= 40 из уравнения состояния получаем 1* = 200—40=160. В соответствующем (7-м) столбце табл. 2 получаем x2*(160)=80 = x2*. Вычисляем 2* = 160—80 = 80 (остаток средств перед выделением предприятию III). В 5-м столбце табл. 2 находим х3* = =x3*(80) =40. Тогда 3* = 2*—х3* = 80—40 = 40. Наконец, из 3-го столбца табл. 2 получаем x4* = x4*(40) =40.

Итак, максимальный доход, равный 24 млн. руб., бу­дет получен, если распределять средства между пред­приятиями следующим образом: предприятию I выде­лить x1* = 40 млн. руб., предприятию II — х2* = 80 млн. руб., предприятию III — x3* = 40 млн. руб., предприя­тию IV — х4* = 40 млн. руб.


ЛИТЕРАТУРА.



  1. Беллман Р. Динамическое программирование. М.:ИЛ, 1960

  2. Бёеллман Р. Процессы регулирования с адацптацией. М.:Наука,1964

  3. Беллёёёман Р., Дрейфус С. Прикладные задачи динамического прграммирования. М.:Наука, 1965.

  4. Хедли Дж. Нелинейное и динамическое программирование. М.:Мир, 1967

  5. Габасов Р., Кириллова Ф.М. Основы динамического программирования. Минск,

БГУ, 1975

  1. Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск, БГУ, 1975

  2. Исследование операций в экономике. Под редакцией Н.Ш.Кремера. М.: ЮНИТИ,

1997

8. Исследование операций в экономике.Под. ред. Кремера Н.Ш. М.:ЮНИТИ. 1997.



ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1.ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ






F1

F2

F3

F4

F5

F6

0

0

0

0

0

0

0

10

14

15

16

13

12

14

20

26

25

26

24

25

25

30

36

34

35

34

36

35

40

48

43

44

42

46

42

50

59

52

53

52

55

52

Варианты


№ варианта

Номера предприятий

№ варианта

Номера предприятий

№ варианта

Номера предприятий

№ варианта

Номера предприятий

1

1234

18

2564

35

4321

52

6543

2

1235

19

3214

36

5321

53

6542

3

1236

20

3215

37

6321

54

6541

4

1345

21

3216

38

5431

55

6531

5

1346

22

3241

39

6431

56

6532

6

1342

23

3245

40

2431

57

6534

7

1425

24

3246

41

5241

58

6521

8

1426

25

3251

42

6251

59

6523

9

1562

26

3254

43

2651

60

6524

10

1563

27

3256

44

3651

61

6512

11

1564

28

3261

45

4651

62

6513

12

2316

29

3264

46

1263

63

6514

13

2456

30

3265

47

1264

64

6451

14

2453

31

3451

48

1265

65

6452

15

2451

32

3452

49

1352

66

6453

16

2561

33

3456

50

1354

67

6431

17

2563

34

3465

51

1356

68

6432


2. ПОСТРОЕНИЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ ЗАДАЧИ О ЗАМЕНЕ [ 8]

Определить оптимальные сроки замены оборудования в течение N лет, при которых прибыль от эксплуатации оборудования максимальна, если известны: p - начальная стоимость оборудования; f(t) - стоимость производимой продукции на оборудовании возраста t лет; r(t) - ежегодные затраты на эксплуатацию оборудования возраста t лет; y(t) - ликвидная стоимость оборудования возраста t -лет.

f(t)=f1*exp(-a1*t)

r(t)=r1*exp(a2*t)



y(t)=y1*exp(-a3*t)

№ варианта

F1


A1

R1

A2

Y1

A3

P

1

40

0.1

10

0.05

15

0.1

20

2

40

0.1

15

0.1

20

0.15

25

3

50

0.1

15

0.1

20

0.15

25

4

50

0.2

15

0.1

20

0.15

25

5

50

0.1

10

0.05

15

0.1

20

6

55

0.2

15

0.1

15

0.1

20

7

40

0.1

16

0.06

16

0.15

20

8

45

0.1

17

0.06

17

0.16

25

9

46

0.2

17

0.05

16

0.15

25

10

44

0.1

16

0.04

17

0.2

27

11

47

0.2

14

0.05

16

0.17

26

12

45

0.1

15

0.04

15

0.13

24

13

43

0.1

16

0.05

18

0.14

25

14

46

0.1

17

0.1

14

0.1

26

15

50

0.2

14

0.12

15

12

25








izumzum.ru