Исследование вопроса сводимости задачи к потоковым моделям
Нас будут интересовать такие задачи W(M), для которых применимы процедуры их сводимости к задаче L – поиска циркуляции минимальной стоимости. Пусть в системе ограничений (1) Определение 1. Будем говорить, что задача W(M) сводится к задаче L, если некоторое подмножество компонент оптимального решения задачи L образует оптимальное решение задачи W(M), и задача W(M) не имеет допустимого решения, если не имеет допустимого решения задача L. Так как система ограничений (1) задачи W(M) определяется заданием множества M, MÍ2N(s), будем решать задачу поиска таких множеств M, при которых задача W(M) сводится к задаче L. В [2] приведены достаточные условия, которые могут быть использованы для исследования сводимости рассматриваемых задач, однако проверка этих условий связана с исследованием свойств матрицы системы ограничений и является достаточно трудоемкой. В данной работе приводятся достаточные условия сводимости задачи W(M) к задаче L, основанные на исследовании множества M, мощность которого на порядок меньше количества строк системы ограничений задачи W(M). Введем следующее вспомогательное определение: Определение 2. Будем говорить, что набор значений индексов Теорема 1. Для того чтобы задача W(M) сводилась к задаче L достаточно, чтобы существовало такое разбиение Доказательство. Приведем конструктивное доказательство, основанное на построении сетевой модели. Не уменьшая общности, можно предположить, что если Æ и N(s)ÎM, то Будем конструировать сеть, состоящую из: 1. узлов множества 2. специального замыкающего узла 3. дуг, определяемых множеством 4. дуги, определяемой множеством 5. дуг, определяемых множеством 6. дуг, определяемых множеством 7. замыкающих дуг Дугам вида Очевидно, что любому допустимому решению задачи W(M) соответствует допустимая циркуляция построенной сети и, наоборот (здесь каждой переменной Теорема 2. Матрица, соответствующая системе ограничений (1), для которой выполняются условия теоремы 1, абсолютно унимодулярна. Доказательство. Проведем доказательство от противного. Предположим, что для системы ограничений (1) выполняются условия теоремы 1, но матрица, соответствующая этой системе, не абсолютно унимодулярна. Так как условия абсолютной унимодулярности, если Примеры
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (190)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |