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

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

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

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

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

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

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

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

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

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

Видатний фахівець з ДО Т. Л. Сааті в книзі [6] дав таке іронічне визначення: „дослідження операцій - мистецтво давати погані відповіді на ті практичні питання, на які даються ще гірші відповіді іншими методами”.

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

Перейдемо до аналізу найпростіших аналітичних моделей економіки.

3. Модель «затрати-випуск» В. В. Леонтьєва

Розглянемо найпростішу модель «затрати-випуск» - замкнену і статичну [3]. Будемо вважати, що об'єкт економічної діяльності випускає найменувань продукції , де значок «*» при векторі означає операцію транспонування. Крім того,

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

Y - вектор кінцевої продукції (продукції, яка йде на продаж, у запаси, тощо).

Будемо вважати, що

де - невід'ємна матриця своїх елементів, які є коефіцієнтами прямих затрат при виробництві продукції. Або

(3.1)

У деталізованому вигляді матричне рівняння (3.1) має вигляд:

(3.2)

де - кількість продукції і-го виду, потрібної для виробництва одиниці продукції j-го виду. - компоненти вектора кінцевого випуску. Зміст компонентів вектора - кількість валового продукту відповідної номенклатури.

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

Матриця А називається продуктивною (інколи вживають термін цілком продуктивна), якщо матриця не має від'ємних елементів. Матриця Е - одинична матриця розмірності (nЧn).

Приклад. Нехай матриця А має вигляд

вектор .

Знайти:

а) матрицю повних затрат ;

б) вектор валового випуску ;

в) виробничу собівартість S₁, S₂, S₃, S₄ кожного виду продукції.

Розв'язування. Шукаємо матрицю

де - детермінант (визначник) матриці

(det B = ):

Шукаємо вектор валового випуску :

Шукаємо виробничу собівартість S₁, S₂, S₃, S₄ :

Часто виникає необхідність встановлення факту продуктивності матриці без знаходження елементів матриці . Справедливі наступні твердження:

Твердження 1. Для продуктивності матриці достатнє виконання умов:

або

Твердження 2. Згідно з [5] для продуктивності матриці необхідне і достатнє виконання таких умов:

існує рядок і₀ у матриці для якого виконується умова:

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

Припустімо, що , тоді

.

,

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

Завдання для самостійних і контрольних робіт

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

4. Модель розподілу ресурсів

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

Будемо вважати, що, крім балансових рівнянь В.В. Леонтьєва (3.1), (3.2) у нашій моделі є критерій оптимальності:

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

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

або

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

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

при

(4.1)

Якщо матриця продуктивна, то з (3.1) можна знайти , а підставивши х⁰ у (4.1) одержимо задачу: знайти такі, щоб

, (4.2)

(4.3)

,

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

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

Потрібно знайти вектор , який забезпечує найбільше (max) або найменше (min) значення функції:

(5.1)

за виконання умов:

(5.2)

Числа - довільні дійсні числа.

Будемо вважати, що завжди в (5.1) стоїть знак «mах». Це припущення не зменшує загальності міркувань, адже заміною змінних будь-яку ЗЛП можна завжди звести до процедури максимізації L, якщо для L у (5.1) стояла вимога її мінімізації. Так само в (5.2) множенням на «-» правої та лівої частини нерівності, у якій стоїть знак «?», можна досягнути стандарту (5.2). Якщо в нерівностях (5.2) є знак «=», наприклад, при і₀-ій нерівності, тоді замість однієї рівності можна записати дві еквівалентні нерівності:

Задачу (5.2),(5.3) можна розв'язати за допомогою симплекс-методу [1], а задачі малої розмірності (n=2,3) - графічно.

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

Приклад. Знайти найбільше та найменше значення функції

якщо х₁ та х₂ задовольняють нерівностям (лежать в області D₁):

(6.1)

Розв'язування: - нормалі до прямих, які утворені заміною знаків «?» та «?» на знак «=». - нормаль до прямої

Будуємо область D₁ (рис. 1).

1

92

Рис. 1

Алгоритм побудови області D₁, може бути таким:

Будуємо прямокутник Р: ().

У побудованому прямокутнику шукаємо точки, які задовольняють першу нерівність Для цього будуємо пряму за двома точками перетину з осями координат (0, 6) та (6, 0). Пряма ділить прямокутник Р на дві частини. Та частина прямокутника, яка лежить у напрямку від прямої, має значення лівої частини рівності більші за 6 (у напрямку нормалі лінійна функція зростає), але щоб задовольнити першу нерівність треба розглядати всі значення х₁ та х₂ для яких ліва частина нерівності менша за 6. Цю умову буде виконано якщо в прямокутнику Р узяти частину, яка лежить на самій прямій та в напрямку антинормалі . Тобто, щоб задовольнити першу нерівність, треба брати точки прямокутника Р, які лежать на прямій і нижче від неї.

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

В одержаному трикутнику слід вилучити точки, які не задовольняють умову (третій нерівності в (6.1)). Будуємо пряму і вибираємо точки на прямій та поза прямою в бік антинормалі . Одержимо знову чотирикутник (див. рис. 1).

Завершуємо побудову області D₁, вилученням з одержаного чотирикутника точок, що не задовольняють нерівності . Це точки, які лежать поза прямою в напрямку антинормалі . Одержуємо п'ятикутник АВСDE. Переходимо до виконання пункту 2.

Шукаємо оптимальні розв'язки.

знаходиться в крайній точці області D₁, в напрямку нормалі до L, .

знаходиться в крайній точці області D₁ в напрямку антинормалі . Крайньою точкою області D₁ будемо називати точку у якій перетинаються пряма з областю так, що будь-яке зміщення цієї прямої в окіл точки ( в напрямку ) спричиняє відсутність на прямій точок області D₁; d - величина (відстань) на яку зміщується пряма в напрямку нормалі або антинормалі.

знаходиться шляхом обчислення функції L у точці перетину прямих l₂ та l₃ (напрям ). Точку перетину знаходять як результат розв'язку системи рівнянь - значення функції L у точці перетину осі х₂ з прямою l₁ (напрям ). Точку перетину знаходять через розв'язання системи рівнянь

Відповідь: .

Завдання для самостійних і контрольних робіт

Розв'язати графічно ЗЛП.

7. Алгоритм розв'язання задачі лінійного програмування за допомогою симплекс-методу

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

І. Згідно [1], записуємо ЗЛП (5.1), (5.2) в нормальному стандартному вигляді.

(7.1)

ІІ. Будуємо симплекс-таблицю.

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

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

ІІІ. Шукаємо допустимий розв'язок. Для цього побудуємо нову симплекс-таблицю (7.3), згідно наступних правил:

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

Нехай таким елементом є b_m < 0.

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

У базовому стовпчику перебираємо всі елементи (крім першого), які мають однакові знаки з відповідними елементами першого стовпчика. Для них обчислюємо відношення , j₀ - номер базового стовпчика. Нехай j₀ =2 , тоді m рядок призначаємо базовим, а елемент a_m2, який стоїть у клітинці, де перетинаються базовий рядок і базовий стовпчик, - базовим елементом. Проводимо взаємозаміну вільної та базової змінних, які відповідають базовому стовпчику та базовому рядку.

У базовій клітинці таблиці (7.3) записуємо елемент обернений до відповідного елемента табл. (7.2).

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

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

Усі інші елементи табл. (7.3) утворюються як результат додавання відповідного елемента табл. (7.2) та добутку відповідного елемента базового стовпчика табл. (7.3) на чисельник відповідного елемента базового рядка тієї самої таблиці.

Після заповнення табл. (7.3), повторюємо процедуру починаючи з п. 1, використовуючи як вихідну табл. (7.3).

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

ІV. Будуємо оптимальний розв'язок ЗЛП

Знаходимо серед елементів першого рядка (крім першого елемента) додатні числа. Якщо таких елементів немає, переходимо до виконання п. V.

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

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

Зауваження 1. Якщо в задачі (5.1), (5.2) тоді в (7.1) перша нерівність виглядатиме так:

,

а в першій симплекс-таблиці перший рядок матиме такий вигляд:

Кінцева таблиця симплекс-процедури І-V у першій клітинці міститиме число, яке дорівнює

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

Приклад. Розв'язати ЗЛП

за умов

Розв'язування: Запишемо задачу в нормальному вигляді (виконаємо п.І).

Складаємо симплекс-таблицю:

Визначаємо базовий стовпчик і базовий рядок, перетин яких дає базовий елемент. Базовий елемент «-1». Будуємо нову таблицю.

Повторюємо симплекс-процедуру.

Записуємо фінальну симплекс-таблицю:

Відповідь:

Завдання для самостійних і контрольних робіт

Розв'язати за допомогою симплекс-методу:

8. Спряжені (двоїсті) задачі лінійного програмування. Основні властивості

Розглянемо основну ЗЛП, записану (без зменшення загальності міркувань) у вигляді:

(8.1)

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

(8.2)

Розглянемо, також, задачу:

(8.3)

(8.4)

Задачу (8.3), (8.4) одержана із задачі (8.1), (8.2) згідно з такими правилами:

вільні члени обмежень (8.2) є коефіцієнтами нового критерію , а коефіцієнти в критерії - вільними членами в обмеженнях (8.4);

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

у нових обмеженнях (8.4) знаки нерівностей протилежні знакам нерівностей (8.2);

максимізація критерію змінюється на мінімізацію критерія

Задача (8.3), (8.4) називається спряженою (двоїстою) до задачі (8.1), (8.2).

Не важко помітити, що задачу (8.1), (8.2) можна розглядати як спряжену відносно своєї спряженої задачі (8.3), (8.4) або

Властивість 1. Якщо одна зі спряжених задач (8.1), (8.2) чи (8.3), (8.4) має розв'язок, то й інша має розв'язок, причому виконується рівність:

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

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

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

Інакше кажучи, оптимальні розв'язки пари спряжених задач задовольняють умови:

1)

2)

Приклад. Сформулювати ЗЛП, спряжену до заданої:

Розв'язування Запишемо нерівності у формі (8.2):

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

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

Завдання для самостійних і контрольних робіт

Розв'язати ЗЛП, спряжену до заданої.

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

10. Задачі транспортного типу

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

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

(10.1)

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

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

(10.2)

де - кількість товару, що перевозиться з пункту в пункт .

Побудуємо математичну модель цієї задачі.

Невід'ємні змінні (кількість яких ) повинні задовольняти такі умови:

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

(10.3)

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

(10.4)

Має виконуватись умова (10.2):

(10.5)

Функція - лінійна, обмеження рівності (10.3), (10.4) також лінійні. Перед нами типова ЗЛП з обмеженнями-рівностями.

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

Неважко переконатися, що не всі n+m рівнянь (10.3), (10.4) незалежні. Дійсно, підсумовуючи всі рівняння (10.3) та (10.4) одержимо одне й теж саме число згідно з умовою (10.1). Отже, умови (10.3), (10.4) зв'язані однією лінійною залежністю, і фактично з цих рівнянь лише n+m-1, не n+m, лінійно незалежні. Це означає, що ранг системи рівнянь (10.3), (10.4) однаковий:

r = n+m-1,

а отже, можна розв'язати ці рівняння відносно n+m-1 базових змінних, виразивши їх через інші, вільні.

Підрахуємо кількість вільних змінних:

k = mn-(m+n-1) = mn - m - (n-1) = (m-1)(n-1).

Із розгляду ЗЛП відомо, що оптимальний розв'язок досягається в одній з вершин області допустимих розв'язків (ОДР), де хоча б k змінних перетворюється на нуль. У нашому випадку для оптимального плану перевезень хоча б (m-1)(n-1) значень повинні бути рівні нулю. Значення кількості одиниць ватажу, який направляється з пункту в пункт будемо називати перевезеннями.

Будь-яку сукупність будемо називати планом перевезень, або просто планом.

План будемо називати допустимим, якщо він задовольняє умови (10.3), (10.4) («балансові умови» - всі замовлення виконані, всі запаси вичерпані).

Допустимий план будемо називати опорним, якщо в ньому відмінні від нуля не більше r = n+m-1 базових перевезень , а всі інші дорівнюють нулю.

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

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

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

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

сума перевезень у кожному рядку таблиці має дорівнювати запасу даного ПВ;

сума перевезень у кожному стовпчику таблиці має дорівнювати розміру замовлення певного ПП;

сумарна вартість перевезень - мінімальна.

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