Page 27 - 4729

- пошук опорного рішення ;

- пошук оптимального рішення.
Якщо обмеження задачі ЛП вміщують одиничну матрицю порядна m ( m —

кількість рівнянь-обмежень) і всі вільні члени невід’ємні то опорний план
задачі відомий, необхідно переходити до визначення оптимального плану.

Розв’язок задач симплекс методом починається із аналізу індексного рядка

— значень коефіцієнтів функції. Якщо всі значення ,n , то

одержаний план оптимальний.

Якщо серед коефіцієнтів , є додатні, і якщо їх декілька, то вибирають

найбільший — таким чином визначили провідний стовбчик. Далі визначають

яку із базисних змінних необхідно вивести із базису. Ця змінна, яка

знаходиться на перетині провідного рядка і провідного стовбняка, називається

провідним елементом.

Провідний елемент шукають із умови

(3.3)

Обчислюються коефіцієнти нової симплекс-таблиці користуючись правилами :

- Провідний елемент замінили інверсним значенням ;

- Елементи провідного рядка (крім провідного елемента) поділити на провідний

елемент;

- Елементи провідного стовпчика (крім провідного елемента) поділити на

провідний елемент і частку взяти із протилежним знаком;

Решту елементів таблиці визначають за правилом прямокутника. Для

цього в початковій таблиці виділяється прямокутник, вершинами якого є

елементи, які беруть участь в обчисленнях. Діагональ, що утримує провідний

елемент головна, друга — бічна. Із добутку елементів головної діагоналі

25