11766

Тема 1. Двоїстий та модифікований симплекс-метод. Блочні задачі ЛП

Практическая работа

Математика и математический анализ

Двоїстий та модифікований симплексметод. Блочні задачі ЛП Пряма та двоїста задачі лінійного проґрамування. Зв’язок між розв’язками прямої та двоїстої задач. Отримання оптимального розв’язку двоїстої задачі за допомогою симплексметоду. Економічна інтерп

Украинкский

2013-04-11

876 KB

31 чел.

  1.  Двоїстий та модифікований симплекс-метод. Блочні задачі ЛП
  2.  Пряма та двоїста задачі лінійного проґрамування.
  3.  Зв’язок між розв’язками прямої та двоїстої задач.
  4.  Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу.
  5.  Економічна інтерпретація задач лінійного проґрамування.
  6.  Двоїстий симплекс-метод.
  7.  Модифікований симплекс-метод.
  8.  Блочні задачі лінійного проґрамування. Метод Данціґа-Вулфа. 
    1.  Пряма та двоїста задачі лінійного проґрамування

Для прямої задачі ЛП справедливі наступні співвідношення:

, .

Двоїста відносно прямої задача ЛП в канонічній формі має вигляд:

, .

Відповідно в матричній формі пряма задача зображається як

, а двоїста – , або  .

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

                       Змінні прямої задачі

x1

x2

xj

xn

c1

c2

cj

cn

a11

a12

a1j

a1n

b1

y1

a21

a22

a2j

a2n

b2

y2

am1

am2

amj

amn

bm

ym

 Змінні

 двоїстої

 задачі

Приклад.

Q= 5x1+12x2 +4x3 Max,

       x1+  2x2+   х3       < =10                         

     2x1 -    x2 + 3х3          =  8

       x1 >=0, x2 >=0, x3 >=0.

Приводимо задачу до канонічної форми:

Q= 5x1+12x2 +4x3   +0x4 Max,

       x1+  2x2+   х3  +  х4      =10      y1                    

     2x1 -    x2 + 3х3 +0x4      =  8        y2

       x1 >=0, x2 >=0, x3 >=0, x4 >=0

Умова двоїстої задачі:

G= 10y1+ 8y2  Min,

         y1+ 2y2   > =  5                         

        2y1-    y2   > = 12

         y1+ 3y2   > =  4

y1+ 0y2   > =  0,

y1, y2   >< 0.

Двоїста задача до двоїстої буде первісною прямою задачею, тобто, якщо A — пряма задача, D{A} — двоїста до A, то A=D{D{A}}. Покажемо, що це насправді так.

Тепер переходимо до двоїстої задачі:

  1.  Зв’язок між розв’язками прямої та двоїстої задач

Зв’язок між розв’язками прямої та двоїстої задач встановлюється за допомогою двох теорем двоїстості. Для їх доведення використаємо наступну лему.

Лема.

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

Доведення.

Нехай  та  — припустимі розв’язки прямої та двоїстої задач, тобто  Помножимо перший вираз на  зліва, а другий — на  справа: , . Порівнюючи ці вирази, отримаємо .

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

1-а теорема двоїстості.

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

Доведення.

Запишемо задачу ЛП в перетвореному вигляді:

,

, , де .

На останній ітерації — в останній симплекс-таблиці розв’язок є оптимальним,  , тобто . Введемо позначення . Тоді , , і об’єднуючи ці обидва вирази , отримаємо .

Таким чином  — припустимий розв’язок двоїстої задачі. Доведемо, що  — оптимальний розв’язок двоїстої задачі: . Таким чином значення функції мети для двоїстої задачі для  її припустимого розв’язку  дорівнює значенню функції мети  прямої задачі для її припустимого розв’язку . Згідно до леми це означає, що   є оптимальним розв’язком двоїстої задачі.

Доведемо другу частину теореми.

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

Примітка.

Твердження, обернене до 2-ї частини теореми 1, взагалі кажучи, є недійсним, тобто, якщо одна з пари двоїстих задач має пусту множину припустимих розв’язків, то інша не обов’язково повинна мати необмежену функцію мети. Обидві задачі можуть бути неприпустимими, наприклад:

Q= 2x1-x2   Max,

       x1- x2 =1      y1                    

      -x1+x2 =1      y2

          x1 >=0, x2 >=0           Область припустимих розв’язків .

Умова двоїстої задачі:

G= y1+ y2  Min,

     y1 - y2   > =  5                         

        2y1-    y2   > =  2

        -y1+  y2   > = -1       Область припустимих розв’язків .

Теорема 2.

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

Ця теорема може бути також сформульована у наступному еквівалентному вигляді. Розв’язки ,  є оптимальними тоді і лише тоді, якщо виконуються співвідношення:

,

.

Ця теорема дає можливість за оптимальним розв’язком однієї з задач знайти оптимальний розв’язок двоїстої до неї.

Доведення.

Нехай для кожного , для якого , маємо . Тоді . Справді, ті складові, для яких , фактично рівні нулю, оскільки для них . Залишаються до розгляду лише ті складові, для яких , що доводить справедливість рівності. Після перегрупування суми отримаємо . Оскільки  - припустимий розв’язок прямої задачі, то суми в дужках рівні відповідним значенням , тобто  і згідно до леми ці розв’язки є оптимальними.

  1.  Нехай тепер навпаки, відомо, що ,  — оптимальні розв’язки прямої та двоїстої задач. Тоді за першою теоремою двоїстості  . Оскільки  — припустимий розв’язок задачі, то  . Підставляючи ці вирази в рівність та перегруповуючи складові в лівій частині, отримаємо: . Якщо хоча б для одного j, для якого , було б , то попереднє співвідношення не виконувалося б. Тобто дійсно, для кожного j, для якого б виконувалося попередня строга нерівність, отримуємо , що й потрібно було довести
    1.  Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу

Розглянемо можливості отримання оптимального розв’язку двоїстої задачі з оптимального розв’язку (за допомогою останньої симплекс-таблиці) прямої задачі.

Приклад.

Пряма задача.

Q= 3x1+2x2   Max,

x1+2x2<=6                       x1+2x23                                   =6       y1                   

2x1+x2<=8                      2x1+x2             4                         =8       y2

-x1+x2<=1                       -x1+x2                       5                =1       y3

x2<=2                                    x2                                6       =2       y4

x1 >=0       x2 >=0                  xj>=0

Кожне обмеження прямої задачі відповідає змінній двоїстої задачі, кожна змінна прямої задачі відповідає обмеженню двоїстої. Запишемо умову двоїстої задачі:

Двоїста задача.

6y1+ 8y2 +  y3  +  y4   Min,

   y1+ 2y2 -   y3             >=3 

2y1+   y2 +  y3  +  y4      >=2

y1>=0  y2 >=0   y3 >=0   y4>=0.

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

c1

c2

c3

c4

c5

c6

xb

cb

P0

3

2

0

0

0

0

P1

P2

P3

P4

P5

P6

x2

2

4/3

0

1

2/3

-1/3

0

0

x1

3

10/3

1

0

-1/3

2/3

0

0

x5

0

3

0

0

-1

1

1

0

x6

0

2/3

0

0

-2/3

1/3

0

1

Q

38/3

0

0

1/3

4/3

0

0

Початкові базові змінні: x3, x4, x5, x6.

Різниця між лівою та правою

частинами обмеження двоїстої

задачі, яке асоційоване з цією

початковою змінною

  =   

Для визначення оптимальних значень змінних двоїстої задачі згідно до теорем двоїстості складаємо рівняння:

Коефіцієнт       при

початковій  базовій змінній в рядку прямої задачі  

Це ж співвідношення в звичній формі: , .

Відповідні співвідношення для прикладу:

1/3 = y1 - 0     x3  

4/3 = y2 - 0     x4  

1/3 = y3 - 0     x5  

1/3 = y4 - 0     x6  

<=

Наслідком з 1-ї теореми є те, що для будь-якої пари припустимих розв’язків прямої та двоїстої задачі:


Значення функції мети

в задачі максимізації

Значення функції мети

в задачі мінімізації

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

  1.  Економічна інтерпретація задач лінійного програмування

Розглянемо пряму та двоїсту задачі ЛП:

Пряма задача:

, .

Двоїста задача: 

, .

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

В цій інтерпретації:

індекс видів ресурсів, що застосовуються для виробництва всіх продуктів;

індекс видів продуктів, що можуть продукуватися;

кількість продукції го типу, яка випускається;

прибуток від реалізації одиниці го продукту;

величина запасу  го ресурсу;

кількість го ресурсу, що витрачається на виробництво одиниці го продукту;

прибуток від реалізації продукції.

Коефіцієнт       при  змінній  в рядку прямої задачі

Різниця між лівою та правою

частинами обмеження двоїстої

задачі, яке асоційоване з цією

початковою змінною

 =   

Для подальшого аналізу використаємо результати теорем двоїстості, власне співвідношення , тобто змістовно

а також рівність значень функцій мети для прямої та двоїстої задачі в оптимальній точці.

Використаємо співвідношення  для змістовної інтерпретації змінних двоїстої задачі. Перепишемо це співвідношення у вигляді  і визначимо розмірність y:

.

Звідси розмірність змінних двоїстої задачі:, тобто  є цінністю ресурсу (його тіньовою ціною). Для неоптимального розв’язку , тобто (прибуток)<=(цінність ресурсу), іншими словами цінні ресурси не використані повністю, і можливе збільшення прибутку за рахунок використання відповідних видів виробничої діяльності (випуску продукції певних видів).

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

.

Тобто, якщо , то відповідний вид виробничої діяльності повинен бути введений в базу (з  випливає, що ).

  1.  Двоїстий симплекс-метод

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

.

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

В двоїстому симплекс-методі спочатку отримуємо розв’язок “кращий, ніж оптимальний” (надоптимальний), але неприпустимий. Двоїстий  СМ забезпечує виконання умови оптимальності та наближення кожного наступного біжучого розв’язку до області припустимих розв’язків. В момент, коли отриманий розв’язок виявляється припустимим, процес розв’язування закінчується, так як останній розв’язок є оптимальним і припустимим.

Всі значення  , і це співвідношення зберігається на кожній ітерації двоїстого СМ. Деякі елементи стовпчика  є від’ємними. Перехід від одного біжучого розв’язку до іншого здійснюється до моменту, поки з   не будуть виключені від’ємні елементи.

Алгоритм двоїстого СМ включає наступні кроки:

  1.  Знаходження початкового надоптимального розв’язку.

Перевірка біжучого надоптимального розв’язку на припустимість (Якщо в стовпчику  відсутні від’ємні значення, то знайдений оптимальний розв’язок. Стоп. ).

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

Переходимо до наступного надоптимального розв’язку так само, як і в звичайному СМ, використовуючи схему Ґауса-Жордана.

Приклад.

- 4x1- 7x2 - 8x3  - 5x4   Max,

      x1+ x2            +2x4  >=4                        x1+ x2            +2x4  - x5       >=4

 2x1+ x2 +2x3             >=2              2x1+ x2 +2x3                  - x6  >=2

x1>=0  x2 >=0   x3 >=0   x4>=0.

c1

c2

c3

c4

c5

c6

xb

cb

P0

-4

-7

-8

-5

0

0

P1

P2

P3

P4

P5

P6

x5

0

-4

-1

-1

0

-2

1

0

x6

0

-6

-2

-1

-2

0

0

1

Q

0

4

7

8

5

0

0

x5

0

-1

0

-1/2

1

-2

1

½

x1

-4

3

1

½

1

0

0

-1/2

Q

-2

0

5

4

5

0

2

x4

-5

½

0

¼

-1/2

1

-1/2

-1/4

x1

-4

3

1

½

1

0

0

-1/2

Q

-29/2

0

2

13/2

0

5/2

13/4

  1.  Модифікований симплекс-метод

В варіантах симплекс-методу, що розглядалися раніше, при реалізації послідовних ітерацій — переході від попередньої до наступної симплекс-таблиці — використовувався метод Ґауса-Жордана, при застосуванні якого для автоматизації розрахунків необхідний великий об’єм пам’яті. З метою усунення  такого недоліку застосовується модифікований симплекс-метод, що являє собою різновид симплекс-методу, який крім того дозволяє в багатьох випадках зменшити ще й загальну кількість арифметичних операцій. Суттєвою в цьому методі є реалізація процедури обчислення оберненої матриці .

Основні кроки модифікованого симплекс-методу не відрізняються від класичного (різниця полягає в деталях реалізації) і утворюють наступну послідовність:

  1.  Знаходження початкового базового розв’язку.
  2.  Розрахунок матриці , що являє собою обернену до матриці , яка складається з векторів початкової бази.
  3.  Розрахунок компонент вектору .
  4.  Обчислення значень критеріїв оптимальності досягнутого текучого розв’язку задачі ЛП . Якщо  то знайдений біжучий розв’язок є оптимальним — робота алґоритму зупиняється. В іншому випадку обирається  — найбільше за абсолютним значенням від’ємне число.
  5.  Обчислення компонент вектору  у вихідній базі. Якщо серед цих компонент немає додатніх, то функція мети не обмежена на множині припустимих розв’язків — стоп. Якщо ж серед компонент вектору є додатні, то перехід до наступного базового розв’язку.
  6.  Знаходження ведучого рядка за відомими правилами симплекс-методу та обчислення компонент нового базового розв’язку і матриці  , що є тепер матрицею, оберненою до матриці компонент векторів нового базового розв’язку.
  7.  Перевірка нового розв’язку на оптимальність. Якщо розв’язок неоптимальний, то перехід до кроку 3.

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

xb

cb

P0

c1

c2

...

cn

...

P1

P2

...

Pn

x1

c1

b1

x11

x12

...

x1n

...

x2

c2

b2 

x21

x22

...

x2n

...

.

.

.

.

.

...

.

...

...

...

xi

ci

bi 

xi1

xi2

...

xin

...

.

.

.

.

.

...

.

...

...

...

xm

 сm

bm 

xm1

xm2

...

xmn

...

...

...

...

...

...

...

...

...

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

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

замість стовпчиків векторів Рj з відповідними значеннями сj записуються стовпчики векторів Aj, координатами яких є відповідні стовпчики матриці B-1 ;

в (m+1)- му рядку записуються компоненти вектору , а не знгачення ;

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

xb

cb

P0

А1

А2

...

Аn

Ps

x1

c1

b1

a11

a12

...

a1n

x1s

x2

c2

b2 

a21

a22

...

a2n

x2s

.

.

.

.

.

...

.

xi

ci

bi 

ai1

ai2

...

ain

xis

.

.

.

.

.

...

.

xm

 сm

bm 

am1

am2

...

amn

xms

...

Для того, щоб знайти вектор Рs , спочатку знаходимо вектор  компоненти якого визначаються як скалярний добуток вектору  на відповідні вектори  (знайдені значення записуємо в останньому рядку основної таблиці та у відповідному стовпчику додаткової таблиці). Після цього розраховуємо елементи відповідного -рядка  допоміжної таблиці. Якщо всі компоненти цього рядка невід’ємні, то знайдено оптимальний розв’язок. В іншому випадку , якщо задача має розв’язок, здійснюється перехід до наступного. В останньому стовпчику основної таблиці записуємо компоненти вектора , розкладені за векторами біжучої бази. Ці значення отримуємо в результаті множення матриці   основної таблиці на вектор  допоміжної таблиці. Далі знаходимо ведучий рядок і за відомими правилами переходимо до наступної основної таблиці.

Приклад.

Розв’яжемо за допомогою модифікованого симплекс-методу задачу, яку ми вже розв’язали звичайним симплекс-методом.

               Q= 3x1+2x2   Max,

                       x1+2x23                                   =6                         

                     2x1+x2             4                         =8

                     -x1+x2                       5                =1

                            x2                                6       =2

                                        x1 >=0       x2 >=0            

Ця задача має початковий базовий розв’язок x=(0; 0; 6; 8; 1; 2), що визначається векторами P3, P4, P5, P6. Складовім цих векторів визначають одиничну матрицю , обернена до якої теж є одиничною.

Складаємо основну та допоміжну таблиці. В допоміжній таблиці заповнюємо 4 рядки стовпчиків векторів, а в основній — перші 4 рядки, враховуючи що обернена до одиничної матриці є одиничною матрицею.

Допоміжна таблиця

c1

c2

c3

c4

c5

c6

xb

cb

P0

3

2

0

0

0

0

P1

P2

P3

P4

P5

P6

x3

0

6

1

2

1

0

0

0

0

0

1/3

x4

0

8

2

1

0

1

0

0

0

3/2

4/3

x5

0

1

-1

1

0

0

1

0

0

0

0

x6

0

2

0

1

0

0

0

1

0

0

0

-3

-2

0

0

0

0

0

-1/2

0

3/2

0

0

0

0

1/3

4/3

0

0

Визначаємо вектор , записуючи його в основну таблицю:

 

Розрахуємо також значення функції мети та запишемо його в 1-у основну таблицю. Після заповнення 1-го додаткового рядка основної таблиці значення компонент  перепишемо в 1-й додатковий стовпчик додаткової таблиці.

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

В базу необхідно ввести вектор  Р1. Тому цей стовпчик з додаткової таблиці, розкладений за векторами наявної бази (для цього множимо обернену матрицю, наявну в стовпчиках А 1-ї основної таблиці, на вектор Р1 в додатковій таблиці )  дописуємо в 1-у основну таблицю.

1-а основна таблиця

xb

cb

P0

А1

А2

А3

А4

P1

x3

0

6

1

0

0

0

1

6/1=6

x4

0

8

0

1

0

0

2

8/2=4

x5

0

1

0

0

1

0

-1

x6

0

2

0

0

0

1

0

0

0

0

0

0

-3

З бази за правилами звичайного симплекс-методу виводимо х4. Число 2 є ведучим елементом. Виконуємо перехід до нової основної таблиці симплекс-методу.

2-а основна таблиця

xb

cb

P0

А1

А2

А3

А4

P2

x3

0

2

1

-1/2

0

0

 3/2

4/3

x1

3

4

0

1/2

0

0

1/2

8

x5

0

5

0

1/2

1

0

3/2

10/3

x6

0

2

0

0

0

1

1/2

4

12

0

3/2

0

0

-1/2

Визначаємо вектор , записуючи його в основну таблицю:

.

Обчислюємо  в основній таблиці. До бази вводимо Р2 , записуємо в 2-гу основну таблицю його представлення за векторами нової бази:

З бази виводимо х3 , а вводимо Р2 . Переходимо до наступної основної симплекс-таблиці.

3-я основна таблиця.

xb

cb

P0

А1

А2

А3

А4

x2

 2

4/3

 2/3

-1/3

0

0

x1

3

10/3

-1/3

2/3

0

0

x5

0

3

-1

1

1

0

x6

0

2/3

-2/3

1/3

0

1

38/3

1/3

4/3

0

0

Розраховуємо значення . Оскільки всі його компоненти невід’ємні, то знайдений оптимальний розв’язок.

  1.  Блочні задачі лінійного програмування та підходи до їх розв’язування

Для більшості практичних задач ЛП характерною є їх велика розмірність (наявність багатьох змінних та обмежень) і розрідженість (наявність великої кількості нульових елементів) в матриці обмежень. Класичні методи в цьому випадку виявляються малопридатними, що привело до розроблення як точних, так і наближених методів для розв’язування задач великої розмірності такого типу. В основному ці методи використовують прийом декомпозиції, тобто розбиття первісної задачі великої розмірності на ряд підзадач меншої розмірності, які незалежно розв’язуються за допомогою класичних методів, та координації, або узгодження незалежних розв’язків, виходячи з наявності спільних обмежень. Цей процес ітеративно повторюється до моменту отримання оптимального розв’язку задачі загалом, або ж до того моменту, коли будуть виконані умови зупинки.

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

, де  - підматриці. Змістовно задачу такого типу можна розглядати наступним чином. До складу фірми, що випускає певні вироби,  входить  відділень, кожне з яких для виробництва використовує незалежні від інших відділень автономні ресурси (для -го відділення норми витрат незалежних ресурсів відображаються підматрицею . Окрім того, в розпорядженні керівництва фірми є спільні ресурси, норми витрат яких задані зв’язуючим рядком  матриці обмежень. Необхідно побудувати такий план виробництва, для якого б досягався максимальний прибуток фірми загалом.

Відповідна задача ЛП формулюється наступним чином:

Вважаючи, що множини , , — непусті та обмежені (ця умова не є обмежуючою), а ,  — екстремальні точки цієї множини, будь-яка з точок множини  може бути представленою у вигляді опуклої комбінації крайніх точок, тобто , . Підставивши отримані співвідношення в умову первісної задачі, отримаємо:

                                              ...

Ця задача є головною — координуючою задачею, в якій невідомі значення  (припускаючи, що відомі  значення координат всіх крайніх точок кожної з множин ).  Якщо ми знайдемо ці значення, то цим самим розв’яжемо задачу.

Оптимальний розв’язок знаходиться за допомогою дворівневої процедури, яка має назву методу Данціґа-Вулфа. В координуючій задачі кількість обмежень становить , що суттєво менше, ніж кількість обмежень , де , - кількості рядків у матрицях   відповідно. Але кількість стовпчиків у координуючій задачі надзвичайно велика - рівна числу всіх крайніх точок множин . Якщо б розв’язувати цю задачу безпосередньо, то ніякого виграшу в порівнянні з первісною задачею не було б. У методі Данціґа-Вулфа  не зберігаються всі стовпці матриці обмежень координуючої задачі — вони отримуються по мірі необхідності з використанням методу ґенерації стовпців та розв’язуванням множини допоміжних підзадач з використанням первісних підматриць .

Представимо координуючу задачу в еквівалентній формі:

, ,...,, ,

де  , .

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

Таким чином укрупнена схема алгоритму декомпозиції включає два етапи:

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

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

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

Розглянемо деталі реалізації цієї процедури. Нехай — біжуча база, а  — вектор коефіцієнтів функції мети при базових змінних. Згідно до схеми обчислень модифікованого симплекс-методу біжучий розв’язок є оптимальним, якщо для всіх небазових векторів   виконується умова оптимальності , де згідно до визначення координуючої задачі  та , одиничний вектор має  компонент, одиниця знаходиться в -ій позиції. Здійснимо наступні перетворення. Нехай , де  — матриця , що складається з перших  стовпчиків матриці , а  —  -й стовпчик цієї ж матриці. У цьому випадку

= .

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

Замість того, щоб знаходити всі кутові точки всіх  n підмножин, задачу можна звести до визначення кутової точки     кожної з підмножин, якій відповідатиме найменше значення .

Нехай  та . Таким чином, якщо , змінна , що відповідає , повинна бути введена до бази. В іншому випадку, якщо , отриманий розв’язок є оптимальним. Кожна з екстремальних кутових точок визначається внаслідок розв’язання наступної задачі ЛП:

.

В цій задачі індекс k не вживається з наступної причини. Внаслідок припущення про обмеженість множини  мінімальне значення  також обмежене і повинно відповідати деякій кутовій точці цієї множини. Оскільки  =  і  — постійна, що не залежить від k, задача переформульовується наступним чином:

Звідси визначаємо , де  — оптимальне значення  . Змінна, що виводиться з бази, знаходиться згідно до умови припустимості, що використовується в модифікованому симплекс-методі.

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

  1.  Перетворити первісну задачу таким чином, щоб в її модифікованому формулюванні фіґурували нові змінні .
  2.  Знаходимо початковий базовий розв’язок модифікованої задачі. (На цьому кроці доцільно застосувати перший етап двоетапного симплекс-методу.
  3.  На біжучій ітерації знайти  для кожної з підзадач та визначити . Якщо , то знайдений розв’язок оптимальний — стоп.  
  4.  Включити  змінну , що відповідає , до бази. Визначити змінну, що виключається з бази, виключити її та обчислити нову матрицю . Перейти до кроку 3.


Данной работой Вы можете всегда поделиться с другими людьми, они вам буду только благодарны!!!
Кнопки "поделиться работой":

 

А также другие работы, которые могут Вас заинтересовать

17528. Java Servlet та JSP 86 KB
  Лабораторна робота №2 Тема: Java Servlet та JSP. Мета: Навчитись створювати та виконувати Java Servlet та JSPсторінки всередині серверу Tomcat. Хід роботи: Теоретичні відомості: Сервлет Javaоб’єкт що працює всередині спеціальної програми сервлетконтейнера і застосовується
17529. Розробка Java-програм з Web-інтерфейсом, що працюють з базами даних, на основі фреймворка Spring та Java Persistence API (JPA) 305.5 KB
  Лабораторна робота №3 Тема: Розробка Javaпрограм з Webінтерфейсом що працюють з базами даних на основі фреймворка Spring та Java Persistence API JPA. Мета: Навчитись використовувати шаблон проектування MVC та фреймворк Spring при створенні Javaпрограм з Webінтерфейсом. Навчитись вико...
17530. Робота з базами даних в Java з використанням JDBC 51.5 KB
  Лабораторна робота №1 Тема: Робота з базами даних в Java з використанням JDBC. Мета: Навчитись виконувати основні операції при роботі з базами даних в Java використовуючи JDBC API. Теоретичні відомості Таблиці. В бібліотеці javax.swing є клас JTable який представляє таблицю. Для
17531. Робота зі збереженими процедурами баз даних 25 KB
  Лабораторна робота №3 Тема: Робота зі збереженими процедурами баз даних. Мета: Навчитись створювати та викликати збережені процедури. Завдання: Створити Firebirdбазу даних в якій є дві таблиці що знаходяться у відношенні одиндобагатьох masterdetail. Створити збережену...
17532. Базові поняття С++ 184.5 KB
  Лабораторна робота №1 Базові поняття Мета роботи – вивчити правила синтаксису мови програмування С особливості використання різних типів даних операції потокового введення / виведення. Теоретичні положення 1.1 Правила синтаксису Множина символів ...
17533. Реалізація розгалужених обчислювальних процесів в С++ 109 KB
  Лабораторна робота №2 Реалізація розгалужених обчислювальних процесів. Мета роботи – вивчити особливості використання: умовного оператора; стандартних математичних функцій. Умовний оператор Умовний оператор має наступний формат: ...
17534. Дослідження операторів ітерації (циклів) в С++ 58 KB
  Лабораторна робота №3 Дослідження операторів ітерації циклів Мета Набути практичних навичок щодо використання циклів у програмного коду. Теоретичні відомості Цикл оператор ітерації це різновид керуючої конструкції яка призначена для організації багат
17535. Дослідження індексованого типу (одновимірні масиви) в С++ 77 KB
  ЛАБОРАТОРНА РОБОТА № 4 Дослідження індексованого типу одновимірні масиви Мета лабораторної роботи – дослідити опис ініціювання індексованого типу та навчитися виконувати практичні завдання над ним. Завдання Написати програму на мові Сі яка складається
17536. Дослідження індексованого типу (одновимірні масиви) в С++ 55.5 KB
  ЛАБОРАТОРНА РОБОТА № 5 Дослідження індексованого типу одновимірні масиви Мета лабораторної роботи – дослідити опис ініціювання індексованого типу та навчитися виконувати практичні завдання над ним. Мета: набути умінь і навичок роботи зі статичними масивами