Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 25
Текст из файла (страница 25)
Одпако правая часть оценки (22) трудно обозрима. Поэтому полезло иметь другие, быть может, более грубые, но более обозримые оценки. Здесь может быть полезна следующая простая Л е м м а 7. Пусть числовая последовательность (в„) такова, что пРедвАРительные сВедения 1гл. 3 Доказательство легко проводится по индукции. Прн й = 1 оценка (25) очевидна. Если (25) верно для некоторого й > 1, то из (23), (24) следует 0 < свц., < (1 — г„) (свс+ с)+ дс < <(1 — г,)се,+(1 — г„)с+сг, < сос+ с, что п требовалось. Покажем, как может быть применена лемма 7 для оценки конссретных последовательностей. Лемма 8. Пусть числовая последовательность (а,) такова, что 0<а,+1<(1 — 1/й)ас+с,/й', й=1, 2, ..., (26) с, = сопз1> О, а, > О.
Тогда справедлива оиенсса О==а,< с,1п(й+1)lй, й=1, 2, ..., с, = сопзФ> О. (27) Доказательство. Сделаем замену о11 = асй (1п (й + 1) ) н, пользуясь леммой 7, докажем ограниченность (св11. Из (26) имеем 1 ) )с-)-1 1п ()с+ 1) )с+ 1 0(~ь11+1(~(1 — й) ~ 1 ь, 2 ыь+ с, )сг 1п ()с + 2) й = 1, 2, ... Таким образом, (се11 удовлетворяет условиям (23) при гд= 1 — 1 — —, (,) .™ — 11 1 ~1п(А+1) в+1 дь= сг )сг) 1п ()с + 2) ™ 1 )сс )п с сс+ 2) Нетрудно впдетгч что 0 < г, < 1 и11п1 с(1/гь = с„так что гпр ась!гь.= ь 1>1 = сг < оо. Пз леммы 7 имеем 0 < сев< св, + с, (й = 1, 2, ...), Чта раВНОСНЛЬЕО ОЦЕНКЕ (27) С С, = С, + асПП 2.
Лемма 9. Пусть числовая последовательность (а,) такова, что О-.=аьы<(1 — Ис)ос+ос/йсг, й=1, 2, ..., ос = сопз1 > О, О < р < 1, а, > О. (28) Тогда 0(аь((а1+ — '~ —, й = 1, 2, ... (29) 1 — ()) АЕ' Доказательство. Сделаем замену ос= й'а,. Тогда из (28) имеем 1 1 (й + 1)З 1й + 1)З 0 (~ сод 1~ ((1 — — а) е11 + с1 Аа) лез Это значит, что (ы11 удовлетвортет условня11 (23) при г„=1 — (1 — — ',) (1+ —,')'(1, ь~а1 ос, —— с, (1+ — ) —, й = — 1 2, ...
)сст Вспогзоглткльнык пгвдложвнпя 99 я 31 Поскольку (1+ 1Я) ' ) 1 — (1//г (/с = 1, 2, ...), то гь = (1 + — „1 ~~1 + — ) — 1 + — „1) = ) 1 + — ) — (1 — —,/1 ) аь —, (1 — р) ) О, /с = 1, 2, ...; '1 отсюда нзе следует, что 4/г„) с1/(1 — р) (/с = 1, 2, ...). По лемме 7 тогда 0(ьз,~аз,+с,/(1 — р), что равносильно оценке (29). Лемма 10.
Пусть (г,), (й,) — некоторые последовательности из евклидова пространства Е", г„— точка из Е" такая, что а (~о„.Ь, — г„)г + ) йьч т — гв (з () гь — гь (', СΠ— й,+,)(ЬЬ„Ь,Р=О, /с=0,1, ..., ч"„д,(, (31) а=о еде а, Ь вЂ” положительные постоянные.
Тогда существует конечный предел 1пп ) гь — га ) = 1пп )йь — г (32) и справедливо равенство (ЗЗ) 1пп ( йь, г — гь ! =О. ь ~з Если, кроме того, точка г„из (30) является предельной для (г,), то обе последовательности (г,), (й,) сходятся к гз. Доказательство. Из (30) следует, что ~йь+,— г )( ~(~ гь — гз ~. Тогда с помощью (31) имеем ) гье, — г„) ( ) гь+г — и ь д ( + ) йь+г — г ) ( Ьдь + ) гь — г,„), (34) или )ге+,— гз)()гь — гв)+Ьбд, У=0,1, Отсюда и пз леммы 2 прк а„= ~ гь — гз~ вытекает сущест- вование конечного предела )пп!гь — г„). Йз (34) следует (32), л что в свою очередь гарантирует выполнение равенства (33).
На- конец, пусть в (30) ге — предельная точка (гД пусть [гь )-эг„ ТогдаНгп(гь — г„.,! = 11зп(гь — г,„)= О, т. е. (гь)-+г . Отсюда и из (32) получим, что (ьзь)-~г,„. Л е и ма 11. Пусть пестри уательное число г таково, что О < г' < Ьг + с), (35) 1гл. 2 пРедВАРнтельные СВедения 1ОО где Ь, д — неотрицательные числа, р) 1. Тогда о < 2 < (Ьв+ цд) "т, (36) где о определяется равенством р ' + д ' 1. Доказательство. Если с(=0, то из (35) имеем О< <зт-'( Ь, или 0<2< Ъь е "= Ь"', что совпадает с оценкой (36) при с(=0. Поэтому можем считать, что д) О, Рассмотрим функцию 1р(х) = х" — Ьх — д, х ~ О. Нетрудно проверить, что эта функция имеет единственную точку минимума х.
(Ь)р)П1Р-1>)0, 1р(х )(ср(0) = — с1(0, 1пп ~р(х) = Х х = со, строго монотонно убывает при О~х((хе(если хе)0), строго монотонно возрастает при х)~хе. Отсюда следует, что уравнение 1р(х) = 0 имеет единственное решение х = ц, так что юр(х) < О при 0 - х < ц и 1р(х)~ 0 при х) ц. Согласно (35) 1Р(2) < О, поэтому справедлива оценка 0 < 2 < ц. Однако получить явное выражение для ц в общем случае не удается, поэтому в приложениях удобнее оценка (36). Дчя доказательства оценки (36) достаточно установить, что ц < а = (Ь' + цд) "". Пользуясь известным неравенством (10, 160, 179] 1аЫ <!а! "/р+ ~ЫЧд, справедливым для всех действительных чисел а, Ь, р ) 1, о ) 1, р '+д '=1, имеем 1р(а)=а' — аЬ вЂ” д>а" — а'р ' — Ь'д ' — 11= = а"' ' — (Ь'+ дд) ц ' = О.
Следовательно, а ~ ц и 0 < 2 < а = = (Ьв+ дд) пт. Глава 3 ЭЛЕМЕНТЫ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ Изучение методов минимизации функций многих переменных начнем с методов решения сравнительно простых и достаточно хорошо изученных задач линейного программирования, Под линейным программированием понимается раздел теории экстремальных задач, э котором изучаются задачи минимизации (или максимизации) линейных функций ва множествах, задаваемых системами линейных равенств и неравенств.
Различные аспекты теории и методов линейного программирования, его приложения к техникоэкономическим задачам изложены, например в (3, 7, 11, 12, 15, 21 — 23, 25, 30, 33, 35, 40, 41, 48, 57, 71, 79, 102, 106, 130, 144, 146, 150, 155, 183, 190, 194, 202, 2О, 224, 225, 234, 250, 261, 265, 274, 290, 292, 297, 307, 313, 320 †3, 333, 340).
й 1. Постановка задачи 1. Общая задача линейного программирования может быть сформулирована следующим образом: минимизировать функцию У(и)=с,и'+...+с и (1) при условиях (2) и'>О, йш1; а„и'+...+а,„и (Ь', а„,и'+... + а „и'( Ь, а э,,и'+...+а +, „и" = Ь"+', (3) а„и'+... + а,„и" = Ь', где ся ае, Ь' (1= 1, ..., г, 1 =1, ..., и) — заданные числа, причем не все из чисел с; и ао равны нулю; 1 — заданное подмножество индексов из множества (1, ..., и) (в частности, здесь возможно, что 1= 13 или Е = (1, ..., и); в (3) не исключаются случаи, когда отсутствуют ограничения типа равенств (т =г) или типа нера- венств (т= О)).
Если ввести векторы с =(с„..., с„), а,=(а;„... ..., а, ), и=(и', ..., и ), то задачу (1) — (3) можно кратно за- писать так: э(и) = < с, и> - 1п1; и ш У = (и ш Р: и" > О, )с ш 1; <аэ и> < Ь', 1=1, ..., т; <аэ и>=Ь', 1=т+1, ..., г). (4) 102 ЭЛЕМЕНТЫ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ [ГЛ. 3 Если для каких-либо двух векторов х = (хь, ..., хт), у =(у', ..., у") справедливы неравенства хь>уь при всех ь = 1, ...
..., р, то будем кратко писать: х> у. Тогда, например, неравенство х Р-О означает, что х'~ О для всех ь = 1, ..., р. Используя принятые обозначения, задачу (1) — (3), или (4), можно записать и в таком виде: Х(п)=(с, и)- 1п1; и~У=(иьнЕ": и" >О, ХгжХ, Ап<Ь, Аи=й), (5) где Точку ивен(Х назовем точкой минимума функции (с, и> на многкестве ХХ или, короче, решением задачи (4) или (5), если (с, и,„) = 1п1 (с, и). и 2. Приведем примеры прикладных задач, приводящих к задачам линейного программирования. Задача оптимального планирования производства.
Пусть на некотором предприятии изготовляются и видов продукции нз з видов сырья. Известно, что на изтотовление одной единицы продукции Х-Го вида нужно аи единиц сырья ь-Го вида. В распоряжении предприятия имеется Ьь единиц сырья ь-Го вида. Известно также, что на каждой единице продукции у-Го вида предприятие получает с, единиц прибыли. Требуется определить, сколько единиц и', ..., п" каждого вида продукции должно изготовить предприятие, чтобы обеспечить себе максимальную прибыль.
Если предприятие наметит себе план производства и = (иь, ... ..., И"), тО ОНО ИЗРаСХОДУЕт аььн'+...+аь„и" ЕДИНИЦ СЫРЬЯ 1-ГО вида и получит с,п'+...+с„п" единиц прибыли. Ясно также, что все величины иь (1=1, ..., и) неотрицательны. Поэтому мы приходим к следующей задаче линейното протраммирования: максимизировать функцию Х(п)= с,п'+...+ с„п" при ограничениЯх и'>О, ..., и" >О, аььпь+...+аь„и" <Ь' (ь=1, ..., з). Поскольку задача максимизации функции Х(п) равносильна задаче минимизации функции — Х(п), то с учетом введенных выше обозначений сформулированную задачу линейного программирования можно кратко записать в виде (-с, и) -+ 1в1; и ж ХХ = (и ьи Е": и > О, Аи < Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
