2015-06-30
459
| Таблица 13.32. Вычитание наименьшего элемент» по столбцам | ||
| 0 2 0 2 3 3 7 0 | 7 10 2 2 0 5 0 0 |
В соответствии с процедурой, описанной в этапе 2, осуществляются назначения. Наличие назначения обозначается черезГо7|
| Таб | лица 13.33. | Назначения в клетки | |
| с нулевыми значениями | |||
| ы | |||
| е 3 7 | в | 2 5 в |
На данном этапе мы можем осуществить только три нулевых назначения, тогда как требуемое их количество равно четырем. Полученное распределение является недопустимым. Переходим к этапу 3. Проводим наименьшее число прямых, проходящих через все нули таблицы.
Таблица 13.34. Проведение прямых через нулевые элементы
| < | > 2 | |
| > 2 | ! 2 | |
| 1 3 i | 1 5 | |
| I " ' | ) U |
Наименьшим элементом, через который не проходит ни одна из прямых, является число 2. Скорректируем таблицу так, как это описано выше в соответствии с этапом 3, т.е. вычтем 2 из каждого элемента, через который не проходит ни одна прямая, и добавим 2 ко всем элементам, лежащим на пересечении двух прямых, оставив без изменения все прочие элементы, через которые проходит только одна прямая. Теперь перераспределим соответствующие назначения сбытовых баз и потребителей.
Таблица 13.35. Скорректированная таблица с назначениями для нулевых клеток
| / | II | III | IV | |
| А | Го1 | в | ||
| В | в | ш | в | |
| С D | 3 9 | 1 в | L0J | й |
Гл. 13. Транспортная задача и задача о назначениях 489
Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В — к потребителю II, с базы С — к потребителю III и с базы D — к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. Тем не менее в любом оптимальном решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных распределения назначений представлены ниже.
Таблица 13.36. Первое альтернативное оптимальное решение
| / | и | in | IV | |
| А | щ | е | ||
| В С | е | е 1 | Й | |
| D | Lil | в |
Таблица 13.37. Второе альтернативное оптимальное решение
| / | II | III | IV | |
| А В С D | е | в 1 в | 8 в |
Минимальную дальность перевозок для каждого из трех решений можно вычислить из исходной таблицы:
Решение 1: 68 + 60 + 35 + 45 = 208 миль;
Решение 2: 68 + 63 + 35 + 42 = 208 миль;
Решение 3: 72 + 56 + 35 + 45 = 208 миль. Общая дальность перевозок для всех трех решений одинакова.
Примечание: в задачах большей размерности, чем задача из примера 13.7, убедиться в том, что проведенное в соответствии с пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":
1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.
2. Если выбрана строка, прямая проводится через столбец, в котором находится данный нулевой элемент.
3. Если выбран столбец, прямая проводится через строку, содержащую данный нулевой элемент.
4. Пункы 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.
490 Ч. 4. Моделирование в бизнесе
