Метод "северо-западного угла". Циклы

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

В правом верхнем углу каждой клетки таблицы перевозок укажем стоимость перевозки единицы груза и будем стремиться последовательно удовлетворять требования каждого потребителя и каждого поставщика.

Начнем заполнение таблицы перевозок с левого верхнего ("северо-западного") угла. Потребителю Бх требуется 80 единиц груза. Эти 80 единиц груза могут быть доставлены от первого поставщика Ъг. Поэтому запишем в клетку 81Б1 количество перевозок 80.

Поставщик 81 требует, чтобы с его предприятия было вывезено 100 единиц груза, а пока вывезено только 80. Увезем оставшийся груз к потребителю Б2. Запишем в клетку .V,остающиеся у поставщика Л'; 20 единиц груза.

Таблица 11

Перевозки (1): метод “северо-западного угла”
5/0, А А А Запасы
$1 ■4

80

л

20

—* 3 100
£ 70 13 5

0

200
Заказы 80 90 130

Займемся теперь потребителем Б2. Ему требуется 90 единиц груза, а пока доставлено от только 20. Недостающие 70 единиц доставим от поставщика Ъ2. Продолжая заполнять таблицу, позаботимся об удовлетворении поставщика Ъ2. От него вывезено 70 единиц груза, в то время как требуется вывезти 200. Увезем оставшийся груз к потребителю 83, и, поскольку наша транспортная задача сбалансирована, именно эти оставшиеся у поставщика 82 130 единиц груза и нужны потребителю Вз.

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

Легко видеть, что полученный план можно улучшить (уменьшить суммарные транспортные издержки). Маршрут Ъ]Б3 имеет цену перевозки единицы груза меньше, чем Ъ]Б2. Понятно поэтому, что было бы дешевле вывезти 20 единиц груза от поставщика .82 не к потребителю Б2, а к потребителю Б3. Но в таком случае, чтобы не нарушить выполнение требований потребителей Б2 и Б3 необходимо увеличить количество грузов, перевезенных от поставщика Ъ2 к потребителю Б2, за счет уменьшения числа единиц грузов, перевезенных от 82 к Б3.

Тогда таблица перевозок приобретет следующий вид.

Таблица 12

5/0, о, Ог Запасы
5, А

80

і 3

20

100
& к -1

90

5

110

200
Заказы 80 90 130
Перевозки (2

циклы оптимизации

Полученный нами план также является опорным. Легко видеть, что в результате этого преобразования 20 единиц грузов были как бы перенесены по круговому пути, или, как говорят, по "циклу", 8}В2 ^ 8}В3 ^ Б2В3^Б2В2. При переносе каждой единицы груза из 8}В2 в 8}В3 выигрыш в цене составляет 3 у.е.. Аналогично при переносе единицы груза из 82В3 в 82В2 происходит выигрыш в 1 у.е.. Итак, при переносе 20 единиц груза по этому циклу выигрыш в издержках составил 4 у.е. * 20 = 80 у.е.

Говорят, что найденный нами цикл имеет "отрицательную цену" (- 4 у.е.). Процесс оптимизации плана перевозок, таким образом, состоит в отыскании циклов с отрицательной ценой и переносе наименьшего в этом цикле количества грузов вдоль этого цикла. В процессе такого преобразования план остается опорным и суммарная стоимость перевозок шаг за шагом уменьшается. Процесс следует продолжать до тех пор, пока не останется циклов с отрицательной ценой. Получившийся в результате план, очевидно, будет оптимальным. В нашей "игрушечной" задаче таких циклов, как легко убедиться, нет уже после первого циклического переноса. Таким образом, таблица перевозок (2) представляет собой оптимальный план перевозок для нашей задачи.

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

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

<< | >>
Источник: Зайцев М.Г.. Методы оптимизации управления для менеджеров. Комп.-ориент. подход_ _ -304с.. 2008

Еще по теме Метод "северо-западного угла". Циклы:

  1. Метод северо-западного угла
  2. Мини-кейс "На кондитерской фабрике". Акт 2 (Жаль... ведь мы все так любим "Батончик"!)
  3. Основное содержание курса "Количественные методы в менеджменте"
  4. Место курса "Количественные методы в менеджменте" в программе МВА
  5. Какие вопросы рассматриваются в курсе "Количественные методы в менеджменте"?
  6. Миссия курса "Количественные методы в менеджменте"
  7. "Культурное производство" и "творческие (культурные) индустрии"
  8. Курс "Количественные методы в менеджменте" в программе МВА
  9. Курс "Количественные методы в менеджменте" в программе МВА
  10. Алесинская Т.В.. Учебное пособие по решению задач по курсу "Экономико-математические методы и модели". Таганрог: 153 с, 2002