Ідея симплекс-методу

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

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

Розглянемо задачу лінійного програмування:

(2.6)

(2.7)

(2.8)

Система обмежень (2.7) визначає в випуклий многогранник , в одній із вершин якого досягається максимум або мінімум функціоналу (2.6).

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

Тому в основу так званого симплекс-методу розв’язку ЗЛП покладена наступна ідея. Необхідно знайти будь-яку вершину многогранника, а потім здійснювати перехід від вершини до вершини, добираючись до оптимальної вершини.

Для реалізації цієї ідеї необхідно розробити методику відшукання початкової вершини (опорної), а послідуючий перебір вершин впорядкувати таким чином, щоб на кожному кроці наближатися до оптимального розв’язку. Все це забезпечується спеціальною системою правил.

Читайте також:

Загальна характеристика симплекс-методу

<== попередня сторінка	\|	наступна сторінка ==>
Алгоритм жорданових перетворень	\|	Алгоритм знаходження початкового опорного плану

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.016 сек.