Реферат

з дисципліни Дослідження операцій в економіці

Блокове програмування. Метод декомпозиції Данціга-Вульфа

Виконав

студент групи Екк - ЕКК-31с

Бобеляк Ірина Євгенівна

Науковий керівник

доцент, к.е.н.

Артим-Дрогомерецька З.Б.

Львів-2011Зміст

Вступ

1. Блокове програмування

1.1 Поняття блокового програмування

1.2 Застосування блокового програмування в економіці

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

2.1 Ідея методу декомпозиції Данціга-Вульфа

2.2 Метод декомпозиції Данціга-Вульфа(загальний випадок)

3. Визначення початкових базисних планів - задач

Висновок

Список використаної літератури

Вступ

Для більшості задач лінійного програмування характерною є їх велика розмірність (наявність багатьох змінних та обмежень) і розрідженість (наявність великої кількості нульвих елементів) матриці обмежень. При розв'язування задач на макрорівні, матриця обмежень досягає розмірності 10 - 10. Класичні методи в цьому випадку виявляються малопридатними, що привело до розроблення як точних, так і наближених методів для розв'язування задач великої розмірності.[2,]

Блокове програмування є одним з розділів математичного програмування, в якому розглядаються методи зведення задач великої розмірності до послідовності задач меншої розмірності.[3]

В основному ці методи використовують прийом декомпозиції, тобто розбиття первісної задачі великої розмірності на ряд підзадач меншої розмірності, які незалежно розв'язуються за допомогою класичних методів та координіції, або узгодження незалежних розв'язків, виходячи з наявності спільних обмежень. Цей процес ітеративно повторюється до моменту отримання оптимального розв'язкузадічі загалом, або ж до того моменту коли будуть виконані умовні зупинки. [2] Метод декомпозиції, розроблений американськими вченими Дж. Данцігом та Ф. Вульфом в 1960році, а пізніше розвинутий в роботах Д.Б.Юдина, Б.Г.Гольштейна, М.Месаровича, Л.Лесдона , В.Цуркова та інших.

Поява методу декомпозиції викликана тим, що розв'язування за допомогою ЕОМ складних економічних вимагало багаторазового звертання до пасивної пам'яті машини, а це дуже збільшувало тривалість розв'язання цих задач і тим самим знижувало ефективність дії ЕОМ.

Метод декомпозиції певною мірою вирішує проблему зменшення кількості звертань до пасивної пам'яті машини при розв'язуванні задачі лінійного програмування . Це робиться шляхом зведення вихідної задачі до послідовності задач меншої розмірності.[3]

1. Блокове програмування

Блокове програмування - розділ математичного програмування, в якому розглядаються методи зведення задач великої розмірності до послідовності задач меншої розмірності, шляхом розкладу моделі на блоки.

Серед теоретичних схем блокового програмування найбільш відомі дві: метод декомпозиції Данцига--Вульфа і метод планерування на двох рівнях Корнаї--Ліптака. Обидві вони є послідовними (ітеративні) перерахунками, розв'язку головної задачі.[5]

Метод декомпозиції Данцига--Вульфа можна застосувати до для задач великої розмірності зі спеціальною матрицею обмежень. Найефективнішим цей метод виявився для задач , матриця обмежень яких має блоково-діагональну структуру (рис.1) [4] Блоково-діагональна матриця -- квадратна матриця, яку можна розбити на підматриці так, щоб лише на її головній діагоналі стояли ненульові квадратні матриці.[5]

В загальному випадку блоків може бути багато, а задачі, які мають блокову структуру можуть бути як задачами лінійного програмування, так і нелінійного програмування.[5]

Як свідчать подальші дослідження, метод декомпозиції Данцига--Вульфа можна використовувати і для задач лінійного програмування з матрицею обмежень загального вигляду.

Для задач великої розмірності, в яких частина обмежень має блоково-діагональну структуру, крім зв'язувальних обмежень, є також і зв'язувальні змінні, застосування методу декомпозиції Данцига--Вульфа призведе до ускладнення алгоритму. Тому для таких задач розроблений спеціальний метод релаксації обмежень, запропонованих Джофріоном.

Система обмежень задачі з блоково-діагональною структурою включає блок- зв'язку, що містить усі змінні , та блоки,ю кожен з яких містить тільки певну частину змінних, що не входять до інших блоків, а в сукупності вони містять усі змінні.

Для отримання діагональних блоків інколи може бути потрібно перенумерація змінних, а також зміна послідовності обмежень.

Блоком-зв'язкою називають сукупність загальних обмежень, що зв'язують між собою змінні різних блоків. Якщо такого блока-зв'язки немає, то це призводить до розпаду задачі на кілька (за кількість діагональних блоків) самостійних , незалежних між собою підзадач, що визначені окремими блоками та відповідними доданками цільової функції. Розв'язок початкової задачі складається з розв'язків окремих задач, а оптимальне значення цільової функції дорівнює сумі значень цільових функцій підзадач. Наявність блока-зв'язки початкової задачі не дає змоги розглядати окремі діагональні блоки як самостійні задачі, оскільки змінні, що входять до них, підпорядкована також і спільним обмеженням[4]

1.2 Застосування блокового програмування в економіці

Розглядаючи структуру деяких регіональних економічних задач, можна зауважити, що вони складаються з декількох часткових задач, пов'язаних певними загальними обмеженнями. Прикладом такого випадку є ситуація розвитку виробництва декількох галузей на одній території. Ці галузі можуть не залежати одна від одної, і їхній розвиток лімітований різними умовами, проте територія у них одна, а це означає, що трудові ресурси, транспортна мережа у них спільні. Спільні у них і екологічні проблеми.

Аналогічні ситуації можуть траплятися і з однією галуззю коли виробництво її продукції мало пов'язане між собою, однак існує певне число спільних обмежень, які накладаються на розвиток галузі загалом.

У такому випадку матриця умов задачі оптимального розвитку регіону чи галузі набуває спеціальної, так званої блоково-діагональної структури у вигляді :

А= (1.2.1)

де ? - число видів продукції, виробництво яких слабо пов'язане між собою ;

- матриця коефіцієнтів затрат-випуску продукції групи щ розмірності х ;

- матриця коефіцієнтів затрат-випуску у виробництві продукції тільки групи щ розмірності х ;

n - число обмежень у виробництві продукції групи щ, які впливають і

на інші групи продукції, виробництво яких оптимізуємо у регіоні загалом.

Таку структуру коефіцієнтів затрат-випуску задачі оптимізації розвитку виробництва продукції даного регіону у загальному випадку можна записати так :

F(x)= (1.2.2) (1.2.3)

(1.2.4)

, (1.2.5)

де X=() - розв'язок задачі (1.2.2)-(1.2.5);

- обмеження властиві тільки групі продуктів щ, представлених вектором -стовпчиком розмірності ;

обмеження , спільні для всіх видів продукції, представлених вектором - стовпчиком розмірності n.

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

2.1 Ідея методу декомпозиції Данціга-Вульфа

Розглянемо задачу лінійного програмування:

(2.1.1)

Нехай перші обмежень визначають блок- зв'язку, а наступні обмежень та умова - діагональний блок. Позначимо

A= ,

.

Задача (2.2.1) набуде вигляду :

(2.1.2)

Нехай - множина допустимих розв'язків задачі (2.2.2); - множина розв'язків, які відповідають блок- зв'язці: - множина невід'ємних розв'язків, які задовольняють умову діагонального блока:

==.

Згідно з теоремою про представлення будь-якої точки опуклої многогранної множини її можна подати як лінійну комбінацію її вершин та напрямних векторів необмежених ребер:

, (2.1.3)

де - вершини многогранника,

- напрямні вектори необмежених ребер, , , , ,

Якщо многогранник обмежений, то ,

Нехай множина діагонального блока - непорожній, замкнений та опуклий многогранник. [4]

Введемо позначення:

, , , .

блокове програмування декомпозиція данціг вульф

Враховуючи ці позначення задачу (2.1.2) можна записати так:

 (2.1.4)

Таким чином, початкова задача звелася до задачі лінійного програмування, невідомими якої є коефіцієнти розкладення плану через базисні плани другого блоку умов. Цю задачу будемо називати - задачею.[3]

Задача (2.1.1) має обмежень та n змінних, а - задача (2.1.4) має обмежень та N змінних. Якщо , то за кількістю обмежень - задача виграє, але кількість змінних у - задачі може бути більшою , ніж у задачі (2.1.1). Кількість змінних у - задачі дорівнює кількості вершин многогранника

В процесі побудови - задачі потрібно визначити всі вершини многокутника , що не завжди легко знаходиться. Виникає питання чи: чи потрібно переходити до - задачі при розв'язку початкової. Відповідь на це питання дає метод декомпозиції Данціга-Вульфа.[4]

У методі декомпозиції Данціга-Вульфа розв'язувати - задачу можна не знаючи всіх базисних планів, тобто не обов'язково знати всі вектори

На кожному кроці розв'язування - задачі необхідно мати тільки m+1 векторів умов - задачі, які становлять її поточну базу і один вектор , який слід увести в базу, якщо вона не оптимальна (m - кількість обмежень у першому блоці умов вихідної задачі). Що стосується вектора, який на певному кроці включається в базу, то його вибір здійснюється за допомогою деякої допоміжної задачі лінійного програмування. Множина планів в цій задачі збігається з множиною планів другого блоку умов вихідної задачі, а цільова функція будується за певним правилом і змінюється при переході від одного базисного плану - задачі до другого.

Для розв'язання - задачі Данціг і Вульф запропонували симплекс метод з оберненою матрицею. Розглянемо одну ітерацію цього методу.

Нехай -допустима база - задачі. Для того щоб перевірити цю базу на оптимальність, знайдемо найменшу серед оцінок (). Якщо вона від'ємна, то це означає, що це означає, що база B не оптимальна. Для оптимальної бази найменша серед оцінок дорівнює нулю

Отже, шукають

{} {} (2.1.5)

де - транспонований вектор коефіцієнтів лінійної форми при базисних змінних - задачі.

- рядок що має m+1 компоненту. Перші m позначають через , а останній через , тобто

=( ,) (2.1.6)

Тоді

{}={(,)*}=

={+-}=

={-()*}+= (2.1.7)

={()*}

Таким чином щоб знайти найменшу серед оцінок - задачі, відповідних базі , потрібно визначити той з базисних планів другого блоку умов {}, який надає найбільшого значення лінійній формі . Такий план можна визначити , якщо симплексним методом розв'язати задачу

(2.1.8)

Цю задачу називають - задачею. Отже для перевірки на оптимальність бази - задачі слід побудувати і розв'язати - задачу. Якщо умови вихідної задачі сумісні, то з припущення що множина R обмежена, випливає, що - задача має розв'язок. Якщо оптимальне значення лінійної форми - задачі дорівнює , то {}=о, а це означає, що база B - задачі є оптимальною. Якщо ж оптимальне значення лінійної форми - задачі, яке досягається на базисному плані ( - оптимальний план - задачі), більше за , то {}=о, а це свідчить про не оптимальність бази B - задачі і означає, що для поліпшення плану - задачі базу слід ввести вектор

Якщо для бази виконується умова оптимальності, то перехід до оптимального плану вихідної задачі здійснюється за формулою

(2.1.9)

а через те, що серед лише m+1 компонента може не дорівнювати нулю, то значення векторів - відповідних вільним змінним оптимального базисного плану - задачі, для визначення оптимального плану вихідної задачі є непотрібні.

Коли ж база не є оптимальна, то дальше розв'язування задачі виконується згідно з правилами симплексного методу з оберненою матрицею, тобто обчислюється розв'язковий стовпець , визначається розв'язковий елемент, за відомими формулами обчислюються елементи нової оберненої матриці, вільні члени, а також

Якщо - задача має канонічну форму, то зведення її до канонічної форми проводить до появи додаткових векторів , тому крім оцінки основних векторів , необхідно врахувати і оцінки додаткових векторів. Проведені ними міркування не поширюються на ці вектори, оскільки вони не пов'язані з базисними планами другого блоку умов вихідної задачі. Оцінки для додаткових векторів визначаються таким чином: оскільки

і-та компонента

І в цільовій функції - задачі вектором відповідають нульові коефіцієнти , то за вже розглянутою формулою отримаємо

() (2.1.10)

Таким чином, база - задачі при наявності додаткових векторів є оптимальною, якщо невід'ємними є оцінки всіх основних векторів і невід'ємними

Тому в цьому випадку для введення в базу - задачі вектора з найменшою оцінкою, необхідно з чисел {}, вибрати найменше.

Якщо це число дорівнює {}=, то в базу введеться вектор :

, (2.1.11)

а якщо , то - вимірний вектор

і-та компонента

2.2 Метод декомпозиції Данціга-Вульфа(загальний випадок)

Відмовляються від припущення, що множина є обмеженою.

Нехай є множиною всіх базисних планів, - множина всіх спрямовуючих векторів нескінченних ребер множини . Тоді довільний план множини можна подати у вигляді:

, ( 2.2.1)

причому

( 2.2.1)

де

Переходять від початкової задачі до - задачі подібно до того, як це було зроблено в попередньому пункті:

( 2.2.2)

де

Для перевірки допустимої бази - задачі на оптимальність слід перевірити, чи серед оцінок

( 2.2.3)

є від'ємні.

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

- задачі:

( 2.2.3)

дає можливість встановити, оптимальною чи ні є база - задачі

При цьому можна одержати або найменшу, або від'ємну оцінку. Розв'язання - задачі може закінчитися одним з випадків:

а)одержанням оптимального плану;

б)виявлення необмеженості лінійної форми

Якщо при розв'язуванні задачі симплексним методом на деякій ітерації отримують базисний план з базою , невід'ємною оцінкою і недодатнім розв'язковим стовпцем, говорять що лінійна форма такої задачі є не обмежена на множині допустимих планів.

3. Визначення початкових базисних планів - задач

Якщо вихідна задача має вигляд

( 3.1)

причому вектор та невід'ємні, то початковий базисний план - задачі визначити просто. У цьому випадку в - задачі потрібно знайти

=

(3.2)

де

Е - одинична матриця розмірності х

Першим стовпцем початкової бази можуть бути стовпці коефіцієнтів при змінних (). Останнім стовпцем початкової бази може бути стовпчик , коефіцієнтів при змінній , яка відповідає базисному плану множини .

Стовпець є також одиничним

(3.2)

Таким чином, початкова база і обернена до неї матриця для даної задачі є одиничними матрицями.

Слід зауважити, що при розв'язанні цієї задачі, перевіряючи базисні плани - задачі на оптимальність, крім оцінок змінних , , слід розглядати також оцінки , змінних , . Через те що

(3.3)

де - одиничний - мірний вектор

та , то

, (3.3)

Тому якщо хоч одна компонента вектора від'ємна , то план - задачі не оптимальний і в базу для поліпшення його можна ввести вектор .

У протилежному випадку для перевірки плану - задачі на оптимальність будується та розв'язується - задача.

Якщо обмеженнями вихідної задачі є рівняння, то початковий план - задачі може бути визначений шляхом побудови і розв'язання такої допоміжної задачі :

}

Ця задача має очевидний початковий план:

, ,,

а для розв'язання її також доцільно використовуваним симплекс метод з оберненою матрицею. Оцінки змінних цієї задачі :

,

та

, ,

Тому при розв'язанні допоміжної задачі для перевірки умови оптимальності базисних планів перевіряємо, чи ,, і розв'язуємо задачі, подібні до - задачі:

Правильними є такі твердження: якщо оптимальне значення лінійної форми допоміжної задачі дорівнює нулю, то її оптимальний план є допустимими для - задачі; а якщо ж це значення від'ємне, то умови - задачі, а отже й вихідної задачі є несумісні.

Якщо початковий базисний план - задачі не є очевидним, то можна також перейти до розв'язання так званої - задачі:

}

де - достатньо велике додатне число. Ця задача має очевидний початковий базисний план :

, ,,

Оцінки змінних цієї задачі:

,

та

отже аналіз добутку та розв'язання - задачі дає можливість на кожній ітерації перевірити базисний план цієї задачі на оптимальність і визначити вектор, який слід увести в базу, якщо це план виявляється не оптимальний.

4. Алгоритм методу декомпозиції

1) Визначення початкових базисних планів - задачі та заповнення початкової таблиці

2) Обчислення компонент вектора за формулою

3) Обчислення добутку

4) Побудова та розв'язання - задачі:

На кожній ітерації розв'язання - задачі, починаючи з другої , початковим планом - задачі доцільно брати останній план - задачі, одержаний на попередній ітерації розв'язання - задачі

При розв'язанні - задачі може трапитися один із двох випадків:

а) Одержано оптимальний план. У цьому перевіряємо чи виконується рівність ,

- якщо так, то це свідчить про оптимальність плану - задачі. Тоді переходять до пункту 6;

- якщо ні, то обчислюють вектор і переходять до пункту 5.

б) Лінійна форма - задачі не обмежена, тобто одержано симплекс таблицю - задачі з і недодатніми елементами -го стовпця. У цьому випадку будуємо спрямовуючий вектор нескінченного ребра так: компоненти цього вектора, номери яких дорівнюють номерам базисних компонент останнього плану - задачі, беруться за рівні відповідним елементам -го стовпця, помноженими на (-1), -та компонента береться за рівну 1 , а всі решта - 0. Після цього обчислюємо вектор і переходять до пункту 5

5) Вектор заносять в симплекс таблицю - задачі, обчислюють елементи розв'язкового стовпця і виконують перехід до наступного плану - задачі. Після цього переходять до пункту 2

6) Обчислюють оптимальний план вихідної задачі. Оптимальне значення вихідної задачі дорівнює оптимальному значенню лінійної форми - задачі

Список використаної літератури

1. Вовк В.М., Дрогомирецька З.Б. Основи системного аналізу. Навч. посібник. - Львів : ВЦ ЛНУ ім. Івана Франка, 2002. - 248с

2. Катренко А.В. Дослідження операцій: Підручник. - Львів: Магнолія Плюс, 2004.- 549с.

3. Мачкур А.Є., Ланьош О.М.. Блокове програмування. Навч. посібник. - Львів, ЛДУ, 1998

4. Федоренко І.К., Черняк О.І. Дослідження операцій в економіці: Підручник. - К.: Знання, 2007. - 558 с.

5. Акулич И.А. Математическое програмирование в примерах и задачах: Учеб. пос. для студ. эконом. спец. - М.: Высшая школа, 1986. - 319 с.

Размещено на Allbest.ru