Опис варіанту симплекс-методу, який був використаний

При використанні метода послідовного уточнення оцінок, необхідно перевести ЗЛП у канонічну форму.

де? план завдання;

? вектор обмежень;

? матриця умов розміром ;

? вектор умов;

? вектор коефіцієнтів лінійної форми L [2].

Крім того, необхідно вказати опорний план задачі з базисом. Послідовне просування по базисам опорних планів задачі аж до отримання оптимального базису становить ідею методу послідовного уточнення оцінок [2]. Алгоритм починається з заповнення основної таблиці:

та допоміжної таблиці :

e_ij — елементи зворотньої матриці базисних компонент, i=1…m, j=1…m;

;

e₀ — базисні компоненти псевдо плану, за допомогою яких обирається направляюча строка r=min{ e₀ < 0}. Вони обчислюються за формулою:

e_i0 = e_i1 * b₁ + e_i2 * b₂ +…+ e _{i m} * b_m (1).

Далі заповнюються строки та Х^r відповідно формулам:

= ( А_1j * _1j + А_2j * _2j +…+ А_mj * _mj) — C_j (2).

Х_j = e_r1 * A_1j + e_r2 * A_2j +…+ e _{r m} * A_{m j} (3).

Якщо має місце ситуація, коли Ш, то слід вважати, що задача не може бути вирішена через необмеженість знизу, при цьому умови прямої та двоїстої задач не сумісні. У іншому випадку заповнюється строка O використовуючи наступну формулу:

O_j = - / Х_j (4).

та знаходять направляючу строку k, знайшовши найнайменьше O_j? 0. Якщо виявляэться декылька таких однакових O_j, то обираеться O_j меньшим порядковим номером. Замінюється Cs_r та Fs_r на С_k та A_k відповідно.І нарешті заповнюється стовбчик А_к основної таблиц за формулою:

A_j = e_i1 * A_1k + e_i2 * A_2k +…+ e _{i m} * A_{m k} , j=1…m (5).

A_m+1 = ?_k

Перерахунок елементів таблиць відбувається до тих пір, поки у стовбчику е₀ не залишиться від'ємних елементів. Елементи основної таблиці перераховуються за наступною формулою.

і= 1,2,…, m+1,j= 0,1,2,…, n. (6).