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

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

величина прибыли

,создаваемая i -й отраслью, в зависимости от объема вложений

Исходные данные удобно представить в виде таблице 5

Таблица 5 - Исходные данные для задачи вложения средств

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

следующим образом:

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

, где U_i – объем вложений в i -ю отрасль, а на компоненты вектора решений накладывается следующее ограничение:

Тогда множество вариантов решений имеет следующий вид:

Для применения метода динамического программирования необходимо определить основные компоненты: этап, состояние, управление, оператор перехода, локальный доход, условный оптимальный доход за i этапов.

этап – соответствует распределению средств для текущего количества отраслей. Номера этапов меняются от единицы до m: номер текущего этапа равен

и предполагает распределение средств между 1, 2, 3,..., i -й отраслями, а номер этапа, равный m, соответствует распределению средств между всеми m отраслями;

состояние – количество распределяемых средств v_j;

управление U_i – количество средств, которые распределены на i -м этапе для инвестирования в отрасль с номером i;

оператор перехода – для состояния v_j и выбранного управления U_i устанавливает количество оставшихся средств для вложения в 1, 2, 3,..., i– 1-ю отрасли, т.е.

;

локальный доход, полученный на i -м этапе, – это прибыль, достигнутая в i -й отрасли при вложении в нее средств в объеме U_i, т.е. q_i (U_i);

условный оптимальный доход W_i (v_j)за i этапов для состояния v_j – это доход, полученный от оптимального распределения имеющихся v_j средств между i отраслями.

Тогда уравнение Беллмана имеет следующий вид:

где

– условный оптимальный доход, полученный от вложения в первые по порядку i – 1 отраслей v_j – U_i средств.

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

Этап 1. На этом этапе принятия решений все средства вкладываются только в первую отрасль, т.е. i= 1,

Реализация первого этапа может быть представлена в виде таблицы 6.

Этап 2. Средства в объеме v_j распределяются между первой и второй отраслями, управление U ₂– это количество средств, которое распределено для вложения во вторую отрасль, v_j – U ₂ – количество оставшихся средств, направляемых для вложения в первую отрасль:

Тогда второму этапу будет соответствовать таблице 7.

Таблица 6 - Реализация первого этапа оптимального распределения средств

Первый столбец содержит перечень дискретных значений

, которые могут принимать объемы вложений в различные отрасли, во втором столбце для каждого из значений v_j указаны возможные варианты распределения средств между второй и первой отраслями, в третьем столбце приведены значения прибыли, получаемой от деятельности второй отрасли для приведенного варианта распределения, в четвертом столбце представлены значения

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

Определенную сложность представляет реализация процедуры формирования множества управлений. Предположим, что производится распределение средств в объеме v_j, т.е. система находится в состоянии v_j. Тогда управление U ₂ принимает следующие значения:

Этап 3. Производится распределение средств между тремя отраслями. Уравнение имеет следующий вид:

Управлением U ₃ является вложение средств в третью отрасль, а остаток средств, равный v_j – U ₃ направляется для инвестирования в первую и вторую отрасли. При решении уравнения учитывается, что значения

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

; второй столбец включает для каждого значения v_j допустимые значения вложения в третью отрасль U ₃:

; в третьем столбце указываются значения прибыли, получаемой от вложения средств в объеме U ₃, в третью отрасль –

; четвертый столбец содержит величины

суммарного дохода, получаемого при распределении v_j средств между первыми по порядку тремя отраслями, при условии, что в третью отрасль вложены средства в объеме U ₃; в последнем столбце фиксируются максимальные значения доходов для каждого из объемов вложений

На последнем этапе i=m производится оптимальное распределение средств

, между m отраслями. Управление U_m представляет собой вложение средств в последнюю m -ю отрасль, а остаток средств в объеме

направляется для вложения в первую, вторую,..., i -ю,..., m – 1-ю отрасли.

Функциональное уравнение Беллмана для i=m имеет следующий вид:

В результате решения функционального уравнения получается набор значений:

Ввиду того, что общее количество распределяемых средств равно v_n, то оптимальное вложение в m -ю отрасль определяется, как

. Тогда сравнительно просто вычисляется оптимальный объем вложений в первые m – 1 отраслей

. Из этого объема определяется оптимальная величина вложений в m – 1-ю отрасль:

. Аналогично находится объем вложений в первые по порядку m – 2 отрасли: он равен

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

Пример. Руководство корпорации решило провести реконструкцию четырех заводов. Общий объем инвестиций, равный 400 единиц, необходимо распределить между заводами так, чтобы добиться максимальной суммарной прибыли. Величина прибыли q_i (v_j), получаемой от инвестирования v_j средств в i -й завод корпорации, задается таблицей 8.

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

Этап 1. Все средства инвестируются в завод 1. Уравнение Беллмана имеет следующий вид: W ₁(v_j) = q ₁(v_j). Для уменьшения громоздкости используется строчное представление результатов, а так же шрифтовое выделение наилучших вложений средств для каждого из состояний. Тогда W ₁(0)=0; W ₁(100)=40; W ₁(200)=50; W ₁(300)=65; W ₁(400)=75.

Этап 2. Производится распределение финансовых ресурсов между первым и вторым заводами. Управление U ₂– это инвестирование средств во второй завод. Уравнение Беллмана имеет следующий вид: W ₂(v_j) = max (q ₂(U ₂) + W ₁(v_j – U ₂)), 0£ U ₂£ v_j;

W ₂(100) = max(q ₂(100) + W ₁(0); q ₂(0) + W ₁(100)) =max(40 + 0; 0 + 50) = 50;

W ₂(200) = max(q ₂(200) + W ₁(0); q ₂(100) + W ₁(100); q ₂(0) + W ₁(200)) =

W ₂(300) = max(q ₂(300) + W ₁(0); q ₂(200) + W ₁(100); q ₂(100) + W ₁(200); q ₂(0) + W ₁(300)) =

W ₂(400) = max(q ₂(400) + W ₁(0); q ₂(300) + W ₁(100); q ₂(200) + W ₁(200); q ₂(100) +

+ W ₁(300) q ₂(0) + W ₁(400)) =max(95 + 0; 85 + 40; 70 + 50; 50 + 65; 0 + 75) =

Этап 3. Производится распределение финансовых ресурсов между первым, вторым и третьим заводами.

Управление U ₃ – это инвестирование средств в третий завод. Уравнение Беллмана имеет следующий вид: W ₃(v_j) = max (q ₃(U ₃)+ W ₂(v_j – U ₃)), 0£ U ₃£ v_j;

W ₃(100) = max(q ₃(100) + W ₂(0); q ₃(0) + W ₂(100)) =max(30 + 0; 0 + 50) = 50;

W ₃(200) = max(q ₃(200) + W ₂(0); q ₃(100) + W ₂(100); q ₃(0) + W (200)) =

W ₃(300) = max(q ₃(300) + W ₂(0); q ₃(200) + W ₂(100); q ₃(100) + W ₂(200); q ₃(0) + W ₂(300))=

W ₃(400) = max(q ₃(400) + W ₂(0); q ₃(300) + W ₂(100); q ₃(200) + W ₂(200); q ₃(100) + W ₂(300);

Этап 4. Производится распределение финансовых ресурсов между всеми заводами. Управление U ₄ – это инвестирование средств в четвертый завод. Уравнение Беллмана имеет следующий вид: W ₄(v_j) = max (q ₄(U ₄)+ W ₃(v_j – U ₄)), 0£ U ₄£ v_j _;

W ₄(100) = max(q ₄(100) + W ₃(0); q ₄(0) + W ₃(100)) =max(0 + 50; 60 + 0) = 60;

W ₄(200) = max(q ₄(200) + W ₃(0); q ₄(100) + W ₃(100); q ₄(0) + W ₃(200)) =

W ₄(300) = max(q ₄(300) + W ₃(0); q ₄(200) + W ₃(100); q ₄(100) + W ₃(200); q ₄(0) + W ₃(300)) =

W ₄(400) = max(q ₄(400) + W ₃(0); q ₄(300) + W ₃(100); q ₄(200) + W ₃(200); q ₄(100) + W ₃(300);

Решение задачи в обратном порядке позволяет найти оптимальное распределение средств: завод 4 – 100; завод 3 – 100; завод 2 – 100; завод 1 – 100. Суммарная прибыль составляет 180 единиц.

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

Пусть требуется найти максимальное значение функции

Здесь

(i =

; j =

)— заданные постоянные числа (т<п и b_i>0).

Векторная форма данной задачи имеет следующий вид: найти максимум функции

то по определению опорного плана X = (

) является опорным планом данной задачи (последние п—т компонент вектора X равны нулю). Этот план определяется системой единичных векторов

, которые образуют базис m-мерного пространства. Поэтому каждый из векторов

,а также вектор

могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть

Положим

. Так как векторы Р₁, Р₂,..., Р_т - единичные, то

,а

Теорема 1. (признак оптимальности опорного плана). Опорный план Х *= (

) задачи (16 ) — (18) является оптимальным, если для любого j (

Теорема 2. Если <0 для некоторого j = k и среди чисел a_ik (

) нет положительных (

), то целевая функция (16) задачи (16) — (18) не ограничена на множестве ее планов.

Теорема 3. Если опорный план X задачи (16) —(18) не вырожден и , но среди чисел есть положительные (не все ), то существует опорный план такой, что F ()>F(X).

Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

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

В столбце

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

В столбце

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

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

В таблице 9 первые m строк определяются исходными данными задачи, а показатели (m+1) -й строки вычисляют. В этой строке в столбце вектора Р_о записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора Р_j — значение

Зн ачени е

находится как скалярное произведение вектора

(

) на вектор

Значение

равно скалярному произведению вектора

на вектор

После заполнения таблицы 9 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:

для j=m + 1, m + 2,..., п (при

). Поэтому в данном случае числа

для всех j от 1 до п;

для некоторог о j, и все соответствующие этому индексу величины

(i =

);

для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел

положительно.

В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов P_j имеющий индекс j, для которого

. Пусть, например,

и решено ввести в базис вектор P_k.

Для определения вектора, подлежащего исключению из базиса, находят min (

)для всех

. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор Р_r, а число а_rk называют разрешающим элементом.

Столбец и строку, на пересечении которых находится разрешающий элемент, называют направляющими.

После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения векторов

через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана—Гаусса. При этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам

а коэффициенты разложения векторов Р_j через векторы нового базиса, соответствующего новому опорному плану,— по формулам

После вычисления

согласно формулам (19) и (20) их значения заносят в таблицу 10. Элементы (m+1)-й строки этой таблицы могут быть вычислены либо по формулам (21) и (22), либо на основании их определения.

Наличие двух способов нахождения элементов (m + 1)-й строки позволяет осуществлять контроль правильности проводимых вычислений.

Из формулы (21) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис вектор

, имеющий индекс j, при котором максимальным по абсолютной величине является число (b_r/a_rj) ; ( <0, а_г_j>0), Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел . Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел c_j, определяемых данными числами ( <;0).

Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (19) — (22), так и по правилам, непосредственно вытекающим из них. Эти правила состоят в следующем.

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

Элементы векторов Р₀ и Р_j в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце С_б в строке вводимого вектора проставляют величину с_k, где k— индекс вводимого вектора.

Остальные элементы столбцов вектора Р₀ и P_j новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;

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

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

После заполнения новой симплекс-таблицы просматривают элементы (т+1) -й строки. Если все

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

Итак, нахождение оптимального плана симплексным методом включает следующие этапы:

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

4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка — минимальным из отношений компонент столбца вектора

к положительным компонентам направляющего столбца.

5. По формулам (19) — (22) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов

по векторам нового базиса и числа

. Все эти числа записываются в новой симплекс-таблице.

6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.