Постановка задачі. Єnрізноманітних робіт A , A , ... , A i n механізмів B , В , ... , В , кожний з яких може виконувати будь-яку роботу. Продуктивність механізму B_і при виконанні роботи Aj позначимо с (i,j=l,2„..,n).

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

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

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

Опис алгоритму угорського методу.

На підготовчому етапі знаходимо найбільший елемент j-гo стовпчика (β_j), i всі елементи цього стовпця послідовно віднімаємо від максимального. Цю операцію проводять над усіма стовпцями матриці С (l≤j≤n).

У новій матриці знаходимо найменший елемент α_i вкожному і-му рядку i віднімаємо його віделементів i-ого рядка, (1≤i≤n). У результаті одержуємо матрицю з невід’ємними елементами, в кожному стовпцю i рядку якої є принаймні один нуль.

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

Вирішальну роль в подальшому відіграє поняття незалежних нулів. Це нульові елементи матриці ,. будь-які два з яких належать до різних рядківi різних стовпців. Незалежні нулі позначимо 0*.

Спочатку в матриці знаходимо всілякінезалежні нулі і вилучаємо знаком "+" стовпці, що містять 0*.

При цьому, якщотаких незалежних нулів виявилося рівноn, тоді задача вирішена і елементи, що стояли в матриці С на місцях 0*, є шуканими.

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

І Вилучаємо знаком "+" стовпці, щомістять незалежні нулі 0*.

ІІ Пошук невилученого нуля (тобто нуля, що стоїть в непозначеному знаком "+" рядку або стовпцю); невилучений нуль позначимо 0^’.

ІІІ Пошук 0* в рядку з 0^’.

ІV Вилучаємо знаком "+" рядок з 0^’ i знищуємо "+" над стовпцем з 0*.

V Будуємо ланцюжок від знайденого 0^’ по стовпцю. до 0*, від цього 0* по рядку до 0^’ i т.д. Якщо в одному стовпцю. з 0^’ немає 0*, тоді ланцюжок складається з одного 0’. Ланцюжок завжди починається з 0’ і закінчується 0’.

VI Знищуємо в ланцюжку всі "*" і ставимо "*" замість"‘".

VII Знищуємо в матриці всі "‘" і всі знаки вилучення (стовпців і рядків).

VIII Знаходимо найменший елемент серед невилучених елементів (що потрапили в невилучені рядки i стовпці). Позначимо його h>0.

ІХ Віднімаємо h з елементів невилучених рядків і додаємо h до елементів вилучених стовпців.

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

Приклад. Дана матриця продуктивностей

Розв’язати задачу про вибір (призначення).

Розв’язання. На підготовчому етапі знаходимо найбільший елемент j-гo стовпчика (β_j), i всі елементи цього стовпця послідовно віднімаємо від максимального. Цю операцію проводять над усіма стовпцями матриці С (l≤j≤n).

У новій матриці знаходимо найменший елемент α_i вкожному і-му рядку i віднімаємо його віделементів i-го рядка, (l≤j≤n). У даному випадку всі мінімальні елементи рядків дорівнюють нулю, тому отримана матриця є матрицею . Далі діємо за алгоритмом.

Число незалежних нулів менш 5

Є невилучений

нуль

У рядку 0^’ немає 0^*, тобто переходимо до етапу V, і будуємо ланцюжок.

Є 0^*в рядку з 0’, здійснюємо етап ІV, а після цього повертаємось до етапу ІІ

Переходимо до етапів VІ і VІІ:

Знову переходимо до етапу І, помітивши, що число незалежних нулів збільшилось на одиницю:

− тут пройдені етапи ІІ, ІІІ, ІV. Переходимо до етапу ІІ.

Тепер уже невилученихнулів немає. . Переходимо до етапу VІІІ. Тут h=1 і переходимо до етапу ІХ. В результаті одержуємо матрицю:

Переходимо до етапу ІІ. Далі діємо за алгоритмом.

Отже, одержуємо матрицю:

Таким чином, у первісній матриці треба вибрати елементи с₁₂. с₂₅, с₃₁, с₄₃, с₅₄: 4+3+4+2+2=15.

Питання для самоперевірки

1 Сформулюйте постановку задачі про призначення (вибір).

2 Що треба зробити на підготовчому етапі до розв’язання задачі про вибір?

3 Що таке незалежний нуль(0*)?

Задачі для самостійної роботи

Розв’язати задачу про призначення, якщо задана матриця продуктивностей.

Глава 5 ТЕОРІЯ ІГОР

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

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

- варіанти дій гравців;

- об’єм інформації кожного гравця про поведінку партнерів;

- виграш, до якого приводить кожна сукупність дій.

Як правило, виграш (програш) може бути заданий кількісно. Наприклад, можна оцінити програш нулем, виграш – одиницею, а нічию − .

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

Гра називається грою з нульовою сумою, якщо виграш одного з гравців дорівнює програшу другого, тобто для повного задання результату гри достатньо вказати величину виграшу одного з них. Якщо позначити a – виграш одного з гравців, b – виграш другого, то для гри з нульовою сумою b = - a, тобто достатньо розглядати, наприклад, a.

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

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

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

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

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

не обов’язково антагоністичні.

Предыдущая 1 2 3 4 567 8 9 10 Следующая