Размещено на http://www.allbest.ru/

1. Загальна ЗЛП (координатна, матрична, векторна форми). Цільова функція та обмеження. Допустимі вектори і розв'язки

опуклий множина алгоритм задача

Ми хочемо дослідити на екстремум лінійну функцію. Нехай розглянемо вектор Є . ЗЗЛП може бути сформульована наступним чином:

Дослідити на екстремум лінійну функцію L(x): (1)

При обмеженнях (2) і таких (3), де символ

Задача (1), (2), (3) - це ЗЗЛП.

Озн.1: Сукупність точок , які задовольняють обмеженням (2) і (3), будемо називати допустимою множиною ЗЗЛП, кожен елемент цієї множини

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

Озн.2: Функцію L(x) з співвідношення (1) будемо називати цільовою функцією ЗЗЛП.

Обмеження виду (2) будемо називати основними обмеженнями ЗЗЛП, а обмеження виду (3) - природними обмеженнями ЗЗЛП.

Озн.3: Точка , в якій цільова функція (1) досягає свого екстремуму і яка задовольняє співвідношенням (2) і (3) буде називатися розв'язком ЗЗЛП. (вона не завжди існує).

опуклий множина алгоритм задача

2. Геометрична інтерпретація ЗЛП

Будемо вважати, що в співвідношенні виконується умова k=n і розглянемо задачу L(x): (1), (2), (3) для двох випадків: а) n=2 б) n-m=2

Використовуючи мат. аналіз для знаходження підозрілих на екстремум точок задачі (1), (2), (3), необхідно обчислити градієнт функції L(x). Очевидно, що цей grad не може бути рівний 0 ні при якому виборі вектора х. Тому розв'язок задачі (1), (2), (3) (якщо він існує), повинен знаходитись на границі допустимої довжини.

Розглянемо випадок: а) n=2

Введемо на площині систему координат, тоді обмеження виду (2) будуть задавати в цій системі координат півплощини у випадку та прямі лінії у випадку =. Аналізуючи все можливі варіанти взаємодії перетинів півплощин і прямих, можна зробити висновок, що допустима множина D може бути: порожня, не порожня і обмежена, не порожня і не обмежена.

Якщо множина D порожня, то задача (1), (2), (3) розв'язку не має. Якщо D складається з однієї точки, то розв'язком (1), (2), (3) буде власно ця точка.

Якщо побудувати лінію рівня L(x)=const, конкретне значення цієї константи слід підбирати рак, щоб допустима множина знаходилась в напрямку gradL(x) у випадку задачі на максимум або в напрямку антиградієнта функції L(x) у випадку задачі на мінімум. Потім рухаємо лінію рівня в обраному напрямку до її останнього перетину з допустимою множиною. Можливі такі випадки:

- останній перетин досягається в окремо взятій вершині допустимої множини;

- останній перетин досягається на ребрі допустимої множини;

- останній перетин досягнути неможливо. Множина D не порожня і не обмежена.

В першому випадку розв'язком ЗЛП і буде ця вершина (її координати). В другому випадку розв'язком буде будь-яка точка з останнього ребра. В третьому - розв'язку не існує.

б) n-m=2

При додаткових припущеннях k=n:

rank A= rank=m; всі обмеження мають вигляд рівності.

Оскільки, згідно з припущення rank A=m, то з n змінних m змінних є базисними, а 2 змінних є небазисними.

Будемо вважати, змінні є небазисними, а змінні - базисними. Виразимо тепер, з основних обмежень базисні змінні через небазисні. Отримаємо систему рівнянь:

Враховуючи природні обмеження на базисні змінні, можемо записати:

Розглядаючи даль m лінійних нерівностей, впевнюємось, що вона залежить тільки від двох змінних. Далі підставимо в цільову функцію L(x) знайдені вирази для базисних змінних, отримаємо: , зробимо заміну: . Отримаємо задачу:

Очевидно, що це є задача з n=2, її можна розв'язати за допомогою методу, описаного в пункті а).

Знайдені значення , використовуємо для знаходження значень . Знаючи вектор , знаходимо .



3. Опуклі множини, перетин опуклих множин. Опуклість гіперплощини і півпростору. Опуклість множини допустимих векторів ЗЛП

Означ.1: Розглянемо в просторі сукупність точок , при чому . Будемо називати опуклою лінійною оболонкою точок для кожної із яких, справедливе представлення.

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

Порожня множина вважається опуклою. Множина, яка складається з однієї точки теж опукла.

Означ.3: Множину точок Є , які задовольняють нерівності , де вектор а і число b задані, будемо називати підпростором простору .

.

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

Лема1. Перетин довільного числа опуклих множин є опуклою множиною.

Нехай - опуклі множини. Доведемо, що множина є опуклою множиною. Відкидаючи тривіальні випадки припустимо, що множина М містить хоча б 2 точки. Оскільки випливає . Кожна множина є опуклою, тому відрізок . Випливає , що й означає, що множина М опукла.(за озн.2)

Лема 2. Півпростір є опуклою множиною.

Будемо розглядати для визначеності півпростір , де вектор а і число b задані. Нехай точки належать вказаному півпростору. Покажемо, що відрізок, який з'єднує ці точки теж належить вказаному півпростору. Кожну точку з відрізка згідно означення 1, можна представити у вигляді:

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

Лема 3. Гіперплощина є опуклою множиною.

Очевидно, що кожна гіперплощина можна представити у вигляді перетину . Застосовуючи результати леми1 і леми2, отримаємо твердження леми3.

4. Властивості допустимої множини ЗЛП

Теорема 1: Множина допустимих векторів D ЗЛП є опуклою.

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

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

Теорема 2: Множина розв'язків ЗЛП - опукла.

Виключаючи з розв'язку тривіальні випадки, коли множина розв'язків порожня або складається з 1 точки, припустимо, що існує 2 точки , які є розв'язком ЗЛП (напр. для задачі на мінімум). Побудуємо відрізок, який з'єднує точки : . Кожну точку з цього відрізку можна представити у вигляді: . Підрахуємо значення цільової функції L в точці х:

Висновок: множина розв'язків ЗЛП не може бути скінченою множиною, за винятком випадку, коли розв'язок єдиний.

Назвемо кутовою точкою або вершиною опуклого багатогранника D таку його точку , для якої не існує інших двох точок (). Таких, що точка х може бути представлена у вигляді: .

5. Лема про вершини опуклого многогранника. Теорема про досяжність оптимуму ЗЛП в вершині допустимої множини

Лема: Кожна точка опуклого багатокутника може бути представлена у вигляді опуклої лінійної комбінації його вершин.

Теорема: ЗЛП досягає розв'язку в вершині множини D. Якщо оптимальне значення цільової функції досягається в 2 точках множини D, то також значення цільова функція досягає в кожній точці відрізку, що з'єднує ці точки.

Будемо розглядати для визначеності задачу мінімізації функції на множині D, яка є опуклим багатокутником. Нехай множина розв'язків задачі не порожня: . Розглянемо деяку точку . Якщо - це вершина допустимої множини, то теорема доведена.

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

Оскільки точка є розв'язком ЗЛП, то повинно виконуватись співвідношення : . З іншого боку запишемо таку послідовність співвідношень: . Отже, тоді . Тоді звідси випливає , де - вершини множини D.

6. Стандартна ЗЛП. Зведення ЗЛП до СЗЛП. Співвідношення між числом змінних, числом обмежень, рангом матриці рангом розширеної матриці. Зведення СЗЛП до КЗЛП

Введемо для початку нову форму запису ЗЛП: це є так звана стандартна задача лінійного програмування СЗЛП.

Для СЗЛП існує кілька форм:

1) координатна форма запису СЗЛП:

, ,

2) векторна форма



, ,

3) матрична форма СЗЛП:

,

Припустимо .

Дослідимо тепер як ЗЗЛП перевести в СЗЛП:

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

Введемо в розгляд нову форму ЗЛП, яка називається КЗЛП.

Знайти в просторі такий вектор , який доставляє мінімум лінійній функції

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

Додатковою умовою є ще те , що , що дозволяє легко виписати початковий базисний вектор:

7. Базисні вектори. Базис базисного вектора. Базисна матриця. Базисні і небазисні змінні. Вироджений і не вироджений випадки

Озн.1: Допустимий вектор х з множини D будемо називати базисним вектором, якщо його нульовим компонентом відповідає система лінійно незалежних стовпців матриці А .

Висновок 1: .

Висновок 2: ненульовий компонент може бути .

Озн. 2: Якщо в базисному векторі є рівно m ненульових компонент, такий вектор будемо називати не виродженим базисним вектором. Якщо ця кількість <m, то такий базисний вектор - вироджений базисний вектор.

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

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



8. Теорема про базисні вектори СЗЛП

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

Необхідність: Нехай вектор х - це є вершина допустимої множини. Покажемо, що х - базисний вектор.

Оскільки х - вершина, то , тому має місце співвідношення: .

Припустимо, що перші r координат вектора х, додатні і покажемо, що має місце нерівність .

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

, де .

Виберемо тепер число так, щоб виконувались нерівності . Перевіримо тепер, чи будуть побудовані вектори , допустимі для задачі лінійного програмування. Для цього підставимо в основні обмеження СЗЛП.

, є допустимим.

Цілком аналогічно впевнюємось, що - допустимий.

Очевидною є рівність: , що суперечить означенню вершини.

Отримали протиріччя. Отже, припущення, що невірне, тому . Тобто вектор х є базисним.

Достатність: Нехай вектор х - базисний вектор ЗЛП, покажемо, що х- вершина.

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

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

9.Алгоритм СМ

Алгоритм СМ застосовується до КЗЛП:

Будемо вважати,що перші m-змінних є базисними,а решта (n-m)-небазисні.

Таке припущення дає можливість виписати перший базисний вектор:

Для того,щоб розібратися з основними ідеями симплекс-методу розв'яжемо кілька прикладів. Впевнимося, що задача задов. умові R.

. Виберемо змінні за базисні, відповідно будуть вільними змінними. Виразимо базисні через небазисні.

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

Отримаємо, що перший базисний вектор матиме вигляд ,m=3. Підрахуємо значення цільової функції на цьому векторі . Попробуємо зменшити значення цільової функції. Для цього проаналізуємо вигляд . Аналізуючи вигляд умов, отримаємо . Перерахуємо при , а - новий базисний вектор . перевіряємо,що вектор базисний вектор. Для цього випишемо вектори умов для : ,отже,це є базисний вектор, який призвів до зменшення цільової функції. Виразимо з основних умов базисні змінні через небазисні:

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

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

2)проілюстрований в прикладі спосіб виведення однієї базисної змінної з базису, та вводу іншої змінної в базис, може бути формалізований і такі перетворення назив. Симплексним перетворенням.

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

10.Зміна значень цільової функції ЗЛП при переході від однієї вершини допустимої множини до іншої. Відносні оцінки змінних. Симплексні перетворення

Відомий вектор Х для задачі (10)-(12) буде мати вигляд:

Для того,щоб вивести з базису змінну ,а ввести в базис змінну,необхідно зробити такі дії: для цього від і-того рівняння в системі (11) необхідно відняти l-те рівняння, умножено на коефіцієнт ()

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

Де для обчислення нових коефіцієнтів використовуються такі співвідношення :

(13) (14)

Підкреслимо структуру стовпчика ,він матиме вигляд: .

Отже,для співвідношення (13),(14) ми здійснили перехід від відомого базисного вектора КЗЛП до іншого для того,щоб ця вершина була вершиною множини допустимих відрізків,необхідне виконання декількох умов:

1)

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

2) перепишемо цю умову так: , звідси випливає,що позначимо : використовуючи співвідношення (14), з урахуванням визначення величини ,можна знайти структуру його базисного вектора:

Безпосередньо можна підрахувати,що то

Описаний метод назив. методом виключення Жордана-Гауса і задає перехід від відомого базисного вектора до іншого базисного вектора.

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

На старому базисному вектору нас було:

На новому базисному векторі маємо: Величини к іноді називають відносними оцінками змінних або симплекс різницями. Іноді вони набувають такого значення:

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

Доведення: підставимо вирази до базисних змінних в цільову ф-цію,отримаємо:

11.Критерій оптимальності базисного вектора

Теорема(критерій оптимальності):якщо для деякого базисного вектора виконується співвідношення:, j=1,n є небазисною змінною,то цей базисний вектор х* є розв'язком ЗЛП.

Доведення:проведемо доведення задачі лін. програмування в стандартній формі розглянемо деяку СЗЛП:

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

В загальноприйнятих позначеннях КЗЛП : або у векторній формі:

Ввівши позначення де буде являти собою вектор стовпчик матриці . (*) оскільки в силу умов теореми ,то враховуючи означення відносних оцінок маємо: (**). якщо Х* -розв2язок ЗЛП - це означає,що для повинно виконуватися співвідношення: . візьмемо дов. вектор Уз множини Д:

оскільки вектор ,то він є допустимим,тобто виконується співвідношення: підставимо в це співвідношення представлення (*):

(`): . Оскільки ,то він теж є допустимим,а,отже задов. основні умови: («). порівняємо вирази (`) і («). оскільки розклад дов. Вектора,в даний момент вектора b ,по системі лінійно незалежних векторів єдиний,то з отриманих представлень робимо висновок: . підставимо тепер отримані рівності в раніше отриману нерівність , то побачимо, що

12.Ознака необмеженої цільової функції

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

Доведення:є базисним вектором КЗЛП і задовольняє умови теореми.

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

Підрахуємо значення цільової ф-ції на y:



13. Відносні оцінки змінних та способи їх визначення

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

Нагадаємо, що початковий базисний вектор для задачі (10 -12) має вигляд: (10-12)

Вектор на цьому базисному векторі цільова функція прийме значення:

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

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

Величини називаються відносними оцінками в даному випадку не базисних змінних.

Приведені вище співвідношення можна використовувати тоді, коли перші m змінних є базисними, в загальному випадку можна використовувати співвідношення:

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

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

Найбільш широко використовується вибір індексу к, з умови, що

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

Будемо розглядати КЗЛП задачу співвідношення (10-12) базисні через не базисні, отримаємо:

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



14. Пошук початкового базисного вектора

Проблема пошуку початкового базисного вектора при великому розмірі задачі є досить складною процедурою. Розглянемо ЗЗЛП вигляду

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

В цій задачі згрупуємо обмеження по таку нерівність:

I: обмеження зі знаком ; II: обмеження зі знаком ;

III: обмеження зі знаком =; Розв'яжемо групу обмежень I:

I.

Зведемо ці обмеження до стандартного вигляду ввівши нові невід'ємні змінні.



де - це матриця .

Очевидно, що це є обмеження КЗЛП. При цьому початковий базисний вектор буде мати вигляд:

II:

Аналогічно пункту 1 стандартизуємо ці обмеження. Отримаємо:

серед чисел знаходимо максимальне. Нехай воно має індекс l. віднімемо тепер від l-го рівняння і-те і запишемо результат на місце і-го рівняння.

ми отримали m-1 рівняння в якому явно присутні базисні змінні і 1 рівняння l-те в якому базису немає (m+1)l.

Останнє l-те рівняння, оскільки воно записується у вигляді рівності ми віднесемо до групи 3, а з рештою m-1 рівнянням легко знайти базисні змінні та відповідний базисний вектор.

III: Введемо до розгляду та розглянемо допоміжну задачу:

при чому легко знайти її початковий базисний вектор

Записуємо симплекс-метод для розв'язку цієї допоміжної задачі. В результаті можливі 2 випадки:

1. Розв'язок існує

Якщо необмежений знизу, то це суперечить постановці допоміжної задачі. Функція є обмеженою числом 0 знизу, тому 2) бути не може.

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

1) 2)

Тому , покажемо, що в цьому випадку вектор є початковим базисним вектором початкової СЗЛП. Очевидно, що , тобто природне обмеження. Тобто вектор є допустимим вектором початкової СЗЛП.

З вигляду основних обмежень допоміжної задачі та з того, що вектор є розв'язком допоміжної задачі випливає, що серед компонент вектора не > m ненульових компонентів, при чому вектор-стовпчики матриці А, які їм відповідають є лінійно-незалежними. Тому вектор є базисним вектором початкової СЗЛП. Переходимо тепер до КЗЛП по відомій процедурі і продовжуємо розв'язання СЗЛП симплекс-методу.

2) В цьому випадку можна стверджувати, що допустима множина початкової задачі є порожньою.

Проведемо доведення цього факту від супротивного. Нехай множина D не порожня, тобто .

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

Оскільки на розв'язку допоміжної задачі , а множина отриманих , то є протиріччя. Значить D - порожня.



15. Метод штучної бази

В цьому методі спочатку будують та розв'язують допоміжну задачу КЗЛП.

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

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

Введемо до розгляду та розглянемо допоміжну задачу:

при чому легко знайти її початковий базисний вектор

Записуємо симплекс-метод для розв'язку цієї допоміжної задачі. В результаті можливі 2 випадки:

2. Розв'язок існує



Якщо необмежений знизу, то це суперечить постановці допоміжної задачі. Функція є обмеженою числом 0 знизу, тому 2) бути не може.

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

1) 2)

Тому , покажемо, що в цьому випадку вектор є початковим базисним вектором початкової СЗЛП. Очевидно, що , тобто природне обмеження.

Тобто вектор є допустимим вектором початкової СЗЛП.

З вигляду основних обмежень допоміжної задачі та з того, що вектор є розв'язком допоміжної задачі випливає, що серед компонент вектора не > m ненульових компонентів, при чому вектор-стовпчики матриці А, які їм відповідають є лінійно-незалежними. Тому вектор є базисним вектором початкової СЗЛП. Переходимо тепер до КЗЛП по відомій процедурі і продовжуємо розв'язання СЗЛП симплекс-методу.

2) В цьому випадку можна стверджувати, що допустима множина початкової задачі є порожньою.

Проведемо доведення цього факту від супротивного. Нехай множина D не порожня, тобто .

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

Оскільки на розв'язку допоміжної задачі , а множина отриманих , то є протиріччя. Значить D - порожня.

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

16. М-метод розв'язання ЗЛП

Розглянемо стандартну ЗЛП:

Побудуємо допоміжну М-задачу

В цій допоміжній М-задачі число M>0 це досить велике додатне число.

Очевидно, що в силу побудови М-задачі це є КЗЛП.

Розв'язуємо М-задачу за допомогою симплекс-методу. Аналогічно методу штучної бази проаналізуємо можливі випадки закінчення алгоритму симплекс-методу:

а) розв'язок М-задачі , при чому всі компоненти вектора

б) існує розв'язок М-задачі

, однак серед компонент вектора

в) на допустимій множині М-задачі

можна показати, що про початкову задачу можливі такі варіанти тверджень:

а)розв'язок початкової задачі існує це

б) Д(СЗЛП)=

в) цільова функція СЗЛП необмежена з низу на допустимій множині, якщо Д



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

Доведемо для прикладу твердження а):

а) дійсно нехай у розв'язку М-задачі маємо . Візьмемо довільний вектор х, який є допустимим для СЗЛП, і побудуємо вектор очевидна нерівність:

б)Нехай існує розв'язок . Тоді розглянемо

число М також більше 0, згідно М-методу. Доведемо від супротивного. Припустимо, що . Розглянемо деякий вектор . Побудуємо допоміжний вектор

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

Аналізуючи, цю нерівність та враховуючи структуру отримаємо, що основне М досить велике але фіксоване, дана нерівність може не використовуватись.

Отримали протиріччя

17. Приклади двоїстих задач

Задача А: Деяке підприємство А виготовляє продукцію, використовуючи при цьому n-технологію. Для виробництва продукції підприємство використовує м-ресурсів, к-кості яких обмежені величинами b1,b2…bm. Позначимо символами a_ij, i-1,m - к-сть і-го ресурсу, що витрачається на виробництво одиниці продукції за j - технологією, а через символи cj прибуток від реалізації одиниці продукції виробленої за j технологією.

Задача максимізації прибутку підприємства А полягає в складанні такого плану x= (x1,…x2) де х - це запланований об'єм випуску продукції по j технологій може бути сформульована математично наступним чином:

Задача В: Нехай є таке підприємство В, яке виявило намір купити у підприємства А його ресурси. Виникає задача: Які нині потрібно встановити підприємству А щоб не втратити можливого прибутку від виготовленого продукту.

Позначимо: u1,u2,…,um - це ціни, які встановило підприємство А на свою продукцію. Та сформулюємо для підприємства В наступну задачу.

Очевидно що задачі А і В надзвичайно тісно пов'язані між собою і їх вирішення може вважатися успішним тільки за умови:

Задачі для підприємств А і В називають двоїстими задачами (спряженими).

18 Побудова двоїстих задач

Будемо досліджувати як будувати двоїсті задачі для випадку СЗЛП та ЗЗЛП. Розглянемо спочатку СЗЛП:

(1)

Ax=b

(A=(m*n), x=(n), b=(m), c=(n)) b-Ax=0; Для має місце співвідношення:

c^Tx= c^Tx+ u^T(b-Ax)=( c^T- u^TA)x+ u^Tb

Виберемо тепер вектор u так щоб c^T- u^Tt>=0 => (c^T- u^TA)?0, c^Tx? u^Tb

І розглянемо задачу: (2)

u^TA? c^TA A^Tu<=c



Озн. Пара задач (1), (2) називається несиметричною парою двоїстих задач. Несиметричні бо в (1) х>=0, а в (2) такої умови немає.

Для побудови симетричної пари двоїстих задач розглянемо ЗЗЛП у формі:

(3)

Ax=b

Стандартизуємо цю задачу, при чому основні обмеження запишемо так:

, де І - це одинична матриця м*м,

Природні обмеження будуть очевидні x>=0, а Випишемо двоїсту до отриманої задачі. Вона матиме вигляд:

u^TA(A|-I)?

(4)

u^TA? c^T

^u?0

Пора задач (3), (4) називають симетричною парою двоїстих задач.

Заув. Як легко переконатися двоїстою до двоїстої задачі є початкова задача.

19. Двоїста до ЗЛП. Характерні властивості пари двоїстих задач

Лема: Значення цільових ф-цій пари двоїстих задач зв'язані нерівністю L(x)=c^Tx>=b^Tu=w(u) при довільних векторах х та u відповідно. Якщо ж на деяких допустимих векторах Х та u має місце рівність L(x)=w(u), то ці вектори є розв'язками відповідних задач. Приведемо тепер кілька характерних особливостей пари двоїстих задач:

Одна із задач двоїстої пари це задача на мінімум, а друга на максимум;

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

Кількість двоїстих обмежень рівна кількості обмежень і навпаки;

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

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

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

20. Теорема двоїстості

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

Перша теорема двоїстості:

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



21. Друга теорема двоїстості. Застосування до розв'язування пари двоїстих задач

Теорема(друга теорема двоїстості) допустимий вектор х для задачі (15) буде розв'язком задачі (15) тоді і тільки тоді, коли буде існувати вектор такий, що виконуються умови:

(19)

Дов Необхідність. Нехай вектор є розв'язком задачі (15). Необхідно доказати що існує вектор такий, що умови (19) мають місце. Оскільки задачі (15)(16) є парою двоїстих задач, то згідно теореми 7 частина а) (перша т-ма двоїст.) отримаємо, що задача (16) має розв'язок (позначимо розв'язок ) і при цьому має місце співвідношення . Розглянемо далі ланцюжок співвідношень:

звідси й випливає справедливість умов (19). В якості вектора можна взяти .

Достатність. Нехай вектор є допустимим вектором для задачі (15) та виконується умова теореми. Покажемо, що є розв'язком задачі (15) Перепишемо співвідношення (19) у векторній формі :

- допустимий вектор(16). Помножимо співвідношення на вектор справа, отримаємо: згідно результатів леми 6 част1) це означає, що вектор є розв'язком задачі (15).

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

Випишемо двоїсту до заданої задачі:

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

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

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

22. Двоїстий См. Означення псевдоканонічної ЗЛП, майже допустимого вектора, геометрична інтерпретація, обмеження на відносні оцінки

Двоїстий симплекс метод - це метод розв. задач лін. Програмування, який своїм походженням зобов'язаний теорії двоїстості. Ідея ДСМ. Аналогічно звичайному СМ ми спробуємо здійснювати перехід від одного (псевдобазисного) вектора до іншого так, щоб значення цільової ф-іїї покращувалося. При цьому ми повинні за скінченну к-сть кроків знайти розв ЗЛП або встановити його відсутність.

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

, або випишемо тепер перетворену задачу (15) (21) Ця задача відрізняється від КЗЛП відсутністю умов на . Його компоненти можуть бути як і додатнім так і ні. Таку задачу (21) будемо називати «псевдо КЗЛП» або «майже КЗЛП». Аналог тому, як ми це робили для КЗЛП, для задачі (21) можна ввести поняття псевдобазисного вектора : вектор буде псевдобазисним вектором задачі (21) якщо: - його невід'ємним компонентам відповідає лін. нез с-ма векторів матриці ; - він задовольняє основні обмеження задачі (21), але може не задовольняти природні.

Задачу (21) надалі будемо представляти у вигляді: (22) Скористаємось тепер результатами леми 5 і перепишемо задачу (22) у вигляді: (23) надалі будемо розгул. тільки такі «майже КЗЛП» в яких відносні оцінки небазисних змінних невід'ємні. (23) + (24). Умова (24) гарантує, що як тільки «майже» базисний вектор задачі (23) стане базисним (всі його компоненти стануть невід'ємні), то цей базисний вектор буде розв. ЗЛП. Перетворимо тепер задачу (23) з умовою (24) та помножимо основні обмеження задачі (23) на (-1) а потім випишемо двоїсту до отриманої задачі.

, (25) Канонізуємо задачу (25) і (26) Проаналізуємо структури задач (23), (24) і (26). Очевидно, що змінними які є базисними задачі (23), (24) відповідають (по номеру) змінні, які є небазисними в задачі (26) і навпаки, базисним змінним в одній задачі відпов. небазисні в іншій. В (26) компоненти вектора відіграють роль коефіцієнтів при небазисних змінних, а відносні оцінки з умови відіграють роль правих частин основних обмежень. Отже задача (26) це є КЗЛП і її можна розв. звичайним СМ.

23. Алгоритм двоїстого СМ

Двоїстий СМ застос. до майже КЗЛП, в якої відносні оцінки небазисних змінних задовольняють умови (24)

Знаходимо майже базисний вектор у вигляді і перевіряємо його на оптимальність

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

Визначаємо провідний елемент в симплекс таблиці, тобто повинні знайти такий , що , визначаємо: :для :

Перерозраховуємо симплекс таблицю за правилом прямокутника, отримаємо новий майже базисний вектор і переходимо на пункт 2.

24. Постановка ТЗБО. Зведення ТЗБО до ЗЛП. Властивості ТЗБО

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

(1), (2)- це математична модель задачі. В залежності від специфіки задачі, до умов (1), (2) додають так звану умову збалансованості ТЗ. В найпростішому випадку умова баланс має вигляд : (3), яка гарантує, що вся продукція буде розділена між споживачами, а їхні потреби будуть задовольнятись повністю. Відповідно задача (1)-(3) називається збалансованою ТЗ. Якщо в ТЗ умова (3) не виконується то така задача наз. небаланс ТЗ. Цільова ф-ія (1) - це лінійна ф-ія. Обмеження (2)- теж лінійні (в тому числі тут є і природні обмеження). Покажемо, як ТЗ (1), (2) привести до звичного виду ЗЛП. Для цього, введемо такі позначення: Аналогічно введемо вектор с: , , ,

(4)

З урахуванням введених позначень, ми отримаємо задачу (1), (2) у вигляді: , , (5). Очевидний підхід до розв. ТЗ. Необхідно перетв. задачу (1), (2) до форми (5). Розв. її СМ та виписати розв задачі (1), (2). Основна складність з-чі (5)- це розмірність матриці А. Специфікою є структура з-чі А- велика к-сть нулів і немала к-сть одиниць. Для розв ТЗ, як правило, використання транс. таблиці.

Властивості:

Властивість 1. збалансована ТЗ (1),(2),(3) завжди має розв. Дов. Оск задача (1),(2),(3) є еквівалентною з-чі (5) то необхідно показати, що з-ча (5) за умови (3) завжди має розв. Ця задача може не мати розв або якщо допустима множина порожня, або якщо цільова ф-ія необмежена на допустимій множ. Покажемо, що допустима м-на з-чі (5) за умов (3) не порожня. Побудуємо допустимий вектор для (5) за умови (3): , , де Як легко впевнитись, побудований т.ч. вектор є



25. методи побудови початкового базисного плану ТЗБО. Критерій оптимальності

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

(7) v_j - u_i = c_ij (для базисних кліток)

v_j - u_i <= c_ij (для небазисних)

На основі співвідношень (7) ми будемо будувати метод розв'язування ТЗ.

Метод побудови поч. планів.

Метод пн-зх кута

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

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

Метод мінімального елемента

При використанні метода пн-зх кута ми не врахували вартості переведень. В цьому методі суттєво використання вартості.

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

Геометричний зміст базисного плану

Приведемо декілька означень

озн.1 послідовність різних комунікацій

Pi1Qj1, Pi2Qj1, Pi2Qj2 .... PisQjs (над усіма ними стрілочки: )

будемо називати маршрутом, що з'єднує пункти ... та ...

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

Озн.2. Комунікацію ... будемо називати основною комунікацією плану перевезень х, якщо в цьому плані відповідна компонента хij>0

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

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

Прикладом таких планів є плани, побудовані методом пн-зх кута та мін елем.

26. Метод потенціалів розв'язування ТЗ

Ми розглядаємо не вироджені ТЗ, тобто всі базисні плани є не виродженими і мають рівно m+n-1 додатною компоненту. При побудові та використанні методу потенціалів суттєво використовується співвідношення з номером на основі цього співвідношення і побудовано метод потенціалів для розв'язування ТЗ.

Опишемо тепер метод потенціалів розв'язування ТЗБО.

1) В якості поч.. базисного розв'язку вибирає об-я поч. базисний розв'язок, побудований одним з відомих методів (пн-зх кута або б-я іншим)

2) Визначаємо потенціали п-тів виробництва та п-тів спожив так, щоб ДЕЛЬТА(ij) в базисних кліток є m+n-1, то отримуємо m+n-1 рівняння виду :

в цих р-нях є m+n невідомих, тому одну з невідомих змінних можна взяти за небазисну. Як правило, завжди вибирають небазисною змінною n1 і надають їй значення 0. Далі розв'язуємо отримані р-ня і знаходимо всі потенціали.

3) Перевіряємо критерії оптимальності ДЕЛЬТА більше або рівне нуля по небазисних клітках . Якщо критерій оптимальності виконується. Отриманий базисний розв'язок є розв'язком задачі, в противному розв'язком задачі, в противному випадку його можна покращити (до пункту 4)

4) Розглянемо спочатку випадок, коли для деякого індексна має місце співвідношення : ДЕЛЬТА(i0,j0)<0. Це означає, що клітку з індексами слід ввести до базису. Оскільки небазисних кліток було m+n-1, то разом з цією кліткою стає m+n , це означає, що можна побудувати замкнений цикл, який розпочинається і в клітці (i0,j0) і вершини якого знаходяться в базисних клітках.

Розмітимо вершини отриманого циклу знаками + та -, чергуючи їх, в клітці (i0,j0) ставимо +.

Розглянемо величину (!!!) і збільшимо значення перевозок в клітках, відмічених знаком +, та зменшимо значення перевозок в клітках, відмічених знаком -.

Оскільки ми розглядаємо невироджений випадок, то в тільки одній кліточці з знаком - значення перевозок=0. це означає, що ця клітка виводиться з числа базисних.

Як легко побачити, значення цільової ф-ії зміниться так :

Оскільки ДЕЛЬТА(i0,j0)<0, це означає, що значення цільової ф-ії зменшилось. Це співвідношення гарантує нам , що в невиродженому випадку за скінченну к-ть кроків буде знайдено розв'язок задачі. У випадку коли від'ємних відносних оцінок є кілька, слід вибирати найменшу з них.

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

З урахуванням вищесказаного мат модель ТЗО може бути представлена так:

Величини r(ij) з допомогою яких задане природне обмеження ТЗО будемо на об'єм на пропускну здатність комунікації. Числа r(ij) задані наперед. Відповідно до зміни структури задачі необхідно змінити поняття базисного плану, або базисного розв'язку. Назвемо допустимий план Х для ТЗО (9) базисним планом (вектором), якщо перевозкам цього плану, таким, що має місце.

0<x(ij)<r(ij)

відповідає система лінійно незалежних комунікацій, що з'єднують відповідні п-ти виробництва і споживання для ТЗБО: невироджений план, в якому є рівно n+m-1 перевозка, що задовольняє умові 0<x(ij)<r(ij)Якщо план має менше ніж таку перевозку, такий план будемо називати виродженим.

Введемо далі критерій для оптимальності базисного плану

Якщо для деякого плану Х виконується (10), то такий план є розв'язком ТЗО (9).

Алгоритм методу потенціалів:

1.обчислюємо потенціалів виробництва і п-тів споживання з с-ми n+m-1 рівнянь

зауважуючи при цьому, що маємо n+m змінних. Одну змінну = 0. решту знаходимо з с-ми. Відносні оцінки будуть =0.

Обчислюємо відносні оцінки для небазисних кліток. Якщо вик (10)

- розв'язок знайдено. Алг. закінчено.

Як ні---- п.2

2.припустимо спочатку що у нас є тільки1 клітка, в якій критерій опт. невик.

Можливі 2 випадки :

2а. (!!!)

будуємо цикл з вершинами у баз. Клітках і розмічаємо його вершини, починаючи зі знака +. Обчислюємо величину И (!!!)

збільшуємо перевозки в клітках циклу помічених знаком + на величину И і зменшимо перевозки на И в клітках помічених знаком -.

2б.нехай x(i0,j0)=r(i0,j0) але ДЕЛЬТА(i0,j0) більше 0.

Будуємо цикл, починаючи із клітки (i0,j0) з вершинами в баз. Клітках. Розмічаємо вершини циклу, починаючи з вершини (i0,j0), починаючи зі знака -. Обчислюємо величини И (з штрихом і двома штрихами). Аналогічно до 2а знаходимо И. Та зменшуємо/збільшуємо перевозки.

Отримавши новий базисний план. Переходимо до п.1.

28. Знаходження початкового базисного плану

Для того щоб побудувати почтк. базисний план недостатньо здійснити попередній розподіл перевозок одним з відомих методів. Зауважимо також що ТЗО може взагалі не мати розв'язків. Наприклад якщо сумарна пропускна здатність комунікацій, які виходять з п-ту виробництва Рі буде менша за к-ть запасів одиниць продукції в п-ті Рі:

Знайти поч.. баз план для ТЗО можна з допомогою такої процедури:

І(попередній етап):

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

для клітки з інд (i1,j1) встановлюємо величину перевезення рівною величині :

при цьому розрізняємо 3 випадки:

(від виробника i1 забрали всю продукцію)

покладаємо величину перевезень (!!!)

стрічку з індексом i1 викреслюємо з таблиці , вона заповнена , у випадку б) аналогічно :

стовпчик з індексом j1 вик. з таблиці. Він заповнений

викреслюємо з табл. тільки клітку (i1,j1) змінивши при цьому відповідним чином величини запасів та потреб.

Якщо трансп. задача заповнена переходимо до п.2. інакше п.1 повторюємо.

2. отриманий план перевезень обмеження :

позначимо величиною

з умови збалансованості задача очевидне виконання співвідношення :

Позначимо цю величину щ.

Якщо щ=0 побудований план перевезень є базисним планом. Переходимо до етапу ІІ.

Якщо ж щ>0 то будуємо розширену ТЗО.

Введемо в розгляд виробника з індексом Р(м+1) та споживача з індексом Q(n+1) з можливостями в щ одиниць відповідно. Покладемо вартість перевезення одиниці продукції з п-ту Р(м+1) в б-я п-т споживання крім n+1 рівній М. Аналогічно вартість перевезення одиниці продукції з б-я п-ту вир крім м+1 в п-ту спож n+1 рівного числу М (тому ж самому). Вартість перевезення одиниці продукції з Р(м+1) в Q(n+1) поставимо = 0.

Всім додатковим комунікаціям, що виходять з даного пункту та входять в Q(n+1) поставимо пропускну здатність = безмежність». Можна довести, що побудований план перевезень є базисним планом для розширеної ТЗО. Розвіємо розширену ТЗО методом потенціалів, при цьому її розв'язок буде знайдено за скінченну к-ть ітерацій.

Викреслюємо з останньої таблиці стрічку m+1 та стовпчик n+1. Отриманий план перевезень буде початковим базисним планом для початкової ТЗО.

Етап ІІ: розв'язуємо ТЗО методом потенціалів з відомим початковим баз. Планом.

29. Задача про найкоротший шлях. Метод Мінті

Постановка задачі. Нехай задана мережа (IU) та дві вершини і₁ і₂, Які будемо називати початковим і кінцевим пунктами. Вважаємо, що обмеження на пропускні здатності дуг відсутнє, а величини с_ij будемо трактувати як довжину дуги (i,j)єU. Для того, щоб забезпечити існування потоку в мережі, який буде складатися тільки з 0 і 1, вважатимемо інтенсивність першини d_i1=1 d_is=-1, а всі решта мають інтенсивність 0. Задача полягає в знаходженні найкоротшого шляху з вершини і1 в вершину is. Для розв'язування цієї задачі можна використати т-зв метод Мінті, який, в принципі, розв'язує дещо складнішу задачу - знаходження найкоротших шляхів із заданої вершини i1 у всі інші вер. мережі. Запишемо алгоритм цього методу та проаналізуємо його використання п-дом.