Помножимо другу нерівність на (– 1) і введемо додаткові змінні.
Початковий базис: вектори А4 та А5.
Псевдоплан: .
- тому виведемо вектор А5 і змінну х5.
Введемо – на основі розрахунку значення :
, = ввести вектор А1. Розв’язувальним елементом буде а21 (–1).
Оптимальний план початкової задачі:
,
та оптимальний план двоїстої задачі:
, .
3. Метод відтинаючих площин (метод Гоморі)
варіанти:
1. Перший алгоритм Гоморі для рішення повністю цілочисельних задач.
2. Другий алгоритм Гоморі для рішення частково цілочисельних задач.
Ідея розрахунків методом відтинаючих площин для розв’язання повністю цілочисельних задач (1-й метод Гоморі) полягає у такому підході:
1) лінійна задача (1)
(1)
Опорний план, який має канонічний вигляд:
(2)
2) якщо серед рівнянь-обмежень (2) є дробові значення базисних змінних xi = bi, то обирають серед них таке значення, яке має найбільшу дробову частину. Це рівняння
Перетворюють у додаткову нерівність:
(3)
Правила обрання чисел [aij] та [bi]:
1. Якщо дробові числа aij або bi є додатними числами, то [aij] та [bi] є цілими додатними числами і дорівнюють цілій частині числа aij або bi. Наприклад:
2. Якщо дрібне число aij або bi є від’ємним числом, то [aij] та [bi] є від’ємним цілим числом, яке за абсолютним значенням на “1” більше за абсолютне значення цілої частини числа aij або bi. Наприклад:
Якщо aij або bi є цілими числами, то αij =0, βi =0.
3. Додаткова нерівність (3) має лише додатні коефіцієнти. Вона множенням на «-1» спочатку приводиться до вигляду, який повинна мати нерівність у симплекс-методі згідно зі стандартною формою () , а потім за допомогою додаткової змінної перетворюється у рівняння , яке додається до оптимального опорного плану – системи (2) і разом із ним створює псевдоплан (має одне від’ємне значення ).
Якщо в новому оптимальному опорному плані існують базисні змінні , які мають дробові значення, то знов додають одне додаткове обмеження, і процес розрахунків повторюється до отримання цілочисельних значень базисних змінних.
Ознакою відсутності розв’язку задачі є наявність у таблиці хоча б одного рядка з цілими величинами aij та вільним дробовим членом bi, що вказує на відсутність розв’язку в цілих числах (наприклад, ) .
Часткові цілочислові задачі (в них вимоги щодо цілочисельності ставляться лише до окремих змінних) розв’язуються так само, як попередні, за рахунок введення додаткового обмеження