Шанкибаев Б.Н.
Республика Казахстан, Центрально-Азиатский университет
Новый подход к решению задач
транспортного типа
В данной работе продолжается изложение
метода «сокращения невязок», [1-3], и дается его реализация для двух видов
задач транспортного типа: транспортной задачи с ограниченными пропускными
способностями коммуникаций; обобщенной транспортной (распределительной) задачи.
Метод
сокращения невязок для решения транспортной задачи с ограниченными пропускными
способностями коммуникаций
Рассмотрим задачу,
заданную следующей моделью: найти минимальное значение линейной функции
(1)
при ограничениях:
(2)
(3)
(4)
Наличие верхнего
ограничения для переменных
, означает ограничение пропускных способностей коммуникаций.
Модель (1)-(4),
когда некоторые из равны нулю,
называется моделью транспортной задачи с запретами соответствующих перевозок.
Опишем алгоритм
решения задачи (1)-(4), разработанный автором
и изложенный, в частности, в работах [1] - [3]. Этот алгоритм является
обобщением алгоритма решения общей транспортной задачи, [1].
Предварительный этап.
Шаг 1. Все элементы каждого столбца нумеруются в порядке
возрастания значений
(устанавливаются
номера
).
Шаг 2. Заполняется
матрица . Опишем заполнение произвольного столбца
. В клетке, где
, устанавливается
. (5)
Если , то столбец заполнен и все остальные элементы этого столбца
равны нулю. Если
, то выбирается клетка с номером
. В этой клетке устанавливается
. (6)
Здесь - значение
в клетке с номером
.
Если , то столбец заполнен и все остальные элементы этого столбца
равны нулю; в противном случае, рассматривается клетка с номером
и т.д.
Шаг 3.
Для всех клеток устанавливаются
прямые компоненты
по формуле
(7)
Здесь клетка столбца
, у которой номер
на единицу больше
номера клетки
.
Шаг 4. В
клетках с номером устанавливаются
обратные компоненты
.
Шаг 5.
Вычисляются значения
(8)
Если все , то задача решена; иначе, выполняется основной этап.
Основной
этап.
Шаг 1. Пусть строка, для которой
. В
выбирается наименьшая
допустимая компонента
. Если она отмеченная, выполняется шаг 5.
Шаг 2. Пусть на шаг 2 вышли по компоненте . Отыскивается строка
, для которой имеет место
(9)
Если выполняется одно из двух условий: а)
строка совпадает со строкой
; б) имеет место
(10)
то
компонента становится отмеченной
и выполняется шаг 3 по строке
. Если
и
(11)
то
выполняется шаг 3 по строке . Если
(12)
то выполняется шаг 2 по компоненте .
Шаг 3. Описывается по строке . В строке
отыскивается
наименьшая компонента
из расширенного
множества допустимых компонент. Если она отмеченная, выполняется шаг 5 при
, шаг 4 по строке
при
. Если компонента неотмеченная, выполняется шаг 2.
Шаг 4. Описывается по строке . Компонента
становится отмеченной
и вычисляется по формуле
(13)
Выполняется шаг 3 по строке .
Шаг 5. Величина уменьшается, а
величина
увеличивается на
(14)
здесь строка , удовлетворяет условию (9).
Шаг 6. В клетке устанавливается
компонента
по формуле
(15)
Все компоненты становятся неотмеченными.
Выполняется шаг 5 предварительного этапа.
Метод сокращения невязок для решения распределительной задачи
Рассматриваем задачу
вида: найти минимальное значение линейной функции
(16)
при ограничениях:
(17)
(18)
(19)
Приведём алгоритм,
разработанный автором данной статьи и предложенный, для целочисленного
варианта, в работе [3].
Предварительный этап.
Шаг 1. Для каждого
столбца производится
нумерация (матрица
) всех клеток
в порядке возрастания
.
Шаг 2. Заполняется
матрица следующим образом:
(20)
Шаг 3. Для
всех клеток устанавливаются
прямые компоненты
по формуле
(21)
Здесь клетки столбца
, у которых номер p на единицу больше номера клетки
.
Шаг 4. В клетках с
номером устанавливаются
обратные компоненты
.
Шаг 5.
Вычисляются значения
.
(22)
Если все , задача решена. В противном случае выполняется основной этап
алгоритма.
Основной этап.
Шаг 1. Пусть строка с наибольшей
пометкой
, и
компонента этой
строки, указываемая пометкой. Если
, устанавливается
, где
- строка, на которую
указывает «в смысле (9)» компонента
; переходим на шаг 3. Если
, переходим на шаг 2.
Шаг 2. Принимается за строка, которой
соответствует пометка
. Если такой нет, за
принимается
какая-либо строка
, у которой
. Пометка строки
стирается. Переходим
на шаг 3.
Шаг 3. Если строка имеет пометку,
меньшую чем
, то компонента
, указываемая наибольшей пометкой, становится особой и
получает метку
, а клетка
получает метку
.
Если , то компонента
, указываемая наибольшей пометкой, становится отмеченной.
В обеих случаях при максимальная пометка
строки стирается и выполняется шаг 1, а при
- шаг 2.
Если , находится компонента
(23)
для всех допустимых компонент
строки при
и для всех компонент
из расширенного множества допустимых компонент при
.
Если отмеченная, условно
отмеченная или особая, выполняется шаг 4. Если она неотмеченная, строке
присваивается пометка
. Компонента
становится условно
отмеченной и выполняется шаг 1.
Шаг 4. Если , то компонента
становится
разрешающей и выполняется шаг 5.
Если , то компонента
, указываемая этой пометкой, становится отмеченной (перестаёт
быть условно-отмеченной) и пересчитывается по формуле
. (24)
Если - особая, то
компонента
также становится
особой и получает метку
, а клетка
получает метку
.
При наибольшая пометка
строки
стирается и
выполняется шаг 1. При
выполняется шаг 2.
Шаг 5. Если - разрешающая не особая
компонента, то
уменьшается, а
увеличивается на
. Если компонента особая, то изменения происходят на величину
. Здесь
(25)
(26)
а величина определяется из
уравнения
(27)
Шаг 6. Для
клетки вычисляется заново
компонента
по формуле
, (28)
где - наименьшая
компонента из расширенного множества допустимых компонент строки.
Все компоненты
становятся неотмеченными и выполняется шаг 5 предварительного этапа.
Алгоритм окончен.
Литература
1. Сатыбалдиев О.С., Шанкибаев Б.Н. Метод
сокращения невязок для решения транспортной задачи //Materialy IV Mezinarodni vedecko – prakticka conference «Veda a technologie:
Krok do budoucnosti – 2008»//, 1-15 brezen (марта) 2008 roku (Материалы Международной научной конференции «Наука и
технологии: шаг в будущее»), Praha, Publishing House «Education and Science» s.r.o, 2008, с. 25-28.
2. Шанкибаев Б.Н. Новый
подход к решению задач целочисленного программирования //Materialy IV Miedzynarodowej naukowi – praktycznej konferencji «Strategiczne pytania swiatowej nauki»// (Материалы Международной
научно-практической конференции «Стратегические вопросы мировой науки»), 15-28 lutego (февраль) 2008 roku, Przemysl, Nauka i
studia, с. 22-27.
3. Шанкибаев Б.Н.
Условия оптимальности и алгоритмы
решения целочисленных распределительных задач // Диссертация на соискание
ученой степени кандидата физико-математических наук. Москва, ЦЭМИ АН СССР,
1972.