Задача 4

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

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

Т а б л и ц а 4.

Объем капиталовложения S (млн. руб.)	Ожидаемая прибыль от i-го предприятия (млн. руб.)

Решение:

- построение математической модели задачи

Введем следующие обозначения:

- сумма капиталовложения, предоставляемая инвестором i–му производителю, [ ]=млн.руб.

- ожидаемая прибыль инвестора от i-го клиента в случае предоставления ему суммы вложения капитала, [ ] = млн. руб.

Распределение суммы капиталовложений между тремя предприятиями для получения наибольшей прибыли инвестора должно соответствовать следующим условиям:

,

= 0, 100, …, 500; i = 1, 2, 3

Z =

Задачу будем решать методом динамического программирования программирования.

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

Использование этого метода предполагает рассмотрение трех однопараметрических задач и в каждой задаче определяются условно-оптимальные решения , где S – сумма капиталовложения и S = 0, ..., 500. Отметим, что при решении этих задач должно выполняться следующее условие: при определении суммы капиталовложения очередному производителю рассматривается ожидаемая прибыль от этого клиента вместе с наибольшей суммарной прибылью, которую можно получить от ранее рассмотренных производителей при всевозможных вариантах выделения суммы капиталовложения последнему.

• Рассмотрим первую задачу: выделение суммы капиталовложения первому производителю.

Введем следующее обозначение:

- максимальная ожидаемая прибыль инвестора от первого производителя в случае предоставления ему S млн. руб.:

,

т.к. все функции монотонно возрастают. В этой задаче все значения функции при S = 0, …, 500 совпадают со значениями заданной функции . Условно-оптимальные решения совпадают с величиной S для каждого рассматриваемого значения S = 0, …, 500.

• Рассмотрим вторую задачу.

Пусть S млн. руб. распределяются инвестором между первым и вторым производителями. Тогда сумму S разделяем на две части: и ( ), где - сумма, выделенная второму производителю, а оставшаяся часть ( ) - первому производителю.

Тогда наибольшая ожидаемая прибыль инвестора от первого производителя составит величину , а от второго производителя - . Общая прибыль будет равна + .

Эта задача содержит только одну неизвестную величину - сумму капиталовложения второму производителю.

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

Пусть - наибольшая прибыль инвестора от двух первых производителей при распределении между ними S млн. руб. Значение определим, используя уравнение Беллмана:

Приведем таблицу с результатами расчетов второй задачи:

Т а б л и ц а 4.1

Объем кредита S	Сумма кредита второго клиента	Прибыль от первого клиента	Прибыль от первого клиента	Общая прибыль +	Максимальная прибыль
	100			58
	200			114
	300			160
	400			210
	400			250

В столбце показаны возможные значения . Так при S = 300 млн. руб. возможны четыре значения = 0, 100, 200, 300 при распределении 300 млн. руб. между вторым и первым производителями. В столбце записываются значения из исходной таблицы. Т.к. все значения функции при S = 0, …, 500 совпадают со значениями заданной функции , в столбце записываются значения из столбца исходной таблицы в обратном порядке. Затем складываются элементы столбцов , и выбирается максимальный элемент из + . Этот элемент подставляется в последний столбец. Значения , соответствующие максимумам и поэтому являющиеся условно-оптимальными решениями, подчеркиваются.

• Рассмотрим третью задачу, когда S распределяется между тремя производителями.

Пусть S млн. руб. распределяются инвестором между первым, вторым и третьим производителями. Тогда сумму S разделяем на две части: и ( ), где - сумма выделенная третьему производителю, а оставшаяся часть ( ) - первому и второму производителям.

Тогда наибольшая ожидаемая прибыль инвестора от первого и второго производителей составит величину , а от третьего производителя - . Общая прибыль будет равна + .

Эта задача содержит только одну неизвестную величину - сумму капиталовложения третьему производителю.

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

Пусть - наибольшая прибыль инвестора от трех производителей при распределении между ними S млн. руб. Значение определим, используя уравнение Беллмана:

В столбце таблицы 4.2 записываются значения из исходной таблицы.

Значения функции определяем из последнего столбца таблицы 4.1.

Приведем таблицу с результатами расчетов третьей задачи:

Т а б л и ц а 4.2

Объем кредита S	Сумма кредита третьего клиента	Прибыль от третьего клиента	Прибыль от первого и второго клиентов	Общая прибыль +	Максимальная прибыль
	100
	100 200
	200 300
	300
	300

Используя табличные данные, определим оптимальное решение и соответствующую максимальную прибыль Z.

Величина прибыли млн. руб. при млн.руб.

Остаток 500 – 300 = 200 млн.руб.должен быть распределен между первым и вторым производителями. В строке S = 200 таблицы 4.1 находим величину соответствующей максимальной прибыли. Тогда .

Таким образом, прибыль инвестора и распределение S млн. руб. между тремя производителями:

млн. руб.

Х = (0, 200, 300).