Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Казахский Гуманитарно-Юридический Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

метод Данцига.docx

Скачиваний:

Добавлен:

05.02.2016

Размер:

139.59 Кб

Скачать

☆

<<< < Предыдущая 12 / 22

Описание алгоритма декомпозиции

Дадим формальное описание алгоритма декомпозиции Данцига-Вульфа для решения задачи (10.1.29)—(10.1.32) (20). Пусть уже имеется начальное допустимое базисное решение задачи (10.1.18)—(10.1.21), которому соответствует вектор разрешающих множителей . Каждая итерация алгоритма состоит из двух этапов.

Первый этап. 1. Используя вектор оценок предыдущей итерации, сформируем и решим подзадачи (10.1.36)—(10.1.37) и найдем оптимальное значение целевой функции, а также соответствующие решения

2. Вычислим минимальную оценку

(10.1.38)

3. Если то вычисление заканчивается и определяем оптимальное решение задачи (10.1.29)—(10.1.32)

(10.1.39)

где — предыдущее базисное решение координирующей задачи, а — крайняя точка , соответствующая базисной переменной

Если то переходим ко второму этапу.

Второй этап. Формируем столбец который необходимо ввести в базис задачи (10.1.18)—(10.1.21):

(10.1.40)

Вводим вектор в базис, выполняем первый шаг симплекс-метода, после чего находим новое допустимое базисное решение

а также новый вектор оценок

На этом итерация заканчивается и переходим к первому этапу очередной итерации.

Как видно из описания, алгоритм декомпозиции Данцига-Вульфа представляет собой двухуровневый алгоритм, где на первом уровне решаются подзадачи (10.1.36), (10.1.37), а на втором уровне — координирующая задача (10.1.18)—(10.1.21). Если координирующая задача является невырожденной, то на каждой итерации значение целевой функции возрастает, и поскольку число базисов ее конечно и ни один из них не используется дважды, оптимальное решение находится за конечное число шагов.

Ограниченная координирующая задача

Как следует из приведенного выше описания алгоритма декомпозиции, оптимизационная задача в нем решается лишь на первом уровне, тогда как на втором фактически выполняется лишь одна итерация симплекс-метода. Однако возможна модификация этого метода, заключающаяся в решении оптимизационных задач на двух уровнях. В этом случае решается так называемая ограниченная координирующая задача, которая получается из координирующей задачи (10.1.18)—(10.1.21) в результате отбрасывания всех столбцов, за исключением базисных и претендующих на включение в базис на текущей итерации.

Такую ограниченную координирующую задачу можно представить в виде:

максимизировать

(10.1.41)

при ограничениях

(10.1.42)

где — переменные текущего базиса: — переменная, вводимая в базис (для нее ). Если текущий базис является невырожденным, то из него будет выведена переменная, для которой и полученное решение будет оптимальным.

Заметим, что возможны случаи, когда использование ограниченной координирующей задачи по сравнению с обычной координирующей задачей дает эффект.

Варианты декомпозиции прямой задачи

Существует много разных способов декомпозиции прямой задачи, каждый из которых приводит к своей форме координирующей и ограниченной координирующей задач.

Рассмотрим, например, вариант декомпозиции для матрицы блочно-диагонального вида. Обозначим решение системы

(10.1.43)

где крайние точки многогранника ;

Тогда координирующая задача будет иметь вид:

максимизировать

(10.1.44)

при ограничениях

(10.1.45)

(10.1.46)

где

Координирующая задача (10.1.44)—(10.1.46) отличается от координирующей задачи (10.1.18)—(10.1.21). Во-первых, она имеет не одно, а ограничений типа (10.1.46), во-вторых, решение для каждой подсистемы самостоятельно выражается через переменные , тогда как в задаче (10.1.13)—(10.1.21) эти решения рассматривались совместно. Применим метод обратной матрицы с использованием процедуры генерации столбцов для решения задачи (10.1.44)—(10.1.46).

Пусть — базисная матрица размерности а — вектор относительных оценок для этого решения ( -оценка ограничений (10.1.45), а — оценка для i-го ограничения (10.1.46)).

Вычисляем теперь оценки для векторов, соответствующих переменным

(10.1.47)

Для определения при фиксированном решаем подзадачу вида:

минимизировать

(10.1.48)

при ограничениях

(10.1.49)

Если

то текущее решение – оптимально, в противном случае – в базис задачи (10.1.44)—(10.1.46) вводится переменная, для которой

(10.1.50)

Если этот минимум достигается при а решение подзадачи с индексом то в базис координирующей задачи вводится столбец

где -мерный вектор, все компоненты которого равны 0, за исключением -й компоненты, равной 1.

Пример 10.1. Для иллюстрации метода декомпозиции рассмотрим задачу ЛП:

максимизировать

(1)

при ограничениях

(2)

(3)

(4)

Эта задача имеет одно связывающее ограничение и два независимых блока. Области допустимых решений неравенств обоих подсистем представлены на рис. 10.1.

Разбиение задачи (1)—(4) может быть осуществлено разными способами, и каждому из них будет соответствовать своя координирующая задача с определенным типом ограничений вида Воспользуемся видом ограничений и построим ограниченную координирующую задачу, которая будет иметь два ограничения. Пусть и — допустимые решения блоков (1) и (2) соответственно. Тогда справедливо соотношение

где крайние точки множеств и соответственно определяемые ограничениями (3) и (4).

Целевая функция (1) в векторном виде запишется:

а связывающее ограничение

где

Запишем теперь координирующую задачу:

максимизировать

(5)

при условиях

(6)

(7)

(8)

(9)

Выберем в качестве начального допустимого базисного решения

Будем решать эту задачу методом обратной матрицы. Начальная симплекс-таблица будет иметь вид Табл. 10.1.

В последней строке таблицы находятся переменные { }:

где соответствует ограничению (7); — ограничению (8), а соответствует ограничению (8), а — ограничению (9).

Первая итерация. Первый этап. Составим и решим подзадачи, отвечающие начальному ДБР:

1) минимизировать

при ограничениях

2) минимизировать

при ограничениях

Оптимальные решения этих задач легко находятся графически и равны:

Найдем минимальные оценки векторов-столбцов:

Тогда оптимальные решения подзадач и образуют новые столбцы координирующей задачи, которые имеют вид:

Второй этап. Запишем ограниченную координирующую задачу, используя ее текущий базис и эти столбцы:

максимизировать (14)

при условиях

Для решения этой задачи используем метод обратной матрицы, как наиболее подходящий для реализации процедуры генерации новых столбцов, и введем их в исходное ограничение. Используя ее, получим последовательность основных таблиц 10.2–10.4 и вспомогательную таблицу 10.5, где приводятся оценки для векторов задачи. Решение, полученное в табл. 10.4 (цикл 2) , оказывается оптимальным, так как для него все оценки в табл. 10.5 будут положительными. В табл. 10.2 вводится а выводится

Таблица 10.2 Таблица 10.3

Таблица 10.4 Таблица 10.5

В результате получили новое оптимальное решение задачи

При этом значение целевой функции равно

Вторая итерация. Первый этап. Из последней строки табл. 10.4 находим вектор оценок

Используем это значение для формирования целевых функций подзадач.

Подзадача 1. Минимизировать

при условии

Подзадача2.Минимизировать

при условии

Решив эти подзадачи, получим оптимальные решения

которым отвечают следующие минимальные оценки:

и столбцы

Так как то необходимо перейти ко второму этапу.

Второй этап. Составим новую ограниченную координирующую задачу, которая включает базисные столбцы оптимального решения предыдущей задачи и новые столбцы:

минимизировать

при ограничениях

Решаем эту задачу методом обратной матрицы, использовав в качестве начального базиса оптимальный базис предыдущей координирующей задачи (табл. 10.4). Результаты решения приводятся в табл. 10.6—10.8. В табл. 10.6 выводится , вводится .