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

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

x_j - число изделий, производимых в j -й месяц;

y_j - величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);

d_j - число изделий, которые должны быть отгружены в j -й месяц;

f_j (x_j,y_j+1) - затраты на хранение и производство изделий в j -м месяце.

Будем считать, что величины запасов к началу первого месяца y₁ и к концу последнего y_n+1 заданы.

Задача состоит в том, чтобы найти план производства

(x₁, x₂, ..., x_n) (1)

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

x_j + y_j - d_j = y_j+1 j = 1,n (2)

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

(3)

причем по смыслу задачи

x_j  0, y_j  0, j = 1,n (4)

Прежде чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина y_j+1 запаса к концу месяца должна удовлетворять ограничениям

0  y_j+1  d_j+1 + d_j+2 + ... + d_n (5)

т.е. объем производимой продукции x_j на этапе j может быть настолько велик, что запас y_j+1 удовлетворяет спрос на всех последующих этапах, но не

имеет смысла иметь y_j+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная x_j должна удовлетворять ограничениям

0  x_j  d_j + y_j+1 (6)

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

Будем решать задачу (1)-(6) методом динамического программирования.

Введем параметр состояния и составим функцию состояния.

За параметр состояния  примем наличный запас в конце k -го месяца

 = y_k+1 (7)

а функцию состояния F_k() определим как минимальные затраты за первые k месяцев при выполнении условия (5)

(8)

где минимум берется по неотрицательным целым значениям x₁,...,x_k, удовлетворяющим условиям

x_j + y_j - d_j = y_j+1 j = 1, k-1 (9)

x_k + y_k - d_k =  (10)

Учитывая, что

(11)

и величина запаса y_k к концу (k-1) периода, как видно из уравнения (10), равна

y_k =  + d_k - x_k (12)

приходим к рекуррентному соотношению

(13)

где минимум берется по единственной переменной x_k, которая, согласно (6) может изменяться в пределах

0  x_k  d_k +  (14)

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

0    d_k+1 + d_k+2 + ... + d_n (15)

а индекс k может принимать значения

k = 2, 3, 4, ... , n (16)

Если k=1, то

F₁( = y₂) = min f₁(x₁, ) (17)

x₁

где

x₁ =  + d₁ - y₁ (18)

0   d₂ + d₃ + ... + d_n (19)

т.е. на начальном этапе при фиксированном уровне y₁ исходного запаса каждому значению параметра  отвечает только одно значение переменной x₁, что несколько уменьшает объем вычислений.

Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты x_n* оптимального решения, а остальные компоненты определяем как

(20)

Рассмотрим более подробно функции затрат f_j(x_j, y_j+1) и рекуррентные соотношения. Пусть

_j(x_j) = ax_j² + bx_j + c

_j (x_j) - затраты на производство (закупку) x_j единиц продукции на этапе j;

h_j - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.

Тогда затраты на производство и хранение на этапе j равны

f_j(x_j, y_j+1) = _j(x_j) + h_j y_j+1 = ax_j² + bx_j + c + h_j y_j+1. (21)

Выведенные ранее рекуррентные соотношения динамического программирования для решения задачи управления производством и запасами в нашем случае принимают вид:

(22)

где

k = 2, 3, ... , n (23)

0  y_k+1  d_k+1 + d_k+1 + ... + d_n (24)

0  x_k  d_k + y_k+1 (25)

y_k = y_{k+1 +} d_k - x_k (26)

Е

(27)

сли же k=1, то

(30)

(29)

(28)

Остается заметить, что полезно обозначить выражение в фигурных скобках через

_k(x_k, y_k+1) = ax_j² + bx_j + c + h_ky_k+1 + F_k-1(y_k) (31)

и записать рекуррентное соотношение (22) в виде

F_k(=y_k+1) = min _k(x_k, y_k+1) (32)

x_k

где минимум берется по целочисленной переменной x_k, удовлетворяющей условию (25).

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

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d₁=2 единицы, на второй – d₂=3, на третий - d₃=3 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y₁=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁=3, h₂=2, h₃=3. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

_j(x_j) = 2x_j² + 3x_j + 4 (33)

т.е. а=2 b=3; с=4. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

Исходные данные задачи можно кратко записать одной строкой:

d₁ d₂ d₃ a b c h₁ h₂ h₃ y₁

2 3 3 2 3 4 3 2 2 2

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

F₁ ( = y₂), F₂ ( = y₃), ..., F_k ( = y_k+1), ... и соответственно находим ₁ (= y₂), ₂ ( = y₃ ), ..., _k ( = y_k+1), ...

Положим k = 1. Согласно (27) имеем

(34)

Учтем, что согласно (28) параметр состояния  = у₂ может принимать целые значения на отрезке 0 у₂ d₂ + d₃ , т.е. у₂ = 0, 1, 2, 3, 4, 5, 6.

При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x₁, характеризуемая условием (29)

0 х₁ 2 + у₂

Однако, на первом этапе объем производства х₁ не может быть меньше единицы, так как спрос d₁ = 2, а исходный запас у₁ = 2. Более того, из балансового уравнения

х₁ + у₁ - d₁ = у₂

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

x₁ = y₂ + d₁ - y₁ = y₂ + 2 - 2 = y₂ (35)

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у₂ отвечает единственное значение х₁ и потому

F₁( = y₂) = ₁ (x₁, y₂)

Придавая у₂ различные целые значения от 0 до 6 и учитывая (35), находим

y₂ = 0, x₁ = 0, ₁ (0;0) = 0² + 30 + 4 + 30 = 4

y₂ = 1, x₁ = 1, ₁ (1;1) = 1² + 31 + 4 + 31 = 11

y₂ = 2, x₁ = 2, ₁ (2;2) = 2² + 32 + 4 + 32 = 20

y₂ = 3, x₁ = 3, ₁ (3;3) = 3² + 33 + 4 + 33 = 31

y₂ = 4, x₁ = 4, ₁ (4;4) = 4² + 34 + 4 + 34 = 44

y₂ = 5, x₁ = 5, ₁ (5;5) = 5² + 35 + 4 + 35 = 59

y₂ = 6, x₁ = 6, ₁ (6;6) = 6² + 36 + 4 + 36 = 76

. Значения функции состояния F₁() представлены в табл.

 = y2	0	1	2	3	4	5	6
F1 (= y2)	4	11	20	31	44	59	76
x1(=y2)	0	1	2	3	4	5	6

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F₂( = y₃) с помощью соотношения (32)

Здесь минимум берется по единственной переменной х₂, которая может изменяться, согласно (25), в пределах 0  x₂  d₂ + y₃ или 0  x₂  3 + y₃ (38)

где верхняя граница зависит от параметра состояния  = у₃, который, согласно (15), принимает значения на отрезке 0  y₃  d₃ , т.е. 0  y₃  3 (39)

а аргумент у₂ в последнем слагаемом справа в соотношении (37) связан с х₂ и у₃ балансовым уравнением x₂ + y₂ - d₂ = y₃

откуда следует y₂ = y₃ + d₂ - x₂ = y₃ + 3 - x₂ (40)

Придавая параметру состояния различные значения от 0 до 3, будем последовательно вычислять ₂ (x₂, ), а затем определять F₂( ) и ₂( ).

Положим, например  = у₃ = 2. Тогда, согласно (38), 0  x₂  5,

т.е. переменная х₂ может принимать значения: 0, 1, 2, 3, 4, 5, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (40): у₂ = 5 - х₂

Последовательно находим:

если x₂ = 0, то y₂ = 5-0 = 5, ₂ (0,2) = 0² + 30 + 4 + 22 + F₁(5) = 8 + 59 = 67,

x₂ = 1, y₂ = 5-1 = 4, ₂ (1,2) = 1² + 31 + 4 + 22 + F₁(4) = 12 + 44 = 56,

x₂ = 2, y₂ = 5-2 =3, ₂ (2,2) = 2² + 32 + 4 + 22 + F₁(3) = 18 + 31 = 49,

x₂ = 3, y₂ = 5-3 = 2, ₂ (3,2) = 3² + 33 + 4 + 22 + F₁(2) = 26 + 20 = 46*,

x₂ = 4, y₂ = 5-4 = 1, ₂ (4,2) = 4² + 34 + 4 + 22 + F₁(1) = 36 + 11 = 47.

x₂ = 5, y₂ = 5-5 = 0, ₂ (5,2) = 5² + 35 + 4 + 22 + F₁(0) = 48 + 4 = 52.

Н

29

аименьшее из полученных значений₂ есть F₂ (2), т.е.

F₂ ( = y₃ = 2) = min ₂ (x₂,2) = min (67, 56, 49, 46, 47,52) = 46,

причем минимум достигается при значении х₂, равном₂ ( = y₃ = 2) = 3

Аналогично для значения параметра  = у₃ = 3,. 0  x₂  6,

если x₂ = 0, то y₂ = 6-0 = 6, ₂ (0,3) = 0² + 30 + 4 + 23 + F₁(6) = 10 + 76 = 86,

x₂ = 1, y₂ = 6-1 = 5, ₂ (1,3) = 1² + 31 + 4 + 23 + F₁(5) = 14 + 59 = 73,

x₂ = 2, y₂ = 6-2 = 4, ₂ (2,3) = 2² + 32 + 4 + 23 + F₁(4) = 20 + 44 = 64,

x₂ = 3, y₂ = 6-3 = 3, ₂ (3,3) = 3² + 33 + 4 + 23 + F₁(3) = 28 + 31 = 59,

x₂ = 4, y₂ = 6-4 = 2, ₂ (4,3) = 4² + 34 + 4 + 23 + F₁(2) = 38 + 20 = 58*.

x₂ = 5, y₂ = 6-5 = 1, ₂ (5,3) = 5² + 35 + 4 + 23 + F₁(1) = 50 + 11 = 61.

x₂ = 6, y₂ = 6-6 = 0, ₂ (5,3) = 6² + 36 + 4 + 23 + F₁(0) = 64 + 4 = 68.

Наименьшее из полученных значений ₂ есть F₂ (3), т.е.

F₂ ( = y₃ = 3) = min ₂ (x₂,3) = min (86, 73, 64, 59, 58,61, 68) = 58,

причем минимум достигается при значении х₂, равном₂ ( = y₃ = 3) = 4

 = у₃ = 0, 0  x₂  3,

если x₂ = 0, то y₂ = 3-0 = 3, ₂ (0,0) = 0² + 30 + 4 + 20 + F₁(3) = 4 + 31 = 35,

x₂ = 1, y₂ = 3-1 = 2, ₂ (1,0) = 1² + 31 + 4 + 20 + F₁(2) = 8 + 20 = 28,

x₂ = 2, y₂ = 3-2 = 1, ₂ (2,0) = 2² + 32 + 4 + 20 + F₁(1) = 14 + 11 = 25*,

x₂ = 3, y₂ = 3-3 = 0, ₂ (3,0) = 3² + 33 + 4 + 20 + F₁(0) = 22 + 4 = 26,

Наименьшее из полученных значений ₂ есть F₂ (0), т.е.

F₂ ( = y₃ = 3) = min ₂ (x₂,3) = min (35, 28, 25, 26) = 25,

причем минимум достигается при значении х₂, равном₂ ( = y₃ = 0) = 2

 = у₃ = 1, 0  x₂  4,

x₂ = 0, y₂ = 4-0 = 4, ₂ (0,1) = 0² + 30 + 4 + 21 + F₁(4) = 6 + 44 = 50,

x₂ = 1, y₂ = 4-1 = 3, ₂ (1,1) = 1² + 31 + 4 + 21 + F₁(3) = 10 + 31= 41,

x₂ = 2, y₂ = 4-2 = 2, ₂ (2,1) = 2² + 32 + 4 + 21 + F₁(2) = 16 + 20 = 36,

x₂ = 3, y₂ = 4-3 = 1, ₂ (3,1) = 3² + 33 + 4 + 21 + F₁(1) = 24 + 11 = 35*,

x₂ = 4, y₂ = 4-4 = 0, ₂ (4,1) = 4² + 34 + 4 + 21 + F₁(0) = 34 + 4 = 38,

Наименьшее из полученных значений ₂ есть F₂ (1), т.е.

F₂ ( = y₃ = 1) = min ₂ (x₂,3) = min (50, 41, 36, 35, 38) = 35,

причем минимум достигается при значении х₂, равном₂ ( = y₃ = 1) = 3

= у3	0	1	2	3
F2 (= y3)	25	35	46	58
(= y3)	2	3	3	4

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F₃ ( = y₄):

Вычисляем значение функции состояния только для одного значения аргумента  = у₄ = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода, 0  x₃  3 + y₄

x₃ = 0, y₃ = 3-0 = 3, ₃ (0,0) = 0² + 30 + 4 + 20 + F₂(3) = 4 + 58 = 62,

x₃ = 1, y₃ = 3-1 = 2, ₃ (1,0) = 1² + 31 + 4 + 20 + F₂(2) = 8 + 46= 54,

x₃ = 2, y₃ = 3-2 = 1, ₃ (2,0) = 2² + 32 + 4 + 20 + F₂(1) = 14 + 35 = 49,

x₃ = 3, y₃ = 3-3 = 0, ₃ (3,0) = 3² + 33 + 4 + 20 + F₂(0) = 22 + 25 = 47*,

Наименьшее из полученных значений ₂ есть F₃ (0), т.е.

F₃ ( = y₄ = 1) = min ₃ (x₃,3) = min (62, 54, 49, 47) = 47,

причем минимум достигается при значении х₂, равном₃ ( = y₄ = 0) = 3

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

Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции

= 3.

Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что

х₃ + у₃ - d₃ = y₄

3 + у₃ - 3 = 0,

у₃ = 0.

Из таблицы значений находим

Аналогично, продолжая двигаться в обратном направлении и учтя, что

х₂ + у₂ - d₂ = y₃

2 + у₂ - 3 = 0

у₂ = 1.

Из таблицы значений находим

6. Матричная игра как модель конкуренции и сотрудничества

1. Пусть игроки – Первый и Второй, играют в матричную игру с матрицей . Пусть стратегия Первого есть , а Второго –. Тогда выигрыш Первого есть случайная величина (с.в.)с рядом распределения:

W(P,Q)	a11		...		aij		...		amn
	p1q1		...		piqj		...		pmqn

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

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

Математическое ожидание с. в. называется ценой игры, обозначим ее.

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

Пусть матрица игры есть

3. Проведем анализ матрицы игры на доминирование:

А _2.4=;;

a_1.2=a_1.3= -2

a_2.2≥a_2.3, т.е 3 ≥ 1, значит 2-ый столбец доминирует над третьим, вычеркиваем его и получаем новую матрицу:

А`_2.3=;;

a_2.1=a_2.3= -2

a_1.1 ≤ a_1.3, т.е 1 ≤ 4, значит 3-ый столбец доминирует над 1-м, вычеркиваем его и получаем новую матрицу:

А``_2.2=;;

4. Проведем анализ матрицы игры на седловую точку:

Вывод: Так как , то в матрице игры нет седловой точки.

5. Так как седловой точки нет, решим задачу графически:

А=.

ν_j(x) – средний выигрыш 1-го в расчете на партию, когда он использует стратегию (х, 1-х), а 2-ой j-ую.

1.

2.

3.

4.

Возьмем на плоскости систему координат, по горизонтали оси вправо х, по вертикали оси – значения функции ν_j(x). Масштаб по осям выберем разный – ведь нужна только часть графиков – над отрезком [0;1]. Функции ν_j(x), i = 1, 2, 3 – линейные, значит, их графики – прямые линии I, II, III, VI соответственно. Находим нижнюю огибающую семейства четырех прямых над отрезком [0;1]. Это ломаная АВС. Высшая точка В. Она дает решение игры. Ее координаты определяются решением уравнения ν₁(x) = ν₃(x).

,

Таким образом, средний выигрыш 1-го при игре обоих игроков с оптимальными стратегиями, т. е. цена игры равна , а оптимальная стратегия первого игрока

8. Рассмотрим стратегию 2-ого игрока. Так как прямые ,находятся выше точки О, то вероятности 2-ой и 4-ой стратегии равны 0, т.е,

А``_2.2=

3y- 2 = -3y+ 1

6y= 3, т.е получаем :

Оптимальные стратегии и цена игры равны: ;и

Риски.

Пусть игроки – Первый и Второй, играют в матричную игру с матрицей . Пусть стратегия Первого есть, а Второго –. Тогда выигрыш Первого есть случайная величина (с.в.)с рядом распределения:

			…				…
			…				…

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

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

Математическое ожидание с. в. называется ценой игры, обозначим ее.

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

.

Так как , а черезсумма обозначена.

Заметим, что в сумме можно оставить лишь те слагаемые, у которых

Заметим теперь, что если Первый играет со стратегией , а Второй отвечает-й чистой стратегией, то выигрыш первого есть с.в. с рядом распределения:

			…				…
			…				…

Е

34

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

Пусть игроки играют в матричную игру со стратегиями P, Q. Тогда выигрыш первого игрока есть случайная величина и ее среднее квадратическое отклонение называется риском игры со стратегиями P, Q и обозначается . Пусть игроки играют в матричную игру 2х4. В общем случае, второй игрок при своей оптимальной стратегии два столбца выбирать не будет, следовательно, фактически игра свелась к матричной игре 2х2. Обозначим оптимальные стратегии игроков в этой игре черезP и Q. Найдем четыре риска ,,,и найдем из них наименьший, это значение и называется риском игры.

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

1. Первый и второй игроки играют по оптимальной стратегии:

2. Первый игрок играет по оптимальной стратегии, а второй по 1-ой чистой (стратегия игрока от партии к партии остается неизменной):

3. Первый игрок играет по оптимальной стратегии, а второй игрок - по 2-ой чистой:

4. Первый игрок играет по 1-ой чистой стратегии, а второй игрок - по оптимальной:

5. Первый игрок играет по 2-ой чистой стратегии, а второй игрок - по оптимальной:

Минимальное значение можно назвать риском всей игры. Однако с таким риском можно играть лишь при согласии обеих сторон.

- 20-