- •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.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
u1=0
10
x13
10
¾
7
+14
Å
9
2
8
1
5
u2=-2
4
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
x23
14
¾
+13
Å
2
7
3
9
2
u3=7
10
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=-1
14
0
14
¾
-13
Å
-11
7
3
9
2
u3=7
X31
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=-2
4
10
0
14
¾
Å
-11
7
3
9
2
u3=6
x32
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=-2
4
10
14
¾
-13
Å
-11
7
3
9
2
u3=6
x31
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=0
10
x13
10
¾
-3
+1
Å
-1
2
8
1
5
u2=-2
4
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 |