Ф.П. Васильев - Методы оптимизации (1125241), страница 28
Текст из файла (страница 28)
Если же й е Т и й + 1 е Хо то из (14), (17) получим ай„, < В(й+ 1) 'з < В(й + 1) '(й +1) й < 2А(й + 1) '. Если й е 7!, но й + 1 е Тп, то из (14), (15), (17), (19) имеем ай, < (В+ С)й 'з < Ай аз <А(й' — 1)й ез < < А(й' — 1)й '" = А(й ' — й 'з) < 2А(й+1) '. Этим показано, что ай<2АЙ ' при всех й>й, +1. Если 1 < й < й,, то а,= =й'айй '<й,й з таха,.
Остается в (16) принять|)= шах(2А; й шах ай), П !<й<й, !<й<й Л е м м а 6. Пусть числовая последовательность (юй) такова, что 0 < юй, < (1 — в„)ш, + <(„й = 1, 2,..., ю, > О, (20) где 0<ей<1, дй>0, й=1,2,, 2 в =со, !!ш Ый/ей=О.
(21) Тогда 1!гп юй =О. й До к а з а т е л ь с т в о. Поскольку 1 — х < е * при 0 < х < 1, то 1 — вй < е ". Из неравенства (20) тогда имеем 0 < ш,, < юй е " + дй, й = 1, 2,... Отсюда с помощью индукции нетрудно получить, что О < шй, < (ш, + 2„!(, ехр( ~ , 'з,)) ехр( — '! в,), й = 1, 2,, (22) й= ! в=! й=! Далее воспользуемся известной теоремой Штольца (1352, ч. 1, с.
88)), которая представляет собой разностный аналог правила Лопиталя и гласящей, что если последовательность (уй) монотонно 'возрастает, предел 1!ш (х, — хй,)/(уй — уй,) существует, 11гп уй = со, то также существует и предел !нп хй/уй, причем !!ш х /уй = !пп (хй — х,,)/(уй — уй,). Положим у, = ехр( — 2.' в ), х, = ш, + 2' ,д! ехр( 2,' в ), й = 1, 2,...
Из условий (21) следует, что (уй) монотонно возрастает и стремится к бесконечности. Кроме того, 1пп й " ' = йгп дй ехР1(+ 2 вз) й уй ей — ! й (ехр( — 2 в ) — ехр( — 2 в,)) = 1!ш ", = !!ш ( —,й) ! так как функция х/(1 — е-*) ограничена на множестве 0< х < 1. По теореме Штольца с учетом неравенства (22) получим !!ш шй = !!ш х,/уй = 1!ш (хй — хй,)/(уй — у,) = О.
й " й Заметим, что неравенство (22) по существу представляет собой оценку скорости сходимости последовательности (шй). Однако правая часть оцен- ки (22) трудно обозрима. Поэтому полезно иметь другие, быть может, более грубые, но более обозримые оценки, Здесь может быть полезна следующая простая Л е м м а 7. Пусть числовая последовательность (шй) такова, что 0 < юй й, < (1 — зй)юй + <(й, й = 1, 2,..., ю, > О, (23) 0<юй<ю,+с, й= Доказательство легко проводится по инду очевидна.
Если (25) верно для некоторого й 0 < юй, <(1 — в )(ш, + с)+!(й < (1 — вй)ю, + требовалось доказать. П Покажем, как может быть применена лемма 7 для оценки конкретных последовательностей. Л е и м а 8. Пусть числовая последоват 0 < а, < (1 — 1/й)ай+с,/йз, Й = 1, 2,..., 0< ай < с,!п(й+1)/й, й =1,2,..., с, =сонэ! >О. (27) Доказательство. Сделаем замену ш =а й(1п (й+1))-' и, пользуясь леммой 7, докажем ограниченность (ю„).
Из (26) имеем 0<ю <(1 — — ) — ю +с ! '1 ь+ ! (п(ь+ и ь+1 Ьу Ь !п(а+2) й ' Ьв!п(Ь+2)' Таким образом, (юй) удовлетворяет условиям (23) при Нетрудно видеть, что 0 < вй <1, 1!ш Ый/вй = Из леммы 7 имеем 0< шй <ю,+с,, й =1,2,... с с = с + а, / 1п 2. П Л е м м а 9. Пусть числовая последовательность (ай) такова, что 0 < ай < (а, + — '„) — „, й = 1, 2, (29) Доказательство. Сделаем замену ю =йзай. Тогда из (28) имеем $1, ПОСТАНОВКА ЗАДАЧИ 96 ГЛАВА 3 Элементы линейного программирования Изучение методов минимизации функций многих переменных начнем с методов решения сравнительно простых и достаточно хорошо изученных задач линейного программирования, Под линейным программированием понимается раздел теории экстремальных задач, в котором изучаются задачи минимизации (или максимизации) линейных функций на множествах, задаваемых системами линейных равенств и неравенств.
Различные аспекты теории и методов линейного программирования, его приложения к технико-экономическим задачам Изложены, например в 11; 13; 33; 481 49; 52-54; 61; 76; 116; 135; 179; 203; 204; 214; 216; 231; 232; 243! 252; 259; 295; 297-299; 304! 317; 320; 330; 356; 361; 370; 373; 374; 398; 410; 422; 466; 470; 471; 487; 499; 506; 516; 517; 525; 541; 566; 584-586; 601; 612," 620; 636; 644; 652; 670; 676; 683; 685; 686; 688; 690; 719; 725; 736; 746; 747; 750-752; 775; 776; 796; 8181.
у 1. Постановка задачи 1. Общая задача линейного программирования может быть сформули рована следующим образом: минимизировать функцию 1(х) =с'х'+с х +...+счх" хй>0, ЬЕ1~, при условиях (2) опх'+ агах +... + а,„х" < Ь', (4) а„х' + а„х'+... + а,„х" = Ь', гй(х) = (с, х) — ! !п(, х ю Х = (х ю Е'. хй ) О, Й е Х„ (аг, х) < Ь', г' = 1,, т;! (аг, х) = 6', г = тп + 1,, в), где (с, х), (а„х) — скалярное произведение соответствующих векторов. Приведем еще одну форму матрично-векторной записи задачи (1)-(4) Предварительно договоримся о некоторых обозначениях. Если для каких- где с', ав, Ь*', г' = 1,..., в, у' = 1,..., п заданные числа, причем не все из чисел сг и не все из ав Равны нУлю, 1 — заданное подмножество индексов из множества (1, 2,..., и). В частности, здесь возможно, что 1 = О или 1 = (1, 2,..., и); не исключаются случаи, когда отсутствуют ограничения типа равенств (т = в) или типа неравенств (та =0).
Если ввести векторы с =(с',..., с ), а! =(аг„... ..., аг„), х = (х',..., х"), то задачу (1)-(4) можно кратко записать так: "ж=[ мй!!~ " ' '~ мй!Ч А„= агы ..., а, а!ч й„..., а!ч ачм й„..., а„„! а,„„„,„..., а„„, ~) а, й„' ..., а,„ Ан= А„= Ь,= ..., 6,= ..., с,= ..., сг= Подчеркнем, что в (6) н всюду ниже в произведениях вида Аг,х„ Аггхз, Ах, Ву,...
матриц Аг„Аг„А, В... на соответствующие векто- ра х„х„х, у,, будем подразумевать, что х„х, х, у,... — это векторы- столбцы подходящей размерности, хотя для экономии места, как мы уже делали выше, часто будем записывать этн векторы в виде строки. Укажем еще на одну форму записи множества (6) Х=(х=(хыхг): х!юЕ"', х СЕ ', ж Е Аг!х!' + Х' А!гхй < Ь! чл' Аз! х! + Е Аггхгй = Ьг х!') 0)> й=! й=! й=! й=! где А,'; — й-й столбец матрицы Ав. Точку х, е Х назовем точкой минимума функции (с, х) на множестве Х или, короче, решением задачи (6), (6) если (с, х„) = !и!(с, х).
2. Приведем примеры прикладных задач, приводящих к задачам линейно- го программирования. Задача оптимального планирования производства. Пусть на некото- ром предприятии изготовляются и видов продукции из в видов сырья. Из- вестно, что на изготовление одной единицы продукции у'-го вида нужно ав единиц сырья г-го вида.
В распоря>кении предприятия имеется 6,, единиц сырья г-го вида. Известно также, что на каждой единице продукции 7'-го ви. да предприятие получает сг единиц прибыли. Требуется определить, сколько единиц х',..., х каждого вида продукции должно изготовить предприятие, чтобы обеспечить себе максимальную прибыль. либо двух векторов х = (х',..., хг), у = (у1,..., у") справедливы неравенства х! > у! при всех г = 1,..., р, то будем кратко писать; х > у. Тогда, например, неравенство х > 0 означает, что х' > 0 для всех г = 1,..., р.
Далее, не умаляя общности дальнейших рассмотрений, можем считать, что переменные х', х',..., х" перенумерованы так, что 1 = (1,...,и!), 0 < и, < п (и! = 0 соответствует случаю 1 = 0). Отдельно выделяя неотрицательные координаты, вектор х можем представить так: х = (х„ х ), х =(х!',х!,...,х,')юЕ"', хг — — (хг',хг,...,хгч)юЕ"', х,)0, а,+п =п. 'г(спользуя принятые обозначения, задачу (1)-(4) можем записать в следующем виде: 1(х) = (с!, х!) + (сг, хг) — ! !п1, х =(х!, хг) Е Х, Х =(х=(х„х ): х, 6 Е"', х, Е Е"', А н х, + А „хг < 6„Ам х, + Агг хе = 6г, х, > О), где Аи — матрицаразмером тг хи, Ь,ЕЕ ', с'ЕЕ", г',1=1,2; т,=т, т,+т =в, 4 !. ПОСТАНОВКА ЗАДАЧИ 1 и, +...+и.=б, т'=1,...,р! (12) (13) 7(и) = 2,' '> сви! .
>'=!>=! Естественно требовать, чтобы зт 96 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Если предприятие наметит себе план производства х = (х',...,х"), то оно израсходует а>,х'+...+а х" единиц сырья Его вида и получит с х'+... ... + с„х" единиц прибыли. Ясно также, что все величины х', ! = 1,..., и, неотрицательны. Поэтому мы приходим к следующей задаче линейного программирования; максимизировать функцию 7(х) = с, х'+...
+ с„х" при ограничениях х' > О,..., х" > О, а,х' +... + а>„х" < 6', ( = 1,..., з, Поскольку задача максимизации функции 7(х) равносильна задаче минимизации функции — 7(х), то с учетом введенных выше обозначений сформулированную задачу линейного программирования можно кратко записать в виде ( — с,х) — !1п1; хЕХ=(хЕЕ": х>0, Ах(6). (7) Ясно, что задача (7) является частным случаем задачи (5), (6), Задача об оптимальном использовании посевной площади. Пусть под посев р культур отведено г земельных участков площадью соответственно в 6„..., б„гектаров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
