Прикладная математика (стр. 7 из 14)

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

f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max

Таблица 2

x - x₂	0 100 200 300 400 500 600 700
x2	F₁(x - x₂)f₂(x₂)	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 .

Таблица 3

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

Таблица 4

x - x₃	0 100 200 300 400 500 600 700
x3	F₂(x - x₃)f₃(x₃)	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
F₃(x)	0 25 45 63 79 94 112 126
(x)	0 100 100 100 200 400 400 400

Таблица 6

	x - x₄	0 100 200 300 400 500 600 700
x4	F₃(x - x₄)f₄(x₄)	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. Динамическая задача управления производством

и запасами

Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на 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)

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

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

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

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

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

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

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

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

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

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

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

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