Составители:
Рубрика:
156
А
2
250
180 70
А
3
230
100 130
А
4
220
200
20
Кроме того, этот опорный план считается невырожденным, т.к. число
положительных поставок х
ij
>0 равно рангу r=m+n-1 системы ограничительных уравнений
(4.2), (4.3). В данном примере r=4+4-1=7 и число базисных клеток – клеток, заполненных
числами х
ij
>0, также равно 7.
Следующий этап решения транспортной задачи заключается в проверке
полученного исходного опорного плана на оптимальность.
Проверка опорного плана на оптимальность. Чтобы установить является ли
опорный план оптимальным, надо проверить, как повлияет на величину целевой функции
(4.7) любое возможное перераспределение поставок, удовлетворяющее ограничительным
условиям (4.2), (4.3), (4.4).
План распределения поставок будет оптимальным лишь в том случае, когда
целевая функция (4.1) имеет минимальное значение, т.е. когда дальнейшее уменьшение
затрат на поставку будет невозможно.
Проверим возможность уменьшения суммарных затрат на поставку продукции. С
этой целью для каждой свободной от поставки клетки определяется величина ∆
ij
,
характеризующая изменение суммарных затрат на поставку (в расчете на единицу
перераспределяемой продукции), при условии включения в план единичной поставки х
ij
=1
от поставщика А
i
к потребителю В
j
. При этом должно быть произведено такое изменение
остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса
спроса и поставок транспортной задачи, т.е. удовлетворяла ограничительным условиям
(4.2), (4.3), (4.4).
Величину ∆
ij
в дальнейшем будем называть оценкой свободной клетки (некоторые
авторы называют характеристикой).
В нашем примере, в исходном решении задачи (см.табл.4.4) клетки А
1
В
1
, А
1
В
2
,
А
1
В
1
, А
2
В
1
, А
2
В
3
, А
3
В
1
, А
3
В
2
, А
4
В
3
и А
4
В
4
оказались свободными от поставок.
Необходимо вычислить значение оценок ∆
ij
для этих свободных от поставок
клеток. С этой целью для каждой свободной клетки составляется означенный цикл
перерасчета (в литературе иногда называют его замкнутой цепью, кругом, кольцом,
контуром и т.д.).
Рассмотрим сначала наиболее простые формы циклов (цепей) приминительно к
нашему примеру.
Вычислим оценку ∆
21
для свободной клетки А
2
В
1
при условии включения в план
единичной поставки х
21
=1.
Поставщик и их
мощности
Потребители и их спрос
В
1
В
2
200 200
А
2
250
+1 180-1
А
4
220 200-1 20+1
3
4
1 2
3
4
5 4
2
5
6
5
1 2
3 6
Страницы
- « первая
- ‹ предыдущая
- …
- 154
- 155
- 156
- 157
- 158
- …
- следующая ›
- последняя »
