Вырожденность в транспортной задаче

Материал из Циклопедии
Перейти к: навигация, поиск

 → Транспортная задача

Вырожденность в транспортной задаче — ситуация, когда в процессе решения транспортной задачи число базисных (занятых перевозками) ячеек транспортной таблицы меньше m + n - 1 (где m и n — число поставщиков и потребителей, соответственно), и алгоритм решения впадает в бесконечный цикл или завершается с ошибкой. Для решения этой проблемы предлагается несколько методов.

Содержание

[править] Пример транспортной задачи, в которой возникает вырожденность

B1, 20 кг B2, 40 кг B3, 30 кг B4, 10 кг B5, 50 кг B6, 25 кг
A1, 30 кг 1 2 1 4 5 2
A2, 50 кг 3 3 2 1 4 3
A3, 75 кг 4 2 5 9 6 2
A4, 20 кг 3 1 7 3 4 6

Здесь Ai — объемы предложения у поставщиков (для предметности добавлены условные единицы измерения — килограммы), Bj — объемы спроса у потребителей, а на пересечении строк и столбцов находятся цены доставки Cij (например, в рублях). Это тестовый пример из программы на Python по ссылке.[1]

[править] Включение в базис определенной ячейки

Чтобы метод потенциалов позволил вычислить сами потенциалы u и v в вырожденной транспортной задаче, необходимо включить в число базисных одну из свободных (не занятых перевозками) ячеек транспортной таблицы. Данциг предлагает включать в базис ячейку таблицы с максимальной ценой[2]:312 (Кузнецов, напротив, предлагает включать в базис свободную ячейку с наименьшим тарифом).[3]:115 Проверка у автора статьи показала, что оба этих метода не работают на показанном выше примере, и решение оказывается зацикленным (впадает в бесконечный цикл).

[править] Включение в базис ациклической ячейки

 → Ацикличность в транспортной задаче

Самаров и Хазанова предлагают включать в базисные ячейку, которая не образует перераспределительный цикл.[4]:9[5]:59 При испытании у автора статьи этот способ также не заработал на показанном выше тестовом примере,[1] и программа не выходила из бесконечного цикла. Чтобы метод заработал, надо выбирать случайную ячейку из возможных ациклических.

[править] Случайный выбор свободной ячейки для включения в базис

Для выбора базисной ячейки можно использовать случайный выбор, что, по мнению Данцига, гарантирует успех с вероятностью единица.[2]:312 Автор статьи проверил этот метод и считает, что это действительно так. Вычисление потенциалов u и v может дать сбой, и в этом случае случайный выбор следует повторить. Пример программной реализации этого метода приведен по ссылке.[6]

[править] Добавление возмущений к объемам спроса и предложения

Чтобы ситуация вырожденности не возникла, можно прибавить к объемам потребления небольшие возмущения — числа, обозначаемые ε, такие как 0,00001, а также прибавить сумму этих чисел к объему одного из поставщиков, чтобы равенство суммарных объемов груза для поставщиков и потребителей не нарушалось. При получении итогового результата эти значения должны округляться. Данциг, ссылаясь на Ордена[7], утверждает, что ни одно допустимое базисное решение не будет вырожденным, если 0 < ε < 1/n — в этом случае решение не окажется зацикленным и алгоритм завершается через конечное число шагов.[2]:303 Гасс, ссылаясь на более раннюю статью Ордена,[8] предлагает выбирать ε < δ/2m, где δ — единица последнего значащего разряда аi и bj.[9]:195 Совсем маленькие возмущения могут попадать на ошибки округления компьютеров, поэтому нужно выбрать значения, заведомо не выходящее за пределы точности используемого компьютером или платформой для вычислений формата вещественных чисел, и при этом имеющие ничтожное значение для перевозимого груза (например, миллиграммы при перевозках, измеряемых в килограммах или тоннах). Проверка у автора статьи показала работоспособность этого алгоритма с возмущениями 0,00001 при целочисленных перевозках. Пример реализации с возмущениями 0,001 на Python имеется, например, по ссылке.[1]

[править] Источники

  1. 1,0 1,1 1,2 Stepping stone algorithum for solving the transhipment problem (Python recipe). Created by James Coliins on Sat, 29 Nov 2008 (MIT). копия http://www.peeep.us/5a45cffc
  2. 2,0 2,1 2,2 Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
  3. А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
  4. К. Л. Самаров. Учебное пособие для студентов. Транспортная задача. Москва, СВАО, Учебный центр «Резольвента»
  5. Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
  6. http://kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2
  7. Orden A. The transshipment problem, Manag. Sci. 2, № 3 (1956), 276—285.
  8. Orden A., Application of the Simplex Method to a Variety of Matrix Problems, pp. 28—50 of Directorate of Management Analysis // Directorate of Management Analysis, Symposium on Linear Inequalities and Programming, A. Orden and L. Goldstein (eds.), DCS/Comptroller, Headquarters US Air Force, Washington, D. C, April 1952.
  9. С.Гасс. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961 (djvu)


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты