Каталог статей

Шанкибаев Б.Н.

Новый подход к решению задач транспортного типа

В данной работе продолжается изложение метода «сокращения невязок», [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.