Тематика лабораторних занять з дисципліни

«Методи оптимізації та дослідження операцій»

Загальна кількість годин – 243 години

Лабораторних занять – 32 години

Лабораторна робота № 1-2. Задача лінійного програмування. Графічний спосіб розв’язування задач лінійного програмування.

Питання, які виносяться на лабораторну роботу:

 

1. Загальна математична модель задачі лінійного програмування.

2. Різні форми запису задач лінійного програмування

4. Геометрична інтерпретація задачі лінійного програмування.

5. Допустимий розв’язок задачі лінійного програмування.

6. Область допустимих планів.

7. Опорний план, невироджений план.

8. Основні аналітичні властивості розв’язків задачі лінійного програмування.

9. Які задачі можна розв’язувати графічним методом?

10. За яких умов задача лінійного програмування з необмеженою областю допустимих планів має розв’язок?

11. Суть алгоритму графічного методу розв’язування задачі лінійного програмування.

 

Завдання:

1. Розв’язати графічно задачу лінійного програмування:

знайти max Z та min Z в області, заданій системою обмежень

2. Виконати перевірку засобами MS Excel (Поиск решения)

№ варіанта	Задача 1	Задача 2	Задача 3
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

Лабораторна робота № 3-4-5. Симплекс-методрозв’язування задачі лінійного програмування.

Питання, які виносяться на лабораторну роботу:

 

1. Для розв’язування яких математичних задач застосовується симплексний метод?

2. Суть алгоритму симплексного методу.

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

4. Як вибрати напрямний вектор-стовпець?

5. Як вибрати розв’язувальний елемент?

6. За яких умов задача лінійного програмування з необмеженою областю допустимих планів має розв’язок.

7. Суть методу штучного базису.

8. Алгоритм методу штучного базису.

Завдання:

1. Розв’язати задачі лінійного програмування з лабораторної роботи № 1 (знайти max Z та min Z) використовуючи симплекс-метод;

2. Написати програму розв’язування задачі лінійного програмування на будь-якій мові.

 

Лабораторна робота № 6. Двоїсті задачі лінійного програмування.

Питання, які виносяться на лабораторну роботу:

 

1. У чому сутність двоїстості у лінійному програмуванні?

2. Економічна інтерпретацію двоїстих оцінок.

3. Які взаємоспряжені задачі називаються симетричними, а які — несиметричними? Чим вони відрізняються?

4. Скільки змінних та обмежень має двоїста задача відповідно до прямої?

5. Сформулюйте першу теорему двоїстості та дайте її економічне тлумачення.

6. Сформулюйте другу теорему двоїстості та дайте її економічне тлумачення.

7. Сформулюйте третю теорему двоїстості та дайте її економічне тлумачення.

8. Сформулюйте правила побудови двоїстих задач.

9. Як за розв’язком прямої задачі знайти розв’язок двоїстої?

10. Запишіть всі можливі види прямих і двоїстих задач.

 

Завдання:

1. Записати задачі, двоїсті до задач лінійного програмування з лабораторної роботи № 1.

2. Розв’язати отримані задачі симплекс-методом.

3. Перевірити результати, використовуючи програму, написану в ЛР № 3-5 або можливості MS Excel.

 

Література

 

Лабораторна робота № 7. Транспортна задача. Методи побудови опорного плану транспортної задачі.

Питання, які виносяться на лабораторну роботу:

Економічна і математична постановка транспортної задачі

Властивості опорних планів транспортної задачі

Методи побудови опорного плану транспортної задачі

Випадок виродження опорного плану транспортної задачі

Методи розв’язування транспортної задачі - Задача, двоїста до транспортної - Метод потенціалів розв’язування транспортної задачі - Монотонність і скінченність методу потенціалів - Приклади розв’язування транспортних задач методом потенціалів - Угорський метод розв’язування транспортної задачі

Транспортна задача з додатковими умовами

Двохетапна транспортна задача

Транспортна задача за критерієм часу

Розв’язування транспортної задачі на мережі - Транспортна задача у мережевій формі - Метод потенціалів на мережі

Приклади економічних задач, що зводяться до транспортних моделей

 

1.Економічна і математична постановка транспортної задачі.

2.Чим відрізняється транспортна задача від загальної задачі лінійного програмування?

3.Необхідна і достатня умова існування розв’язку транспортної задачі.

4.Властивості опорних планів транспортної задачі.

5.Відкрита і закрита транспортна задача.

6.Методи побудови опорного плану:

Ø метод північно-західного кута,

Ø метод мінімального елемента,

Ø метод подвійної переваги,

Ø метод апроксимації Фотеля.

7. Що означає «виродження» опорного плану? Як його позбутися?

 

Завдання:

1. Побудуйте невироджений опорний план методами

Ø північно-західного кута,

Ø мінімального елемента,

Ø подвійної переваги

Ø апроксимації Фогеля для такої транспортної задачі.

Ø Порівняйте ці плани.

Варіант 1

ai = (8; 10; 5); bj = (5; 5; 10);

.

Варіант 2

ai = (8; 7; 6); bj = (7; 10; 6);

.

Варіант 3

ai = (15; 10; 5; 20); bj = (10; 20; 15);

.

Варіант 4

ai = (10; 20; 40); bj = (30; 10; 60);

.

Варіант 5

ai = (30; 35; 60); bj = (25; 25; 40; 30);

.

Варіант 6

ai = (160; 80; 60); bj = (60; 20; 40; 20; 100);

.

Варіант 7

ai = (5; 20; 10); bj = (10; 25; 15);

.

Варіант 8

ai = (30; 40; 20); bj = (40; 30; 20; 40);

.

Варіант 9

ai = (30; 40; 50); bj = (35; 30; 60);

.

Варіант 10

ai = (10; 20; 80; 50); bj = (30; 10; 60; 50);

.

Варіант 11

ai = (40; 20; 50; 20); bj = (20; 45; 35; 40);

.

Варіант 12

А=(60, 100, 40,30,120), В=(70, 90, 80, 110), .

Варіант 13

А=(200, 180,120), В=(95, 110, 135, 70), .

Варіант 14

А=(130, 70, 50, 80, 60), В=(100, 80, 60, 150), .

Варіант 15

А=(115, 90, 205), В=(95, 150, 85, 80), .

Варіант 16

А=(200, 180, 120), В=(95, 110, 135, 70), .

Варіант 17

А=(100, 150, 50), В=(75, 80, 60, 85), .

Варіант 18

А=(30, 20, 15), В=(10, 20, 25, 20), .

Варіант 19

А=(100, 250, 200, 300), В=(200, 200, 100, 100, 250), .

Варіант 20

А=(200, 150, 50), В=(175, 80, 60, 85), .

Варіант 21

А=(120, 130, 50), В=(75, 50, 80, 85), .

Лабораторна робота № 8. Транспортна задача. Метод потенціалів розв’язування транспортної задачі.

Питання, які виносяться на лабораторну роботу:

 

1. Суть методу потенціалів.

2. Алгоритм розв’язування транспортної задачі методом потенціалів.

3. Як обчислюють потенціали?

4. Умова оптимальності транспортної задачі.

Завдання:

Розв’язати транспортну задачу з ЛР № 7 методом потенціалів.

 

 

Лабораторна робота № 9. Транспортна задача. Метод потенціалів розв’язування транспортної задачі з додатковими умовами.

Питання, які виносяться на лабораторну роботу:

1. Економічна і математична постановка транспортної задачі з додатковими умовами.

2. Особливості розв’язування транспортних задач з додатковими умовами

Завдання:

Розв’язати транспортні задачі з додатковими умовами

Варіант 1. Передбачено штрафи за недопостачання одиниці продукції до споживачів В ₁, В ₂, В ₃ у розмірі відповідно 5, 3 та 2 ум. од. Визначити оптимальний план такої транспортної задачі:

ai = (10; 80; 15); bj = (75; 20; 50);

.

Варіант 2. Районне агропромислове об’єднання складається з трьох господарств А ₁, А ₂, А ₃, що спеціалізуються на вирощуванні ранніх овочів. Кожне господарство щотижня збирає відповідно 50, 30 та 20 т овочів, які необхідно відправляти в чотири магазини B ₁, B ₂, B ₃, B ₄. Магазини бажають отримувати ранні овочі в кількості відповідно 30, 30, 10 та 20 т. Вартість перевезення 1 т овочів від господарства до магазинів наведено в таблиці.

Господарство	Вартість перевезення 1 т овочів у магазини
В 1	В 2	В 3	В 4
А 1
А 2
А 3

Визначити такий план перевезення овочів до магазинів, за якого загальні витрати агропромислового об’єднання будуть найменшими.

Розв’язати задачу за умови, що вартість збереження та переробки невивезеної продукції в господарствах А ₁, А ₂ і А ₃ дорівнює відповідно 2, 4 та 1 ум. од.

Варіант 3. Розв’язати транспортну задачу:

ai = (80; 40; 60; 40); bj = (70; 60; 80);

,

якщо вартість зберігання одиниці невивезеної продукції у постачальників А ₁, А ₂, А ₃, А ₄ дорівнює відповідно 5, 4, 2 та 3 ум. од.

Варіант 4. Розв’язати транспортну задачу:

ai = (75; 40; 35; 40); bj = (20; 60; 140);

,

якщо штрафи за недопостачання продукції споживачам В ₁, В ₂, В ₃ становлять відповідно 6, 4 та 8 ум. од.

Варіант 5. Розв’язати транспортну задачу за умови, що вартість зберігання невивезеної продукції в постачальників А ₁, А ₂, А ₃ дорівнює відповідно 8, 7 та 5 ум. од. за одиницю продукції:

ai = (60; 90; 50); bj = (30; 80; 20; 40);

.

Варіант 6. Розв’язати транспортну задачу:

ai = (80; 40; 60; 40); bj = (70; 60; 80);

,

якщо незадоволений попит споживачів В ₁, В ₂, В ₃, В ₄ обкладається штрафом у розмірі відповідно 6, 7, 3 та 2 ум. од. за кожну одиницю продукції. Визначити новий оптимальний план транспортної задачі.

Варіант 7. У транспортній задачі загальний обсяг виробництва продукції перевищує загальний попит. Припустимо, що вартість зберігання одиниці продукції, яка не вивозиться від постачальників А ₁, А ₂, А ₃, А ₄, дорівнює відповідно 7, 3, 4 та 8 ум. од. Визначити оптимальний план задачі:

ai = (30; 80; 20; 40); bj = (60; 80; 20);

.

Варіант 8. У незбалансованій транспортній задачі загальний попит перевищує загальний обсяг виробництва на 10 ум. од. продукції. За недопостачання продукції споживачам умовою задачі передбачаються штрафи в розмірі 6 та 4 ум. од. за кожну одиницю продукції відповідно для першого та другого постачальників. Визначити оптимальний план такої транспортної задачі:

ai = (10; 10; 30; 20); bj = (20; 30; 20; 10);

.

Варіант 9. Визначити оптимальний план такої транспортної задачі:

ai = (10; 80; 15); bj = (75; 20; 50);

.

якщо висунуто таку вимогу: попит третього споживача має задовольнятися повністю.

 

Варіант 10. У незбалансованій транспортній задачі призначено плату за зберігання кожної одиниці невивезеної продукції від постачальників у розмірі відповідно 5, 4 та 3 ум. од.. Визначити оптимальний план задачі, якщо висунуто таку додаткову умову: уся продукція від другого постачальника має бути вивезена повністю для того, щоб звільнилося місце для нової продукції.

ai = (20; 40; 30); bj = (30; 20; 20);

.

Варіант 11. Розв’язати транспортну задачу:

ai = (20; 25; 20; 10); bj = (20; 30; 40; 15);

.

Додаткова умова: попит третього споживача задовольнити пов­ністю.

Варіант 12. Розв’язати транспортну задачу:

ai = (20; 16; 14; 22); bj = (16; 18; 12; 15);

.

Додаткова умова: ресурси четвертого постачальника використати повністю.

Варіант 13. Розв’язати транспортну задачу:

ai = (10; 8; 15; 12); bj = (15; 10; 5; 20);

.

Додаткова умова: попит першого та четвертого споживачів задовольнити повністю.

Варіант 14. Розв’язати транспортну задачу:

ai = (75; 80; 70); bj = (30; 70; 70; 35);

.

Додаткова умова: ресурси першого та третього постачальників використати повністю.

Варіант 15. У транспортній задачі визначити оптимальний план за умови повного задоволення потреб першого та другого споживачів:

ai = (100; 150; 180; 70); bj = (100; 200; 230; 80);

.

Варіант 16. Розв’язати транспортну задачу:

ai = (40; 30; 20; 40); bj = (20; 40; 30);

.

Додаткова умова: ресурси першого та другого постачальників в оптимальному плані використати повністю.

Варіант 17. Визначити оптимальний план транспортної задачі:

ai = (75; 40; 35; 40); bj = (20; 60; 180);

,

в якій потрібно повністю задовольнити попит третього споживача та неможливо виконувати перевезення за маршрутами А ₁ В ₂ та А ₃ В ₁.

Варіант 18. Знайти оптимальний план транспортної задачі:

ai = (80; 40; 60; 40); bj = (45; 65; 20; 80);

.

Додаткові умови: повністю використати ресурси четвертого постачальника та не виконувати перевезення за маршрутами А ₂ В ₃ та А ₃ В ₄.

Варіант 19. Розв’язати транспортну задачу:

ai = (5; 20; 10; 15); bj = (10; 25; 15; 5);

.

Додаткова умова: попит другого споживача задовольнити повністю та за маршрутом А ₂ В ₃ перевезти рівно 10 од. продукції.

Варіант 20. Визначити оптимальний план транспортної задачі:

ai = (10; 20; 20; 30); bj = (20; 15; 25; 10);

,

якщо ресурси четвертого постачальника потрібно використати повністю і за маршрутом А ₄ В ₃ перевезти 20 од. продукції.

 

 

Лабораторна робота № 9. Транспортна задача. Метод потенціалів розв’язування двохетапної транспортної задачі..

Питання, які виносяться на лабораторну роботу:

 

1. Економічна і математична постановка двохетапної транспортної задачі.

2. Особливості розв’язування двохетапних транспортних задач.

Завдання:

Варіант 1, 6, 11,16. Розглянути транспортну задачу, в якій необхідно перевезти деяку продукцію від постачальників А ₁, А ₂, А ₃ до споживачів В ₁, В ₂, В ₃, В ₄ через проміжні пункти D ₁, D ₂, D ₃. Запаси продукції у постачальників, попит споживачів та місткість складів відповідно a_i = (200; 220; 380), b_j = (150; 50; 350; 250), d_{i (j)}= (350; 200; 400).

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

А	D
D 1	D 2	D 3
A 1
A 2
A 3

 

D	B
B 1	B 2	B 3	B 4
D 1
D 2
D 3

 

Перевезення продукції зі складу на склад неприпустиме.

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

Варіант 2, 7, 12, 17. Розв’язати двохетапну транспортну задачу a_i =
= (400; 200; 300), b_j = (300; 200; 350; 50), d_{i (j)}= (250; 250; 500).

 

А	D
D 1	D 2	D 3
A 1
A 2
A 3

 

D	B
B 1	B 2	B 3	B 4
D 1
D 2
D 3

 

Неприпустиме перевезення продукції зі складу на склад.

Варіант 3, 8, 13, 18. Розглянути транспортну задачу з проміжними пунктами, в якій кількість складів менша за ресурси постачальників. У такій ситуації дозволене транзитне перевезення продукції безпосередньо від постачальників А ₁ та А ₂ до першого споживача. Вартість перевезення одиниці продукції за транзитними маршрутами А ₁ В ₁ та А ₂ В ₁ становить відповідно 6 та 5 ум. од.; a_i = (200; 300), b_j = (250; 100; 150), d_{i (j)}= (100; 150; 150).

 

А	D
D 1	D 2	D 3
A 1
A 2

 

D	B
B 1	B 2	B 3
D 1
D 2
D 3

 

Визначити оптимальний план поставленої задачі.

Варіант 4, 9, 14, 19. Розглянути двохетапну транспортну задачу, в якій дозволене пряме перевезення продукції від першого постачальника до споживачів В ₁, В ₂, В ₃, В ₄. Вартість перевезення одиниці продукції за транзитними маршрутами дорівнює відповідно 3, 4, 5, 3 ум. од.; a_i = (300; 200; 100), b_j = (150; 50; 200; 200), d_{i (j)}= (250; 250).

 

А	D
D 1	D 2
A 1
A 2
A 3

 

D	B
B 1	B 2	B 3	B 4
D 1
D 2

 

Варіант 5,10,15,20. Розглянути транспортну задачу з проміжними пунктами, в якій кількість складів менша за ресурси постачальників. У такій ситуації дозволене транзитне перевезення продукції безпосередньо від постачальників А ₁ та А ₂ до першого споживача. Вартість перевезення одиниці продукції за транзитними маршрутами А ₁ В ₁ та А ₂ В ₁ становить відповідно 6 та 5 ум. од.; a_i = (200; 300), b_j = (250; 100; 150), d_{i (j)}= (100; 150; 200).

 

А	D
D 1	D 2	D 3
A 1
A 2

 

D	B
B 1	B 2	B 3
D 1
D 2
D 3

 

Лабораторна робота № 9-10. Задача цілочисельного програмування. Метод Гоморі. Метод «віток і меж».

Питання, які виносяться на лабораторну роботу:

2. Економічна і математична постановка задачі цілочислового програмування. Загальний вид ЗЦП.

3. Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині

4. Методи відтинання. Метод Гоморі розв’язування ЗЦП.

5. Поняття умовно-оптимального плану ЗЦП.

6. Недоліки методу Гоморі.

7. Метод «гілок і меж» розв’язування ЗЦП.

8. Недоліки методу «гілок і меж».

 

Завдання:

1. Методом Гоморі розв’язати задачу цілочислового програмування.

1. ,	2. ,
3. ,	4. ,
5. ,	6.
7. ,	8. ,
9. ,	10. ,
11. ,	12. ,
13. ,	14. ,
15. ,	16. ,
17. ,	18. ,
19. ,	20. ,

2. Методом «гілок і меж» розв’язати задачу цілочислового програмування

1. ,	2. ,
3. ,	4. ,
5. ,	6. ,

 

Лабораторна робота № 11-12. Задача нелінійного програмування.

Питання, які виносяться на лабораторну роботу:

 

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

2. Геометрична інтерпретація задачі нелінійного програмування

3. Основні труднощі розв’язування задач нелінійного програмування

4. Класичний метод оптимізації. Метод множників Лагранжа

5. Умовний та безумовний екстремуми функції

6. Метод множників Лагранжа

7. Необхідні умови існування сідлової точки

8. Теорема Куна—Таккера

9. Опуклі й угнуті функції

10. Опукле програмування

11. Квадратичне програмування

12. Метод розв’язування задач квадратичного програмування

13. Економічна інтерпретація множників Лагранжа

14. Градієнтний метод

Завдання:

1. Розв’язати графічно задачу нелінійного програмування

51. , .
52. , .
53. , .

Лабораторна робота № 13-14. Динамічне програмування.

 

Питання, які виносяться на лабораторну роботу:

1. Економічна сутність задач динамічного програмування

2. Задача про розподіл капіталовкладень між двома підприємствами на п років.

3. Метод рекурентних співвідношень

4. Задача про розподіл капіталовкладень між підприємствами

5. Принцип оптимальності

6. Багатокроковий процес прийняття рішень

7. Приклади розв’язування задач динамічного програмування

Лабораторна робота № 15-16. Теорія ігор.

Питання, які виносяться на лабораторну роботу:

1. Основні поняття теорії ігор

2. Класифікація ігор

3. Матричні ігри двох осіб

4. Гра зі змішаними стратегіями

5. Геометрична інтерпретація гри 2 × 2

6. Зведення матричної гри до задачі лінійного програмування

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

1. Зайченко Ю.П. Дослідження операцій: Підручник. - К.: ВІПОЛ, 2000.

2. Таха X. Введение в Исследование операций. - М.: Издат. дом "Вильямс",2001.

3. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. Посіб.-К.:КНЕУ, 2003. - 452с.

4. Ржевський С.В., Александрова В.М. Дослідження операцій: Підручник. –К.: "Академвидав", 2006.- 560с.

5. Боровик О.Л., Боровик Л.В. Дослідження операцій: Навч. Посіб.-К.:Центр учбової літератури, 2007. - 424с.

6. Охріменко М.Г., Дзюбан І.Ю. Дослідження операцій. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 184с.