Составители:
Рубрика:
172
равной нулю. Значит, имеется еще вариант оптимального плана этой задачи. Найти его и
проверить на оптимальность предлагается читателю в качестве небольшого упражнения.
Вычислим значения целевых функций F и G.
F=4
⋅
100+2
⋅
90+4
⋅
20+4
⋅
150+4
⋅
30+3
⋅
160+3
⋅
100=2160,
G=190
⋅
(—2)+200
⋅
(0)+160
⋅
(-1)+100
⋅
(—3)+
+180
⋅
4+200
⋅
6+150
⋅
4+120
⋅
4=2160.
Как и следовало ожидать, значения целевых функций одинаковы, т. е. F=G. Это
еще раз подтверждает оптимальность плана. Общие затраты на поставку продукции по
этому оптимальному плану составят минимальную величину, равную 2160 тыс. руб.
На этом можно было бы закончить рассмотрение сущности алгоритма метода
потенциалов, если бы не один вопрос, который нами еще не рассмотрен.
Читатель уяснил сущность, а также общность и различия, рассмотренных выше
двух математических методов — метода потенциалов и распределительного. Эти методы
различаются друг от друга способом оценки плана на оптимальность. В этой связи
возникает вопрос: есть ли какая-нибудь зависимость между показателями оценки
свободных клеток, вычисленной по циклу пересчета, и характеристикой ее, рассчитанной
по потенциалам задачи? Такая зависимость есть, так как если для какой-либо свободной
клетки рассчитать оценку ее, а затем характеристику, то значения их непременно
совпадут.
В качестве примера рассмотрим свободную клетку А
2
В
2
из плана табл. 4.11. Оценка
этой свободной клетки, вычисленная по циклу пересчета, равна единице.
Этот расчет формульной записи может быть представлен так:
∆
22
=(c
22
+c
14
)-(c
12
+ c
24
) (4.25)
Характеристика этой же свободной клетки, вычисленная по потенциалам задачи и формуле
∆
22
=c
22
-(u
2
+ v
2
) (4.26)
равна также единице.
Из соотношений (4.20), (4.21) получим значения
с
14
=u
1
+ v
1
, c
12
=u
1
+ v
2
и c
24
=u
2
+ v
4
. (4.27)
Далее подставим значения (5.27) в (5.25) и получим
∆
22
=(c
22
+u
1
+ v
4
)- (u
1
+ v
2
+ u
2
+ v
4
).
Раскроем скобки и приведем подобные члены. В результате получим
∆
22
=c
22
-(u
2
+ v
2
),
что равно характеристике (4.26).
Аналогичное соотношение можно дать и для всех других свободных клеток при
любой форме цикла.
4.3. Метод дифференциальных рент
Этот метод создан советскими учеными. В конце 50-х годов А.Л.Лурье на основе
общих идей линейного программирования, сформулированных Л.В.Канторовичем,
разработал метод решения транспортных задач, который назвал методом разрешающих
слагаемых. Затем А.Л. Брудно, используя основные идеи метода А.Л.Лурье, разработал
оригинальный алгоритм - алгоритм дифференциальных рент - и реализовал его в
машинной программе. В дальнейшем самими же авторами были предложены и другие
названия этих методов (первый называли - методом приближения условно-оптимальными
планами, второй - алгоритмом вычеркивающей нумерации). Однако в литературе уже
утвердились старые названия, к тому же термин дифференциальных рент удачно
Страницы
- « первая
- ‹ предыдущая
- …
- 170
- 171
- 172
- 173
- 174
- …
- следующая ›
- последняя »
