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

РЕШЕНИЕ БЛОЧНЫХ  ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ДАНЦИГА-ВУЛФА

Метод декомпозиции Данцига  и Вульфа представляет собой специализированный вариант симплекс-метода.

В 1960 г. Данциг и Вульф  разработали метод декомпозиции для решения задач высокой  размерности со специальной структурой матрицы ограничений [1].

Этот метод оказался наиболее эффективным для решения  задач, матрица ограничений которых  имеет блочно-диагональный вид с небольшим числом переменных. Однако, как показали дальнейшие исследования, метод применим также и для задач ЛП с матрицей общего вида. Соответствующий метод предложен Д.Б.Юдиным и Э.Г.Гольштейном и называется 'блочным программированием'.

Отличительной особенностью метода декомпозиции является использование координирующей задачи, которая имеет, по сравнению с исходной, небольшое число строк и большое число столбцов.

 

     При решении задач  по специализации цехов (родственных  цехов, которые могут выпускать одну и ту же продукцию) определяют в основном загрузку мощностей отрасли.

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

     В блочной задаче обычно используются следующие уравнения-ограничения:

• по плану производства,
• по ресурсам (по фонду рабочего времени оборудования или по материальным ресурсам).

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

Матрица.

 

 

 

  Х₁₁   Х₁₂  …Х₂₀

             *а_ij =0

            (свободное 

                 пространство) 

 

 Как правило, *а_ij ≠0

«А» (занятое коэффици-    

ентами пространство)          

*а_ij =0                                                                                            (свободное пространство)

        Х_n-2   Х_n-1 …Х_n

 

 

 

 

 

 

 

 

 

«В»

 

……………………………………………………………………………

 

ФЦ

 

 

Ограничения типа “А” местные, а  ограничения типа “В” являются общими и охватывают всю отрасль (компанию).

a₁x₁ + a₂x₂ + … + a_nx_n £ b

Пояснения:

1. В блоки предприятий (заводов, цехов) входят ограничения типа «А», описывающие внутренние производственные возможности предприятий:

• различные применяемые технологические схемы (процессы);
• производственные мощности (например, фонд времени);
• природные ресурсы (например, местные сырьевые источники);
• транспортные средства;
• другие лимитирующие факторы по данному заводу (предприятию, цеху).

2. Общие для всех или ряда предприятий ограничения типа «В», связывающие блоки, отражают условия 3-х видов:

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

     Целевая  функция задачи отражает требования  либо максимизации выпуска конечной  продукции в ценностном исчислении  или заданном сортаменте (или  максимум прибыли), либо минимизации  издержек при заданном объеме конечной продукции.

Характеристика  метода разложения (декомпозиции) решения  блочных задач

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

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

 

Задача  решается в несколько этапов:

 

1-й этап  решения: находятся базисные решения подзадач для каждого предприятия.

2-й этап  решения: полученные для каждого предприятия планы анализируются с точки зрения     выполнения условий, охватывающих все предприятия. При этом возможно, что:

• по некоторым общим ресурсам лимит превышен,
• некоторые конечные продукты выпускаются в недостаточном количестве.

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

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

4-й этап  решения: принимается во внимание, что если два предыдущих варианта плана допустимы с точки зрения каждого предприятия, то допустимыми будут и промежуточные планы. На базе этой предпосылки отыскивается комбинация усредненных планов предприятий, полученных на 1-ом и 3-ем этапах решения (удовлетворяющих общим ограничениям и максимизирующих прибыль в целом по объединению).

 

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

 

 

Предприятие №1   Предприятие №2

 

                                                                                                                                                                                                                                                    Х₁                       Х₂                                   Х₃                    Х₄     

 

Внутренние возможности:

  Предприятие №1   Предприятие №2

Ресурс №1: х₁+ 0,1х₂ ≤ 10             Ресурс №3: 2х₃+ х₄ ≤ 50

Ресурс №2:             х₂ ≤ 20              Ресурс №4:   х₃           ≤ 20

 

Общий ресурс №5:

4х₁ + х₂ + 2х₃ + х₄ ≤ 80

Прибыль, которую может получить объединение:

 х₁ + 2х₂ + 3х₃ + х₄ = С _(max)

х₁, х₂, х₃, х₄ ≥ 0

 

 

1-й этап решения:

  Предприятие №1   Предприятие №2

              х₁+ 0,1х₂ ≤ 10                   2х₃+ х₄ ≤ 50

                         х₂ ≤ 20                      х₃           ≤ 20

              х₁ ≥ 0; х₂ ≥ 0                                            х₃ ≥ 0; х₄ ≥ 0

Ф.ц.: х₁ + 2х₂→max      Ф.ц.: 3х₃ + х₄→max

Решение:        Решение:

              х₁ = 8; х₂ = 20                                           х₃ = 20; х₄ = 10

Прибыль: 48 руб.       Прибыль: 70 руб.

Общая прибыль: 48+70=118 руб.

2-й этап решения:

(анализируется расход общего  ресурса).

На 1-ом этапе не учитываются ограничения  по общему ресурсу.

По условию:  4х₁+ 1х₂ + 2х₃+ х₄ ≤ 80

Потребное количество общего лимитированного  ресурса на 1-ом этапе решения задачи:

               4х₈+ 1х₂₀             +          2х₂₀+ 1х_{10        =}  100>80

    Предприятие №1        Предприятие №2

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

3-й этап решения:

  Предприятие №1   Предприятие №2

              х₁+ 0,1х₂ ≤ 10                   2х₃+ х₄ ≤ 50

                         х₂ ≤ 20                      х₃           ≤ 20

              х₁ ≥ 0; х₂ ≥ 0                                            х₃ ≥ 0; х₄ ≥ 0

Ф.ц.: с учетом штрафа  Ф.ц.:  с учетом штрафа

(1-1*4)х₁ +(2-1*1)х₂=  (3-1 х₂)х₃+ (1-1*1)х₄=

= -3х₁+ х₂ →max!    =1х₃ + 0х₄→max!

Решение:        Решение:

              х₁ = 0; х₂ = 20                                           х₃ = 20; х₄ = 0

Прибыль: 20 руб.       Прибыль: 20 руб.

Общая прибыль: 20+20=40 руб. (с учетом штрафа).

Без учета ограничения по общему ресурсу, но со штрафом за каждую использованную единицу этого ресурса.

Без учета штрафа :  2*20 + 3*20 + 1*0=100 руб.

Расход лимитированного общего ресурса:

               4*0+ 1*20         +    2*20+ 1*0        ₌  60<80

    Предприятие №1  Предприятие  №2

Для каждого предприятия мы получим  по 2 плана. Оба плана достижимы.

 4-й этап решения:

На этом этапе находят средние планы, полученные на 1 и 3 этапах, которые будут удовлетворять условию по общему ресурсу. Условия-ограничения по общему ресурсу с усреднением планов, полученных для каждого предприятия на 1 и 3 этапах решения задачи, формализуются следующим образом: обозначим веса (доли) планов:

1. Для 1-го предприятия:

λ₁ – доля первого плана;   λ₂ – доля второго плана;

при этом   λ₁ + λ₂ = 1

2. Для 2-го предприятия:

     μ₁- доля первого плана; μ₂ – доля второго плана;

     при этом μ₁+ μ₂ = 1

 

 

 

Условие по расходу общего ресурса запишем так:

 

   (4*8 + 1*20) λ₁    +    (4*0 + 1*20) λ₂    +     (2*20 + 1*10) μ₁+ (2*20 + 1*0)μ₂ ≤ 80

   расход общего           расход общего

ресурса по 1 плану   ресурса по 2 плану        х₃          х₄              х₃         х₄

 После преобразования:

   52λ₁ + 20λ₂ + 50μ₁+ 40μ₂ ≤ 80  ₍₁₎       Уравнения-ограничения задачи на 4 этапе

       λ₁ + λ₂ = 1                              ₍₂₎          λ₁

        μ₁+ μ₂ =1                                ₍₃₎

   λ₁ ≥ 0; λ₂ ≥0; μ₁ ≥ 0; μ₂ ≥ 0        ₍₄₎

 

Функция цели (максимум общей прибыли) может быть записана следующим образом:

   (1*8 + 2*20) λ₁ + (1*0 + 2*20) λ₂ + (3*20 + 1*10) μ₁+ (3*20 + 1*0)μ₂ →С(max)

После преобразования:  48λ₁ + 40λ₂ + 70μ₁+ 60μ_2 = С(max)

 

Иногда задачу 4 этапа называют главной задачей, она имеет следующее решение:

48λ₁=10/32;  λ₂=22/32; μ₁=1;  μ₂ =0.

Взяв соответствующие доли 1 и 2 планов предприятия №1, получим:

Х₁= 10/32*8 + 22/32*0 = 2,5

Х₂= 10/32*20 + 22/32*20 = 20

Для предприятия №2:

Х₃= 1*20 +  0*20 = 20

Х₄= 1*10 + 0*0 = 10

Прибыль: 1*2,5 + 2*20 + 3*20 + 1*10 = 112,5 руб. Что меньше, чем прибыль по 1 плану (118 руб.)

Расход общего ресурса:

4*2,5 + 1*20 + 2*20 + 1*10 = 80, т.е. общий ресурс не перерасходован.