Dual линейното програмиране проблем

Предприятието произвежда п продукти (Р1, Р2, ..., Pn) като се използва за производството на видове м ресурси (S1, S2, ..., SM). Известни данни за нормите на потребление на ресурси за единица продукция на всеки вид и тяхното предприятие, т.е. акции

- степента на потребление на ресурси Si за производство на единица PJ продукти; - доставка на Si ресурс в предприятието.

Pj единична цена на продуктите е.

Необходимо е да се направи план на производството, в който приходите от продажбата й ще бъдат на максимум.

Ние означаваме с - обем на производството Pj. планирано за производство - неизвестните количества. Тогава математически модел на този проблем ще бъде, както следва:

Получената Проблемът е линейното програмиране проблем писмено в стандартна форма. За удобство на проблема (8,1) - (8.3) може да бъде представена в компактна форма:

В резултат на математически модел на проблем планиране на производството може да бъде формулиран, както следва: за да плана на производството X = (X1, Х2, ..., хп), отговаря на режима на ограничения (8.4), състоянието (8.5), в която става обективната функция (8.6) най-голямата стойност.

Да предположим, че дадена организация реши да купуват от средства на дружеството S1, S2, ..., SM, и че е необходимо да се определи оптималната цена за тези ресурси y1, y2, ..., YM. при следните условия:

1) от общата стойност на средствата за възложителя трябва да бъде минимално;

2) за всеки тип ресурси на предприятието, за да се плати не по-малко от сумата, която то може да получава обработката на този вид ресурс в готовия продукт.

Въз основа на условията на 1-купуване организация се интересува от факта, че цената на всички ресурси на Z в сумите, В1, В2, ..., BM на цени съответно y1, y2, ..., YM са минимални, т.е.

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

Според естеството си променлива ай не е отрицателна, т.е.
. (8.9)

По този начин, математически модел за възложителя ще има следния вид:

Нека сравним математическия модел (8.1) - (8.3) и (8.7) - (8.9):

1) броят на неизвестните е равен на броя на аудио задачи други ограничения;

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

3) неравенството ограничения системи имат противоположни посоки;

4) наличие на система ограничения една от целите на неизвестни са коефициентите в обективната функция на друга задача или обратно;

5) обективни функции в проблеми имат противоположни значения.

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

В теорията на линейното програмиране също се разграничи nesimmetrichnyedvoystvennyepary. Например, ако системата за задача на ограничения включват ограничен капитал и / или условия не са без негативност на променливи.

Правила за структурата на двоен чифт:

1) Признаци на неравенство в оригиналната проблема ограничава система са в съответствие с целта си функция, т.е. ако тя е сведена до минимум, неравенството трябва да бъде на формуляра «≥», а ако минимизиран, на «≤». Този принцип се отнася до двоен проблем.

2) Определяне на броя на неизвестните параметри на двоен проблем, е равен на броя на ограниченията на първоначалния проблем.

3) Определяне на границите на допустимите стойности на всяка от променливите на двойното проблема в съответствие със следните правила:

всеки и-ти ограничение-неравенство съответства на първоначалния проблем и -s променлива двойна проблем удовлетворява условието за не-негативизъм; и всяко входно-тия ограничения равенство на първоначалния проблем съответства на аз променлива звезда на двойния проблем, неограничен знака.

4) Определяне на двойна проблемни ограничения матрични коефициентите на матрица система от транспозиция на ограниченията коефициенти на оригиналния проблема.

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

6), отчетени от системата ограничава двоен проблем, където всеки вид ограничение се определя въз основа на следните правила:

всеки й тата променлива първоначалното проблем отговаря състояние без негативизъм съответства й тата ogranichenie- неравенство двойна проблем (неравенство вид се определя в съответствие с принципа формулирани в правило 1, и като се изхожда от факта, че обективната функция на двойната проблема има противоположни функции за разтоварване на оригиналния проблем смисъла (правило 7)); и всеки к-ти променлива на първоначалния проблем, неограничен знак съответства на ограниченията й корекция равенство на двойна проблема.

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

Пример 8.1. Създаване на двойно по следната Задачата на линейното програмиране:

В съответствие с правило 1 на задвижващата система на ограничения в съответствие с целевата функция (умножена по -1 първо ограничение), след първоначалното проблем ще има формата:

В съответствие с член 2, въвежда две променливи Y1 и Y2. при което, въз основа на принципа 3, y1 ≥ 0, и променлива Y2 не е ограничено по знак.

Ние определяме матрицата на двойния проблем на ограничения на коефициентите на основата на Правило 4:

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

Пишем ограниченията на двоен проблем:

Първото и Второто ограничение има неравенство се дължи на факта, че x1 променливи и x2 задоволи състояние без негативизъм и знака «≥» определя от правилата 1 и 7. х3 на променливи и х4 не се ограничават в знак, така че трети и четвърти ограниченията на двоен проблем, написани под формата уравнения.

Въз основа на член 7, пишем целевата функция на двоен проблем:
.

По този начин, двойно двойка ще бъде както следва: