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