Приближенные распределительные методы

К приближенным распределительным методам можно отнести метод наилучших цен и метод аппроксимации. Приближенными они называются вследствие того, что полученное при помощи этих методов распределение груза в таблице не требует дополнительной проверки на оптимальность, так как-либо сразу оказывается оптимальным, либо максимально к нему приближено. транспортный аппроксимация алгоритм перевозка Метод наилучших цен Метод наилучших цен позволяет получить более выгодный опорный план, чем метод северо-западного угла. При распределении груза на каждом шаге этого метода выбирается клетка с наилучшей ценой. Наилучшей считается минимальная цена при Z>min, и максимальная цена при Z>max. Если существует несколько клеток с одинаковыми лучшими тарифами, то из них для определенности можно выбрать клетку, находящуюся левее и выше остальных.

Алгоритм метода наилучших цен:

• 1) рассматривая рабочую таблицу, найти клетку с наилучшей ценой;
• 2) проставить в эту клетку максимально допустимое значение хij;
• 3) вычеркнуть свободные нерабочие клетки;
• 4) откорректировать клетки bi и aj.

На этом заканчивается один шаг (итерация) метода.

Из оставшихся свободных рабочих клеток снова выбрать клетку с наилучшей ценой и повторять до тех пор, пока полностью не будет распределен весь груз.

Заполнение рабочей таблицы методом наилучших цен.

Zmin = 300*13 + 1200*12 + 1000*13 + 500*15 + 1400*13 + 100*16 = 58 600.

Замечание. Предлагаемый алгоритм метода можно использовать для решения задач небольшого размера. При решении задач большого размера алгоритм этого метода применяется не для всей рабочей таблицы, а или для каждой стоки, или каждого столбца.

Метод аппроксимации Данный метод, также как и предыдущий, использует понятие «наилучшая цена», но в отличие от него позволяет более однозначно сделать выбор между равнозначными клетками при распределении груза.

Алгоритм метода аппроксимации:

• 1) в рабочей таблице задачи берем дополнительную строку и столбец «разностей»;
• 2) заполняем эти строку и столбец разностями между двумя наилучшими ценами по каждой строке и каждому столбцу;
• 3) из всех разностей строки и столбца выбрать наибольшую, указать номер итерации;
• 4) в соответствующей строке или столбце выбираем клетку с наилучшей ценой, проставляем в эту клетку максимальное значение xij;
• 5) корректируем свободные члены и вычеркиваем нерабочие свободные клетки;
• 6) из оставшихся неиспользованных разностей снова выбрать наибольшую и так до тех пор, пока или не будут использованы все разности или не будет распределен весь груз.

Если разности будут использованы все, а груз распределен не до конца, то в малых задачах дораспределение груза производится вручную. В больших же задачах приходится дочерчивать строку и столбец «разностей» и заполнять их, но теперь разности берутся между двумя наилучшими ценами, но только по свободным рабочим клеткам.

Заполнение рабочей таблицы методом аппроксимации.

Zmin = 300*13 + 1200*12 + 1000*13 + 500*15 + 1400*13 + 100*16 = 58 600.

Разность 31 означает, что заполнение таблицы начинать следует с клетки (2,4) (столбец выбран с учетом наибольшей разности, клетка в этом столбце выбрана с наименьшей ценой, так как Z>min).

При заполнении таблицы следует помнить, что:

• 1) если разности использованы все, а грузы распределены не до конца, то если существует единственный вариант, дораспределение происходит вручную. Если же дораспределять грузы можно разными способами, то чертится еще одна строка и столбец разностей и заполняются они разностями между наилучшими ценами только по свободным клеткам. Далее алгоритм действий повторяется;
• 2) если в строке и столбце окажется несколько одинаковых разностей, то предпочтение надо отдать той, которая будет иметь «оптимальный элемент». «Оптимальный элемент» — это цена, которая является наилучшей, как по строке, так и по столбцу, на пересечении которых она стоит. Исследование на наличие «оптимального элемента» проводить после каждой итерации;
• 3) если оптимальный элемент имеется у нескольких одинаковых разностей, то предпочтение отдать тому «оптимальному элементу», который будет иметь наибольшую сумму «разностей» по строке и столбцу, на пересечении которых он стоит. Если и сумма окажется одинаковой, то заполнять можно клетку с любым «оптимальным элементом»;
• 4) если мы имеем несколько одинаковых разностей и ни одна из них не имеет «оптимального элемента», то тогда в соответствующих строках и столбцах исчисляются новые разности, но между 1-ой и 3-ей наилучшими ценами.

Замечание. В качестве недостатка этого метода можно отметить необходимость в знании всех его особенностей, а также некоторую громоздкость таблиц.