<< Предыдущая

стр. 3
(из 7 стр.)

ОГЛАВЛЕНИЕ

Следующая >>



1.3. Динамическая модель в условиях поэтапного кредитования с
постоянным дисконтным коэффициентом.

Предположим более выгодную с точки зрения фирмы-
организатора ситуацию, когда размер кредита неограничен, и может
быть получен в любой момент времени по мере возникновения
необходимости. Процент, выплачиваемый по кредиту в единицу
времени, как и раньше, равен ?. Этот процент считается стабильным,
не зависящим от времени.
Итак, пусть S - множество всех источников сырья для
предприятий из множества N, а R - рынок сбыта всех видов товаров,
включая сырьё и продукцию всех предприятий из множества N.
Предполагается, что для производства своей продукции каждому
предприятию требуется ровно один вид сырья, а все остальные
расходные материалы учитываются в производственных затратах.

Пусть - затраты на производство единицы продукции в
wi
вершине i, ki - коэффициент усиления в i, равный количеству готовой

продукции, которая может быть изготовлена в i из единицы сырья, ci -
18


рыночная стоимость единицы продукции i, - ограничение на
ai
производственную мощность в вершине i, т.е. максимальное количество

продукции, которое может быть произведено в единицу времени ,?ij -

время прохождения дуги (i,j), f(i,j)- величина потока из i в j.

Рассмотрим производственную “технологическую цепочку” {i1 ,

i2 , ... , in} такую, что i1 ? S?N, in ? R , i2 , i3 , ... , in-1 ? N и для
каждой пары ik , ik+1 существует дуга (ik , ik+1). Вычислим прибыль от
функционирования цепочки в расчете на единицу сырья, поступающего
из i1 в i2, при условии, что кредит может быть получен в момент
возникновения необходимости.

Если из i1 в i2 поступит единица сырья, то в результате
функционирования всей “цепочки “ на рынке R будет продано

k2 ? k3 ??? kn-1,
конечного продукта в количестве и доход от его

продажи составит

? k2 ? k3 ??? kn-1 .
ci
(14) D =
n?1
Затраты с учетом дисконтного процента будут равны:
n ?1 n ?1
?? i i ?i
?
k ,ik +1 +...
(1 + ? ) k =1 k , k +1
F = Wi1 + ki2 Wi2 (1 + ? ) k =2

(15)
n ?1 ? i in
+( ? kik )Win ?1 (1 + ? ) n ?1
k =1


Ясно, что прибыль от этой цепочки будет равна D-F.
19


Рассмотрим задачу построения цепочки, оптимальной с точки
зрения максимизации удельной прибыли, т.е. прибыли, которая может
быть получена в расчете на единицу исходного сырья. Такая
постановка, очевидно, упрощает исходную задачу, т.к. сводит ее к
построению простейших линейных цепочек без разветвлений. Этот
подход, однако, обоснован с практической точки зрения, т.к. делает
явными, прозрачными производственные связи и источники доходов и
расходов, что необходимо при распределении конечной прибыли и
ответственности за возможные срывы в сроках и поставках.




Введем следующие обозначения. Пусть P1 - множество всех
вершин графа, связанных с R- ориентированной цепочкой длины 1, т.е.
P1= {i: ? (i,R)}, P2 - множество вершин связанных с R ориентированной
цепочкой длины 2 , P2={i: ? (i,j) и ? (j,R)} и т.д., Pm - множество вершин,
из которых существует путь в R длины m. Ясно, что эти множества
могут пересекаться, возможно, что Pl ? P2 ?...? Pm??. Это означает,
что продукция предприятий может либо быть либо непосредственно
продана на рынке, либо переработана на других предприятиях, причем
вариантов технологических цепочек может быть много. Отметим, что
множества P1, P2,..., Pm нет необходимости строить отдельно, т.к. в
ходе выполнения алгоритма формируются только те их элементы,
которые требуются для построения оптимальной цепочки.
20


2. МЕТОДЫ РЕШЕНИЯ

2.1. Построение оптимальной цепочки с использованием сетевых
методов

Задача, описанная в разделе 1.2 относится к классу задач поиска
экстремальных путей на графах. Однако, специфический вид критерия
T (µ)
? ?t затрудняет применение известных алгоритмов[3].
F=L(µ)-
t =1
Заметим, что если ?t=? для всех t, то

T (µ)
? ? = ? ? T ( µ ) = ? ? ? ij ,
k =1 ( ij )?µ
и задача сводится к определению пути максимальной длины при длинах

? принимает значения ?(k) на (T k-1,Tk ],
дуг , равных (lij-??ij). Пусть

T0= 0 , k=1?s.
Рассмотрим случай, когда ?( 1) > ?( 2) > ... > ?(s). Пусть далее

T(µ) ? ( T k-1, T k ] . Тогда целевую функцию (7) можно представить в
виде
k ?1
? ( ? ( i ) ? ? ( i + 1))Ti
(16) F(µ)=L(µ)? ? ( k ) ? T ( µ ) ?
i =1

Пусть µk - путь максимальной длины при длинах дуг, равных (lij -
?(k) ?ij) и М= U µ k
k
21


Теорема. Оптимальный путь исходной задачи µ0 существует
среди путей множества М.
Доказательство.
Предположим противное, то есть, что T(µ0)?(T T k) и в то же
k-1,

время, L(µ0) - ?(к) T(µ0) < L(µk) -?(k) T(µk). Если T(µk) ?(T k-1, T k],

то путь µk лучше, чем µ , что противоречит оптимальности µ0.

ПустьT(µk) ? (Tq-1, Tq], где q > k. В этом случае имеем T(µk) > Ti , i

k ?1
? ( ? ( i ) ? ? ( i + 1)) ? Ti <L(µk)-
= k ? -1 и F(µ0)=L(µ0)-?(k)?T(µ0)-
1
k ?1
? ( ? i ? ? i +1 ) ? Ti =L(µk)-?(q)?T(µk)-
- ?(k)?T(µk)-
1
q ?1 k ?1
? ( ? i ? ? i +1 ) ? T ( µ k ) - ? ( ? i ? ? i +1 ) ? Ti <L(µk)-
-
k 1
q ?1
? ( ? i ? ? i +1 ) ? Ti =F(µk) (17)
- ?(q)?T(µk)-
1
Таким образом, мы нашли путь µk лучший, чем путь µ0, что

противоречит оптимальности µ0.

Tq], где q<k. В этом случае имеем
Пусть теперь T(µk)?(T q-1,

T(µk)?Ti и F(µ0)=L(µ0)-?(k)?T(µ0)-
k ?1
? ( ? ( i ) ? ? ( i + 1)) ? Ti <L(µk)-?(k)?T(µk)-
-
1
22


q ?1
k ?1
? ( ? ( i ) ? ? ( i + 1)) ? Ti - ? ( ? ( i ) ? ? ( i + 1)) ? Ti ?L(µk)-
-
q 1

q ?1
? ( ? ( i ) ? ? ( i + 1)) ? Ti =F(µk) (18)
- ?(q)T(µk) -
1
и также получаем противоречие. Теорема доказана.

Теорема утверждает, что оптимальный путь µ0 существует среди

путей µk , причем таких, для которых T(µk)?(Tk-1, Tk].

Опишем алгоритм решения .

1. Определяем оптимальный путь µ1 при ?=?(1). Переходим к
следующему шагу.

2. Если T(µ1)?[0,T1) , то определяем путь µ2 . Если T(µ1)?(Tк-1,

Tк] , где к > 1, то определяем путь µк. Переходим к следующему шагу.
3. Если T(µ к)?(Tк-1, Tк], то определяем путь µк+1. Если T(µ

Tq], где q > k, то определяем µq. Переходим к следующему
к)?(Tq-1,

шагу.

В силу конечности числа отрезков описанный алгоритм за
конечное число шагов позволяет определить все пути µk , такие что T(µ

Tк] . Среди этих путей определяем оптимальный по критерию
к)?(Tк-1,

(16).
Для обоснования алгоритма достаточно показать, что описанная
процедура позволяет получить все пути µk ,удовлетворяющие условию

Tk-1 < T(µk) ? Tk.. Для этого достаточно доказать, что если Tq-1 < T(µk)
23


? Tq , где q > k, то для всех k < j < q T(µj) > Tq-1 . Это следует из
того, что T(µk) являются неубывающими функциями к, то есть T( µ1) ?

T(µ2) ? ... ? T(µs). Поэтому , T(µj) ? T(µk) ? Tq-1. Следовательно,
оптимальное решение не может быть среди путей µj , таких , что k < j <

q.
Если условие убывания ?(k) с ростом k не выполняется, то
теорема уже не имеет места. В этом случае для решения задачи
необходимо развернуть сеть во времени [3 ].При этом, одному и тому
же предприятию, выпускающему продукцию в различные моменты
времени, будут соответствовать различные вершины. Дугу в такой сети
будем обозначать [i(ti),j(tj)], где i(ti) означает, что предприятие i

завершает выпуск продукции в момент времени ti. Длина дуги [i(ti),j(tj)
] определяется выражением
tj
? ? t , где ? t=?(k) при t?[Tk-1, Tk)
= lij ?
(19) li( t ) j ( t )
i j
t = t i +1


Пример.
Сеть возможных технологических цепочек приведена на рис. 2.
Числа в скобках у дуг соответствуют длинам lij (первое число) и

времени движения по дуге ?ij (второе число). Значения Тk и ?(k)
приведены в таблице 1.
24


k 1 2 3
?
Tk 6 10
? 0,5 0,4 0,3

табл. 1


Шаг 1. Берем ?(1)=0.5 и полагаем длины дуг равными lij?= lij-

0.5?ij . Соответствующая сеть приведена на рисунке 3. Длины дуг
указаны в скобках у соответствующих дуг, выделенными дугами

<< Предыдущая

стр. 3
(из 7 стр.)

ОГЛАВЛЕНИЕ

Следующая >>