Задачи двухуровневого программирования, полиномиально разрешимые методом декомпозиции

• Автор: Плясунов, Александр Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Новосибирск
• Количество страниц: 108 с.

_ ОГЛАВЛЕНИЕ

Введение

Глава 1. Линейные модели

1.1. Основные определения

1.2. Задача с линейным ранцем на нижнем уровне

1.3. Задача с дополнительными ограничениями

1.4. Задача с многоинвариантным ранцем на нижнем уровне . 31 Глава 2. Нелинейные модели

2.1. Постановка задачи

2.2. Невырожденный случай

2.2.1. Функция возмущения задачи НЗР(у)

2.2.2. Условия оптимальности для задачи НЗР(г/)
2.2.3. Декомпозиция и полиномиальная разрешимость задачи
2.3. Вырожденный случай
2.3.1. Функция возмущения задачи НЗР(у)
2.3.2. Декомпозиция в вырожденном случае
Глава 3. Частично-целочисленные модели
3.1. Задача выбора ряда изделий с частичным внешним финансированием
3.2. Сведение к задаче выбора ряда изделий
3.3. Линейная задача
3.4. Задачи на максимум
3.5. Вырожденный случай
Заключение
Список литературы
Введение
Задачи многоуровневого программирования появились в связи с проблемами управления производственными, экономическими, социальными и другими сложными системами. Традиционное моделирование таких процессов основывается на предположении, что имеется одно лицо, принимающее решение. Подобный подход игнорирует других участников процесса управления, имеющих свои предпочтения и стратегии выбора. Поэтому в разных областях человеческой деятельности все чаще стали появляться схемы принятия решений, позволяющие учесть конфликтные ситуации, характерные для современного общества. Так как теперь априори предполагается наличие разнородных интересов или факторов, плохо поддающихся прямому контролю, то в качестве подходящей математической модели принятия решений могли бы использоваться системы оптимизационных моделей так или иначе связанных друг с другом. Когда рассматриваются схемы принятия решений, согласовывающие противоречивые интересы, то возникают задачи равновесного программирования [2]. В этих задачах в качестве решений используются неподвижные точки или равновесные решения.
Задачи многоуровневого программирования чаще всего возникают при моделировании процессов управления в иерархических системах. Верхний уровень в таких системах (центральное правитель-

Пусть М-— столбцы матрицы ограничений соответствующие ненулевым переменным у].у Очевидно, что ранг матрицы М равен п и для каждой нулевой переменной г1 или у*■ соответствующее двойственное ограничение задачи ДМВР(т) выполняется как строгое неравенство на любом оптимальном оптимальном решении (гг,7), где и/ £ [гг^у,,, гг*
7,- = /у (ад). Отсюда имеем, что рассматриваемое допустимое решение задачи МВР(г) является ее единственным оптимальным решением.
Предположим, что /з(гт*) < 0 < р(гт*). Тогда гг* совпадает с одним из узлов гл*0у0 или и является единственной точкой, в которой функция Рх достигает свое минимальное значение. Следовательно, в задаче ДМВР(т) существует единственное оптимальное решение (гг*,7*), где 7] = /у (гг*). Допустим, что гг* = гг*^. Тогда для у ф у) имеем, что ,иу(гг*) = ру(гг*) = -р^. Если у = ^ то ДуДгг*) = ~Ркгп и = ~Рк:+1д. Рассмотрим допустимое решение (у'Ъ, г2) задачи
МВР(х), которое является решением следующей системы равенств:
г = 0= 0,у фп,г ф ij,yih =0,%ф къкх + 1, (1.20)
Уц] = Ту,У ф Уь (1-21)
УкхЗ! + 2/*1+1л = Ту,, (1*22)
X/ РузУуЗ РЬЗхУкгп т Рг-1-МУ,г/*,-|-1У| = X (1}ху (1-23)
зфк г'е-г
Так как уг(г«*) < 0 < />(гт‘), то обе переменные г/*^ и г/^у, являются
ненулевыми. Как и в предыдущем случае, рассмотрим множество М
— столбцов матрицы ограничений, соответствующих ненулевым переменным у]у. Так как ранг матрицы М равен п+1, то есть числу ненулевых переменных, то решение системы уравнений (1.20)-(1.23) является базисным допустимым решением задачи МВР(т). Учитывая, что для