Автор работы: Пользователь скрыл имя, 12 Ноября 2013 в 19:08, шпаргалка
Работа содержит ответы на вопросы для экзамена (зачета) по "Математике"
(3.6)
В системе 3.5 премен образует базис наз искусственным
= из 3.5 получ начальный опорный план (0; 0;…0;
план максимальной задачи
F (, 0…0) = f(
Получение оптим плана с привлечение М-задачи основывается на след теоремах
Теорема 3.1. Если в оптим плане М-задачи все искусственные переменные равны 0 то план явл оптимальным для исходной задачи
Теорема 3.2. Если в оптим плане М-задачи по крайне мере одна из искусственных переменных положительна при любом большом М-задачи, то исходная задача не имеет ни одного плана
Теорема 3.3. Если М-задач неразрешима, то и исходная задача не разрешима
Замечание!Прирешение ЗЛП методом искусст базиса, искусственные переменные следует вводить лишь в те, которые не разрешимы относительно базисных переменных.
Из формулы 3.4 следует, что F выражение включает два слогаемых и поэтому в симплеск таблице лучше отводить две строки. Тогда признак оптимальности проверяется по первой строке, которая соответствует т.к. знак коэф-та при неизменном в функции f определяется слогаемым, содержащим множество М. Лишь после того, как все элементы этой строки станут равными 0, признаки оптимальности проверяются по первой строке соотносящейся
По мере исключения из базиса искусственных переменных соответст-щие им элементы можно опускать
Если в исходной задачи fmin, то в М задаче Fmin
16 Построение двойственных задач к задачам симметричного и канонического видов
К кажд задаче ЛП можно поставить в соотвнекотдр зад ЛП называемую двойственной по отнош к первой. Если при этом в первой зад треб-сямаксимизировать целевую ф-ю при заданном ограничении, то во второй двойственной к ней задаче треб-сяминимиз-тьдрцелев ф-ю.
Целев ф-я и огран, наложенная на переменную двойственной задачи целеком определяется целью первой задачи. Исходная и двойственная образу.ют пару взаимно двойственных задач . Любую из них можно рассматривать как исходную или прямую.
Решая одну задачу тем самым находим решения и второй.
Теория двойственности позволяет расширить число задач ЛП решение которых представляет практический интерес.
Рассмотрим одну из двойств задач об использ-нии сырья.
Задача планирования произв-ваэ
Предприятие в пр-ве исп-етmразл видов ресурсов объем которых ограничен вел-нами b1…bm. Может производитсяn видов продукции. Величтина выпуска хар-сяx1…xn. Изв нормы затрат i-го ресурса на единицу j-го вида продукции (i=1,m; j=1,n). Изв выпуска от реализации едпродj-го вида = . Требуется найти такой план )(т.е. найти количество единиц продукции каждого вида) при котором расход ресурсов не превышал бы заданного их кол-ва а суммарная выручка была бы максимальной.
Математическая форма данной задачи(прямой):
(max) (1)
(j=1…m) (2)
(3)
Двойственная задача по этим исходным данным экономически формулируется так: Пусть предприятие по некоторым обстоятельствам решило реализовать имеющиеся ресурсы не выпуская готовую продукцию, при этом оно заинтересованно получить выручку не менее той суммы которую можно получить при изготовлении новой продукции. При закупке ресурсов предприятие стремится, чтобы стоимость приобретения ресурсов была минимальной => необходимо установить оптимал цены на ресурсы y1…ym, которудовлетв указ условию.
Математич форма двойств задачи:
(min) (4)
(j=1,n) (5)
(6)
ВВ задаче 1-3 и задаче 4-6 отраз пару симметричных взаимодвойств задач.
Любая из них может рассм как двойствен.
Целевая ф-я Fоопис затраты предприприобрет по ценам y1…yn, а нер-во (5)- условия, что выручка предпрреализ сырье по условным ценам будет не меньше той кот может получить изготавливая прод-ю и реализуя ее.
Двойственная задача к канонической
Найти макс знач целевой ф-ции
(max) (7), при ограничениях
(i=1,m) (8)
(j=1,n) (9)
Двойственная задача сформулир след образом: Найти минимал значение ф-ции:
(мин) (10) при ограничении:
(11)
Двойственная задача (10-11) может исключать условие что значение были не отрицат .
В рассм парах двойствен задач любую зад в паре можно приним за исходн и тогда др зад будет двойственна к ней.
Связь между моделями двойственных задач:
В задаче максимизограничнер-ва имеет смысл ≤, а в зад минимнаоб ≥.
17,Соответствие междупеременным пары взаимно двойственных задач.
Между перемен парой
(макс) (12)
(i=1…m) (13)
≥0 (j=1,n) ; (14)
ДДвойственная задача будет формулироваться как нахождиеминимального значение ф-ции
(мин) (15)
(j=1,n) (16)
(17)
ЧЧисло переменных в сис-мах 13и 16 одинаково и равно в сумме (m+n).
ББазисом в исходн зад будут переменные …, а в двойственн задач устанавл соответствие
…
y1 ym
Уст соответствие между базисными переменн двойствен зад и своб перемен исх зад.
…
x1xn
ССоответствие между переменными устанавливаются в виде таблиц
БП |
1 |
СП |
||
-x1 |
… |
-xn | ||
b1 |
… |
|||
… |
.. |
… |
… |
… |
bm |
… |
|||
f= |
0 |
-C1 |
… |
-Cn |
Ттабл 1
Для двойственной задачи:
БП |
1 |
СП |
||
y1 |
… |
|||
-C1 |
… |
| ||
… |
.. |
… |
… |
… |
-Cn |
… |
|||
F= |
0 |
b1 |
… |
bm |
ТТабл 2
Приняв свободные переменные
x1=…=xn=0 получим
.
Приняв свободн перемен
y1=…=ym=0 получим
.
Объединим таблицы 1 и 2
Значение базисн перемен исх зад 1 станут определяться F-ой строкой двойственной задачи табл 2. И наоборот значбазиснпеременндвойств зад будут опр-ся той строкой исх задачи.
СП |
БП |
F |
БП | ||
… |
|||||
1 |
СП | ||||
-x1 |
… |
-xn | |||
y1 |
b1 |
… |
|||
… |
… |
… |
… |
… |
… |
ym |
bm |
… |
|||
1 |
f= |
0 |
-C1 |
… |
-Cn |
Табл 3
Значение базисных переменных исходной задачи опредF-ми столбцами, а знач баз перемдвойств задачи опредf-ой строкой.
Вывод. Решая одну из пары задач дополучениюоптимал плана и учитывая соотв-е между переменными автоматич получаем оптимал план второй задачи.
18,Основное неравенство теории двойственности. Теоремы двойственности
Пусть между парами двойств задач 1-3 и 4-6 (см вопрос 16) составлено соответствие. Для любых допустимых планов с х=(х1,,,xn) ззаданосоотв-е справедливое неравенство:
(19)
Достаточный признак оптимальности. Теорема 1. Если ) и - допустимые планы пары двойств задач (1-3) и (4-6) (см вопрос 16) для которых выполн рав-во: f(x*)=F(y*) (20), то х*-оптимал план зад(1-3), а у*-(4-6)
Теорема 2 (Существование оптимальных планов). Для того чтобы задачи двойственн пары имели оптимал планы необх и достат чтобы кажд из этих задач имела хотя бы один допустимый план.
Первая основная теорема двойственности. Теорема 3 Если одна из двойств задач имеет оптимал план то другая так же имеет оптимал план то другая также имеет оптимал план, причем для люб опт планов х* и у* выполн равенство: f(x*)=F(y*) (21) . Для пары двойств задач fmax=Imin, т.к. f(x*)=F(y*) (22)
Если одна из двойств задач неразрешима из-за того что fmax→+∞ ((или Fmin→-∞) тто другая задача не имеет допустимых планов.
Например пусть fmax→+∞. ЭЭто значит что в табл 4 среди элементов f-той строки имеется по крайней мере один отриц элемент, а в соотв столбце нет положит элементов, т.е. нельзя выбрать разрешающий эл-т. Таблица 4
БП |
1 |
СП |
||||
-x1 |
… |
-xs |
… |
-xn | ||
b1’ |
… |
… |
||||
… |
.. |
… |
… |
… |
… |
… |
xr= |
br’ |
… |
… |
|||
… |
… |
… |
… |
… |
… |
… |
bm’ |
… |
… |
||||
f= |
0 |
q1 |
… |
Qs |
… |
qn |
В s-ттом столбце qs<0, а все (i=1.m).
Однако обратное утверждение не верно, если одна из пары взаимодействующих задач не имеет допустимого плана то отсюда не следует что целевая ф-ция второй задачи не ограничена. Экономический вывод: Для задач об использованном сырье и относит ценах первая осн теорема двойственности означ, что макс возм доход fmax от реализпрод совпадает с мин возм стоимостью сырья.
Вторая теорема двойственности. Теорема 4. Для оптимальности допустимых планов х* и у* прямой и двойств задач необх и достат чтобы выполнялись нер-ва(ограничения):
)-ооптимал планнн прямой задачи, и —оптимал план двойств задачи
19)Экономическое содержание оптимальных планов пары двойственных задач
Теорема об оценках: В оптимальном решении двойственной задачи знание переменных yi* оценок численно равны частным производным Dfmax/Dbi для исходной задачи