Метод аппроксимации (метод Фогеля).

Суть метода аппроксимации заключается в том, что на каждом шаге выбор очередной клетки, заполняемой ресурсом, осуществ­ляется не на основе строго локальных оценок стоимостей Су, как в методе минимального элемента, а на основе расчетов так назы­ваемых штрафов¹, позволяющих приближенно оценивать полез­ность данного шага с точки зрения скорейшего приближения к оптимальному решению с учетом состояния таблицы на следую­щем шаге.

'Таха X. Введение в исследование операций. Кн. 1. — М.: Мир, 1985. — С. 216.

Схема метода аппроксимации для случая минимизации целевой функции такова.

1. По каждой строке и столбцу находят два минимальных зна­чения Су.

2. Определяют их разности (штрафы) ц, -, /= 1,..., т (для строк) и ц_/; }= I,..., п (для столбцов).

3. Из всех разностей выбирают наибольшую ц_тах.

4. По строке (или столбцу), к которой относится ц_тах, в клет­ку, где размещается наименьшее значение Су, записывают значе­ние ху, равное наименьшей из соответствующих величин А-, и В_у

5. Определяют новые значения указанных величин А₁ и В/.

А\=А/ - Ху\ 2»у= В^ - ху.

6. Если Л/=0 и 2? у> 0, то из таблицы вычеркивают соответству­
ющую строку и далее с этой строкой не работают. Если
Д-> 0 и -8/=0, то вычеркивают соответствующий столбец. Если обе

величины А- и #у равны нулю, то вычеркивают только (!) строку или только столбец (но неодновременно столбец и строку). С ос­тавшимся столбцом (строкой), имеющим нулевое значение

В)(А1), далее работают, как с нормальным столбцом (строкой).

7. Далее операции повторяются до тех пор, пока в таблице все
строки, кроме одной (или все столбцы, кроме одного), не ока­
жутся вычеркнутыми. Оставшиеся ресурсы АЦВ'^) заносят в со­
ответствующие клетки последней невычеркнутой строки (после­
днего невычеркнутого столбца). Полученное решение проверяют
так же, как и при использовании метода минимального элемента.

При решении задач на максимум приведенный алгоритм ме­няется только в двух пунктах: в п. 1 вместо минимальных нахо­дят два максимальных значения Су, а в п. 4 заполняют клетку не с наименьшим, а с наибольшим значением Су.

При реализации приведенного алгоритма возможны некоторые осложнения (напоминаем, что мы рассматриваем случай миними­зации целевой функции). Например, в п. 3 не одна, а несколько неличин |Я/ и цу могут иметь одинаковое наибольшее значение. В этом случае в качестве дальнейшей расчетной можно выбрать лю­бую из них, однако опорное решение можно улучшить (прибли­зить к оптимальному), если в качестве дальнейшей взять ту из ве­личин Ц./ или Цр для которой в соответствующих строках и столб­цах находится наименьшее значение Су. Если при этом наимень­шее значение достигается несколькими Су, то для решения берут ту клетку, которую можно заполнить наибольшим значением ху.

Как уже отмечалось, в случае, когда 4'=0и6у=0, можно вы­черкнуть либо /-ю строку, либоу'-й столбец. Для того чтобы при­близить опорное решение к оптимальному, целесообразно со-

1л>

4^

87. Нахождение опорного решения задачи 15.5 методом аппроксимации*

© 0 © ®

* Числа в кружках указывают последовательность вычеркивания столбцов и строк. Значения базисных переменных опор­ного решения выделены полужирным шрифтом. Звездочкой помечены максимальные на данном шаге значения ц.

блюдать следующее правило: в /-и строке, исключая вычеркнутые и занятые клетки, а также рассматриваемую (/, у)-ю клетку, опре­деляем наименьшее значение Су (обозначим его Су); в у'-м стол­бце, исключая вычеркнутые и занятые клетки, а также рассмат­риваемую (/, у)-ю клетку, определяем наименьшее значение Су

(обозначим его Су); если Су < С[[, то вычеркиваем у-й столбец, в противном случае — /-ю строку.

Если в ходе применения приведенного алгоритма на каких-либо шагах окажется, что одновременно Д'=0и5у=0, опорное решение будет вырожденным — некоторые клетки будут условно занятыми. Как правило, вырожденное решение может появить­ся, если выполняются какие-либо из равенств А_{ = В_х; А\ = В₂; А_х = В_х + В₂; А₁+А₂ = В₁ + В₂и т. п.

Необходимо подчеркнуть, что при использовании рассмотрен­ного алгоритма (так же, как и алгоритма метода минимального элемента) наличие вырожденных решений не усложняет как полу­чение опорного решения, так и улучшение его до оптимального. Никакие специальные приемы в операциях с вырожденными ре­шениями не требуются. С условно занятыми клетками (занятыми нулями) необходимо работать, как с обычными занятыми.

Определение опорного решения методом аппроксимации удобно проводить в таблице специального вида (табл. 87).

Заметим, что опорное решение, полученное методом аппрок­симации, не совпадает с решением, полученным методом мини­мального элемента. Значение целевой функции (2- 5730 руб.) в первом случае меньше, то есть данное решение ближе к опти­мальному.

15.3. МЕТОД ПОТЕНЦИАЛОВ

Основные понятия.

Опорное решение, полученное любым из известных методов, как правило, не является оптимальным. Поэтому алгоритмы оп­тимизации основаны на его последовательном улучшении. Прежде чем изложить строго формализованный метод такого улучшения, рассмотрим циклическую процедуру преобразования любого (в том числе опорного) решения транспортной задачи. Суть ее заключается в перемещении части транспортируемого ресурса внутри некоторой замкнутой последовательности клеток (цикла), причем в каждом цикле одна клетка свободна, а осталь­ные заняты. Тем самым происходит замена одного базисного ре­шения другим.

Замкнутый цикл (многоугольник) строится по следующим правилам:

стороны многоугольника должны располагаться только вдоль строк и столбцов матрицы, то есть пересекаться только под пря­мыми углами;

вершины многоугольника должны находиться в занятых клет­ках, кроме одной начальной, лежащей в выбранной свободной {испытуемой) клетке;

пересечение несмежных сторон многоугольника вершиной не считается;

начальной вершине приписывается знак «+», далее знаки че­редуются.

В теории линейного программирования доказывается, что при выполнении указанных правил для любой свободной клетки можно построить единственный цикл. Два примера построения циклов для свободных клеток (3, 5) и (2, 5) показаны в таблицах 88 и 89, где размещено опорное решение задачи 15.5, полученное методом минимального элемента.

88. Цикл испытуемой клетки (3, 5)

89. Цикл испытуемой клетки (2, 5)

Преобразование решения осуществляется следующим обра­зом (см., например, табл. 88). Среди клеток, помеченных знаком «—», находят клетку с наименьшим ресурсом (обозначим его х_тт) и далее последовательно в клетках, помеченных знаком «+», ре­сурс увеличивают на х_т1п, а в помеченных знаком «-» —умень­шают на х_т[п. Очевидно, что при этом, как минимум, в одной из

клеток ресурс уменьшится до нуля и в испытуемой клетке (/, /) появится ресурс ху = х_т1п, то есть переменная ху будет введена в базис. При таком изменении решения значение целевой функ­ции может уменьшиться (то есть достигается улучшение решения задачи на минимизацию) или увеличиться (то есть решение ухуд­шится). Чтобы выяснить, как изменится решение, вычисляют так называемую оценку испытуемой клетки (такую оценку иногда называют ценой цикла, или характеристикой клетки):

(+) (-) ^(П-^

где (+) и (—) относятся к клеткам, помеченным знаками «+» и «—» соответственно.

В силу единственности цикла для каждой испытуемой клетки оценку оу действительно можно рассматривать как характеристи­ку именно этой клетки (а не конкретного цикла). Эта величина показывает, как изменится стоимость транспортировки ресурса в случае перемещения по циклу единицы ресурса. Полное измене­ние стоимости транспортировки ресурса (то есть изменение зна­чения целевой функции) задается величиной

Л^=ХтнАу- (15.7)

На этой формуле основан также один из видов контроля зна­чений целевой функции промежуточных решений транспортной задачи: 2'= 2₀ + А2 или 2^/=ЪСуХу, где 2, '— значение целевой функции улучшенного плана, 2! ₀ — значение целевой функции предыдущего плана. Значения Т, вычисленные по двум разным формулам, должны совпадать.

Таким образом, в задачах на минимизацию положительное чначение ау означает, что соответствующее преобразование ре­шения невыгодно, а отрицательное — что оно выгодно.

Нетрудно видеть, что оценки а у незанятых клеток (соответ­ствующие переменные ху не входят в базис) играют роль элемен­тов индексной строки в симплекс-методе. По их знакам можно установить, достигнуто оптимальное решение или нет.

Для примеров циклов, приведенных в таблицах 88 и 89, оцен­ки свободных клеток составляют:

а₃₅ = С₃₅ + С, ₃ - С₁₅ - С₃₃ = -45 < 0;

°" 25 = С₂5 + С\Ъ + ^С31 - С*15 - С₃3 ~ С₂1 = -5 < 0.

Таким образом, преобразование решения с помощью обоих циклов выгодно.

Рассмотренные особенности циклического преобразования решений транспортной задачи и лежат в основе распределитель-

ного метода. Суть его заключается в построении на каждом шаге циклов для всех свободных клеток, вычислении оценок а, _у, выбо­ре одной из клеток с отрицательной оценкой (для задач на мини­мизацию) и преобразовании решения. Этот процесс повторяется до тех пор, пока оценки всех свободных клеток не станут неотри­цательными.

Распределительный метод — весьма трудоемкая процедура, поскольку требует построения циклов для всех свободных клеток. Существенно меньше вычислений требует метод потенциалов, позволяющий в результате небольшого числа операций сразу (без построения циклов) определить оценки свободных клеток. Пол­ное обоснование этого метода потенциалов может быть получено в рамках общего метода решения задач линейного программиро­вания — симплекс-метода и теории двойственности таких задач. Мы воспользуемся более простой, но также достаточно строгой схемой (Вентцель Е. С. Исследование операций. — М.: «Советс­кое радио», 1972. — С. 99), хотя и опустим доказательство проме­жуточных теорем. Полезность схемы заключается в том, что она позволяет естественным образом выйти на экономическую ин­терпретацию потенциалов.

Введем новые характеристики поставщиков и потребителей транспортируемого ресурса — потенциалы ос, - и р, соответственно. Придадим этим характеристикам следующий экономический смысл: при заданном решении транспортной задачи будем пола­гать, что:

а, —это взятые с обратным знаком средние расходы /-го по­ставщика на транспортировку единицы продукции к потребите­лям;

Р_у- — это средние расходы /-го потребителя на доставку едини­цы продукции.

Термин «средние» предполагает, что, например, значение а, характеризует всю продукцию /-го поставщика (предназначен­ную в общем случае для нескольких потребителей).

При принятых предположениях- значение целевой функции должно быть равно:

п т

2=Ъ$РгЪщА- (15.8)

у' = 1 1 = 1