Составители:
Рубрика:
173
отражает экономическую сущность алгоритма. Это будет видно из дальнейшего
изложения.
В этой главе нами будет рассмотрена сущность алгоритма метода
дифференциальных рент, который является наиболее оригинальным и удачным для
решения малых и крупных задач транспортного типа задач, приводимых к типу таковых.
Сущность алгоритма метода дифференциальных рент
Ранее были рассмотрены распределительный метод и его модификация - метод
потенциалов. Особенность этих методов заключалась в том, что сначала определялся
некоторый опорный план, какое-то неотрицательное решение задачи, а затем шаг за
шагом план улучшался до тех пор, пока не становился оптимальным.
Метод разрешающих слагаемых, дифференциальных рент, венгерский и
некоторые другие основаны на противоположном принципе; в них план с самого начала
соответствует критерию оптимальности, но должен проверяться на допустимость.
Если план оказывается недопустимым, т.е. если сумма поставок оказывается меньше (а
иногда и больше) мощностей поставщиков (или спросов потребителей), а так именно и
бывает на первой и промежуточных итерациях, то постепенно, шаг за шагом план
доводится до допустимого. Как только это достигается, решение считается
законченным и полученный план оказывается оптимальным.
Таким образом, до самого конца решения план, удовлетворяя критерию
оптимальности, не является допустимым - он является условно оптимальным. Поэтому
все методы, относящиеся к этой группе, называются методами условно оптимальных
планов.
Основная идея метода дифференциальных рент заключается в том, что
первоначально в каждом столбце отмечаются кружками или ( как в данном случае)
полужирным курсивом минимальные показатели с
ij
и в клетки с выделенными
минимальными стоимостями записываются величины поставок х
ij
. Если вся продукция
окажется распределенной и спрос потребителей удовлетворен полностью, это
означает, что получен оптимальный план. Если это условие не выполняется, начинается
итеративный процесс, в ходе которого матрица
ij
cC = изменяется особым образом и
процесс распределения поставок повторяется, но уже в соответствии с новой матрицей
стоимости поставок. При этом общее количество распределенной продукции
∑∑
= =
m
i
n
j
ij
x
1 1
при переходе от одной итерации к другой постепенно увеличивается.
Если на какой-то итерации оказывается распределенной вся продукция, то на
этом процесс заканчивается и при правильном выполнении его последний план будет
оптимальным.
Рассмотрим сущность метода дифференциальных рент на небольшом числовом
примере.
Предположим, что имеются поставщики А
1
, А
2
, А
3
какого-то конкретного
сортимента лесоматериалов, потребителями которого являются
деревообрабатывающие предприятия B
1
, B
2
, B
3
.
В условии задачи известны: количества лесоматериалов (тыс.м
3
), предназначенных
к реализации (поставке) от каждого из поставщиков а
i
, потребности (спрос) в них по
деревообрабатывающим предприятиям b
j
, а также себестоимость производства и доставки
Страницы
- « первая
- ‹ предыдущая
- …
- 171
- 172
- 173
- 174
- 175
- …
- следующая ›
- последняя »
