Лекции по теории линейного программирования - файл n1.doc

Лекции по теории линейного программирования
скачать (1295.5 kb.)
Доступные файлы (1):
n1.doc1296kb.29.05.2012 22:23скачать

n1.doc

  1   2   3   4   5



ЛЕКЦИИ ПО ТЕОРИИ ЛИНЕИНОГО
ПРОГРАММИРОВАНИЯ



Содержание








1. Основная задача линейного программирования
– в трех формах.…………………………………


3

2. Эквивалентность различных форм постановки
основной задачи..................................…….


5

3. Преобразование Лежандра......................…...

7

4. Определение двойственной задачи с помощью
преобразования Лежандра......................…...


17

5. Теорема двойственности и теорема
существования решения.........…………………


22

6. Критерии крайней точки невырожденной
канонической задачи.....…………………………


24

7. Алгоритм симплекс-метода решения задачи
линейного программирования.......................


29

8. Обоснование алгоритма симплекс-метода...…..

34

9. Нахождение крайней точки...........................

40

10. Постановка транспортной задачи..........………

42

11. Исторические сведения о возникновении и
развитии линейного программирования..........


44














1. Основная задача линейного программирования - в трех формах
Задача линейного программирования – это нахождение минимума линейной функции f : RnR1, заданной на некотором замкнутом выпуклом множестве, выделенном линейными неравенствами.

Задача: arg = ? ,
x = {x | Axb, A = , b = (b1,…,bm)T}

называется общей задачей линейного программирования – будем обозначать ее Зо.
Определение 1. Функцией цели общей задачи назовем функцию

So : b → So(b) = ; So : Rm.

Задачу линейного программирования записывают и в других формах – канонической и нормальной.

Канонической задачей – обозначение Зк, назовем такую

Зк: arg = ? , x = {x | Ax = b, xj 0, j = }.

Нормальной задачей Зн, назовем такую

Зн: arg = ? , x = {x | Ax b, xj 0, j = }.

(Ее называют и канонической в симметричной форме).

Множеством допустимых значений задачи З назовем область определения функции - обозначаем DЗ.
2. Эквивалентность различных форм постановки основной задачи
Теорема 1. Постановки задач Зо, Зк, Зн эквивалентны.

«Эквивалентность» означает, что Зо, Зк, Зн – это различные постановки одной задачи. Если задачу в одной форме мы можем преобразовать к какой-то задаче в другой форме, то скажем, что мы можем свести первую задачу ко второй, З1 → З2. Задачи эквивалентны, если их можно преобразовать друг в друга.

Доказательство проведем по схеме Зн → Зк → Зо → Зн.

1) Зн → Зк. Итак, пусть мы умеем решать задачи в канонической форме, а задана задача в нормальной форме

Зн: arg max < c, x > = ?, Ax b, x0.

Введем дополнительные координаты = (xn+1,…, xn+m)T условиями
xn+j = bj – (Ax)j, j=, 0 и положим x'=, c'=(c1,…,cn, 0…0)T Rn+m, A'=(A, Im).

Поставим каноническую задачу З'к: arg max < c', x'>=?, A'x'=b, x'0. Если ' - решение З'к, то =(x'1,…,x'n)T решает первоначальную задачу Зн. Это очевидно.
2) Зк  Зо. Задачу Зк : arg max <c, x>=?, Ax=b, x0, запишем в виде

arg min < -c, x >=?, Axb, -Ax-b, -x0.

Теперь введем замены переменных с'=-c, и получим

З'о: arg min < c', x >=?, A'xb' A'=, b'=.

Очевидно, ее решение х будет решением и первоначальной задачи.

3) ЗоЗн. Рассмотрим Зо : arg min < c, x >=?, Axb и положим в ней
х = - с условиями ,0. Образуем векторы x' = , c'= и матрицу A' = (A, -A). Приходим к задаче З'н: arg max < c',x'>max?

A'x'=A-A=Axb, x'0. Если x'R2n решение этой задачи, то
x=(x'1,…x'n)T-(x'n+1,…,x'2n)T является решением первоначальной задачи Зо.


3. Преобразование Лежандра
Мы рассмотрим функции, заданные на Rn с вещественными значениями, допуская и значения равные ±∞

f : R n RR ∪ {-∞,+∞}.

Функцию назовем собственной, если:

1) для всех x, f (x) > – ∞

2) f (x) ≢ + ∞.

Надграфиком функции f : Rn R называется множество

{ (x, y) | xDf, y f (x) }.

Очевидно, по заданной функции надгрaфик однозначно определяется. Верно и обратное: надграфик однозначно определяет функцию. Замыканием функции f назовем функцию cl f (от английского слова close - замкнуто), имеющую своим надграфиком замыкание надграфика самой функции. Функция, совпадающая со своим замыканием, называется замкнутой.
Пример 1. (Примеры замкнутой и незамкнутой функций).

Непрерывная функция с замкнутой областью определения-– замкнута.

Функция



незамкнута, а функция



замкнута и является замыканием функции f.
Теорема 2. Собственную замкнутую выпуклую функцию f можно задать как поточечный "supremum" всех таких афинных функций h, что h(x)  f(x).

Доказательство. Очевидно, функция выпукла тогда и только тогда, когда надграфик ее выпуклый. У замкнутой выпуклой функции надграфик является замкнутым выпуклым множеством в Rn. Сначала покажем, что любое замкнутое выпуклое множество является пересечением всех содержащих его замкнутых полупространств. Действительно, если точка P лежит в замкнутом выпуклом множестве , то она принадлежит и любому содержащему замкнутому полупространству. Значит, P лежит и в пeресечении этих полупространств. Если же точка Q не лежит в , то . Тогда существует опорная плоскость множества , разделяющая и Q так, что Q лежит строго внутри соответствующего полупространства (опорной плоскостью множества Rn называется такая гиперплоскость, которая проходит через какую-то точку границы w так, что множество w лежит по одну сторону от этой гиперплоскости). Но тогда Q не может попасть в пересечение всех замкнутых полупространств, содержащих .

Обратимся к заданной в теореме замкнутой выпуклой функции f. Надграфик ее – выпуклое замкнутое множество, является пересечением содержащих его полупространств. Эти полупространства могут быть трех видов:

нижние ,

верхние ,

и вертикальные .

Однако ни одно нижнее полупространство не может участвовать в образовании надграфика, так как они ограничивают множество относительно оси ординат сверху, а надграфик сам неограничен сверху. Содержащие надграфик верхние полупространства как раз отвечают неравенству h(x)  f(x), пересечение таких надграфиков афинных функций и является поточечной верхней гранью всех этих функций h(x).

Нам надо показать сейчас, что вертикальные полупространства не играют роли в формировании надграфика функции f, то есть любое такое вертикальное полупространство можно убрать и это не изменит объема пересечения оставшихся полупространств. Действительно, пусть есть – вертикальное полупространство, содержащее надграфик f и пусть некоторая точка , то есть . Покажем, что найдется такое верхнее полупространство , которое также содержит надграфик f и не содержит точку , тогда вычеркивание полупространства V не увеличит объема пересечения полупространств. Во-первых, хотя бы одно верхнее полупространство участвует в формировании надграфика f, ведь этот надграфик ограничен снизу, т.к. функция f собственная.

Теперь мы имеем для любого x из и . Значит, для любого (это верно и для тех x, в которых значения f бесконечны, т.к. тогда ). Подберем так, чтобы в точке выполнялось нужное неравенство

,

и потом положим .



Благодаря этой теореме мы можем описать собственную замкнутую выпуклую функцию через множество F*, состоящее из всех пар таких n+1, что функции мажорируются функцией f(x)

.

Выписанное неравенство выполняется при всех x тогда и только тогда, когда Rn , (Rn) Таким образом F* является надграфиком функции .
Определение 2. Функция f* : RnR называется сопряженной к функции f, а отображение называется преобразованием Лежандра. Будем обозначать его ℒ.
Теорема 3. Пусть

f : RnR, f ,

f – строго выпуклая:

,



и надграфик f не содержит ни одной невертикальной полупрямой (такая функция называется кофинитной). Тогда .

Доказательство. Условие кофинитности означает, что для любого множество ограничено.

На ограниченном множестве супремум функции превращается в максимум и благодаря строгой выпуклости функции f достигается в единственной точке. Так как , эта точка максимума находится из условия обращения в нуль производной. То есть . Как мы уже получили, это уравнение разрешимо относительно при любом Rn. Значит, область значения Df есть все Rn и Df отображает Rn на Rn взаимно однозначно и

.



Таким образом, мы получили другое определение преобразования Лежандра:

ℒ: , , .
Теорема 4. Пусть f – выпуклая функция. Тогда f* является замкнутой выпуклой функцией, которая является собственной тогда и только тогда, когда f – собственная и , .

Доказательство. Выпуклые несобственные функции – это только или . Очевидно, что эти функции взаимно сопряжены. Пусть теперь f – выпуклая собственная функция

.

Рассмотрим множество .

Оно задано нестрогим неравенством, выдерживающим предельный переход по , поэтому замкнуто.

F* – выпуклое: если и таковы, что и , то такое же неравенство выполняется и для . В то же время очевидно

.

то есть

.

и является замкнутой и выпуклой.

Заметим, что F и определяют одно и то же множество своих опорных плоскостей, причем является пересечением только верхних полупространств, определяемых этими опорными плоскостями (см. доказательство теоремы 2). А это однозначно определяет F*, то есть .

Воспользуемся теоремой 2







.



Следствие. Преобразование Лежандра ℒ осуществляет взаимно однозначное соответствие множества всех замкнутых выпуклых функций на себя.
Теорема 5. Преобразование Лежандра ℒ осуществляет взаимно однозначное соответствие на себя и подмножества замкнутых выпуклых функций, неотрицательных и обращающихся в нуль в нуле.

Доказательство.

.

Если и , то , т.е. . Обратно, , значит, .



Рассмотрим множество W пар функций , удовлетворяющих неравенству



и пусть наилучшие из них, то есть если , и , то необходимо , . Предыдущие теоремы дают такое
Следствие: множество есть множество наилучших пар замкнутых выпуклых функций: для любых x, x* и любой собственной выпуклой функции f справедливо

– неравенство Фенхеля.

Функции, связанные преобразованием Лежандра ℒ, называются двойственными. Приведем примеры пар двойственных функций.
Пример 2.

,

, ,





то есть .

Заметим, что – это самый узкий инвариантный относительно преобразования Лежандра класс, состоящий только из одной функции.

До сих пор мы рассматривали выпуклые функции, определенные на всем пространстве Rn. Если же область определения C собственной выпуклой функции f есть часть Rn, C Rn то, очевидно, C – необходимо выпуклое множество. Введем индикаторную функцию множества C:



Пусть f – замкнутая, а заменим замкнутой, положив .

Тогда – замкнутая выпуклая собственная функция с областью определения Rn и к ней применима описанная выше теория преобразования Лежандра.
Задача. Найти ℒ(|C) и показать, что ℒ. Эта функция называется опорной функцией множества C. Нарисовать для R2.
Теорема 6. So(b) – выпуклая функция.

Доказательство. Пусть b=b'+(1-)b'', (0,1),

So(b') < c, x'o> = min < c, x'>, Ax'b'.

So(b'') < c, x''o> = min < c, x''>, Ax''b''.

Положим x= xo'+(1-)xo''. Имеем Ax b и
< c, x> = < c, x'o>+(1-)< c, x''o> = So(b') +(1-) So(b'').

А тогда So(b)= <c, x> <c, x> So(b') +(1-) So(b'').


4. Определение двойственной задачи с помощью преобразования Лежандра
Определение 3. Двойственной задачей к Зо называется такая задача линейного программирования

о)*: arg max <y,b>=?

(на некоторой области определения , являющейся выпуклым многогранником), для которой

< yopt, b > = Sо(b), где yopt= arg max <y,b>, у.
Задача. Показать, что двойственная задача однозначно определена, если b>0.
Теорема 7 (Вычисление задачи, двойственной к Зо).

о)*: arg max <y,b>=? Aтy=c, .

Доказательство. Применим преобразование Лежандра к функции Sо(b) min {<c,x> | Axb}.

Sо*(y) [<y,b>-Sо(b)] =

= [<y,b>-{<c,x> | Axb}] =

=[<y,b>+{-<c,x> | Axb}] =

={<y,b>-<c,x> | Axb} =

= {<y,b>-<c,x> | Axb} = I(b)

Если у0, то максимальное по b значение будет при b минимальном (допустимом), т.е. при b=Ax. Поэтому максимум по b будет равен . Если у>0, то, т.к. на b нет ограничений сверху, максимум по b будет равен +).

Поэтому I(b) = и

S*(y) = I(b)= =

S**(b) = [<y,b> - S*(y)] = {<y,b> | ATy=c,y0}.

Таким образом, получаем двойственную к Зо задачу

о)*: arg max <y,b>=? ATy=c, y0.



Замечание. Задачу (Зо)* можно превратить в каноническую задачу

Зк': arg max <y',-b>=? ATy'=-c, y'0. (yopt- yopt').
Определение 4. Для задач канонической и нормальной (и другим) двойственными называются те, которые являются двойственными к общим задачам, эквивалентным первоначально поставленным.
Теорема 8. Задача, двойственная к двойственной, совпадает с первоначальной.

Доказательство. Пусть сначала была дана общая задача

Зо: arg min <c,x>=?, Axb.

Двойственная задача имеет вид

о)*: arg max <y,b>=? ATy=c, y0.

Нам надо придать ей вид общей задачи. Как это сделать, было указано в доказательстве теоремы 1. Пусть y'=y, с'=-b. Тогда требуется найти arg min<y',с'>.

ATy=c запишем в виде ATyc, -ATy-c, то есть с матрицей

A'= имеем A'yb'=.
  1   2   3   4   5


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации