Прикладная математика
Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x ) определим как максимальную прибыль на первых k предприятиях, если они вместе получают x рублей. Параметр x может изменяться от 0 до b. Если из x рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные x - xk рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль Fk-1(x - xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x - xk). Надо выбрать такое значение xk между 0 и x , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению
Fk(x )=max{fk(xk) + Fk-1(x -xk)}
0 £ xk £ x
для k = 2, 3, 4, ... , n . Если же k=1, то
F1(x ) = f1(x )
Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.
Таблица I
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1(x
- x2) = f1(x
- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение
. Заполняем таблицу 3.
Продолжая процесс, табулируем функции F3(x
),
(x
) и т.д. В табл. 6 заполняем только одну диагональ для значения x
= 700. Наибольшее число на этой диагонали:
Zmax = 155 тыс. руб.,
причем четвертому предприятию должно быть выделено
х*4 =
4 (700) = 300 тыс. руб.
На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено
x*3 =
3 (700-x*4) =
3 (400) = 200 тыс. руб.
Продолжая обратный процесс, находим
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
Таблица 3
§ 9. Динамическая задача управления производством >и запасами
Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на 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+1j = 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+1j = 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)
а индекс k может принимать значения
k = 2, 3, 4, ... , n (16)
Если k=1, то
(17)
где
x1 = x + d1 - y1(18)
0£ x £ d2 + d3 + ... + dn(19)
т.е. на начальном этапе при фиксированном уровне y1 исходного запаса каждому значению параметра x отвечает только одно значение переменной x1, что несколько уменьшает объем вычислений.
Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты xn* оптимального решения, а остальные компоненты определяем как
(20)
Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть
j j(xj) = axj2 + bxj + c
j j (xj) - затраты на производство (закупку) xj единиц продукции на этапе j;
hj - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.
Тогда затраты на производство и хранение на этапе j равны
fj(xj, yj+1) = j j(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, то

Остается заметить, что полезно обозначить выражение в фигурных скобках через
W k(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk)(31)
и записать рекуррентное соотношение (22) в виде
(32)
где минимум берется по целочисленной переменной xk, удовлетворяющей условию (25).
Пример. Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=2, на третий - d3=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=1, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией
j
j(xj) = xj2 + 5xj + 2
(33)
т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3y1
1 2 4 15 2 1 3 22
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем
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
0
y2
2 + 4
т.е.
у2 = 0, 1, 2, 3, 4, 5, 6.
При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29)
0
х1
3 + у2
Однако, на первом этапе объем производства х1 не может быть меньше единицы, так как спрос d1 = 3, а исходный запас у1 = 2. Более того, из балансового уравнения
х1 + у1 - d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния x = у2 соотношением
x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1(35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому
F1(x = y2) = W 1 (x1, y2)
Придавая у2 различные целые значения от 0 до 6 и учитывая (35), находим
y2 = 0,x1 = 0+1 = 1,W 1 (1;0) = 12 + 5× 1 + 2 + 1× 0 = 8
y2 = 1, x1 = 1+1 = 2,W 1 (2;1) = 22 + 5× 2 + 2 + 1× 1 = 17
и т.д. Значения функции состояния F1(x ) представлены в табл. 1
Таблица 1
|
x = y2 |
0 |
1 |
2 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |