Задача распределения инвестиций между предприятиями

Глава 3. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Основные понятия и постановка задачи

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

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

Рассмотрим некоторый развивающийся экономический процесс, разделяющийся по времени из нескольких этапов (шагов). На каждом шаге выбираются параметры, влияющие на ход и исход операции, и принимается решение, от которого зависит выигрыш и на данном шаге по времени, например, в текущем году, и в операции в целом, например, за пятилетку. Этот выигрыш называется шаговым управлением.

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

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

Метод динамического программирования рассмотрим на отдельных примерах.

1. Задача управления производством. Планируется работа промышленного объединения, состоящего из предприятий, , на период времени из лет, . В начальный период на развитие объединения выделяются средства в размере . Их нужно распределить между предприятиями. В процессе работы выделенные средства частично расходуются. Каждое предприятие за год дает прибыль, зависящую от вложенных в него средств. В начале каждого года средства можно перераспределять. Нужно так распределить средства между предприятиями, чтобы суммарная прибыль объединения за период T летбыла максимальной.

Принятие решения разбивается на шагов, . Управление заключается в начальном распределении и последующих перераспределениях средств. Управление на каждом шаге t выражается вектором , где – объем средств, выделенных i-му предприятию в начале года t. Управление процессом в целом состоит из совокупности шаговых управлений .

Пусть – материальное и финансовое состояние системы на начало t-го года, . Состояние каждого предприятия также является вектором. Его компонентами являются трудовые ресурсы, основные фонды, финансовое положение и т.д. То есть , где – число компонент вектора. Вектор управления – это функция состояния системы предприятий на начало соответствующего финансового года . Начальное состояние системы задается.

Целевая функция – суммарная прибыль объединения за лет. Пусть – прибыль объединения за год . Тогда целевая функция . На состояние системы и вектор управления в каждом году могут быть наложены ограничения. Пусть – множество этих ограничений, которое называется множеством допустимых управлений или множеством экономических возможностей. Возможные управления должны принадлежать ей . Таким образом, окончательно задача имеет вид .

2. Задача о ремонте и замене оборудования. Владелец автомашины эксплуатирует её в течение m лет. В начале каждого года он может принять одно из трёх решений: 1) продать машину и заменить её новой; 2) отремонтировать и продолжать эксплуатацию; 3) продолжить эксплуатацию без ремонта.

Пошаговое управление – выбор одного из трех решений. Его нельзя выразить числами, но можно приписать первому значение 1, второму – 2, третьему – 3. Как чередовать управления 1, 2, 3 по годам, чтобы суммарные расходы на ремонт, эксплуатацию, покупку новой машины были минимальными: .

Управление операций представляет собой какую-то комбинацию чисел, например: . Любое управление – это вектор такого вида, содержащий m компонент, каждый из которых принимает одно из трех значений 1, 2, 3.

Особенности задач динамического программирования.

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

2. Решение, принимаемое на конкретном шаге, не зависит от «предыстории»: от того, каким образом оптимизируемый процесс достиг настоящего состояния. Оптимальное решение выбирается с учетом факторов, характеризующих процесс в данный момент;

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

Общая постановка задачи динамического программирования. Рассмотрим некоторую развивающуюся во времени систему управления, на которую можно влиять принимаемыми решениями. Пусть эта система распадается на T шагов (этапов). Ее состояние на начало каждого шага описывается вектором . Множество всех состояний, в которых может находиться система на начало t-го шага, обозначим через . Начальное состояние системы считается известным, то есть при задан вектор .

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

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

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

Функциональные уравнения динамического программирова­ния называются функциональными уравнениями Беллмана.

Математическая формулировка принципа оптимальности с адди­тивным критерием. Пусть заданы начальное и конечное состояние системы . Введем обозначения: – значение функции цели на первом этапе при началь­ном состоянии системы X₀ и при управлении , – значение функции цели на втором шаге при со­стоянии системы и при управлении . Соответственно далее – значение функции цели на -ом этапе, . Очевидно, что

.

Требуется найти оптимальное управление , такое что

(69)

при ограничениях

. (70)

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

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

, . (71)

Обозначим соответственно оптимальные значения функции цели на двух последних, трех последних этапах и т.д., на Т этапах. В силу этих обозначений имеем:

(72)

(73)

. . . . . . . . . . . . . . .

(74)

. . . . . . . . . . . . . . .

(75)

Выражения (71) – (75) называются функциональными уравнениями Беллмана. Эти уравнения имеют рекуррентный характер, так как для нахождения оптимального уравнения на T шагах нужно знать условно оптимальное управление на последующих T–1 шагах и т.д. Поэтому функциональные уравнения также называют рекуррентными соотношениями Беллмана.

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

Запишем функциональное уравнение последнего этапа

.

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

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

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

Задача выбора кратчайшего пути. Задана транспортная железнодорожная сеть (рис.11), на которой указан пункт отправления A и пункт назначения B. Между ними имеется много других пунктов. Некоторые соединены между собой железнодорожным полотном. Над каждым участком железнодорожной сети проставлены цифры, указывающие расстояние между двумя соседними пунктами. Требуется составить маршрут из пункта A в пункт B минимальной длины.

Разобьем все расстояние между A и B на этапы (рис.11). Оценим отрезки, на которые делят линии (2-2) и (3-3) участки сети.

Рис. 11

Выбор кратчайшего пути начнем с конца. Найдем кратчайшие пути, соединяющие конечный пункт B с каждой точкой пересечения линии (2-2) с транспортной сетью. Таких точек пересечения три: D₁, D₂, D₃. Для точки D₁ min(10;8+4;8+3+5)=10; для точки D₂ min(5+4;5+3+5)=9; для точки D₃ min(2.5+3+4; 2.5+5)=7.5.

На рисунке кратчайшие расстояния от точек D₁,D₂ и D₃ до конечного пункта B показаны в скобках. Далее рассматриваем точки пересечения линии (3-3) с участком сети. Эти точки C₁, C₂, C₃. Находим кратчайшие расстояния от этих точек до пункта B. Они показаны в скобках у точек C₁(19), C₂(14), C₃(12). Наконец находим минимальную длину пути, ведущего из A в B. Это расстояние равно 23. Затем находим этапы в обратном порядке. Находим кратчайший путь: .

Ключевые слова: динамическое программирование, многоэтапный процесс, управление, управляемый процесс, стратегия, оптимальная стратегия, принцип оптимальности, условно оптимальное управление, функциональные уравнения Беллмана.

Вопросы для самопроверки

1. Что является предметом динамического программирования?

2. В чем отличие динамического программирования от линейного программирования?

3. Каковы основные свойства динамического программирования?

4. В чем заключается принцип оптимальности динамического программирования?

5. Какова модель задачи планирования работы промышленного объединения?

6. Какова формулировка общей задачи динамического программирования?

7. Что выражают функциональные уравнения Беллмана?

8. В чем заключается идея решения задачи динамического программирования?

Задачи для самостоятельного решения

Пример 1. Сформулировать приведенные задачи в терминах динамического программирования.

А) Производственное объединение состоит из т предприятий. В начале каждого года между ними полностью распределяется централизованный фонд развития производства. Выделение i-му предприятию из этого фонда тыс.руб. обеспечивает получение дополнительной прибыли, равной тыс. руб. К началу планового периода из T лет централизованному фонду развития производства выделено тыс.руб. В каждый последующий год этот фонд формируется за счет отчислений от полученной прибыли. Эти отчисления для i-го предприятия составили тыс.руб. Найти такой вариант распределения централизованного фонда развития производства, чтобы получить за T лет максимальную общую прибыль.

Б) В состав производственного объединения входят два предприятия, связанные между собой кооперированными поставками. Вкладывая дополнительные средства в их развитие, можно улучшить технико-экономические показатели деятельности производственного объединения в целом, обеспечив получение дополнительной прибыли. Ее величина зависит от величины средств, выделяемых каждому предприятию, и использованию этих средств. Считая, что на развитие i-го предприятия в начале k-го года выделяется тыс.руб., найти такой вариант распределения средств между предприятиями в течении T лет, чтобы за данный период времени будет получить максимальную прибыль.

Пример 2. Требуется перевезти груз из пункта A в пункт B.

Рис. 12

На рис.12 показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами сети (проставлены у соответствующих ребер). Определить маршрут доставки груза из пункта A в пункт B, которому соответствуют наименьшие затраты.

Пример 3. На данной сети дорог имеется несколько маршрутов по доставке груза из пункта A в пункт B (рис.13). Стоимость перевозки единицы груза между отдельными пунктами сети проставлена у соответствующих ребер. Определить оптимальный маршрут доставки груза из пункта A в пункт B, по которому общие затраты будут минимальными.

Рис. 13

Задача распределения инвестиций между предприятиями

На реконструкцию и модернизацию основного производства объединению выделяются материальные ресурсы в объеме . Эти ресурсы нужно распределить между n предприятиями объединения.

Пусть – прибыль, получаемая, если i-му предприятию выделено единиц ресурса. Общая прибыль объединения складывается из прибылей отдельных предприятий

Математическая модель распределения инвестиций имеет вид

, (76)

, (77)

, (78)

Требуется добиться максимума целевой функции (76) при условиях полного распределения инвестиций объема между предприятиями (77) и неотрицательности переменных (78).

Решение задачи представим в виде многоэтапного процесса. Вместо решения одной задачи с заданным объемом инвестиций и фиксированным числом предприятий n рассмотрим семейства задач, в которых объем выделяемого ресурса может меняться от 0 до , а число предприятий – от 1 до n. Например, предполагается, что на первом этапе инвестиция в объеме выделяется только одному предприятию, на втором этапе – двум предприятиями и т.д., на n-ом этапе – предприятиям.

Введем последовательность функций , где – максимальное значение прибыли, получаемой, когда ресурс x распределен только одному предприятию; – максимальное значение прибыли, получаемой при условии, что объем ресурса распределен между двумя предприятиями и т.д.; – максимальное значение прибыли, получаемой при условии, что ресурс распределен между n предприятиями. Очевидно, что .

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

Пусть инвестиция объема x , , распределяется между двумя предприятиями. Если – объем инвестиций, выделенный второму предприятию, то его прибыль составит

.

Допустим, что инвестиция объема x распределяется между k предприятиями. Если – объем инвестиций, выделенный k-му предприятию, то оставшееся количество ресурса распределяется между оставшимися k–1 предприятиями наилучшим образом. Так как известно, то

. (79)

Полученное рекуррентное соотношение (79) и есть функциональное уравнение Беллмана.

Решение исходной задачи получим при из соотношения (79):

.

Рассмотрим вычислительную схему решения задачи распределения инвестиций методом динамического программирования.

Промежуток разбивают, например, на N интервалов с шагом и считают, что функции определены для значений . При i=1 функция определяется равенством . Множество значений , записывают в таблицу. Зная значения , переходят к вычислению значений функции :

.

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

,

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

Затем процесс вычислений просматривается в обратном порядке. Зная , находят – объем инвестиций, подлежащий распределению между оставшимися n–1 предприятиями.

Прежде всего, используя соотношение

находят значения и и т.д. Продолжая таким образом, в конце процесса находится значение .

Пример 1. Между четырьмя предприятиями следует распределить 200 единиц ограниченного ресурса. Значения, получаемой предприятиями прибыли в зависимости от выделенной суммы , приведены в табл.57 , составленной с «шагом» единиц ресурса. Составить план распределения ресурса, дающий наибольшую суммарную прибыль.

Таблица 57

Выделяемый объем инвестиций	Величина прибыли предприятия

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

Таблица 58

При инвестиция распределяется между двумя предприятиями. В этом случае общая прибыль вычисляется с помощью следующего функционального уравнения

. (80)

Для каждого значения находят значения , суммы и определяют максимум (80). Например,

• пусть , тогда ;
• пусть , тогда возможны случаи :

· пусть , то :

· пусть , то :

· пусть то :

· пусть , то :

Результат вычисления запишем в табл.59.

Таблица 59

	0+15	14+0
	0+28	14+15	30+0
	0+60	14+28	30+15	55+0
	0+75	14+60	30+28	55+15	73+0
	0+90	14+75	30+60	55+28	73+15	85+0

На 3-ем этапе инвестиция в объеме единиц распределяется между тремя предприятиями. В этом случае общая прибыль объединения определяется с помощью функционального уравнения

.

Результаты вычислений представим в табл.60.

Таблица 60

	0+15	17+0
	0+30	17+15	33+0
	0+60	17+30	33+15	58+0
	0+75	17+60	33+30	58+15	73+0
	0+90	17+75	33+60	58+30	73+15	92+0

На 4-м этапе инвестиция распределяется между четырьмя предприятиями и общая прибыль при этом распределяется с помощью функционального уравнения

Результаты вычислений сведем в табл.61.

Таблица 61

	0+17	13+0
	0+33	13+17	35+0
	0+60	13+33	35+17	57+0
	0+77	13+60	35+33	57+17	76+0
	0+93	13+77	35+60	57+33	76+17	86+0

Результаты всех предыдущих вычислений (табл.58-61) представим в виде сводной таблицы (табл.62).

Таблица 62

Табл.62 дает оптимальный план распределения инвестиций. Максимальное значение функции цели при распределении 200 единиц ресурса четырем предприятиям составляет max(90;90;93;95)=95, т.е. . Четвертому предприятию нужно выделить 80 единиц инвестиций, а остальным трем единиц.

Из этой же таблицы находим, что оптимальное распределение инвестиций в 120 единиц между тремя предприятиями доставляет объединению 60 единиц прибыли. При этом третьему предприятию не следует выделять инвестиций: . Следовательно, остаток 120 единиц инвестиций нужно распределить между оставшимися двумя предприятиями. Оптимальное распределение приносит 60 единиц прибыли, причем . Значит . Итак, оптимальный план распределения инвестиций

.

Вычисления можно значительно упростить, если воспользоваться табл.63:

Таблица 63

Например, вычислим – максимальное значение суммы . В колонке двигаемся от числа 58 вверх, а в колонке от числа 0 вниз. При этом образуются суммы:

,

наибольшая из сумм равна 60. Следовательно, .

Согласно табл.63, наибольшая прибыль, которую могут дать предприятия, составляет 95 единиц:

;

;

;

т.е. .

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

Вопросы для самопроверки

1. Каков вид математической модели задачи распределения ресурсов?

2. Как статическую задачу распределения инвестиций можно преобразовать в многоэтапную динамическую задачу?

3. Запишите функциональное уравнение, определяющее максимальную прибыль для каждого i-этапа?

Задачи для самостоятельного решения

Пример 1. Между четырьмя предприятиями нужно распределить 120 единиц ограниченного ресурса. Величина получаемой предприятиями прибыли зависит от выделенной суммы и приведена в табл.64, составленной с шагом . Найти оптимальный план распределения

Таблица 64

Выделенный объем ресурса, x	Величина прибыли на предприятиях
Z1(x)	Z2(x)	Z3(x)	Z4(x)

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

Таблица 65

Выделенный объем инвестиций, x	Величина прибыли на предприятиях

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

Таблица 66

Выделенный объем капиталовложений, x	Величина прибыли на предприятиях