Загрузка...

Метод декомпозиции Данцига- Вульфа


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

Рассмотрим метод по этапам.

Полная главная задача или полная задача центра

Рассмотрим метод для задачи с двумя почти самостоятельными блоками, т. е. с двумя подсистемами.

Условия (2а) определяют некоторое множество решений подсистемы (2а) и одновременно некоторый многогранник D(1), пусть он ограниченный.

А условие (2б) определяет множество решений соответственно системы неравенств и одновременно некоторое ограничение многогранника D(2).

Обозначим clip_image002clip_image004— угловые точки многогранника D(1), а через clip_image006— угловые точки D(2).

clip_image008clip_image010

Каждой угловой точке соответствует опорный план и наоборот, т. е. определяя опорные планы подсистем (2а) и (2б), мы одновременно находим и угловые точки множеств D(1) и D(2).

По теореме любое решение (точку) подсистемы (2а) можно представить в виде выпуклой линейной комбинации опорных решений (угловых точек многогранника D(1)) подсистемы (2а), т. е. для любого clip_image002[1]clip_image012 имеет место:

Задача (6), построенная по всем угловым точкам многогранников D(1) и D(2), называется полной главной задачей, или полной задачей центра. Задача (6) эквивалентна задаче (1). Решив задачу (6), найдем оптимальное значение clip_image014 и clip_image016 и Zmax . Оптимальное решение исходной задачи (1) найдем по формулам (4) и (5), подставив в них значения clip_image014[1] и clip_image016[1], т. е.

Тогда clip_image018

Но для того, чтобы построить полную главную задачу, необходимо найти все угловые точки многогранников D(1) и D(2) или все опорные решения подсистем (2а) и (2б). Таких угловых точек (опорных планов) как правило много и задача (6) также как и задача (1) имеет большую размерность. Заменяя (1) задачей (6) мы облегчение не получим.

Заслуга Данцига и Вульфа состоит в том , что они показали, что для решения полной задачи центра нет необходимости или не обязательна знать заранее все опорные решения подсистем (все угловые точки), а их можно находить последовательно по мере необходимости.

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

Вводимый вектор – столбец строится по некоторой вершине многогранника D(1) или D(2).

Этап1: построение ограниченной главной задачи центра.

Пусть нам удалось по две угловые точки (по 2 опорных плана) многоугольников clip_image020 и clip_image022: clip_image024 и clip_image026. Найдем их выпуклую линейную комбинацию.

Подставим (7) и (8) в условие (3), получим следующую ограниченную главную задачу центра:

Решим эту задачу симплекс методом. Найдем ее оптимальное решение clip_image028(10) и одновременно найдем оптимальное решение двойственной задачи:

m – мерный вектор, так как clip_image030 — m – мерное. Проверим является ли решение (10) оптимальным решением полной главной задачи (6). Согласно основной теории симплекс метода решение ЗЛП является оптимальным, если оценки clip_image032 свободных переменных

Этап 2: Построение подзадач

Найдем среди оценок полной главной задачи наименьшую (относительного оптимального базиса задачи (9)). Оценки соответствующие столбцам переменных li, обозначается clip_image034, а оценки соответственно переменных mi clip_image036.

Запишем полную главную задачу заново

Решение подзадач

Математические модели подзадач записываем в матричной форме. Решение их также будем проводить в матричной форме. Поэтому следует правило умножения матриц. С учетом этого запишем подзадачи в след. виде:

Решив эту ЗЛП, мы найдем некоторую вершину многогранника D(1) (или опорное решение), для которой достигается min функции clip_image038. Обозначим эту вершину clip_image040.

Решив эту ПЗ, мы найдем некоторую вершину многогранника D(2) (или соответствующее опорное решение), для которых функция clip_image042 достигает минимального значения. Обозначим эту вершину clip_image044. Тогда clip_image046

Вершины clip_image040[1], clip_image044[1] могут быть новыми вершинами многогранника, а могут и совпадать с ранее найдеными.

clip_image049

Вершины clip_image040[2], clip_image044[2] это те вершины, которые соответствуют наименьшим оценкам столбцов полной главной задачи.

Этап 3: Условие оптимальности решения полной главной задачи

Решив подзадачи, найдем оценки clip_image051 и clip_image053

Это наименьшие оценки в полной главной задаче. Если clip_image055 и clip_image057, то решая ограниченную главную задачу, мы одновременно нашли оптимальное решение (10) ограниченной главной задачи (т. е. найденные значения clip_image059) будут одновременно и оптимальным решением полной главной задачи.

Отсюда следует, что если наименьшие оценки положительны, то должны выполняться следующие условия:

Условия (*) называется условиями оптимальности решения полной главной задачи. Выполнение их означает, что в полной главной задаче все оценки clip_image061 и clip_image063

Справедлива Теорема

План clip_image065, где clip_image067 clip_image069, является оптимальным, если для исходной задачи (1) выполняется условие оптимальности:clip_image071

clip_image073

Если хотя бы одна из оценок clip_image051[1] или clip_image053[1] является отрицательным, т. е. условие оптимальности не выполняется, то переходим к следующему этапу.

Этап 4: Построение новой ограниченной главной задачи.

Пусть среди оценок clip_image051[2] и clip_image053[2] есть отрицательная оценка или обе отрицательные. Пусть для определенности оценка clip_image079 Ей соответствует вершина многогранника clip_image081. Тогда любое решение clip_image083 представим в виде выпуклой линейной комбинации 3-х вершин, т. е.

clip_image071[1]

Подставляем эти значения в условие (3) и получаем следующею новую ограниченную главную задачу:

Находим оптимальное решение задачи: clip_image085и clip_image087 и новое оптимальное решение двойственной задачи clip_image089.

Строим новые две подзадачи, решаем их и проверяем, является ли оптимальным решение новой ограниченной главной задачи одновременно и оптимальным решением полной главной задачи, т. е. проверяем выполнение условий оптимальности (*), т. е. мы повторим этапы 2 и 3 до тех пор, пока не будут выполнены условия (*).

Пусть условия (*) выполнены для ограниченной главной задачи, которая построена с учетом вершин clip_image091 и clip_image093 и оптимальное решение ее: clip_image095. Тогда вычисляем значения clip_image097 clip_image069[1]. Тогда вектор clip_image065[1] будет оптимальным решением задачи (1).

Пример.

Дана двухуровневая система с двумя подсистемами. Центр обладает одним глобальным ресурсом в количестве 30 единиц. Каждая подсистема может выпускать по 2 продукта, используя по 2 локальных ресурса. Данные о нормах расхода ресурсов, прибыли на единицу продукции и наличии локальных ресурсов в подсистемах даны в таблицах:

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

Строим математическую модель.

Пусть 1 подсистема выпускает Х1 единиц продукции 1 вида, Х2 единиц продукции 2 вида. 2 подсистема – Х3 единиц продукции 1 вида, Х4 единиц продукции 2 вида.

Запишем отдельно почти самостоятельные блоки

Запишем эти блоки в матричной форме.

п\з следует выделить глобального ресурса x1+x2=10+6=16

Ответ: I подсистема получила от центра 16 единиц глобального ресурса и выпускает 10 единиц продукции 1 вида и 6 единиц продукции 2 вида. II подсистема от центра 14 единиц глобального ресурса и выпускает 16 единиц продукции 1 вида и 8 единиц продукции 2 вида.

Загрузка...