аблиці записано рішення ЗЛП, а саме, значення базисних компонент оптимального опорного плану і відповідне йому максимальне значення лінійної форми. На цьому процес вирішення ЗЛП завершується. p> Якщо хоча б в одному стовпці з негативною оцінкою всі елементи менше або дорівнюють 0, то лінійна форма не обмежена зверху і рішення ЗЛП не існує. На цьому процес вирішення ЗЛП також завершується. p> Якщо ж у кожному стовпці з негативними оцінками знайдеться хоча б один позитивний елемент, то для побудови нового опорного плану необхідно знайти вектор, який буде вводитися в базис. Він визначається за номером найменшою негативної оцінки і, таким чином, визначається дозволяє стовпець. p> Крок 5. Визначити вектор, якого виключають, з базису для чого необхідно заповнити останній стовпець t симплекс-таблиці нульової ітерації шляхом ділення елементів стовпця на відповідні їм за номером позитивні елементи дозволяє стовпця, тобто br/>
,
При цьому, у рядках стовпчика, відповідних непозитивним елементам, записуємо, не виконуючи ділення.
Далі необхідно вибрати. Якщо досягається на декількох позиціях стовпця, то з базису може бути виключений будь-який з векторів. Для визначеності, договоримся виключати з них вектор з найменшим номером. p> Нехай вийшов на-тій позиції, тобто , Тоді відповідний цим індексом вектор повинен виводитися з базису. Рядок симплекс-таблиці, відповідна цим індексом, називається роздільною рядком. Елемент, що стоїть на перетині роздільної рядки і дозволяє стовпця називається що дозволяє елементом. На цьому нульова ітерація завершена і належить приступити до виконання наступної ітерації. p> Крок 6. Заповнити нову симплекс-таблицю в наступній послідовності. p> На-тих позиціях стовпців і записати відповідно і, а на інших позиціях цих стовпців залишити колишні елементи.
Заповнити-тую рядок нової симплекс-таблиці елементами, виходить розподілом відповідних елементів ()-того рядка старої симплекс-таблиці на дозволяючий елемент, тобто за формулами
В
Всі інші-ті рядки головної частини нової симплекс-таблиці отримати як результат вирахування з-того рядка старої симплекс-таблиці-того рядка нової симплекс-таблиці, помноженої на відповідний-тий елемент дозволяє стовпця, тобто відповідно до рекурентними формулами,. З аналогічних формулами обчислюються також і елементи-го рядка нової таблиці:,,. p> Цим завершується побудова нової симплекс-таблиці.
Описаний процес побудови симплекс-таблиць повторюється до отримання оптимального опорного плану або до встановлення необмеженості лінійної форми, тобто нерозв'язності ЗЛП.
Якщо серед оцінок небазисних векторів умов щодо базису знайденого оптимального опорного плану знайдеться хоча б одна рівна нулю, то це означає, що ЗЛП має неєдиний рішення.
Алгоритм зворотної матриці
Опишемо алгоритм стосовно до вирішення ЗЛП, записаної в канонічній формі з односторонніми обмеженнями:
В
Не...
