Основните факти от теорията на двойственост

където броят на променливи в още две броя на ограниченията за равенство, т.е. п-т = 2,

където ранга на матрица А = м. След това двете променливи в тази система от уравнения, казват x1 и x2. са свободни, т.е. може да се изрази чрез тях всички други променливи:

... къде - някои цифри. Замествайки тези изрази в обективната функция, ние получаваме

където - някои цифри.

Да разгледаме проблема с линейното програмиране с две променливи:

Използването на геометрични конструкции, ние откриваме, неговото решение (). Заместването тези номера в (7.9), (7.10), ние се получи разтвор и стойността на първоначалния проблем (7.8).

Пример 7.2. Намерете максималната стойност на функцията

Решение. За разлика от проблемите, описани по-горе в оригиналните проблемни ограничения са дадени под формата на уравнения. В този случай, броят на неизвестните е равен на пет. Ето защо, този проблем трябва да се намали с проблем, в който броят на неизвестни би било равно на две. В този случай това може да бъде направено чрез преместване от първоначалната задача записан в основната форма, задачата записва в стандартен формуляр.

Тя е показана по-горе (вж. § 1.2), че първоначалната задача се записва под формата на ядро ​​на проблема, състояща се от намиране на максималната стойност на функцията

От обективна функция на оригиналния проблемни променливи х3. х4, х5 елиминира чрез заместване на тези стойности на съответните ограниченията на системата от уравнения.

Ние изграждане на многоъгълник което получената проблема (фиг. 7.1.). Както се вижда от фиг. 7.1. максималната стойност на обективната функция на проблема се в точката на пресичане на линиите I и II. Заедно всеки от правия Граничната стойност на една от променливите, изключени по време на прехода към съответната неравенството е нула. Поради това, във всеки един от върховете на многоъгълника, получена окончателните решения на най-малко две променливи от първоначалния проблем става нула. По този начин, в момента имаме x3 = 0 и x4 = 0. Заместването etiznacheniya в първата и втората уравнения на системни ограничения на първоначалния проблем, ние получаваме система от две уравнения

Замествайки стойностите на x1 и x2 през третото уравнение на първоначалния проблем ограниченията на системата, ние се определи стойността на променлива х5 ravnoe14 на.

Следователно, оптималната план на проблема е х * = (3, 4, 0, 0, 14). В тази връзка, цел стойност на функция е Fmax = 18.

7.1.3. Двойствеността в линейното програмиране

Всеки LP проблем може да бъде свързана с друга задача PL, наречена двойна. Тяхното съвместно проучване е предмет на теорията на двойственост, която е важна част от линейното програмиране. По-ефектно теория двойственост е в случаите, когато двойно проблемът е решен лесно, отколкото директно.

За удобство пишем отново общото LP проблема:

Двойното проблема (7.11) е следния проблем:

За да се построи двойна проблем е необходимо да се използва на следните правила:

1) ако директно проблемът е решен до максимум, след трикамерна спринцовка - най-малко, и обратно;

2) в ограниченията за максимизиране - неравенства ≤ смисъл, и по проблема минимизиране - което означава, ≥;

3) Всяко ограничена напред проблем съответстващ двойна променливи задачи, и обратно, всеки ограничение на двойната проблема съответства на променлива директно проблем;

4) ограничения на матрица система, получена от два проблема на система матрица транспониране ограничения първоначалното проблем;

5) постоянни система ограничения условия са преки проблемни коефициенти за съответните променливи на обективната функция на двойната проблема, и обратно;

6) Ако променливата директен проблема поставила условие не е негативност (≥), а след това на съответната граница на двоен проблем е написан като ограничение - неравенство. ако не, как ограниченията на половете;

7), ако аз-е ограничаването на първоначалния проблем е неравенство, тогава аз-ти променливата на двойната проблем ил ³0. Ако-тото ограничение е уравнение, променлива у, за да вземете както положителни, така и отрицателни стойности, т.е. условието е да не не се налага негативност.

На първо място, на масата се съхранява цялата информация за прякото проблем: стойностите на параметрите Aij, двупосочно. и Джей. неравенства знаци или равенства в ограниченията (в дясно), в условията на не-негативност на съответните променливи (по-горе). След това, всеки аз - ти ред (-тото ограничение прякото проблема) е свързан с двойна променлива ай, която се припокрива състоянието на не-негативност, ако правото на тази линия е знак за неравенство. На дъното остави признаци на неравенство или собствен капитал в зависимост от това дали са наложени или не налага условие-Vie неотрицателност на съответната променлива на пряката проблема. След тази двойна задача "се чете" чрез умножаване на вектор Y = (у) на колоните на матрицата А = (Aij) и вектор б = (Bi).

Таблица. 7.1 даден преките и двойни проблеми в най-важните специални случаи.

Съставил протокол преки и двойни проблеми

Формата на първичен LP проблем

Формата на съответната двойна проблема LP