Глава 1. Предмет і завдання дослідження операцій.

§ 1. Що таке дослідження операцій і чим воно займається.

§ 2. Основні поняття і принципи дослідження операції.

§ 3. Математичні моделі операцій.

Глава 2. Різновиди завдань дослідження операцій і підходів до їх вирішення.

§ 4. Прямі та обернені задачі дослідження операцій. Детерміновані задачі.

§ 5. Проблема вибору рішення в умовах невизначеності.

§ 6. багатокритеріальні задачі дослідження операцій. "Системний підхід".

Глава 3. Лінійне програмування.

§ 7. Завдання лінійного програмування.

§ 8. Основне завдання лінійного програмування.

§ 9. Існування рішення 03ЛП і способи його знаходження.

§ 10. Транспортна задача лінійного програмування.

§ 11. Завдання цілочисельного програмування. Поняття про нелінійному програмуванні.

Глава 4. Динамічне програмування.

§ 12. Метод динамічного програмування.

§ 13. Приклади рішення задач динамічного програмування.

§ 14. Завдання динамічного програмування в загальному вигляді. Принцип оптимальності.

Глава 5. Марковские випадкові процеси.

§ 15. Поняття про марковском процесі.

§ 16. Потоки подій.

§ 17. Рівняння Колмогорова для ймовірностей станів. Фінальні ймовірності станів.

Глава 6. Теорія масового обслуговування.

§ 18. Задачі теорії масового обслуговування. Класифікація систем масового обслуговування.

§ 19. Схема загибелі і розмноження. Формула Літтла.

§ 20. Найпростіші системи масового обслуговування та їх характеристики.

§ 21. Більш складні задачі теорії масового обслуговування.

Глава 7. Статистичне моделювання випадкових процесів (метод Монте-Карло).

§ 22. Ідея, призначення та область застосування методу.

§ 23. Єдиний жереб і форми його організації.

§ 24. Визначення характеристик стаціонарного випадкового процесу по одній реалізації.

Глава 8. Ігрові методи обгрунтування рішення.

§ 25. Предмет і задачі теорії ігор.

§ 26. Антагоністичні матричні гри.

§ 27. Методи вирішення кінцевих ігор.

§ 28. Задачі теорії статистичних рішенні.

ПРЕДМЕТ І ЗАВДАННЯ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

Основні поняття і принципи дослідження операцій

У цьому параграфі ми познайомимося з термінологією, основними поняттями та принципами науки «дослідження операцій».

Операцією називається всяке захід (система дій), об'єднане єдиним задумом і спрямоване до досягнення якоїсь мети (всі заходи, розглянуті в пунктах 1 - 8 попереднього параграфа, є «операціями»).

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

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

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

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

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

Ті параметри, сукупність яких утворює рішення, називаються елементами рішення. Як елементи рішення можуть фігурувати різні числа, вектори, функції, фізичні ознаки і т. Д. Наприклад, якщо складається план перевезень однорідних вантажів з пунктів відправлення А 1, А 2, ..., А mв пункти призначення В 1,В 2, ..., В n, то елементами рішення будуть числа x ij , показують, яка кількість вантажу буде відправлено з 1-го пункту відправлення А i в j-й пункт призначення В j. сукупність чисел x 11 , x 12, …, x 1 n, ..., x m 1, x m 2, ..., x mnутворює рішення.

У найпростіших завданнях дослідження операцій кількість елементів рішення може бути порівняно невелика. Але в більшості завдань, що мають практичне значення, число елементів рішення дуже велике, в чому читач може переконатися, спробувавши самостійно виділити і «назвати по імені» елементи рішення в прикладах 1 - 8 попереднього параграфа. Для спрощення ми будемо всю сукупність елементів рішення позначати однією літерою x і говорити «рішення х ».

Крім елементів рішення, якими ми, в якихось межах, можемо розпоряджатися, в будь-якому завданні дослідження операцій є ще і задані, «дисциплінують» умови, які фіксовані з самого початку і порушені бути не можуть (наприклад, вантажопідйомність машини; розмір планового завдання ;

вагові характеристики обладнання і т. п.). Зокрема, до таких умов відносяться засоби (матеріальні, технічні, людські), якими ми вправо розпоряджатися, і інші обмеження, що накладаються на рішення. У своїй сукупності вони формують так зване «безліч можливих рішень».

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

Йдеться про те, щоб в безлічі можливих рішень Х виділити ті рішення х (Іноді - одне, а частіше - цілу область рішень), які з тієї чи іншої точки зору ефективніше (вдаліше, зручніше) інших. Щоб порівнювати між собою по ефективності різні рішення, потрібно мати якийсь кількісний критерій, так званий показник ефективності (його часто називають «цільовою функцією»). Цей показник вибирається так, щоб він відображав цільову спрямованість операції. «Кращим» буде вважатися те рішення, яке в максимальному ступені сприяє досягненню поставленої мети. Щоб вибрати, «назвати по імені» показник ефективності W, потрібно, перш за все, запитати себе: чого ми хочемо, до чого прагнемо, роблячи операцію? Вибираючи рішення, ми, природно, віддамо перевагу таке, яке звертає показник ефективності W в максимум (або ж в мінімум). Наприклад, дохід від операції хотілося б звернути в максимум; якщо ж показником ефективності є витрати, їх бажано звернути в мінімум. Якщо показник ефективності бажано максимізувати, ми це будемо записувати у вигляді W \u003d\u003e mах, а якщо мінімізувати - W \u003d\u003e min.

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

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

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

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

1. План постачання підприємств. Завдання операції - забезпечити постачання сировиною при мінімальних витратах на перевезення. показник ефективності R - сумарні витрати на перевезення сировини за одиницю часу, наприклад, місяць ( R \u003d\u003e min).

2. Споруда ділянки магістралі. Потрібно так спланувати будівництво, щоб закінчити його якомога швидше. Природним показником ефективності був би час завершення будівництва, якби воно не було пов'язано з випадковими факторами (відмови техніки, затримки у виконанні окремих робіт). Тому в якості показника ефективності можна вибрати середнє очікуване час Т закінчення будівництва (Т \u003d\u003e min).

3. Продаж сезонних товарів. Як показник ефективності можна взяти середню очікувану прибуток П від реалізації товарів за сезон (П \u003d\u003e max).

4. снігозахист доріг. Йдеться про найбільш вигідному економічно плані снігозахист, тому в якості показника ефективності можна вибрати середні за одиницю часу (наприклад, за рік) витрати R на утримання та експлуатацію доріг, включаючи витрати, пов'язані як зі спорудженням захисних пристроїв, так і з розчищенням доріг і затримками транспорту (R \u003d\u003e min).

5. Протичовневий рейд. Так як рейд має цілком певну мету А - знищення човна, то в якості показника ефективності слід вибрати ймовірність Р(A) Того, що човен буде знищена.

6. Вибірковий контроль продукції. Природний показник ефективності, підказаний формулюванням завдання, це середні очікувані витрати R на контроль за одиницю часу, за умови, що система контролю забезпечує заданий рівень якості, наприклад, середній відсоток браку не вище заданого ( R\u003d\u003e Min).

7. Медичне обстеження. Як показник ефективності можна вибрати середній відсоток (частку) Q хворих і носіїв інфекції, яких вдалося виявити (Q \u003d\u003e шах).

8. Бібліотечне обслуговування. У формулюванні завдання свідомо допущена деяка нечіткість:

неясно, що означає «найкраще обслуговування абонентів» або «задоволення їх запитів в максимальній мірі». Якщо про якість обслуговування судити за часом, яке запитав книгу абонент чекає її отримання, то в якості показника ефективності можна взяти середній час Т очікування книги читачем, які подали на неї заявку ( Т\u003d\u003e Min). Можна підійти до питання і з дещо інших позицій, вибравши в якості показника ефективності середнє число Мкниг, виданих за одиницю часу (М \u003d\u003e mах).

Розглянуті приклади спеціально підібрані настільки простими, щоб вибір показника ефективності був порівняно неважкий і прямо диктувався словесної формулюванням завдання, її (майже завжди) однозначної цільовою спрямованістю. Однак на практиці це далеко не завжди буває так. У цьому читач може переконатися, спробувавши, наприклад, вибрати показник ефективності роботи міського транспорту. Що взяти в якості такого показника? Середню швидкість пересування пасажирів по місту? Або середня кількість перевезених пасажирів? Або середня кількість кілометрів, яке доведеться пройти пішки людині, якого транспорт не може доставити до потрібного місця? Тут є над чим поміркувати!

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

Приклади розв'язання задач динамічного програмування

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

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

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

Як це зробити? Можна вчинити одним з двох способів: або перебрати всі можливі варіанти шляху, і вибрати той, на якому витрати мінімальні (а при великій кількості відрізків це дуже і дуже важко!); або розділити процес переходу з А в В на окремі кроки (один крок - один відрізок) і оптимізувати управління по кроках. Виявляється, другий спосіб незрівнянно зручніше! тут, як і всюди в дослідженні операцій, позначаються переваги цілеспрямованого, організованого пошуку рішення перед наївним «сліпим» перебором.

Продемонструємо, як це робиться, на конкретному прикладі. Розділимо відстань від А до В в східному напрямку, скажімо, на 7 частин, а в північному - на 5 частин (в принципі дроблення може бути як завгодно дрібним). Тоді будь-який шлях з А в В складається з т \u003d 7 + 5 \u003d\u003d 12 відрізків, спрямованих на схід або на північ (рис. 13.2). Проставимо на кожному з відрізків число, що виражає (в якихось умовних одиницях) вартість прокладки шляху по цьому відрізку. Потрібно вибрати такий шлях з А в В, для якого сума чисел, що стоять на відрізках, мінімальна.

Будемо розглядати споруджуваний шлях як керовану систему S, переміщається під впливом управління з початкового стану А в кінцеве В.Стан цієї системи перед початком кожного кроку буде характеризуватися двома координатами: східної (Х) і північній (У), обидві - цілочисельні (0 х 5 7, 0 у 5). Для кожного з станів системи (вузловий точки прямокутної сітки на рис. 13.2) ми повинні знайти умовне оптимальне управління: йти нам з цієї точки на північ (управління «с») або на схід (управління «в»). Вибирається це управління так, щоб вартість всіх, хто лишився до кінця кроків (включаючи даний) була мінімальна. Цю вартість ми як і раніше будемо називати «умовним оптимальним виграшем» (хоча в даному випадку це не «виграш», а «програш») для даного стану системи S перед початком чергового кроку.

Процедуру умовної оптимізації будемо розгортати в зворотному напрямку - від кінця до початку. Перш за все зробимо умовну оптимізацію останнього, 12-го кроку. Розглянемо окремо правий верхній кут нашої прямокутної сітки (рис. 13.3). Де ми можемо перебувати після 11-го кроку? тільки

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

Тепер давайте оптимізувати передостанній (11-й) крок. Після предпредпоследнего (10-го) кроку ми могли опинитися в одній з точок З 1, З 2, З 3 (Рис. 13.4). Знайдемо для кожної з них умовне оптимальне управління і умовний оптимальний виграш. для точки З 1 управління вимушене: йти на схід;

обійдеться це нам до кінця в 21 одиницю (11 на даному етапі, плюс 10, записаних в гуртку при В 1).Число 21 записуємо в гуртку при точці З 1 . для точки З 2 управління вже не вимушене: ми можемо йти як на схід, так і на північ. У першому випадку ми витратимо на даному етапі 14 одиниць і від В 2 до кінця - ще 14, всього 28 одиниць. Якщо підемо на північ, витратимо 13 + 10, всього 23 одиниці. Значить, умовне оптимальне керування в точці З 2 - йти на північ (відзначаємо це стрілкою, а число 23 записуємо в гуртку у З 2), для точки З 3 управління знову вимушене ( «с»), обійдеться це до кінця в 22 одиниці (ставимо стрілку на північ, число 22 записуємо в гуртку при З 3).

Аналогічно, «задкуючи» від передостаннього кроку назад, знайдемо для кожної точки з цілочисельними координатами умовне оптимальне керування ( «с» або «в»), яке позначимо стрілкою, і умовний оптимальний виграш (витрата до кінця шляху), який запишемо в гуртку. Обчислюється він так: витрата на даному етапі складається з уже оптимізованим витратою, записаним в гуртку, куди веде стрілка. Таким чином, на кожному кроці ми оптимізуємо тільки цей крок, а наступні за ним - вже оптимізовані. Кінцевий результат процедури оптимізації показаний на рис. 13.5.

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

W * \u003d 118.

Тепер залишається побудувати безумовне оптимальне керування - траєкторію, яка веде з А і В найдешевшим способом. Для цього потрібно тільки «слухатися стрілок», т. Е. Прочитати, що вони наказують робити на кожному кроці. Така оптимальна траєкторія відзначена на рис. 13.5 двічі обведеними кружками. Відповідне безумовне оптимальне керування буде:

х * \u003d (С, з, с, з, в, в, с, в, в, в, в, в),

т. е. перші чотири кроки ми повинні робити на північ, наступні два - на схід, потім знову один на північ і інші п'ять - на схід. Завдання вирішена.

Зауважимо, що в ході умовної оптимізації ми можемо зіткнутися з випадком, коли обидва керування для якоїсь точки на площині є оптимальними, т. Е. Призводять до однакового витраті коштів від цієї точки до кінця, Наприклад, в точці з координатами (5; 1) обидва управління «с» і «в» є оптимальними і дають витрата до кінця рівним 62. з них ми довільно вибираємо будь-який (в нашому випадку ми вибрали «с»; з тим же успіхом ми могли б вибрати «в»). Такі випадки неоднозначного вибору оптимального управління постійно зустрічаються в динамічному програмуванні; в подальшому ми спеціально відзначати їх не будемо, а просто виберемо довільно будь-який з рівноцінних варіантів. Від цього свавілля, зрозуміло, може залежати оптимальне управління всім процесом, але не оптимальний виграш. Взагалі, в задачах динамічного програмування (як і в завданнях лінійного) рішення далеко не завжди єдине.

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

х \u003d (с, с, в, в, в, в, с, в, в, в, з, с).

Підрахуємо витрати для цієї траєкторії. Вони дорівнюватимуть W \u003d 10 +12 + 8 + 10 +11 +13 + 15 + 8 + + 10 + 9 + 8 + 14 \u003d 128, що безумовно більше, ніж W * \u003d 118. В даному випадку різниця не дуже велика, але в інших вона може бути істотною.

У вирішеною вище завданню умови були навмисно до крайності спрощені. Зрозуміло, ніхто не буде вести залізничну колію «сходами», переміщаючись тільки строго на північ або строго на схід. Таке спрощення ми зробили для того, щоб в кожній точці вибирати тільки з двох управлінь: «с» або «в». Можна було б замість двох можливих напрямків ввести їх кілька і, крім того, взяти кроки подрібніше; принципового значення це не має, але, зрозуміло, ускладнює і подовжує розрахунки.

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

Зробимо одне попутне зауваження. Уважний читач, мабуть, зауважив, що в нашій задачі точки А і В (Початок і кінець) в принципі нічим один від одного не відрізняються: можна було б будувати умовні оптимальні керування не з кінця до початку, а з початку до кінця, а безумовні - в зворотному напрямку. Дійсно, це так: в будь-якій задачі динамічного програмування «початок» і «кінець» можна поміняти місцями. Це абсолютно рівносильно описаної раніше методиці в розрахунковому відношенні, але дещо менш зручно при словесному поясненні ідеї методу: легше аргументувати, посилаючись на «вже сформовані» умови до початку даного кроку, ніж на ті, які ще «мають бути» після цього кроку. По суті ж обидва підходи абсолютно рівнозначні.

2. Завдання про розподіл ресурсів. Метод динамічного програмування дозволяє з успіхом вирішувати багато економічні завдання (див., Наприклад,). Розглянемо одну з найпростіших таких завдань. У нашому розпорядженні є якийсь запас коштів (ресурсів) К, який повинен бути розподілений між тпідприємствами П 1, П 2, ..., П m. Кожне з підприємств П i при вкладенні в нього якихось коштів х приносить дохід, який залежить від x, Т. Е. Що представляє собою якусь функцію ( x). Всі функції ( x) (i = 1, 2, ..., т) задані (зрозуміло, ці функції - неубутних). Питається, як потрібно розподілити кошти К. між підприємствами, щоб в сумі вони дали максимальний дохід?

Це завдання легко вирішується методом динамічного програмування .. Хоча в своїй постановці вона не містить згадки про час, можна все ж операцію розподілу коштів подумки розгорнути в якийсь послідовності, вважаючи за перший крок вкладення коштів в підприємство П 1, за другий - в П 2 і т. д.

керована система S в даному випадку - кошти або ресурси, які розподіляються. стан системи S перед кожним кроком характеризується одним числом S - готівковим запасом ще не вкладених коштів. У цьому завданні «кроковими управліннями» є кошти х 1, х 2, ..., х 3, виділяються підприємствам. Потрібно знайти оптимальне управління, т. Е. Таку сукупність чисел х 1, х 2, ..., х m, при якій сумарний дохід максимальний:

(13.1)

Вирішимо цю задачу спочатку в загальному, формульному вигляді, а потім - для конкретних числових даних. Знайдемо для кожного i-го кроку умовний оптимальний виграш (від цього кроку і до кінця), якщо ми підійшли до цього кроку з запасом коштів S. Позначимо умовний оптимальний виграш W i (S), а відповідне йому умовне оптимальне керування - кошти, вкладені в i-е підприємство, - x i (S).

Почнемо оптимізацію з останнього, т -го кроку. Нехай ми підійшли до цього кроку з залишком коштів S. Що нам робити? Очевидно, вкласти всю суму Sцілком в підприємство П m. Тому умовне оптимальне керування на m-м кроці: віддати останньому підприємству всі наявні засоби S, т. е.

а умовний оптимальний виграш

W m (S) \u003d (S).

Переймаючись цілою гамою значень S (Розташовуючи їх досить тісно), ми для кожного значення S знатимемо x m (S) і W m (S). Останній крок оптимізований.

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

,

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

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

і відповідне йому умовне оптимальне керування x i (S) - то значення х, при якому цей максимум досягається.

Продовжуючи таким чином, дійдемо, нарешті, до 1-го підприємства П 1. Тут нам не потрібно буде варіювати значення S; ми точно знаємо, що запас коштів перед першим кроком дорівнює К:

Отже, максимальний виграш (дохід) від усіх підприємств знайдений. Тепер залишається тільки «прочитати рекомендації». те значення х, при якому досягається максимум (13.4), і є оптимальне управління на 1-му кроці. Після того як ми вкладемо ці кошти в 1-е підприємство, у пас їх залишиться К.«Читаючи» рекомендацію для цього значення S, виділяємо другому підприємству оптимальну кількість коштів:

,

і т. д. до кінця.

А тепер вирішимо чисельний приклад. Вихідний запас коштів К \u003d 10 (умовних одиниць), і потрібно його оптимальним чином розподілити між п'ятьма підприємствами (Т \u003d 5). Для простоти припустимо, що вкладаються тільки цілі кількості засобів. Функції доходу ( х) Задані в таблиці 13.1.

Таблиця 13.1

х
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

У кожному стовпці, починаючи з певної суми вкладень, доходи перестають зростати (реально це відповідає тому, що кожне підприємство здатне «освоїти» лише обмежена кількість коштів).

Зробимо умовну оптимізацію так, як це було описано вище, починаючи з останнього, 5-го кроку. Кожен раз, коли ми підходимо до чергового кроку, маючи запас коштів S, ми пробуємо виділити па цей крок ту чи іншу кількість коштів, беремо виграш па даному етапі по таблиці 13.1, складаємо з уже оптимізованим виграшем на всіх наступних кроках до кінця (враховуючи, що коштів у нас залишилося вже менше, як раз на таку кількість коштів, яке ми виділили) і знаходимо то вкладення, на якому ця сума досягає максимуму. Це вкладення і є умовне оптимальне керування на даному етапі, а сам максимум - умовний оптимальний виграш.

У таблиці 13.2 дані результати умовної оптимізації по всіх кроків. Таблиця побудована так: в першому стовпці даються значення запасу засобів S, з яким ми підходимо до цього кроку. Далі таблиця розділена на п'ять пар стовпців, відповідно номеру кроку. У першому стовпчику кожної пари наводиться значення

Таблиця 13.2

S	i \u003d 5	i \u003d 4	i \u003d 3	i \u003d 2	i \u003d 1
x 5(S)	W 5(S)	x 4(S)	W 4(S)	x 3(S)	W 3(S)	x 2(S)	W 2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

умовного оптимального управління, у другому - умовного оптимального виграшу. Таблиця заповнюється зліва направо, зверху вниз. Рішення на п'ятому - останньому - крок вимушений: виділяються всі засоби;

па всіх інших кроках рішення доводиться оптимізувати. В результаті послідовної оптимізації 5-го, 4-го, 3-го, 2-го і 1-го кроків ми отримаємо повний список всіх рекомендацій по оптимальному управлінню і безумовний оптимальний виграш W *за всю операцію - в даному випадку він дорівнює 5,6. В останніх двох стовпчиках таблиці 13.2 заповнена тільки один рядок, так, як стан системи перед початком першого кроку нам в точності відомо:

S 0 = К \u003d 10. Оптимальні управління на всіх етапах виділені рамкою. Таким чином, ми отримали остаточний висновок: треба виділити першому підприємству дві одиниці з десяти, другого - п'ять одиниць, третього - дві, четвертому - жодної, п'ятого - одну одиницю. При цьому розподілі дохід буде максимальний і дорівнює 5,6.

Щоб читачеві було зрозуміло, як заповнюється таблиця 13.2, продемонструємо це на одному зразку розрахунку. Нехай, наприклад, нам потрібно оптимізувати рішення х 3(7)- як чинити на третьому кроці, якщо ми підійшли до нього з запасом засобів S \u003d 7, і скільки максимум ми можемо виграти на всіх, хто лишився

Таблиця 13.3

x	7 - x		W 4(7 - x)	+W 4 (7 - x)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

кроках, включаючи третій? Припустимо, що всі кроки після третього (4-й і 5-й) вже оптимізовані, т. Е. Заповнені дві перші пари стовпців таблиці 13.2. знайдемо x 3 (7) і W 3(7). Для цього складемо допоміжну табличку (див. Таблицю 13.3). У першому її стовпці перераховані всі можливі вкладення х на третьому кроці, не перевищують S \u003d 7. У другому стовпці - те, що залишиться після такого вкладення від запасу засобів S \u003d 7. У третьому стовпці - виграш на третьому кроці від вкладення коштів х в третє підприємство заповнюється по стовпці (таблиці 13.1). У четвертому стовпці - оптимальний виграш на всіх, хто лишився кроках (четвертому і п'ятому) за умови, що ми підійшли до четвертого кроку з рештою засобами (заповнюється по стовпці i \u003d 4 таблиці 13.2). У п'ятому стовпці - сума двох виграшів: крокової і оптимізованого подальшого при даному вкладенні х в третій крок.

З усіх виграшів останнього стовпця вибирається максимальний (в таблиці 13.3 він дорівнює W 3(7) \u003d 3,6, а відповідне управління х(7) = 2).

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

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

Як приклад розглянемо задачу про завантаження машини (ми вже згадували про пий в попередньому розділі): є певний набір предметів П 1, П 2, ..., П n (кожен в єдиному екземплярі); відомі їх ваги q 1, q 2, ..., q n і вартості з 1, з 2, ..., з n. Вантажопідйомність машини дорівнює Q. Постає питання, які з предметів потрібно взяти в машину, щоб їх сумарна вартість (при сумарному вазі Q) була максимальна?

1. Основні поняття ІВ

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

ІВ включає в себе наступні розділи:

1) математичне програм. (Обгрунтування планів, програм господарської діяльності); воно включає в себе розділи: лінійне програм, нелінійне програм, динамічне програм

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

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

При вирішенні конкретної задачі управління застосування методів ІВ передбачає:

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

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

Основні поняття і визначення ІС.

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

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

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

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

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

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

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

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

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

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

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

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

2. Загальна задача лінійного програм. Оптим реш-е

Економіко-математична модель

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

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

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

Загальна схема формування моделі: I

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

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

3) кількісне вираження обраного критерію оптимальності у формі цільової функція; I

4) математична формулювання завдання, як завдання відшукання екстремуму цільової функції за умови виконання обмежень, що накладаються на змінні.

Загальна задача лінійного програмування має вид:

Дана система т лінійних рівнянь і нерівностей з п змінними

і лінійна функція

Необхідно знайти таке рішення системи X \u003d (x1, x2, ..., xj, ..., xn), де при якому лінійна функція F приймає оптимальне (тобто максимальне або мінімальне) значення.

Система (1) називається системою обмежень, а функція F - лінійною функцією, лінійної формою, цільовою функцією або функцією мети.

Більш коротко загальну задачу лінійного програмування можна представити у вигляді:

при обмеженнях:

Оптимальним рішенням (або оптимальним планом) завдання ЛП називається рішення X \u003d (x1, x2, ..., xj, ..., xn), системи обмежень (1), що задовольняє умові (3), при якому лінійна функція (2) приймає оптимальне (максимальне або мінімальне) значення.

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

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

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

4 . Елементи лінійної алгебри

Система m лінійних рівнянь з n змінними має вид

або в короткій записи

Будь-які m змінних системи m лінійних рівнянь з n змінними (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Для вирішення системи (2.1) за умови m< n сформулируем утверждение.

затвердження 2.1. Якщо для системиm лінійних рівнянь зn змінними (m < n) Ранг матриці коефіцієнтів при змінних дорівнює т, тобто існує хоча б одна група основних змінних, то ця система є невизначеною, причому кожному довільному набору значень неосновних змінних відповідає одне рішення системи.

Рішення X \u003d (x1, x2, ..., xn) системи (2.1) називається допустимим, якщо воно містить лише невід'ємні компоненти, тобто xj\u003e \u003d 0 для будь-яких j \u003d 1, n. В іншому випадку рішення називається неприпустимим.

Серед нескінченної кількості рішень системи виділяють так звані базисні рішення.

базовим рішенням системи т лінійних рівнянь з n змінними називається рішення, в якому все n-m неосновних змінних дорівнюють нулю.

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

Опуклі безлічі точок

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

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

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

Серед точок опуклого безлічі можна виділити внутрішні, граничні і кутові точки.

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

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

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

На рис. 2.4 наведені приклади різних точок багатокутника: внутрішньої (точки М), граничної (точка N) і кутових (точки А, В, С, D, Е). Точка А - кутова, так як для будь-якого відрізка, цілком належить многоугольнику, наприклад, відрізка АР, вона не є внутрішньою; точка А - внутрішня для відрізка KL, але цей відрізок не належить цілком многоугольнику.

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

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

Геометричний сенс рішень нерівностей, рівнянь і їх систем

Розглянемо рішення нерівностей.

Твердження 1. Безліч рішень нерівності з двома змінними a11x1 + a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>\u003d B1.

Для визначення шуканої півплощині (верхньої або нижньої) рекомендується поставити довільну контрольну точку, що не лежить на її кордоні - побудованої прямий. Якщо нерівність виконується в контрольній точці, то воно виконується і в усіх точках півплощини, що містить контрольну точку, і не виконується в усіх точках інший півплощині. І навпаки, в разі невиконання нерівності в контрольній точці, воно не виконується в усіх точках півплощини, що містить контрольну точку, і виконується в усіх точках інший півплощині. В якості контрольної точки зручно взяти початок координат О (0; 0), що не лежить на побудованій прямій.

Розглянемо безліч рішень систем нерівностей.

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

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

Координати кутових точок - вершин багатокутника знаходять як координати точок перетину відповідних прямих.

При побудові областей рішень систем нерівностей можуть зустрітися і інші випадки: безліч рішень - опукла багатокутна область (рис. 2.9, а); одна точка (рис. 2.9, б); порожня множина, коли система нерівностей несумісна (рис. 2.9, в).

5 . Геометричний метод розв'язання задач ЛП

оптимальне рішення задачі ЛП

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

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

Наступна теорема присвячена аналітичному методу знаходження кутових точок.

Теорема 2. Кожному допустимому базисного вирішення завдання ЛП відповідає кутова точка багатогранника рішень, і навпаки, кожній кутовій точці багатогранника рішень відповідає допустимий базисний розв'язок.

З теорем 1 і 2 безпосередньо випливає важливий наслідок: якщо завдання ЛП має оптимальне рішення, то воно збігається, по крайней мере, з одним з її допустимих базисних рішень.

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

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

Розглянемо задачу в стандартній формі з двома змінними (п = 2).

Нехай геометричним зображенням системи обмежень є багатокутник ABCDE (Рис. 4.1). Необхідно серед точок цього багатокутника знайти таку точку, в якій лінійна функція F \u003d c1x1 + c2x2 приймає максимальне (або мінімальне) значення.

Розглянемо так звану лінію рівня лінійної функції F, Тобто лінію, уздовж якої ця функція приймає одне і те ж фіксоване значення а, Тобто F = а, або c1x1 + c2x2 \u003d a.

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

Рівняння лінії рівня функції c1x1 + c2x2 \u003d a є рівняння прямої лінії. При різних рівнях а лінії рівня паралельні, так як їх кутові коефіцієнти визначаються тільки співвідношенням між коефіцієнтами c1 і c2 і, отже, рівні. Таким чином, лінії рівня функції F – це своєрідні "паралелі", розташовані зазвичай під кутом до осей координат.

Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зсуві лінії в одну сторону рівень тільки зростає, а при зміщенні в іншу сторону - тільки убуває. Вектор c \u003d (c1, c2), що виходить з початку координат, вказує напрямок найшвидшого зростання функції F. Лінія рівня лінійної функції перпендикулярна вектору c \u003d (c1, c2).

Порядок графічного рішення задачі ЛП:

1.Построіть багатокутник рішень.

2.Построіть вектор c \u003d (c1, c2), і перпен-но йому провести лінію рівня лінійної функції F, Наприклад, F \u003d 0.

3.Параллельним переміщенням прямої F \u003d 0 в напрямку вектора c (-c) знайти точку Amax (Bmin), в якій F досягає максимуму (мінімуму).

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

2.Вичісліть Fmax (Fmin).

Зауваження. Точка мінімуму - це точка «входу» в багатокутник рішень, а точка максимуму - це точка «виходу» з багатокутника.

6. Загальна ідея симплекс-методу. геометрична інтерпретація

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

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

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

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

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

Вперше симплексний метод був запропонований американським вченим Дж. Данцигом в 1949 р, проте ще в 1939 р ідеї методу були розроблені російським ученим Л.В. Канторовичем.

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

Для реалізації симплексного методу - послідовного поліпшення рішення - необхідно освоїти три основних елементи:

спосіб визначення будь-якого початкового допустимого базисного рішення задачі;

правило переходу на краще (точніше, не гіршому) рішенням;

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

Для використання симплексного методу завдання лінійного програмування повинна бути приведена до канонічного вигляду, тобто система обмежень має бути представлена \u200b\u200bу вигляді рівнянь.

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

7 . Алгоритм симплекс-методу.

Розглянемо рішення ЗЛП симплекс-методом і викладемо її стосовно до задачі максимізації.

1. За умовою завдання складається її математична модель.

2. Складена модель перетворюється до канонічної формі. При цьому може виділитися базис з початковим опорним планом.

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

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

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

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

5. Знайдений початковий опорний план досліджується на оптимальність:

а) якщо в F-рядку немає негативних елементів (не рахуючи вільного члена), то план оптимальний. Якщо при цьому немає і нульових, то оптимальний план єдиний; якщо ж є хоча б один нульовий, то оптимальних планів безліч;

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

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

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

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

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

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

2) складають відносини елементів стовпця вільних членів до відповідних елементів дозволяє стовпця, що мають однакові знаки (сімплексні відносини);

3) з симплексних відносин вибирають найменше. Воно і визначить роздільну рядок. Нехай нею буде, наприклад, р -строка;

4) на перетині дозволяють стовпця і рядка знаходять дозволяє елемент. Якщо що дозволяє виявився елемент y-рядки, то після симплексного перетворення вільний член цього рядка стане позитивним. В іншому випадку на наступному кроці знову звертаються до t-рядку. Якщо завдання можна вирішити, то через деякий число кроків в стовпці вільних членів не залишиться негативних елементів.

8. Метод оберненої матриці

Розглянемо ЛП виду:

A- матриця обмежень;

C \u003d (c1, c2, ..., cn) вектор-рядок;

X \u003d (x1, x2, ..., xn) - змінні;

- вектор правої частини.

Вважаємо, що всі рівняння лінійно незалежні, тобто rang (a) \u003d m. В цьому випадку базис - це мінор порядку матриці A. Тобто існує принаймні одна така подматріца B порядку m, що | B |<>0. Усі невідомі, відповідні B, називаються базисними. Всі інші вільними.

Нехай B- деякий базис. Тоді перестановкою стовпців матриці A завжди можна привести A до виду A \u003d (B | N),

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

Будь-яке рішення задачі (1) задовольняє умові A * x \u003d b, і, отже, система набуває такого вигляду:

Оскільки | B |<>0, то існує обернена матриця. Множимо зліва на зворотний, отримуємо:

- спільне рішення.

Базовим рішенням (щодо базису B) називається приватне рішення задачі (2), отримане за умови. Тоді визначається однозначно.

Базисне рішення називається реалізованим, Якщо.

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

Загалом вирішенні закладені всі рішення, які є. Повернемося до цільової функції. Вводимо Cb- коефіцієнти перед базисними змінними, Cn- інші.

Таким чином, отримуємо. Підставляємо із загального рішення:

Затвердження. Критерій оптимальності базисного рішення.

Припустимо. Тоді базисне рішення є оптимальним. Якщо, то базисне рішення не оптимально.

Док-во: Нехай. Розглянемо базисне рішення,.

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

Нехай є інше рішення: (Xb, Xn).

тоді дивимося

Т.о, базисне рішення саме min. Нехай, навпаки, не виконується, тобто існує.

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

Нехай відповідає вільної змінної Xi: Xj надаємо значення і вводимо її в базис, а іншу змінну виводимо і називаємо її вільною.

Як визначити? Всі вільні змінні, окрім, як і раніше рівні 0, а.

Тоді в загальному рішенні, де.

Винесемо: необхідна умова.

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

алгоритм:

1.Задача ЛП у стандартній формі.

2.Оставляем лінійно незалежні рівняння.

3.Находім матрицю B, таку що | B |<>0 і базисне рішення.

Рахуємо:

якщо, то оптимальне рішення є - це базисне рішення;

якщо, то знаходимо компоненту, надаємо, таким чином знайдемо інше рішення; - при якому одна з базисних змінних \u003d 0. Цю змінну викидаємо з базису, вводимо xi. Отримали новий базис B2, пов'язаний базису B1. Потім знову обчислюємо.

1.Якщо є оптимальне рішення, то через кінцеве число кроків ми його отримаємо.

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

9. Економічна інтерпретація завдання, двоїстої задачі про використання ресурсів

Завдання. Для виготовлення двох видів продукції P1 і P2 використовують чотири види ресурсів S1, S2, S3, S4. Дано запаси ресурсів, число одиниць ресурсів, що витрачаються на виготовлення одиниці продукції. Відома прибуток, одержуваний від одиниці продукції P1 і P2. Необхідно скласти такий план виробництва продукції, при якому прибуток від її реалізації буде максимальною.

завданняI (Вихідна):

F \u003d c1x1 + c2x2 + ... + CnXn-\u003e max при обмеженнях:

і умови невід'ємності x1\u003e \u003d 0, x2\u003e \u003d 0, ..., Xn\u003e \u003d 0

Скласти такий план випуску продукції X \u003d (x1, x2, ..., Xn), при якому прибуток (виручка) від реалізації продукції буде максимальною за умови, що споживання ресурсів за кожним видом продукції не перевершить наявних запасів

завданняII (Двоїста)

Z \u003d b1y1 + b2y2 + ... + BmYm-\u003e min

при обмеженнях:

і умови невід'ємності

y1\u003e \u003d 0, y2\u003e \u003d 0, ..., yn\u003e \u003d 0.

Знайти такий набір цін (оцінок) ресурсів Y \u003d (y1, y2, ..., yn), при якому загальні витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менш прибутку (виручки) від реалізації цієї продукції

У наведеній моделі bi (i \u003d 1,2, ..., m) позначає запас ресурсу Si; aij - число одиниць ресурсу Si, споживаного при виробництві одиниці продукції Pj (j \u003d 1,2, ..., n); cj- прибуток (виручка) від реалізації одиниці продукції Pj (або ціна продукції Pj) .

Припустимо, що деяка організація вирішила закупити ресурси S1, S2, ..., Sm підприємства і необхідно встановити оптимальні ціни на ці ресурси y1, y2, ..., ym. Очевидно, що купує організація зацікавлена \u200b\u200bв тому, щоб витрати на всі ресурси Z в кількостях b1, b2, ..., bm за цінами відповідно y1, y2, ..., ym були мінімальні, тобто Z \u003d b1, y1 + b2y2 + ... + bmym-\u003e min.

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

На виготовлення одиниці продукції P1 витрачається a11 одиниць ресурсу S1, a21 одиниць ресурсу S2, ...., Aj1 одиниць ресурсу Si1, ......, am1 одиниць ресурсу Sm за ціною відповідно y1, y1, ..., yi, ..., ym. Тому для задоволення вимог продавця витрати на ресурси, що споживаються при виготовленні одиниці продукції P1 повинні бути не менше її ціни c1, тобто a11y1 + a21y2 + ... + am1ym\u003e \u003d c1.

Аналогічно можна скласти обмеження у вигляді нерівностей по кожному виду продукції P1, P2, ... Pn. Економіко-математична модель та змістовна інтерпретація отриманої таким чином двоїстої задачі II наведені в правій частині таблиці.

Ціни ресурсів y1, y1, ..., yi, ..., ym в економічній літературі отримали різні назви: облікові, неявні, тіньові . Сенс цих назв полягає в тому, що це умовні , "Несправжні" ціни. На відміну від "зовнішніх" цін c1, c2, ..., cn на продукцію, відомих, як правило, до початку виробництва, ціни ресурсів y1, y2, ..., ym є внутрішніми , бо вони задаються не ззовні, а визначаються безпосередньо в результаті рішення задачі, тому їх найчастіше називають оцінками ресурсів.

10.Взаімно двоїсті завдання ЛП і їх властивості

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

Обидва завдання володіють наступними властивостями:

1.В одному завданню шукають максимум лінійної функції, в іншій - мінімум.

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

3.Каждая із завдань задана в стандартній формі, причому в задачі максимізації все нерівності виду "<=", а в задаче минимизации – все неравенства вида ">=".

4.Матріци коефіцієнтів при змінних в системах обмежень обох завдань є транспоновану один до одного.

5.Число нерівностей в системі обмежень однієї задачі збігається з числом змінних в іншому завданні.

6.Условія невід'ємності змінних зберігаються в обох задачах.

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

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

Кожній задачі ЛП можна поставити у відповідність двоїсту їй завдання.

11. Алгоритм складання двоїстої задачі:

1. Привести все нерівності системи обмежень вихідної задачі до одного змістом: якщо у вихідній задачі шукають максимум лінійної функції, то все нерівності системи обмежень привести до виду "<=", а если минимум – к виду ">\u003d ". Для цього нерівності, в яких дана вимога не виконується, помножити на -1.

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

3. Знайти матрицю, транспоновану до матриці A .

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

12. Перша теорема подвійності

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

Достатній ознака оптимальності.

якщо X * \u003d (x1 *, x2 *, ..., xn *) і Y * \u003d (y1 *, y2 *, ..., ym *) - допустимі рішення взаємно двоїстих задач, для яких виконується рівність,

то - оптимальне рішення вихідної задачі I, а - двоїстої задачі II.

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

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

Fmax = Zmin або F (X *) \u003d Z (Y *) .

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

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

Економічний сенс першої теореми подвійності.

План виробництва X * \u003d (x1 *, x2 *, ..., xn *) і набір цін (оцінок) ресурсів Y * \u003d (y1 *, y2 *, ..., ym *) виявляються оптимальними тоді і тільки тоді, коли прибуток (виручка) від реалізації продукції, знайдена при "зовнішніх" (відомих заздалегідь) цінах c1, c2, ..., cn, дорівнює витратам на ресурси по "внутрішнім" (визначеним тільки з рішення задачі) цінами y1 , y2, ..., ym. Для всіх же інших планів Х і Y обох завдань прибуток (виручка) від реалізації продукції завжди менше (або дорівнює) витрат на ресурси.

Економічний сенс першої теореми подвійності можна інтерпретувати і так: підприємству байдуже, виробляти чи продукцію по оптимальному плану X * \u003d (x1 *, x2 *, ..., xn *) і отримати максимальний прибуток (виручку) Fmax або продавати ресурси за оптимальними цінами Y * \u003d (y1 *, y2 *, ..., ym *) і відшкодувати від продажу рівні їй мінімальні витрати на ресурси Zmin.

13. Друга теорема подвійності

Нехай дано дві взаємно двоїсті задачі. Якщо кожну з цих завдань вирішувати симплексним методом, то необхідно привести їх до канонічного вигляду, для чого в систему обмежень задачі I (в короткій записи) слід ввести т невід'ємних змінних, а в систему обмежень задачі II () – n невід'ємних змінних, де i (j) - номер нерівності, в яке введена додаткова змінна.

Системи обмежень кожної з взаємно двоїстих задач приймуть вид:

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

Теорема. Позитивним (ненульовим) компонентам оптимального вирішення однієї з взаємно двоїстих задач відповідають нульові компоненти оптимального вирішення іншої задачі, тобто для будь-яких i \u003d 1,2, ..., m u j \u003d 1,2, ..., n: якщо X * j\u003e 0, то; якщо , То, і аналогічно,

якщо то ; якщо то.

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

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

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

14. Об'єктивно обумовлені оцінки та їх зміст

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

Додаткові змінні вихідної задачі I, що представляють різницю між запасами bi ресурсів S1, S2, S3, S4 і їх споживанням, висловлюють залишки ресурсів , а додаткові змінні двоїстої задачі II, що представляють різницю між витратами на ресурси для виробництва з них одиниці продукції і цінами cj продукції P1, P2 , висловлюють перевищення витрат над ціною.

Т.о, об'єктивно обумовлені оцінки ресурсів визначають ступінь дефіцитності ресурсів: по оптимальному плану виробництва дефіцитні (тобто повністю використовуються) ресурси отримують ненульові оцінки, а недефіцитних - нульові оцінки. Величина y * i є оцінкою i-го ресурсу. Чим більше значення оцінки y * i, тим вище дефіцитність ресурсу. Для недефіцитного ресурсу y * i \u003d 0.

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

Третя теорема подвійності . Компоненти оптимального рішення двоїстої завдання дорівнюють значенням приватних похідних лінійної функції Fmax(b1, b2,…, bm) за відповідними аргументів, тобто

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

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

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

1. Показником дефіцитності ресурсів і продукції.

2.Показателі впливу обмежень на значення цільової функції.

3.Показники ефективності виробництва окремих видів продукції з позицій критерію оптимальності.

4.Інструментом зіставлення сумарних умовних витрат і результатів.

15.Постановка транспортної задачі за критерієм вартості.

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

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

Найпростіша формулювання ТЗ за критерієм вартості наступна: в т пунктах відправлення A1, ..., Am знаходиться відповідно a1, ..., am одиниць однорідного вантажу (ресурси), який повинен бути доставлений n споживачам B1, ..., Bn в кількостях b1, ..., bn одиниць (потреби). Відомі транспортні витрати Cij перевезень одиниці вантажу з i-го пункту відправлення в j- й пункт споживання.

Потрібно скласти план перевезень, т. Е. Знайти, скільки одиниць вантажу має бути відправлено з i-го пункту відправлення в j- й пункт споживання так, щоб повністю задовольнити потреби і щоб сумарні витрати на перевезення були мінімальними.

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

Постачальник	споживач			запас вантажу
потреба

Тут кількість вантажу, що перевозиться з i-го пункту відправлення в j- й пункт призначення, так само xij, запас вантажу в i-му пункті відправлення визначається величиною ai\u003e \u003d 0, а потреба j-го пункту призначення у вантажі дорівнює bj\u003e \u003d 0 . Передбачається, що всі xij\u003e \u003d 0.

матриця називається матрицею тарифів (Витрат або транспортних витрат).

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

Загальні сумарні витрати, пов'язані з реалізацією плану перевезень, можна уявити цільовою функцією

Змінні xij повинні задовольняти обмеженням по запасах, по споживачах і умов невід'ємності:

- обмеження по запасах (2);

- обмеження по споживачах (2);

- умови невід'ємності (3).

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

Система обмежень задачі (1) - (3) містить m + n рівнянь з тn змінними. Передбачається, що сумарні запаси дорівнюють сумарним потребам, т. Е.

16. Ознака можливості розв'язання транспортної задачі

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

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

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

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

Якщо ж, то вводиться фіктивний (m + 1) -й пункт відправлення, якому приписують запас вантажу, що дорівнює.

Тарифи на доставку вантажів від цього фіктивного постачальника знову вважаємо рівними нулю. У матриці додасться один рядок, на цільову функцію це не вплине, а система обмежень задачі стане спільною, т. Е. Стане можливим відшукання оптимального плану.

Для транспортної задачі важливе значення має наступна теорема.

Теорема. Ранг матриці транспортної задачі на одиницю менше числа рівнянь, т. Е. r ( a )= m + n -1.

З теореми випливає, що кожен опорний план повинен мати (m-1) (n-1) вільних змінних, рівних нулю, і m + n-1 базисних змінних.

План перевезень транспортної задачі будемо відшукувати безпосередньо в розподільчій таблиці. Приймемо, що якщо змінна xij приймає значення, то в відповідну клітку (I, j) будемо записувати це значення, якщо ж xij \u003d 0, то клітку (I, j) залишимо вільною. З урахуванням теореми про ранг матриці в розподільній таблиці опорний план повинен міститиm + n-1 зайнятих клітин, А решта будуть вільні.

Зазначені вимоги до опорного плану не є єдиними. Опорні плани повинні задовольняти ще одній вимозі, пов'язаному з циклами.

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

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

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

1) допустимий план транспортної задачі є опорним тоді і тільки тоді, коли з зайнятих цим планом клітин можна утворити жодного циклу;

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

17. Побудова вихідного опорного плану

Правило «північно-західного кута».

Для складання вихідного плану перевезень зручно користуватися правилом «північно-західного кута», яке полягає в наступному.

Заповнюватимемо, починаючи з лівого верхнього, умовно званого «північно-західним кутом», рухаючись далі по рядку вправо або за стовпцем вниз. Занесемо в клітку (1; 1) менше з чисел a1 і b1, т. Е.. Якщо, то і перший стовпець «закритий», т. Е. Попит першого споживача задоволений повністю. Це означає, що для всіх інших клітин першого стовпчика кількість вантажу для .

Якщо, то аналогічно «закривається» перший рядок, т. Е., Для . Переходимо до заповнення сусідньої клітки (2; 1), в яку заносимо.

Заповнивши другу клітку (1; 2) або (2; 1), переходимо до заповнення наступної третьої клітки по другому рядку або по дві колонки. Будемо продовжувати цей процес до тих пір, поки на якомусь етапі не вичерпаються ресурси am і потреби bn. Остання заповнена клітина виявиться лежачої в останньому n-м стовпці і в останній m-му рядку.

Правило «мінімального елемента».

Вихідний опорний план, побудований за правилом «північно-західного кута», зазвичай виявляється досить далеким від оптимального, так як при його визначенні не враховуються величини витрат cij. Тому в подальших розрахунках буде потрібно багато ітерацій для досягнення оптимального плану. Число ітерацій можна скоротити, якщо вихідний план будувати за правилом «мінімального елемента». Сутність його полягає в тому, що на кожному кроці здійснюється максимально можливе «переміщення» вантажу в клітку з мінімальним тарифом cij. Заповнення таблиці починаємо з клітки, якої відповідає найменший елемент cij матриці тарифів. У клітку з найменшим тарифом поміщають менше з чисел ai або bj . Потім з розгляду виключають рядок, відповідну постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, попит якого повністю задоволений. Може виявитися, що слід виключити рядок і стовпець одночасно, якщо повністю витрачені запаси постачальника і повністю задоволений попит споживача. Далі з решти клітин таблиці знову вибирають клітку з найменшим тарифом і процес розподілу запасів продовжують до тих пір, поки всі вони не будуть розподілені, а попит задоволений.

18. Метод потенціалів

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

Суть методу потенціалів полягає в наступному. Після того як знайдений вихідний опорний план перевезень, кожному постачальнику (кожному рядку) ставимо у відповідність деяке число, зване потенціалом постачальника Ai, а кожному споживачеві (кожному колонку) - деяке число зване потенціалом споживача.

Вартість тонни вантажу в пункті дорівнює вартості тонни вантажу до перевезення + витрати на її перевезення:.

Щоб вирішити транспортну задачу методом потенціалів, необхідно:

1. Побудувати опорний план перевезень по одному з викладених правил. Число заповнених клітин має бути m + n-1.

2. Обчислити потенціали і відповідно постачальників і споживачів (для зайнятих клітин):. Число заповнених клітин - m + n-1, а число рівнянь - m + n. Оскільки число рівнянь на одиницю менше числа невідомих, то одне з невідомих виявляється вільним і може приймати будь-яке числове значення. Наприклад,. Решта потенціали для даного опорного рішення визначаться однозначно.

3. Перевірити на оптимальність, тобто для вільних клітин обчислити оцінки. Якщо, то перевезення доцільна і план X оптимальний - ознака оптимальності. Якщо хоча б одна різниця, то переходять до нового опорного плану. За своїм економічним змістом величина характеризує те зміна в сумарних транспортних витратах, яке відбудеться через здійснення одиничної поставки i-м постачальником j-му споживачеві. Якщо, то одинична поставка призведе до економії транспортних витрат, якщо ж - до збільшення їх. Отже, якщо серед вільних напрямків поставок немає заощаджують транспортні витрати напрямків, то отриманий план оптимальний.

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

а) Кожній з клітин, пов'язаних циклом з даної вільної кліткою, приписують певний знак, причому даної вільної клітині «+», а всім іншим клітинам (вершин циклу) - по черзі знаки «-» і «+». Будемо називати ці клітини мінусовими і позитивними.

б) У мінусових клітинах циклу знаходимо мінімальну поставку, яку позначимо через. До цієї вільну клітину переносять менше з чисел xij, що стоять в мінусових клітинах. Одночасно це число додають до відповідних числах, що стоять в клітинах зі знаком «+», і віднімають з чисел, що стоять в мінусових клітинах. Клітка, яка раніше була вільною, стає зайнятою і входить в опорний план; а мінусова клітина, в якій стояло мінімальне з чисел xij, вважається вільною і виходить з опорного плану.

Т.ч., визначили новий опорний план. Описаний вище перехід від одного опорного плану до іншого називається зрушенням по циклу перерахунку. При зсуві по циклу перерахунку число зайнятих клітин залишається незмінним, а саме залишається рівним m + n-1. При цьому якщо в мінусових клітинах є два або більше однакових числа xij, то звільняють лише одну з таких клітин, а решта залишають зайнятими з нульовими поставками.

5. Отриманий опорний план перевіряють на оптимальність, тобто повторюють всі дії з п.2.

19. Поняття про динамічний програмуванні.

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

Зазвичай методами ДП оптимізують роботу деяких керованих систем, ефект якої оцінюється адитивної, або мультипликативной, Цільовою функцією. адитивноїназивається така функція кількох змінних f (x1, x2, ..., xn), значення якої обчислюється як сума деяких функцій fj, що залежать тільки від однієї змінної xj:. Складові адитивної цільової функції відповідають ефекту рішень, прийнятих на окремих етапах керованого процесу.

Принцип оптимальності Р. Беллмана.

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

1. об'єктом дослідження повинна служити керована система (Об'єкт) з заданими припустимими станами і допустимими управліннями;

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

3. завдання не повинна залежати від кількості кроків і бути визначеною на кожному з них;

4. стан системи на кожному кроці має описуватися однаковим (за складом) набором параметрів;

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

Розглянемо питання застосування моделі динамічного програмування в узагальненому вигляді. Наприклад, потрібно управління деяким абстрактним об'єктом, який може перебувати в різних станах. Поточний стан об'єкта ототожнити з деяким набором параметрів, який позначається в подальшому S і називається вектором стану. Передбачається, що задано безліч S всіх можливих станів. Для об'єкта визначено також безліч допустимих управлінь (Керуючих впливів) X, яке, не применшуючи спільності, можна вважати числовим безліччю. Керуючі впливи можуть здійснюватися в дискретні моменти часу, причому управлінське рішення полягає у виборі одного з управлінь. планом завдання або стратегією управління називається вектор x \u003d (x1, x2, ..., xn-1), компонентами якого служать управління, обрані на кожному кроці процесу. З огляду на передбачуваного відсутність післядії між кожними двома послідовними станами об'єкта Sk і Sk + 1, існує відома функціональна залежність, що включає також вбрання управління:. Тим самим завдання початкового стану об'єкта та вибір плану х однозначно визначають траєкторію поведінки об'єкта.

Ефективність управління на кожному кроці k залежить від поточного стану Sk, обраного управління xk і кількісно оцінюється за допомогою функцій fk (xk, Sk), що є складовою частиною адитивної цільової функції , характеризує загальну ефективність управління об'єктом. (Відзначимо , що в визначення функції fk (xk, Sk) включається область допустимих значень xk , і ця область, як правило, залежить від поточного стану Sk). оптимальне керування , при заданому початковому стані S1, зводиться до вибору такого оптимального плану x * , при якому досягається максимум суми значень fk на відповідній траєкторії.

Основний принцип динамічного програмування полягає в тому, що на кожному кроці слід прагнути не до ізольованої оптимізації функції fk (xk, Sk), а вибирати оптимальне управління x * k в припущенні про оптимальність всіх наступних кроків. Формально вказаний принцип реалізується шляхом відшукання на кожному кроці k умовних оптимальних управлінь , Які забезпечують найбільшу сумарну ефективність починаючи з цього кроку, в припущенні, що поточним є стан S.

Позначимо Zk (s) максимальне значення суми функцій fk протягом кроків від k до п (Отримується при оптимальному управлінні на даному відрізку процесу), за умови, що об'єкт на початку кроку k знаходиться в стані S. Тоді функції Zk (s) повинні задовольняти рекурентному співвідношенню:

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

Оптимальна стратегія управління повинна задовольняти наступні умови: яким би не було початковий стан sk на k-му кроці і вбрання на цьому кроці управління xk, наступні управління (управлінські рішення) повинні бути оптимальними по відношенню до cocmo янию , Отримувати в результаті рішення, прийнятого на кроці k .

Основне співвідношення дозволяє визначити функції Zk (s) тільки в поєднанні з початковою умовою, яким в нашому випадку є рівність.

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

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

20. Поняття про ігрові моделях.

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

Для кожної формалізованої гри вводяться правила , тобто система умов, яка визначає: 1) варіанти дій гравців; 2) обсяг інформації кожного гравця про поведінку партнерів; 3) виграш, до якого приводить кожна сукупність дій. Як правило, виграш (або програш) може бути заданий кількісно; наприклад, можна оцінити програш нулем, виграш - одиницею, а нічию - 1/2. Кількісна оцінка результатів гри називається платежем .

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

гра називається грою з нульовою сумою, або антагоністичний ської , якщо виграш одного з гравців дорівнює програшу іншого, тобто сума виграшів обох сторін дорівнює нулю. Для повного завдання гри досить вказати величину одного зних . якщо позначити а - виграш одного з гравців, b – виграш іншого, то для гри з нульовою сумою b \u003d –а, Тому досить розглядати, наприклад а.

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

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

Деякі ігри можуть складатися тільки з випадкових ходів (так звані чисто азартні ігри) або тільки з особистих ходів (шахи, шашки). Більшість карткових ігор належить до ігор змішаного типу, т. Е. Містить як випадкові, так і особисті ходи. Надалі ми будемо розглядати тільки особисті ходи гравців.

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

Одним з основних понять теорії ігор є поняття стратегії .

стратегією гравця називається сукупність правил, що визначають вибір його дії при кожному особистому ході в залежності від ситуації, що склалася. Зазвичай в процесі гри при кожному особистому ході гравець робить вибір в залежності від конкретної ситуації. Однак в принципі можливо, що всі рішення прийняті гравцем заздалегідь (у відповідь на будь-яку ситуацію, що склалася). Це означає, що гравець вибрав певну стратегію, яка може бути задана у вигляді списку правил або програми. (Так можна здійснити гру за допомогою ЕОМ). гра називається {!LANG-4c160ecfe60a55b3bb97dc56dc726e27!} , {!LANG-c6bfe812d1456d0a991e7bdf1a611115!} {!LANG-e259e3b9d8cda0b21acdee07b55bd05c!} .– {!LANG-9b96f9905d846d68573dea156261307c!}

{!LANG-be3f62697691f2ec9965a9497864641d!} {!LANG-5588dfefa0d09bf688dbae260ff98c1a!} {!LANG-45126f0108c2fc161307ae483dc525da!} , {!LANG-43396af9f92c294a8a6b3ebfe4525705!} {!LANG-a521dd85bcf29b3d515578cd82d33be3!} , {!LANG-5dcb8508d4d788eb8861c0999353a03e!} {!LANG-4a6b62af2686cb04bb72ec87106b26ec!} , {!LANG-826a9fb8f0c23e6c86919b31f62ca679!} {!LANG-9f8662833576ffde055bc167ecf62273!} {!LANG-a7da787032230eeca5b60bbbf7001855!} {!LANG-8ef8b84003734ecc6b705eae50abc0da!} , {!LANG-18a15704e1d51cb9220ce72e3abcf13f!} {!LANG-af0b1ddd4c0b4bfd4c335b72de478756!} . {!LANG-a6ec14b685adc22e52df7abbdaa7c652!} {!LANG-6e7f61ca7ec3dfecefc50898fc856ab1!} , {!LANG-77c9dc72cc2750a901caaaf25ad8ef28!}

{!LANG-c6559207b398259eed36283f6bd10651!} {!LANG-b4deb9012718710ef136359d8252ff7e!} {!LANG-266fea6d536da686728c80fb76373199!} {!LANG-b41829729d8fbc4568ffc9cacf498bfa!}

{!LANG-bcd78ac1f473c0ce2ef3557edf4445e5!}

21. {!LANG-9964070d6762a95fc666c7ab2dddcd8c!}

{!LANG-021de19c1ab4b81082949118e9c51719!} А{!LANG-f8001df60460c19e32c53ffc3069c216!} т{!LANG-1c461c81939fea2278c6783a1622d6a0!} {!LANG-fc4be3ae14dfddf987fb61ef97944b51!}{!LANG-c405606eb0de9a71683c16cac3c718ef!}

{!LANG-976c4e29a4d04cde78c414a3882b4083!} А і В{!LANG-9d6a1be8247f0e1742b4644ac25c32e8!}

{!LANG-35638f75e252deaccf04cbc165688ea1!} А{!LANG-bdb530a69fe1dd9ef838d8a356213922!} т{!LANG-a87c32fb1485e9750defecc8ac348f4b!} В{!LANG-6fc519c00be58bf7015ea4b58f2d3585!} n{!LANG-5dc7ea4c00310b0bdcb72cff51f54ec1!}

{!LANG-31e0dd7194b030c4b6318862fd076829!} А{!LANG-8afa8777afa6d89067f1cdeb4dc6cdd4!} В.

{!LANG-9aa3c170b4342e488d1a95924db6cb15!} . {!LANG-63b348082d9108d9771a8864d3cdbb5a!} , {!LANG-8a0de6a5c54386d11a6619a2d1f3c69a!} {!LANG-eb7df8f769fb564853c84759469298c6!} {!LANG-d4ff10429e788eb5b054669eca08e761!} або {!LANG-4973feaa3ff24f8decac11ea40ecd280!} {!LANG-7e1cf9844c568f9d34c53ae3acd9da01!} А,{!LANG-23415ce1641b0951f0800cbd5bcfc189!} {!LANG-30cf3d7d133b08543cb6c8933c29dfd7!}{!LANG-bbddabfb91e28e0158dd41380a04afd8!}

{!LANG-2a3e44d591cfa52e0e2f42184ab61c41!}

{!LANG-003e238224aa7cce41e23848b1fa3760!} . {!LANG-cfeb792771c48ccf0a1f43dd39bf2e9e!} А{!LANG-2eaf9ea82c039cde29ecd3c5d964e7ec!} В{!LANG-d492b0f51cdd7962d99542c0c23fd181!} А{!LANG-6225611c6d4425314d1f8f048949491c!} В{!LANG-9bbc4ae20d83df4213c6ebd8a8e863b1!} A).

{!LANG-576b46899bd5d570701b723cf6a0e06b!} А{!LANG-b09528a20c87a42d18d7e0d0f300cd3a!} В{!LANG-677496e588805bc92584d3764e8327f1!} i{!LANG-59b6f72c72330ab8abda0247a76b307c!}

{!LANG-b2cc96157c68d0e15e02c7911d2213e7!}

{!LANG-0b2108f5c01e3574905c5579e982b014!} {!LANG-9c142b5701f7d9bff05961eb3db56958!} або {!LANG-577a23888cec40627f09a51593ebab70!} {!LANG-04a4bcfd99907a8e21733a2f5ccbc50b!} {!LANG-944955e0aa419df7493d951d0747a6ee!}

{!LANG-e5a7ea74fe09b3df1ce989ede40fd2d8!} {!LANG-7ca98f397da02d670bc76b3714c18de1!} . {!LANG-2ff4c03939e98993e6b64d77990e7f12!} В{!LANG-1c6757d24d37626eae86f9e82d54dfb6!} А,{!LANG-bd8361e698a0d911e03e933f527d4420!} {!LANG-379991589a958b5295ff4ccb6fca25c3!}{!LANG-0c842b95cadfd5c9e3ecf756e445cf7c!}

{!LANG-9b4ad9f90ea2dbb3b1997810109e2549!}

{!LANG-1373c67b1c0bfa8a7e320b384a54cc95!} {!LANG-56dfd3935ba608843017021cba1986f6!} {!LANG-57f0880763ef2ee2622dadff9532c0bf!} {!LANG-86e271091424aa3e1c27fe08de0b22d4!}{!LANG-94720e0394e5d71dc3690d63c63f73cd!} {!LANG-a44fe5f1ad9a8ff5a7007320834e8cc5!}. {!LANG-a2b0793b23cbb6b23a03f26ec27333c6!}

{!LANG-3be01e36856256226d50e7c87375e3f6!} {!LANG-5358547e7f8fafe788a0ca0cf8474ae1!}

{!LANG-1edf585f99d6d21138f83f8c4fbdd881!} {!LANG-28c22c1448d8f5ea86bfc3f6a3441182!} . {!LANG-4662244143a9a1bf4f6dec162e983529!}

Теорема. {!LANG-ca80c47c4233ef8452ca562b600b444d!} .

{!LANG-ca529019efb03a0250e1f8953bd903bf!} {!LANG-b59d2324e032ebdffd3a5aebfbeaf4be!} або {!LANG-753e34959354a22ed82a2ff6af6c03b4!} {!LANG-8a3830219ac4f1bb27fe68fe390c3c61!} {!LANG-ba3edcac96561bc885a97da5bd27cb29!} , {!LANG-de95a7a33bfcb08bab378c651335ed70!} {!LANG-fe3575206b875261aa08f9e12928d3bd!} {!LANG-09d4ed4baa25238e520f008614992b57!} {!LANG-8e7406556781a2e29b9f3107e25fcb47!} {!LANG-f0bc409cd4685971abc1d1f4d927854c!} А{!LANG-b786ff4f116bcbe592d5681d3247c14b!} {!LANG-3228bc46dfd93ca53006680b93853221!}{!LANG-6093a62a39e8ce91d2f33d8ea4169e70!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-f53b0a43156f8d237dc974fb893a07cc!} В{!LANG-32f6ddef7b8d39597dbebdcaa050e9ba!} {!LANG-384384012da1cc04e6f022bcf59cc4e8!}{!LANG-078f73d8ae6787e24fc1d0b5e7a71167!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-8143a58a0a543fda668c168828bc1328!} {!LANG-46742255829bcfe5bb28fabfe84c7e65!} , {!LANG-9851f918537aa4e1d1d25b0a23f4d325!}

{!LANG-429b8b1bab0e31910e33b75b052fe244!} {!LANG-384384012da1cc04e6f022bcf59cc4e8!}{!LANG-bb33b294e2a218b7cf9f77239c3c0631!} {!LANG-21f9a4cf41cd20deef018527a520b241!}{!LANG-1952525deca5b927fb96c65f74b4b65e!} {!LANG-1fc15576855668460241dc79d2508cc2!}{!LANG-f54bb635bc934a52884bb4eb6fe7e0d7!} В{!LANG-9754a28f79b3d08819e1a432cb8c81d5!}

{!LANG-061f658c1d40a59a2288376d06e574f1!} В{!LANG-51e6cd122e7a6f2b624f76cda9fb7aa1!} А{!LANG-d9357bb857b7099b4f044f603133fe4b!} {!LANG-379991589a958b5295ff4ccb6fca25c3!}

{!LANG-582d34ab23b47b66419bf3988e7a5622!} {!LANG-a29e93a3f10a70a6f0b212c8d71b94c0!} {!LANG-1c3731c051bcbabf1de65e20c6639ce0!} {!LANG-af26571fa02aae3892f5ce708d0dd6e7!} {!LANG-a68a28d8d4a49fa67490989d2c4dbfaf!} {!LANG-df747e94ae4258a1d826da82a146b07b!}

{!LANG-0da10acd8ef1113ea52e5f60784eaa55!} , {!LANG-c8a8b249ba98e5391bb40a16a56b25af!} {!LANG-e0e054e8be9d9140f2051186ec2df69a!} {!LANG-bfd64420d5ad0c89b1579e6cbce284b7!}

{!LANG-7a88c479dff370aa639cf274bb65c8a8!}

{!LANG-ea3366ce15147813287416ebad1f6cd0!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-b7af88214ee9bb4ff578e21390c239c4!}

{!LANG-8189a10d3b00d9d581281fba798e9a59!}

{!LANG-357f736f9d16cff43aa5c1686c7119e8!}

{!LANG-99ac1dcf83a6c7d40dda2559bcf53dbb!}

{!LANG-cbbb93dc1c8b2935be5d62b099863cb3!} {!LANG-c9aeb3280273cb3b708430f63470fdea!}

{!LANG-d525bca97af821078fa2779f945ce3f9!} {!LANG-53e15c6b34582ac134b29d6a093998bf!} {!LANG-f4a7e2c6a240c5aa3995e5512617872f!}

{!LANG-8dbd15af33ed94436e7ab953559da602!}

{!LANG-531cccac9f728ae9e46c1dbf9947c791!}

{!LANG-c4b1840f006ecbdd7f5024bb9f5707fa!}

{!LANG-2473a6cc88e8bea4d49320f335bb776c!}

{!LANG-2f3168a9095a703693a9f9acd9cc37dc!}

{!LANG-e49392ef6eb13377c4c906f3bc81f48d!} {!LANG-5d451ea03588f0a0d3df8e156e827c0a!} {!LANG-baef36f3460ec46361ec62ce70f51c14!} {!LANG-d119b7a4c64c2f8d877523e9872e347d!}{!LANG-3ea871699d55fc9c404f8e0959ec0b18!} {!LANG-a49d747cba40422b6d950203dd767ab6!} {!LANG-de36e3659f3a7291224e01baf6acf856!} {!LANG-44193f9c2dae099b51219a956714f390!}

{!LANG-0a0395f6c6dd935bdda081549a972afd!}

{!LANG-714daa5b8e61fbe5ce5cfd2ac119abce!} {!LANG-1d9979bf97b8e536c34782f29d0ff5c5!}{!LANG-2d59601de1ec1155ae3d0601113ffe67!}

{!LANG-27aee4dd560da7aa96c5aa350307890c!}

{!LANG-464994647264fcf1c6340397419e8bb4!}

{!LANG-322f881639a39e0a483b3be78d54d8ed!} – {!LANG-423ccf92c3bc1284a3d945a5089189f2!} {!LANG-89d12bf425fe88965da73230ebc0786f!} .

{!LANG-5e9511cce332578f8ffc1c64c3c41165!} {!LANG-153aaee58e254d1af078ed5d42cfe72b!}: {!LANG-9f3998358b73b6702bdb310354241fcd!}

{!LANG-40d60f2533c54a62ab6da69845afc5cd!}

{!LANG-39979f70ffd7689d0fdef10f7527232b!}

{!LANG-6462161dfdee7d66ca05ab6fa3a46797!} {!LANG-451adb87b1b7a437dcbfd79ea284d6af!}{!LANG-39e5b530c131b4acd45cfa8bc2fac140!}

{!LANG-716f9efce6b7a98625da4cb0a74fbe5f!} {!LANG-b5a4628425f36fd738e6c42479a034c2!}{!LANG-50604d64cc34e2d6e4f447f7be2f8689!}

{!LANG-baa6046d53587ab7859e66a445274079!} А{!LANG-8f8bd3396a1fecd20407b02780f1997a!} , {!LANG-4353ef129e9fa0fc2b27b27494844382!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-6ce4bffb6736edcf5f2329236bfbdcb5!} В.{!LANG-9913cca77e6484a1c62198448ad2a373!} А{!LANG-6582a328e10b8f0485079589b782a6e9!} {!LANG-3228bc46dfd93ca53006680b93853221!}{!LANG-f26f708c4a00f8e20d8df235c9b06dc4!} А{!LANG-813e146da3ea7f7ec2cd4d142d5a2bf9!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-5b60c9d69d3a6b5cc387651a3e2345bc!}

{!LANG-d20a3ecac0f431d5debd09db6ab75fcd!}

{!LANG-19e8d54c835ad664d17809ea6773e90d!} А,{!LANG-8a0c89af75a76ba4445a59d058f44096!} {!LANG-04cf86725934e67d1248aeaa6622549b!}{!LANG-ac4beee5f39a75d9df6e55c64ee49f05!} {!LANG-cb7fbad7786c415b829e67f556760195!}{!LANG-7d51c4c53245447f70f3162656aab6d4!} {!LANG-e734a88a1110fa3d657454b2dd348822!}: .

{!LANG-230183382c8aff267918360020df7adf!} А{!LANG-0c353903702f950c1365a910c5a7bc6c!} {!LANG-266e3e5cee070c3ddce4f7836cf87c07!} {!LANG-e734a88a1110fa3d657454b2dd348822!}:

{!LANG-9c011d3246f276c7ec11643ff8bb60e0!}

{!LANG-4beeb69f6c071dbcb330fe226b2f561d!}

{!LANG-0b1604242c91cdf8d79f8763661cf0d3!} – {!LANG-29c66aa5a8bfc1876d8b1d773fb933a5!} В,{!LANG-7f2c0ad37bf3a762040d301c63fe3fe6!} {!LANG-89de23009e91ccad5046ea3efd55c235!}A1 або A2) {!LANG-c6194912a02152b101e66b5ef7f962eb!} В{!LANG-59014b54ddc9a44506d6c4766ea5c8db!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-ce80d38536d72434195df8b1bb4056d0!}

{!LANG-87a1c51b0de607c6652139ffb5f465dd!}

{!LANG-3bcd2ff5daced38ddf5e18e44505710c!} m і n. {!LANG-d159445d808bab40ddee2eccfd3d22af!} {!LANG-d1eb6098055720d8463f9de708d72cd5!} {!LANG-4008e5971cab4ee78ac36b8b4495ca91!} {!LANG-c96cb19efbf29eecc0c5714e722b4c6c!} {!LANG-7d7850064059e6caa51edbf90237f95c!}

{!LANG-5ac4c129c1991f548786e3faa95cf3b9!} {!LANG-16658844242a481d7bb3c5d64ef66487!}

{!LANG-6e9f8a68c3efcdc15d46fc9631fc5d80!} А{!LANG-00060d9819d5ba6767a32050ff76ccd2!}

{!LANG-0f7b38f84befc7abd58160a75a51b0b6!} В{!LANG-a42bc4b9fdd9467cfbd2325f7c6c4136!}

{!LANG-0d8005692f05d5b8bea6932e4f5a5cf0!}

{!LANG-db179669981350807c96a83d240408c4!}

{!LANG-d67c4b49fd2b7168cf1f0ecc59bcf46c!} {!LANG-bfe67e495bb5c3c9016a4f666fdf950a!}{!LANG-36b1fda15201aa16ad8195e5a913b833!}

{!LANG-4a77188a7676d68210f358546ff3fd3e!}

{!LANG-5fa6783847db15c7d6955d5b4c32ed56!} {!LANG-7203735f486538dd70d9745c4934a80b!}{!LANG-87eeb84ef49f5f94c8e40260505a2df9!} х{!LANG-353e5416af8765bbed5c7fac39268d64!} х{!LANG-2ee1312fbaaaf0f7b395dcefbe5f870e!} , {!LANG-809973599f13f8e44fb8090afead6482!} .

{!LANG-29f9510935ce5cea66960f0094338906!}

{!LANG-0d310c81414310f4c514ffdf5efaf05e!}

{!LANG-1c31c4597cf678fafe8ce5d869412b4e!}

{!LANG-5ca1a48317609d1634777ac16ba07df5!} А{!LANG-ae495787893d621fb7d69f60b81719ce!} А{!LANG-49713660b85e30d3d2e6affcb501a837!} {!LANG-ea2d1cbc5a05ee821d8e04109bc1b4c6!}

{!LANG-58dbd88134f61ecbe78635acc3cb3e0a!} {!LANG-c5a6d4c8c56af33433c068ab48b86c4a!}

{!LANG-2d78e0b73c80092c409a4401019727bc!} {!LANG-3228bc46dfd93ca53006680b93853221!}{!LANG-0ba502e5960eb7f1495cd2dc7ed4d7c2!} {!LANG-61b5b0885a189abd071eed6434226892!} {!LANG-05a5ce5ba40e6622fe98d8da82a5d2ac!} , {!LANG-d28135a40c3e820eb5a7ff9a963293ec!} {!LANG-c13e6ee82d9e8e5bd99d6649b0f54f73!} А{!LANG-c88e5762da8e9a96c8516a72e649ad4b!}{!LANG-5e07141d73470853a4d31f05ff2ecf3e!} , {!LANG-4c75472f8bb7855b969bd91436ffccce!} {!LANG-5e07141d73470853a4d31f05ff2ecf3e!}{!LANG-768e099799dcb57d795c2e52c4eac461!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-7971a396bee0bd4de21f872489adad1c!} {!LANG-5e07141d73470853a4d31f05ff2ecf3e!}{!LANG-c41a852bfe365aa865149568b5955aae!}

{!LANG-a71c3403d883fee0fab1914904686ba9!} А,{!LANG-950c5aad01f70fbb8267a4ff778a1f58!} {!LANG-27e8ba1fda70a5137b2ab21fd419ca2e!}{!LANG-f085a8105cd2298db7814fea8f0fd6ef!}

{!LANG-762dff5476778c6a373e241cc747ac05!}

{!LANG-2d97d36f6af97e72e6c762ac09ad4883!}

{!LANG-06ee0c82b8f30e7086d3979a2b20e3e8!} ті n, {!LANG-d0f93e584ea900fddc3ed5d975bf25fa!}

{!LANG-fa34ca5b6ae81c7b32c4d53cd680b616!} . {!LANG-2ff4c03939e98993e6b64d77990e7f12!} А{!LANG-677a9725d8cca68580fb557e731fec28!} , {!LANG-fd3abccdcb4c5e9c977b787f7e0aad8a!} {!LANG-04cf86725934e67d1248aeaa6622549b!}{!LANG-c6ed0545ad550290ef66385f30a762d5!} {!LANG-30cf3d7d133b08543cb6c8933c29dfd7!}1,{!LANG-30cf3d7d133b08543cb6c8933c29dfd7!}2,..{!LANG-30cf3d7d133b08543cb6c8933c29dfd7!}{!LANG-076c0bab4c5ab11dcc0934982cf6bae5!} {!LANG-30cf3d7d133b08543cb6c8933c29dfd7!}{!LANG-47182192508120e5eaed2953a907b171!} {!LANG-f8d74264bb3858fe526524486eb940e1!}

{!LANG-90ef8db6038617e239ae72001a364cec!} А{!LANG-4132e55d59659580eed55ef71354e9d7!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-6e449f3c834085deeac80317a7422311!} В{!LANG-c019f71f1e3fdb3e464d3afe4276495a!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-f1ab98495baa31f2f6dda381aa4b883f!} В.{!LANG-5ae2de5eeab296b5d9f9482d26e4fb98!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-4d94a1881a3e9549928f3548fe7e82ed!} {!LANG-e52c35c70b31f3a1ad75429af2c656eb!} А{!LANG-1b8466faaf25aa9375b7a59ecdea6405!} В,{!LANG-5459966cba9ca47423abac46448476df!} {!LANG-6d35a4150ba6349eaf2d197ec338a83f!} , або {!LANG-b57159b22d30cc7852f3dfa2ed36aa3a!} {!LANG-9ea9eae65f0e5b1b0d91dac97fa7aef8!} j{!LANG-2cdc8263f1117c7a02a5df95365caff3!}{!LANG-e73af36376314c7c0022cb1d204f76b3!}{!LANG-3e6b345315d1efc5351ec5396a50f72a!}

{!LANG-8a118c3e669b3dbd72c9f8853139264b!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-f385c5a00e1555d185f0f46664776f69!}

{!LANG-3903a85d8d298e4823980be80b2e8e55!}

{!LANG-400f668a96355b360b623b4e4ec81871!} {!LANG-d61827930de68418b4fcda2caf394008!}{!LANG-9fddefee8dd00931c2430819ef16a143!} {!LANG-fff1a18a644bea82d501a80374899bcc!}

{!LANG-37a70997e7f6a3f011f11b831b4a9e10!} {!LANG-e734a88a1110fa3d657454b2dd348822!}{!LANG-6b2ad9bf452f7a3c284bcdb53e86291d!} , {!LANG-f8b9076bd63449c280aee29654407d91!} {!LANG-bb3b207e1e7568b85ef1572cc86d4b8d!} , {!LANG-e29bebb50786e8dae153f42e5131bf0e!}{!LANG-7e8871c84637c4e84c86d0550071f39a!}{!LANG-e717fe8462d1b56e75a30162f5e94369!} {!LANG-cd2200d483ce3c875e8be32f91098a50!} (2*) {!LANG-4f5d08fce2ba2470b0eb8765bcd4aa1b!}

{!LANG-c772d4827f1905c621525f622d52c3fd!} {!LANG-af2630fdb7e49456919f05af6b54b998!} .

{!LANG-12922ea2883d6dc67338b5439146ca7d!} В{!LANG-a74924043a9352ba2cf7868d15b34e38!}

{!LANG-3b52090615c5dd3e9e7b436613ec776c!} В{!LANG-a701ff22e01a79a1b1ff134c6d2bd968!} А.

{!LANG-971aee59b664fdbfbf3eed539c1f8b0b!}

{!LANG-c373f704fbfc8822a7240ba9427c9fbb!}

{!LANG-b5a8b3d3af2d8d39d20fa0748fc43f9f!}

{!LANG-22d5945fc01986cc49aef1951584abb2!} {!LANG-f8fd5fbf758f01a8e127eb0e465523fe!} (5*) і {!LANG-8d6d0d1a915b4b949a586444ac802eb1!}

{!LANG-ddecdb7df7c805c9fee66367aa231e01!}

{!LANG-79508847a77a728da848d725c823a8bd!}

{!LANG-7f45670b208a4459d829da1217601ace!}

{!LANG-b206ec35a896a5b3f2e24ccbdf5f9a54!}

{!LANG-f1e36d4d1970f3c6049c254fa45bf13a!} А

{!LANG-c199482c361277fe7273c12f00dd6eb3!}

{!LANG-800047cd63d970694b7b616605aaf457!}

{!LANG-7d2844882099dd53017f83c70b4703b4!}{!LANG-73c04c7ea8525fab6122316e5efb821f!} {!LANG-d18fd28ec8315ad87da82b310d3158f2!}{!LANG-43078d0f45f35685191bae9d08613ea0!} {!LANG-43b6a4373600791e4ef6fe0b6f2d9fac!}.

{!LANG-1aa166cdbf6a22e4c195640eec54def0!} операція{!LANG-aebe1ac6907007bf42da7f53a256fd56!} Рішення{!LANG-7b447724759fb32d852532742a9d4935!} {!LANG-22646f7ce3cc3dbde665573fb84a8100!}{!LANG-3502c5f6487e5fcb6dd1e1e39ec9c38a!} {!LANG-d5a31eb098d533dd0e15ba02d97de4c0!}{!LANG-a174a07e76c8fc9132d2d18c4a0ff3f4!} {!LANG-27153f5f58c1674988a016d2610ef794!}{!LANG-99138645b1e700dadddc50b3430a9f41!} {!LANG-ff3972bf88b0253f4b2af140694b0279!}.

{!LANG-3b7dc5f47ac668ca6a057f6365773b75!}

{!LANG-88b92a5ac5021a276dac5cd25cca546c!}

{!LANG-cdb0a0b869cafd00043447f28c1d5ac9!}

{!LANG-c1043c719edeea462336c2dc9b528147!}

1. {!LANG-417408931b5c9737a99b91b15ac8aca6!}
2. {!LANG-08fcd6196ac2698637003e7d3ef6820c!}
3. {!LANG-21eb95bd9d0a3ad4e5b9f2d8a1341eaa!}
4. {!LANG-a52afc20e36a24a8a23ef20c5e37252e!}
5. {!LANG-19cd37f8424b15ed3706876e133b0019!}
6. {!LANG-49b303779c6ee340a8ad61a3f1bf9d23!}
7. {!LANG-199d84f36296164dcba8513555c12fde!}
8. {!LANG-321be250545e60de0cbbba11c806f0d4!}

{!LANG-23604cc84ee9eb738da76817f49c194f!}

• {!LANG-1b2b6069b07f29be96d083922135c94d!} {!LANG-7eda6f2d29c7be54d3deba34c6a5c3cf!} {!LANG-dc5bc87611cb7c6a0ced294a861f1832!}

{!LANG-64eac4f7e41cc8acf3b2ba573805ef52!}

1. {!LANG-10a72f7b558826192677290d95d569a8!}
2. {!LANG-f2ef07c3e3cb651f75e00d03d1ed9f7f!}

{!LANG-b58cad8b7d2fa431724624d3ee555ff8!}

{!LANG-b8c82bda28a8b34fcc7331b2a67fc4e6!}

{!LANG-32149eb9051332b96496480ba1c93f5b!}

{!LANG-d8f2b0c15a6958455021542720921cb4!}

{!LANG-971c0e30a497db21d900ba581d0e067d!}

{!LANG-06109636de54a1cee8334300c0dad5b5!}

{!LANG-1eee8b75fa895dd016082bfecf63c3b7!}

{!LANG-ed8f0899c5730e2e4b3a168b6c5ccb04!} {!LANG-8cae05b3e7a749e46b200987c7236e47!}{!LANG-d57c891b0e618281ac2712c478fa6ccd!}

{!LANG-29c705624a0cde11cd0a01bc9df14a1f!}

{!LANG-25faa287f09457901bac20b4178bfe56!}

{!LANG-82bf2656991b065b24709c4677dc1809!}

{!LANG-a3af0b282a9f8b78a0b44298c9033fbb!}

{!LANG-98f5d1b30a442eb36d6a95abc2f08fef!}

• {!LANG-c0ee304db900ceac310e96f55f191dd9!}{!LANG-92c605db4bd3feb9b78b6e514086caad!}
• {!LANG-8f1d204cffd328c749962d73658bbcc0!}{!LANG-37ca78378a0bc37447f39720dad729a9!}
• {!LANG-bba132c919c67f37b0510f0722bb0873!}{!LANG-77559b6ee58734911af0aec7b1428101!}

{!LANG-4488457b7de2a4093ddb5676a199b964!}

• {!LANG-7d2844882099dd53017f83c70b4703b4!}{!LANG-e6c367fcc91f4ae09282bbd5cc3e66ad!}

{!LANG-caaa4871a0ab156c09feaf193834a8ae!}

{!LANG-d67c53705de47007c6004d26e4b487e9!}

{!LANG-8620d6cb601654c915e447bba4c4aecb!}{!LANG-d16d8bcaf301cbce263c291cb9658a77!} {!LANG-6ade118c8fdde7ae0766656ca85bd2ec!}

{!LANG-19ad1bd3771713ecdb128213ba0ac08a!} {!LANG-a8447b7a53323cece6e3d1c129cc5807!}

{!LANG-7d2844882099dd53017f83c70b4703b4!}{!LANG-290af357ab0f12beb112bde223627856!} {!LANG-ff92f0456856eaa2e36aa4ca92556944!}

{!LANG-4c4d191bba0e128b13c65181d50c37d6!} {!LANG-5c74e713b5debb60a4c4dd22f3f9ac2e!}

{!LANG-92c1d578c1fc36ff60f5368b102ac5e4!}{!LANG-464967316814f53b545cf3e56a5e9da9!} {!LANG-fa98e954fc9e0e30643c7de556f2bbdc!}

{!LANG-268ed9313da1b35b65cd000dc6838968!} {!LANG-f931d68b7145614e1b1e8b419363a9c8!}

{!LANG-c41a7eed72335e1811c413743431521b!} {!LANG-6e4ff569a6f19dc39c03d951ad2f844b!}

{!LANG-b131420a2da0246d525704e2b1c72f3c!} {!LANG-ba923efc8077145aa5ffeb2dc8a447d7!}

{!LANG-92c1d578c1fc36ff60f5368b102ac5e4!}{!LANG-c0023ac0265d47749ce99e8183079cb1!} {!LANG-da0d49988440fece5686b264f83c7ee3!}

{!LANG-92c1d578c1fc36ff60f5368b102ac5e4!}{!LANG-2c8e2007a8f7abac27f696efa41b7b75!} {!LANG-c58e1938f398b7cfb40c5c18eac54b17!}

{!LANG-0c2c60e8d2d2d620be5bf45b67229ecc!}{!LANG-d06e5924f71a49683cf1809d631ec109!} {!LANG-1f840280fbae774540fbff94e1fa26a5!}{!LANG-b2a777038073878e99cd88cf11c5a0bd!} {!LANG-15ed4615b576c63617e587733a9c8946!}.

{!LANG-fbb1cc42427f34bbaaa34114def62dfc!} {!LANG-cc6269bea8741404a46b2afe3eccffb9!}{!LANG-0d5d1c62f242145740e6fb171c134162!} оптимальними{!LANG-1da4208d563648d5c46aeb744ea93bdf!}

{!LANG-9445051757f4d84c78b156cbf6c16e83!}

{!LANG-bf89cd8abc9ba9f7bfb0f6af88d4f793!}

{!LANG-fdfa9edd506ba15f86c97520cfbf4910!} {!LANG-10f7395d055df40751c01653fa6b42bb!}{!LANG-7a275406f3e6feeb90b29672303788f9!}

{!LANG-8cfd5a33dc07e30dfe23575a9bbf03eb!}

{!LANG-4755fba31905e4b63a222b7197c23051!} А{!LANG-7f2261b4cd5d6be44cf4a1eba48ba125!} {!LANG-9d7bf075372908f55e2d945c39e0a613!}(A{!LANG-81650f98f5145f210757b33e4ae9311c!} {!LANG-9d7bf075372908f55e2d945c39e0a613!}(A{!LANG-763b3e545629c07003fff7667125bac9!}

{!LANG-5510b2ec75ad31fbb8605d1b7f4548ad!}

{!LANG-9d73eb340526c5783d1a885b2f665983!}

{!LANG-08f77fa510f74bb8a90b7af8b49915f7!}

{!LANG-e79c5c1bcd80f2d77353f01ae8f19973!}{!LANG-2667ea47c549b0e16de72ef252319ca5!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-bdc976811acf9cec0445bc167b526304!} {!LANG-009520053b00386d1173f3988c55d192!}  Y{!LANG-d1514de84e953faf2dfdf4ee1341ac73!} x  X. {!LANG-33f434d1659ecf0286d00595685e487c!}

{!LANG-cc92ea81f2041bad8544cde7dbc94562!}
{!LANG-674ad4ee0a786c94169428af8eb15a83!}

{!LANG-35eb85b5086be56517339415e9961ace!}

{!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-d6b8c4b5655b0abf68ffc73a4fba2062!}

F{!LANG-d737a8bc95d0512090bdaac645199e68!}

{!LANG-4c53ffd03eedaf439216ab54a0332762!} і {!LANG-58548f81d836dfec1cebf689fb5185ce!}

{!LANG-16b004cd4c889df393812d733bece1a0!} F{!LANG-7dd1c8ae7ecbff7d936c8c87bb9e011a!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-45d347788ffa963fc3216923e352b97c!} і {!LANG-016873a5eb0d4103b480a79df33de6a6!}

{!LANG-00f71cbe2ba8b84234e6b924eb7ee954!}{!LANG-127953f870ffb5749bdc6a0014feadb4!} {!LANG-fcb24b6a87b6509d40226a59b26a257e!}
{!LANG-f41774a987239db275573ace9f551544!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-981f68c64c4cbcccb11de9c6fbfea228!}

{!LANG-1d8719e56df83a2ff7307f9342323511!} F{!LANG-9d1fd2faf79e66491d795e38c879cf8c!}

{!LANG-51112c47f8cef07c671a77bd1aa7ec2e!}{!LANG-05d63c2f41cc9315eaa9dffe06aac226!}
{!LANG-128873be337165f4da6d3a9287f46330!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!} = {!LANG-bde67c29c12b6c1d756313df607f37a2!}:

{!LANG-cd2c1954f9dcbae14caceb5a5b023184!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-317737e51443021a61e82b400c53e0d3!}
{!LANG-435d888e6c2a566a938086716c75d921!} X.

{!LANG-0b23c835fc667ded9aa61b271e879556!} {!LANG-41ff0912a07fdc52799ff27b38e7f140!}{!LANG-dbb3851bb1652a989947f0ad6decd24e!} {!LANG-e6b0a41ae3f180a66218a1309793adf6!} F{!LANG-00ccfdd18ff8d583c4dcf05eaf99fa78!}