Вырожденность в транспортной задаче
Вырожденность в транспортной задаче — ситуация, когда в процессе решения транспортной задачи число базисных (занятых перевозками) ячеек транспортной таблицы меньше 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] (Кузнецов, напротив, предлагает включать в базис свободную ячейку с наименьшим тарифом).[3] Проверка у автора статьи показала, что оба этих метода не работают на показанном выше примере, и решение оказывается зацикленным (впадает в бесконечный цикл).
Включение в базис ациклической ячейки[править]
→ Ацикличность в транспортной задаче
Самаров и Хазанова предлагают включать в базисные ячейку, которая не образует перераспределительный цикл.[4][5] При испытании у автора статьи этот способ также не заработал на показанном выше тестовом примере,[1] и программа не выходила из бесконечного цикла. Чтобы метод заработал, надо выбирать случайную ячейку из возможных ациклических.
Случайный выбор свободной ячейки для включения в базис[править]
Для выбора базисной ячейки можно использовать случайный выбор, что, по мнению Данцига, гарантирует успех с вероятностью единица.[2] Автор статьи проверил этот метод и считает, что это действительно так. Вычисление потенциалов u и v может дать сбой, и в этом случае случайный выбор следует повторить. Пример программной реализации этого метода приведен по ссылке.[6]
Добавление возмущений к объемам спроса и предложения[править]
Чтобы ситуация вырожденности не возникла, можно прибавить к объемам потребления небольшие возмущения — числа, обозначаемые ε, такие как 0,00001, а также прибавить сумму этих чисел к объему одного из поставщиков, чтобы равенство суммарных объемов груза для поставщиков и потребителей не нарушалось. При получении итогового результата эти значения должны округляться. Данциг, ссылаясь на Ордена[7], утверждает, что ни одно допустимое базисное решение не будет вырожденным, если 0 < ε < 1/n — в этом случае решение не окажется зацикленным и алгоритм завершается через конечное число шагов.[2] Гасс, ссылаясь на более раннюю статью Ордена,[8] предлагает выбирать ε < δ/2m, где δ — единица последнего значащего разряда аi и bj.[9] Совсем маленькие возмущения могут попадать на ошибки округления компьютеров, поэтому нужно выбрать значения, заведомо не выходящее за пределы точности используемого компьютером или платформой для вычислений формата вещественных чисел, и при этом имеющие ничтожное значение для перевозимого груза (например, миллиграммы при перевозках, измеряемых в килограммах или тоннах). Проверка у автора статьи показала работоспособность этого алгоритма с возмущениями 0,00001 при целочисленных перевозках. Пример реализации с возмущениями 0,001 на Python имеется, например, по ссылке.[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,0 2,1 2,2 Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
- ↑ А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
- ↑ К. Л. Самаров. Учебное пособие для студентов. Транспортная задача. Москва, СВАО, Учебный центр «Резольвента»
- ↑ Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
- ↑ http://kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2
- ↑ Orden A. The transshipment problem, Manag. Sci. 2, № 3 (1956), 276—285.
- ↑ 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.
- ↑ С.Гасс. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961 (djvu)
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |