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

|500 |69 |69 |111 |127 | | | | | |

|600 |65 |65 |107 | | | | | | |

|700 |60 |60 | | | | | | | |

|Таблица 5. |

|[pic] |0 |100 |200 |300 |400 |500 |600 |700 |

|[pic] |0 |42 |72 |91 |107 |121 |134 |143 |

|[pic] |0 |0 |100 |200 |200 |300 |300 |300 |

Для заполнения таблицы 7 необходимо в таблице 6 сложить значения функции

[pic] со значениями [pic] и на каждой северо-восточной диагонали выбрать

наибольшее число (отмечено звездочкой), указав соответствующие значение

[pic]:

| |

|Таблица 6. |

| |[pic] |0 |100 |200 |300 |400 |500 |600 |700 |

|[pic|[pic] |0 |42 |72 |91 |107 |121 |134 |143 |

|] | | | | | | | | | |

| |[pic] | | | | | | | | |

|0 |0 |0 |42* |72* |91 |107 |121 |134 |143 |

|100 |22 |22 |64 |94* |113* |129* |143 |156 | |

|200 |37 |37 |79 |109 |128 |144* |158* | | |

|300 |49 |49 |91 |121 |140 |156 | | | |

|400 |59 |59 |101 |131 |150 | | | | |

|500 |68 |68 |110 |140 | | | | | |

|600 |76 |76 |118 | | | | | | |

|700 |82 |82 | | | | | | | |

|Таблица 7. |

|[pic] |0 |100 |200 |300 |400 |500 |600 |700 |

|[pic] |0 |42 |72 |94 |113 |129 |144 |158 |

|[pic] |0 |0 |0 |100 |100 |100 |200 |200 |

Теперь, в таблице 8, необходимо сложить значения функции [pic] со

значениями [pic], но только для значения [pic], т.е. заполнить только одну

диагональ:

|Таблица 8. |

| |[pic] |0 |100 |200 |300 |400 |500 |600 |700 |

|[pic|[pic] |0 |42 |72 |94 |113 |129 |144 |158 |

|] | | | | | | | | | |

| |[pic] | | | | | | | | |

|0 |0 | | | | | | | |158 |

|100 |50 | | | | | | |194 | |

|200 |68 | | | | | |197* | | |

|300 |82 | | | | |195 | | | |

|400 |92 | | | |186 | | | | |

|500 |100 | | |172 | | | | | |

|600 |107 | |149 | | | | | | |

|700 |112 |112 | | | | | | | |

Наибольшее число этой диагонали показывает максимально возможный

суммарный прирост прибыли всех четырех предприятий данного

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

700 денежных единиц, т.е.:

[pic] денежных единиц

причем четвертому предприятию должно быть выделено:

[pic] денежных единиц

Тогда третьему предприятию должно быть выделено (см. табл. 7.):

[pic] денежных единиц

второму предприятию должно быть выделено (см. табл. 5.):

[pic] денежных единиц

на долю первого предприятия остается:

[pic] денежных единиц

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

вложений по предприятиям:

[pic][pic][pic][pic]

которое обеспечивает производственному объединению наибольший возможный

прирост прибыли:

[pic] денежных единиц

6. Динамическая задача управления запасами

Задача управления запасами – это задача о поддержании баланса

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

предприятия на производство и хранение продукции.

Предположим, что предприятие, производящее партиями некоторую продукцию,

получило заказы на n месяцев. Размеры заказов значительно меняются от

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

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

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

Поэтому необходимо составить план производства на эти n месяцев с учетом

затрат на производство и хранение изделий.

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

|[pic] |Номер месяца (j=1,2,…,n) |

|[pic] |Число изделий, производимых в j-ом месяце |

|[pic] |Величина запаса к началу j-го месяца |

|[pic] |Число изделий, которые должны быть отгружены в j-ом |

| |месяце |

|[pic] |Затраты на хранение и производство изделий в j-ом |

| |месяце |

Тогда, задача состоит в том, чтобы найти план производства [pic]

компоненты которого удовлетворяют условиям материального баланса:

[pic], где [pic]

и минимизируют суммарные затраты за весь планируемый период:

[pic]

причем по смыслу задачи [pic], [pic], при [pic]

Т.к. объем произведенной продукции [pic] на этапе j может быть настолько

велик, что запас [pic] может удовлетворить спрос всех последующих этапов и

при этом не имеет смысла иметь величину запаса [pic] больше суммарного

спроса на всех последующих этапах, то переменная [pic] должна удовлетворять

ограничениям:

[pic]

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

чего необходимо определить параметр состояния [pic] и функцию состояния

[pic]:

|[pic]|Наличный запас продукции в конце k-го месяца ([pic]) |

|[pic]|Минимальные затраты за первые [pic] месяцев: [pic] |

Тогда, минимальные затраты за один первый месяц ([pic]):

[pic]

Следовательно, минимальные затраты при [pic]:

[pic], где [pic]

Если при этом функция затрат на хранение и производство изделий в j-ом

месяце имеет вид:

[pic], где

|[pic], при [pic] и [pic], при [pic] |

|[pic] |Затраты на оформление заказа (переналадку |

| |оборудования) в j-ом месяце |

|[pic] |Затраты на хранение единицы продукции, |

| |переходящей из j-го месяца в месяц j+1 |

|[pic] |Затраты на производство (закупку) [pic] единиц |

| |продукции в j-ом месяце |

то минимальные затраты за один первый месяц ([pic]):

[pic]

если ввести обозначение:

[pic]

то следовательно, минимальные затраты при [pic]:

[pic], где [pic]

Допустим, что предприятие заключило договора на поставку своей продукции

на три месяца. Исходные данные приведены в таблице 9. При этом исходный

запас товара на складе составляет две единицы, т.е [pic].

|Таблица 9. |

|Период k |1 |2 |3 |

|Спрос ([pic]) |3 |2 |3 |

|Затраты на оформление заказа |4 |2 |3 |

|([pic]) | | | |

|Затраты на хранение единицы запаса |1 |1 |1 |

|([pic]) | | | |

Предполагается, что затраты на приобретение продукции составляют 5 руб.

за каждую единицу для первых трех единиц и 7 руб. за каждую дополнительную

единицу, т.е.

[pic]

Положим [pic], тогда:

[pic]

Тогда, т.к. параметр состояния [pic] может принимать значения на отрезке:

[pic]

т.е. [pic], при этом каждому значению параметра состояния отвечает

определенная область изменения переменной [pic]:

[pic]

Однако на первом этапе объем производства не может быть меньше одной

единицы, т.к. спрос [pic], а исходный запас [pic], при этом из балансового

уравнения следует, что объем производства связан с параметром состояния

[pic] соотношением:

[pic]

т.е. каждому значению [pic] отвечает единственное значение [pic], поэтому:

[pic], тогда:

|[pic] |[pic] |[pic] |

Значения функции состояния [pic] приведены в таблице 10.:

|Таблица 10. |

|[pic] |0 |1 |2 |3 |4 |5 |

|[pic] |9 |15 |21 |29 |37 |45 |

|[pic] |1 |2 |3 |4 |5 |6 |

Положим [pic], тогда:

[pic], где:

[pic]

Здесь минимум берется по переменной [pic], которая может изменяться в

пределах:

[pic]

где верхняя граница зависит от параметра состояния [pic], который принимает

значения на отрезке:

[pic]

т.е. [pic], при этом из балансового уравнения следует, что остаток товара

на начало второго месяца [pic] связан с объемом производства [pic] и с

параметром состояния [pic] соотношением:

[pic]

Тогда:

|[pic] |[pic] |[pic] |[pic]* |

|([pic]) |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic]* |

Наименьшие из полученных значений [pic], есть [pic], т.е.:

[pic]

причем минимум достигается при [pic] и [pic], т.е.:

[pic] и [pic]

эти значения указываем в результирующей таблице 11.

Аналогично:

|[pic] |[pic] |[pic] |[pic] |

|([pic]) |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic]* |

|[pic] |[pic] |[pic] |[pic] |

|([pic]) |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic]* |

| |[pic] |[pic] |[pic] |

|[pic] |[pic] |[pic] |[pic] |

|([pic]) |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic]* |

| |[pic] |[pic] |[pic] |

Таким образом:

|Таблица 11. |

|[pic] |0 |1 |2 |3 |

|[pic] |21 |27 |34 |41 |

|[pic] |0 |2 |3 |3 |3 |

Теперь положим, что [pic], тогда:

[pic], где:

[pic]

Если оставлять продукцию к концу третьего периода не нужно, тогда

параметр состояния принимает единственное значение [pic], следовательно,

переменная [pic] может изменяться в пределах:

[pic]

а из балансового уравнения следует, что остаток товара на начало третьего

месяца [pic] связан с объемом производства соотношением:

[pic]

Тогда:

|[pic] |[pic] |[pic] |[pic] |

|([pic]) |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic] |

| |[pic] |[pic] |[pic]* |

Следовательно, получаем:

[pic]

причем минимум достигается при [pic], т.е.:

[pic]

Таким образом, получили минимальные общие затраты на производство и

хранение продукции и последнюю компоненту оптимального решения:

[pic]

Для нахождения остальных компонент оптимального решения, необходимо

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

Тогда т.к. [pic], то [pic], откуда [pic], следовательно, из таблицы 11.:

[pic] или [pic]

Аналогично т.к. [pic], то [pic] или [pic], откуда [pic] или [pic],

следовательно, из таблицы 10.:

[pic] или [pic]

Следовательно, получен оптимальный план производства, который имеет два

варианта:

|[pic] |[pic] |

при этом, каждый вариант оптимального плана производства обеспечивает

минимальные общие затраты на производство и хранение продукции в размере

39 денежных единиц.

7. Анализ доходности и риска финансовых операций

Финансовой называется операция, начальное и конечное состояние которой

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

дохода в виде разности между конечной и начальной оценками. При этом

практически все финансовые операции проходят в условиях неопределенности и,

следовательно, их результат невозможно предсказать заранее. Поэтому при

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

убытка.

Поэтому задача анализа доходности и риска финансовой операций заключается

в оценке финансовой операции с точки зрения ее доходности и риска. Наиболее

распространенным способом оценки финансовой операций является представление

дохода операции как случайной величины и оценка риска операции как среднего

квадратического отклонения этого случайного дохода.

Например, если доход от проведения некоторой финансовой операции есть

случайная величина [pic], то средний ожидаемый доход [pic]– это

математическое ожидание случайной величины [pic]:

[pic], где [pic] есть вероятность получить доход [pic]

Т.к. среднеквадратическое отклонение:

[pic], где [pic]

это мера разбросанности возможных значений дохода вокруг среднего

ожидаемого дохода, то его можно считать количественной мерой риска операции

и обозначить как [pic]:

[pic]

Допустим, что по четырем финансовым операциям [pic], [pic], [pic], [pic]

ряды распределения доходов и вероятностей получения этих доходов имеют вид:

|[pic]|2 |6 |8 |4 | |[pic]|2 |3 |4 |10 |

| |[pic]|[pic]|[pic]|[pic]| | |[pic]|[pic]|[pic]|[pic]|

| | | | | | | | | | | |

|[pic]|0 |1 |2 |8 | |[pic]|0 |4 |6 |10 |

| |[pic]|[pic]|[pic]|[pic]| | |[pic]|[pic]|[pic]|[pic]|

Тогда т.к. [pic], то средний ожидаемый доход каждой операции имеет вид:

[pic]

Т.к. [pic], то риски каждой финансовой операции имеют вид:

|[pic] |[pic] |

|[pic] | |

|[pic] |[pic] |

|[pic] | |

|[pic] |[pic] |

|[pic] | |

|[pic] |[pic] |

|[pic] | |

Нанесем средние ожидаемые доходы [pic] и риски [pic] каждой операции на

плоскость (см. график 2.).

Тогда, чем правее точка на графике, тем более доходная операция, чем

точка выше – тем более она рисковая.

Для определения операции оптимальной по Парето, необходимо на графике

найти точку, которую не доминирует никакая другая точка.

Так как точка [pic] доминирует точку [pic], если [pic] и [pic], то из

графика 2. видно, что 3-ая операция доминирует 2-ую операцию, а 1-ая

операция доминирует 3-ую и 2-ую операции. Но 1-ая и 4-ая операции

несравнимы, т.к. доходность 4-ой операции больше, но и риск ее тоже больше,

чем доходность и риск 1-ой операции, следовательно, 1-я операция является

оптимальной по Парето.

Для нахождения лучшей операции можно применить взвешивающую формулу,

которая для пар [pic] дает одно число, по которому можно определить лучшую

операцию. Допустим, что взвешивающей формулой будет [pic], тогда:

|[pic] |[pic] |

Отсюда видно, что 1-ая финансовая операция – лучшая, а 2-ая – худшая.

8. Оптимальный портфель ценных бумаг

Задача о формировании оптимального портфеля ценных бумаг – это задача о

распределении капитала, который участник рынка хочет потратить на покупку

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

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

Из характеристик ценных бумаг наиболее значимы две: эффективность и

рискованность. Т.к. эффективность [pic] – это некоторый обобщенный

показатель дохода или прибыли, то ее считают случайной величиной, а ее

математическое ожидание обозначают как [pic]. Рискованность ценных бумаг

отождествляют со средним квадратическим отклонением, при этом дисперсию

обычно называют вариацией и обозначают как [pic], т.е.:

[pic], где [pic]

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

|[pic|Номер вида ценных бумаг |

|] | |

|[pic|Доля капитала, потраченная на закупку ценных бумаг |

|] |i-го вида (сумма всех долей равна единице) |

|[pic|Эффективность ценных бумаг i-го вида, стоящих одну |

|] |денежную единицу |

|[pic|Математическое ожидание эффективности [pic] |

|] | |

|[pic|Ковариация ценных бумаг i-го и j-го видов |

|] | |

|[pic|Вариация (дисперсия) эффективности [pic] |

|] | |

|[pic|Рискованность ценных бумаг i-го вида |

|] | |

|[pic|Эффективность портфеля (набора) ценных бумаг |

|] | |

Тогда, математическое ожидание эффективности портфеля ценных бумаг:

[pic]

вариация портфеля ценных бумаг:

[pic]

риск портфеля ценных бумаг:

[pic]

Следовательно, математическая формализация задачи формирования

оптимального портфеля ценных бумаг:

Найти такое распределение долей капитала, которое минимизирует вариацию

эффективности портфеля, при заданной ожидаемой эффективности портфеля

[pic].

Тогда, если оптимальное решение обозначить как *, то:

|[pic] |означает рекомендацию вложить долю [pic] капитала в |

| |ценные бумаги i-го вида |

|[pic] |Означает возможность проведения операции “short sale”, |

| |т.е. краткосрочного вложения доли капитала в более |

| |доходные ценные бумаги |

Если на рынке есть безрисковые ценные бумаги, то решение задачи о

формировании портфеля ценных бумаг приобретает новое качество.

Пусть:

|[pi|Эффективность безрисковых ценных бумаг |

|c] | |

|[pi|Доля капитала, вложенного в безрисковые ценные бумаги|

|c] | |

|[pi|Средняя ожидаемая эффективность рисковой части |

|c] |портфеля |

|[pi|Вариация рисковой части портфеля |

|c] | |

|[pi|Среднее квадратическое отклонение эффективности |

|c] |рисковой части портфеля |

Тогда в рисковую часть портфеля вложена [pic] часть всего капитала, а

т.к. считается, что безрисковые ценные бумаги некоррелированы с остальными,

то ожидаемая эффективность всего портфеля ценных бумаг:

[pic]

вариация портфеля ценных бумаг:

[pic]

риск портфеля ценных бумаг:

[pic]

Допустим, что задача состоит в нахождении распределения капитала, при

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

состоящего из трех видов ценных бумаг: безрисковых эффективности 3 и

некоррелированных рисковых, с ожидаемой эффективностью 5 и 9, риски которых

равны 4 и 6, т.е.:

[pic], [pic], [pic], [pic], [pic]

Тогда, вариации некоррелированных рисковых ценных бумаг первого и второго

вида:

|[pic] |[pic] |

Следовательно, матрица [pic] ковариаций рисковых видов ценных бумаг и

вектор-столбец [pic]ожидаемой эффективности рисковых видов ценных бумаг

имеют вид:

|[pic] |[pic] |

Пусть [pic] - двухмерный вектор-столбец, компоненты которого равны 1,

т.е.:

[pic]

Тогда значение вектора-столбца [pic] оптимальных значений долей,

вложенных в рисковую часть портфеля ценных бумаг:

[pic]

Где:

[pic]

Т.е.:

[pic]

Таким образом, доли рисковых ценных бумаг в оптимальном портфеле:

[pic], [pic]

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

[pic]

Т.к. необходимость проведения операции “short sale” возникает, когда

[pic], то в данном случае, необходимость проведения операции “short sale”

возникает, когда [pic]:

[pic], т.е. когда [pic].

-----------------------

(

[pic]

(

110

[pic]

(

[pic]

График 2.

Страницы: 1, 2, 3

МЕНЮ

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

ИНТЕРЕСНОЕ