2. Побудова симплексної таблиці

Обчислювальний процес та перевірку опорного плану на оптимальність подають у симплексній таблиці.

У першому стовбчику таблиці – Базис – записуються базисні змінні опорного плану, у тій послідовності, в якій врни розміщуються в системі обмежень задачі. Наступний стовбчик - С_баз. – коефіцієнти при базисних змінних у цільовій фукції задачі. У третьому стовбчику - План – записують значення базисних змінних опорного плану задачі і відповідне значення цільової фукції опорного плану (Z₀). У решті стовбчиків, кількість яких відповідає кількості змінних задачі, записують відповідні коефіцієнти обмежень задачі лінійного програмування (вектори A_j, j=1:n).

Останні рядок і стовбчик таблиці є оцінковими – в них записують розраховані оцінки.

3. Перевірка опорного плану на оптимальність за допомогою оцінок Δ_j = Z_j - C_j відбувається у відповідності до теореми:

Теорема (ознака оптимальності опорного плану).

Опорний план X^* = (x₁^*;x₂^*;…x_n^*), задачі лінійного програмування є оптимальним, якщо для всіх j ( j=1:n) виконується умова

Δj=Zj-Cj ≥ 0 - для задачі на max

Δj=Zj-Cj ≤ - для задачі на min

Якщо для побудови опорного плану було використано метод штучного базису, необхідною умовою оптимальності є вимога виведення з базису штучних змінних , або рівність їх нулеві.

Значення оцінок Δj=Zj-Cj визначають заформулою

Δj=Zj-Cj= ; ( j=1:n),

або безпосуредньо з симплексної таблиці, як скалярний добуток векторів стовбчиків С_баз і x_j мінус відповідний коефіцієнт С_j . Розраховані оцінки записують в останній рядок таблиці, який є оцінковим.