Задачі лінійного програмування

1. Розмітимо вершини і₁, приписавши їй значення h_i1=0 Через r кроків будемо мати мн-ну І^(r)= {i1,iл,…} кожній з якій приписане число h_{i л}.

2. Розг. Мн-ну І^(r)={…iм…} нерозмічених в-н таких що (і _л,і_м )єU, і _лєІ^(r), і_мєІХ^(r), І^(r)ІХ^(r) = для кожної такої дуги (і _л,і_м ) обчислюю величину {h_{i л}+С_ілім}; знаходимо най < серед отриманих значень (якщо min досягається на кількох дугах одночасно, то одну довільну із них). Відмічаємо кінець обраної дуги (відповідної вершини) обчис. знач. Та виділяємо цю дугу. Так продовжується до тих пір, доки можна розширювати множину помічених вершин.

3. Якщо в-на і_s входить в мн-ну поміч. вершин, то виписуємо найкоротший шуканий шлях в оберненому порядку по виділених дугах і_s. Якщо і_s не входить в мн-ну помічених вершин, то жодного шляху з в-ни і₁ в в-ну і_s не існує. Приклад: Розглянемо мережу:

Рис.

1)1->h₁=0; I⁽¹⁾={1}

2)I⁽¹⁾={2,3,4,5,6,7,8}

(1,2):h₁+c₁₂=0+3=3

(1,3):h₁+c₁₃=0+2=2->min

3) I⁽²⁾={1,3}; I⁽²⁾={2,4,5,6,7,8}

(3,2):h₃+1=2+1=3

(3,5):h₃+3=2+3=5

(1,2):h₁+1=0+3=3(min)

Продовжуючи далі цей процес то отримаємо такий малюнок:

Рис.

Маючи мережу з даними відмітками, можемо зайти шлях, що почин. в вершині 1 і закінчується у верш. к, причому довжина шляху найкоротшою. Знайдемо шлях для верш к=6. Отже довж. Найкор. шляху з перш 1 в 6 рівна 5. А сам шлях опис. в оберненому порядку при русі з вершини 6 до верш. 1 по виділеним дугам (1,3,2,5,6), к=4 шляху не має. Розглянемо тепер дві інші важливі задачі на мережах:

а) Задача про максимальний потік. Нехай задана мережа (I,U). Причому вважатимемо що в цій мережі ! джерело - s та єдиний стік t. Припустимо, що інтенсивність джерела це є деяка величина d, тоді для того щоб мережа пропускала потік. Необх. щоб інтенс. стеку була -d. Вважаємо що наближення на пропускні здатності дуг задано. Тоді, цей потік Х має задовольняти співвідношення:

0<=x_ij<=r_ij, (i,j)єU. Задача про max потік полягає в знаходженні такого max числа d, при якому мережа допускає потік.

б) задача про мінімальний переріз. Введемо для початку поняття перерізу мережі, що відділяє джерело від стоку будемо називати величину U(c), що U(c)={(i,j)єU, iс,jc} Нагадаємо що пропускною здатністю є число r, де

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

{1,2,3}; U(c)={(2,4)(2,5)(3,5)}; r(c)=5+2+1=8.

Рис.

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

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

30. Теорема про максимальний потік та мінімальний переріз. Алгоритм Форда-Фалкерсона

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

Дов. У випадку, коли із дж s_i до стоку s веде єдиний шлях, твердження теор. є тривіальним. Нехай тепер параметр d^* - це є велич мах потоку, який являє собою: x*={x_ij:(i,j)єU}. Нехай далі U(c)-це деякий переріз мережі, r(c) пропускна здатність перерізу. В силу т-ми про ! Потоку, необх. існування співвідношення d^*<=r(c). Покажемо що можна побудувати мн-ну с^* таку що d^*=r(c^*). Покажемо що ця множина с^* може бути задана наступним співвідношенням: sc^* якщо ic^* i x_ij<r_ij, to jc^*; якщо ic^* i x_ki<0, to kc^*;(1)

По перше покажемо що побудована за спів. від (1) с^*дійсно задає переріз, який відділяє джерело від стоку. По заданій мн-ні с^* можна побудувати переріз. Залишилося показати що tс^*. Доведення проведемо від супротивного. Нехай tс^*, тоді можна побудувати ланцюжок [s=i1,i2,…,im=t], який з'єднує верш. s, і верш. t. Якщо для ребра [i_k,i_k+1] відповідає дуга (i_k,i_k+1) належить множині дуг U(c^*), то має виконатися нерівність.

x_ik,ik+1<r_ik,ik+1 (2)

Якщо для ребра [i_k,i_k+1] відповідає дуга (i_k,i_k+1) U(c^*);

x_ik+1,ik>0 (3)

Визначимо величину Q_ik,ik+1=x_ik,ik+1, для (3) Q=minQ_ik,ik+1 ik; Згідно визначення величина Q=>Q>0, збільшимо потік x^* на величину Q по всіх дугах які задовольняють співвідношення (2) та зменшимо його на величину Q по всіх дугах які задовольняють співвідношення. (3). Отримаємо новий допустимий потік (d^*+Q), що суперечить умові про те що d^* - max потік, який не можливо збільшити. Отже це означає, що tс^*. Отже с^*- дійсно визначає переріз, що відділяє число від стоку.

2)Покажемо тепер що дійсно має місце співвідношення: d^*=r(c^*) із співвідношення (1) очевидним чином отримуємо: якщо ic^* I jc^* (i,j)U to x_ij=r_ij ; якщо ic^* , kc^* (i,k)U to x_ki=0 ; (4)

З обмежень на допустимий потік отримуємо: і, іt

Просумуємо ці два співвідношення по і і отримаємо

Розпишемо першу суму по таких j:jc^*, jc, другу по к:кc^*, кc^* одержимо:

легко побачити що 1=3, 4=0 отримали те що треба було довести: с*: d^*=r(c^*)

теорема доведена!

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

Цілочисельні задачі ЛП. Порівняння неперервної та дискретної задачі.

Задачі дослідження на умовний екстремум лін. ф-ції не обмежується тільки лін. моделями. Найпоширеніший спосіб розширення множини ЗЛП є введення додаткового обмеження на компоненти розв'язку. В залежності від того яке це обмеження будемо вирізняти: а) задачі цілком цілочислового програмування (ЗЛП+x_ij-цілі j=1,n). б) частково числового програмування: ЗЛП + x_ij-цілі j=1,k; k<n). в) задачі дискретного програмування ЗЛП+x_ijj j=1,n де _j={0,x^*1_j,x^*2_j,…,x^*r_j}).

Виникає питання як розв'язувати задачі а б в, Очевидний підхід полягає в тому , щоб розв'язати ЗЛП відповідним чином, заокруглити результат. Однак такий підхід може давати неправильний результат. Ця складність пов'язана з невизначеністю поняття заокруглення та великою розмірністю вектора Х.

Пр. L(x)=x₁+x₂->min

x_j>=0, j=1,2

Рис.

Таким чином цей приклад ілюструє необхідності розробки нового підходу до розв'язання задачі.

31. Ідеологія методу відтину. Методи Гоморі. Теоретичні обґрунтування

Задачі дослідження на умовний екстремум лін. ф-ції не обмежується тільки лін. моделями. Найпоширеніший спосіб розширення множини ЗЛП є введення додаткового обмеження на компоненти розв'язку. В залежності від того яке це обмеження будемо вирізняти: а) задачі цілком цілочислового програмування (ЗЛП +x_ij-цілі j=1,n). б) частково числового програмування: ЗЛП + x_ij-цілі j=1,k; k<n). в) задачі дискретного програмування ЗЛП+x_ijj j=1,n де _j={0,x^*1_j,x^*2_j,…,x^*r_j}). Виникає питання як розв'язувати задачі а б в, Очевидний підхід полягає в тому , щоб розв'язати ЗЛП відповідним чином, заокруглити результат. Однак такий підхід може давати неправильний результат.

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