2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Доказательство основной двойственной теоремы
Сообщение04.02.2011, 05:17 


21/03/09
406
Здравствуйте.
Меня "подвесили" на сессии и теперь мне нужно пересдавать "методы оптимизации".
Сам я особыми знаниями в математике не обладаю, и не учусь на математика, но мне обязано нужно понять всё или хотябы вызубрить на крепкую пятерку.
Я уверен что у меня будут следующие два доказательства на экзамене. Поэтому мне надо их как-то "вбить" их себе в голову. С зубрёжкой очень боюсь что приду на экзамен и несмогу вспомнить из-за чего-либо.
Другим путём я вижу понять смысл, но самому без посторонней помощи мне эти доказательства кажутся просто набором чего-либо написанного. Другими словами я не усвоил понятий которые дали-бы мне возможность по другому взглянуть. Поэтому прошу помощи у тех кто понимает и может в доступной форме дать толкование.

Может кто-нибудь может дать краткое и чёткое (которое легко запоминается) доказательство этой теоремы, которая состоит из двух частей
Цитата:
1. Если канонический либо ему двойственный имеет оптимальный план, то другой имеет план и их оптимумы совподают.
2. Если канонического либо ему двойственного целевая функция неопределенна (канонического снизу, а дуального с верху), то другой тоже не имеет.


-- Пт фев 04, 2011 07:10:46 --

На что эти доказательств внутринне опираются?

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение04.02.2011, 17:08 


21/03/09
406
Своими словами, на что тут надо опираться чтобы доказать. Или в какой-либо другой легкой форме?

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение04.02.2011, 22:22 


21/03/09
406
Может ктото как-то хоть что-нибудь подскажет. Просто зубрить их очень не хочется.

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение04.02.2011, 22:33 
Заслуженный участник


27/04/09
28128

(Оффтоп)

Все остальные форумчане тоже ничего не понимают в начальном сообщении, так же, как и я?

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение04.02.2011, 22:43 


21/03/09
406
Хорошо, набираю что у меня в конспекте есть ....

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение05.02.2011, 00:51 


21/03/09
406
Да простит меня модератор за неформальное оформление
Вот первая часть доказательства, сейчас набираю вторую будет вторая.....
Мне совсем тут не понятно, тоесть какие-то скалярные произведения вектором, зачем они нужны, что они выражают? Ну полностью не понимаю.
Хочу что-бы кто-нибудь прояснил суть, а то если зубрить это дело то просто становиться страшно
Изображение
Изображение

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение05.02.2011, 02:56 


21/03/09
406
Конкретный вопрос
Как будет выглядеть матрица
$$\[B = \left( {\begin{array}{*{20}{c}}
   {{a_i}}  \\
   {i \in {S^*}}  \\

 \end{array} } \right)\]
$$
из этой таблицы
Изображение
?

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение05.02.2011, 16:15 


21/03/09
406
Не ну я немогу понять, по моему определению таблицы $B$ это матрица составленная из середины вектором таблицы? Если да то это противоречит тому что она должна быть квадратно. Как быть?

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение06.02.2011, 01:48 


21/03/09
406
Вот тут http://otherreferats.allbest.ru/dlt/unpack.cgi?n=84165&captcha_n=1&captcha_code=allbest&file=84165.rtf есть реферат с таким-же самым доказательством........
Я целый день провёл мучаясь, но немогу понять что значит там $A_j = DX_j (j= 1,2, ,.., n).$ Откуда оно берётся?

-- Вс фев 06, 2011 02:50:03 --

Как тут доказывается? По какому принципу? Ну хоть как-то кто-нибудь откликнитесь....

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение06.02.2011, 03:59 
Заслуженный участник


08/09/07
841
По той ссылке которую Вы привели, очень много непонятного (наверное опечатки). Рассмотрим задачу линейного программирования
$\min c'x$
$Ax=b$,
$x \geq 0$.
Двойственная ей задача
$\max p'b$
$p'A \leq c'$.
Докажем, что если первая задача имеет оптимальное решение, то вторая задача тоже имеет оптимальное решение и значения целевых функций равны.
1. Применям симплекс метод и получаем оптимальный базис $B$ состоящий из некоторых столбцов матрицы $A$. Оптимальное решение равно $x_B=B^{-1}b$.
2. Если найдено оптимальное решение, то $c'-c_BB^{-1}A \geq \mathbf{0}'$, где $c_B$ те компоненты вектора $c$ которые соответствуют базисным переменным.
3. Определим $p'=c_B^{'}B^{-1}$. Тогда получаем $p'A \leq c'$, то есть $p$ является допустимым решением двойственной задачи.
4. Теперь $p'b=c_B^{'}B^{-1}b=c_B^{'}x_B=c'x$. Отсюда следует, что $p$ является оптимальным решением двойственной задачи.
Почему это следует?
Для этого надо доказать, что если $x,p$ являются допустимыми решениями прямой и двойственной задач соответственно, то $p'b \leq c'x$.

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение06.02.2011, 18:13 


21/03/09
406
Благодарю за пост.
Сейчас сижу разбираюсь ....

 Профиль  
                  
 
 Re: Доказательство основной двойственной теоремы
Сообщение06.02.2011, 21:11 


21/03/09
406
Намного яснее для разбора по сравнению с обоими предыдущими вариантами.
Буду опираться на Ваш вариант. Спасибо ещё раз.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group