Ацикличность в транспортной задаче
Ацикличность в транспортной задаче — свойство ячейки транспортной таблицы с нулевой перевозкой при решении транспортной задачи, при котором для этой ячейки невозможно построить перераспределительный цикл.
Вырожденность в транспортной задаче[править]
В ситуации вырожденности транспортной задачи при ее решении методом потенциалов требуется ввести в базис одну из свободных ячеек (то есть одну из ячеек с нулевым объемом перевозки). Но какую же ячейку выбрать? Разные авторы расходятся в указании на то, что в этой ситуации следует делать. Если Данциг утверждает, что можно включить в число базисных произвольную случайную (рандомную, то есть выбранную всякий раз наугад) свободную ячейку,[1] то Самаров и Хазанова предлагают включать в базис не любую ячейку, а только обладающую свойством ацикличности.[2][3]
Проверка автора на примере из статьи «Вырожденность в транспортной задаче» показала, что способ Данцига дает сбой при вычислении потенциалов (этот сбой, однако, можно устранить повторным выбором случайной (рандомной) ячейки, для которой сбой не возникает). А способ с выбором ациклической ячейки впадает в бесконечный цикл, если выбор из возможных ациклических ячеек не является случайным (рандомным). Таким образом, очевидно, что проверять на ацикличность нужно случайную (рандомную) ячейку, либо не проверять ее на ацикличность, а отсеивать неудачный выбор ячейки для включения в базис на этапе вычисления потенциалов.
Пример программной реализации приведен по ссылке.[4] Там эта проверка, однако, закомментирована и избран способ Данцига — выбирать произвольную ячейку.
Источники[править]
- ↑ Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
- ↑ К. Л. Самаров. Учебное пособие для студентов. Транспортная задача. Москва, СВАО, Учебный центр «Резольвента»
- ↑ Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
- ↑ http://kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2, функция ПоискНулевойЯчейкиДляВводаВБазис
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |