5.6. Приклад розв’язання транспортної задачi лiнiйного програмування
Розв’язати ТЗЛП, наведену в табл. 5.11.
Таблиця 5.11
-
4
3
2
0
10
2
8
1
5
14
7
3
9
2
16
14
10
10
6
Покажемо, що якщо на деякому етапі побудови ДБР будемо мати альтернативу: "що викреслити – стовпчик чи рядок?" (випадок отримання виродженого базисного розв’язку), то не має значення, яку альтернативу обирати. На значення оптимального розв’язку це не вплине.
У цій задачі умова балансу виконується, тому вводити фіктивні пункти не треба.
Оскільки
у вихідній задачі
,
то при знаходженні початкового розв’язку
методом північно-західного кута одержимо
вироджений розв’язок. Тобто на ітерації
3 побудови ДБР будемо мати альтернативу:
"що викреслити – стовпчик чи рядок?"
У табл. 5.12 подано початковий
розв’язок, що відповідає випадку, коли
після визначення значення змінної
викреслюється другий рядок.
Таблиця 5.12
-
4
3
2
0
10
10
¾
2
8
1
5
4
10
14
10
¾
7
3
9
2
0
10
6
16
16
6
¾
14
10
10
6
4
0
¾
¾
¾
¾
Сумарні витрати за таким
планом перевезень складають:
У
табл. 5.13 наведено початковий розв’язок,
що відповідає випадку, коли після
визначення значення змінної
викреслюється другий стовпчик.
Таблиця 5.13
-
4
3
2
0
10
10
¾
2
8
1
5
4
10
0
14
10
0
¾
7
3
9
2
10
6
16
6
¾
14
10
10
6
4
10
¾
¾
¾
¾
Сумарні витрати за таким
планом перевезень складають:
Спочатку знайдемо оптимальний розв’язок вихідної задачі, відштовхуючись від початкового розв’язку (табл. 5.11). Для нього шукаємо потенціали і за ними – відносні оцінки небазисних змінних (табл. 5.14).
Таблиця 5.14
-
v1=4
v2=10
v3=16 ß
v4=9
Ü
4
3
2
0
u
1=010
x13
10
¾
7
+14
Å
9
2
8
1
5
u
2=-24
10
14
Å
¾
13
2
7
3
9
2
u3=-7
0
10
6
16
-10
Å
¾
14
10
10
6
Небазисна змінна x13,
що має найбільшу додатну оцінку d13=14,
увійде до складу базисних. З аналізу
компенсаторного циклу, що відповідає
x13,
,
випливає, що з базису повинна бути
вилучена одна з трьох змінних, бо
.
У цьому випадку все одно, яку змінну
виводити з базису. Хай це буде змінна
.
У
табл. 5.15 представлено черговий
базисний розв’язок. Сумарні витрати
складають:
.
Оскільки
,
то розв’язок не оптимальний. Відповідну
змінну будемо вводити до базису.
Таблиця 5.15
-
v1=-10
v2=-4
v3=2
v4=-5
4
3
2
0
u1=0
10
10
-14
-7
-5
2
8
1
5
u2=12
14
0
x
2314
¾
+13
Å
2
7
3
9
2
u
3=710
0
6
16
-10
Å
¾
14
10
10
6
Для змінної, що вводиться до
базису x23,
побудуємо компенсаторний цикл:
.
З аналізу циклу випливає, що з базису
може бути вилучена одна з двох змінних.
Нехай це буде змінна
У табл. 5.16 подано новий базисний розв’язок. Сумарні витрати на перевезення складають ті самі 90 од. вартості.
Таблиця 5.16
-
v1=3
v2=-4
v3=2
v4=-5
4
3
2
0
u1=0
10
10
-1
-7
-5
2
8
1
5
u2=-114
0
14
¾
-13
Å
-11
7
3
9
2
u3=7X31
10
0
6
16
+3
Å
¾
14 Ý
10
10
6
Оскільки
,
то розв’язок не оптимальний. Для змінної,
що вводиться до базисуx31,
побудуємо компенсаторний цикл:
.
Оскільки
,
то з базису вилучається змінна
.
У
табл. 5.17 наведено новий базисний
розв’язок. Сумарні витрати складають:
Таблиця 5.17
-
v1=3
v2=-1
v3=2
v4=-2
4
3
2
0
u1=0
10
10
-1
-4
-2
2
8
1
5
u2=-1
14
0
14
-10
-8
7
3
9
2
u3=4
0
10
6
16
-3
14
10
10
6
Оскільки відносні оцінки всіх небазисних змінних недодатні, розв’язок оптимальний.
Тепер знайдемо оптимальний розв’язок вихідної задачі, спираючись на початковий розв’язок з табл. 5.12. Для нього шукаємо потенціали і за ними – відносні оцінки небазисних змінних (табл. 5.18).
Таблиця 5.18
-
v1=4
v2=10
v3=3
v4=-4
4
3
2
0
u1=0
10
10
7
1
-4
2
8
1
5
u2=-24
10
0
14
¾
Å
-11
7
3
9
2
u3=6x32
10
6
16
3
+13
Å
¾
14
10 Ý
10
6
Оскільки
,
то розв’язок не оптимальний. Для змінної
x32,
що вводиться до базису, побудуємо
компенсаторний цикл:
.
З аналізу циклу випливає, що з базису
може бути вилучена одна з двох змінних.
Нехай це буде змінна
:
Табл. 5.19
містить базисний розв’язок. Сумарні
витрати на перевезення складають:
Оскільки
,
то розв’язок не оптимальний. Для змінноїx31
, що вводиться до базису, побудуємо
компенсаторний цикл:
Замкнений цикл вказує на те, що з базису
вилучається змінна
Таблиця 5.19
-
v1=4
v2=-3
v3=3
v4=-4
4
3
2
0
u1=0
10
10
-6
1
-4
2
8
1
5
u2=-24
10
14
¾
-13
Å
-11
7
3
9
2
u3=6x31
10
0
6
16
+3
Å
¾
14 Ý
10
10
6
Табл. 5.20 містить черговий
базисний розв’язок, сумарні витрати
якого дорівнюють:
Таблиця 5.20
-
v1=4
v2=0
ßv3=3
v4=-1
4
3
2
0
u1=010
x13
10
¾
-3
+1
Å
-1
2
8
1
5
u2=-24
10
14
Å
-10
¾
-8
7
3
9
2
u3=3
0
10
6
16
-3
14
10
10
6
Оскільки
,
то розв’язок не оптимальний. Для змінноїx13,
що вводиться до базису, побудуємо
компенсаторний цикл:
З аналізу циклу випливає, що з базису
може бути вилучена одна з двох змінних.
Нехай це буде змінна
:
Табл. 5.18 містить черговий базисний розв’язок. Йому відповідають сумарні транспортні витрати:
Таблиця 5.21
-
v1=3
v2=-1
v3=2
v4=-2
4
3
2
0
u1=0
10
10
-1
-4
-2
2
8
1
5
u2=-1
14
0
14
-10
-8
7
3
9
2
u3=4
0
10
6
16
-3
14
10
10
6
Оскільки відносні оцінки всіх небазисних змінних недодатні, розв’язок оптимальний. Відзначимо, що цей розв’язок збігається з розв’язком табл. 5.16.
Отже, оптимальний план перевезень буде таким, як наведено в табл. 5.22.
Таблиця 5.22
|
Пункт виробництва |
Пункт споживання |
Обсяг перевезення |
Вартість перевезення |
|
1 |
3 |
10 |
20 |
|
2 |
1 |
14 |
28 |
|
3 |
2 |
10 |
30 |
|
3 |
3 |
6 |
12 |
|
Усього |
40 |
90 | |