- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Самостійна робота №2 двоїстий симплекс-метод
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Самостійна робота №3 задача комівояжера
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Самостійна робота №4 транспортна задача за критерієм часу на перевезення
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Самостійна робота №5 детермінована задача управління запасами
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Самостійна робота №6 системи масового обслуговування з пріоритетами
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
Самостійна робота №2 двоїстий симплекс-метод
Мета заняття: вивчення алгоритму рішення задач лінійного програмування двоїстим симплекс-методом.
Стисла теоретична довідка
Алгоритм двоїстого симплекс-методу витікає з теорем двоїстості. При його застосування, у порівнянні зі звичайним симплекс-методом не висувається вимога щодо додатних значень базисних змінних у початковому опорному плані задачі, але для задачі мінімізації необхідно, щоб всі коефіцієнти при змінних цільової функції були невід’ємними. Тобто, у стовпчику С вільних членів симплекс-таблиці допустимі від’ємні значення базисних змінних, при цьому всі значення індексного рядка повинні бути невід’ємними.
Процедура двоїстого симплекс-методу полягає виконанні наступних кроків:
1) перевірка поточного опорного плану задачі на оптимальність. Якщо всі базисні змінні невід’ємні, то даний опорний план є оптимальним рішенням задачі і процес рішення припиняється. Інакше виконують крок 2;
2) знаходження змінної для виключення з базису. Відшукують найменшу від’ємну базисну змінну. Рядок, що відповідає цій змінній називається провідним рядком, а базисна змінна, що відповідає цьому рядку, у наступному опорному плані задачі стане небазисною;
3) знаходження змінної для включення до базису. У провідному рядку відшукують від’ємні значення. Якщо не знайдено жодного від’ємного значення, то не існує жодного допустимого плану задачі і рішення припиняється. Якщо від’ємних значень декілька, то вибирається стовпчик, у якому досягається найменше за абсолютною величиною відношення числа з індексного рядка до цих значень. Знайдений таким чином стовпчик називається провідним стовпчиком, а вільна змінна, що відповідає цьому стовпчику, у наступному опорному плані стане базисною. На перетині провідного рядка та провідного стовпчика знаходиться провідний елемент.
4) побудова нового опорного плану задачі. Виконується аналогічно симплекс-перетворенням звичайного симплекс-методу.
Зміст практичного заняття та вихідні дані до його виконання
Для перевезення вантажів за трьома маршрутами (І–ІІІ) автотранспортне підприємство може використати чотири типи автомобілів (ГАЗ-53, ЗІЛ-4315, КАМАЗ-5320, КАМАЗ-53212). Мінімальний змінний обсяг перевезення вантажів на маршрутах, продуктивність транспортних засобів та витрати на експлуатацію автомобілів кожного типу наведені у таблиці 2.1.
Таблиця 2.1 – Вихідні дані до виконання завдання 2
Маршрут |
Змінна продуктивність автомобіля на перевезеннях, т |
Змінний обсяг перевезень, т |
|||
ГАЗ-53 |
ЗІЛ-4315 |
КАМАЗ-5320 |
КАМАЗ-53212 |
||
І |
p11 |
p12 |
p13 |
p14 |
250 |
ІІ |
p21 |
p22 |
p23 |
p24 |
120 |
ІІІ |
p31 |
p32 |
p33 |
p34 |
175 |
Змінні витрати на експлуатацію автомобіля, грн. |
175 |
210 |
250 |
275 |
|
Визначити, яку кількість автомобілів кожного типу необхідно використати на перевезеннях з метою досягнення мінімальних сумарних витрат на зміну експлуатацію рухомого складу. Вважати, що парк автомобілів достатній для виконання перевезень.
Вихідні дані для виконання роботи по варіантах наведені у таблиці 2.2.
Таблиця 2.2 – Вихідні дані до виконання самостійної роботи 2
Вар. |
p11 |
p12 |
p13 |
p14 |
p21 |
p22 |
p23 |
p24 |
p31 |
p32 |
p33 |
p34 |
1 |
16 |
20 |
25 |
35 |
10 |
12 |
14 |
15 |
14 |
15 |
18 |
25 |
2 |
11 |
15 |
16 |
18 |
5 |
8 |
10 |
12 |
6 |
9 |
11 |
14 |
3 |
20 |
24 |
30 |
32 |
10 |
16 |
18 |
20 |
12 |
15 |
18 |
24 |
4 |
24 |
24 |
25 |
27 |
15 |
16 |
17 |
22 |
14 |
15 |
16 |
26 |
5 |
8 |
15 |
27 |
34 |
9 |
12 |
15 |
16 |
10 |
14 |
15 |
18 |
6 |
22 |
25 |
34 |
34 |
11 |
12 |
14 |
15 |
15 |
19 |
20 |
21 |
7 |
25 |
28 |
32 |
32 |
14 |
14 |
15 |
20 |
14 |
15 |
20 |
25 |
8 |
15 |
24 |
30 |
32 |
10 |
11 |
12 |
16 |
14 |
16 |
22 |
26 |
9 |
24 |
28 |
35 |
38 |
14 |
18 |
20 |
20 |
16 |
18 |
24 |
30 |
10 |
20 |
24 |
25 |
27 |
10 |
16 |
17 |
20 |
12 |
15 |
16 |
22 |
11 |
14 |
22 |
24 |
26 |
8 |
10 |
20 |
22 |
20 |
20 |
25 |
26 |
12 |
10 |
20 |
25 |
27 |
11 |
12 |
16 |
21 |
12 |
15 |
16 |
20 |
13 |
12 |
16 |
24 |
25 |
10 |
14 |
15 |
20 |
11 |
12 |
14 |
22 |
14 |
14 |
28 |
32 |
35 |
10 |
15 |
18 |
24 |
14 |
16 |
22 |
26 |
15 |
22 |
25 |
34 |
35 |
11 |
12 |
14 |
16 |
15 |
19 |
20 |
24 |
16 |
10 |
15 |
27 |
34 |
10 |
12 |
15 |
16 |
12 |
14 |
15 |
18 |
Продовження таблиці 2.2
Вар. |
p11 |
p12 |
p13 |
p14 |
p21 |
p22 |
p23 |
p24 |
p31 |
p32 |
p33 |
p34 |
17 |
16 |
20 |
22 |
25 |
8 |
10 |
14 |
18 |
10 |
12 |
15 |
20 |
18 |
11 |
13 |
15 |
20 |
7 |
9 |
13 |
15 |
8 |
11 |
12 |
13 |
19 |
12 |
14 |
17 |
24 |
8 |
12 |
14 |
14 |
9 |
12 |
15 |
16 |
20 |
22 |
24 |
25 |
27 |
9 |
20 |
32 |
34 |
7 |
10 |
15 |
20 |
21 |
15 |
24 |
38 |
42 |
14 |
15 |
15 |
16 |
18 |
20 |
22 |
32 |
22 |
14 |
15 |
20 |
22 |
8 |
15 |
15 |
18 |
9 |
12 |
12 |
15 |
23 |
22 |
24 |
32 |
34 |
11 |
14 |
15 |
16 |
15 |
19 |
20 |
21 |
24 |
22 |
25 |
34 |
35 |
11 |
12 |
15 |
16 |
15 |
19 |
24 |
24 |
25 |
12 |
12 |
14 |
16 |
10 |
14 |
15 |
18 |
8 |
11 |
12 |
15 |
26 |
8 |
12 |
15 |
26 |
15 |
16 |
16 |
22 |
9 |
11 |
14 |
15 |
27 |
26 |
30 |
35 |
45 |
14 |
15 |
17 |
20 |
15 |
20 |
22 |
32 |
28 |
11 |
12 |
15 |
18 |
15 |
16 |
16 |
22 |
5 |
9 |
10 |
11 |
29 |
22 |
25 |
32 |
34 |
11 |
12 |
14 |
15 |
15 |
19 |
20 |
21 |
30 |
14 |
15 |
21 |
25 |
10 |
12 |
15 |
18 |
9 |
12 |
14 |
15 |