Методи дослідження операцій

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

МЕТОДИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Програма
Програма дисципліни «Методи дослідження операцій» призначена для студентів спеціальності «Економічна кібернетика».
Мета навчальної дисципліни «Методи дослідження операцій» - озброїти студентів фундаментальними теоретичними знаннями і допомогти сформувати практичні навички в питаннях постановки і рішення оптимізаційних економічних задач методами дослідження операцій.
Дисципліна має практичну спрямованість щодо вирішення питань оптимального розподілу обмежених ресурсів, вибору оптимального варіанту (об'єкта, проекту) з безлічі альтернативних варіантів і т.д.
Основний зміст дисципліни розкривають такі теми:
I семестр
1. Методи дослідження операцій і їх використання в організаційному управлінні.
2. Загальна задача лінійного програмування і деякі методи її вирішення.
3. Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
4. Аналіз лінійних моделей економічних завдань.
5. Транспортна задача. Постановка, методи розв'язання.
6. Цілочисельні задачі лінійного програмування. Деякі методи їх вирішення і аналізу.
II і III семестри
7. Елементи теорії ігор.
8. Блочне програмування.
9. Параметричне програмування.
10. Завдання календарного планування.
11. Завдання нелінійного програмування. Деякі методи їх вирішення.
12. Динамічне програмування.
13. Управління запасами.

Дослідження операцій - це наука, що займається розробкою і практичним застосуванням методів найбільш ефективного (або оптимального) управління організаційними системами.
Предмет дослідження операцій - це системи організаційного управління (організації), які складаються з великого числа взаємодіючих між собою підрозділів, причому інтереси підрозділів не завжди узгоджуються між собою і можуть бути протилежними.
Метою дослідження операцій є кількісне обгрунтування прийнятих рішень з управління організаціями.
Рішення, яке виявляється найбільш вигідним для всієї організації, називається оптимальним, а рішення, найбільш вигідне одному або декільком підрозділам, буде субоптимальний.
Як приклад типової задачі організаційного управління, де стикаються суперечливі інтереси підрозділів, розглянемо задачу управління запасами підприємства.
Виробничий відділ прагне випускати якомога більше продукції при найменших витратах. Тому він зацікавлений у якомога більш тривалому і безперервному виробництві, тобто у випуску виробів великими партіями, оскільки таке виробництво знижує витрати на переналагодження устаткування, а отже і загальні виробничі витрати. Проте випуск виробів великими партіями вимагає створення великих обсягів запасів матеріалів, комплектуючих виробів і т. д.
Відділ збуту також зацікавлений у великих запасах готової продукції, щоб задовольнити будь-які запити споживача в будь-який момент часу. Укладаючи кожен контракт, відділ збуту, прагнучи продати якомога більше продукції, повинен пропонувати споживачеві максимально широку номенклатуру виробів. Внаслідок цього між виробничим відділом та відділом збуту часто виникає конфлікт з приводу номенклатури виробів. При цьому відділ збуту наполягає на включенні в план багатьох виробів, що випускаються в невеликих кількостях навіть тоді, коли вони не приносять великих прибутків, а виробничий відділ вимагає виключення таких виробів з номенклатури продукції.
Фінансовий відділ, прагнучи мінімізувати обсяг капіталу, необхідного для функціонування підприємства, намагається зменшити кількість «пов'язаних» оборотних коштів. Тому він зацікавлений у зменшенні запасів до мінімуму. Як бачимо, вимоги до розмірів запасів у різних підрозділів організації виявляються різними. Виникає питання, яка стратегія щодо запасів буде найбільш сприятливою для всієї організації. Це типове завдання організаційного управління. Вона пов'язана з проблемою оптимізації функціонування системи в цілому і зачіпає суперечливі інтереси її підрозділів.
Основні особливості дослідження операцій.
1. Системний підхід до аналізу поставленої проблеми. Системний підхід, або системний аналіз, є основним методологічним принципом дослідження операцій, який полягає в наступному. Будь-яке завдання, якою б приватної вона не здавалася на перший погляд, розглядається з точки зору її впливу на критерій функціонування всієї системи. Вище системний підхід був проілюстрований на прикладі задачі управління запасами.
2. Для дослідження операцій характерно, що при вирішенні кожної проблеми виникають все нові і нові завдання. Тому якщо спочатку ставляться вузькі, обмежені цілі, застосування операційних методів не ефективно. Найбільший ефект може бути досягнутий тільки при безперервному дослідженні, що забезпечує спадкоємність в переході від однієї задачі до іншої.
3. Однією з істотних особливостей дослідження операцій є прагнення знайти оптимальне рішення поставленої задачі. Однак часто таке рішення виявляється недосяжним через обмеження, що накладаються наявними ресурсами (грошові кошти, машинний час) або рівнем сучасної науки. Наприклад, для багатьох комбінаторних завдань, зокрема завдань календарного планування при числі верстатів п> 4, оптимальне рішення при сучасному розвитку математики виявляється можливим знайти лише простим перебором варіантів. Тоді доводиться обмежуватися пошуком «досить хорошого», або субоптимального рішення. Тому дослідження операцій один з його творців - Т. Сааті - визначив як «... мистецтво давати погані відповіді на ті практичні питання, на які даються ще гірші відповіді іншими методами».
4. Особливість операційних досліджень полягає в тому, що вони проводяться комплексно, з багатьох напрямків. Для проведення такого дослідження створюється операційна група. До її складу входять фахівці різних областей знання: інженери, математики, економісти, соціологи, психологи. Завданням створення подібних операційних груп є комплексне дослідження всього безлічі факторів, що впливають на рішення проблеми, і використання ідей і методів різних наук.
Кожне операційне дослідження проходить послідовно наступні основні етапи:
1) постановка завдання,
2) побудова математичної моделі,
3) знаходження рішення,
4) перевірка і коректування моделі,
5) реалізація знайденого рішення на практиці.
У самому загальному випадку математична модель задачі має вигляд:
знайти
max Z = F (x, y) (1.1)
при обмеженнях
, (1.2)
де Z = F (x, y) - цільова функція (показник якості або ефективність) системи; х - вектор керованих змінних; у - вектор некерованих змінних; Gi (x, y) - функція споживання i-го ресурсу; bi - величина i -го ресурсу (наприклад, плановий фонд машинного часу групи токарних автоматів у верстато-годинах).
Визначення 1. Будь-яке рішення системи обмежень задачі називається допустимим рішенням.
Визначення 2. Допустиме рішення, в якому цільова функція досягає свого максимуму або мінімуму називається оптимальним рішенням задачі.
Для знаходження оптимального рішення задачі (1.1) - (1.2) в залежності від виду і структури цільової функції і обмежень використовують ті чи інші методи теорії оптимальних рішень (методи математичного програмування).
1. Лінійне програмування, якщо F (x, y), - Лінійні відносно змінних х.
2. Нелінійне програмування, якщо F (x, y) або - Нелінійні відносно змінних х.
3. Динамічне програмування, якщо цільова функція F (x, y) має спеціальну структуру, будучи адитивної або мультиплікативної функцією від змінних х.
F (x) = F (x1, x2, ..., xn) - адитивна функція, якщо F (x1, x2, ..., xn) = , І функція F (x1, x2, ..., xn) - мультиплікативна функція, якщо F (x1, x2, ..., xn) = .
4. Геометричне програмування, якщо цільова функція F (x) і обмеження являють собою функції виду

Математична модель задачі в цьому випадку записується у вигляді

за умов ,
,
де I [0] = (m0, m0 +1, ..., n0); I [k] = (mk, mk +1, ..., nk); mk +1 = nk +1; m0 = 1; n0 = n .
5. Стохастичне програмування, коли вектор некерованих змінних у випадковий.
У цьому випадку математична модель задачі (1.1-1.2) матиме
maxMyE = My {f (x, y)}
при обмеженнях

або імовірнісних обмеження

де My - математичне очікування по у; Р {gi (х) £ b} - ймовірність того, що виконується умова gi (х) £ b.
6. Дискретне програмування, якщо на змінні xj накладено умову дискретності (наприклад, цілочисельності): xj - ціле, j = 1,2, ..., n1 £ п.
7. Евристичне програмування застосовують для вирішення тих завдань, в яких точний оптимум знайти алгоритмічним шляхом неможливо з-за величезного числа варіантів. У такому разі відмовляються від пошуку оптимального рішення і відшукують досить гарна (або задовільний з точки зору практики) рішення. При цьому користуються спеціальними прийомами - евристиками, що дозволяють істотно скоротити число переглядаються варіантів. Евристичні методи також застосовують, коли оптимальне рішення в принципі може бути знайдено (тобто задача алгоритмічно розв'язна), однак для цього потрібні обсяги ресурсів, що значно перевищують готівку.
За змістовною постановці виділяють наступні типові класи задач дослідження операцій:
1) управління запасами,
2) розподілу ресурсів,
3) ремонту та заміни обладнання,
4) масового обслуговування,
5) упорядкування,
6) мережевого планування і управління,
7) вибору маршруту,
8) комбіновані.
З перерахованих вище методів математичного програмування найбільш розвиненим і закінченим є лінійне програмування. У його рамки укладається широке коло завдань дослідження операцій.
Лінійне програмування
Незважаючи на вимогу лінійності цільової функції й обмежень, у рамки лінійного програмування укладаються задачі розподілу ресурсів, управління запасами, мережного і календарного планування, транспортні задачі, задачі теорії розкладів і т. д.
Визначення оптимального асортименту. Є р видів ресурсів у кількостях а1, а2, ..., аi, ..., аp і q видів виробів. Задано матриця А = | | aik | |, де аik характеризує норми витрати i-го ресурсу на одиницю k-го виробу (k = 1, 2, ..., q).
Ефективність випуску одиниці k-го виробу характеризується показником сi, що задовольняє умові лінійності.
Визначити план випуску виробів (оптимальний асортимент), при якому сумарний показник ефективності приймає найбільше значення.
Кількість одиниць k-го виробу, що випускаються підприємством, позначимо хk. Тоді математична модель задачі має такий вигляд:
знайти
(1.3)
при обмеженнях
(1.4)
Крім обмеження по ресурсах (1.3), у модель можуть бути введені додаткові обмеження на планований випуск продукції xj ³ xj0, умови комплектності для збірки xi: хj: xk. = Bi: bj: bk для всіх i, j, k і т. д.
Оптимальний розподіл взаємозамінних ресурсів. Є т видів взаємозамінних ресурсів а1, а2, ..., аi, ..., аm використовуються при виконанні п різних робіт в обсязі b1, b2, ..., bn.
Задані числа lij, що вказують, скільки одиниць j-ї роботи можна отримати з одиниці i-го ресурсу, а також Сij - витрати при виготовленні одиниці j-го продукту з i-го ресурсу.
Потрібно розподілити ресурси по роботах таким чином, щоб сумарна ефективність була найбільшою (або сумарні витрати - найменшими).
Дане завдання називається загальною розподільній завданням.
Кількість одиниць i-го ресурсу, який виділено для виконання робіт j-то виду, позначимо xij.
Математична модель задачі така:
знайти
(1.5)
при обмеженнях
(1.6)
(1.7)
Обмеження (1.6) означає, що план усіх робіт повинен бути виконаний повністю, а обмеження (1.7) - що ресурси повинні бути витрачені цілком.
2. Математична модель задачі лінійного програмування (ЗЛП).

Задачу лінійного програмування можна сформулювати так

Знайти
(2.1)
за умов
(2.2)
і
(2.3)
Обмеження (2.3) називають умовами неотрицательности. У даному випадку всі умови мають вигляд нерівностей. Іноді вони можуть бути змішаними, тобто нерівності та рівності.
Визначення 3. Допустимим безліччю розв'язків задачі (2.1) - (2.3) називається безліч R (х) усіх векторів х, які відповідають умовам (2.2) та (2.3).
Очевидно безліч R (х) являє собою опукле багатогранне безліч або опуклий багатогранник.
Зазначимо, що оскільки minF (х) еквівалентний max [-F (х)], то завдання ЛП завжди можна звести до еквівалентної задачі максимізації.

Стандартна форма задачі лінійного програмування

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

Допустимі базисні рішення.
Нехай обмеження завдання ЛП задані у формі рівнянь, тобто завдання записана в стандартній формі і містить m рівнянь і n (n ³ m) змінних. Тоді всі допустимі крайні точки множини припустимих рішень визначаються як усі однозначні невід'ємні рішення системи m рівнянь, в яких nm змінних дорівнюють нулю. Однозначні рішення такої системи рівнянь, одержувані шляхом прирівнювання до нуля (nm) змінних, називаються базисними рішеннями. Якщо базисне рішення задовольняє вимогу неотрицательности, воно називається допустимим базисним рішенням. Змінні, що мають нульове значення називається небазисная або вільними змінними, а решта засадничими.

Основні теореми лінійного програмування

В основі методів рішення задач лінійного програмування лежать наступні теореми.
Основна теорема лінійного програмування, що встановлює місце знаходження оптимальних рішень.
Теорема 2.1. Якщо цільова функція приймає максимальне значення в деякій точці допустимого множини R, то вона приймає це значення в крайній точці R (вершині опуклого багатогранника). Якщо цільова функція приймає максимальне значення більш, ніж в одній крайній точці, то вона приймає це ж значення в будь-якій їх опуклої комбінації.
З теореми 2.1 випливає, що при знаходженні оптимального рішення досить переглянути тільки крайні точки допустимого безлічі рішень R.
Теорема 2.2. Кожне дозволене базисне рішення відповідає крайній точці R.
Справедлива також наступна теорема, обернена до теореми 2.2. Теорема 2.3. Якщо - Крайня точка допустимого безлічі рішень R, то відповідне рішення x0 - є допустимим базисним рішенням системи обмежень задачі лінійного програмування.
Використовуючи результати теорем 2.1 та 2.2, можна зробити висновок, що для відшукання оптимального рішення задачі лінійного програмування досить перебрати лише допустимі базисні рішення. Цей висновок лежить в основі багатьох методів вирішення завдань лінійного програмування.
Симплекс-метод.
Загальна ідея симплекс-методу полягає в наступному: починаючи із певною вихідної припустимою кутовий точки (зазвичай початку координат), здійснюються послідовні переходи від однієї крайньої точки в іншу до тих пір, поки не буде знайдена точка відповідна оптимального рішення. Рішення задачі лінійного програмування симплекс-методом зручно оформляти у вигляді симплекс-таблиць.
Алгоритм симплекс-методу складається з наступних кроків:
Крок 0. Використовуючи лінійну модель стандартної форми, визначають початкова дозволене базисне рішення шляхом прирівнювання до нуля nm (небазисних) змінних. При цьому якщо матриця системи обмежень задачі лінійного програмування містить одиничну підматриць порядку m, то це рішення є очевидним. Змінні, стовпці яких утворюють цю одиничну матрицю, є базисними, інші - вільними. Якщо ж такий одиничної матриці немає, то для отримання початкового базисного рішення вводяться штучні змінні. Потім базисні змінні виражаються через небазисних з відповідних обмежень і отримані вирази підставляються у цільову функцію. Якщо використовуються штучні змінні, то застосовуються спеціальні методи (метод великих штрафів, двоетапний метод).
Крок 1. З-поміж поточних небазисних змінних вибирається включається в новий базис мінлива, збільшення якої забезпечує поліпшення значення цільової функції. Якщо такої змінної немає, обчислення припиняються, тому що отримане базисне рішення оптимально. В іншому випадку переходять до кроку 2.
Крок 2. З числа змінних поточного базису вибирається исключаемая змінна, яка повинна ухвалити нульовий рішення (стати небазисной) при введенні до складу базисних нової змінної.
Крок 3. За допомогою методу виключення змінних або методу Гауса-Жордана знаходиться нове базисне рішення, відповідне нових складів базисних і небазисних змінних і здійснюється перехід до кроку 1.
Приклад. Вирішити симплекс-методом задачу
Максимізувати z = 3x1 +2 x2
при обмеженнях x1 +2 x2 £ 6;
2x1 + x2 £ 8;
-X1 + x2 £ 1;
x1 £ 2;
x1 ³ 0, x2 ³ 0.
Рішення.

Запишемо завдання в стандартному вигляді

z-3x1-2x2 = 0
x1 +2 x2 + s1 = 6;
2x1 + x2 + s2 = 8;
-X1 + x2 + s3 = 1;
x1 + s4 = 2,
де s1, s2, s3, s4 - додаткові невід'ємні змінні, які вводяться в праві частини обмежень мають знак «£» і називаються залишковими. Якщо завдання лінійного програмування є завданням оптимального розподілу обмежених ресурсів, і праві частини кожного обмеження представляють запаси ресурсів, то значення залишкових змінних в будь-якому рішенні показують залишок цих ресурсів. Матриця системи обмежень містить одиничну матрицю порядку 4. Її утворюють коефіцієнти при залишкових змінних, значить змінні s1, s2, s3, s4 будуть базисними змінними, а x1, x2 - вільними або нульовими.
Крок 0. Заповнюємо початкову симплекс-таблицю.
Базисні
змінні
x1
x2
S1
s2
s3
s4
Рішення
У
Z
-3
-2
0
0
0
0
0
Z-рівняння
s1
1
2
1
0
0
0
6
s1-рівняння
s2
2
1
0
1
0
0
8
s2-рівняння
s3
-1
1
0
0
1
0
1
s3-рівняння
s4
0
1
0
0
0
1
2
s4-рівняння
Крок 1. Умова оптимальності або правило вибору включається в базис змінної. Вводиться в базис змінної в задачі максимізації (мінімізації) є небазисная мінлива, має в Z-рядку найбільший за модулем від'ємний (позитивний) коефіцієнт. Якщо таких коефіцієнтів кілька, то вибір - довільний і після цього переходять до кроку 2. Якщо таких коефіцієнтів немає, то рішення оптимально.
Стовпець симплекс-таблиці, відповідний включається змінної, будемо називати ведучим стовпцем. У нашому випадку включаємо в базис змінну x1.
Крок 2. Умова допустимості чи правило вибору исключаемой з базису змінної (однакове в завданнях максимізації та мінімізації). Як исключаемой з базису змінної вибирається та базисна змінна, на яку ставлення постійної у правій частині відповідного обмеження до позитивного коефіцієнта ведучого шпальти мінімально. У випадку рівності цього стосунки для кількох базисних змінних вибір робиться довільно.
Рядок симплекс-таблиці, відповідну исключаемой змінної, будемо називати провідною рядком. У нашому випадку виключаємо з базису змінну s2.
Крок 3. Обчислюємо нове базисне рішення і переходимо до кроку 1.
Симплекс-таблиця, відповідна першій ітерації:
Базисні
змінні
x1
x2
s1
S2
s3
s4
Рішення
У
Z
0

0
3 / 2
0
0
12
Z-рівняння
s1
0
3 / 2
1
- Ѕ
0
0
2
s1-рівняння
x1
1
Ѕ
0
Ѕ
0
0
4
s2-рівняння
s3
0
3 / 2
0
Ѕ
1
0
5
s3-рівняння
s4
0
1
0
0
0
1
2
s4-рівняння
Рішення не оптимально. Включаємо в базис x2 замість s1. Друга ітерація:
Базисні
змінні
x1
x2
s1
s2
s3
s4
Рішення
У
Z
0
0
1 / 3
4 / 3
0
0
12 2 / 3
Z-рівняння
x2
0
1
2 / 3
-1 / 3
0
0
4 / 3
s1-рівняння
x1
1
0
-1 / 3
2 / 3
0
0
10 / 3
s2-рівняння
s3
0
0
-1
1
1
0
3
s3-рівняння
s4
0
0
-2 / 3
1 / 3
0
1
2 / 3
s4-рівняння
Рішення оптимально.
Аналіз рішення на чутливість.
З оптимальної симплекс-таблиці або безпосередньо, або за допомогою простих перетворень можна отримати інформацію щодо
1. Оптимального рішення: значення базисних змінних записані в стовпці У оптимальної симплекс-таблиці. Оптимальне значення цільової функції знаходиться на перетині Z-рядка та стовпця У оптимальної симплекс таблиці. Для розглянутого прикладу: x1 = 10 / 3, x2 = 4 / 3, s1 = s2 = 0, s3 = 3, s4 = 2 / 3, Zmax = 12 2 / 3.
2. Статусу ресурсів: ресурс називається дефіцитним, якщо в оптимальному рішенні він використано повністю. Залишкова мінлива, відповідна дефіцитного ресурсу в оптимальному рішенні дорівнює нулю. Для розглянутого прикладу дефіцитними будуть ресурси 1 і 2, тому що s1 = s2 = 0,
3. Цінності кожного ресурсу: характеризуються величиною поліпшення оптимального значення цільової функції, що припадає на одиницю приросту обсягу даного ресурсу. Їх ще називають тіньовими цінами ресурсів або подвійними оцінками. Ця інформація представлена ​​в Z-рядку оптимальної симплекс-таблиці у стовпцях, відповідних залишковим змінним.
4. Чутливості оптимального рішення до змін запасів ресурсів, варіацій коефіцієнтів цільової функції та інтенсивності споживання ресурсів.
Двоїстість в лінійному програмуванні.
Будь-яке завдання максимізації з економічної точки зору можна розглядати як завдання про розподіл обмежених ресурсів b1, b2, ..., bn між різними споживачами, наприклад, між деякими технологічними процесами, які представляються стовпцями A1, А2, ..., Аm матриці обмежень задачі. Будь-яке допустиме рішення задачі лінійного програмування х1, х2, ..., хm дає конкретний розподіл, яке вказує ту частку кожного з ресурсів, яка повинна бути використана під час здійснення відповідного технологічного процесу.
Розглянемо приклад. Завод виробляє три види продукції х1, x2 і x3, кожен з яких вимагає витрат часу на обробку на токарному, фрезерному і свердлильному верстатах. Кількість машинного часу для кожного з верстатів обмежена. Нехай з1, c2 і c3 - прибуток від реалізації одиниці відповідного виду продукції. Необхідно визначити, яку кількість кожного виду продукції необхідно робити протягом тижня, щоб отримати максимальний прибуток.
Формально ця задача записується так:
знайти
(1)
при обмеженнях
(2)
де a1j, a2j, a3j - час, необхідний для обробки одиниці j-го виду продукції відповідно на токарному, фрезерному і свердлильному верстатах (j = 1, 2, 3); b1, b2, b3 - тижневий ресурс машинного часу відповідно для токарного, фрезерного та свердлильного верстатів.
Позначимо y1, y2 і y3 - ціну одиниці часу роботи на токарному, фрезерному і свердлильному верстатах. Тоді a1jy1 + a2jy2 + a3jy3 можна трактувати як витрати на виготовлення одиниці продукції виду j.
Припустимо, що ціни ресурсів y1, y2 і y3 вибрані так, що виконуються наступні співвідношення:
(3)
Оскільки b1, b2, b3 - використаний ресурс машинного часу для кожного з верстатів, то b1y1 + b2y2 + b3y3 - сумарні витрати на виробництво.
Потрібно знайти такі y1, y2 і y3, що задовольняють умовам (3), при яких мінімізуються сумарні витрати на виробництво:
min g (y1, y2, y3) = b1y1 + b2y2 + b3y3, (4)
y1 ³ 0, y2 ³ 0, y3 ³ 0.
Таке завдання називають двоїстої завданням по відношенню до задачі (1), званої прямої.
Запишемо тепер пряму і двоїсту завдання в загальному випадку. Пряма задача
(5)
за умов
(6)
. (7)
Двоїста задача
(8)
за умов
(9)
. (10)
Зіставляючи форми запису прямої і двоїстої задач, можна встановити між ними наступні взаємозв'язки:
1) якщо пряма задача є задачею максимізації, двоїста буде завданням мінімізації, і навпаки;
2) коефіцієнти цільової функції прямої задачі c1, c2, ..., cn стають вільними членами обмежень двоїстої задачі;
3) вільні члени обмежень прямої задачі b1, b2, ..., bm стають коефіцієнтами цільової функції двоїстої задачі;
4) матрицю обмежень двоїстої задачі отримують транспонування матриці обмежень прямої задачі;
5) якщо знаки всіх нерівностей в обмеженнях прямої «£», то в двоїстої задачі всі обмеження будуть мати знак «³»;
6) кількість обмежень прямої задачі дорівнює числу змінних двоїстої задачі, а кількість обмежень двоїстої задачі дорівнює числу змінних прямої задачі.
Змінні y1, y2, ..., ym двоїстої завдання іноді називають «тіньовими цінами».
Двоїсту задачу вигідніше вирішувати, ніж вихідну пряму, якщо в прямій задачі при малій кількості змінних є велика кількість обмежень (т> n).
Зв'язок між оптимальними рішеннями прямої і двоїстої задач встановлюють за допомогою наступних теорем теорії подвійності.
Теорема. Якщо x0 і у0 - допустимі вирішення прямої і двоїстої задач, тобто якщо Ах0 £ b і АTy0 ³ с, то
cTx0 £ bTy0,
тобто значення цільової функції прямої задачі ніколи не перевищують значень цільової функції двоїстої задачі.
Теорема (основна теорема подвійності). Якщо x0 і у0 - допустимі вирішення прямої і двоїстої задач і якщо cTx0 = bTy0, то x0 і у0 - оптимальні рішення пари двоїстих задач.
Теорема. Якщо в оптимальному рішенні прямої задачі i-е обмеження виконується як суворе нерівність, то оптимальне значення відповідної двоїстої змінної дорівнює нулю.
Сенс цієї теореми полягає в наступному. Якщо певний ресурс bi є в надлишку і i-е обмеження при оптимальному рішенні виконується як суворе нерівність, то воно стає несуттєвим, і оптимальна ціна відповідного ресурсу дорівнює 0.
Теорема. Якщо в оптимальному вирішенні двоїстої задачі обмеження j виконується як суворе нерівність, то оптимальне значення відповідної змінної прямої задачі має дорівнювати нулю.
Економічна інтерпретація цієї теореми: оскільки величини yj являють собою ціни відповідних ресурсів, то - Це витрати на i-й технологічний процес, величина сi - прибуток від реалізації на одиницю виробу. Тому з економічної точки зору теорема означає наступне: якщо i-й технологічний процес виявляється строго невигідним з точки зору оптимальних цін ресурсів УГХТ, то в оптимальному рішенні прямої задачі інтенсивність використання даного технологічного процесу хi повинна бути дорівнює 0.
Таким чином, теорема висловлює принцип рентабельності оптимального організованого виробництва.
Теорема (теорема існування). Пряма і двоїста завдання мають оптимальні рішення тоді і тільки тоді, коли обидві вони мають допустимі рішення.
Теорема (теорема подвійності). Допустимий вектор x0 оптимальний тоді і тільки тоді, коли в двоїстої задачі є таке допустиме рішення уо, що
.

Методи рішення цілочисельних ЗЛП.
Цілочисельне програмування орієнтоване на рішення задач математичного програмування, в яких всі або деякі змінні повинні приймати тільки цілочисельні значення. Завдання називається повністю целочисленной, якщо умова цілочисельності накладено на всі змінні; коли ця умова відноситься лише до деяких змінним, завдання називається частково целочисленной. Якщо при цьому цільова функція і функції, що входять в обмеження, лінійні, то завдання є задачею лінійного програмування.
Методи рішення задач цілочислового програмування можна класифікувати як методи відсікань (1) і комбінаторні методи (2).
Вихідною задачею для методів відсікань, використовуваних при вирішенні лінійних цілочислових задач, є завдання з ослабленими обмеженнями, яка виникає внаслідок вилучення вимоги цілочисельності змінних. У міру введення спеціальних додаткових обмежень, що враховують вимоги цілочисельності, багатогранник допустимих рішень ослабленою завдання поступово деформується до тих пір, поки координати допустимого рішення не стануть цілочисельними. Назва «методи відсікань» пов'язано з тією обставиною, що вводяться додаткові обмеження відсікають (виключають) деякі області багатогранника допустимих рішень, в яких відсутні точки з цілочисельними координатами,
В основі комбінаторних методів лежить ідея перебору всіх допустимих цілочислових рішень, зрозуміло, на перший план тут висувається проблема розробки тестових процедур, що дозволяють безпосередньо розглядати лише відносно невелику частину зазначених рішень, а інші допустимі рішення враховувати деяким непрямим чином. Найбільш відомим комбінаторним методом є метод гілок і меж, який також спирається на процедуру вирішення завдань з ослабленими обмеженнями. При такому підході з розглянутої задачі виходять дві підзадачі шляхом спеціального «розбиття» простору допустимих рішень і відкидання областей, що не містять допустимих цілочислових рішень.
У випадку, коли цілочисельні змінні є булевими, застосовуються комбіновані методи. Булеві властивості змінних істотно спрощують пошук рішення.
Алгоритм методу відсікань для вирішення повністю целочисленной завдання.
Необхідною умовою застосування даного алгоритму є целочисленость всіх коефіцієнтів і правих частин обмежень вихідної задачі. Будь-яке обмеження з раціональними коефіцієнтами легко приводиться до необхідного вигляду шляхом множення обмеження на найменший спільний знаменник входять до нього коефіцієнтів.
Алгоритм полягає в наступному. На першому кроці вирішується завдання з ослабленими обмеженнями, що не містить умов цілочисельності змінних. Якщо отримане оптимальне рішення виявляється цілочисловим, то воно є також рішенням вихідної задачі. В іншому випадку слід ввести додаткові обмеження, які породжують (разом з деякими обмеженнями) нову задачу лінійного програмування, рішення якої виявляється цілочисловим і збігається з оптимальним рішенням вихідної целочисленной завдання. Нехай остання симплекс-таблиця завдання з ослабленими обмеженнями має наступний вигляд:
Базисні перемінні
x1
...
xi
...
xm
w1
...
wj
...
wn
Рішення

Z

0
...
0
...
0
C1
...
Cj
...
Cn
b0
x1
1
...
0
...
0
a11
...
aj1
...
an1
b1
...
...
...
...
...
...
...
...
...
...
...
...
xi
0
...
1
...
0
a1i
...
aji
...
ani
bi
...
...
...
...
...
...
...
...
...
...
...
...
xm
0
...
0
...
1
a1m
...
ajm
...
anm
bm
Розглянемо i-й рядок, який відповідає неціле значення базисної змінної xi, і висловимо xi через небазисних змінні:
, BI - неціле.
Кожну рядок симплекс-таблиці, що породжує аналогічне рівність будемо називати виробляє рядком. Оскільки коефіцієнти цільової функції можна вважати цілими числами, мінлива Z також повинна бути целочисленной, і верхній рядок таблиці також може бути обрана в якості виробляє. Нехай
bI = [bI] + fi, aji = [aji] + fij, 0 <fi <1, 0 £ fij <1.
В якості додаткового обмеження вводимо таке
,
де Si - невід'ємна додаткова змінна, яка за визначенням повинна приймати цілі значення. Таке обмеження рівність визначає відсікання Гоморі для повністю целочисленной завдання. Додавши побудоване обмеження у симплекс-таблицю, отримаємо неприпустиме, але оптимальне рішення. У такій ситуації слід використовувати двоїстий симплекс-метод для отримання допустимого і оптимального рішення.
Метод гілок і меж.
На першому кроці також вирішується завдання з ослабленими обмеженнями, що не містить умов цілочисельності змінних. Але на відміну від методів відсікань цей метод може застосовуватися як для повністю целочисленной завдання, так і для частково целочисленной. Якщо отримане оптимальне рішення виявляється цілочисловим, то воно є також рішенням вихідної задачі. Ідея методу полягає в наступному. Нехай xr цілочисельна змінна, значення якої xr в оптимальному вирішенні ослабленою завдання є дробовим. Інтервал
[Xr] <xr <[xr] +1
не містить допустимих цілочислових компонент рішення. Тому допустиме ціле значення xr має відповідати одній з нерівностей [xr] ³ xr або xr ³ [xr] +1. Введення цих умов у завдання з ослабленими обмеженнями породжує дві не пов'язані між собою завдання. У такому випадку говорять, що вихідна задача розгалужується на дві підзадачі. Здійснюваний в процесі розгалуження облік необхідних умов цілочисельності дозволяє виключити частини багатогранника допустимих рішень, що не містять точок з цілими координатами.
Потім кожна з підзадач вирішується як задача лінійного програмування двоїстим симплекс-методом. Якщо отриманий оптимум виявляється допустимим для целочисленной завдання, то це рішення слід зафіксувати як найкраще. В іншому випадку підзадача у свою чергу повинна бути розбита на дві підзадачі за іншою змінною і т.д.
Завдання лінійного програмування транспортного типу.
Постановка завдання. Нехай у m пунктах виробляють деякий однорідний продукт, причому обсяг виробництва в пункті i становить Ai одиниць. Припустимо, що даний продукт споживається в n пунктах споживання, а обсяг споживання в пункті j складає одиниць Bj. Припустимо, що з кожного пункту виробництва i можливе транспортування продукту в будь-який пункт споживання j з витратами cij. Завдання полягає у визначенні такого плану перевезень, при якому запити всіх споживачів повністю задоволені, весь продукт вивезений з пунктів виробництва і сумарні транспортні витрати мінімальні.

Математична модель. Нехай xij - кількість продукту, що перевозиться з пункту i в пункт j. Знайти безліч змінних задовольняють умови

,

.

і таких, що цільова функція

досягає мінімуму.

Метод вирішення транспортної задачі [6, 7, 10].

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

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

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

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

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

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

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

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

(А) вирахувати q з усіх cij-;

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

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

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

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


Максимальний потік з s в t дорівнює

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


Література

1. Протосеня А.Г., Куліш С.А., Азбель Є.І. та ін Математичні методи плануванні та управлінні гірничим виробництвом. Навчальний посібник для вузів. - М.: Наука, 1985.
2. Філліпс Д., Гарсіа-Діас А. Методи аналізу мереж. -М.: Світ, 1984.
3. Пападімітру Х., Стайгліц К. Комбінаторна оптимізація. Алгоритми і складність. - М.: Світ, 1985.
4. Грешілов А.А. Як взяти найкраще рішення в реальних умовах. - М.: Радіо і зв'язок, 1991.
5. Попов Ю.Д. Лінійне і нелінійне програмування. Навчальний посібник. - Київ, 1988.
6. Зайченко Ю.П. Дослідження операцій. Навчальний посібник для студентів вузів. - Київ: Вища школа. Головне видавництво, 1979
7. Таха Х.. Введення в дослідження операцій: у 2-х книгах. - М.: Світ, 1985.
8. Акофа Р., Сасіені М. Основи дослідження операцій. - М.: Світ, 1997.
9. Акулич І.Л. Математичне програмування в прикладах і задачах. - М.: Вища школа, 1986.
10. Данко. Вища математика в прикладах і задачах.

Контрольна робота.
Контрольна робота виконується в окремому зошиті або на аркушах. Контрольна робота складається з 7 завдань, представлених у загальному вигляді. Числові дані до кожного завдання видаються викладачем і повинні слідувати у виконаній контрольної роботи після титульного аркуша. Рішення задач повинні супроводжуватися достатніми поясненнями. При вирішенні допускається використання ПЕОМ. Контрольна робота вважається виконаною, якщо вирішені всі завдання. Контрольна робота захищається на консультації або протягом семестру, або перед заліком. До заліку допускаються тільки студенти, які захистили свою роботу.
Завдання 1
Для виготовлення трьох видів продукції Р1, Р2 і Р3 використовують чотири види ресурсів S1, S2, S3 і S4. Запаси ресурсів, кількість кожного ресурсу, що витрачається на виготовлення одиниці продукції, прибуток, одержуваний від одиниці продукції, наведені в таблиці.

Вид ресурсу

Запас ресурсу

Число одиниць ресурсу, що витрачаються на виготовлення одиниці продукції

Р1
Р2
Р3

S1

B1
A11
A12
A13
S2
B2
A21
A22
A23
S3
B3
A31
A32
A33
S4
B4
A41
A42
A43
Прибуток, що отримується від одиниці продукції
C1
C2
C3
Потрібно:
a) скласти такий план виробництва продукції, при якому прибуток від її реалізації буде максимальною;
b) провести аналіз на чутливість оптимального рішення до певних змін вихідної моделі, використовуючи оптимальну симплекс-таблицю. Для цього
1) Побудувати математичну модель, з докладним описом змінних, обмежень і цільової функції.
2) Привести задачу до стандартного вигляду.
3) Визначити початковий допустимий план.
4) Заповнити початкову симплекс-таблицю.
5) Знайти оптимальний план виробництва симплекс-методом. (Допускається використання ПЕОМ). Рішення оформити у вигляді симплекс-таблиць.
6) За оптимальної симплекс-таблиці визначити: обмежена чи простір допустимих рішень; єдино чи оптимальне рішення задачі; чи є у завдання вироджені рішення. Усі відповіді пояснити і обгрунтувати.
7) Визначити, які з ресурсів є дефіцитними. Чому?
8) Визначити на скільки можна збільшити запас дефіцитних ресурсів, для поліпшення отриманого оптимального значення цільової функції.
9) Визначити, на скільки можна знизити запас деякого ресурсу при збереженні отриманого оптимального значення цільової функції.
10) Визначити збільшення запасу якого із ресурсів найвигідніше.
11) Визначити, в яких межах допустимо зміна коефіцієнтів цільової функції.
Завдання 2.
Для задачі, отриманої в першому завданні побудувати двоїсту. Дати економічну інтерпретацію двоїстої задачі. Вирішити двоїсту задачу. Використовуючи співвідношення подвійності, отримати оптимальне рішення прямої задачі.
Завдання 3.
До математичної моделі, отриманої в завданні 1 додати умова цілочисельності для всіх змінних. Вирішити нову задачу методом відсікань.
Завдання 4.
Вирішити транспортну задачу.
Завдання 5.
Для кожної дуги (i, j) неориентированной мережі вказана її довжина. Побудувати мінімальне дерево-остов.
Завдання 6.
Для кожної дуги (i, j) неориентированной мережі вказана її довжина. Знайти найкоротший маршрут з вузла 1 у вузол 13.
Завдання 7.
Для кожної дуги (i, j) мережі вказана її пропускна здатність. Знайти максимальний потік з джерела s у стік t.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Лекція
169.2кб. | скачати


Схожі роботи:
Кабінетні дослідження і методи збору вторинних даних Дослідження переваг студентів
Методи дослідження сечовивідної системи Дослідження в гінекології і акушерстві
Методи прояви системної ідеї Евристичні методи дослідження систем управління
Ультразвукове дослідження МРТ і методи дослідження легень
Дослідження операцій 4
Дослідження операцій
Дослідження операцій 2
Дослідження операцій 2
Дослідження операцій 5
© Усі права захищені
написати до нас