Лекція №1

Література:

1. Таха Х.А. Введение в исследование операций. – М.:Мир, 1985. – 496 с.

2. Мину М. Математическое программитование и алгоритмы.– М.:Наука, 1990.– 448 с.

3. Вентцель Е. С. “Исследование операций”, М. 1972 г.

4. Зайченко Ю.П. Дослідження операцій.Підручник. – К. «Слово»,2006. – 816с.

5. Зайченко О.Ю., Зайченко Ю.П. Дослідження операцій. Збірник задач. – К.: «Слово»,2007. – 472 с.

6. Заславский В.С. “Исследование операций. Сборник задач”, М.1980. – 275с.

7. Юдин Д. Б., Гольштейн Е. Г. “Линейное программирование. Задачи и методы линейного программирования ” , М. 1994, 344с.

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

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

Ціль ДСО – кількісне обгрунтування приймаємих рішень стосовно керування організацією.

Основні етапи ДСО:

1. Постановка задачі.

2. Побудова математичної моделі.

3. Знаходження розв”язків.

4. Перевірка і корегування моделі.

5. Реалізація знайденого рішення на практиці.

(1). Задача ставиться замовником, а операційна група конкретизує її.

(2). Формалізація задачі.

Цільова функція задачі (показник якості, чи ефективності системи):

max E = f (x , y) (1.1)

при обмеженнях g_i (x, y)  b_i , i = 1, m (1.2), де

х- вектор керованих змінних;

у – вектор некерованих змінних;

g_i – функція споживання і-го ресурсу;

b_i – величина і-го ресурсу.

(3). Для знаходження оптимального рішення задачі (1.1 , 1.2 ) в залежності від виду і структури цільової функції та обмежень використовують відповідні методи теорії оптимальних рішень:

• лінійне програмування ( якщо f (x , y), g_i (x, y) – лінійні функції відносно змінної х);

• нелінійне програмування ( якщо f (x , y), g_i (x, y) – не лінійні функції відносно змінної х);

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

• стахостичне програмування ( якщо вектор у – випадковий);

• дискретне програмування ( якщо на змінну х накладена умова дискретності);

• евристичне програмування ( якщо точний оптимум знайти алгоритмічним шляхом неможливо через велику кількість варіантів).

Класи задач ДСО ( за своєю постановкою):

1. Задача керування запасами.

2. Задача розподілення ресурсів.

3. Задача ремонту і заміни обладнання.

4. Задача масового обслуговування.

5. Задача теорії розкладів.

6. Задача вибору маршруту.

7. Задача планування і розміщення.

Приклади задач.

1. Транспортна задача.

Маємо m пунктів виробництва. Нехай виробництво однієї продукції з обсягами виробництва за даний період часу а₁, а₂, …, а_m . Маємо n споживачів з потребами в₁, в₂, …, в_n . Сумарний обсяг виробництва співпадає з потребами. Вартість перевезень одиниці продукції з і-го пункту виробництва в j–й пункт споживання с_{і j}.

Завдання: скласти такий план перевезень від постачальників до споживачів, щоб всі потреби були задоволені, а сумарні витрати на перевезення – мінімальними.

Розв”язок:

Вводимо невідомі х _іj ( обсяг перевезень з і-го пункту виробництва в j–й пункт споживання.

Визначаємо цільову функцію:

Визначаємо умови обмеження:

Тоді повинні виконуватись такі умови:

(3.1)

(j = 1, 2, …, n) (3.2)

(i = 1, 2, …, m) (3.3)

X_ij ≥ 0; (3.4)

Умова (3.3) гарантує повне вивезення продукту з усіх пунктів виробництва, а умова (3.2) – повне задоволення попиту в усіх пунктах споживання.

Матрицю

Х =	║xij║mn =	x11 x12 ... x1n x21 x22 ... x2n .............. xm1 xm2 ... xmn

називають планом перевезень Т-задачі, а змінні x_ij – перевезеннями.

2. Задача про дієту.

Для людини необхідно скласти харчовий раціон, який повинен включати :

• білків не менше а1 гр.,

• вуглеводів не менше а2 гр.,

• мінеральних солей не менше а3 гр.,

• вітамінів не менше а4 гр. за добу.

Нехай:

• добова потреба в цих елементах – m;

• маємо n видів харчових продуктів;

• а _іj – кількість елемента і в одиниці продукту j;

• с_j – ціна одиниці продукту j.

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

Розв”язок:

Вводимо невідомі х _j (кількість j–го продукту).

Визначаємо цільову функцію:

Визначаємо умови обмеження:

а _іj х _j  а ₁

3. Задача про рюкзак.

Маємо рюкзак визначеного розміру. Нехай місткість рюкзака дорівнює d. Маємо n предметів з обсягами а₁, а₂, …, а_n. Ступінь важливості кожного продукту – с _j. Виконуються умови .

Завдання: вирішити які предмети покласти в рюкзак, щоб сумарна цінність була максимальна.

.

Висновки:

• функція, яка максимізується (мінімізується) називається цільовою;

• умови, яким підпорядковуються змінні, називаються обмеженнями задачі;

• любий набір значень невідомих х₁, х₂ , …, х_n , х_і 0 , задовольняє всім обмеженням над допустимим розвязком задачі (сукупність всіх допустимих розвязків складає допустиму множину);

• допустиме рішення , яке дає цільовій функції максимум (мінімум), називають оптимальним рішенням задачі, а саме значення цільової функції при цьому розвязкі – оптимумом.