Лекция 4 Алгоритм циклических преобразований опорного решения транспортной задачи
План
4.1. Описание алгоритма однократного замещения
4.2. Метод «северо-западного угла»
4.2.1. Алгоритм решения
4.3. Метод «потенциалов»
4.3.1. Алгоритм решения
4.1. Описание алгоритма однократного замещения
Распределительная таблица фактически является матрицей, с которой можно проводить преобразования и получать новые опорные решения используя метод однократного замещения Жордана-Гаусса, сущность которого сводится к назначению другой базисной переменной, вместо одной из свободных.
При таком замещении свободная переменная объявляется базисной и подлежит определению, а некоторая базисная (безразлично какая) становится свободной. В математике доказано, что в каждом опорном решении задачи линейного программирования, размещённом в распределительной таблице, можно построить цикл, (и притом только один), однократного замещения одной свободной переменной на одну базисную переменную. При этом продуцируется новый опорный план с новым значением целевой функции. Матрица «единичных стоимостей», обеспечивает общий расчёт затрат по любому полученному решению. То есть она обеспечивает оценку решения записанного в таблице.
При целенаправленном преобразовании начальной таблицы-матрицы можно достигать как минимизации затрат. Рассмотрим методику названного алгоритма.
Циклом называют набор клеток, в котором две и только две клетки расположены в одной строке или в одном столбце, причём, последняя клетка столбца образует первую клетку строки, и так далее, вплоть до замыкания цепочки в цикле (см. рис. 4.1).
Рис. 4.1. Схема циклического преобразования
Целевая функция при этом равна Z0= 1130
С каждым опорным решением можно провести циклическое преобразование, которое всегда начинается в одной из свободных клеток, затем проходит только через занятые клетки, и заканчивается на исходной клетке.
Число вариантов таких преобразований равно числу свободных клеток. Число занятых клеток всегда должно быть равно рангу системы.
Приводим пример проведения циклического преобразования со свободной клеткой 4-1 (координаты клеток определяются номерами индексов переменных). Построим «от неё» схему цикла однократного замещения, изобразив его в таблице найденного ранее исходного («нулевого») варианта опорного решения.
В свободной клетке (4-4) размещаем +λ1 (первая нечётная порядковая клетка). Протягиваем далее от неё стрелку до занятой клетки (4-4), где будет размещаться - λ2 ... далее поступаем аналогичным образом, чередуя положительные и отрицательные значения λm , размещённые в угловых клетках, согласно последовательности построения цикла. Заметим, что индексы фиксируют только порядковое расположение λ, и к его численному значению никакого отношения не имеет. Численное значение λ определяется после построения цикла. Правила построение циклов всегда обеспечивают равное количество отрицательных и положительных по знаку значений λm..
Для выполнения очередного циклического преобразования достаточно выбрать клетку, которая, в построенном начальном цикле, имеет наименьшее, (по абсолютной величине), значение переменной, и находится в углу цикла со знаком «минус». В нашем примере это клетка 1-1 (рис. 4.2.).
3начение величины λ определяем (см. рис 4.2) следующим образом:
1) выберем в углах цикла клетку, с наименьшим размером корреспонденции, это будет клетка (1-1) с корреспонденцией λ11= 10;
2) выполним одно преобразование однократного замещения;
3) определим оценку клетки: О4-1 = +4 -4 +7-4+7-2+3-1 = 21-11 = +10
4) далее, можно определить ΔZ1 = λ · О1 = (+10)· (+10) = 100.
5) делаем вывод, что выбранная клетка (4-1) не обеспечивает уменьшение целевой функции Z. (Z1 >Z0), и от преобразования с ней надо отказаться. Выбираем следующую клетку... и так далее, пока не найдём клетку с отрицательной оценкой.
Z1 = 1230; λ = + 10; О4-1 = +10
Рис. 4.2. Табличная матрица после преобразования № 1