як твір-го рядка зворотної матриці з основної таблиці на стовпець допоміжної таблиці. Отримані значення занести в стовпець основний симплекс-таблиці. p> Крок 7. Визначити вектор, виведений з базису. Для цього необхідно заповнити стовпець основної таблиці значеннями шляхом ділення елементів стовпця основної таблиці на відповідні їм за номером елементи стовпця основної таблиці. p> Якщо все, то вихідна задача нерозв'язна в силу необмеженості зверху лінійної форми. На цьому процес вирішення ЗЛП завершується. p> Якщо, то необхідно вибрати. Нехай ним виявився елемент з номером, тобто . Тоді відповідний цим індексом вектор повинен виводитися з базису. Елемент є В«дозволенимВ». На цьому нульова ітерація завершена і належить приступити до виконання наступної ітерації. p> Крок 8. Для заповнення нової основної таблиці обчислити за рекурентним формулами нові значення параметрів ітерації. p> Заповнити-тую рядок нової основної таблиці елементами,, виходить розподілом відповідних елементів ()-того рядка старої основної таблиці на дозволяючий елемент, тобто за формулами.
Всі інші-ті рядки головної частини нової основної симплекс-таблиці отримати як результат вирахування з-того рядка старої основний симплекс-таблиці-того рядка нової симплекс-таблиці, помноженої на відповідний-тий елемент дозволяє стовпця старої основний симплекс-таблиці, тобто відповідно до рекурентними формулами. З аналогічних формулами можуть бути обчислені також і елементи-й рядки:. p> Описаний процес побудови симплекс-таблиць повторюється до отримання оптимального опорного плану або до встановлення необмеженості лінійної форми, тобто нерозв'язності ЗЛП.
Про кінцівки симплекс - методу
Нехай ЗЛП є невиродженому. Тоді на кожному кроці симплекс - методу будемо мати. Процес розрахунку буде полягати в переході
,
де два сусідніх базису відрізняються лише одним вектором. Наприклад, перехід від до здійснено введенням вектора. При цьому лінійна форма зміниться так:
,
тому і.
Таким чином, при переході від одного опорного плану до іншого у невиродженому завданню лінійна форма зростає. Тому неможливий повернення до старого опорному плану, тобто кожен крок симплекс - методу призводить до нового, раніше не зустрічалася, опорного плану. І оскільки число опорних планів (вершин багатогранного безлічі) звичайно, те у невиродженому завданню через кінцеве число кроків або встановлюється необмеженість лінійної форми, або виходить оптимальний план. p> Нехай ЗЛП є виродженою. Тоді у виродженого опорного плану може бути (але не обов'язково) і тому може бути. p> Чи не призведе це до нескінченного числа кроків? У силу кінцівки числа вершин безлічі це може бути лише тоді, коли через кілька кроків ми повернемося до вихідного базису. Отже, повинні зустрічатися ланцюжка
В
в яких початкове і кінцеве ланки збігаються, тобто . Такі ланцюжки називаються циклами. Для них. А...
