Методы операционного исследования

Завдання про найкоротший шлях.

 Завдання про найкоротший шлях полягає в знаходженні зв'язаних між собою доріг на транспортній сітці, які мають мінімальну довжину від вихідного пункту до пункту призначення. Для вирішення цього завдання можна застосувати наступний алгоритм. Кожному вузлу сітки приписуватимемо тимчасові позначки рівні відстані від початкового вузла до даного вузла. Якщо виявляється, що вузол належить найкоротшому маршруту, то тимчасову позначку оголошуємо постійною. На першій ітерації початковому вузлу приписується постійна позначка рівна нулю, а останнім вузлам – тимчасові позначки, рівні довжині дуги з початкового вузла в даний вузол, якщо така дуга існує і «¥», якщо немає такої дуги. Потім, до тих пір, поки кінцевий вузол не отримає постійну позначку виконуються наступні дві процедури:

1) серед тимчасових позначок  вибирається мінімальна і оголошується  постійною;

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

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

Завдання про максимальний потік.

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

Пропускні спроможності Сij сітки можна представити в матричній формі. Для визначення максимального потоку з джерела s в стік t використовується наступний алгоритм.

Крок 1. Знайти ланцюг, що сполучає s з t, по якому потік приймає позитивне значення у напрямі sRt. Якщо такого ланцюга не існує, перейти до кроку 3. Інакше перейти до кроку 2.

Крок 2. Нехай Сij- (Сij+) – пропускні спроможності дуг ланцюга (s, t) у напрямі sRt (tRs) і q = min{cij-}>0. Матрицю пропускних спроможностей (cij) змінити таким чином:

(а) відняти q з усіх cij- ;

(б) додати q до всіх cij+ .

Замінити поточну cij-матріцю на знов отриману і перейти до кроку 1.

(а) відняти q з усіх cij- ;

(б) додати q до всіх cij+ .

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

Крок 3. Знайти максимальний потік в сітці. Нехай C = ςij - вихідна матриця пропускних спроможностей, і хай C* = ςij - остання матриця, що вийшла в результаті модифікації вихідної матриці (кроки 1 і 2). Оптимальний потік X = ςij у дугах задається як

Максимальний потік з sRt дорівняє

При цьому z є сума всіх позитивних q, визначених на кроці 2. Таким чином, можна пояснити, чому використовуються позитивні елементи матриці C – C* для визначення результуючого потоку у напрямі sRt.

 

ВИСНОВКИ

Виконавши дану роботу по дослідженню застосування методів операційного дослідження для оптимізації задач організації виробництва, можна зробити наступні висновки:

1. Розглянуті та проаналізовано такі підходи операційних досліджень, як процесний підхід, ситуаційний підхід, системний підхід, інтеграційний підхід, структурний та підхід організаційного розвитку, і всі вони є актуальними для застосування їх в сучасних умовах.
2. Досліджено застосування методів операційного дослідження в організаційному управлінні і проаналізовано, що необхідно для їх оптимізації.
3. Розглянуто підходи управління та виявлений їх зв'язок з теорією організації. Всі підходи є необхідними для вирішення задач організації виробництва.
4. Вивчено основні поняття та етапи операційного дослідження і розглянуті такі методи математичного програмування як, лінійне програмування, метод допустимих базисних рішень, симплекс-метод, та методи рішення цілочисельних ЗЛП. Всі ці методи використовуються в сучасних організаціях.
5. Розглянуто основні особливості та властивості дослідження операцій.

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

 

 

 

 

 

 

 

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

1. Филлипс Д. Методы анализа сетей: пер. с англ./Д. Филлипс, А. Гарсиа-Диас.-М.:Мир, 1984. – 496с.
2. Зайченко Ю.П. Исследование операций/ Зайченко Ю.П. – К.: Вища школа. Головное издательство, 1979. – 816с.
3. Таха Х. Введение в исследование операций/ Таха Х. – М.: Мир, 1985. – 901с.
4. Акоф Р. Основы исследования операций/ Р. Акоф, М. Сасиени. – М.: Мир, 1997. – 540с.
5. Зайцев Н.Л. Экономика промышленного предприятия/ Зайцев Н.Л. – М.: Инфра-М, 1998. – 172с.