Підсумкове завдання 4

Задача про призначення (вибір).

Дана матриця продуктивності

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

Розв’язання.

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

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

Далі діємо за алгоритмом, блок-схема якого має вигляд:

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

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

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

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

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

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

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

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

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

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

Кількість неза­леж­них нулів менше 5	Є не вилучений нуль	Є 0* в рядку з 0, здійснюємо етап ІV, а після цього повер­таємось до етапу ІІ
	У рядку 0’ немає 0*, тобто переходимо до етапу V, і будуємо ланцюжок

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

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

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

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

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

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

.

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

VІ Завдання для самостійної роботи (самопідготовки)

Для засвоєння матеріалу курсу “Дослідження операцій” пропонується розглянути і розв’язати наступні задачі, які не увійшли до підсумкових завдань.

1 Маємо два верстати і п’ять деталей. Кожна з деталей повинна пройти обробку на обох верстатах. Задано час обробки (в хв.) кожної деталі на кожному верстаті.

№ верстата № деталі
І
ІІ

Скласти такий порядок обробки, щоб сумарний час обробки був мінімальним.

2 Розв’язати задачу про розклад у випадку, коли час обробки (в сек.) задано таблицею.

№ верстата № деталі
І
ІІ

3 Розв’язати задачу про розклад, коли час обробки (в хв.) задано таблицею.

№ верстата № деталі
І
ІІ
ІІІ

4 Скласти матрицю суміжності вершин графа і матрицю суміжності дуг графа.

5 Скласти матрицю суміжності вершин і ребер графа.

6 Скласти матрицю інцидентності неорієнтованого графа.

7 Скласти матрицю інцидентності орієнтованого графа.

8 Скласти граф за його матрицею інцидентності.

9 Підрахувати число остовних дерев графа.

10. Побудувати остовне дерево графа.

11 Побудувати мінімальне і максимальне остовне дерево графа.

12 Знайти максимальну течію у орграфі.

13 Знайти максимальну течію в неорграфі.

14 Маємо 5 предметів. Відомі їх вартість і їх вага . Потрібно покласти в рюкзак сукупність предметів з мінімальною сумарною вагою за умови, що вартість вантажу не менша ніж С=30грн.

Вага і вартість кожного предмета задані в таблиці.

i
(грн)
(кг)

С=30 грн.

15 Розв’язати матричну гру.

16 Розв’язати матричну гру.

17 Скласти математичну модель для розв’язання матричної гри методом лінійного програмування.

18. Заявки на телефонні перемовини в телеательє надходять з інтенсивністю заявок за годину, а середня тривалість розмови хв. Визначити показники ефективності роботи СМО (телефонного зв’язку) за умови наявності одного телефонного номера.

19. В умовах задачі 18 визначити оптимальне число телефонних номерів в телеательє, якщо умовою оптимальності вважати задоволення в середньому з кожних 100 заявок не менже ніж 90.

20. В порту є один причал для розвантаження суден. Інтенсивність течії суден дорівнює 0, 4 суден за добу. Середній час розвантаження одного судна дорівнює 2 доби. Припускаємо, що черга може бути необмеженої довжини. Знайти показники ефективності роботи причала, а також ймовірність того, що чекають розвантаження не більше ніж 2 судна.

21. В універсамі до вузла розрахунку поступає течія покупців з інтенсивністю 81 людина за годину ( люд/год.) Середня тривалість обслуговування контролером-касиром одного покупця дорівнює 2 хвилини. ( хв.). Визначити:

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

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

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

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

СПИСОК ЛІТЕРАТУРИ

1 Хемди А.Таха. Введение в исследование операций. – М.: «Вильямс», 2007. 912 с.

2 Исследование операций в экономике / Под редакцией Н.Ш.Кремера. – М.: «Банки и биржи», 2003. 395 с.

3 Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. – Новосибирск.: НГУ, 2000. 105 с.

ЗМІСТ

Вступ.............................................................................................................3

І Програма курсу........................................................................................3

ІІ Структура модуля та його елементи.....................................................4

ІІІ Питання для перевірки теоретичних знань..........................................5

ІV Індивідуальні завдання...........................................................................7

V Зразки виконання індивідуальних завдань..........................................18

VІ Завдання для самостійної роботи (самопідготовки)...........................31

Список літератури.......................................................................................36