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