Автор работы: Пользователь скрыл имя, 17 Ноября 2011 в 09:47, контрольная работа
Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С.
Технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:
Вектор B объемов ресурсов, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:
Вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции 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 + ... + dn (5)
т.е. объем производимой продукции xj на этапе j может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих этапах, но не
имеет смысла иметь yj+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная xj должна удовлетворять ограничениям
0 £ xj £ dj + yj+1 (6)
Следует также заметить, что переменные xj, yj могут принимать только целые неотрицательные значения, т.е. мы получили задачу целочисленного нелинейного программирования.
Будем решать задачу (1)-(6) методом динамического программирования.
Введем параметр состояния и составим функцию состояния.
За параметр состояния x примем наличный запас в конце k -го месяца
x = yk+1 (7)
а функцию состояния Fk(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5)
(8)
где минимум берется по неотрицательным целым значениям x1,...,xk, удовлетворяющим условиям
xj + yj - dj = yj+1 j = 1, k-1 (9)
xk + yk - dk = x (10)
Учитывая, что
и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна
yk = x + dk - xk (12)
приходим к рекуррентному соотношению
где минимум берется по единственной переменной xk, которая, согласно (6) может изменяться в пределах
0 £ xk £ dk + x (14)
принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах
0 £ x £ dk+1 + dk+2 + ... + dn (15)
а индекс k может принимать значения
k = 2, 3, 4, ... , n
Если k=1, то
F1(x = y2) = min f1(x1, x) (17)
где
x1 = x + d1 - y1 (18)
0£ x £ d2 + d3 + ... + dn (19)
т.е. на
начальном этапе при
Применив
известную вычислительную процедуру
динамического
Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть
jj(xj) = axj2 + bxj + c
jj (xj) - затраты на производство (закупку) xj единиц продукции на этапе j;
hj - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.
Тогда
затраты на производство и хранение
на этапе j равны
fj(xj, yj+1) = jj(xj) + hj yj+1 = axj2 + bxj + c + hj yj+1. (21)
Выведенные ранее рекуррентные соотношения динамического программирования для решения задачи управления производством и запасами в нашем случае принимают вид:
(22)
где
k = 2, 3, ... , n (23)
0 £ yk+1 £ dk+1 + dk+1 + ... + dn (24)
0 £ xk £ dk + yk+1 (25)
yk = yk+1 + dk - xk (26)
Если же k=1, то
Остается заметить, что полезно обозначить выражение в фигурных скобках через
Wk(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk) (31)
и записать рекуррентное соотношение (22) в виде
Fk(x=yk+1) = min Wk(xk, yk+1) (32)
xk
где минимум берется по целочисленной переменной xk, удовлетворяющей условию (25).
Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=2 единицы, на второй – d2=3, на третий - d3=3 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=3, h2=2, h3=3. Затраты на производство xj единиц продукции на j-м этапе определяются функцией
jj(xj) = 2xj2 + 3xj + 4 (33)
т.е. а=2 b=3; с=4. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3 y1
2 3 3 2 3 4 3 2 2 2
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем
F1 (x = y2), F2 (x = y3), ..., Fk (x = yk+1), ... и соответственно находим 1 (x= y2), 2 (x = y3 ), ..., ` k (x = yk+1), ...
Положим k = 1. Согласно (27) имеем
(34)
Учтем, что согласно (28) параметр состояния x = у2 может принимать целые значения на отрезке 0 у2 d2 + d3 , т.е. у2 = 0, 1, 2, 3, 4, 5, 6.
При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29)
0
Однако, на первом этапе объем производства х1 не может быть меньше единицы, так как спрос d1 = 2, а исходный запас у1 = 2. Более того, из балансового уравнения
х1 + у1 - d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния x= у2 соотношением
x1 = y2 + d1 - y1 = y2 + 2 - 2 = y2 (35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому
F1(x = y2) = W1 (x1, y2)
Придавая у2 различные целые значения от 0 до 6 и учитывая (35), находим
y2 = 0, x1 = 0, W1 (0;0) = 02 + 3×0 + 4 + 3×0 = 4
y2 = 1, x1 = 1, W1 (1;1) = 12 + 3×1 + 4 + 3×1 = 11
y2 = 2, x1 = 2, W1 (2;2) = 22 + 3×2 + 4 + 3×2 = 20
y2 = 3, x1 = 3, W1 (3;3) = 32 + 3×3 + 4 + 3×3 = 31
y2 = 4, x1 = 4, W1 (4;4) = 42 + 3×4 + 4 + 3×4 = 44
y2 = 5, x1 = 5, W1 (5;5) = 52 + 3×5 + 4 + 3×5 = 59
y2 = 6, x1 = 6, W1 (6;6) = 62 + 3×6 + 4 + 3×6 = 76