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

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

ОГЛАВЛЕНИЕ

Следующая >>

обозначен путь максимальной длины


µ1= [ 0, 1, 4, 6]. При этом, F(µ1)=3, T(µ1)=12. Так как T(µ1)?(10,?),
то переходим к шагу 2.
Шаг 2. Берем ?(3)=0.3 и полагаем длины дуг равными lij?= lij-

0.3 ?ij. Соответствующая сеть приведена на рис.4. Имеем µ3=[ 0, 1, 3, 6]
, T(µ3) = 16. T(µ3)?(10,?). Поэтому путь µ3 определяет оптимальное

решение. При этом по формуле (16)F(µ3)= l?01 + l?13+ l?36- (?(1)-

?(2)) T1 - (?(2)-?(3)) T2=-2.9 -2.5 + 10.6 - 0.6 - 1 = 3.6




(5;1) 1 (-1;5) 3


(13;5)
0 (-4;2) (-4;2) 4 6
2
25


(7;2) 5 рис.2
?=0.5


4.5
-3.5

3

11.5
46
0 -5 -5
2
65
рис.3




?=0.3


4.7
-2.5
13


11.5 6
0 -4.6 -4.6 4
2


6.4 5 рис.4
26


На рисунке 5 приведена развернутая во времени сеть для
вышеописанного примера. Путь максимальной длины в этой сети
определяет оптимальное решение задачи для любых
последовательностей {?t}. Оптимальный путь для {?t} из таблицы 1
выделен утолщенными дугами, Очевидно, что он определяет то же
оптимальное решение, которое было получено выше, то есть путь µ=[

0,1,3,6].


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
61

3 10.4 6

11.2 6
64
0 6



2 -5 4 рис. 5
-9.2 5



2.2 Построение оптимальной цепочки с использованием методов
динамического программирования.

Алгоритм построения оптимальной цепочки в условиях
поэтапного кредитования при наличии ограничений на
производственные мощности предприятий с использованием
методологии динамического программирования имеет следующий вид:
27


Шаг 1. Построим множество P1, как множество вершин графа,
связанных с R по исходящим дугам. Каждой вершине i?P1 припишем
два значения:

?iR
(20) g(i) = ci - wi (1+?)


?(i) =.?iR
(21)

Величина g(i) равна доходу от продажи единицы продукции i-го
предприятия на рынке минус затраты на его производство с учетом

процента на кредит. Величина?iR промежуток времени от
-

производства единицы продукции на предприятии i до ее реализации на
рынке R.
Шаг 2. Строим множество P2 всех вершин графа, связанных с P1
исходящими дугами: P2 = {i: ? (i,j), j? P1}.

Если из вершины i исходит более одной дуги, т.е. ? (i,j1), ..., (i,jk)

? P1, то представляем вершину i в виде k вершин i1, ...,ik так, чтобы из
каждой вершины исходила ровно одна дуга (il,jl).


j1 i1 j1
i
j2 i2 j2
рис.6
Далее, каждой вершине i?P2 с исходящей из неё дугой (i,j)
припишем пару значений:
28


?ij+?1(j)
(22) g(i) = kj ? g(j) -wi ? (1+?)


?(i) =?ij + ? (j).
(23) l


Шаг повторяется для множеств Алгоритм
2 P3, P4, ...
заканчивается, когда на m-ом шаге в множестве Pm не окажется ни
одной вершины, у которой не существует вхоящей дуги, т.е. множество
Pm+1 построить будет нельзя.
На модифицированном графе, полученном в результате
выполнения алгоритма, выделим вершины, не имеющие входящих дуг,
и назовем их “исходными”. Такие вершины могут принадлежать
любому из множеств P1, P2, ... , Pm. Обозначим множество исходных
вершин через I. Тогда оптимальная с точки зрения максимального
удельного дохода “технологическая цепочка” выбирается из условия:
(24) i1 = arg {max g(i) }.

Вершина i1 является исходной в оптимальной цепочке. Поскольку
каждая вершина на модифицированном графе имеет ровно одну
исходящую дугу, и в соответствии с шагом 1 алгоритма все цепочки
заканчиваются в вершине R, то, зная исходную вершину, всю цепочку
можно построить однозначно.
Существуют очевидные способы усовершенствования приведенного
выше алгоритма. Так, если для некоторой вершины i g(i) < 0, эту
вершину можно отбросить и далее не рассматривать. Среди всех
вершин i ? Pk можно отобрать только Парето-оптимальные, а
остальные исключить из дальнейшего рассмотрения. А именно, если
для некоторой вершины i ? Pk найдётся вершина j ? Pk такая, что g(i)
29



?(i) ?(j),
< g(j) и то вершину i можно исключить из
>
модифицированного графа.
После того, как оптимальная цепочка построена, можно
вычислить прибыль от её функционирования. Используя предельные
пропускные способности входящих в неё вершин, можно вычислить
максимальный поток по этой цепочке. Итак, пусть оптимальная цепочка
{i1, i2,...,im}.
Шаг 0. Примем f (i1, i2) = ai1 , j = 2.

Шаг 1. f (ij, ij+1) = kij ? f (ij-1 , ij) .

Шаг 2. Если f (ij, ij+1) ? aij , то j = j+1, перейти к шагу 1.

Шаг 3. Если f (ij, ij+1) < aij , то принять f (ij, ij+1) = aij , j= j+1,

перейти к шагу 1.Выполнять до тех пор, пока j ? m.

Если в течение всего алгоритма шаг 3 не исполнялся ни разу, то
оптимальный поток f (i1,i2),...,f (im-1,im) построен.

Если шаг 3 выполнялся хотя бы один раз и последний раз для j =

n, то следует пройти по цепочке, начиная с f(in,in+1), в обратном
порядке, пропорционально уменьшая потоки:


(25) Ошибка! Объект не может быть создан из кодов полей
редактирования.
_______


Суммарный доход от такой цепочки составляет f(i1,i2) ? g(i1).
Пример.
30


Исходный граф приведен на рис. 7. Числа в скобках над
вершинами - затраты на производство единицы продукции в вершине i.
Числа в скобках у дуг - стоимость единицы продукции (первое число) и
время прохождения дуги (второе число). Заметим, что положительные
значения стоимости потока только на дугах, входящих в вершину 6
(рынок). Это следует из условия, что фирма-организатор получает
доход только после реализации продукции на рынке. На остальных
дугах стоимости единицы потока нулевые.
Построим множества P1,...,Pm. На рисунке 8 над каждой

вершиной указана пара чисел (g(i);?(i)), вычисленных соответственно

по формулам (22) и (23).
Заметим, что если на каком-то шаге для i-й вершины получается
g(i) ? 0, дальнейший путь из этой вершины не строится.
Максимальный удельный доход g(i)=1.2 получен на цепочке (0,2,5,6).
Следовательно, в показанном примере эта цепочка является
оптимальной.

(5;1)

[3] [4]

1 (0;5) 3

[2] [7]
0 [4] 4 (13;5) 6

2 (0;1) [8]
5
(7;2) рис.7
31




(0.9;1)
0
(-1.4;4) (1.85;1)
01
(0.16;4) (2.59;1)
02
(-0.5;16) (1.4;13) (7.1;8) 6
013
(-2.6;12) (0.6;9) (4.1;9)
014
(-1.6;7) (8.8;3)
(1.2;6) 2 (2.2;10) 5
0 2 рис.8
.




3.ТЕОРЕТИКО-ИГРОВОЙ АНАЛИЗ МЕХАНИЗМОВ ОБМЕНА.

В рассмотренной задаче выбора оптимальной технологической
цепочки необходима информация о технологических коэффициентах kij

?ij и
, продолжительностях производственного цикла рисках rij. Эту

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

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

ОГЛАВЛЕНИЕ

Следующая >>