Умови оптимальності

Зобразимо цільову функцію F через вільні змінні. Це дає можливість аналізувати кожну вільну змінну та встановити, чи може вона поліпшити значення F, якщо її перевести до базисної.

Нехай

і припустимо, що перші т змінних вибрані базисними. Позначимо їх через . Тоді

Перетворимо обмеження до вигляду

Потім базисні змінні виразимо через вільні:

.

Підставимо останній вираз у цільову функцію, перетворимо її і дістанемо

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

Такий розв’язок є базисним.

Якщо позначити

то

де – значення базисного плану; – оцінки коефіцієнти? при вільних змінних.

Проаналізуємо вираз цільової функції через оцінки та .

Якщо , то при можна зменшити значення цільової функції шляхом збільшення ; якщо , значення можна збільшити при . Тому вільні змінні , для яких означає дозволяє? поліпшення значення , слід вивести з вільних та ввести до сукупності базисних змінних.

Цілком зрозуміло, якщо при та ?при , то знайдений план розв’язування задачі не можна поліпшити. Згідно з цим умови оптимальності розв’язку задачі лінійного програмування симплексним методом такі: варіант вважається оптимальним, якщо при та при . Коли розв’язок задовольняє таким умовам, то це означає, що зміна жодноїа вільноїа змінноїа не зможе поліпшити значення ., якщо її ввести до сукупності базисних змінних.

Інтерпретація коефіцієнтів така: значення означають поліпшення величини , якщо збільшити на одиницю відповідну вільну змінну у випадку (+ ) при або (- ) при . Кожна величина відображує міру відхилення від базисногооптимального? значення при збільшенні змінної на одиницю.