Доказательство основной двойственной теоремы

[nbyte]

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

Может кто-нибудь может дать краткое и чёткое (которое легко запоминается) доказательство этой теоремы, которая состоит из двух частей

Цитата:

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

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

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

[nbyte]

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

[nbyte]

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

[arseniiv]

(Оффтоп)

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

[nbyte]

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

[nbyte]

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

[nbyte]

Конкретный вопрос
Как будет выглядеть матрица

$$\[B = \left( {\begin{array}{*{20}{c}} {{a_i}} \\ {i \in {S^*}} \\ \end{array} } \right)\] $$

из этой таблицы

?

[nbyte]

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

[nbyte]

Вот тут 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 --

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

[Alexey1]

По той ссылке которую Вы привели, очень много непонятного (наверное опечатки). Рассмотрим задачу линейного программирования
$\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$.

[nbyte]

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

[nbyte]

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