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

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

Ацикличность в транспортной задаче — свойство ячейки транспортной таблицы с нулевой перевозкой при решении транспортной задачи, при котором для этой ячейки невозможно построить перераспределительный цикл.

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

В ситуации вырожденности транспортной задачи при ее решении методом потенциалов требуется ввести в базис одну из свободных ячеек (то есть одну из ячеек с нулевым объемом перевозки). Но какую же ячейку выбрать? Разные авторы расходятся в указании на то, что в этой ситуации следует делать. Если Данциг утверждает, что можно включить в число базисных произвольную случайную (рандомную, то есть выбранную всякий раз наугад) свободную ячейку,[1]:312 то Самаров и Хазанова предлагают включать в базис не любую ячейку, а только обладающую свойством ацикличности.[2]:9[3]:59

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

Пример программной реализации приведен по ссылке.[4] Там эта проверка, однако, закомментирована и избран способ Данцига — выбирать произвольную ячейку.

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

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

Транспортная задача (классическая) • Решение симплекс-методомРешение в ExcelТранспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента)

Начальное решение

Метод северо-западного углаМетод минимальных тарифовМетод Фогеля‎

Вырожденные случаи

Вырожденность в ТЗАцикличность в ТЗ