Продолжая обратный процесс, находим

x*2 = 2 (700 - x*4 - x*3) = 2 (200) = 100 тыс. руб.

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

x*1 = 700 - x*4 - x*3 - x*2 = 100 тыс. руб.

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

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

x*1 =100; x*2 =100; x*3 = 200; x*4 = 300.

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

прибыли 155 тыс. руб.

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

f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 20 34 46 53 55 60 60
0	0	0 20* 34 46 53 55 60 60
100	18	18 38* 52* 64 71 73 78
200	29	29 49 63 75 82 84
300	45	45 65* 79 91 98
400	62	62 82* 96 108
500	78	78 98* 112*
600	90	90 110
700	98	98 .

23

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0 20 38 52 65 82 98 112
`(x)	0 0 100 100 300 400 500 500

Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 20 38 52 65 82 98 112
0	0	0 20 38 52 65 82 98 112
100	25	25* 45* 63* 77 90 107 123
200	41	41 61 79* 93 106 123
300	52	52 72 94* 112 126
400	74	74 94* 112* 126*
500	82	82 102 120
600	88	88 106
700	90	90 .

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0 25 45 63 79 94 112 126
(x)	0 100 100 100 200 400 400 400

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 25 45 63 79 94 112 126
0	0	126
100	30	142
200	52	146
300	76	155*
400	90	153
500	104	149
600	116	141
700	125	125 .

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

24

и запасами

Предприятие производит партиями некоторые изделия. Предположим, что оно

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

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

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

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

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

производство и хранение изделий. Обозначим:

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

yj - величина запаса к началу j го месяца (это число не содержит

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

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

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

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

концу последнего yn+1 заданы.

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

(x1, x2, ..., xn)

(1)

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

xj + yj - dj = yj+1 j

= 1,n (2)

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

(3)

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

xj ³ 0, yj ³ 0, j = 1,n

(4)

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

месяца j величина yj+1 запаса к концу месяца должна удовлетворять

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

0 £ yj+1 £ dj+1 + dj+2 + ... + d

n (5)

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

велик, что запас yj+1 удовлетворяет спрос на всех последующих

этапах, но не

имеет смысла иметь yj+1 больше суммарного спроса на всех последующих

этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что

переменная xj должна удовлетворять ограничениям

0 £ xj £ dj + yj+1 (6)

Следует также заметить, что переменные xj, yj могут

принимать только целые неотрицательные значения, т.е. мы получили задачу

целочисленного нелинейного программирования.

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

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

25

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

x = yk+1

(7)

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

k месяцев при выполнении условия (5)

(8)

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

k, удовлетворяющим условиям

xj + yj - dj = yj+1

j = 1, k-1 (9)

xk + yk - dk = x

(10)

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

(11)

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

yk = x + dk - xk

(12)

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

(13)

где минимум берется по единственной переменной xk, которая, согласно

(6) может изменяться в пределах

0 £ xk £ dk + x (14)

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

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

0 £ x £ dk+1 + dk+2 + ... + dn

(15)

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14