Нека запишем двойствения проблем в директния проблем на линейното програмиране

Концепцията за дуалност в икономически и математически модели на проблеми. Икономическа интерпретация на преки и двойни проблеми.

1. Преки и двойни проблеми. Правила за конструиране на двойствени задачи.

2. Решаване на директни задачи по симплексния метод

3. Двоен симплексен метод

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

5. Използване на двойни оценки за анализиране на оптималния план

Аз. Преки и двойни проблеми. Правила за конструиране на двойни задачи.

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

Нека едно предприятие има m вида икономически ресурси, чиито запаси са съответно равни на b1, b2, …, bm (iͼm), където i е числото на икономическия ресурс, m е наборът, който включва броя на икономическите ресурси.

Нормите на потребление на всеки вид ресурс за единица от всеки вид продукт са известни и равни на aij (iͼm; jͼn), където j е номерът на типа продукция, n е множеството, включващо числата продукция.

Необходимо е да се състави такъв производствен план, при който предприятието да получи максимален икономически ефект, ако е известно, че икономическият ефект от производството на една единица от j-тия вид продукт = cj (jͼn).

Нека формализираме задачата.

Означаваме xj (jͼn ) – количеството на j-тия вид продукт, произведен от предприятието в оптималния план. Тогава е възможнода се състави система от ограничения на задачата върху използването на всеки вид икономически ресурси.

Ограничение за използването на първия тип ресурси

Ограничение за използването на втория вид ресурс

M) Ограничение за използването на m-тия вид ресурс

m+1) Ограничение върху неотрицателността на променливите

Целева функция на задачата - максимален икономически ефект

Критерият за оптимизация на задачата може да клони към максимума или към минимума.

Горният модел може да бъде написан в съкратена форма:

1)

2) xj ≥0 (jͼn)

Разширената и съкратена форма на нотация не е нищо повече от нотация на проблем с директно линейно програмиране. Винаги обаче имадвоен проблем спрямо прекия проблем.

Първоначално пишемправила за конструиране на двойни проблеми:

1) Целевата функция на директния проблем се обозначава с буквата C, когатодвойственият проблем W, иако целевата функция на проблема (директен) ® max, тогава двойственият проблем ® min и обратно.

2) Акотипът на ограничението на прекия проблем е „≤“, тогава двойният проблем е „≥“ и обратно.

3) Свободните членове на директния проблем (b1, b2, …, bm) действат като коефициенти на целевата функция на двойния проблем

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

5) Брой ограничения на двойния проблем = брой променливи в директния проблем

6) Технически и икономически коефициенти на двойния проблем се получават чрез транспониране на матрицата от технически и икономически коефициенти на прекия проблем

7) Аконеобходимите променливи на директния проблем са означени с xj, тогава двойните проблеми са yi

8) Техническите и икономическите коефициенти на двойния проблем са означени като bij, въпреки че в оригиналната нотация можетеизползвайте същите коефициенти aij

Нека запишем двойствения проблем към директния проблем на линейното програмиране.

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

Нека предприятието произвежда 3 вида продукти: T1, T2, T3. След изпълнение на годишната задача предприятието разполага с два вида суровини S1 и S2, от които се произвеждат горепосочените стоки T1, T2, T3. Възниква въпросът какво да правим с остатъците от суровини:

1) Произвеждайте стоки отново

2) Продайте остатъците от суровини на нуждаеща се организация

Кое е по-изгодно? Произвеждате продукти и ги продавате или продавате суровини?

Числените данни за наличието на суровини, потреблението на суровини за единица от всеки вид продукт, печалбата от продажбата на всеки вид са дадени в таблицата: