|
108 Таким образом, мы построили сетевую модель, которая содержит все рациональные варианты закупок продукции. Каждому такому варианту соответствует путь в сети, соединяющий вход с выходом. Затраты на оплату продукции и хранение ее на складе равны длине соответствующего пути. Задача свелась к определению пути минимальной длины. Алгоритмы определения экстремальных путей в графах (то есть путей максимальной или минимальной длины) достаточно хорошо известны и описаны в литературе [1]. Для нашего случая наиболее эффективен алгоритм определения кратчайших путей при правильной нумерации вершин сети. Напомним, что нумерация вершин называется правильной, если для любой дуги (i, j) имеет место i < j. В этом случае кратчайший путь определяется на основе последовательного присвоения вершинам сети индексов q, согласно следующей процедуре (индекс вершины 1 принимается равным 0); qj =min jдлина дуги (j, i). В этом случае индекс последней вершины qm+i будет равен длине кратчайшего пути или величине минимальных затрат. Путь минимальной длины определяется на основе процедуры «обратного хода». Опишем эту процедуру. Находим вершину ii, такую что Ч т + 1 = 4 i + S i,,m + 1 • Если i[ I, то находим вершину i2, такую что Продолжаем таким образом, пока на очередном шаге к не получим ik = 1, то есть =Ч+Чч-,Путь ц = (I, ik-i, ik-2»— >ii^ m+1) и является путем минимальной длины. Применим этот алгоритм к сети, рис. 5.6. Индексы вершин указаны в нижней половине соответствующего кружка. Имеем: qi = 0; |
89 получаем, что длина дуги (42, 6) равна 100 + 4 48 = 56 тыс. руб,Дуге (5, 6) соответствуют две рациональные операции закупки. Первая закупить 4 ед. продукции по цене 5 тыс. руб. Затраты при этом составят 20 тыс. руб. Вторая закупить 25 ед. продукции по льготной цене. Затраты с учетом дохода от 21 ед. избыточной продукции составят 25-4 21-3 = 37 тыс. руб. Выберем вариант с меньшими затратами. Длина дуги (5, 6) равна 20. Длины всех дуг указаны на рис. 2.2.7 у соответствующих дуг в скобках. Таким образом, мы построили сетевую модель, которая содержит все рациональные варианты закупок продукции. Каждому такому варианту соответствует путь в сети, соединяющий вход с выходом. Затраты на оплату продукции и хранение ее на складе равны длине соответствующего пути. Задача свелась к определению пути минимальной длины. Алгоритмы определения экстремальных путей в графах (то есть путей максимальной или минимальной длины) достаточно хорошо известны и описаны в литературе [114]. Для нашего случая наиболее эффективен алгоритм определения кратчайших путей при правильной нумерации вершин сети. Напомним, что нумерация вершин называется правильной, если для любой дуги (i, j) имеет место i < j. В этом случае кратчайший путь определяется на основе последовательного присвоения вершинам сети индексов q, согласно следующей процедуре (индекс вершины 1принимается равным 0): где Sji длина дуги (j, i). В этом случае индекс последней вершины qnl( будет равен длине кратчайшего пути или величине минимальных затрат. Путь минимальной длины определяется на основе процедуры “обратного хода”. Опишем эту процедуру. Находим вершину i,, такую что Чш+1 = 4ij + sij,m+l • Если i, * 1, то находим вершину i2, такую что = ч;, + si2>i. 89 |