овпець X (вільні члени B i ≥ 0) з підсумовуванням дає значення L (X); аналогічне множення його на стовпець X k дасть Z k ). Останній рядок виходить вирахуванням з попередньої рядка елементів першого рядка таблиці і дозволяє судити про оптимальності плану.
Т.к. вибір типу шуканого екстремуму (максимуму або мінімуму) носить відносний характер, то при вирішенні завдань максимізації/мінімізації в останньому рядку повинні бути тільки невід'ємні елементи.
Звернемо увагу на визначення початкового опорного плану. Нехай задача приведена до канонічної формі та компоненти вектора правої частини ненегативні. Якщо в системі векторів коефіцієнтів при змінних (матриці А) виявляється підсистема, що утворює одиничну підматрицю, то ці вектори утворюють базис опорного плану і вектор правій частині визначає базисні компоненти цього плану.
Якщо такий одиничної підматриці не виявляється, то або доведеться перебирати всі підсистеми m рівнянь з m невідомими в надії виявити невід'ємні рішення, або вдатися до методу штучного базису.
В останньому випадку в обмеження додають невід'ємні, т.зв. штучні змінні так, щоб виникла одинична подматріца коефіцієнтів, і ці змінні включають в лінійну форму з коефіцієнтом - М для задачі максимізації, де М > 0 - як завгодно велике число. p> Отримана М-задача вирішується до отримання оптимального плану.
Якщо в оптимальному плані М-задачі значення штучних змінних дорівнюють нулю, то значення інших компонент утворюють оптимальний план вихідної задачі .
Якщо в оптимальному плані М-задачі значення хоча б однієї з штучних змінних відмінно від нуля, то вихідна задача не має жодного плану (її обмеження суперечливі).
Якщо деяка задача вирішується прямим алгоритмом симплексного методу, то рішення пов'язаною завдання можна бачити в рядку Z кінцевої симплексной таблиці в позиціях, відповідних початкового одиничного базису.
В
3. МЕТОД Гомори [1]
При вирішенні багатьох завдань (Планування дрібносерійного виробництва, розподіл кораблів по коліях повідомлення, вироблення суджень типу "так-ні" і т.п.) нецілочисельне рішення не має сенсу. Спроба тривіального округлення до цілих значень призводить або до порушення обмежень задачі, або до недовикористання ресурсів. Як ми мали можливість переконатися, для довільної лінійної програми (за винятком програм типу класичної транспортної задачі, де коефіцієнти матриці обмежень рівні 1 або 0) гарантувати цілочисельність рішення неможливо.
У разі двомірної завдання проблема вирішується відносно просто шляхом виявлення всіх цілочисельних точок, близьких до границі безлічі планів, побудови опуклого безлічі планів, яке містить всі цілочисельні плани і рішення задачі над цим безліччю.
B загальному випадку висувається ідея послідовного відсікання нецілочисельне оптимальних планів : звичайним симплексним методом відшукуєтьс...
