- •5. Транспортна задача лiнiйного програмування
- •5.1. Змiстовна постановка та формальна модель транспортної задачi лiнiйного програмування
- •5.2. Умова iснування розв’язку транспортної задачі лінійного програмування
- •5.3. Побудова формальної моделi транспортної задачі лінійного програмування при порушеннi умов балансу в змiстовiй постановцi
- •5.4. Векторна форма запису транспортної задачі лінійного програмування
- •5.5. Метод потенцiалiв
- •5.5.1. Загальна схема алгоритму
- •5.5.2. Методи побудови початкового допустимого базисного розв’язку
- •Крок 3.
- •5.5.4. Знаходження змінної, що виводиться з базису (побудова циклу)
- •5.5.5. Перехiд до нового допустимого базисного розв’язку
- •5.5.6. Схема методу потенціалiв
- •5.6. Приклад розв’язання транспортної задачi лiнiйного програмування
- •5.7. Приклади компенсаторних циклiв
- •5.8. Зіставлення методу потенціалів I симплекс-методу
- •Задачi для самостійної роботи
- •Контрольнi запитання
- •Завдання до контрольної роботи
- •Двоїстий симплекс-метод
- •6.1. Основні теоретичні положення
- •6.2. Схема двоїстого симплекс-методу для задачі максимізації цільової функції
- •6.3. Сфера застосування двоїстого симплекс-методу
- •6.4. Приклад застосування двоїстого симплекс-методу
- •6.5. Додавання нового обмеження
- •Завдання до самостійної роботи
- •Варіанти завдань
- •Контрольні завдання
- •Список літератури
5.7. Приклади компенсаторних циклiв
Iснують випадки, коли компенсаторний цикл набуває досить складного вигляду, як показано в табл. 5.23 — 5.24.
Таблиця 5.23
-
v1=3
v2=5
v3=4
v4=6
v5=2
4
5
4
6
0
u1=0
2
2
1
x15
5
-1
¾
2
Å
Ü
1
4
8
7
0
u2=-2
2
4
6
Å
-1
-6
-3
¾
9
8
10
7
4
u3=1
5
5
-5
-2
-5
-1
2
10
3
11
5
u4=-1
1
13
14
¾
-6
Å
-6
-4
3
2
15
6
4
Таблиця 5.24
-
4
5
0
1
2
¾
4
Å
5
0
5
8
0
3
2
6
11
-4
-6
9
9
5
¾
3
Å
3
2
4
4
-3
-2
-3
1
Ü
Å
3
5
6
4
¾
1
-1
1
2
3
-1
-7
-4
Þ
6
¾
6
5
Å
2
4
1
6
3
9
-1
-4
-1
4
8
6
7
2
Компенсаторний цикл для будь-якої вiльної клiтини визначається за допомогою методу викреслювань. Розглянемо його на прикладi (рис. 5.1). Нехай маємо транспортну таблицю, в якiй через x позначено базиснi змiннi. Будемо послiдовно викреслювати тi рядки та стовпчики, де є тiльки одна базисна змiнна (заповнена клiтина). Клiтина, де знаходиться змiнна, що вводиться у базис, вважається заповненою. У даному випадку – це клiтина (3,6).
X |
|
|
X |
|
|
|
|
X |
|
|
X |
|
|
|
|
X |
|
|
X |
|
|
|
|
X |
|
X |
|
|
|
|
|
X |
|
X |
|
|
|
|
|
X |
|
X |
|
|
X |
|
|
|
|
X |
|
|
X |
|
|
|
|
|
|
|
X |
|
|
|
|
|
|
|
X |
|
|
|
|
|
|
|
X |
|
|
|
|
|
|
|
X |
|
|
|
X |
X |
X |
|
|
|
|
|
X |
X |
X |
|
|
|
|
|
X |
X |
X |
|
|
|
|
|
|
X |
X |
|
|
|
|
|
|
X |
X |
|
|
|
|
|
|
X |
X |
Рис. 5.1
Викреслюємо стовпчик 1, рядок 1, рядок 4, стовпчик 4. Змiннi, що залишилися невикресленими, входять до компенсаторного циклу, на зламах якого знаходяться невикреслені базисні змiнні та небазисна змiнна, що вводиться. У даному випадку – це цикл x36 x32 x52 x53 x23 x25 x65 x66 x32.