1611141234-c9398682b029dca593d2e7400e783f93 (824980), страница 63
Текст из файла (страница 63)
оператор дифференцирования по 1 и х(77г) = '~г" + а, Ю' +... + аи 1'Рг + аис линейный оператор, позволяющий переписать (4) в виде ХРг)г = О (4') В!ногочлен;((1) называется харакгаеристическим мноеочленом дифференциального уравнения (4'). В этой терминологии есть определенный смысл. Так,попробовав искать решение в виде г = е~',мы приходим к соотношению Х(А)ем = ~(Р~)ем = О уь и Выпуклые. многогранники и линейное. программирование 315 из которого следует, что е ' - решение уравнения (4') с==о Л(Л) = О.
Теорема 2. Пусть Лм...,Л„, совокупность всех попарно различных корней характеристического многочлена Л(1) уравнения (4'), причем корень Л, имеет кратность Й з так что Й~ +... -~- Й = и. Тогда функции 1ле~", 1<у<т, О<А<к — 1, составляют, фундаментальную систему решений. Доказательство мы не будем приводить, отсылая читателя к у.помянутому учебнику Л.С.
Понтрягина. В частном сяучае простых корней (все А = 1) рассуждения совсем несложныо, но наличие кратных корней вынуждает использовать УйНФ (см. гл. 2). Наша задача заключалась лишь в том, чтобы проиллюстрировать методы линейной аягебры в теории дифференциальных уравнений простейшего типа. 2 3. Выпуклые многогранники и линейное программирование 1. Формулировка задачи. Основная задача линейного программирования ставится следующим образом.
Дано конечномерное аффинное пространство А над полем вещественных чисел К и т+ 1 аффннно-линейных функций ум..., )„,; у; А — ь Я. Требуется отыскать точку (или точки) а, Е А, удовлетворяющие условиям х1(а) > О, ~,„(а) > О, для которых функция ~ принимает наибольшее возможное значение при этих ограничениях. Вариант, в котором некоторые из неравенств направлены в обратную сторону, 1,(а) < О н/или требуется отыскать точки, в которых 1 принимает наименьшее возможное значение, сводится к предыдущему случакг заменой знака соответству.ющих функций. Усчовие Яа) = О равносильно совокупности условий ~,,(а) > О и — Д(а) > О. Все функции 1, можно считать непостоянными.
2. Мотивировка. Рассмотрим следующую математическую модель производства. Пусть имеется предприятие, использующее т видов различных ресурсов и производящее и видов различных продуктов. Ресурсы и продукты измерякгтся в своих единицах неотрицательными вещественными числами (случай, когда это целые числа, например, количество штук автомобилей, мы не рассматриваем: при больших объемах производства и потребления ресурсов он хорошо аппроксимируется 'непрерывной" моделью).
316 Гл. 7. Прилолссния Объем выпуска всех видов продукции данного предприятия естественно описывать векторож производства (хг,хз,...,х„) Е И". Широкое распространение полу чила следующая.линейная модель потребления ресурсов. Считается, что расход ресурса с номером !з = 1,2,...,п) на производство единицы продукции вида у Ц = 1,2,...,гп) составляет аб > О,причем наличие ресурса г ограничено величиной йе Другими словами, 1?(хг,..., х„) = 6! — ~ а,.х. > О, 1( г< т, или, что эквивалентно, а„хл < Ьь Е з=! ?: =1,2,...,т. При этом, конечно, !2) у =1,2,...,п, х >О, 1(хг,..., х„) = ~ ?г х .
з=! (3) Функцию (3) в линейном программировании принято называть целевой функцией. Допустимый вектор производства, обеспечивающий максимум целевой функции (3), называется оптимальным по прибыли. Интересы предприятия заключаются в том, чтобы извлечь наиболыпую прибыль, т.е, правильно распорядившись имеющимися ресурсами, получить оптимальный вектор производства.
Х1ы видим, что эта задача является частным случаем задачи, сформулированной вп. 1. Прежде чем переходить к более содержательной геометрической интерпретации общей задачи линейного программирования, рассаютрим пример из конкретной экономики. Пример. Предположим, что некая фирма Огазовйм ее МВКВ) производит два вида продукции: моторные лодки и речные трамвайчики 1коротко МВ и КВ). Фирма располагает четырьмя типами оборудования, каждое фиксированной мощности:по сборке МВ,по сборке КВ,по сборке моторов и по штамповке листового металла.
Задача: сколько моторных лодок и сколько речных трамвайчиков следует производить фирме? Прибыль от МВ или от КВ зависит от рыночной цены за моторнуго лодку или за речной трамвайчик и от посто- т.е. предприятие не добывает производимых им продуктов на стороне для продажи или для запчастей. Предполагается, что система неравенств (1), (2) совместна. Любой вектор производства, удовлетворяющий этой системе неравенств, называется допусгпимыяь Пусть, далее,?г. прибыль, получаемая предприятием с каждой единицы утго продукта. Положим уг 3. Выпуклые мноеогранники и линейное.
нроарцммирование 317 янных издержек фирмы. Предположим, что рыночная цена и средние переменные издержки производства 1хорошо известные понятия экономики) постолнны, т.е. они не меняются при выпуске продукции в разумвых пределах. Более определенно, допустим, что рыночная цена моторной лодки равна 70000 руб., а цена речного траллвайчика —. 125000 руб. Средние переменные издержки производства МВ равны 65 500 руб, а средние переменные издержки производства ВВ— 120 000 руб. Таким образом, фирма получает 4 500 руб. за вычетом переменных издержек за каждую проиаведенную МВ и 5000 руб. -- за каждый ВВ.
Если Ж ь (соответственно Х„ь1 число МВ (соответственно ВВ1, произведенных фирмой за один день, то доходы фирмы 1до вычета постоянных издержек) должны равняться = 71М ь,ю„ь7 = 4500Л „-9500057„ь. 141 Допустим, что каждан МВ Ьсоответственно ПВ), произведенная за день, использует 15% мощности МВ-ооорудования, 12%с мощности моторного оборудования, 9% — — оборудования по лптамповке металла ьсоответственно 17% мощности ВВ-оборудования, 8 % мощности моторного оборудования и 13 % оборудования по штамповке металла). 11сно,что ограничения на решения руководителеи фирмы будут следующие: 0<155л э<100, 0 <17Ж ь <100: 12Л,ь Ь 85с ь < 100 95л Ь -~- 137Л гл < 100, Опустив очевидные пояснения, проиллюстрируем это с помощью рис.
23. Рис. 23 Чтобы учесть все указаные выше ограничения, сочетание выпуска моторных лодок и речных трамвайчиков должно лежать внутри области ОЛВСОЕ, яюляюшейся "ареной" для дейс гний руководителей фирмы. Каждан прямая ливия одинаковых прибылей Ьштрихованные прямые на чертеже1 показывает различные комбинации производства МВ и ВВ, которые ведут к одной и той же суммарной прибыли, Чертеж показывает, что оптимальное решение лежит в точке С, где фирма водного транспорта производит 5,95 МВ и 3,57 ВВ в день. С этими данными по выпуску валовой доход фирмы МВВВ составит 44625 руб. в день.
318 Гл. 7. Прияо:кения В рассмотренном примере целевая функция (4) принимает свое максимальноо значение в вершине С выпуклого многоугольника. Мы собираемся показать, что;это отнюдь не случайно. Разумеется, практические приложения линейного программирования связаны с разработкой конкретных алгоритмов отыскания оптимального вектора производства, которые можно применять вручную или на ЭВМ. Здесь мы ограничимся изложением геометрических аспектов задачи, лежащих, конечно, в основе всех алгоритмов.
3. Основные геометрические понятия. Фиксируем конечно- мерное аффинное пространство А над полем К. Буквы 7" с индексами будут обозначать аффинно-линейные функции на А. Полупространстеам называется множество точек вида (а е А! Д(а) ) О), где 7' непостоянная аффинно-линейная функция. Мноеоеранником называется пересечение конечного числа полупространств. Напомним (см. гл. 4, з 3, п. 6), что подмножество Я С А выпуклое, если из ам аз Е 5 и О < Л < 1 следует, что Лаэ + (1 — Л)аз Е 5. Поскольку Д(Лаэ + (1 — Л)ая) = ЛД(аэ) + (1 — Л)Д(ая), все полупространства выпукзы. Так как пересечение любого семей- ства выпуклых множеств является выпуклым, то все многогранники выпуклые. Как и ранее, будем говорить, что любая точка Ла~ + (1 — Л)аз, О < Л < 1, является внутиреннсй точкой отрезка аэая с концами аэ и аю Пусть Я .
- выпуклое множество. Выпуклое подмножество Т С Я называется сранью множества Я, если любои отрезок с концами в 5, некоторая внутренняя точка которого лежит в Т, целиком лежит в Т. Все множество Я является своею гранью. Грань множества 5, состоящая из одной точки, называется вершиной Я. (Читателю следует представить себе куб, октаэдр и многогранный угол в трехмерном пространстве, чтобы иметь наглядную картину основной ситуации, вагкной для линейного программирования. Грани этих фигур в смысле нашего определения --- это грани, .ребра и вершины из школьной геометрии плюс сама фигура.
Вершины шара это все точки его поверхности. Число всех граней многогранника Я не превосходит числа поДмножеств в системе аффинно-линейных фУнкций 7ы..., ~ио определяющих Я, и, следовательно, конечно.) Многогранник Я с А естественно называть оерпниченным, если для какой-либо системы координат в А найдется такое число ээ', что координаты любой точки а Е Я по абсолютной веяичине не превосходят Х.
От выбора системы координат это определение не зависит. Важнейший результат, доказываемый ниже, будет состоять в том, что максимум аффинно-линейной функции на ограниченном много- ~' 5. Выпуклые многогранники и линейное. программирование 319 граннике (в приложениях этот случай наиболее распространен) достигается на одной из его вершин; послодних конечное число. Но прежде нам придется разобраться подробнее в структуре многогранников и их граней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
