Составители:
Рубрика:
158
Наконец, форма цикла может быть различной. На рис. 4.2 представленный цикл
пересчета для клетки A
2
B
1
имеет форму четырехугольника. В других случиях цикл
пересчета может быть в виде многоугольника различной конфигурации.
Вершины, в которых поставки при перераспределении увеличиваются (на рис. 4.1
– вершины A
2
B
1
и A
4
B
2
), отмечаются плюсом и называются положительными вершинами
И, наоборот, вершины, в которых поставки при перераспределении уменьшаются ( на рис.
4.1 - A
2
B
2
и A
4
B
1
) отмечаются минусом и называются отрицательными вершинами. В
цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке,
для которой определяется
∆
ij
. В нее записывают знак плюс, затем знаки по вершинам
чередуются: минус, плюс , минус, плюс и т. д., независимо от того, расставляют ли их по
часовой стрелке или в обратном направлении. Таким образом, в цикле всегда
насчитывается одинаковое число положительных и отрицательных вершин.
Поскольку конечная цель составления циклов пересчета заключается в
определении оценок
∆
ij
свободных клеток, условимся по вершинам цикла пересчета
записывать соответствующие клеткам показатели критерия оптимальности с
ij
с
присвоенным вершине знаком. И еще одна условность. Вершины, лежащие в базисных
клетках, будем отмечать квадратами, а вершину, лежащую в свободной клетке, без
квадрата. Тогда для клетки A
2
B
1
цикл пересчета можно представить в форме
четырехугольника, показанного на рис.4.3.
Теперь можем определить оценку этой свободной клетки A
2
B
1
. Поскольку оценка
∆
ij
этой и любой другой свободной клетки должна характеризовать изменения суммарных
затрат на поставку (в расчете на единицу перераспределяемой продукции), ее можно
вычислить как алгебраическую сумму стоимостей поставок, расставленных по вершинам
замкнутого цикла пересчета, т.е.
∑
=∆ .
ijij
c
(4.8)
Так, для свободной клетки A
2
B
1
оценка
∆
21
будет равна:
∆
21
=+3-4+2-1=0
Поясним, что записав поставку, равную 1м
3
, в клетку A
2
B
1
(см.рис.4.1), мы
увеличили значение целевой функции на 3 (с
21
=3). Уменьшив на 1 м
3
поставку A
2
B
2
, мы
тем самым уменьшили значение целевой функции на 4 (с
22
=4); увеличив поставку в
клетке A
4
B
2
, мы увеличили целевую функцию на 2, и, наконец, уменьшив поставку в
клетке A
4
B
1
, мы уменьшили целевую функцию на 1. Те же числа фигурируют в вершинах
цикла на рис. 4.3.
Поскольку оценка свободной клетки A
2
B
1
оказалась равной нулю, занятие ее
поставкой не отразится на величине целевой функции (4.7). Далее построим циклы
пересчета (рис.4.4) и по ним вычислим значение оценок
∆
ij
для всех остальных свободных
клеток табл.4.4.
Проведенные расчеты оценок свободных клеток показывают, что исходный
опорный план, представленный в табл. 4.4, является неоптимальным решением задачи,
так как оценка свободной клетки A
3
B
1
оказалась равной – 2, что свидетельствует о
возможности снижения значения целевой функции (4.7) на 2 руб. в расчете на каждый
перераспределенный кубометр продукции.
Следующий этап решения транспортной задачи заключается в улучшении опорного
плана.
Переход от неоптимального опорного плана к лучшему.
Поскольку в исходном
опорном плане рассматриваемой задачи только одна свободная клетка A
3
B
1
имеет
отрицательную оценку, то для получения плана, обеспечивающего меньшее значение
Страницы
- « первая
- ‹ предыдущая
- …
- 156
- 157
- 158
- 159
- 160
- …
- следующая ›
- последняя »
