Прикладная математика
x2
причем минимум достигается при значении х2, равном
2
(
= y3 = 2) = 3
Аналогично для значения параметра = у3 = 3, проведя необходимые вычисления, найдем
F2
(
= y3 = 3) =
63;
2
(
= y3 = 3) = 3.
Процесс табулирования функции F2 ( = y3) приведен в табл. 2, а результаты табулирования сведены в табл. 3.
Таблица 3
-
= у3
0 1 2 3 4 F2 (= y3)
24 36 49 63 78
(=
y3)2 2 3 3 4
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 ( = y4):

Вычисляем значение функции состояния только для одного значения аргумента = у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем
F3 ( = y4) = min 3 (x3,0) = min (80, 71, 65, 62, 62) = 62,
x3
причем минимум достигается при двух значениях переменной х3, равных
3
(
= y4 = 0) = 3
или
3
(
= y4 = 0) = 4.
Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна
=
3 или
=
4.
Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции
=
3.
Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что
х3 + у3 - d3 = y4
или
3 + у3 - 4 = 0,
откуда
у3 = 1.
Из таблицы
(3) значений
находим
Аналогично, продолжая двигаться в обратном направлении и учтя, что
х2 + у2 - d2 = y3
|
K=2 Таблица 2 30
|
|
|
xk |
yk = yk+1 + dk - xk |
k(xk, yk+1) =k(xk) + hkyk+1 + Fk-1(yk) |
|
0 y3 d3 |
= y3 |
0 x2 d2 + y3 |
x2 |
y2 = y3 + d2 - x2 |
2(x2,
y3) = a |
|
0 y3 4 |
= y3 |
0 x2 2 + y3 |
x2 |
y2 = y3 + 3 - x2 |
|
|
y3 = 0 |
0 x2 2 |
x2 = 0 x2 = 1 x2 = 2 |
y2 = 2-0 = 2 y2 = 2- 1 = 1 y2 = 2-2 = 0 |
2(0;0) = 02 + 50 + 2 + 30 + F1(2) =2+28 =30 2(1;0) = 12 + 51 + 2 +30 + F1(1)=8+17 =25 2(2;0) = 22 +52 + 2 + 30 +F1(0) =16+8=24* |
|
|
y3 = 1 |
0 x2 3 |
x2 = 0 x2 = 1 x2 = 2 x2 = 3 |
y2 = 3 - 0 = 3 y2 = 3-1 = 2 y2 = 3-2 = 1 y2 = 3-3 = 0 |
2(0;1) = 02 + 50 + 2 + 31 + F1(3) = 5+41=46 2(1;1) = 12 + 51 + 2 + 31 + F1(2) =11+28 =39 2(2;1) = 22 + 52 + 2 + 31 + F1(1)=19+17 =36* 2(3;1) = 32 + 53 + 2 + 31 + F1(0)=29+8 =37 |
|
|
y3 = 2 |
....................... | ........ | ............................ | ............................................................. | |
|
y3 = 3 |
0 x2 5 |
x2 = 0 x2 = 1 x2 = 2 x2 = 3 x2 = 4 x2 = 5 |
y2 = 5 - 0 = 5 y2 = 5 - 1 = 4 y2 = 5 - 2 = 3 y2 = 5 - 3 = 2 y2 = 5 - 4 = 1 y2 = 5 - 5 = 0 |
2(0;3) = 02 + 50 + 2 + 33 + F1(5) = 11+73=84 2(1;3) = 12 + 51 + 2 + 33 + F1(4) =17+56 =73 2(2;3) = 22 + 52 + 2 + 33 + F1(3)=25+41 =66 2(3;3) = 32 + 53 + 2 + 33 + F1(2)=35+28 =63* 2(4;3) = 42 + 54 + 2 + 33 + F1(1)=47+17 =64 2(5;3) = 52 + 55 + 2 + 33 + F1(0)=61+8 =69 |
|
|
y3 = 4 |
0 x2 6 |
x2 = 0 x2 = 1 x2 = 2 x2 = 3 x2 = 4 x2 = 5 x2 = 6 |
y2 = 6 - 0 = 6 y2 = 6 - 1 = 5 y2 = 6 - 2 = 4 y2 = 6 - 3 = 3 y2 = 6 - 4 = 2 y2 = 6 - 5 = 1 y2 = 6 - 6 = 0 |
2(0;4) = 02 + 50 + 2 + 34 + F1(6) = 14+92=106 2(1;4) = 12 + 51 + 2 + 34 + F1(5) =20+73 =93 2(2;4) = 22 + 52 + 2 + 34 + F1(4)=28+56 =84 2(3;4) = 32 + 53 + 2 + 34 + F1(3)=38+41 =79 2(4;4) = 42 + 54 + 2 + 34 + F1(2)=50+28 =78* 2(5;4) = 52 + 55 + 2 + 34 + F1(1)=64+17 =81 2(6;4) = 62 + 56 + 2 + 34 + F1(0)=80+8 =88 |
Таблица 4
31
|
K=3
|
|
|
xk |
yk = yk+1 + dk - xk |
k(xk, yk+1) = k(xk) + hkyk+1 + Fk-1(yk) |
|
0 y4 0 |
= y4 |
0 x3 d3 + y4 |
x3 |
y3 = y4 + d3 - x3 |
3(x3,
y4) = a |
|
y4 = 0 |
= y4 |
0 x3 4 |
x3 |
y3 = y4 + 4 - x3 |
|
|
y4 = 0 |
0 x3 4 |
x3 = 0 x3 = 1 x3 = 2 x3 = 3 x3 = 4 |
y3 = 4-0 = 4 y3 = 4- 1 = 3 y3 = 4-2 = 2 y3 = 4-3 = 1 y3 = 4-4 = 0 |
3(0;0) = 02 + 50 + 2 + 20 + F2(4)=2+78=80 3(1;0) = 12 + 51 + 2 + 20 + F2(3)=8+63=71 3(2;0) = 22 + 52 + 2 + 20 + F2(2)=16+49=65 3(3;0) = 32 + 53 + 2 + 20 + F2(1)=26+36=62* 3(4;0) = 42 + 54 + 2 + 20 + F2(0)=38+24=62* |
Самопроверка результатов Таблица 5
| Этапы | январь | февраль | март | Итого за 3 месяца |
| Имеем продукции к началу месяца, шт. |
у1 = 2 |
у2 = 1 |
у3 = 1 |
у1 = 2 |
| Производим в течение месяца, шт. |
х1 = 2 |
х2 = 2 |
х3 = 3 |
х1+ х2+ х3 = 7 |
| Отпускаем заказчикам, шт. |
d1 = 3 |
d2 = 2 |
d3 = 4 |
d1+ d2+ d3 = 9 |
|
Остаток к концу месяца (храним в течение текущего месяца), шт. |
у2 = 1 |
у3 = 1 |
у4 = 0 |
|
| Затраты на производство, руб. |
(х1)=16 |
(х2)=16 |
(х3)=26 |
(х1) + (х2) + (х3) = 58 |
| Затраты на хранение, руб. |
h1у2 = 1 |
h2у3 = 3 |
0 |
h1у2 + h2у3 = 4 |
и
32
ли2 + у2 - 2 = 1,
получаем
у2 = 1;
из таблицы (2) значений х1() находим
.
Итак, оптимальный план производства имеет вид
х1 = 2
х2 = 3
х3 = 3,
а минимальные общие затраты составляют 62 единицы.
Полезна самопроверка полученного результата. Для этого по исходным данным и найденному плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом этапе выполняются
у1 + х1 d1 у2 + х2 d2 у3 + х3 d3
2 + 2 3 1 + 2 2 1 + 3 4
и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности
у1 + х1 + х2 + х3 = d1 + d2 + d3
2 + 2 + 2 + 3 = 3 + 2 + 4
причем это достигается при наименьших возможных затратах на производство и хранение продукции
(х1) + (х2) + (х3) + h1у2 + h2у3 = F3(y4=0)
16 + 16 + 26 + 1 + 4 = 62
Студенту рекомендуется найти другой вариант оптимальной производственной программы, когда на последнем этапе предполагается произвести 4 единицы продукции, и так же выполнить самопроверку.
§10. Матричная модель производственной
программы предприятия
Предприятие состоит из n цехов. Каждый цех выпускает только один вид продукции. Пусть j-й цех выпускает xj единиц продукции, из которых yj единиц отправляет за пределы предприятия как товарную продукцию, а остающаяся часть используется другими цехами предприятия.
Пусть ajk – кол-во продукции j-го цеха, расходуемое на производство единицы продукции k-го цеха. Числа aij образуют матрицу А коэффициентов прямых затрат, называемую структурной. Производственная программа предприятия представляется вектором X(x1, … , xn), а выпуск товарной продукции – вектором У(у1, … , уn). Очевидно,
(Е - А)Х = У или Х = (Е - А)-1У.
Элементы любого столбца матрицы (Е - А)-1, называемой матрицей коэффициентов полных затрат, показывают затраты всех цехов, необходимые для обеспечения выпуска единицы товарного продукта того цеха, номер которого совпадает с номером данного столбца.
При заданном векторе У выпуска товарной продукции легко определить производственную программу Х и наоборот.
Д
33
ополним структурную матрицу А матрицей В коэффициентов прямых затрат, получаемых со стороны сырья, полуфабрикатов и т.п. Очевидно, затраты получаемых со стороны материалов определяются элементами матрицы S, гдеВ = (Е - А)-1У = S
Зная закупочные цены сырья и рыночные цены готовой продукции, можно подсчитать прибыль.
§11. Матричная игра как модель конкуренции
и сотрудничества
Пусть игроки
– Первый и Второй,
играют в матричную
игру с матрицей
.
Пусть стратегия
Первого есть
,
а Второго –
.
Тогда выигрыш
Первого есть
случайная
величина (с.в.)
с рядом распределения:
|
|
|
… |
|
… |
|
||||
|
|
… |
|
… |
|
Математическое
ожидание этой
с.в., т.е.
есть средний
выигрыш Первого.
Пусть
есть дисперсия
этой с.в. Естественно
назвать среднее
квадратическое
отклонение
с.в.
,
т.е.
риском для
Первого при
игре со стратегиями
.
Поскольку
выигрыш Первого
есть проигрыш
для Второго,
то
есть случайный
проигрыш Второго
и
вполне естественно
можно назвать
риском игры
с такими стратегиями
и для Второго.
Предположим
сначала, что
игроки озабочены
только максимизацией
среднего дохода
за партию игры
– обычная цель
в таких играх.
Тогда игроки
будут играть
со своими
оптимальными
стратегиями:
– Первый
игрок и
– Второй.
Математическое
ожидание с. в.
называется
ценой игры,
обозначим ее
.
Но что же назвать риском всей игры?
Вычислим дисперсию выигрыша Первого при оптимальных стратегиях игроков.
.
Так как
,
а через
сумма обозначена
.
Заметим,
что в сумме
можно оставить
лишь те слагаемые,
у которых

Заметим
теперь, что
если Первый
играет со стратегией
,
а Второй отвечает
-й
чистой стратегией,
то выигрыш
первого есть
с.в. с рядом
распределения:
|
|
|
… |
|
… |
|
||||
|
|
… |
|
… |
|
Е
34
сли
есть оптимальная
стратегия
Первого, а
,
то из теории
матричных игр
с нулевой суммой
известно, что
выигрыш Первого
при таких стратегиях
по-прежнему
равен цене игры
,
а дисперсия
выигрыша Первого
при этом равна
,
то есть равна
.
Таким образом,
что происходит
с риском выигрыша
Первого, можно
понять, сравнив
дисперсию при
оптимальных
стратегиях
и дисперсию
или величины
и
.
Пусть
Как легко понять,
если среди
есть разные
числа, то
Теперь можно сделать следующий вывод:
Чуть-чуть отойдя от своей оптимальной стратегии (смотрите ниже Пример) и таким образом почти не уменьшив свой выигрыш, Первый может значительно уменьшить свой риск. При этом уменьшается и риск Второго, что отвечает и его интересам.
Чисто математически можно сказать, что в описанной ситуации риск выигрыша Первого не зависит от его стратегии непрерывно.
Рассмотрим
подробно пример
матричной игры
с матрицей
.
Как известно,
общий случай
в окрестности
оптимальных
стратегий
игроков сводится
к анализу такой
игры.
Пример.
Пусть матрица
игры есть
.
Графическое
решение этой
игры показано
на рисунке 1.

Рис. 2
Цена игры
,
оптимальные
стратегии
игроков есть
,
.
Дисперсия
выигрыша Первого
при оптимальных
стратегиях
,
т. е. риск игры
равен примерно
1. Далее вычисления
дают
,
;
,
Примерная, но
достаточно
точная зависимость
риска Первого
в малой окрестности
его оптимальной
стратегии
показана на
рис. 2.

48
К
35
ак видно из рис. 2 при отходе Первого от своей оптимальной стратегии вправо, т. е. при увеличении вероятности x выбора им 1-й строки. Второй начинает отвечать 1-й чистой стратегией и риск Первого скачком увеличивается до
,
а при отходе
Первого от
своей оптимальной
стратегии влево
Второй переходит
на свою 2-ю чистую
стратегию и
риск Первого
скачком снижается
до


Аналогичное
верно и в отношении
Второго. Кратко
повторим. Примерная,
но достаточно
точная зависимость
риска Второго
в малой окрестности
его оптимальной
стратегии
показана на
рис. 3. Как видно
из рис. 3 при отходе
второго от
своей оптимальной
стратегии
вправо, т. е. при
увеличении
вероятности
у выбора им 1-й
строки Первый
начинает отвечать
2-й чистой стратегией
и риск Второго
скачком уменьшается
до
,
а при отходе
второго от
своей оптимальной
стратегии влево
Первый переходит
на свою 1-ю чистую
стратегию и
риск Второго
скачком увеличивается
до
Пусть
.
Эту величину
и можно назвать
риском всей
игры. Однако
играть с таким
риском можно
лишь при согласии
обеих сторон.
Для анализируемой
игры
и игроки для
достижения
такого риска
должны играть
так:
+ bx + c +
h2y3
+ F1(y2)
+ bx3
+ c + h3y4
+ F2(y3)






