![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Цикл пересчетаОпределение 8.2. Цикл пересчета – замкнутая ломаная с вершинами в заполненных клетках и звеньями, расположенными вдоль строк и столбцов матрицы перевозок, при этом одна вершина находится в заполняемой клетке. Цикл пересчета позволяет таким образом перераспределить поставки, чтобы не нарушить баланса перевозимого и поставляемого груза. Для любой свободной клетки можно построить единственный цикл пересчета. Примеры.На рисунке 8.1 изображены возможные варианты циклов пересчета: Рис. 8.1 Алгоритм улучшения опорного плана: 1) Среди всех 2) Для соответствующей клетки строят цикл пересчета. 3) Помечают вершины цикла пересчета последовательно знаками «+» и «–», начиная с «+» в исходной клетке. 4) Среди чисел, стоящих в клетках, помеченных «–» определяют минимальное. 5) К значениям, стоящим в «+» клетках, прибавляют это минимальное число, а из значений, стоящих в «–» клетках, это число вычитают. 6) Проверяют полученный план на оптимальность. Продолжим решение, сформулированной ранее задачи. Поскольку
Строя цикл пересчета по указанному алгоритму, получаем новый план перевозок, представленный в следующей транспортной таблице:
Новый план невырожденный. Проверим его на оптимальность. Для Для Так как
Получаем новый план перевозок, представленный в следующей транспортной таблице:
Проверим план на оптимальность. Для Для Все разности не положительны, следовательно, получен оптимальный план. Оптимальные затраты Ответ:
|