Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 15
Текст из файла (страница 15)
3.5. (0,0) Е аЬвпип, Я ;„ = О, (0,1) Е аЬяпах, Я „ = 1. 3.6. (О, О, 0) Е аЬяи!и, Я и = О, (12, О, 0),(0, 12, 0),(0, О, !2) Е аЬягиах, Я ,„ = 144, (4,4, 4),(0, 6, 6),(б, О, 6),(6, 6, 0) — критические точки в задаче на максимум. 3.7. (0,0,0) Е аЬзпт!и, Я,„= О, (0,12,0) Е аЬяиах, Я,„= 576, ( —, —, ), (, —,О), (О, —, — ),(6,О,б),(!2,О,О),(О,О, Г2) — критические точки в задаче на максимум. 1 1 ! 1 1 1 3.8. (-,—,--) ЕаЬяптп, Я,„= —, (О,—,— -), 6'6' б !2' '4' 4 ( ) 3 3 1т 3 !т — -) к 1осехтг, (Π— -) б 1осгпах Я = +оо. 8'8'4? '4'4 ам 3.9.
( — 2,0,9) Е аЬяп!и, Я„м = — 23, Я „=+ос. 3.10. ( — 5/2,0,20) Е аЬятни, Ямм = — 52,5, Я„,„= +оо. 3.1!. (16,257,592) к 1осехтг, Я и = -оо,' Я,„=+оо. 83 Ответы к залачам главы 1 (0,1,0) Е аЬяптп, Я,„= О, Я,„=+со, 3.12 (- ) 2 1?4 24т —, —, — — ) Е 1оспт1и, Я„,„= -оо, (1,0, 3) Е 1осгпах, 7' 35 ' 5 3.13 Я „=+оо, ( — 1,6,— 3) бт!осехтг. 3 14. (/6,1,!) 6 аЬьпнп, Я и — — т/б, ~/-,Д-,т~-) ЕаЬяпах, 4.1. а > О.
4.2. а > О, 6 > О. 4.3. р > !. 4.4. ан > О, атт > О, анан — ап > О. 4.5. да. 4.6. да. 2 — 3, х<0, [-3, — 1[, х=о, 4,7, д~(Ю) = — 1, 0 < х < 1, 4.8. д/(х) = [О, ![. [ — 1,3[, х=1, 3, ! < х. 49 д/(й) = [ ! 1[ 4.10 (у= (уп. зуа) Е К" [ )у[ < 1).
4.11. (у = (у„...,у„) б К" ~ птах [ут~ < 1). 2=к..,П ч (у = (В ". у») б К" ~ ~~', [у ~ < 1 (. 2=! 4.12. и 4 13. (у = (ун ..., уч) Е К" ~ 1 [уу[ = 1, уу > 0,,1 = 1,...,п) . 2 =! 4.14. [О, а]. 4.15. В' = (х' б Х' [[[х')[х ~(!). 4.18. (1, -!) Е аЬзпнп, Я;„= 3. 4.19. (-1, — 1) Е аЬяп!и, Я;„= — 2. 4.20, ат+ а2 2< 1 ~ (дивт) Е аЬяп!п, я„„„= а, + а21 2 2. а, + ат > 1 ~ ~, /! б аЬяшп, Я„,м = 21/ а, + аз— 2 д2+а2 д2+ а22 1 г! 1т 1 4 21. — < о ~ [ —, -) Е аЬяп!п, Я и —— — —. 5.1. 7'(х)[Л[ = (а, Л). 5.2. У'ф)[Л[ = 2(4, Л). 5.3. У'(4)[Л[ = (У, Л) Р[! Я,„= — —, —, —,1, —,1, —, 1, —, — К !оситах.
84 Глава 1. Экстремальные задачи 5.4. ~'(х)[Л] = 3(Й,Ь)]Щ]. 5.5. У'(х)[Л] = Ь[]х]]+— 4(х, У!) ]]4П Л (х, Ь)8 5.6. у'(х)[Л] = —— ]!«]]! 5 7. ~'(х) [(Ь!, Л!)[ = (2Ь! + Ьн 2Ь! + 4ИС). ! 5.8. У'(х(.))[Ь(.)] = 3 / й (С)Ь(С) аСС. о ! ! 5 9. У (5())[Ь()] = 3( / х(С) <СС) / И(С) «СС. о о ! 5ЛО. У'(4(.))[И(.)] = 6( / Ь'(С) 41) / й(С)Л(С) 41. о о 5.11.
У'(х( ))[Ь(.)] = Ь(0). 5 12. 7 (х())[И()1= х(!)Уг(0) + 4(0)Ь(!). 5.13. У'(«( ))[Л(.)] = !»( )Уо(1) + х(!)Ь( ). 5.14. У'(Ю(.))[Ь()] = созй(0)И(0). 5.15. У'(х())[Л()] = соах(0)Л(0)соах(!) — з!пй(0)япх(!)Ь(!). 5.16. У'(4())[Ь()] = х(!)~! У(Л(0) !ох(!) + х(0) — „). х(1) 5.17. У'(й())[Ь(.)] = (япх(0))'м*!'1(сох х(1) соо й(0) И(О) яп х(0) яп 8(1)Л(1) 1п яп 8(0)). 5.18.
х = О, 5Л9. (х = (х<,...,х„) ] ]хо] = [х ] для некоторых ! ф У'). 5.20. (х = (х<,...,х„) ] х!. хз ....х„= 0). Глава 2 Линейное программирование В линейном программировании изучаются задачи об экстремуме линейной функции нескольких переменных при ограничениях типа равенств и неравенств, задаваемых также линейными функциями. Рождение линейного программирования принято отсчитывать от работы Л. В. Канторовича ! 939 года об оптимизации раскроя листов фанеры для самолетов и распределения ограниченных ресурсов в более обших проблемах, где впервые было показано, чта многие задачи экономики формализуются как задачи об экстремуме линейной функции при линейя ных ограничениях. Канторовйч лля рассмотренного им класса задач ввел двойственные переменные, дал им содержательную зкономическую интерпретацию и описал алгоритм решения двойственной задачи близкий по духу к симплекс-методу.
Через несколько лет (около 1947 гада) интерес к подобным задачам возник у американских математиков. Этот интерес был вызван проблемами, связанными с экономикой и военно-промышленным комплексом. Из числа экономистов, пропагандировавших среди математиков данный класс задач, следует прежде всего назвать Т.Купманса. Он же ввел термин «линейное программирование» (бпеаг ргойгапип!пй), Впоследствии Канторовичу и Купмансу была присуждена Нобелевская премия па экономике за !975 год.
Слово «программирование» заимствовано нз зарубежной литературы и в данном случае означает не что иное, как «планирование». Симплекс-метод был разработан Д.Данцигом. Обшая теория была построена коллективом математиков, среди которых следует отметить так же Куна, Таккера, Гурвица н Дж.фон Неймана. В этой главе рассматриваются постановки задач линейного программирования, правило решения задач в канонической Форме по симплекс- методу, приводятся с решениями примеры.
Вводится понятие двойственности, проводится обоснование симплекс-метода, дается ряд методов нахождения первоначальной крайней точки. Рассматривакпся наиболее известные типы задач линейного программирования — транспортные залачи и задачи а назначении. Вб Глава 2. Лииейяае программирование 4 1. Симплекс-метод 1.1.
Постановки задач. Геометрическая интерпретация Задачей линейного программирования в канонической форме называется задача нахождения максимума линейной функции от и переменных х = (х„...,х„) 1(х) = с|х|+ сгхг +... + с„х„, $ 1. Симплекс-метод Функция 1 называется целевой функцией, вектор с — вектором стоимости, вектор Ь вЂ” вектором ограничений, матрица А — мотрицей условий. Обозначим Яр — численное значение задачи (Р), АгйР— множество решений задачи (Р), т.е. множество допустимых точек х Е К", для которых (с,х) = Бр.
Зодачеи линейного врограмнировония в общей форме назовем задачу (с,х) — пцп; Ах < Ь. удовлетворяющей системе |и линейных неравенств а,х, -|-а,хг+... + а",х„= Ь|, 1 2 агх|+ агхг +... + агх„= Ьм 1 2 л атХ| +а„,аз+ ... + а,"„Х„= Ьгл г н ограничениями неотрицательности х > О, 1 = 1,...,и. Поскольку уравнения системы можно умножать на — 1, то считаем, что Ьг > О, а = 1,...,пг. Одним из важнейших экономических прототипов математической модели данной задачи является нроизводственнол зодочо. Пусть на предприятии имеются производственные ресурсы пг типов в объемах Ь|,..., Ь . Предприятие производит продукцию и типов.
На производство единицы продукции 1-го типа требуется использовать ресурс квкдого г-го типа в объеме аг. Прибыль от реализации единицы продукции у-го типа равна с . Следовательно, при изготовлении х единиц продукции каждое го типа прибыль предприятия составит величину 2, с.х . Надо найти 1=1 план производства (х|,...,х„) такой, чтобы прибыль предприятия была максимальной. Равенства а1х, + агхг +...
+ а,"х„= Ь| будут означать, что весь ресурс каждого а-го типа израсходован полностью. В лальнейшсм мы, как правило, булем использовать векторно- матричную запись: (Рл) (с,х) - |пах; Ах = Ь, х > О. Здесь х = (х|,...,х„) б К" — неизвестная переменная, заданныс вектора с = (с|,...,са) Е К" н Ь=(Ь|,...,Ь ) б К, (с,х); = 2 с,х, — скалярное произведение векторов с и х, А = (аг|),=1 2=1 1 1' аг ~1 1 — заданная матрица со столбцами аг = 1 в г |ггл |глг ам 1 = 1,..., и, размеров ги х и Иногла задачи линейного программирования рассматриваются приве- денными к нормальной форме (с,х) гпах; Ах ( Ь, х > О. Каноническая форма более удобна при описании алгоритмов решения, задачи в обшей и нормальной формах часто используются при рассмотрении проблем сушествования решений и двойственности. Двойственные задачи лля задач в нормальной форме приобретают наиболее симметричный вид.
Задачи в различных формах легко сводятся друг к другу путем введения дополнительных координат и изменением матрицы А. Например, если дана задача в нормальной форме, то ее можно свести к задаче в канонической форме путем введения дополнительных координат й = (х е| ° хл|- )1 (с, х) — ~ |пах; Ах + 1х = Ь, х ~ )О, й > О. Здесь 1 — единичная матрица размеров ггь х ги. В качестве упражнений попробуйте самостоятельно свести другие формы задач линейного программирования лруг к другу. Геометрическая интерпретация. Рассмотрим более подробно задачу линейного программирования в канонической форме. Через В(Рь) будем обозначать множество допустимых точек в задаче (Рь) (В(Рь): = (х Е К" ~ Ах = Ь, х > 0)).
Множество В(Рь) является выпуклым многогранником в пространстве К". Нетрудно видеть, что экстремум линейной функции (еслн он существует) достигается в крайней (угловой) точке выпуклого многогранника. Напомним, что точка 4 выпуклого множества В называется крайней (геновой), если не сушествует точек й1, йг Е В, й| Ф йг, и числа г Е (О, 1) таких, что й = гд1+ (1 — г)йг. У многогранников крайние точки вершины. Имеет место следующая Теорема Минковского.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
