Прикладная математика

6 заполняем только одну диагональ для значения (= 700. Наибольшее число на

этой диагонали:

Zmax = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено

х*4 = [pic]4 (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно,

что третьему предприятию должно быть выделено

x*3 = [pic]3 (700-x*4) = [pic]3 (400) = 200 тыс. руб.

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

x*2 = [pic]2 (700 - x*4 - x*3) = [pic]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

| |( - x2 | 0 100 200 300 400 500 600 |

| | |700 |

|x2 |F1(( - x2) | 0 20 34 46 53 55 |

| |f2(x2) |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

|( | 0 100 200 300 400 500 600 |

| |700 |

|F2(() | 0 20 38 52 65 82 |

| |98 112 |

|([pic](() | 0 0 100 100 300 400 500|

| |500 |

Таблица 4

| |( - x3 | 0 100 200 300 400 500 600 |

| | |700 |

|x3 |F2(( - x3) | 0 20 38 52 65 82 |

| |f3(x3) |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

|( | 0 100 200 300 400 500 600 |

| |700 |

|F3(() | 0 25 45 63 79 94 |

| |112 126 |

|[pic](() | 0 100 100 100 200 400 400|

| |400 |

Таблица 6

| |( - x4 | 0 100 200 300 400 500 600 |

| | |700 |

|x4 |F3(( - x4) | 0 25 45 63 79 94 |

| |f4(x4) |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 месяцев с учетом

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

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)

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

[pic] (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) методом динамического программирования.

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

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

( = yk+1 (7)

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

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

[pic] (8)

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

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

xj + yj - dj = yj+1 j = 1, k-1 (9)

xk + yk - dk = ( (10)

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

[pic] (11)

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

равна

yk = ( + dk - xk (12)

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

[pic] (13)

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

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

0 ( xk ( dk + ( (14)

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

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

0 ( ( ( dk+1 + dk+2 + ... + dn

(15)

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

k = 2, 3, 4, ... , n

(16)

Если k=1, то

F1(( = y2) = min f1(x1, () (17)

x1

где

x1 = ( + d1 - y1 (18)

0( ( ( d2 + d3 + ... + dn (19)

т.е. на начальном этапе при фиксированном уровне y1 исходного запаса

каждому значению параметра ( отвечает только одно значение переменной x1,

что несколько уменьшает объем вычислений.

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

программирования, на последнем шаге (при k = n) находим значение последней

компоненты xn* оптимального решения, а остальные компоненты определяем как

[pic] (20)

Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные

соотношения. Пусть

(j(xj) = axj2 + bxj + c

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

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

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

fj(xj, yj+1) = (j(xj) + hj yj+1 = axj2 + bxj + c + hj yj+1.

(21)

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

для решения задачи управления производством и запасами в нашем случае

принимают вид:

[pic] (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, то

[pic]

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

через

(k(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk)

(31)

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

Fk((=yk+1) = min (k(xk, yk+1)

(32)

xk

где минимум берется по целочисленной переменной xk, удовлетворяющей условию

(25).

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

продукцией и динамическим детерминированным спросом.

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на

первый этап d1=3 единицы, на второй – d2=2, на третий - d3=4 единицы. К

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

начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции

на разных этапах различны и составляют соответственно h1=1, h2=3, h3=2.

Затраты на производство xj единиц продукции на j-м этапе определяются

функцией

(j(xj) = xj2 + 5xj + 2 [pic]

(33)

т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на

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

удовлетворены, а наши общие затраты на производство и хранение за все три

этапа были наименьшими.

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

d1 d2 d3 a b c h1 h2

h3 y1

1 2 4 1 5 2 1 3

2 2

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

вычисляем

F1 (( = y2), F2 (( = y3), ..., Fk (( = yk+1), ... и соответственно

находим [pic]1 ((= y2), [pic]2 (( = y3 ), ..., ([pic]k (( = yk+1),

...

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

[pic] (34)

Учтем, что согласно (28) параметр состояния ( = у2 может принимать целые

значения на отрезке

0 [pic] у2 [pic] d2 + d3

0 [pic] y2

[pic] 2 + 4

т.е.

у2 = 0, 1, 2, 3, 4, 5, 6.

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

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

условием (29)

0 [pic] х1 [pic] 3 + у2

Однако, на первом этапе объем производства х1 не может быть меньше

единицы, так как спрос d1 = 3, а исходный запас у1 = 2. Более того, из

балансового уравнения

х1 + у1 - d1 = у2

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

параметра состояния (= у2 соотношением

x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1

(35)

В этом и состоит особенность первого этапа. Если задан уровень запаса к

началу первого этапа, то каждому значению у2 отвечает единственное значение

х1 и потому

F1(( = y2) = (1 (x1, y2)

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

y2 = 0, x1 = 0+1 = 1, (1 (1;0) = 12 + 5(1 + 2 + 1(0 = 8

y2 = 1, x1 = 1+1 = 2, (1 (2;1) = 22 + 5(2 + 2 + 1(1 = 17

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

Таблица 1

|( = y2 |0 |1 |2 |3 |4 |5 |6 |

|F1 (( = y2) |8 |17 |28 |41 |56 |73 |92 |

|x1((=y2) |1 |2 |3 |4 |5 |6 |7 |

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию

F2(( = y3) с помощью соотношения (32)

[pic] (37)

Здесь минимум берется по единственной переменной х2, которая может

изменяться, согласно (25), в пределах

0 ( x2 ( d2 + y3 или 0 ( x2 ( 2 + y3

(38)

где верхняя граница зависит от параметра состояния ( = у3, который,

согласно (15), принимает значения на отрезке

0 ( y3 ( d3 , т.е. 0 ( y3 ( 4

(39)

а аргумент у2 в последнем слагаемом справа в соотношении (37) связан с х2 и

у3 балансовым уравнением

x2 + y2 - d2 = y3

откуда следует

y2 = y3 + d2 - x2 = y3 + 2 - x2

(40)

Придавая параметру состояния различные значения от 0 до 4, будем

последовательно вычислять (2 (x2, (), а затем определять F2(( ) и [pic]2((

).

Положим, например ( = у3 = 2. Тогда, согласно (38),

0 ( x2 ( 4,

т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому

значению х2 отвечает определенное значение у2, вычисляемое по формуле (40):

у2 = 4 - х2

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

если x2 = 0, то y2 = 4-0 = 4, (2 (0,2) = 02 + 5(0 + 2 + 3(2 +

F1(4) = 8 + 56 = 64,

x2 = 1, y2 = 4-1 = 3, (2 (1,2) = 12 + 5(1 + 2 + 3(2 +

F1(3) = 14 + 41 = 55,

x2 = 2, y2 = 4-2 =2, (2 (2,2) = 22 + 5(2 + 2 + 3(2 + F1(2) =

22 + 28 = 50,

x2 = 3, y2 = 4-3 = 1, (2 (3,2) = 32 + 5(3 + 2 + 3(2 +

F1(1) = 32 + 17 = 49*,

x2 = 4, y2 = 4-4 = 0, (2 (3,2) = 42 + 5(4 + 2 + 3(2 +

F1(0) = 44 + 8 = 52.

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

F2 (( = y3 = 2) = min (2 (x2,2) = min (64, 55, 50, 49, 52) = 49,

x2

причем минимум достигается при значении х2, равном

([pic]2 (( = y3 = 2) = 3

Аналогично для значения параметра ( = у3 = 3, проведя необходимые

вычисления, найдем

F2 (( = y3 = 3) = 63; ([pic]2 (( = y3 = 3) = 3.

Процесс табулирования функции F2 (( = y3) приведен в табл. 2, а

результаты табулирования сведены в табл. 3.

Таблица 3

|(= у3 |0 |1 |2 |3 |4 |

|F2 ((= y3) |24 |36 |49 |63 |78 |

|[pic]((= |2 |2 |3 |3 |4 |

|y3) | | | | | |

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 (( =

y4):

[pic]

Вычисляем значение функции состояния только для одного значения

аргумента ( = у4 = 0, так как не хотим оставлять продукцию в запас в конце

исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем

F3 (( = y4) = min (3 (x3,0) = min (80, 71, 65, 62, 62) = 62,

x3

причем минимум достигается при двух значениях переменной х3, равных

([pic]3 (( = y4 = 0) = 3 или ([pic]3 (( = y4 = 0) = 4.

Таким образом, мы получили не только минимальные общие затраты на

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

решения. Она равна

[pic]= 3 или [pic]= 4.

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

единицы продукции

[pic]= 3.

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

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

компоненту, учтем, что

х3 + у3 - d3 = y4

или

3 + у3 - 4 = 0,

откуда

у3 = 1.

Из таблицы (3) значений [pic] находим

[pic]

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

х2 + у2 - d2 = y3

|[pic] |[pic] |[pic] |xk |yk = yk+1 + dk - |(k(xk, yk+1) =(k(xk) + hkyk+1 + Fk-1(yk) |

| | | | |xk | |

|0 ( y3 ( d3 |( = y3 |0 ( x2 ( d2 + y3 |x2 |y2 = y3 + d2 - x2 |(2(x2, y3) = a[pic] + bx + c + h2y3 + F1(y2)|

|0 ( y3 ( 4 |( = y3 |0 ( x2 ( 2 + y3 |x2 |y2 = y3 + 3 - x2 |[pic] |

| |y3 = 0 |0 ( x2 ( 2 |x2 = 0|y2 = 2-0 = 2 |(2(0;0) = 02 + 5(0 + 2 + 3(0 + F1(2) =2+28 |

| | | | |y2 = 2- 1 = 1 |=30 |

| | | |x2 = 1|y2 = 2-2 = 0 |(2(1;0) = 12 + 5(1 + 2 +3(0 + F1(1)=8+17 =25|

| | | | | | |

| | | |x2 = 2| |(2(2;0) = 22 +5(2 + 2 + 3(0 +F1(0) =16+8=24*|

| |y3 = 1 |0 ( x2 ( 3 |x2 = 0|y2 = 3 - 0 = 3 |(2(0;1) = 02 + 5(0 + 2 + 3(1 + F1(3) = |

| | | | |y2 = 3-1 = 2 |5+41=46 |

| | | |x2 = 1|y2 = 3-2 = 1 |(2(1;1) = 12 + 5(1 + 2 + 3(1 + F1(2) =11+28 |

| | | | |y2 = 3-3 = 0 |=39 |

Страницы: 1, 2, 3, 4, 5