Початкове опорне рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X1, X2, X3, X4, X5, X6 відповідають негативні значення Дj = -1. Для знаходження провідною виявимо максимальний по модулю негативний вільний член bi = -12. Провідна рядок - X11. У рядку X11 так само знайдемо максимальний по модулю негативний вільний член, рівний -1. Стовпець X5 - ведучий. Вибираємо базисну змінну, яку потрібно вивести з базису - (-1), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця. Відповідно Х11 виводимо з базису.
Заповнюємо рядок змінної Х5, для цього записуємо в неї елементи рядка Х11 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х5 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х5 нулі, крім 1 в новому рядку (Таблиця 3):
Таблиця 3
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X7 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | -4 |
| 0 | X8 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -8 |
| 0 | X9 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | -10 |
| 0 | X10 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | -7 |
| 1 | X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 12 |
| 0 | X12 | 0 | 0 | 0 | 1 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 8 |
| Дj | -1 | -1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 0 | 12 | |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X1, X2, X3, X4, X6 відповідають негативні значення Дj = -1.Для знаходження провідною виявимо максимальний по модулю негативний вільний член (-10). Провідна рядок - X9. У рядку X9 так само знайдемо максимальний по модулю негативний вільний член (-1), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця, тому X9 виводимо з базису. Стовпець X3 - ведучий.
Заповнюємо рядок змінної Х9, для цього записуємо в неї елементи рядка Х3 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х9 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х3 нулі (Таблиця 4):
Таблиця 4
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X7 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | -4 |
| 0 | X8 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -8 |
| 1 | X3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 10 |
| 0 | X10 | 0 | 1 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 3 |
| 1 | X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 12 |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X1, X6, X11 відповідають негативні значення Дj = -1. Провідна рядок - X12. У стовпці X6 так само знайдемо максимальний по модулю негативний вільний член (-1), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця, тому рядок X12 виводимо з базису. Стовпець X6 - ведучий. Заповнюємо рядок змінної Х6, для цього записуємо в неї елементи рядка Х12 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х12 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х6 нулі. Будуємо нову симплекс-таблицю (Таблиця 5):
Таблиця 5
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X7 | -1 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | -1 | -12 |
| 0 | X8 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -8 |
| 1 | X3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 10 |
| 0 | X10 | 0 | 1 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 3 |
| 1 | X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 12 |
| 1 | X6 | 0 | 0 | 0 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | -1 | -8 |
| Дj | -1 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | -1 | 0 | 14 | |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X1, X4, X6, X11 відповідають негативні значення Дj = -1. Провідна рядок - X10, в ній знайдемо максимальний по модулю негативний вільний член (-1), він є що дозволяє елементом, так як знаходиться на перетині провідного рядка і стовпця. Стовпець X4 - ведучий. Заповнюємо рядок змінної Х4, для цього записуємо в неї елементи рядка Х10 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х10 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х4 нулі. Перерахуємо таблицю (Таблиця 6):
Таблиця 6
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X7 | -1 | -1 | 0 | 0 | 0 | -1 | 1 | 0 | 1 | -1 | 1 | -1 | -15 |
| 0 | X8 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -8 |
| 1 | X3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 10 |
| 1 | X4 | 1 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | -3 |
| 1 | X5 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 15 |
| 1 | X6 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | -1 | 1 | -1 | -11 |
| Дj | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -2 | 0 | 0 | 11 | |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X1, X10 відповідають негативні значення Дj. Провідна рядок - X8. У стовпці X2 так само знайдемо максимальний по модулю негативний вільний член (-2), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця, тому рядок X8 виводимо з базису. Стовпець X2 - ведучий. Заповнюємо рядок змінної Х8, для цього записуємо в неї елементи рядка Х2 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х2 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х8 нулі (Таблиця 7):
Таблиця 7
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | 1 | -1 | 1 | -1 | -7 |
| 1 | X2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 8 |
| 1 | X3 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 |
| 1 | X4 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | -1 | 1 | -1 | 0 | 0 | 5 |
| 1 | X5 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 7 |
| 1 | X6 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | -1 | 1 | -1 | 1 | -1 | -3 |
| Дj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 2 | -2 | 0 | -1 | 19 | |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, векторах X8, X10, X12 відповідають негативні значення Дj. Провідна рядок - X7. У стовпці X10 так само знайдемо максимальний по модулю негативний вільний член (-1), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця, тому рядок X7 виводимо з базису. Стовпець X10 - ведучий. Заповнюємо рядок змінної Х10, для цього записуємо в неї елементи рядка Х7 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х7 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х10 нулі (Таблиця 8):
Таблиця 8
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X10 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | -1 | 1 | -1 | 1 | 7 |
| 1 | X2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 8 |
| 1 | X3 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 |
| 1 | X4 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 12 |
| 1 | X5 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 7 |
| 1 | X6 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 4 |
| Дj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 33 | |
Дане рішення не є оптимальним, тому що в розглянутій задачі на мінімум, вектору X11 відповідає від'ємне значення Дj = -1. Провідна рядок - X5. У стовпці X11 знайдемо максимальний по модулю негативний вільний член (-1), що дозволяє елемент, так як знаходиться на перетині провідного рядка і стовпця, тому рядок X5 виводимо з базису. Стовпець X11 - ведучий. Заповнюємо рядок змінної Х11, для цього записуємо в неї елементи рядка Х5 поділені на дозволяючий елемент.
Після заповнюємо залишилися рядки. Для цього рядок Х11 послідовно множимо на такі числа, щоб після складання її з кожним рядком таблиці отримати в стовпці Х5 нулі. Будуємо підсумкову симплекс-таблицю (Таблиця 9):
Таблиця 9
| Ci | БП | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | Z(x) |
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | bi | | |
| 0 | X10 | 1 | 0 | 0 | 0 | -1 | 0 | -1 | 0 | -1 | 1 | 0 | 1 | -6 |
| 1 | X2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 8 |
| 1 | X3 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 |
| 1 | X4 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 12 |
| 0 | X11 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -7 |
| 1 | X6 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 4 |
| Дj | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 26 | |
5) Висновок: Так як Дj = 0, то дане рішення оптимально. У рядку Z немає негативних елементів, отже, знайдено оптимальне рішення Z = 26 при значеннях змінних рівних:
X2=8, X3=2, X4=12, X6=4.
Z(X) = 1*8 + 1*2 + 1*12 + 1*4 = 26
Відповідь: зниження інтенсивності внутрішньоміського руху буде досягнуто, якщо в другу зміну додати 8 автобусів, в третю - 2, в четверту - 12, а в шосту - 4 автобуси. Загальна кількість автобусів одно 26.
1 2