operations research) В. о. - порівняно нова галузь, коротка історія к-рій сягає початку Другої світової війни. Ця точна мат. наука містить чітко визначений набір загальних принципів, к-які забезпечують дослідників планом реалізації операцій наукового дослідні. Він включає наступні стадії. 1. Формулювання проблеми. 2. Побудова мат. моделі, що репрезентує досліджувану систему. 3. Отримання рішення з даної моделі. 4. Перевірка моделі і отриманого з неї рішення. 5. Встановлення контролю за рішенням. 6. Практ. реалізація рішення: впровадження. Формулювання проблеми Необхідно приділяти серйозну увагу визначенню загального характеру проблеми і, що ще важливіше, цілям дослідні. Ці цілі повинні формулюватися в поведінкових термінах, з тим щоб мінімізувати або усунути двозначність і невизначеність. Повинно бути тж відведено час на те, щоб коректно встановити пріоритети щодо реально досяжних цілей. Завеликий перелік цілей може викликати потенційні труднощі з їх реалізацією, особливо якщо ці цілі не чітко ув'язані в логічну послідовність. Побудова математичної моделі Друга фаза проведення досліджень з т. Зр. В. о. передбачає опис моделі. Призначення моделі полягає в репрезентації реального світу. У В. о. такі моделі є символічними, виразимими в мат. термінах. Класичне рівняння Е \u003d тс2 - типовий приклад мат. моделі. Традиційними формами для таких моделей служать рівняння алгебри, к-які не тільки знач. більш економні, ніж вербальні формулювання, але тж тягнуть за собою ретельність і точність визначення, необхідну для чіткого вираження і розуміння окремих елементів і їх взаємозв'язків. Найбільш важливим завданням в побудові такої моделі є чітка і точна розробка і визначення цільової функції. Ця функція виражає взаємозв'язок між незалежними і залежними змінними. Отримання рішення з даної моделі Третя фаза полягає в пошуку рішення. Як правило, бажано знайти оптимальне або краще рішення, проте слід враховувати, що таке рішення буде мати цінністю лише в контексті даної моделі. Оскільки модель є лише репрезентацією проблеми реального світу, існує безліч ситуацій, в яких брало оптимальне рішення може виявитися не зв'язаних з найкращим вибором. Однак, коли оптимальне рішення поєднується з менш оптимальними або більш реалістичними альтернативними рішеннями, з можливістю їх подальшої перевірки стосовно реальної проблеми, використання оптимального рішення тягне за собою певні вигоди. Одна з таких вигод пов'язана з визначенням в кінці дослідні. відносної дистанції між цим ідеальним рішенням і прийнятої альтернативою. Побічним продуктом такої методології використання В. о. є припущення, що менш оптимальні рішення можуть розглядатися в якості сходинок на шляху досягнення мети. Цей метод послідовних наближень може призводити дослідника операцій до більш плідним результатами. Існує безліч мат. процедур для отримання рішень в моделі В. о. Ці процедури ґрунтуються на додатках теорії ймовірностей. Перевірка моделі і отриманого з неї рішення Перевірка моделі і рішення пов'язана з реалізацією двох кроків. Перший полягає в ретельному аналізі всіх елементів моделі, включно. повторну перевірку її алгебраїчних множників на присутність спрощенське косметичних помилок, к-які можуть впливати на валідність. Др. ще більш важливий крок пов'язаний з перевизначенням зв'язків моделі з передумовами, к-які спочатку використовувалися для розробки цієї моделі. Більш систематичний план перевірки включає тж використання іст. даних, к-які можна легко ввести в модель, з тим щоб можна було отримати дослідне (prototype) рішення. Ці дані повинні бути ретельно вивчені, щоб гарантувати фахівця з дослідження операцій валідність перевірки. Слід звернути увагу на те, що як тільки ця модель практично розробляється на основі попередніх іст. даних і потреб, вона може повести себе абсолютно інакше в майбутньому. Др. Найпоширенішою помилкою є введення в модель факторів, к-які не були представлені в іст. базі даних. Встановлення контролю П'ята стадія, встановлення контролю за рішенням, з'являється в ході багаторазового використання моделі. Контроль над моделлю встановлюється в тих випадках, коли фахівець з дослідження операцій допускає розбіжності в значеннях іст. даних і визнає, що ці розбіжності можуть впливати на зв'язку між елементами моделі і одержуваними рішеннями. Др. важливим кроком може стати розробка обмежень за відібраними осн. параметрам моделі для встановлення діапазону прийнятних значень з урахуванням реальних даних. Реалізація моделі Заключним кроком є \u200b\u200bвведення в модель реальних даних. Практ. реалізація моделі пов'язана з очевидним кроком введення реальних даних і отримання рішення реального завдання. Крім того, представляється тж важливим оцінити близькість реального вирішення до іст. рішенням, отриманим раніше, а тж наслідки цього рішення для вдосконалення способів експлуатації моделі. Ці кроки забезпечують важливий зв'язок між мат. природою В. о. і практ. результатами дослідження. В кінцевому рахунку, ці рішення і їх управлінські наслідки використовуються досвідченим фахівцем з В. о. для доведення моделі з метою її можливого використання в майбутньому. Див. Також Методологія (наукових) досліджень Р. С. Ендруліс

І.М. Слинкина

Навчальний посібник для студентів педагогічних вузів

за фахом «Інформатика»

Шадринськ, 2003

Слинкина І.М.

Дослідження операцій. Навчально-методичний посібник. - Шадринськ: вид-во Шадринського державного педагогічного інституту, 2002. - 106 с.

Слинкина І.М. - кандидат педагогічних наук

У навчальному посібнику представлена \u200b\u200bтеоретична частина курсу «Дослідження операцій». Воно призначене для студентів очного і заочного відділень факультетів, що реалізують спеціальність «Інформатика».

© Шадринский державний педагогічний інститут

© Слинкина І.М., 2002

Питання до блокам по курсу «Дослідження операцій» 5

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

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

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

1.4. Поняття лінійного програмування 12

1.5. Приклади економічних задач лінійного програмування. Завдання про найкращому використанні ресурсів 13

1.6. Приклади економічних задач лінійного програмування. Завдання про вибір оптимальних технологій 15

1.7. Приклади економічних задач лінійного програмування. Завдання про сумішах 16

1.8. Приклади економічних задач лінійного програмування. Транспортна задача 17

1.9. Основні види записи завдань лінійного програмування 19

1.10. Способи перетворення 21

1.11. Перехід до канонічної формі 22

1.12. Перехід до симетричній формі запису 25

2.1. Геометрична інтерпретація задачі лінійного програмування 28

2.2. Рішення задач лінійного програмування графічним методом 29

2.3. Властивості рішень задачі лінійного програмування 34

2.4. Загальна ідея симплексного методу 35

2.5. Побудова початкового опорного плану при вирішенні задач лінійного програмування симплексним методом 36

2.6. Ознака оптимальності опорного плану. Сімплексні таблиці 40

2.7. Перехід до нехудшему опорного плану. 44

2.8. Сімплексні перетворення 46

2.9. Альтернативний оптимум (ознака нескінченності безлічі опорних планів) 51

2.10. Ознака необмеженості цільової функції 52

2.11. Поняття про виродження. Монотонність і кінцівку симплексного методу. зациклення 53

2.12. Поняття двоїстості для симетричних задач лінійного програмування 54

3.1. Несиметричні двоїсті задачі 57

3.2. Відкрита і закрита моделі транспортної задачі 61

3.3. Побудова початкового опорного плану. Правило "Північно-західного кута" 63

3.4. Побудова початкового опорного плану. Правило мінімального елемент 64

3.5. Побудова початкового опорного плану. Метод Фогеля 64

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

3.7. Рішення транспортних задач з обмеженнями по пропускній здатності 69

3.8. Приклади задач дискретного програмування. Завдання про контейнерні перевезення. Завдання про призначення 71

3.9. Сутність методів дискретної оптимізації 72

3.10. Завдання опуклого програмування 74

3.11. Метод множників Лагранжа 75

3.12. Градієнтні методи 77

4.1. Методи штрафних та бар'єрних функцій 78

4.2. Динамічне програмування. Основні поняття. Сутність методів вирішення 79

4.3. Стохастичне програмування. Основні поняття 81

4.4. Матричні гри з нульовою сумою 83

4.5. Чисті і змішані стратегії і їх властивості 85

4.6. Властивості чистих і змішаних стратегій 88

4.7. Приведення матричної гри до ЗЛП 92

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

4.9. Потоки подій 96

4.10. Схема загибелі і розмноження 97

4.11. Формула Літтла 99

4.12. Найпростіші системи масового обслуговування 101

Питання до блокам по курсу «Дослідження операцій»

блок 1

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

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

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

4. Поняття лінійного програмування.

5. Приклади економічних задач лінійного програмування. завдання

6. Приклади економічних задач лінійного програмування. Завдання про вибір оптимальних технологій.

7. Приклади економічних задач лінійного програмування. Завдання про сумішах.

8. Приклади економічних задач лінійного програмування. Транспортна задача.

9. Основні види записи завдань лінійного програмування.

10. Способи перетворення.

11. Перехід до канонічної формі.

12. Перехід до симетричній формі запису.

блок 2

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

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

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

4. Загальна ідея симплексного методу.

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

6. Ознака оптимальності опорного плану. Сімплексні таблиці.

7. Перехід до нехудшему опорного плану.

8. Сімплексні перетворення.

9. Альтернативний оптимум (ознака нескінченності безлічі опорних планів).

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

11. Поняття про виродження. Монотонність і кінцівку симплексного методу. Зациклення.

12. Поняття двоїстості для симетричних задач лінійного програмування.

блок 3

1. Несиметричні двоїсті задачі.

2. Відкрита та закрита моделі транспортної задачі.

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

4. Побудова початкового опорного плану. Правило мінімального елемент.

5. Побудова початкового опорного плану. Метод Фогеля.

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

7. Рішення транспортних задач з обмеженнями по пропускній здатності.

8. Приклади задач дискретного програмування. Завдання про контейнерні перевезення. Завдання про призначення.

9. Сутність методів дискретної оптимізації.

10. Завдання опуклого програмування.

11. Метод множників Лагранжа.

12. Градієнтні методи.

блок 4

1. Метод штрафних і бар'єрних функцій.

2. Динамічне програмування. Основні поняття. Сутність методів вирішення.

3. Стохастическое програмування. Основні поняття.

4. Матричні ігри з нульовою сумою.

5. Чисті і змішані стратегії.

6. Властивості чистих і змішаних стратегій.

7. Приведення матричної гри до ЗЛП

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

9. Потоки подій.

10. Схема загибелі і розмноження.

11. Формула Літтла.

12. Найпростіші системи масового обслуговування.

Блок 1.

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

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

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

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

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

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

Завдання 1. Про найкращому використанні ресурсів.

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

Завдання 2. Про сумішах.

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

Завдання 3. Транспортна задача.

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

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

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

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

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

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

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

визначення: Всякий певний вибір залежить від вирішальних параметрів називається рішенням.

визначення: Оптимальними називаються рішення, з тих чи інших причин кращі перед іншими.

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

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

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

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

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

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

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

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

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

Завдання 1. Про найкращому використанні ресурсів.

Завдання операції - зробити максимальну кількість товарів. Показник ефективності Z - прибуток від продажу товарів при мінімальних витратах на ресурси (max Z).

Завдання 2. Про сумішах.

Природний показник ефективності, підказаний формулюванням завдання, - це ціна необхідних для суміші продуктів за умови необхідності збереження заданих властивостей суміші (min Z).

Завдання 3.Транспортна задача.

Завдання операції - забезпечити постачання товарами споживачів при мінімальних витратах на перевезення. Показник ефективності Z - сумарні витрати на перевезення товарів за одиницю часу (min Z).

Дослідження операцій

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

Дослідження операцій - застосування математичних, кількісних методів для обґрунтування рішень у всіх областях цілеспрямованої людської діяльності. Дослідження операцій починається тоді, коли для обгрунтування рішень застосовується той чи інший математичний апарат. операція - будь-яке захід (система дій), об'єднане єдиним задумом і спрямоване до досягнення якоїсь мети (напр., Заходи завдань 1-8, зазначених нижче, будуть операціями). Операція завжди є керованим заходом, тобто залежить від людини, яким способом вибрати параметри, що характеризують її організацію (в широкому сенсі, включаючи набір технічних засобів, що застосовуються в операції). Рішення (Вдале, невдале, розумне, нерозумне) - всякий певний набір залежних від людини параметрів. оптимальне - рішення, яке з тих чи іншими ознаками найкращим за всі інші. Мета дослідження операцій - попереднє кількісне обгрунтування оптимальних рішень з опорою на показник ефективності. Саме прийняття рішення виходить за рамки дослідження операцій і відноситься до компетенції відповідальної особи (осіб). елементи рішення - параметри, сукупність яких утворює рішення: числа, вектори, функції, фізичні ознаки і т. Д. Якщо елементами рішення можна розпоряджатися в певних межах, то задані ( «дисциплінують») умови (обмеження) фіксовані відразу і порушені бути не можуть (вантажопідйомність , розміри, вага). До таких умов відносяться засоби (матеріальні, технічні, людські), якими людина має право розпоряджатися, і інші обмеження, що накладаються на рішення. Їх сукупність формує безліч можливих рішень.

Приклади: Складається план перевезень вантажів з пунктів відправлення А1, А2, ..., А m в пункти призначення В1, В2, ..., В n. Елементи рішення - числа x ij, що показують, яка кількість вантажу буде відправлено з i-го пункту відправлення А i в j-й пункт призначення У j. Рішення - сукупність чисел x 11, x 12, ..., x m1, x m2, ..., x mn

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

типові завдання

Взяті з різних областей практики

1. План постачання підприємств
2. Споруда ділянки магістралі
3. Продаж сезонних товарів
4. снігозахист доріг
5. протичовновий рейд
6. Вибірковий контроль продукції
7. Медичне обстеження
8. бібліотечне обслуговування

Деякі приклади формулювань завдань, що мають відношення до ІВ:

• Завдання складання розкладу, диспетчеризації такі як Open Shop Scheduling Problem, Flow Shop Scheduling Problem, Job Shop Scheduling Problem (англ. en: Job shop scheduling ) і т.д.

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

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

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

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

Історія

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

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

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

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

Найбільший внесок у формування і розвиток нової науки зробили Р. Акоф, Р. Беллмана, Дж. Данциг, Г. Кун, Т. Сааті (Англ.)рос. , Р. Чермен (США), А. Кофман, Р. Форд (Франція) та ін.

Важлива роль у створенні сучасного математичного апарату і розвитку багатьох напрямків дослідження операцій належить Л. В. Канторовичу, Б. В. Гнеденко, М. П. Бусленко, В. С. Михалевич, Н. Н. Мойсеєвим, Ю. М. Єрмолаєва, Н. З. Шору і ін.

За видатний внесок у розробку теорії оптимального використання ресурсів в економіці академіку Л. В. Канторовичу разом з професором Т. Купмансом (США) в 1975 році присвоєно Нобелівська премія в економіці.

Див. також

Примітки

література

• Хемді А. Таха. Введення в дослідження операцій \u003d Operations Research: An Introduction. - М.: Вільямс, 2007. - 912 с. - ISBN 0-13-032374-8
• Дегтярьов Ю. І. Дослідження операцій: підручник для вузів за фахом АСУ. - М.: Вища школа, 1986.
• Грешилов А. А. Математичні методи прийняття рішень. - М.: МГТУ ім. Н.е. Баумана, 2006. - 584 с. - ISBN 5-7038-2893-7

посилання

• Дослідження операцій в каталозі посилань Open Directory Project (dmoz).

Wikimedia Foundation. 2010 року.

Дивитися що таке "Дослідження операцій" в інших словниках:

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

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

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

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

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ - метод вивчення, аналізу та оцінки операцій, їх кількісних і якісних показників. Досліджує хід і результат операцій з урахуванням прийнятих рішень, кількісних і якісних характеристик співвідношення сил і засобів, способів бойового ... ... Війна і мир в термінах і визначеннях

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

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

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

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ - напрямок в економіко-математичних методах, засноване на моделюванні математичних процесів і явищ. В.о. передбачає системний підхід, що складається в пошуку істотних взаємодій при оцінці діяльності або стратегії будь-якої частини ... ... Великий економічний словник

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ - напрямок в дослідженні і проектуванні СЛМ, засноване на математичному моделюванні процесів і явищ. В. о. передбачає системний підхід, що складається в пошуку існуючих взаємодій при оцінці діяльності або стратегії будь-якої частини ... Енциклопедичний словник з психології та педагогіки Детальніше

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

Загальні риси дослідження операцій

У кожному завданні мова йде про якомусь заході, що переслідує певну мету.

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

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

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

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

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

Хоча мета дослідження операцій - знайти оптимальне рішення, але через складність обчислення комбінаторних задач обмежуються пошуком «досить хорошого» рішення.

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

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

ОПЕРАЦІЯ - будь-яке кероване (тобто залежить від вибору параметрів) захід, об'єднане єдиним задумом і спрямоване до досягнення якоїсь мети.

РІШЕННЯ - всякий певний вибір залежних від нас параметрів.

ОПТИМАЛЬНІ РІШЕННЯ - рішення з тих чи іншими ознаками кращі перед іншими.

МЕТА ДОСЛІДЖЕННЯ ОПЕРАЦІЇ - попереднє кількісне обгрунтування оптимальних рішень.

ЕЛЕМЕНТИ РІШЕННЯ - параметри, сукупність яких утворює рішення.

ПОКАЗНИК ЕФЕКТИВНОСТІ (ЦІЛЬОВА ФУНКЦІЯ) -кількісні критерій, що дозволяє порівнювати між собою по ефективності різні рішення і відображає цільову спрямованість операції (W \u003d\u003e maxіліW \u003d\u003e min).

Кращим вважається те рішення, яке в максимальному ступені сприяє досягненню поставленої мети.

Поняття математичної моделі операції

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

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

ПРЯМІ ЗАВДАННЯ відповідають на питання, що буде, якщо в заданих умовах ми приймемо якесь рішення х Х, тобто чому дорівнює показник еффектівностіW (або ряд показників).

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

ЗВОРОТНІ ЗАВДАННЯ відповідають на питання, як вибрати рішення х для того, щоб показник ефективності Wобратілся в максимум (мінімум).

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

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

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 –а, Тому досить розглядати, наприклад а.

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

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

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

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

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

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

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

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

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

21. Платіжна матриця. Нижня і верхня ціна гри

Кінцева гра, в якій гравець А має т стратегій, а гравець В - п стратегій, називається грою m × n.

Розглянемо гру m × n двох гравців А і В ( «Ми» і «противник»).

нехай гравець А має т особистими стратегіями, які позначимо A1, A2, ..., Am. Нехай у гравця В є n особистих стратегій, позначимо їх B1, B2, ..., Bn.

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

Припустимо, що значення aij відомі для будь-якої пари стратегій (Ai, Bj) . Матриця P \u003d aij , елементами якої є виграші, що відповідають стратегіям Ai іBj, називається платіжною матрицею або матрицею гри. Рядки цієї матриці відповідають стратегіям гравця А, а стовпці - стратегіям гравця B. Ці стратегії називаються чистими.

Матриця гри m × n має вигляд:

Розглянемо гру m × n з матрицею і визначимо найкращу серед стратегій A1, A2, ..., Am . Вибираючи стратегію Ai гравець А повинен розраховувати, що гравець Ввідповість на неї тієї зі стратегій Bj для якої виграш для гравця А мінімальний (гравець В прагне "нашкодити" гравцеві A).

Позначимо через найменший виграш гравця А при виборі ним стратегії Ai для всіх можливих стратегій гравця В(Найменше число в i-му рядку платіжної матриці), тобто

Серед усіх чисел () виберемо найбільше:.

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

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

Серед усіх чисел виберемо найменше

і назвемо верхньою ціною гри або мінімаксним виграшем (МІНІМАКСІ). Его гарантований програш гравця В. отже,

Стратегія, відповідна мінімаксу, називається мінімаксної стратегією.

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

Теорема. Нижня ціна гри завжди не перевищує верхньої ціни гри .

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

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

Навпаки, якщо В дотримується своєї оптимальної стратегії, а А{!LANG-d9357bb857b7099b4f044f603133fe4b!} А.

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

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

{!LANG-7a88c479dff370aa639cf274bb65c8a8!}

{!LANG-ea3366ce15147813287416ebad1f6cd0!} v{!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!} v{!LANG-6ce4bffb6736edcf5f2329236bfbdcb5!} В.{!LANG-9913cca77e6484a1c62198448ad2a373!} А{!LANG-6582a328e10b8f0485079589b782a6e9!} В){!LANG-f26f708c4a00f8e20d8df235c9b06dc4!} А{!LANG-813e146da3ea7f7ec2cd4d142d5a2bf9!} v{!LANG-5b60c9d69d3a6b5cc387651a3e2345bc!}

{!LANG-d20a3ecac0f431d5debd09db6ab75fcd!}

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

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

{!LANG-9c011d3246f276c7ec11643ff8bb60e0!}

{!LANG-4beeb69f6c071dbcb330fe226b2f561d!}

{!LANG-0b1604242c91cdf8d79f8763661cf0d3!} – {!LANG-29c66aa5a8bfc1876d8b1d773fb933a5!} В,{!LANG-7f2c0ad37bf3a762040d301c63fe3fe6!} {!LANG-89de23009e91ccad5046ea3efd55c235!}A1 або A2) {!LANG-c6194912a02152b101e66b5ef7f962eb!} В{!LANG-59014b54ddc9a44506d6c4766ea5c8db!} v{!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-0ba502e5960eb7f1495cd2dc7ed4d7c2!} {!LANG-61b5b0885a189abd071eed6434226892!} {!LANG-05a5ce5ba40e6622fe98d8da82a5d2ac!} , {!LANG-d28135a40c3e820eb5a7ff9a963293ec!} {!LANG-c13e6ee82d9e8e5bd99d6649b0f54f73!} А{!LANG-c88e5762da8e9a96c8516a72e649ad4b!}{!LANG-5e07141d73470853a4d31f05ff2ecf3e!} , {!LANG-4c75472f8bb7855b969bd91436ffccce!} {!LANG-5e07141d73470853a4d31f05ff2ecf3e!}{!LANG-768e099799dcb57d795c2e52c4eac461!} v{!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-677a9725d8cca68580fb557e731fec28!} , {!LANG-fd3abccdcb4c5e9c977b787f7e0aad8a!} {!LANG-04cf86725934e67d1248aeaa6622549b!}{!LANG-c6ed0545ad550290ef66385f30a762d5!} B1,B2,..B{!LANG-076c0bab4c5ab11dcc0934982cf6bae5!} B{!LANG-47182192508120e5eaed2953a907b171!} {!LANG-f8d74264bb3858fe526524486eb940e1!}

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

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

{!LANG-3903a85d8d298e4823980be80b2e8e55!}

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

{!LANG-37a70997e7f6a3f011f11b831b4a9e10!} v{!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!} А