Общая схема применения метода ДП. Задача об оптимальном распределении ресурсов между отраслями на n лет

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

Предположим, что все требования, предъявляемые к задаче методом ДП, выполнены (требования сформулированы в параграфе 11.1). Построение модели ДП и применение метода ДП для решения сводится к следующим моментам.

  • 1. Выбирают способ деления процесса управления на шаги.
  • 2. Определяют параметры состояния sk и переменные управления Хк на каждом шаге.
  • 3. Записывают уравнения состояний.
  • 4. Вводят целевые функции ⅛-го шага и суммарную целевую функцию.
  • 5. Вводят в рассмотрение условные максимумы (минимумы) Zl (⅞_[) и условное оптимальное управление на ⅛-м шаге: = n, п-1,...,2,1.
  • 6. Записывают основные для вычислительной схемы ДП уравнения Веллмана для Z'(sn_,) и Z'k (⅝_,), ⅛= η-1,..., 1.
  • 7. Решают последовательно уравнения Веллмана (условная оптимизация) и получают две последовательности функций:

  • 8. После выполнения условной оптимизации получают оптимальное решение для конкретного начального состояния s0:
    • а) ;
    • б) по цепочке

оптимальное управление:

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

11.2. Планируется деятельность двух отраслей производства на п лет. Начальные ресурсы л0. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль /↑ (х) и возвращаются в размере q{ (х) < х; аналогично для II отрасли функция прибыли равна /2 (.г), а возврата – q2 (х) {q2 (а:) < х). В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается[1].

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

Необходимо:

  • а) построить модель ДП для задачи и вычислительную схему;
  • б) решить задачу приусловии, что

Кешенис. а} процесс распределения средств между двумя отраслями производства разворачивается во времени, решения принимаются в начале каждого года, следовательно, осуществляется деление на шаги: номер шага – номер года. Управляемая система – две отрасли производства, а управление состоит в выделении средств каждой отрасли в очередном году. Параметры состояния к началу &-го года – sk ↑ (k = 1, 2,..., и) количество средств, подлежащих распределению. Переменных управления на каждом шаге две: хк количество средств, выделенных I отрасли, и ук- II отрасли. Но так как все средства sA , распределяются, то У к =sk-1 ~хк > и поэтому управление на ⅛-м шаге зависит от одной переменной хп, т.е.

Уравнения состояний

(11.13)

выражают остаток средств, возвращенных в конце k-ro года.

Показатель эффективности k-ro шага – прибыль, полученная в конце ⅛-ro года от обеих отраслей:

(11.14)

Суммарный показатель эффективности – целевая функция задачи – прибыль за η лет:

(11.15)

Пусть– условная оптимальная прибыль за

η – к +1 лет, начиная с k-ro года до "-го года включительно при условии, что имеющиеся на начало к-то года средства sk j в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за η лет

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

(11.16)

(11.17)

б) Используем конкретные данные.

Уравнение состояний (11.13) примет вид

(11.18)

Целевая функция ⅛-го шага (11.14)

Целевая функция задачи

(11.19)

Функциональные уравнения

(11.20)

(11.21)

Проводим условную оптимизацию.

Рис. 11.5

IV шаг. Используем уравнение (11.20). Обозначим через Z4 функцию, стоящую в скобках, Z4 = = 0,1;с4 + 0,5s3 ; функция Z4 – линейная, возрастающая, так как угловой коэффициент 0,1 больше нуля. Поэтому максимум достигается на конце интервала(рис. 11.5).

Следовательно,при

III шаг. Уравнение

Найдем s3 из уравнений состояний (11.18): s3 =0,8s2- –О,l.r:5 и, подставив его выражение в правую часть уравнения, получим

Как и в предыдущем случае, максимум достигается при , т.е.при

II шаг. Из уравнения состояния: . Поэтому уравнение (11.20) при k = 2 примет вид

Линейная относительно х2 функция Z2 = 1,316л'! -0,002х2 убывает на отрезке [О; .у, ] и поэтому ее максимум достигается при х2 = 0 (рис. 11.6):

I шаг.. Уравнение (11.20) при k = 1 имеет вид

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

На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получим:,

или,

Рис. 11.6

(все средства выделяются II отрасли) →

(все средства выделяются II отрасли) →

(все средства выделяются I отрасли) –>

(все средства выделяются I отрасли).

Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 10000 ед., равна 15528 ед. при условии, что I отрасль получает по годам (0; 0; 6400; 4480), а II отрасль – соответственно (10000; 8000; 0; 0). ►

  • [1] Последние условия определяют вид уравнений состояний; если поступают новые средства или часть прибыли вкладывается в производство, это можно легко учесть, так как алгоритм метода ДП не изменяется.
 
< Пред   СОДЕРЖАНИЕ     След >