Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 39
Текст из файла (страница 39)
Суточный рацион группы животных включает не менее ! 0 кг продукта П1, 25 кг продукта Пз, |5 кг продукта Пз, 30 кг продукта П4, 5 кг продукта Пз. Эти продукты содержатся з концентратах трех видов йг, йз, йз, причем концентрат й! содержит продукты П1, Пз, Пз, П4. Пб в пропорциях 3: |: 0: |: О, концентрат йз — в пропорциях |: ! . '2 .
"|: |, концентрат йз— |: 0: |: 0; 2, цены концентратов соответственно О, 5; О, 9, О, 7 рублей за килограмм. Сколько нужно в сутки покупать концентратов, чтобы необходимый суточный рацион был наиболее дешевым) б. Показать, что мно!кество Х = )х = (х,... х ) ) 0; х +4х — 5х — 5х -Зх — х = 2, 6 . ! 2 3 4 5 6 -4х'+4хз — |2хз-2хз+2х6= 2, х +2хз-Зх +Зхз+х +х = Ц состоит из единственной точки, У к а з а н и е: применить метод искусственнога базиса, выбрав в начальной симплекс- таблице разрешающий элемент из столбца хз с помощью лексикографического правила (3.48). 6. Множество Х заданоб4гсловиями! х=(х1,, хб)>0: х'-2хз+хз=|, х' — 2х +2х ! х = 2 З 4 — х — 2хз+2хз+2х4 ' х 1 х| 2хз+2х34.2х4-2хб+х~=1, х!+хз+хЗ+х4+х5+хб Симплекс. методом решите задачу 1(х)=(с, х) -+ 'ш|, х е Х при различных с е Е 5 и убедитесь, что минимум достигается в одной и той же точке множества Х. Объясните это явление.
7. Примените симплекс-метод к основной задаче (!.2!) с вектором Ь > О, 'сведя ее к канони- ческой задаче (!.23). У к а в а н и е: сравните системы (!.22) и (3) и найдите угловую точку множества 3 задачи (!.23). В. Обобщить симплексметод на задачу: 1(х) = (с, х) — ~|и|; х е Х =(хе хгч! х > О, Ах = = Ь, и! < хг ~ (Рз, 4 = |,..., п), где ат, Р! заданные величины, пз < Р| (возможно, некоторые сй = — со и некоторые р =+со) ]775], 9.
Пользуясь упражнением 8, рассмотреть задачи ив упраткнений !-3 при дополнительных ограничениях 0 < хт < 2, 4 4. ПОИСК НАЧАЛЬНОЙ УГЛОВОЙ ТОЧКИ ф 6. Условие разрешимости задач линейного программировании. Теоремы двойственности Будем рассматривать общую задачу линейного программирования: ](х) = (с, х) = (сг, х!) + (гап хт) ~ !и], х = (х1, хя) е Х, Х = (х = (х„хз): х, Е Е", хз Е Е"') Апх,+Ашх,<Ь„АЗ х, +А„х,=Ь„х,>0), гДе Ан — матРиЦы РазмеРа тпг х ть., су Е Е", Ь, Е Е, 6, У' = 1,2. Как и выше, будем обозначать 1, = |п],Г"(х), подразумевая при этом, что Х ф яех ф О.
Для случая, когда 1, > — со, введем множество Х. = (х Е Х: Г'(х) = = Г ). Напоминаем, что задача (1), (2) называется разрешимой, если Х, ~о; каждУ|о точкУ хч е Х, называют Решением этой задачи. 1. Приведем теорему существования решения задачи (1), (2), которая дополняет теоремы Веиерштрасса из $2.! и характеризует специфику задач линейного программирования. Теорема 1. Задача(1), (2) разрешима тогда и только тогда, когда Х ф Ы и целевая функция 1(х) ограничена снизу на Х, т. в.
1, > — оо. Нетрудно видеть, что для нелинейных задач такая теорема неверна. Например, задача: Г(х)= е *- !п1, хе Х =Тх ЕЕ'. х >0) не имеет решения, хотя и 1, =0 > — со. Доказательство. Необходим ость очевидна, так какусловие Х. ~опредполагает, что Харон у', > — оо. Докажем достаточность.
Пусть Х ф|2|, 1„> — со. Покажем, что тогда Х, ~ Э. Пользуясь конструкциями теоремы 1.1, задачу (1), (2) запишем в канонической форме: у"(х) = (с, х) — + !и[, х е Х = (х е Е": Ах = Ь, х > 0), при этом с е Е", Ь Е Е", А — матрица размера т х и. С этой целью поло- жим (см. $1) и в пространстве переменных ю =(х„х„г„е) ЕЕ', 0 = о!+2п +ты„асс- смотрим задачу: д(ю) = (с„х ) + (сз, х ) + ( — сз, г ) + (О, е) 4 !п], ю Е р[г, (4) И" =(ю еЕ'1 ю >О, Апх, +А„г, +( — А!2)гт+1 е= Ь„ Аз х, + А„х, +( — А22)гз+Ое = Ьз), (5) где 1 — единичная матрица размера т, х ты Задача (4),(5) совпадает с задачей (3), если принять с = (с„с„— с, 0) е Е", Ь=(Ь„ЬЗ)ЕЕ, А= |,АЗ„А„, -Авм 0 1 — матрица размера т х и, где т гх тп, + тп, в = д = тз! + 2п + ты Согласно теореме 1.1 из Х ф О, 1, > — оо следует, что И" ~ О, д, = 1п] д(ю) > — со, хе Нг 138 Гл.
3. элементы линейнОГО пРОГРАммиРОВАния г«з. УслОВие РА3РешимОсти. теОРемы ДВОЙстВеннОсти 139 Тогда по теореме 4.3, примененной к канонической задаче (4), (5), множество И'„ = (и« е И'. д(ю) = д,) фй. Возьмем произвольную точку гг, = = (х,„, х„, г,„, о,) е Ит,. В силу теоремы 1,1 тогда точка х„ = (х,„ х, = г„— — г„) — решение задачи (1), (2), т. е. Х, ф О.
Теорема 1 доказана.*П Следствие 1. Задача максимизации (й, х)- зпр, хеХ имеет решение тогда и только тогда, когда Х ~о и функция (д, х) ограничена сверху на Х. Для того, чтобы убедиться в справедливости этого утверждения, достаточно заметить, что такая задача максимизации равносильна задаче (1), (2) с с = — 41, и воспользоваться теоремой 1, 2. Прежде чем переходить к изложению так называемых теорем двойственности, докажем несколько важных лемм. Лемма 1. Для того чтобы некоторая точка х.
из множества Х была решением канонической задача (3), т. в. х„е Х„необходимо и достаточно существования точки Л* = (Л;,, Л' ) е Е" такой, что А' Л" + с > О, (с, х.) = — (Ь, Л"), (6) гдг Ат — матрица, полученная транспонированием матрицв4 А. Доказательство. Необходимость. Возьмем произвольную точку х„е Х,. Покажем, что тогда необходимо существует точка Л" е Е со свойствами (6).
Сначала рассмотрим случай гп = т = гапйА. Применим к задаче (3) симплекс-метод с антициклином. По условию 7'(х,) = 7"„> — оо, поэтому симплекс-процесс закончится обнаружением некоторой угловой точки о„ множества Х с базисом В = (А,,, Аз ), 7"(о,) = 7"„, причем будут выполняться неравенства (3.32): гЛ = (с, В 'А,) — с" ( О, й = 1, 2,..., и; с = (с",..., с' ), (7) Положим Л* = — (В ')гс. Пользуясь известным из линейной алгебры тождеством (Мх, у) = (х, Мту), справедливым для любых х е В", у я Е" и любых матриц М размера тп х и, из (7) имеем 0 > ддз = ((В ')гс, А ) — с" = — (Л', А.) — с,",, Ь = 1, 2,..., и В векторной форме эти неравенства можно записать так: АтЛ'+ с > 0 Далее вспомним, что у угловой точки о.
базисные координаты д, = (г«з«, ..., о„') = В 'Ь, а небазисные координаты равны нулю. Поэтому (с, х,) =~„=(с, е,) =(с,д,) = (с, В Ь) = ((В ') с, Ь) = — (Ь, Л*) Таким образом, искомая точка Л* со свойствами' (6) найдена. Случай т = т = гапиА рассмотрен. Пусть теперь т > т = гапиА. Тогда в системе уравнений Ах = Ь, которую можем записать в виде (ад, х) = Ь', г' = 1,, тп, где а — строки матрицы А, имеются ровно т линейно независимых уравненни. Перенумеровав уравнения, можем считать, что первые т уравнений этой системы линеино независимы, а остальные уравнения с номерами г'=т+1,..., тп, линейно выражаются через первые, базисные уравнения 4=1,..., т.
Удаление линейно зависимых уравнений приведет к равносиль- 0 ( (х, АТЛ* + с) = (с, х) + (Ах, Л*) = (с, х) + (Ь, Л*) = (отх) — (с, х„). Это значит, что х, я Х„. Лемма 1 доказана. П Лемму 1 нетрудно обобщить на случай общей задачи линейного программирования (1), (2). Лемма 2. Для того чтобы некоторая точка х,=(хоп х,) из множества (2) была решением задачи (1), (2), необходимо й достаточно, чтобы существовала точка Л' = (Л;, Л,*), Л; с Е ч, Л; 6 Е'ч такая, что А~~ Л*, + АгЛг + с, ) О, А"„Л; + АгтЛг + сг = О, Л; > О, (с„х,„) + (сг, х~д) = — (Ь„Л;) — (Ьг, Лг), гдв Аг — матрица, полученная транспонированигм матрицьг Аи. Доказательство.
Возьмем произвольную точку х„=(хп,х, )ЕХ,. Тогда согласно теореме!.1 точка гв,=(х,„, г„, г„, о„), где вы =шах 0; х„*, гг„=шах(0; — хг„), о.=Ь,— Апх.— А„х,„, является решением задачи 4), (5, д д(щ«=д,=«=44~«.4«р у« д д 44«, (Б), заключаем, что это возможно тогда и только тогда, когда существует точка Л* = (Л"„ Л*), Л*, б Е , Л; е Е *, такая, что (9) (10) М Ат Л«4+ Ат Лг*+ с« А!гЛ*«+ А„Л,* + с — ~ «г Л~ — А газ — сг ' 7;+О АЧ '442„.4ггг Л 4 -1- )О, АТЛ'+с = ~„=д,=д(ш,)=(с„х„)+(~, сп)+( — сг, гг,)+(О, о,)= — (Ь«, Л*,) — (, Л').
Учитывая, что х„= ам — з., эти соотношения нетрудно переписать в равносильном виде (9), (10). Лемма 2 доказана. П С задачей (1), (2) тесно связана следующая задача линейного программирования: "44«(Л) = — (Ь«, Л«) — (Ьг Лг) — зпр, Л = (Л«, Лг) Е Л«(11) л=(Л=(Л„Л,): Л«~Е «Лг~Е~« А,Л, + Ат Лг+ с, ) О, А'„Л, + Ат Лг+ с, = О, Л, Ъ О).
(12) ной системе Ах = Ь, где А — матрица, состоящая из строк а„а,..., а„ матрицы А, Ь = (Ь',..., Ь"), и задача (3) сведется к равносильной канонической задаче: ~(х)=(с, х) — «!п1, хе Х =(х) 0; Ах= 6). В этой задаче число уравнений равно т = гапяА, и по доказанному существует точка Л = (Л;,..., Л„') Е Е" такая, что А'Л +с >О, (с, х,) =-(Ь, Л'). (8) Определим точку Л' = (Л, 0) е Е™, полученную добавлением к координатам Л нулевыхкоординат Л*~«=0,..., Л„"=О. Тогда из (8) следует, что АТЛ"+ + с > Од (с«х„) = — (Ь, Л'$. Необходимость доказана. Достаточность.
Пусть для какихлибо точек х„еХ, Л*еЕ выполнены соотношения (6). Тогда для всех х С Х имеем 140 Гл. 3. элементы линейнОГО пРОГРАммиРОВАния $ 3. УслОВие РАВРешимОсти. теОРемы ДВОЙстВеннОсти 141 ь,. 'а Задача (11), (12) называется двойственной задачей по отношению к исходной задаче (1), (2), переменные Л =(Л„Л,) называются двойственными переменными по отношению к исходным йеременным х = (х„х,). Будем обозначать ~' =знр4(Л), Л'=(Л е Л: 4(Л) = 1Ь'>. Как видим, двойствен- Л лЛ ная задача (11), (12) однозначно определяется по элементам со с, Ьо Ь„ Ап, Аиь Агн А, исходной задачи (1), (2). Лемма 3. Если в задачах (1), (2) и (11), (12) множества Х и Л непустьи то величины 1', = 1п17(х), 1Ь*=зпрф(Л) конечны и Ф <У. (13) Доказательство.
Возьмем произвольные х Е Х, Л ЕЛ. Тогда справедлива следующая цепочка неравенств, вытекающая из определений (2) и (12) множеств Х и Л: Г(х> — Ь(Л) = <с„*,>+ <с„*,>+ <Ь„Л,>+ <Ью Л,» )~ (с„х > + <с2, х2> + (А их, + Апхг, Л,> + (Амх, + Аыхз, Л2> = = <, + 1т,', +Ат,Л„*,>+ < + 1т,Л, + 1т,Л„» О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
