ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Глава 4 ЗАДАЧА ПРО ПРИЗНАЧЕННЯ (ВИБІР)

Загрузка...

Постановка задачі. Є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 і переходимо до етапу ІХ. В результаті одержуємо матрицю:

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

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

.

Таким чином, у первісній матриці треба вибрати елементи с12. с25, с31, с43, с54: 4+3+4+2+2=15.


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

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

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

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

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

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

1

 

 
 



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти