ЗМІСТ

Вступ	4
Тема 1. Постановка задач лінійного програмування	5
Тема 2. Основні методи розв’язування задач лінійного програмування	16
2.1 Графічний метод розв’язування задач лінійного програмування	16
2.2. Симплекс-метод	22
Тема 3. Транспортна задача	32
Тема 4. Марковські процеси з дискретними станами та неперервним часом	45
Тема 5. Системи масового обслуговування з відмовами	53
Тема 6. Системи масового обслуговування з очікуванням	60
Тема 7. Сітьове планування	65
Тема 8. Елементи теорії стратегічних ігор	82
Тема 9. Методи прийняття рішень в умовах невизначеності	95
Тема 10. Задача про впорядкування обслуговування	103
Питання для підготовки до захисту розрахункової роботи	110
Література	111

ВСТУП

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

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

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

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

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

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

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

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

Сформулюємо наступну задачу.

Знайти такі при яких функція

досягає мінімуму або максимуму при додаткових обмеженнях

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

Зауваження1.1. Якщо серед знаків нерівностей є « ≥ », то помноживши дані нерівності на -1 змінимо їх на « ≤ ».

Задача про оптимальне виробництво

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

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

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

.

Розмірковуючи аналогічно відносно інших видів сировини, отримаємо наступну систему обмежень:

, (1.1)

які називають виробничими обмеженнями

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

, . (1.2) Критерій оптимальності (максимальний сукупний прибуток):

(1.3)

Функцію називають цільовою функцією.

Сукупність (1.1), (1.2) і (1.3) буде математичною моделлю задачі про оптимальне виробництво.

Зауваження 1.2. Якщо - це витрати на виробництво одиниці продукції, то цільова функція буде прямувати до мінімуму

.

Max і min об’єднуються одним словом – оптимум (opt).

Зауваження 1.3. Відносно використання деяких ресурсів може бути накладене обмеження їх повного використання:

.

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

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 8	4 2 0	1 1 2	0 3 1	1200 800 2000
Прибуток	2	3	1	4

Розв’язання. Позначимо кількість вироблених видів продукції через Тоді для виробництва продукції першого виду необхідноодиниць сировини А, для виробництва другого та третього видів відповіднота. У виробництві четвертого виду продукції сировина А не використовується. Отже для випуску всієї продукції необхідноодиниць сировини А. Оскільки її запаси складають 1200 одиниць, то маємо обмеження

Аналогічно сировини В необхідно Але враховуючи умову повного її використання отримуємо обмеження – рівність

Обмеження по сировині С:

Оскільки продукції першого виду необхідно виробити не менше 100 одиниць, а продукції четвертого виду – не більше 200 одиниць, то отримаємо додаткові обмеження:

Крім того, ми не можемо виробити від’ємну кількість продукції. Тому

.

Прибуток від реалізації виробленої продукції

Відповідь.