Симплекс - алгоритъм (2-ри етап на симплекс - метод)

Основна теорема на симплексния метод.

Симплекс - методът се състои от два етапа:

1) намиране на първоначалното референтно решение на LPP;

Намиране на оптималното решение. Този етап се нарича симплекс - алгоритъм.

Намиране на оригиналното решение за поддръжка (1-ви етап от симплекс метода).

Помислете за LPP в стандартна форма, преместете неизвестните в целевата функция наляво и разгледайте следния проблем.

xj ≥ 0, j = и макс Z., (1.1)

(1.2)

Коментирайте.Свободният член в уравнението на целевата функция е равен на нула, но може да бъде и е различен от нулата.

Ще приемем, че системата (1.1), (1.2) е последователна, системата от уравнения (1.2) е линейно независима и всички .

Нека намерим решението за поддръжка на система (1.2) чрез извършване на последователност от симплексни преобразувания и нека, в този случай, i-f уравнението на системата (1.2) се оказа разрешено по отношение на променливатаxi (i = ):

xi + цел+единxm+един + прицелвам се+2xm+2 + . + aisxs +. + ainxn = bi (i = ), (1.4)

къде са всички bi>0 (i =).

Основните променливи са променливите хедин, х2, ., xm, и безплатно: xm+един, xm+2, ., xs,., xn (основното може да не е непременно първото м променливи). Оригиналното недегенерирано решение за поддръжка на системата (4.4) има формата:

Ще кажем, че системата от уравнения (4.4) се свежда до референтното решение. Изключваме основните променливи от уравнението (4.3). За това всеки i-e, умножаваме уравнението на системата (1.4) по ci и след това добавете всички получени уравнения, получаваме:

(1,5)

Уравнение (4.3) се записва, както следва:

Z– - см+единxm+един - . - csxs -. - cnxn = 0.

Добавяйки това уравнение с (4.5), получаваме:

Ние обозначаваме:

Тогава уравнението на целевата функция ще има формата

Уравнение (4.6) ще се нарича уравнение на целевата функция, редуцирано до свободни променливи, а коефициентите Δj (j = ) - оценки на свободни променливи, където

(1.7)

В резултат на тези трансформации LPP (1.1) - (1.3) се свежда до следния еквивалентен проблем: намерете стойностите

xj ≥ 0, j = и max Z, (1.1)

Задача (1.1), (1.4), (1.6) ще се нарича LPP в канонична форма или в канонична форма.

Системата от ограничения за този проблем се свежда до референтното решение:

Уравнението на целевата функция се свежда до свободни променливи.

Коментирайте.Уравнение (1.6) се добавя към системата от уравнения (1.4) и ние разглеждаме система от (m + 1) уравнения, докато в уравнение (1.6) основното е свободното

---