Экономико-математические модели и оптимизация

Российский университет дружбы народов Сочинский институт ЛЕКЦИЯ 1. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ОПТИМИЗАЦИЯ 1.1. Экономико-математические модели Экономико-математическая модель − математическое описание экономического процесса или объекта, произведенное в целях их исследования и управления ими. При построении модели предполагается, что ее непосредственное изучение дает новые знания о моделируемом объекте. Построение математической модели экономического объекта позволяют свести анализ экономических процессов к математическому анализу и принятию эффективных решений. Для этого необходимо формализовать экономическую сущность исследуемого экономического объекта и рассматриваемую экономическую задачу представить математически в виде уравнений, неравенств и целевой функции на экстремум (максимум и минимум) при выполнении всех условий на ограничения и переменные. МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Материалы для изучения курса Лекции 1-9 1. Экономико-математические модели и оптимизация 2. Линейное программирование (основные задачи, понятия и результаты, геометрический метод решения) 3. Линейное программирование (каноническая задача, понятие базисных решений, симплекс-метод) 4. Линейное программирование (двойственные задачи, теоремы двойственности) 5. Классические задачи оптимизации 6. Метод множителей Лагранжа 7. Нелинейное программирование 8. Динамическое программирование (непрерывные и многошаговые процессы, принцип оптимальности) 9. Динамическое программирование (оптимальное распределение инвестиций) Сочи 2021 Математическое моделирование − процесс построения математической модели. 1.2. Оптимизация в экономике Оптимизация (в математике) − задача нахождения экстремума (минимума или максимума) функции одной или нескольких переменных (целевой функции) при наличии ограничений, наложенных на эти переменные. Математическое программирование изучает теорию и методы (в том числе численные методы) решения задач оптимизации, в общем случае представляющих серьезные математические трудности. В экономике к задачам оптимизации сводятся задачи оптимального распределения ресурсов, планирования выпуска продукции, ценообразования, транспортные задачи, и другие. Наиболее часто целевые функции в этих задачах определяют прибыль (в задачах на максимум прибыли) или расходы предприятия (в задачах на минимум расходов). Подчеркнем, что термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Этот термин не имеет отношения непосредственно к программированию (составлению программ для компьютера), поскольку был предложен Дж. Данцигом в 40-е годы XX столетия ещё до того, как компьютеры были использованы для решения задач оптимизации. 1.3. Основные задачи математического программирования К основным относятся следующие задачи математического программирования. 1) Классические задачи оптимизации, включающие задачи: − одномерной оптимизации; − многомерной безусловной оптимизации; − многомерной условной оптимизации при ограничениях типа равенств. 2) Задачи нелинейного программирования, в которых рассматриваются ограничения типа неравенств и где целевая функция и (или) ограничения являются нелинейными. 3) Задачи линейного программирования, где целевая функция и ограничения являются линейными соотношениями. 4) Задачи динамического программирования, где рассматриваются задачи, в которых процесс решения можно разбить на отдельные этапы. f(x) = 12x1 + 8x2 → min 1.4. Примеры задач экономико-математического моделирования и оптимизации 0,5x1 + 0,3x2 ≥ 30, 40x1 + 10x2 ≥ 1000, 1,25x1 + 2,5x2 ≥ 100, x1 ≤ 50, x2 ≤ 80. 1.4.1. Оптимальное планирование выпуска продукции предприятия. Пусть цех имеет: 300 кг металла, 100 м2 стекла, 160 чел. - час. рабочего времени. Надо изготовить изделия А и В. Прибыль от реализации изделий: А − 10 у.е., В − 12 у.е. Для изготовления изделия А расходуется: 4 кг металла, 2 м2 стекла и 2 чел.-час. рабочего времени. Для изготовления изделия В расходуется: 5 кг металла, 1 м2 стекла и 3 чел.- час. рабочего времени. Требуется спланировать выпуск продукции так, чтобы прибыль была максимальной. Пусть x1 и x2 − количество изделий соответственно А и В. Прибыль от реализации всей продукции f (x1, x2) = 10x1 +12x2. Ресурсы сырья и рабочего времени запишем в виде ограничений − неравенств: 4x1 + 5x2 ≤ 300, 2x1 + x2 ≤ 100, 2x1 + 3x2 ≤ 160. Получаем следующую задачу оптимизации: найти максимальное значение функции f(x1, x2) при сделанных ограничениях. Данная задача является стандартной задачей линейного программирования. 1.4.2. Оптимальный выбор рациона откорма скота. Имеются корма двух видов: сено и силос. Их можно использовать для кормления скота в количестве не более 50 и 80 кг соответственно. Стоимость 1 кг сена 12 ден. ед., а силоса 8 ден. ед. Составить кормовой рацион минимальной стоимости. Данные приведены в таблице: Корма Сено 1.4.3. Оптимальное сочетание посевов сельскохозяйственных культур. Найти оптимальное сочетание посевов трех культур: пшеницы, гречихи и картофеля. Эффективность возделывания названных культур (в расчете на 1 га) характеризуется показателями, значения которых приведены в таблице. Производственные ресурсы: 6000 га пашни, 5000 чел.-дней труда механизаторов, 9000 чел.-дней ручного труда. Критерий оптимальности – максимум прибыли Показатель Кроме того, по смыслу задачи: x1 ≥ 0, x2 ≥ 0. Питательные вещества x1 ≥ 0, x2 ≥ 0. Силос Минимальное содерж. пит. веществ Пшеница Гречиха Картофель Урожайность, ц 20 10 100 Затраты механизаторов, чел.-дней 0.5 1 5 Затраты ручного труда, чел.дней 0.5 0.5 20 Прибыль от реализации 1 ц продукции, ден.ед. 4 10 3 Пусть x1, x2 и x3 − количество собираемой пшеницы, гречихи и картофеля соответственно. Ограничения: 1) на количество пашни: 20x1 + 10x2 + 10x3 ≤ 6000; 2) на затраты труда механизаторов: 0.5x1 + x2 + 5x3 ≤ 5000; 3) на затраты ручного труда: 0.5x1 + 0.5x2 + 20x3 ≤ 3000. Кроме того, по смыслу задачи: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Целевая функция, выражающая получаемую от реализации прибыль имеет вид: Кормов. ед., кг 0,5 0,3 30 Протеин, г 40 10 1000 f(x) = 4x1 + 10x2 + 3x3. Кальций, г 1,25 2,5 100 Фосфор, г 2 1 80 Получаем следующую задачу оптимизации в виде стандартной задачи линейного программирования: f(x) = 4x1 + 10x2 + 3x3 → max, Пусть x1 и x2 − количество сена и силоса соответственно. Тогда целевая функция, выражающая стоимость рациона имеет вид: f(x) = 12x1 + 8x2. Получаем следующую задачу оптимизации, относящуюся к основным задачам линейного программирования: 20x1 + 10x2 + 100x3 ≤ 6000, 0,5x1 + x2 + 5x3 ≤ 5000, 0,5x1 + 0,5x2 + 20x3 ≤ 9000. x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. 1.4.4. Оптимальный состав инвестиций. Собственные средства банка в сумме с депозитами составляют 100 млн руб. Эти средства банк может разместить в кредиты по ставке 16% годовых и в государственные ценные бумаги по ставке 12% годовых. При этом должны выполняться следующие условия: 1) не менее 35% всех имеющихся средств необходимо разместить в кредитах; 2) ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах. Определить такое размещение средств в кредиты и ценные бумаги, при котором прибыль банка будет наибольшей. Пусть x1 и x2 − средства размещенные в кредитах и ценных бумагах соответственно (млн руб.). В данном случае имеем следующую задачу оптимизации: f = 0,16x1 + 0,12x2 → max, x1 + x2 ≤ 100, x1 ≥ 35, −3x1 + 7x2 ≥ 0, x1 ≥ 0, x2 ≥ 0. 1.4.5. Оптимальное распределение инвестиций между предприятиями. Корпорация планирует деятельность N своих предприятий на некоторый период времени. Установлено, что объем x средств, выделенных i-му предприятию, приносит прибыль Пi(x), где Пi(x) − заданные нелинейные функции. Принято считать, что: 1) прибыль Пi(x) полученная i-ым предприятием, не зависит от вложения средств в другие предприятия; 2) прибыль от каждого предприятия выражается в одних условных единицах; 3) суммарная прибыль концерна равна сумме прибылей, полученных от каждого предприятия. Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей, если объем выделяемых корпораций средств равен I. Пусть xi − объем средств, выделяемых i-му предприятию. Согласно сделанным допущениям суммарная прибыль концерна f(x1, x2, … , xN) = П1(x1) + П2(x2) + … + ПN(xN). Переменные xi удовлетворяют ограничениям x1 + x2 + … + xN = I, xi ≥ 0 (i = 1, … , N). Задача оптимизации: найти максимальное значение функции f(x1, x2, … , xN) при сделанных ограничениях. Данная задача является задачей нелинейного программмирования. 1.5. Задача об оптимальном портфеле ценных бумаг Начало современной портфельной теории было положено в 1952г. работой американского экономиста Гарри Марковица (H.M. Markowitz. Portfolio Selection // The Journal of Finance. 1952. Vol.7. №1. P.77-91). Главной заслугой этой работы явилась предложенная теоретико-вероятностная формализация понятия риска и доходности, что позволило выбор оптимальной инвестиционной стратегии сформулировать как оптимизационную задачу. Результаты Г. Марковица были развиты и дополнены работами Джеймса Тобина и Вильяма Шарпа (W.F. Sharpe). В 1990 г. Г. Марковиц, Д. Тобин и В. Шарп получили Нобелевскую премию по экономике за развитие современной портфельной теории. Портфельная теория Г. Марковица − это методика формирования инвестиционного портфеля, направленная на оптимальный выбор активов исходя из требуемого соотношения риска и доходности. Целевой функцией является либо общая доходность портфеля, которая стремится к максимуму (задачи максимизации доходности при заданном уровне риска), либо общий риск портфеля, который стремится к минимуму (задача минимизации риска при заданном уровне доходности). Изменяемыми параметрами являются доли соотношения активов в портфеле. В модели Г. Марковица допустимыми являются только стандартные портфели (без коротких позиций), поэтому на доли активов в портфеле накладывается условие неотрицательности. Это ограничение отсутствует в модели Фишера Блэка (F.S. Black (1938-1995). Рассмотрим задачу инвестирования в n рискованных активов (акций), которые торгуются на фондовом рынке (фондовой бирже). Будем считать, что инвестор предполагает владеть акциями время T после покупки. Доходность Rj актива j (j = 1, … , n) определяется величиной: Rj = (Coj – CTj + dTj)/ Coj, где Coj – цена покупки акций типа j; CTj – цена продажи акций типа j через время T ; dTj – дивиденды на акцию типа j в период T. Величина Rj представляет собой доход на единицу вложенных средств в акцию типа j. Заметим, что доходность Rj есть случайная величина. Поскольку акции торгуются на бирже, то можно оценить статистические характеристики доходности для всех типов акций: 1) mj = E(Rj ) – ожидаемая доходность акций типа j (E(Rj) – математическое ожидание случайной величины Rj ; 2) Dj = Vjj = E[Rj – E(R j)]2 = E[Rj – mj]2 = E(Rj)2– mj2 – дисперсия доходности акций типа j; 3) σj = Vij – среднеквадратическое отклонение доходности акций типа j. Предполагается, что можно оценить также Vij – ковариации доходности акций типа i и акций типа j: Vjj = cov (Rj, Rj) = E[(Ri – mi)×(Rj – mj)] (i ≠ j; i, j = 1, … ,n). Дисперсии Vjj и ковариации Vij образуют матрицу размера (n×n), называемую ковариационной матрицей доходности ценных бумаг. Портфелем ценных бумаг по Ф. Блэку будем называть такой вектор x = (x1, x2, … , xn), что x1 + x2 + … + xn = 1, где xj – доля вложений в актив j (j = 1, … ,n). Значения xj могут быть как положительными, так и отрицательными; неотрицательное значение (xj ≥ 0) переменной j означает, что инвестор вкладывает в актив j собственные средства, отрицательное значение (xj < 0 ) переменной j означает, что актив j приобретается в долг (разрешены кредитнозаемные операции). Портфелем ценных бумаг по Г. Марковицу будем называть такой вектор x = (x1, x2, … , xn), что x1 + x2 + … + xn = 1, а также xj ≥ 0 (кредитно-заемные операции запрещены. Характеристики портфеля ценных бумаг. Каждый портфель ценных бумаг x = (x1, x2, … , xn) имеет две характеристики: 1) ожидаемую доходность (доходность портфеля); 2) дисперсию доходности (риск портфеля). Ожидаемая доходность m(x) и дисперсия V(x) портфеля x = (x1, x2, … , xn) вычисляются по формулам: m(x) = m1x1 + m2x2 + … + mnxn, V(x) = Vijxixj. Квадратичная форма V(x) неотрицательна (V(x) ≥ 0) при всех значениях x = (x1, x2, … , xn), а ковариационная матрица V(x) положительно полуопределена. Поэтому V(x) – выпуклая функция. Классическая задача нахождения оптимального портфеля ценных бумаг. Найти допустимый портфель, минимизирующий риск, при условии, что доходность портфеля равна заданной величине m: V(x) = Vijxixj → min x1 + x2 + … + xn = 1, m(x) = m1x1 + m2x2 + … + mnxn = m. В случае портфеля Г. Марковица добавляется условие xj ≥ 0. Таким образом, в случае модели Ф. Блэка имеем классическую задачу условного экстремума (при ограничениях в виде равенств). В силу выпуклости функции V(x) эта задача имеет единственное решение, причем решение сводится к решению линейной алгебраической системы уравнений. В случае модели Г. Марковица имеем задачу нелинейного (квадратичного) программирования при ограничениях смешанного типа (вида равенств и неравенств). Вопросы для самоконтроля 1. Что понимается под экономико-математической моделью? 2. Классификация задач математического программирования. 3. Суть термина «программирование» в задачах оптимизации. 4. Приведите содержательные примеры задач оптимизации в экономике. ЛЕКЦИЯ 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (основные задачи, понятия и результаты, геометрический метод решения) Среди задач математического программирования наиболее разработанными в теоретическом и вычислительном аспектах являются задачи линейного программирования, в которых целевая функция является линейной, а система ограничений представляет собой систему линейных неравенств и (или) равенств. Первые результаты в задаче линейного программирования получены в 1939г. советским математиком Л.В. Канторовичем (1912-1986) – лауреатом Нобелевской премии по экономике 1975г. (за вклад в теорию оптимального распределения ресурсов, совместно с Тьяллингом Купмансом (T.C. Koopmans (1910-1985)). Эти результаты были опубликованы в книге «Математические методы организации и планирования производства» (изд-во Ленинградского университета), в которой сформулирован новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, и таким образом были заложены основы линейного программирования. Отметим, что интерес к задаче возник тогда, когда в порядке научной консультации Л.В. Канторович приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась решению обычными методами и стало ясно, что задача не случайная. В общей форме задача линейного программирования была впервые поставлена позднее, в 1949г. году американским математиком Джоном Данцигом (G.B. Dantzig (1914-2005)) в департаменте военно-воздушных сил США, который предложил и общий метод решения (симплекс-метод). В то время там занимались исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952г. До сих пор, по оценкам специалистов, 75% задач оптимизации, решаемых в США, являются задачами линейного программирования. Большинство этих задач многомерные (часто с сотнями и даже тысячами переменных) и для их решения используются современные программные средства. Наличие таких средств и их использование, тем не менее, предполагает понимание теоретических основ линейного программирования. Еще раз подчеркнем, что термин «программирование» нужно понимать в смысле «планирования». 2.1. Основные задачи Основные задачи линейного программирования ставятся следующим образом: 1) задача максимизации линейной функции (целевой функции) f(x) = с1x1 + с2x2 + … + сnxn → max, при ограничениях a11x1 + a12x2 + … + a1nxn ≤ b1, a21x1 + a22x2 + … + a2nxn ≤ b2, … am1x1 + am2x2 + … + amnxn ≤ bm, am+1,x1 + am+1,2x2 + … + am+1,xn ≥ bm+1, … am+k,x1 + am+k,2x2 + … + am+k,nxn ≥ bm+k,m, xi ≥ 0 (i = 1, … , n); 2) задача минимизации линейной функции f(x) = с1x1 + с2x2 + … + сnxn → min, при ограничениях a11x1 + a12x2 + … + a1nxn ≥ b1, a21x1 + a22x2 + … + a2nxn ≥ b2, … am1x1 + am2x2 + … + amnxn ≥ bm, am+1,x1 + am+1,2x2 + … + am+1,xn ≤ bm+1, … am+k,x1 + am+k,2x2 + … + am+k,nxn ≤ bm+k,m, Замечание 2.2.1. 1) Если линейная целевая функция принимает максимальное (минимальное) значение более чем в в одной из угловых точек, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек. 2) Из указанных результатов следует, что оптимум линейной целевой функции основных задач линейной программирования следует искать в угловых точках множества допустимых решений. Для сравнения отметим, что в задачах нелинейного программирования на условный экстремум при ограничениях типа неравенств целевая функция может принимать оптимальное значение как во внутренних, так и в граничных точках. xi ≥ 0 (i = 1, … , n). Стандартные задачи линейного программирования характеризуются тем, что ограничения являются одного знака. Например, стандартная задача максимизации линейной функции (целевой функции) ставится следующим образом: f(x) = с1x1 + с2x2 + … + сnxn → max, при ограничениях a11x1 + a12x2 + … + a1nxn ≤ b1, a21x1 + a22x2 + … + a2nxn ≤ b2, … am1x1 + am2x2 + … + amnxn ≤ bm, xi ≥ 0 (i = 1, … , n). 2.2. Основные понятия и результаты Введем основные понятия, связанные с задачами линейного программирования. 1) Решение x = (x1, x2, … , xn) основной задачи линейного программирования является допустимым, если оно удовлетворяет системе ограничений. 2) Оптимальным решением (оптимальным планом) x*= (x1*, x2*, … , xn*) называется такое допустимое решение, при котором целевая функция f(x) = с1x1 + с2x2 + … + сnxn принимает максимальное (минимальное) значение. Сформулируем основные результаты, которые составляют основу методов (в общем случае – численных) решения указанных задач. Теорема 2.2.1 (характеристика множества допустимых решений). Множество всех допустимых решений системы ограничений основных задач линейного программирования является выпуклым (представляет собой выпуклую многогранную область). Теорема 2.2.2 (характеристика оптимального решения). Если задача линейного программирования имеет оптимальное решение, то линейная целевая функция принимает максимальное (минимальное) значение в одной из угловых точек множества допустимых решений. 2.3. Геометрический (графический) метод решения В случае, когда в задачах линейного программирования n = 2 (две переменных x1 и x2) их решения могут быть получены наглядным геометрическим методом. Этот метод сводится к следующему. 1) Определяется множество допустимых решений. 2) Находится вектор градиента ∇f(x) = (с1, с2, … , сn) целевой функции. 3) Линия уровня f(x) = с1x1 + с2x2 = 0 передвигается в направлении вектора градиента до достижения «точки выхода» (в задаче максимизации) из множестве допустимых решений или до достижения «точки входа» (в задаче минимизации). Пример 2.3.1 (оптимизация размещения побочного производства лесничества). Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, вырастающие за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1,5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 часов в год на свое побочное хозяйство. Практика показывает, что требуется 20 часов для ухода (культивация, подрезание, вырубка и пакетирование) за одной партией деревьев. Для ухода за одним бычком также требуется 20 часов. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам одна новогодняя ель принесет прибыль в 2,5 тыс. руб., один бычок – 5 тыс. руб. Найти оптимальное сочетание количества партий саженцев елей и количества бычков, обеспечивающих максимум прибыли лесничества от указанного побочного производства. Рассматриваемая задача сводится к следующей стандартной задаче линейного программирования: f(x) = 5000x1 + 2500x2 → max, 4x1 + 1,5x2 ≤ 24 1200x1 + 150x2 ≤ 6000 20x1 + 20x2 ≤ 200 x1 ≥ 2, x2 ≥ 0. Множество допустимых решений имеет вид Пример 2.3.3. Решить задачу линейного программирования f(x) = x1 + x2 → max (min), при ограничениях 3x1 + x2 ≥ 8, x1 + 2x2 ≥ 6, x1 – x2 ≤ 3, x1 ≥ 0, x2 ≥ 0. Используя графический метод решения, получаем x1* = 2, x2* = 2, fmin(x) = 4, fmах(x) = +∞ (не существует). Будем передвигать линию уровня f(x) = 5x1 + 2.5x2 = 0 целевой функции в направлении ее вектора градиента ∇f(x) = (5, 2.5) до достижения «точки выхода» (точки B) из множестве допустимых решений. Поскольку точка B является точкой пересечения прямых 4x1 + 1,5x2 = 24 и 20x1 + 20x2 ≤ 200, то оптимальное решение имеет вид x1* = 3.6, x2* = 6.4: следует высаживать 3.6 партии деревьев и вскармливать 6.4 бычков. Оптимальное значение целевой функции в данной точке fmax(x) = f(x*) = 34000 тыс. руб. Пример 2.3.2. Решить задачу линейного программирования f(x) = 3x1 + 2x2 → max, при ограничениях x1 + x2 ≤ 6, x1 – 2x2 ≤ 3, x1 ≥ 3, x2 ≥ 0. Используя графический метод решения, получаем x1* = 5, x2* = 1, fmax(x) = 17. Вопросы для самоконтроля 1. Приведите содержательные примеры задачи линейного программирования. 2. Как определяется стандартная форма задачи линейного программирования ? 3. Охарактеризуйте свойства допустимого множества допустимых решений задачи линейного программирования ? 4. Какие свойства имеет оптимальное решение в задаче линейного программмирования ? 5. Суть и возможности геометрического (графического) метода решения задач линейного программирования. Задания для самостоятельной работы ЛЕКЦИЯ 3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 1. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице. (каноническая задача, понятие базисных решений, симплекс-метод) Исходный продукт Расход исходных продуктов на 1 кг мороженого Запас (кг) Сливочное Шоколадное мороженое мороженое Симплекс-метод позволяет эффективно найти оптимальное решение, избегая простого перебора всех возможных угловых точек. Основной принцип метода: вычисления начинаются с какого-то «стартового» базисного решения, а затем ведется поиск решений, «улучшающих» значение целевой функции. Метод универсален, поскольку позволяет решить любую задачу линейного программирования. На основе метода в настоящее время разработаны эффективные программные средства. 3.1. Каноническая задача линейного программирования Молоко 0,8 0,5 400 Наполнители 0,4 0,8 365 Рассмотрим стандартную задачу линейного программирования на нахождение максимума функции. Для использования симплекс-метода эта задача должна быть приведена к каноническому виду: f(x) = с1x1 + с2x2 + … + сnxn → max, Изучение рынка сбыта показало, что: 1) суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг; 2) спрос на шоколадное мороженое не превышает 350 кг сутки. Отпускная цена 1 кг сливочного мороженого 16 ден.ед., шоколадного мороженого 14 ден. ед. Определить, какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным. Задачу решить геометрическим (графическим) методом решения задач линейного программирования. 2. На ферме имеются корма для животных двух видов K1 и K2, содержащие питательные вещества трех типов B1, B2 и B3. Содержание питательных веществ в 1 кг корма каждого вида и норма потребления в день питательных веществ каждого типа приведены в таблице. Число единиц питательных веществ на Норма Питательные 1 кг корма потребления вещества питательных K1 K2 веществ в день (кг) при ограничениях a11x1 + a12x2 + … + a1nxn = b1, a21x1 + a22x2 + … + a2nxn = b2, … am,1x1 + am,2x2 + … + am,nxn = bm xi ≥ 0 (i = 1, … , n), bj ≥ 0 (j = 1, … , m). Сведение исходных основных задач к каноническому виду осуществляется введением, наряду с основными переменными, дополнительных переменных. Например, рассмотренную в разделе 1.4.1 стандартную задачу линейного программирования f (x1, x2) = 10x1 +12x2 → max 4x1 + 5x2 ≤ 300, 2x1 + x2 ≤ 100, 2x1 + 3x2 ≤ 160, x1 ≥ 0, x2 ≥ 0 введением новых переменных x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 можно свести к каноническому виду: ден.ед. B1 3 1 9 B2 1 2 8 B3 1 6 12 Стоимость 1 кг корма K1 равна 12 ден.ед., стоимость 1 кг корма K2 равна 18 Необходимо составить дневной рацион питания животных, имеющий минимальную стоимость, и содержащий питательные вещества каждого типа не менее установленной нормы потребления. Задачу решить геометрическим (графическим) методом решения задач линейного программирования. f (x1, x2) = 10x1 +12x2 → max 4x1 + 5x2 + x3 = 300, 2x1 + x2 + x4 = 100, 2x1 + 3x2 + x5 = 160, xi ≥ 0 (i = 1, … , 5) 3.2. Понятие базисных решений. Симплекс-метод Последовательность вычислений симплекс-методом можно разделить на две основные фазы: 1) нахождение исходной вершины множества допустимых решений; 2) последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции. В некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, в рассматриваемой стандартной задаче нулевой вектор совершенно точно является допустимым решением, хотя и далеко не самым оптимальным. В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный. Рассмотрим линейную систему уравнений a11x1 + a12x2 + … + a1nxn = b1, a21x1 + a22x2 + … + a2nxn = b2, … am,1x1 + am,2x2 + … + am,nxn = bm определяющую каноническую форму рассматриваемой задачи. Пусть A = (aij) – матрица, коэффициенты которой являются коэффициентами данной линейной системы, и пусть rank A = m. В этом случае система имеет m линейно независимых переменных (они называются основными), и n – m неосновных (свободных) переменных. Решения, в которых неосновные (свободные) переменные равны нулю, называются базисными решениями. Число базисных решений конечно и равно Cnm. Теорема 3.2.1 (характеристика оптимального решения). Каждой угловой точке стандартной задачи линейного программирования соответствует допустимое базисное решение линейной системы уравнений, определяющей канонический вид этой задачи, и наоборот. Из теоремы 3.2.1 следует, что максимум целевой функции следует искать среди конечного числа допустимых базисных решений. Используем вариант симплекс-метода без использования таблиц. Шаг 1. Переменные x3, x4, x5 – основные (базисные), x1, x2 – неосновные (свободные). Выразим основные переменные через свободные x3 = 40 + 2x1 – 6x2, x4 = 28 – 3x1 – 2x2, x5 = 14 – 2x1 + x2. Полагая свободные переменные равными нулю, получим первое базисное решение x1 = (0, 0, 40, 28, 14), которому соответствует значение f(x1) = 0. Увеличить значение линейной функции f(x) можно за счет переменной x2, переводя ее в основные переменные. На место x2 из основных в свободные переменные переводится та переменная, которая первая обратится в нуль при росте x2: это переменная x3. При этом уравнение x3 = 40 + 2x1 – 6x2 будет разрешающим. Шаг 2. Переменные x2, x4, x5 – основные (базисные), x1, x3 – неосновные (свободные). Выразим основные переменные через свободные, начиная с разрешающего уравнения x2 = 40/6 + 1/3x1 – 1/6x3, x4 = 28 – 3x1 – 2(40/6 + 1/3x1 – 1/6x3) = 44/3 – 11/3x1 + 1/3x3, x5 = 14 – 2x1 + 40/6 + 1/3x1 – 1/6x3 = 62/3 – 5/3x1 – 1/6x3. Полагая свободные переменные равными нулю, получим второе базисное решение x2 = (0, 40/6, 0, 44/3, 62/3), которому соответствует значение f(x2) = 20. Выразив f(x) через неосновные переменные на этом шаге, получим f(x) = 2x1 + 3(40/6 + 1/3x1 – 1/6x3) = 20 + 3x1 – 1/2x3. Теорема 3.2.2 (критерий оптимальности). Решение стандартной задачи линейного программирования (на максимум целевой функции) является оптимальным, если коэффициенты целевой функции при неосновных (свободных) переменных неположительны. 3.3. Пример применения симплекс-метода (без использования таблиц) Используя симплекс-метод, решим следующую задачу линейного программирования: f(x) = 2x1 + 3x2 → max, –2x1 + 6x2 ≤ 40 3x1 + 2x2 ≤ 28 2x1 – x2 ≤ 14 x1 ≥ 0, x2 ≥ 0. Для этого введением дополнительных переменных приведем задачу к каноническому виду f(x) = 2x1 + 3x2 + 0∙x3 + 0∙x4 + 0∙x5 → max, –2x1 + 6x2 + x3 + 0∙x4 + 0∙x5 = 40 3x1 + 2x2 + 0∙x3 + x4 + 0∙x5 = 28 2x1 – x2 + 0∙x3 + 0∙x4 + x5 = 14 xi ≥ 0 (i = 1, …, 5). Увеличить значение линейной функции f(x) можно за счет переменной x1, переводя ее в основные переменные. На место x1 из основных в свободные переменные переводится та переменная, которая первая обратится в нуль при росте x1: это переменная x4. При этом уравнение x4 = 44/3 – 11/3x1 + 1/3x3 будет разрешающим. Шаг 3. Переменные x1, x2, x5 – основные (базисные), x3, x4 – неосновные (свободные). Выразим основные переменные через свободные, начиная с разрешающего уравнения x1 = 4 + 1/11x3 – 3/11x4, x2 = 40/6 + 1/3(4 +1/11x3 – 3/11x4) – 1/6x3 = 8 – 3/22x3 – 1/11x4, x5 = 62/3 – 5/3(4 + 1/11x3 – 3/11x4) – 1/6x3 = 14 – 7/22x3 + 5/11x4. Полагая свободные переменные равными нулю, получим третье базисное решение x3 = (4, 8, 0, 0, 14), которому соответствует значение f(x3) = 32. Выразив f(x) через неосновные переменные на этом шаге, получим f(x) = 2(4 + 1/11x3 – 3/11x4) + 3(8 – 3/22x3 – 1/11x4) = 32 – 5/22x3 – 9/11x4. Решение x* = x3 = (4, 8, 0, 0, 14) является оптимальным. В соответствии с теоремой 3.2.1 оно соответствует одному из базисных решений линейной системы уравнений, определяющей канонический вид рассматриваемой задачи. В этом случае также в соответствии с теоремой 3.2.2 коэффициенты целевой функции f(x) при неосновных (свободных) переменных неположительны. 3.4. Пример применения симплекс-метода (с использованием таблиц) Снова изучим каноническую задачу линейного программирования, рассмотренную в разделе 3.3: f(x) = 2x1 + 3x2 + 0∙x3 + 0∙x4 + 0∙x5 → max, –2x1 + 6x2 + x3 + 0∙x4 + 0∙x5 = 40 3x1 + 2x2 + 0∙x3 + x4 + 0∙x5 = 28 2x1 – x2 + 0∙x3 + 0∙x4 + x5 = 14 xi ≥ 0 (i = 1, …, 5). Запишем текущий опорный план: x = (0, 20/3, 0, 44/3, 62/3). Шаг 3. Данный опорный план также не является оптимальным, так как в последней строке есть отрицательный элемент (−3) и, следовательно, в базис следует включить вектор x1. Определяем, какой вектор выходит из базиса. Для этого вычисляем (ai0/ai1) при ai1 > 0 (i = 1,2,3): min (44/3:11/3, 62/3:5/3) = 4 соответствует строке 2. Из базиса выходит вектор x2. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 1, 3, 4 со строкой 2, умноженной на 1/11, −5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент. Симплексная таблица примет следующий вид: Используем вариант симплекс-метода с использованием таблиц. Матрица коэффициентов A = (aij) и правая часть ограничений системы уравнений имеют соответственно вид: Шаг 1. Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка включает коэффициенты целевой функции, умноженной на −1. Последние три векторы столбцы образуют базис в трехмерном пространстве. Следовательно базисные переменные xb = (x3, x4, x5), а свободные переменные xf = (x1, x2). Запишем текущий опорный план: x = (4, 8, 0, 0, 14). Текущий опорный план является оптимальным, так как в строках 4 под переменными x1, x2, x3, x4, x5 нет отрицательных элементов. Оптимальное решение имеет вид x1*= 4, x2*= 8, x3*= x4*= 0, x5*= 14. Оптимальное значение целевой функции в данной точке fmax(x) = f(x*) = 32. Вопросы для самоконтроля Запишем текущий опорный план: x = (0, 0, 40, 28, 14). Данный опорный план не является оптимальным, так как в последней строке симплексной таблицы есть отрицательные элементы. Самый большой по модулю отрицательный элемент (−3) и, следовательно, в базис следует включить вектор x2. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (ai0/ai2) при ai2 > 0 (i = 1,2,3): min (40/6, 28/2) = 20/3 соответствует строке 1. Из базиса выходит вектор x3. Шаг 2. Сделаем исключение Гаусса для столбца x2, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент. Симплексная таблица примет следующий вид: 1. Что такое каноническая задача линейного программирования ? 2. Понятие базисных решений. 3. Дайте характеристику оптимального решения стандартной задачи линейного программирования. 4. Сформулируйте критерий оптимальности стандартной задачи линейного программирования. 5. Сущность симплекс-метода. Задания для самостоятельной работы 1. Используя симплекс-метод, дать решение стандартной задачи линейного программирования: f(x) = 4x1 + 6x2 → max, 2x1 + x2 ≤ 64 x1 + 3x2 ≤ 72 x2 ≤ 20 x1 ≥ 0, x2 ≥ 0. ЛЕКЦИЯ 4. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (двойственные задачи, теоремы двойственности) Каждой задаче линейного программирования можно поставить в соответствие другую задачу, называемую двойственной. Совместное изучение этих задач позволяет лучше понять сущность моделируемых экономических процессов. 4.1. Двойственные задачи линейного программирования Пусть исходная задача линейного программирования является задачей оптимального планирования выпуска продукции: предприятие занимается изготовлением m видов продукции P1, P2, … , Pm при использовании n видов ресурсов S1, S2, … , Sn; запасы ресурсов b1, b2, … , bn; числа aij определяют число единиц ресурсов Si, затрачиваемых на изготовление единицы продукции Pj. Прибыль, получаемая от единицы продукции P1, P2, … , Pm (внешние рыночные цены) равны соответственно с1, с2, … , сm (ден. ед.). Вид ресурса Запас ресурса (единиц) Число единиц ресурсов, затрачиваемых на изготовление единицы продукции P1 P2 … Pm S1 b1 a11 a12 … a1m S2 b2 a21 a22 … a2m … … … … … … Sn bn an1 an2 … anm В данном случае соотношение между исходной и двойственной задачами определяется следующим образом. Задача 1 (исходная) f(x) = с1x1 + с2x2 + … + сnxn → max, a11x1 + a12x2 + … + a1nxn ≤ b1, a21x1 + a22x2 + … + a2nxn ≤ b2, … am1x1 + am2x2 + … + amnxn ≤ bm, xi ≥ 0 (i = 1, … , n); Задача 2 (двойственная) Правила составления задачи, двойственной по отношению к исходной задаче линейного программирования сводятся к следующему. 1) Выписывается матрица A коэффициентов при переменных исходной задачи, полученных после преобразований, описанных в предыдущем пункте, и составляется матрица AT, транспонированная относительно матрицы A. 2) Составляется система ограничений двойственной задачи, в которой в качестве коэффициентов при переменных – элементы матрицы AT, а в качестве свободных членов – коэффициенты при переменных в целевой функции: a11y1 + a21y2 + … + am1ym ≥ c1, a12y1 + a22y2 + … + am2ym ≥ c2, … a1ny1 + a2ny2 + … + amnym ≥ cm. 3) Составляется линейная целевая функция двойственной задачи (y) = b1y1 + b2y2 + … + bmym, в которой за коэффициенты при переменных принимаются свободные члены системы ограничений исходной задачи. 4) Указывается, что при решении двойственной задачи ищется минимум функции цели: (y) → min. 5) Записывается условие неотрицательности переменных двойственной задачи: yi ≥ 0 (i = 1, … , m). Замечание 4.2.1. 1) Компоненты оптимального решения y*= (y1*, y2*, … , ym*) двойственной задачи называются оптимальными двойственными оценками (учетными, неявными, теневыми) исходной задачи, которые определяют степень дефицитности ресурсов. Л.В. Канторович назвал эти оценки объективно обусловленными. Указанные оценки определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т.е. полностью используемые ресурсы) получают ненулевые оценки, а недефицитные – нулевые оценки. 2) Задачи 1 и 2, обладающие указанными свойствами, являются симметричными взаимно двойственными задачами, в отличие от более общих двойственных задач. (y) = b1y1 + b2y2 + … + bmym → min, 4.2. Теоремы двойственности a11y1 + a21y2 + … + am1ym ≥ c1, a12y1 + a22y2 + … + am2ym ≥ c2, … a1ny1 + a2ny2 + … + amnym ≥ cm, yi ≥ 0 (i = 1, … , m). Теорема 4.2.1 (первая или основная теорема двойственности). Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: fmax(x) = min(y) или f(x*) = (y*). 2. Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы. Задача 1 (исходная): cоставить план x*= (x1*, x2*, … , xn*) выпуска продукции, при котором прибыль (выручка) от реализации продукции будет максимальной, при условии, что потребление ресурсов по каждому виду продукции не превышает имеющихся запасов. Задача 2 (двойственная): найти набор цен (оценок) ресурсов y*= (y1*, y2*, … , ym*), при котором общие затраты на ресурсы будут минимальными, при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции. Экономический смысл основной теоремы двойственности. 1) План производства x*= (x1*, x2*, … , xn*) и набор цен ресурсов y*= (y1*, y2*, … , ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от реализации продукции при «внешних» (известных заранее) ценах с1, с2, … , сn, равна затратам на ресурсы при «внутренних» (определяемых из решения задачи) ценах y1*, y2*, … , ym*. Для всех других планов x и y обеих задач прибыль (выручка) всегда меньше или равна затратам на ресурсы. 2) Предприятию безразлично, производить ли продукцию по оптимальному плану x*= (x1*, x2*, … , xn*) и получать максимальную прибыль (выручку) fmax(x), либо продавать ресурсы по оптимальным ценам y*= (y1*, y2*, … , ym*) и возместить от продажи равные ей минимальные затраты на ресурсы min(y). Теорема 4.2.2 (вторая теорема двойственности). Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. Пример 4.2.1. Предприятие занимается изготовлением двух видов продукции P1 и P2 при использовании четырех видов ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в Таблице. Прибыль, получаемая от единицы продукции P1 и P2 (внешние рыночные цены) соответственно с1 = 2 и с2 = 3 (ден. ед.). Вид ресурса Запас ресурса (единиц) Число единиц ресурсов, затрачиваемых на изготовление единицы продукции P1 P2 S1 18 1 3 S2 16 2 1 S3 5 – 1 S4 21 3 – Рассмотрим две задачи оптимизации. Задача 1 (оптимального планирования производства): cоставить план x*= (x1*, x2*) объемов выпуска продукции P1 и P2, при котором прибыль (выручка) от реализации продукции будет максимальной, при условии, что потребление ресурсов по каждому виду продукции не превышает имеющихся запасов. Задача 2 (двойственная): найти объективно обусловленные цены (оценки) ресурсов y*= (y1*, y2*), при котором общие затраты на ресурсы будут минимальными, при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции. Экономико-математическая модель задачи 1 определяется следующим образом: f(x) = 2x1 + 3x2 → max, x1 + 3x2 ≤ 18 2x1 + x2 ≤ 16 0∙x1 + x2 ≤ 5 3x1 + 0∙x2 ≤ 21 x1 ≥ 0, x2 ≥ 0. Канонический вид задачи 1: f(x) = 2x1 + 3x2 + 0∙x3 + 0∙x4 + 0∙x5 + 0∙x6 → max, x1 + 3x2 + x3 + 0∙x4 + 0∙x5 + 0∙x6 = 18 2x1 + x2 + 0∙x3 + x4 + 0∙x5 + 0∙x6 = 16 0∙x1 + x2 + 0∙x3 + 0∙x4 + x5 + 0∙x6 = 5 3x1 + 0∙x2 + 0∙x3 + 0∙x4 + 0∙x5 + x6 = 21 xi ≥ 0 (i = 1, … , 6). Оптимальное решение этой задачи имеет вид (само решение здесь не приводится, но может быть получено симплекс-методом) x* = (x1*, x2*, x3*, x4*, x5*, x6*) = (6, 4, 0, 0, 1, 3), fmax(x) = f(x*) = 24. Это решение показывает, что: 1) x1* = 6, x2* = 4 (ед) являются оптимальными объемами выпуска продукции P1 и P2; 2) ресурсы S1 и S2 использованы полностью (остатки x3* и x4* этих ресурсов – нулевые), а по ресурсам S3 и S4 имеются остатки: x5* = 1, x6* = 3 (ед). Кроме того, можно показать, что в процессе решения задачи 1 симплекс-методом целевая функция f(x), выраженная через неосновные переменные ее оптимального решения, имеет вид f(x) = 24 – (4/5)x3 – (3/5)x5. Заметим, что в соответствии с теоремой 3.2.2 коэффициенты при x3 и x5 – неположительны. Экономико-математическая модель задачи 2 определяется следующим образом: (y) = 18y1 + 16y2 + 5y3 + 21y4 → min, y1 + 2y2 + 3y4 ≥ 2 3y1 + y2 + y3 ≥ 3 yi ≥ 0 (i = 1, … , 4). Канонический вид задачи 2: (y) = 18y1 + 16y2 + 5y3 + 21y4 + 0∙y5 + 0∙y6 → min, y1 + 2y2 + 3y4 + y5 + 0∙y6 = 2 3y1 + y2 + y3 + 0∙y5 + y6 = 3 yi ≥ 0 (i = 1, … , 6). Оптимальное решение этой задачи имеет вид (само решение здесь не приводится, но может быть получено симплекс-методом): y* = (y1*, y2*, y3*, y4*, y5*, y6*) = (4/5, 3/5, 0, 0, 0, 0), * min(y) = (y ) = 24. Это решение показывает, что: 1) y1* = 4/5, y2* = 3/5 (ден. ед) являются объективно обусловленными ценами ресурсов S1 и S2, в то время как аналогичные цены на ресурсы S3 и S4 – нулевые; 2) нет превышения затрат на ресурсы над ценами их реализации, поскольку y5* = * y6 = 0 (например, если бы y5* > 0, то в этом случае по оптимальному плану производства производить продукцию P1 не следовало). Заметим, что f(x*) = (y*) в соответствии с теоремой 4.2.1, и значения y1* = 4/5, y2* = 3/5 (ден. ед) соответствуют утверждению теоремы 4.2.2. Пример 4.2.2. Рассмотрим двойственную задачу для задачи линейного программмирования, рассмотренной в разделе 3.3: f(x) = 2x1 + 3x2 → max, –2x1 + 6x2 ≤ 40 3x1 + 2x2 ≤ 28 2x1 – x2 ≤ 14 x1 ≥ 0, x2 ≥ 0. Для этого введением дополнительных переменных приведем задачу к каноническому виду: f(x) = 2x1 + 3x2 + 0∙x3 + 0∙x4 + 0∙x5 → max, –2x1 + 6x2 + x3 + 0∙x4 + 0∙x5 = 40 3x1 + 2x2 + 0∙x3 + x4 + 0∙x5 = 28 2x1 – x2 + 0∙x3 + 0∙x4 + x5 = 14 xi ≥ 0 (i = 1, …, 5). Экономико-математическая модель двойственной задачи определяется следующим образом: (y) = 40y1 + 28y2 + 14y3 → min, –2y1 + 3y2 + 2y3 ≥ 2 6y1 + 2y2 – y3 ≥ 3 yi ≥ 0 (i = 1, 2, 3). На основании теорем 4.2.1 и 4.2.2 имеем: y* = (y1*, y2*, y3*, y4*, y5*) = (5/22, 9/11, 0, 0, 0, 0), * min(y) = (y ) = 32. Вопросы для самоконтроля 1. Сформулируйте двойственную задачу линейного программирования для задачи оптимального планирования производства продукции. 2. Сформулируйте теоремы двойственности. 3. Экономическая интерпретация двойственных переменных. Задания для самостоятельной работы 1. Используя симплекс-метод, дайте решение задач линейного программирования, рассмотренных в примере 4.2.1. 2. Рассмотрите двойственную задачу для задачи 1 линейного программирования, рассмотренной в заданиях для самостоятельной работы в Лекции 2. ЛЕКЦИЯ 5. КЛАССИЧЕСКИЕ ЗАДАЧИ ОПТИМИЗАЦИИ К классическим относятся задачи, рассмотренные в работах П. Ферма, И. Ньютона, Г.В. Лейбница, Ж.Л. Лагранжа, и составляющие теоретическую основу методов оптимизации. Эти задачи с той или иной степенью полноты рассматриваются в общих курсах математического анализа. 1) Задачи одномерной оптимизации f(x1) → extr, x1 ∈ R1; 2) Задачи безусловной многомерной оптимизации (unconstrained optimization) f(x) → extr, x = (x1, x2, … , xn) ∈ Rn. 3) Задачи условной многомерной оптимизации при ограничениях типа равенств (equality constrained optimization) f(x) → extr, hi(x) = 0 (i = 1, … , m). 5.1. Задачи одномерной оптимизации В простейшем случае функция f = f(x1) зависит только от одной независимой переменной x1. В этом случае можно получить наглядные и легко интерпретируемые результаты, составляющие теоретическую основу всех методов оптимизации. Ключевым является понятие точек локального экстремума (локального максимума или минимума) функции f = f(x1) во внутренних точках множества x1 ∈ D ∈ R1: точка x1*∈ D − точка локального экстремума, если в множестве существует такая окрестность D* этой точки, что f(x1) ≥ f(x1*) или f(x1) ≤ f(x1*) для всех x1 ∈ D*. Существование (или не существование) точек локального экстремума зависит от конкретного вида функции f = f(x1) во внутренних точках множества D. Другим ключевым является понятие точки глобального экстремума (максимума или минимума) функции f = f(x1) на всем множестве x1 ∈ D ∈ R1: точка x1*∈ D − точка глобального экстремума, если f(x1) ≥ f(x1*) или f(x) ≤ f(x1*) для всех x1 ∈ D. Существование (или не существование) точки глобального экстремума непрерывной функции f = f(x1) зависит от топологической структуры множества D. Так, если функции f = f(x1) непрерывна на компактном (замкнутом и ограниченном) множестве, то на основании известной теоремы Вейерштрасса (K.T.W. Weierstraß (1815-1897)) на этом множестве существуют точки глобального максимума и минимума функции. Если множество некомпактно, то возможны точки только глобального максимума или только глобального минимума. 5.1.1. Задача одномерной безусловной оптимизации. Допустим, что ограничения на переменную x1 отсутствуют, и мы имеем одномерную задачу оптимизации в неограниченной области f(x1) → extr, x1 ∈ R1. Первый общий подход к решению экстремальных задач разработан Пьером Ферма по-видимому в 1629 г., но впервые достаточно полно изложен в письме к Ж.П. Робервалю в 1638г. (см. Р. Декарт. Геометрия. М.Л.: ГОНТИ, 1938. с.154). П. Ферма говорит о том, что при приближении к точке оптимума скорость изменения функции падает до нуля. На современной языке прием П. Ферма сводится к тому, что в точке экстремума x1* в задаче без ограничений f(x1) → extr должно иметь место равенство f /(x1*) = 0. Первый намек на этот результат содержится в словах Й. Кеплера из его «Стереометрии винных бочек». Точный смысл рассуждения П. Ферма приобрели только в 1684г. после выхода работы Г.В. Лейбница «Nova methods pro maximus et minimus ...», в которой Лейбниц не только получил в качестве необходимого условия экстремума соотношение f /(x1*) = 0 (сейчас этот результат носит название теоремы Ферма), но и употребил второй дифференциал для различения максимумов и минимумов. Следует, конечно, знать, что большинство результатов Лейбница было известно И. Ньютону, но его работа «Метод флюксий», завершенная в основном виде в 1671г., была опубликована только в 1736г. Теорема 5.1.1. Пусть функция f = f(x1) определена и дважды непрерывно дифференцируема на интервале x1∈ (a, b). 1) Необходимые условия локального экстремума: eсли x1*∈ (a, b) − точка локального экстремума функции f(x1), то f /(x1*) = df(x1*)/dx1 = 0. 2) Необходимые условия локального минимума (максимума): eсли x1*∈ (a, b) − точка локального минимума (максимума) функции f(x1*), то f //(x1*) = d2f(x1*)/dx12 ≥ 0 (f //(x1*) ≤ 0). ствительно, для функции f = x14 в точке x1 = 0 условие ∇2f(x1*) > 0 не выполнено, однако эта точка является точкой минимума указанной функции. Рассмотрим также для наглядности некоторые возникающие ситуации, касающиеся точек экстремума: 1) экстремума нет, первая производная равна нулю; 2) точка максимума, первая производная слева и справа бесконечна; 3) экстремума нет, первая производная слева и справа бесконечна; 4) точка минимума, первая производная слева не равна первой производной cправа; 5) экстремума нет, первая производная слева не равна первой производной справа. Пример 5.1.1. Исследовать на экстремум функцию f(x1) = (x12 – 1)2/3. 3) Достаточные условия локального минимума (максимума): eсли x1* − точка локального экстремума функции f (x1*) и выполняются условия Решение. Найдем стационарные точки (точки подозрительные на экстремум) экстремума функции из условия f //(x1*) > 0 (f //(x1*) < 0), f / = (4/3)(x12 – 1)-1/3x1 = 0, то точка x1* является точкой локального минимума (максимума). * Дополнение 1 к теореме 5.1.1. Пусть в точке x1 первые n – 1 производные функции обращаются в нуль, а производная порядка n отлична от нуля. Тогда: 1) если n – нечетное, то x1* – точка перегиба; 2) если n – четное, то x1* – точка локального оптимума; если, кроме того, эта производная положительная (отрицательная), то x1* – точка локального минимума (максимума). Дополнение 2 к теореме 5.1.1. Если функция f(x1) выпукла (вогнута) при x1 ∈ [a, b] и x1*∈ (a, b) − точка локального экстремума этой функции, то точка x1* является точкой минимума (максимума) при x1 ∈ [a, b]. Замечание 5.1.1. 1) Условие 1) теоремы 5.1.1 является только необходимым, но не достаточным. Действительно, для функции f = x13 в точке x1 = 0 выполнено условие теоремы 1.1.1, однако эта точка не является точкой экстремума. Действительно, рассмотрим разность f(x1) − f(0) = x13. Она больше нуля при всех x1 > 0 и меньше нуля при x1 < 0. Точка x1 = 0 является точкой перегиба или седловой точкой. Этот же пример показывает, что условие 2) теоремы 5.1.1 также является только необходимым. В связи с дополнением к теореме 5.1.1 отметим также, что: для функции f = x13 в точке x1 = 0 выполнены условия f./ = f // = 0, f /// = 6 > 0 (n = 3 – нечетное); для функции f = x14 в точке x1 = 0 выполнены условия f./ = f // = f /// = 0, f //// = 24 > 0 (n = 4 – четное). 2) К точкам, подозрительным на экстремум, относятся также точки, где производная функции f = f(x1) не существует. 3) Условие 3) теоремы 5.1.1 также является достаточным, но не необходимым. Дей- принимая во внимание также точки, где производная не существует. Получаем следующие стационарные точки: x1 = –1, x1 = 0, x1 = 1. Изменение функции в окрестности стационарных точек определяется следующим образом: Поэтому точки x1 = ±1 являются точками минимума, а точка при x1 = 0 – точкой максимума. 5.1.2. Задача одномерной оптимизации на множестве. Пусть требуется найти максимум (минимум) непрерывной функции f = f(x1) на отрезке x1 ∈ [a, b]. Вследствие компактности (замкнутости и ограниченности) множества x1 ∈ [a, b] такая задача имеет решение на основании теоремы Вейерштрасса. Для этого следует выбрать максимальное (минимальное) из значений функции в точках экстремума на интервале (a, b) и на концах отрезка (в точках a и b). Если функция f не только непрерывна, но и дважды дифференцируема на интервале (a, b), для нахождения точек экстремума и выбора максимального (минимального) из значений функции можно ис- пользовать теорему 5.1.1. Замечание 5.1.2. 1) Теорема Вейерштрасса дает только достаточные, но не необходимые условия глобального экстремума (максимума или минимума) функции f = f(x1) на множестве x1 ∈ D. Например, функция f = x12: − на некомпактном множестве D = (0,1] имеет максимум, хотя и не имеем минимума; − на некомпактном множестве D = [0,1) имеет минимум, но не имеет максимума; − на некомпактном множестве D = (0,1) не имеет ни минимума, ни минимума. 2) Таким образом, причина отсутствия локального экстремума функции f = f(x1) в точке x1*, где f /(x1*) = 0, объясняется «седловым характером» этой точки, т.е. свойствами самой функции в окрестности точки x1*. В то же время причина отсутствия глобального максимума или минимума функции f = f(x1) на множестве x1 ∈ D связана с топологической структурой этого множества. Пример 5.1.2. На отрезке x1∈ [0, 3] найти наибольшее и наименьшее значение функции D − точка локального минимума (максимума) функции f(x), то ∇2f(x*) ≥ 0: A ≥ 0 (A ≤ 0), AB – C2 ≥ 0, A = ∂2f(x*)/∂x12, B = ∂2f(x*)/∂x22, C = ∂2f(x*)/∂x1∂∂x2; 3) Достаточные условия локального минимума (максимума максимума): Если x* = (x1*, x2*) ∈ D − точка локального экстремума функции f(x) и выполняются условия ∇2f(x*) > 0: A > 0 (A < 0), AB – C2 > 0 то точка x* = (x1*, x2*) является точкой локального минимума (максимума максимума). Замечание 5.2.1. 1) Условие 1) теоремы 5.2.1 является только необходимым, но не достаточным. Классический пример: функция f = x12 – x22, у которой точка x1 = x2 = 0 является точкой минимакса (седловой седловой точкой). f = (2/3)x13 – (5/2)x12 + 2x1. Решение. Найдем точки экстремума функции из условия f / = 2x12 – 5x1 + 2 = 0: это точки x1 = ½ и x1 = 2, которые принадлежат отрезку x1∈ [0, 3]. Поскольку f //(½) = – 3 < 0, а f //(2) = 3 > 0, то точка x1 = ½ является точкой локального максимума f(½) = 11/24, а точка x1 = 2 – точкой локального минимума функции f(2) = – 2/3. На концах отрезка x1∈ [0, 3] имеем f(0) = 0, f(3) = 3/2 и, следовательно, fmax = 3/2, fmin = – 2/3 на отрезке x1∈ [0, 3]. 5.2. Задачи многомерной безусловной оптимизации Рассмотрим задачу оптимизации функции многих переменных в неограниченной области f(x) → extr, x = (x1, x2, … , xn) ∈ Rn. Для наглядности будем анализировать два случая. 1) n = 2, когда f = f(x1, x2) (функция f зависит от двух переменных x1, x2; 2) общий случай f = f(x) (функция f зависит от n переменных x1, … , xn). 5.2.1. Случай функции двух переменных (n = 2). Этот случай обладает геометрической наглядностью, а также относительной простотой и «алгебраической» наглядностью условий, что важно для понимания используемых методов оптимизации. Теорема 5.2.1. Пусть функция f = f(x1, x2) дважды непрерывно дифференцируема в некоторой области D ∈ R2. 1) Необходимые условия локального экстремума: eсли x* = (x1*, x2*) ∈ D − точка локального экстремума функции f(x), то ∇f(x*) = 0: ∂f(x*)/∂x1 = ∂f(x*)/∂x2 = 0. 2) Необходимые условия локального минимума (максимума): ecли x* = (x1*, x2*) ∈ Впрочем, минимакс не обязательно является характеристикой такого рода точек. Так для функций f = x13 ± x23, f = x13 ± x22 и f = x12 ± x23 точка x1 = x2 = 0 является точкой минимакса, однако условие ∇f(x*) = 0 не является условием локального максимума (минимума). Например, для функции f = x12 + x23 условия экстремума ∇ ∇f(x*) = 0 имеют вид 2x1 = 0, 3x22 = 0 и точка x1 = x2 = 0 будет единственной точкой экстремума экстремума. Однако в этой точке нет экстремума. Действительно Действительно, рассмотрим разность f(0, x2) − f(0, 0) = x23. Она больше нуля при всех x2 > 0 и меньше нуля при x2 < 0. Достаточное условие минимума (максимума) также не выполняется выполняется, поскольку в данном случае A = 2, B = 6x2, C = 0, и в точке x1 = x2 = 0 условие AB – C2 > 0 не выполняется. 2) Условие теоремы 3) теоремы 5.2.1 также является достаточным достаточным, но не необходимым. Действительно, для функции f = x14 + x22 в точке x1 = x2 = 0 условие ∇2f(x1*) > 0 не выполнено, однако эта точка является точкой минимума указанной функции. 3) Пусть требуется найти максимум (минимум) непрерывной функции f = f(x1, x2) на компактном множестве x ∈ K. По теореме Вейерштрасса такая задача имеет решение. Для этого следует выбрать максимальное (минимальное) из значений функции во внутренних точках множества K и на его границе. Если функция f не только непрерывна, но и дважды дифференцируема во внутренних точках множества K, для нахождения точек экстремума и выбора максимального (минимального минимального) из значений функции можно использовать теорему 5.2.1. Пример 5.2.1. Исследовать на экстремум функцию f(x1, x2) = 4x12 – 6x1x2 – 34x1 + 5x22 + 42x2 + 7. Решение. Найдем точки экстремума функции из условия ∇f( f(x*) = 0: ∇2f(x*) ≥ 0 (∇2f(x*) ≤ 0). ∂f(x1, x2)/∂x1 = 8x1 – 6x2 – 34 = 0, ∂f(x1, x2)/∂x2 = – 6x1 + 10x2 + 42 = 0. 3) Достаточные условия локального минимума (максимума): eсли x* ∈ D − точка локального экстремума функции f(x) и выполняются условия Получаем единственную точку экстремума x1 = 2, x2 = – 3. В данном случае A = ∂2f(x1, x2)/∂x12 = 8, B = ∂2f(x1, x2)/∂x22 = 10, C = ∂2f(x*)/∂x1∂x2 = – 6. ∇2f(x*) > 0 (∇2f(x*) < 0), то точка x* является точкой локального минимума (максимума). Поскольку A > 0, AB – C2 = 44 > 0, то найденная точка экстремума является точкой минимума. Таким образом получаем fmin = – 90. 5.2.2. Общий случай. В общем случае для формулировки условий разрешимости задач безусловной оптимизации используются понятия: 1) градиента функции f(x), введенного английским физиком Джемсом Максвеллом (J.C. Maxwell (1831-1879); 2) понятие матрицы Гессе, получившей название по имени немецкого математика Людвига Гессе (L. Hesse (1811-1874)). Градиентом ∇f(x) функции называется вектор ∇f(x) = {∂f(x)/∂x1, ∂f(x)/∂x2, … , ∂f(x)/∂xn}. Матрицей Гессе ∇2f(x) для функции f(x) называется матрица A = {aij}, элементы aij которой являются частными производными второго порядка aij = ∂2f(x)/∂xi∂xj функции f(x):  ∂ 2 f (x ) / ∂x12 , ∂ 2 f ( x) / ∂x1∂x2 ,  2 2 2  ∂ f (x ) / ∂x2 ∂x1 , ∂ f (x) / ∂x2 , ∇ 2 f ( x) =  ...   ∂ 2 f (x ) / ∂x ∂x , ∂ 2 f (x) / ∂x ∂x , n 1 n 2  … , ∂ 2 f (x ) / ∂x1∂xn   … , ∂ 2 f (x ) / ∂x2 ∂xn   .  … , ∂ 2 f ( x) / ∂xn2  Матрица Гессе положительно определена (в этом случае пишут ∇2f(x*) ≥ 0), если все ее главные диагональные миноры ∆i(x) положительны (∆i(x) ≥ 0), и строго положительно определена (в этом случае пишут ∇2f(x*) > 0), если все ∆i(x) > 0. Соответственно, матрица Гессе отрицательно определена (в этом случае пишут ∇2f(x*) ≤ 0), если ее главные диагональные миноры ∆i(x) последовательно меняют знак с “≤” на “≥”, начиная с знака “≤”, и строго отрицательно определена (в этом случае пишут ∇2f(x*) < 0), если ∆i(x) последовательно меняют знак с “<” на “>”, начиная с знака “<”. Теорема 5.2.2. Пусть функция f = f(x) дважды непрерывно дифференцируема в некоторой области D ∈ Rn. 1) Hеобходимые условия локального экстремума: eсли x*∈ D − точка локального экстремума функции f(x), то * * * Замечание 5.2.2. 1) Необходимые условия экстремума задают систему уравнений относительно x*. Эти уравнения нелинейны (за исключением случая квадратичной функции f(x)) и их решение в явном виде невозможно. Подлинное значение этих условий в другом: на их основе строятся численные методы отыскания решений и оценивается скорость их сходимости, а также анализируется устойчивость этих методов. 2) Условия ∇2f(x*) ≥ 0 (∇2f(x*) ≤ 0) и ∇2f(x*) > 0 (∇2f(x*) < 0) теоремы 1.2.2 можно записать в иной (также часто используемой и эквивалентной) форме, если использовать второй дифференциал функции f(x): d2f(x) = ΣiΣj[∂2f(x)/∂xi∂xj]dxidxj. Если матрица Гессе положительно (или строго положительно) определена, то d2f(x) ≥ 0 (или d2f(x) > 0), т.е. второй дифференциал является определенно положительным (или строго определенно положительным) на основании критерия Сильвестра (по имени английского математика Джеймса Сильвестра (J.J. Silvester (1814-1897)). Соответственно, если матрица Гессе (строго) отрицательно или строго отрицательно определена, то второй дифференциал d2f(x) ≤ 0 или d2f(x) < 0 (является определенно отрицательным или строго определенно отрицательным). Вопросы для самоконтроля 1. Достаточное условие существования глобального максимума (теорема Вейерштрасса). 2. Назовите причины отсутствия оптимального решения. 3. Понятие локального экстремума. 4. Условия, когда локальный максимум является глобальным. 5. Сформулируйте понятия градиента функции и матрицы Гессе. Задания для самостоятельной работы 1. На отрезке x1∈ [–1, 2] найти наибольшее и наименьшее значение функции f (x1) = 2x13 – 12x12 + 18x1 + 3. (Ответ: fmax = 11, fmin = – 29.) 2. Исследовать на экстремум функцию * ∇f(x ) = 0: ∂f(x )/∂x1 = ∂f(x )/∂x2 = … = ∂f(x )/∂xn = 0. f(x1, x2) = x12 + x1x2 + x22 – 3x1 – 6x2. 2) Hеобходимые условия локального минимума (максимума): eсли x ∈ D − точка локального минимума (максимума) функции f(x), то матрица Гессе ∇2f(x) этой функции удовлетворяет условиям * (Ответ: x1 = 0, x2 = 3 – единственная точка экстремума, являющаяся точкой минимума; fmin = – 9.) ЛЕКЦИЯ 6. МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА В 1788 г. Ж.Л. Лагранж (J.L. Lagrange (1736-1813)) сформулировал знаменитое правило множителей для задач нахождения экстремума функций многих переменных при наличии ограничений типа равенств. В экономике этот метод впервые применил (≈ 1876г.) датский экономист Гарольд Вестергард (H.L. Westergard (1853-1936)). 6.1. Общая идея метода множителей Лагранжа Общая идея Лагранжа состоит в том, чтобы свести задачу условной (при ограничениях типа равенств) оптимизации к задаче безусловной оптимизации для некоторой другой функции, «включающей» ограничения. Такая функция получила название функции Лагранжа, а сам метод решения называют методом множителей Лагранжа. Рассмотрим задачу f(x) → extr hj(x) = 0 (j = 1, … , m). Следуя Лагранжу, будем использовать функцию вида L(x, λ) = λ0f(x) + λ1h1(x) + … + λmhm(x), где λ0, λj − множители Лагранжа, удовлетворяющие условию λ0 + λ12 + …+ λm2 = 1. 6.2. Необходимые условия локального экстремума В данном случае для формулировки условий оптимизации вводится понятие матрицы Гессе ∇2L(x*, λ) функции L(x*, λ):  ∂ 2 L( x* , λ ) / ∂x12 , ∂ 2 L (x* , λ ) / ∂x1∂x2 ,  2 * 2 * 2  ∂ L( x , λ ) / ∂x2 ∂x1 , ∂ L ( x , λ ) / ∂x2 , ∇ 2 L ( x* , λ ) =  ...   ∂ 2 L( x* , λ ) / ∂x ∂x , ∂ 2 L (x* , λ ) / ∂x ∂x , n 1 n 2  … , ∂ 2 L (x* , λ ) / ∂x1∂xn   … , ∂ 2 L (x* , λ ) / ∂x2 ∂xn  .  … , ∂ 2 L ( x* , λ ) / ∂xn2  Теорема 6.2.1 (необходимые условия локального условного экстремума). Пусть функции f = f(x), hj(x) дважды непрерывно дифференцируемы в некоторой области D ∈ Rn. Если x* ∈ D − точка локального экстремума функции f(x), то найдутся числа λ0 и λj такие, что λ0 и λ12 + …+ λm2 не равны нулю одновременно, для которых выполняются условия ∂L(x*, λ)/∂xi = λ0[∂f(x*)/∂xi] + λ1[∂h1(x*)/∂xi] + … + λm[∂hm(x*)/∂xi] = 0, hj(x) = 0. Для того, чтобы λ0 ≠ 0 (λ0 = 1) достаточно, чтобы векторы ∇h1(x*) = {[∂h1(x*)/∂x1], … , [∂h1(x*)/∂xn]} … ∇hm(x*) = {[∂hm(x*)/∂x1], … , [∂hm(x*)/∂xn]} были линейно независимы. Замечание 6.2.1. 1) Со времен Ж.Л. Лагранжа почти на протяжении целого столетия правило множителей Лагранжа формулировалось в случае λ0 = 1, хотя без дополнительных предположений (называемых условием регулярности) это не верно. Рассмотрим, например, задачу f(x) = x1→ extr, x12 + x22 = 0. Очевидным и единственным решение этой задачи является точка x* = (0, 0). Используя функцию Лагранжа L(x, λ1) = x1 + λ1(x12 + x22) получаем условия экстремума в виде 1 + 2λ1x1 = 0, 2λ1x2 = 0, x12 + x22 = 0, где первое соотношение противоречит третьему. В то же время используя функцию Лагранжа L(x, λ) = λ0x1 + λ1(x12 + x22), получаем условия экстремума в виде λ0 + 2λ1x1 = 0, 2λ1x2 = 0, x12 + x22 = 0; эти условия дают решение x1 = x2 = λ0 = 0, λ1 = с ≠ 0. 2) В качестве условия регулярности обычно используется условие линейной независимости векторов ∇h1(x*), …, ∇hm(x*). Однако проверка этого условия обычно сложнее, чем непосредственная проверка того, что λ0 ≠ 0 в функции Лагранжа. Поэтому общая формулировка теоремы 1.3.1, не использующая никаких дополнительных предположений, очень удобна и часто используется. 3) Условия стационарности в теореме 6.2.1 часто записывают в эквивалентной «симметричной» форме ∂L(x*, λ)/∂xi = 0, ∂L(x*, λ)/∂λj = 0. 4) Метод множителей Лагранжа задает систему уравнений относительно x*, λ. Эти уравнений нелинейны (за исключением случая квадратичной функции f(x) и линейных функций hj(x)) и их решение в явном виде невозможно. Как и в случае безусловной оптимизации подлинное значение этих условий в том, что на их основе строятся численные методы отыскания решений и оценивается скорость их сходимости. Замечание 6.2.2. Если ограничения hj(x) = 0 представить в виде hj(x) = bj (j = 1, … , m) и интерпретировать функцию f(x) как прибыль, а bj − как объемы имеющихся в наличии ресурсов, то множители Лагранжа будут численно равны изменению прибыли при единичном изменении этих ресурсов. Другими словами, множители Лагранжа численно равны «теневым» ценам ресурсов. 6.3. Условия локального минимума (максимума) Введем понятие касательного подмножества S = {x: (∇hk(x), x) = 0, k = 1, … , m} в Rn, в котором (а не на всем Rn) можно сформулировать условия оптимизации: соответствующие условия на матрицу Гессе ∇2f(x) или на второй дифференциал d2f(x). Теорема 6.3.1. Пусть функции f = f(x), hj(x) дважды непрерывно дифференцируемы в некоторой области D ∈ Rn. 1) Необходимое условие локального условного минимума (максимума): если x* ∈ D − точка локального условного минимума (максимума) функции f(x) и выполняются условия регулярности (λ0 = 1), то матрица Гессе ∇2L(x*, λ) функции L(x*, λ) в касательном подпространстве S удовлетворяет условию ∇2L(x*, λ) ≥ 0 (∇2L(x*, λ) ≤ 0). 2) Достаточное условие локального условного минимума (максимума): если x* ∈ D − точка локального условного минимума (максимума) функции f(x), выполняются условия регулярности (λ0 = 1), и матрица Гессе ∇2L(x*, λ) функции L(x*, λ) в касательном подпространстве S удовлетворяет условию ∇2L(x*, λ) > 0 (∇2L(x*, λ) < 0), то точка x* является точкой локального минимума (максимума). Замечание 6.3.1. 1) Проверка условий ∇2L(x*, λ) ≥ 0 (∇2L(x*, λ) ≤ 0) проводится на основе критерия Сильвестра. Так в случае ∇2L(x*, λ) ≥ 0 все главные миноры матрицы Гессе неотрицательны, а в случае ∇2L(x*, λ) > 0 строго положительны. 2) Требование о выполнении условий ∇2L(x*, λ) ≥ 0 (∇2L(x*, λ) ≤ 0) или ∇2L(x*, λ) > 0 (∇2L(x*, λ) < 0) не во всей области x* ∈ D (а только в касательном подмножестве) является существенным. Рассмотрим, например, задачу f(x) = x1 − x22 → min, x2 = 0. Очевидным и единственным решение этой задачи является точка x* = (0, 0). Матрица Гессе является матрицей размера 2×2 с диагональными элементами a11 = 0, a22 = −2, и не удовлетворяет условию ∇2L(x*, λ) ≥ 0 в R2. Однако в данном случае ∇h1 = (0, 1), касательное подмножество S имеет вид S = {x: x2 = 0}, и условие ∇2L(x*, λ) ≥ 0 выполняется в S. 3) Разумеется, если условия ∇2L(x*, λ) ≥ 0 (∇2L(x*, λ) ≤ 0) или ∇2L(x*, λ) > 0 (∇2L(x*, λ) < 0) реально выполняются в Rn, то нет необходимости проверять их на касательном подмножестве S. Пример 6.3.1. Найти экстремумы функции f(x1, x2) = 4x1 + 3x2 на множестве, заданном уравнением x12 + x22 = 1. Решение. Запишем задачу в стандартном виде f(x1, x2) = 4x1 + 3x2 → extr, h1(x1, x2) = x12 + x22 − 1 = 0. Составим для нее функцию Лагранжа L(x1, x2, λ) = λ0(4x1 + 3x2) + λ1(x12 + x22 − 1). Необходимые условия экстремума имеют вид ∂L(x1, x2, λ)/∂x1 = 4λ0 + 2λ1x1 = 0, ∂L(x1, x2, λ)/∂x2 = 3λ0 + 2λ1x2 = 0, x12 + x22 − 1 = 0. Рассмотрим два случая. a) Пусть λ0 = 0. Тогда система принимает вид λ1x1 = 0, λ1x2 = 0, x12 + x22 = 1. Она разрешима лишь при λ1 = 0. Следовательно, λ0 = λ1 = 0 и в этом случае подозрительных на экстремум точек нет. б) Пусть λ0 ≠ 0. Тогда можно положить λ0 = 1 и необходимые условия экстремума примут вид: 4 + 2λ1x1 = 0, 3 + 2λ1x2 = 0, x12 + x22 = 1. Из этих соотношений находим x1 = −2/(λ1), x2 = −3/(2λ1) и, следовательно, λ1 = ±5/2. Таким образом получаем две подозрительные на экстремум точки (x1, x2) = (4/5; 3/5), (x1, x2) = (−4/5; −3/5). Других локальных экстремумов нет. По условию задачи экстремумы целевой функции требуется найти на множестве, задаваемом уравнением x12 + x22 = 1, то есть на окружности. Поскольку окружность является компактным множеством, а целевая функция непрерывна, то по теореме Вейерштрасса она достигает своих максимума и минимума на этой окружности. Для определения точек максимума и минимума найдем значения целевой функции f(x1, x2) в подозрительных на экстремум точках: f(4/5; 3/5 ) = 5, f(− 4/5; −3/5) = −5. Так как других подозрительных точек нет, то глобальный максимум достигается в точке (x1, x2) = (4/5; 3/5) и равен 5, а глобальный минимум достигается в точке (x1, x2) = (−4/5; −3/5) и равен −5. Заметим, что в данном случае матрица Гессе является матрицей размера 2×2 с диагональными элементами a11 = a22 = 2λ1. При λ1 = 5/2 (это значение соответствует точке (x1, x2) = (4/5; 3/5)) условие ∇2L(x*, λ) ≥ 0 выполняется в R2, а при λ1 = −5/2 (это значение соответствует точке (x1, x2) = (−4/5; −3/5)) условие ∇ 2L(x*, λ) ≤ 0 также выполняется в R2 и нет необходимости проверки указанных условий в касательном подмножестве S. Пример 6.3.2. Найти экстремум функции f(x1, x2) = exp(x1x2) на прямой x1 + x2 = 1. Решение. Запишем задачу в стандартном виде f(x1, x2) = exp(x1x2) → extr, h1(x1, x2) = x1 + x2 − 1 = 0. Составим для нее функцию Лагранжа L(x1, x2, λ) = λ0exp(x1x2) + λ1(x1 + x2 − 1). Необходимые условия экстремума имеют вид ∂L(x1, x2, λ)/∂x1 = λ0x2exp(x1x2) + λ1 = 0, ∂L(x1, x2, λ)/∂x2 = λ0x1exp(x1x2) + λ1 = 0, x1 + x2 − 1 = 0. Рассмотрим два случая. a) Пусть λ0 = 0. Тогда λ1 = 0 и подозрительных на экстремум точек нет. б) Пусть λ0 ≠ 0. Тогда можно положить λ0 = 1 и необходимые условия экстремума примут вид: x2exp(x1x2) + λ1 = 0, x1exp(x1x2) + λ1 = 0, x1 + x2 = 1. Из первых двух уравнений следует, что x1 = x2, и из третьего уравнения находим x1 = x2 = ½. Итак, мы получили единственную подозрительную на экстремум точку x1 = x2 = ½. Попробуем определить тип экстремума в найденной точке с помощью достаточного условия (теоремы 1.3.2). В данном случае A = ∂2f(x*)/∂x12 = B = ∂2f(x*)/∂x22 = x1x2exp(x1x2), C = ∂2f(x*)/∂x1∂x2 = (1 + x1x2)exp(x1x2). Поскольку A = B = (1/4)exp (1/4), C = (5/4)exp(1/4) в точке x1 = x2 = ½, то это точка локального максимума. Выясним, будет ли найденный локальный максимум глобальным. Так как прямая x1 + x2 = 1 не является компактным множеством, теорема Вейерштрасса в этой задаче не применима. Очевидно, на прямой x1 + x2 = 1 выполняется соотношение x2 = 1 − x1. Поэтому f(x1, x2) = f(x1, 1 − x1) = exp[x1(1 − x1)] → 0 при x1 → ±∞. В силу этих соотношений на прямой x1 + x2 = 1 можно выбрать такой большой отрезок [a, b], что вне него функция f будет строго меньше, чем f(½,½), а на самом отрезке [a, b] у нее будет единственная точка максимума x1 = x2 = ½. Значит, этот максимум (fmax = exp(1/4)) глобальный. Вопросы для самоконтроля 1. Сущность метода множителей Лагранжа. 2. Суть условия регулярности. 3. Охарактеризуйте модель Ф. Блека оптимизации портфеля ценных бумаг (лекция 1) с позиций задачи условной оптимизации при ограничениях типа равенств. 4. Сформулируйте достаточные условия локального максимума в задаче условной оптимизации при ограничениях типа равенств. 5. Экономическая интерпретация множителей Лагранжа. ЛЕКЦИЯ 7. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Метод множителей Лагранжа предложен для решения задачи на условный экстремум при ограничениях в виде равенств. Поразительно, но аналогичные условия для задач с ограничениями в виде неравенств получены только в середине XX столетия американскими математиками Гарольдом Куном (H. Kuhn (1925-2014)) и Альбертом Такером (A. Tucker (1905-1995)) в их совместной работе Kuhn H.W., Tucker A.W. Nonlinear Programming // Proc. of the Second Berkeley Symposium on Math. Statistics and Probability. University of California Press, Berkeley, Calif., 1951. Р. 481–492.) Позднее выяснилось, что аналогичные условия были получены в 1939г. Вильямом Карушем (W. Karush (1917-1997) в его магистерской диссертации Karush W. Minima of Functions of Several Variables with Inequalities as Side Conditions. M. S. thesis. Department of Mathematics, University of Chicago, Chicago, 1939, которая оказалась неопубликованной. Поэтому условия условной оптимизации в зарубежной литературе часто называют условиями Каруша – Куна – Таккера (KKT-conditions). Другой важный результат опубликован в 1948г. Фрицем Джоном (F. John (19101984)) в его работе John F. Extremum Problems with Inequalities as Side Condition // In: Frierichs K. O., Neugebaur O. E. and Stoker J. J., Eds., Studies and Essays, Courant Anniversary Volume, Wiley (Interscience), New York, 1948, P. 187-204. Данная работа опубликована на три года раньше работы Куна − Таккера и дает более общие условия, соответствующие присутствию множителя λ0 в функции Лагранжа (и допускающие случай λ0 = 0). Отметим также, что в 1835г. М.В. Остроградский, решая задачу механики, показал, что в случае ограничений типа неравенства в правило Лагранжа следует ввести дополнительное условие на знаки множителей. (Ostrogradski M. Considérations générales sur les moments des forces. [Общие сообpажения о моментах сил] // Mém. de l’Acad.des sc. de St.-Pbg. VI sér., sc. math. et phys. V.1 1835–1838. P.129-150. Остpогpадский М.В. Избpанные тpуды. М.: Изд-во АН СССР, 1958.) Однако эта работа попала в поле зрения специалистов по методам оптимизации также только во второй половине XX столетия (см. Prekopa A. On the Development of Optimization Theory // The American Mathem. Monthly. 1980 V.87. №7. P.527–542). Подробное обсуждений всех перипетий, связанных с теоремой Куна − Таккера, можно найти в специально посвященной этому вопросу аналитической обзорной статье Тинна Келдзена (T.H. Kjeldsen. A Contextualized Historical Analysis of the Kuhn–Tucker Theorem in Nonlinear Programming: The Impact of World War II // Historia Mathematica. 2000. V.27. P.331-361.) Строгое обоснование условий Куна − Таккера представляет достаточно сложную задачу. Однако совсем недавно российскими математиками Ю.Г. Евтушенко и А.A. Третьяковым найдено простое доказательство этих условий (Ю.Г. Евтушенко, А.А. Третьяков. Новое доказательство теоремы Куна − Таккера и Фаркаша // ЖВМ и МФ. 2018. Т.58. №7. С.1084-1088). 7.1. Условная оптимизация при ограничениях в виде неравенств. Условия Куна − Таккера Рассмотрим задачу f(x) → min gs(x) ≤ 0 (s = 1, … , p). Для решения используем функцию Лагранжа вида L(x, µ) = μ0f(x) + µ 1g1(x) + … + µ pgp(x), µ 0 + µ 12 + …+ µ m2 = 1. Теорема 7.1.1 (Куна − Таккера). Пусть функции f = f(x), gs = gs(x) дважды непрерывно дифференцируемы в некоторой области D ∈ Rn. 1) Необходимые условия локального минимума (в форме Ф. Джона): если x* ∈ D − точка локального условного минимума функции f(x), то найдутся числа µ 0 и µ s такие, что µ 0 и µ 12 + …+ µ p2 не равны нулю одновременно, для которых выполняются следующие условия: − стационарности ∂L(x*, µ)/∂xi = µ 0[∂f(x*)/∂xi] + µ 1[∂g1(x*)/∂xi] + … + µ p[∂gp(x*)/∂xi] = 0; (i = 1, … , n); − «дополняющей нежесткости» µ sgs(x*) = 0 (s = 1, … , p); − согласования знаков (неотрицательности) µ 0 ≥ 0, µ s ≥ 0 (s = 1, … , p). Для того, чтобы μ0 ≠ 0 (µ 0 = 1) достаточно, чтобы векторы ∇g1(x*) = {[∂g1(x*)/∂x1], … , [∂g1(x*)/∂xn]} … ∇gm(x*) = {[∂gm(x*)/∂x1], … , [∂gm(x*)/∂xn]} были линейно независимы. 2) Достаточные условия локального минимума: если выполняются условия стационарности, «дополняющей нежесткости», неотрицательности и, кроме того, найдется точка x0 такая, что gs(x0) < 0 (s = 1, … , p) (условие Слейтера), то x* ∈ D − точка локального условного минимума функции f(x). Замечание 7.1.1. 1) В задаче на максимум функции f(x) f(x) → max, gs(x) ≤ 0 (s = 1, … , p) условие согласования знаков меняется на µ 0 ≤ 0, µ s ≤ 0 (s = 1, … , p). 2) Условный минимум (максимум) функции f(x) при ограничениях типа неравенств может достигаться в точке x*, которая может лежать как на границе, так и внутри допустимой области. При этом в отличие от случая линейных неравенств нелинейность ограничений не всегда обеспечивает не только выпуклость области допустимых решений и конечность числа его крайних точек, но и может быть даже несвязной. Например, если ограничения имеют вид g1 = x1 − 6 ≤ 0, g2 = x2 − 6 ≤ 0, g3 = x1x2 − 6 ≤ 0 x1 ≥ 0, x2≥ 0, то допустимая область не является выпуклой, а если g1 = x12 + x22− 4 ≤ 0 x1 ≥ 0, x2≥ 0, то допустимая область является выпуклой, но имеет бесконечное число крайних точек. Если ограничения определяются соотношениями g1 = x1x2 ≤ 1, g1 = x1 + x2 ≥ 2.2 x1 ≥ 0, x2 ≥ 0, то допустимая область несвязна. Из-за этих особенностей и возникают основные трудности решения задач нелинейного программирования. 3) Те ограничения gs(x) ≤ 0, для которых gs(x*) = 0, называются «активными» (active constraints). В противном случае ограничения «пассивные» (inactive constraints). Если можно заранее выявить «пассивные» ограничения, то можно соответствующие µ s в функции Лагранжа полагать равными нулю. 4) Если в функции Лагранжа µ 0 = 0, то условия Ф. Джона не используют информацию, которую представляет градиент целевой функции. В этом случае они просто констатируют, что существует неотрицательная, нетривиальная и равная нулю линейная комбинация градиентов функций − активных ограничений в исследуемой точке. В связи с этим более интересен случай, когда µ 0 > 0. Г. Кун и А. Таккер (1951 г.) независимо от Ф. Джона получили необходимые условия оптимальности точно того же типа, но с дополнительным свойством µ 0 > 0 (фактически можно положить µ 0 = 1). Чтобы гарантировать положительность множителя µ 0 > 0, можно предъявлять различные требования к функциям ограничений. Обычно эти требования называют условиями регулярности. Одним из наиболее часто используемых условий регулярности является условие Слейтера, названного именем Мортона Слейтера (M.L. Slater (1921-2002)). Неформально условие Слейтера утверждает, что допустимая область должна иметь внутреннюю точку. Пример 7.1.2. Решить графическим способом задачу нелинейного программирования f(x1, x2) = (x1 − 13)2 + (x2 − 14)2 → min 4x1 + 4x2 ≤ 44, 5x1 − x2 ≥ −5, 2x1 − x2 ≤ 16, x1 ≥ 0, x2 ≥ 0 и проверить выполнение условий Куна − Таккера. Решение. Для решения задачи графическим методом построим на плоскости (x1, x2) выпуклое множество, заданное системой ограничений задачи. Легко видеть, что допустимым множеством является пятиугольник OABCD с угловыми точками O(0, 0), A(0, 5), B(1, 10), C (9, 2) и D(8, 0). Линиями уровня целевой функции f(x1, x2) являются окружности (x1 − 13)2 + (x2 − 14)2 = C с центром в точке E(13, 14) Поэтому минимальное значение функции f(x1, x2) достигается в точке касания K с отрезком BC окружности соответствующего радиуса. Найдем точку касания K как точку пересечения прямой l1: x1 + x2 = 11 и прямой l2, перпендикулярной l1 и проходящей через точку E . Вектор нормали к прямой l1, равный n = (1, 1), является направляющим вектором для прямой l2. Таким образом, каноническое и общее уравнения прямой l2 имеют вид x1 − 13 = x2 − 14 и x1 − x2 = −1 соответственно. Точка пересечения K = l1 ∩ l2 находится как решение системы x1 + x2 = 11, x1 − x2 = −1. Поэтому K = K(5, 6) и fmin = f(5, 6) = (5 − 13)2 + (6 − 14)2 = 128 . Проверим, что точка K(5, 6) удовлетворяет условиям теоремы Куна − Таккера. Перепишем систему ограничений в виде g1 = x1 + x2 − 11 ≤ 0, g2 = −5x1 + x2 − 5 ≤ 0, g3 = 2x1 − x2 − 16 ≤ 0, g4 = −x1 ≤ 0, g5 = −x2 ≤ 0 и составим функцию Лагранжа для функции f(x1, x2): L(x1, x2, µ) = (x1 − 13)2 + (x2 − 14)2 + µ 1( x1 + x2 − 11) + + µ 2(−5x1 + x2 − 5)+ µ 3(2x1 − x2 − 16) + µ 4(−x1) + λ5(−x2). Теперь запишем условия теоремы Куна − Таккера в виде системы: дL/дx1 = 2(x1 − 13) + µ 1 − 5µ 2 + 2µ 3 − µ 4 = 0, дL/дx2 = 2(x2 − 14) + µ 1 + µ 2 − µ 3 − µ 5 = 0, µ 1(x1 + x2 − 11) = 0, µ 2(−5x1 + x2 − 5) = 0, µ 3(2x1 − x2 − 16) = 0, µ 4x1 = 0, µ 5x2 = 0, µ s ≥ 0. Подставляя x1 = 5, x2 = 6, из 3-го − 7-го уравнения этой системы получаем, что µ 2 = µ 3 = µ 4 = µ 5 = 0. Тогда из уравнений 1 и 2 следует, что система сводится к равенству 16 − µ 1 = 0, откуда имеем µ 1 = 16 > 0. Таким образом для точки K(5, 6) выполнены условия теоремы Куна − Таккера. Пример 7.1.3. Рассмотрим следующую задачу условной оптимизации: f(x1, x2) = (x1 − 4)2 + (x2 − 4)2 → min x1 + x2 ≤ 4, x1 + 3x2 ≤ 9. Решение. Составим функцию Лагранжа для функции f(x1, x2): L(x1, x2, µ) = (x1 − 4)2 + (x2 − 4)2 + µ 1(x1 + x2 − 4) + µ 2(x1 + 3x2 − 9). Перепишем систему ограничений в виде g1 = x1 + x2 − 4 ≤ 0, g2 = x1 + 3x2 − 9 ≤ 0. и запишем условия теоремы Куна − Таккера в виде системы: дL/дx1 = 2(x1 − 4) + µ 1 + µ 2 = 0, дL/дx2 = 2(x2 − 4) + µ 1 + 3µ 2 = 0, µ 1(x1 + x2 − 4) = 0, µ 2(x1 + 3x2 − 9) = 0, µ s ≥ 0. Решая полученную систему, рассмотрим 4 случая. 1) x1 + x2 = 4, x1 + 3x2 = 9, µ 1 > 0, µ 2 > 0. Первые два соотношения дают x1 = 3/2, x2 = 5/2. После подстановки в первые два уравнения системы, определяющей условия Куна − Таккера, получаем µ 1 + µ 2 = 3, µ 1 + 3µ 2 = 5, откуда µ 2 = − 1. Это противоречит принятому допущению. 2) x1 + x2 = 4, x1 + 3x2 < 9, µ 1 > 0, µ 2 = 0. Подстановка µ 2 = 0 в первые два уравнения системы, определяющей условия Куна − Таккера, вместе с уравнением x1 + x2 = 4 приводит к системе 2(x1 − 4) + µ 1 = 0, 2(x2 − 4) + µ 1 = 0, x1 + x2 = 4, которая имеет решение x1 = 2, x2 = 2, µ 1 = 4, µ 2 = 0. Это решение удовлетворяют всем условиям Куна–Таккера. 3) x1 + x2 < 4, x1 + 3x2 = 9, µ 1 = 0, µ 2 > 0. Подстановка µ 1 = 0 в первые два уравнения системы, определяющей условия Куна − Таккера, вместе с уравнением x1 + 3x2 = 9 приводит к системе 2(x1 − 4) + µ 2 = 0, 2(x2 − 4) + µ 2 = 0, x1 + 3x2 = 9, которая имеет решение x1 = x2 = 9/4, µ 2 = 7/2. Это противоречит принятому допущению x1 + x2 < 4 (поскольку при x1 = x2 = 9/4 имеем x1 + x2 = 4,5 > 4). 4) x1 + x2 < 4, x1 + 3x2 < 9, µ 1 = µ 2 = 0. Подстановка µ 1 = µ 2 = 0 в первые два уравнения системы, определяющей условия Куна − Таккера, приводит к системе 2(x1 − 4) = 0, 2(x2 − 4) = 0, которая имеет решение x1 = x2 = 4. Это противоречит принятым допущениям x1 + x2 < 4, x1 + 3x2 < 9. Поскольку задача выпуклая и удовлетворяет ослабленным условиям Слейтера, найденная точка x1 = 2, x2 = 2 (случай 2) является решением. Отметим, что в точке x1 = 2, x2 = 2 выполняется ограничение g1 = x1 + x2 − 4 ≤ 0 («активное» ограничение), в ограничение g2 = x1 + 3x2 − 9 ≤ 0 является «пассивным». Пример 7.1.4. Рассмотрим задачу: Составим функцию Лагранжа для функции f *(x1, x2): L(x1, x2, µ) = –x1x2 + µ 1(x1 + x22 – 2) + µ 2(–x1) + µ 3(–x2). и запишем условия теоремы Куна − Таккера в виде системы: дL/дx1 = –x2 + µ 1 – µ 2 = 0, дL/дx2 = –x1 + 2 µ 1x2 – µ 3 = 0, µ 1(x1 + x22 – 2) = 0, µ 2x1 = 0, µ 3x2 = 0, µ s ≥ 0. Решая полученную систему, рассмотрим следующие случаи. 1) Предположим, что µ 1 = 0. Тогда из первого и второго уравнений системы, определяющей условия Куна – Таккера, следуют соотношения x2 + µ 2 = 0, x1 + µ 3 = 0. Поскольку каждое слагаемое в этих соотношениях неотрицательно, имеем x1 = x2 = µ 2 = µ 3 = 0. Это решение удовлетворяют всем условиям Куна – Таккера, хотя ясно, что точка x1 = x2 = 0 не определяет минимум, поскольку f(0, 0) = 0 в то время как f(x1, x2) < 0 во внутренних точках допустимой области. 2) Предположим, что x1 + x22 = 2. Рассмотрим две возможности. 2a) Допустим, что x1 > 0 и, следовательно, µ 2 = 0. Из первого уравнения системы, определяющей условия Куна – Таккера, имеем µ 1 = x2. Тогда второе уравнение приводит к соотношению 2x22 = x1 + µ 3, которое с учетом сделанного предположения запишем в виде 3x22 = 2 + µ 3. В результате x22 > 0 и, на основании условия µ 3x2 = 0, имеем µ 3 = 0. Поэтому в данном случае 3x22 = 2 (x2 = √2/3 в силу x2 ≥ 0), и x1 = 2 − 2/3 = 4/3. Это решение также удовлетворяют всем условиям Куна – Таккера. 2b) Допустим, что x1 = 0. Тогда x2 = √2. Поскольку x2 > 0, то µ 3 = 0. Из второго уравнения системы, определяющей условия Куна – Таккера, имеем µ 1 = 0. В этом случае возвращаемся к допущению 1. Таким образом получаем два кандидата на локальный минимум функции f * = – x1x2 (локальный максимум f(x1, x2) = x1x2)): точки x1 = x2 = 0 и x1 = 4/3, x2 = √2/3. В результате получаем, что точка x1 = 4/3, x2 = √2/3 является точкой глобально максимума функции f(x1, x2) = x1x2. Отметим, что в точке x1 = 4/3, x2 = √2/3 выполняется ограничение g1 = x1 + x22 – 2 = 0 («активное» ограничение), а ограничения g2 = x1 = 0, g3 = x2 = 0 являются пассивными». 7.2. Условная оптимизация при ограничениях в виде равенств и неравенств Рассмотрим задачу f(x1, x2) = x1x2 → max x1 + x22 ≤ 2, x1, x2 ≥ 0. Решение. Область допустимых значений непрерывной функции f(x1, x2) является ограниченным замкнутым множеством, поэтому на основании теоремы Вейерштрасса задача имеет решение. В принятом стандартном виде данную задачу можно записать следующим образом f *(x1, x2) = –x1x2 → min g1 = x1 + x22 – 2 ≤ 0, g2 = –x1 ≤ 0, g3 = –x2 ≤ 0. f(x) → min hj(x) = 0 (j = 1, … , m), gs(x) ≤ 0 (s = 1, … , p). Для решения используем функцию Лагранжа вида L(x, λ, µ) = λ0f(x) + λ1h1(x) + … + λmhm(x) + µ 1g1(x) + … + µ pgp(x). Теорема 7.2.1 (Куна − Таккера). Пусть функции f = f(x), hj(x) дважды непрерывно дифференцируемы в некоторой области D ∈ Rn. 1) Необходимые условия минимума: если x* ∈ D − точка локального условного минимума функции f(x), то найдутся числа λ0 и λj, µ s такие, что λ0 и λ12 + …+ λm2, µ 12 + …+ µ p2 не равны нулю одновременно, для которых выполняются следующие условия: − стационарности * * ∂L(x , µ)/∂xi = λ0[∂f(x )/∂xi] + λ1[∂h1(x*)/∂xi] + … + λm[∂hm(x*)/∂xi] + µ 1[∂g1(x*)/∂xi] + … + µ p[∂gp(x*)/∂xi] = 0; (i = 1, … , n); − «дополняющей нежесткости» µ sgs(x*) = 0 (s = 1, … , p); − согласования знаков (неотрицательности) λ0 ≥ 0, µ s ≥ 0 (s = 1, … , p). Для того, чтобы λ0 ≠ 0 (λ0 = 1) достаточно, чтобы векторы ∇h1(x*) = {[∂h1(x*)/∂x1], … , [∂h1(x*)/∂xn]} … ∇hm(x*) = {[∂hm(x*)/∂x1], … , [∂hm(x*)/∂xn]} были линейно независимы. 2) Достаточные условия минимума: если выполняются условия стационарности, «дополняющей нежесткости», неотрицательности и, кроме того, найдется точка x0 такая, что gs(x0) < 0 (s = 1, … , p) (условие Слейтера), то x* ∈ D − точка локального условного минимума функции f(x). Вопросы для самоконтроля 1. В чем принципиальное отличие задач нелинейного и линейного программмирования ? 2. Понятия «активных» и «пассивных» ограничений. 3. Охарактеризуйте модель Г. Марковица оптимизации портфеля ценных бумаг лекция 1) с позиций задачи условной оптимизации при ограничениях типа неравенств. 4. Сформулируйте достаточные условия локального минимума в задаче условной оптимизации при ограничениях типа неравенств. 5. В чем суть условия Слейтера ? ЛЕКЦИЯ 8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (непрерывные и многошаговые процессы, прннцип оптимальности) Динамическое программирование представляет собой многоэтапный поиск (multistage desigion processes) оптимального решения. Вычисления в динамическом программировании выполняются рекуррентно – оптимальное решение одной подзадачи используется в качестве исходных данных для поиска оптимального решения следующей подзадачи. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне «статической» задачи. Таковы, например, некоторые задачи распределения ресурсов. В этом случае многошаговость отражает искусственное разбиение принятия однократного решения на отдельные этапы и шаги («статическая» задача сводится к динамической). В 50-х годах XX столетия появились первые работы, посвященные изучению многошаговых процессов принятия решений. Оказалось, что для этого хотя и не очень широкого, но часто встречающегося класса задач, методы классического математического анализа, линейного программирования, вариационного исчисления, не дают достаточно эффективных средств решения. Требовалось создать концепцию, которая позволяла бы с единой очки зрения исследовать вопросы многошагового принятия решений. Такая концепция, получившая название динамического программирования, была создана американским математиком Р. Беллманом (R.E. Bellman (1920-1984) и его школой. Выдающейся заслугой Р. Беллмана явилось открытие способа решения многошаговой задачи оптимизации, при котором: 1) эффективно используются ранее полученные оценки состояний системы; 2) большая задача разбита на серию более простых одношаговых задач, решаемых на каждом этапе. Поиск многошагового оптимального управления путем прямой оптимизации возможен лишь в задачах с небольшим числом переменных и временных шагов. При увеличении числа состояний и возможных управлений сложность задачи оптимизации резко возрастает. Это явление названо Р. Беллманом “проклятием размерности”. 8.1. Многошаговые и непрерывные динамические модели Рассмотрим управляемую систему, состояние которой в каждый момент времени характеризуется n-мерным вектором x с компонентами x1 , …, xn . Предполагаем, что время t изменяется дискретно и принимает целочисленные значения 0, 1, … . Так, для процессов в экономике дискретным значениям времени могут отвечать дни, месяцы или годы, а для процессов в электронных устройствах интервалы между соседними дискретными моментами времени равны времени срабатывания устройства. Предполагаем, что на каждом шаге на систему оказывается управляющее воздействие при помощи m-мерного вектора управления u с компонентами u1, …, um. Таким образом, в каждый момент времени t состояние системы характеризуется вектором x(t), а управляющее воздействие – вектором u(t). На выбор управления обычно бывают наложены ограничения, которые в достаточно общей форме можно представить в виде u(t) ∈ U (t = 0, 1, … ), (1) где U – заданное множество в n-мерном пространстве. Под влиянием выбранного в момент t управления (принятого решения) система переходит в следующий момент времени в новое состояние. Этот переход можно описать соотношениями x1(t + 1) = f1(x1(t), … , xn(t), u1(t), …, um(t)), x2(t + 1) = f2(x1(t), … , xn(t), u1(t), …, um(t)), … xn(t + 1) = fn(x1(t), … , xn(t), u1(t), …, um(t)) (t = 0, 1, … ). В векторной форме данные соотношения можно представить в виде x(t + 1) = f(x(t), u(t)) (t = 0, 1, … ). (2) в котором f(x, u) – n-мерная функция от n-мерного вектора x и m-мерного вектора u, характеризующая динамику рассматриваемой системы. Эта функция предполагается известной (заданной) и отвечает принятой математической модели рассматриваемого управляемого процесса. Зададим еще начальное состояние системы x(0) = x0, (3) где x0 – заданный n-мерный вектор. Таким образом, многошаговый процесс управления описывается соотношениями (1) – (3), которые включают дискретную управляемую систему, ограничения на управляющие воздействия, а также начальное состояние процесса. Процедура расчета конкретного процесса сводится к следующему. Пусть в некоторый момент t состояние системы x(t) известно. Тогда для определения состояния x(t + 1) необходимо выполнить две операции: 1) выбрать допустимое управление u(t), удовлетворяющее условию (1); 2) определить состояние x(t + 1) в следующий момент времени согласно (2). Так как начальное состояние системы задано, то описанную процедуру можно последовательно выполнить для всех t = 0, 1, … . Последовательность состояний x(0), x(1), … часто называется траекторией системы. Если время t изменяется непрерывно на некотором промежутке, то рассматриваются непрерывные динамические модели вида x/(t) = f(x(t), u(t)). 8.2. Задача оптимального управления. Критерий оптимизации Выбор управления на каждом шаге содержит значительный произвол. Этот произвол исчезает, если задать цель управления в виде требования минимизации (или максимизации) некоторого критерия оптимальности. Пусть многошаговый процесс управления включает заданное число N шагов (время t принимает целочисленные значения 0, 1, … , N). Критерий качества процесса управления (критерий оптимальности) имеет вид N −1 J=  R(x(t ), u(t )) + F(x(N)) = (4) t =0 Задача оптимального управления: определить допустимые управления u(0), u(1), …, u(N − 1), удовлетворяющих ограничениям (1), и соответствующую траекторию, то есть последовательность x(0), x(1), …, x(N), которые в совокупности доставляют минимальное значение критерию (4) для процесса (2), (3). Минимизация критерия (4) обычно отвечает выбору управления, обеспечивающего наименьшие затраты средств или ресурсов за N шагов процесса. Наряду с этим часто ставится также задача о максимизации критерия вида (4), например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (−J). Поэтому простая замена знака у функций R и F в (4) приводит задачу о максимизации критерия к задаче о его минимизации. Далее всюду для определенности рассматриваем задачу о минимизации критерия (4). 8.3. Принцип оптимальности Рассмотрим сначала стандартный подход к поставленной задаче оптимального управления. При помощи соотношений (2) состояние системы в каждый последующий момент времени выражается через ее состояние и управление в предыдущий момент времени. Применяя это соотношение многократно, можно выразить состояния системы во все моменты времени только через начальное состояние x0 и управления в предшествующие моменты. В результате получим из (4) J = R(x(0), u(0)) + R(f(x(1), u(1)), u(0)) + … = Φ(x(0) , u(0), u(1), …, u(N − 1)), где Φ – некоторая громоздкая, но, вообще говоря, известная функция своих аргументов. Таким образом, поставленная задача оптимального управления свелась к задаче о минимизации функции Φ от векторов u(0), u(1), …, u(N − 1), то есть от Nm переменных. При больших N (а обычно представляют интерес именно процессы с большими N) эта задача о минимизации функции большого числа переменных представляет трудности даже при использовании мощных компьютеров. Дополнительное осложнение вызвано тем, что переменные u(t) должны удовлетворять ограничениям (1). Принципиально иной подход к поставленной проблеме дает метод динамического программирования. Сформулированный Р. Беллманом принцип оптимальности гласит: отрезок оптимального процесса от любой его точки до конца процесса сам является оптимальным процессом с началом в данной точке. Принцип оптимальности легко доказывается от противного, что наводит на мысль о тривиальности этого принципа. Однако это не так: принцип оптимальности является следствием аддитивности критерия оптимальности (4) и не имеет места в случае неаддитивного критерия, например для критерия, являющегося некоторой функций от критериев вида (4). Обозначим: S(x, t) – минимальное значение критерия качества N −1 Jt =  R(x(k ), u(k )) + F(x(N)) (5) k =t = R(x(0), u(0)) + R(x(1), u(1)) + … + R(x(N – 1), u(N – 1)) + F(x(N)), где R(x, u) и F(x) – заданные скалярные функции своих аргументов. Функция R может отражать расход средств или энергии на каждом шаге процесса, а функция F – характеризовать оценку конечного состояния системы или точность приведения в заданное состояние. для оптимального процесса, начинающегося в момент t в точке x(t) = x. Этот процесс можно представить состоящим из двух участков: первого шага, на котором выбирается управление u(t) = u, и остальной части (от момента t + 1 до конца процесса). Вклад в критерий качества первого участка процесса равен R(x, u), а вклад второго участка можно, согласно принципу оптимальности, выразить через введенную выше функцию S в виде S(x(t + 1), t + 1). Учитывая, что управление на первом участке должно выбираться из условия минимизации критерия Jt при ограничении (1), получим равенство S(x, t) = min u ∈ U {R(x, u) + S(x(t + 1), t + 1)}, где для определенности предполагаем, что функция S, как и ранее введенные в (2), (4) функции f, R, F, непрерывна. Подставляя в полученное соотношение равенство (2), получим основное соотношение метода динамического программирования (уравнение Беллмана) S(x, t) = min u ∈ U {R(x, u) + S(f(x, u), t + 1)} t = 0, 1, …, N − 1. (6) Для оптимального процесса, начинающегося в момент t = N, критерий оптимальности (5) сводится к одному последнему слагаемому. Поэтому имеем выигрыш на последних двух шагах. Далее переходим к оптимизации управления на (N − 2)-м шаге и т. д., пока не дойдем до первого шага. Указанный процесс определяет попятную процедуру метода динамического программмирования. Обсудим дополнительные возможности этой процедуры. Отметим, что при вычислении минимума функции по некоторому аргументу обычно определяются две величины: значение минимума и значение аргумента, при котором минимум достигается. Это значение, которое может быть неединственным, будем обозначать символом argmin. Положим t = N − 1 в (6) и воспользуемся условием (7). Получим S(x, N − 1) = min u ∈ U {R(x, u) + F(x)}. Вычисляя этот минимум, найдем функцию S(x, N − 1) и значение u, доставляющее данный минимум: u = υN – 1(x) = argmin u ∈ U {R(x, u) + F(x)}. S(x, N) = F(x). (8) (7) Соотношение (6) и условие (7), играющее роль начального условия, дают возможность последовательно определить функции S(x, t) при t = N − 1, … …, 1, 0, а также рассчитать оптимальное управление и оптимальные траектории. Это достигается при последовательной реализации попятной и прямой процедур динамического программирования. 8.4. Попятная и прямая процедуры Принцип динамического программирования не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, пошаговое управления должно выбираться с учетом всех его последствий в будущем. Что с того, если мы выберем на некотором шаге управления, которое дает максимальный выигрыш на этом этапе, а суммарный выигрыш на данном и последующих шагов не будет максимальным. Поэтому, планируя многошаговый процесс, надо выбирать управления на каждом шагу, кроме последнего, с учетом его будущих последствий на следующих шагах. Последний шаг можно планировать так, чтобы управление на этом этапе принесло наибольшую выгоду. Итак, процесс динамического программирования разворачивается от конца к началу. Сначала планируется последний, N-й шаг. Для этого надо сделать предположение о том, чем может завершиться предпоследний (N − 1)-шаг (т.е. в каком состоянии может находиться система перед последним шагом). И для каждого из таких предположений найти условное оптимальное управление на N-ом шаге («условное» потому, что оно выбирается из условия того, чем закончился предпоследний шаг). Предположим, что для каждого возможного предпоследнего состояния системы мы нашли условное оптимальное управление на последнем шаге и соответствующий ему оптимальный выигрыш на этом этапе. Тогда можем перейти к оптимизации управления на предпоследнем (N − 1)-м шаге. Для этого надо предположить, чем может завершиться (N − 2)-й шаг и для каждого из таких предположений найти такое управление на (N − 1)-м шаге, при котором выигрыш на этом этапе будет максимальным. Поскольку каждое найденное «условное» оптимальное управление на (N − 1)-м шаге переводит систему в один из возможных предпоследних состояний (а какое оптимальное управление переведет систему из этого состояния в конечный, нам уже известно), то для каждого возможного состояния системы перед выполнением (N − 1)-го шага мы найдем условное оптимальное управление на (N − 1)-м шаге и условный оптимальный Запись υN – 1(x) означает, что значение u зависит от x как от параметра. Определив S(x, N − 1) и полагая t = N − 2, найдем из (6) функцию S(x, N − 2) и соответствующее значение аргумента u = υN – 2(x). Продолжая этот процесс в сторону уменьшения t, получим из (6) последовательно функции S(x, t) и (8) при t = N − 1, N − 2, …, 1, 0. Отметим, что функция υt(x) определяет оптимальное управление в момент t при условии, что система находится в состоянии x. Эта форма задания управления называется управлением по обратной связи. Таким образом, попятная процедура состоит в построении функций S(x, t) и υt(x) для всех x и t = 0, 1, …, N. Это построение в отдельных случаях может быть выполнено аналитически, но, как правило, является трудоемкой вычислительный процедурой. Ниже мы обсудим вычислительные аспекты, а пока предположим, что эта процедура так или иначе реализована. Воспользуемся результатами попятной процедуры для решения исходной задачи, то есть для построения оптимального управления и оптимальной траектории при заданном начальном условии (3). Полагая t = 0 и x = x0 в (8), найдем управление в начальный момент: u(0) = υ0(x(0)). Далее из соотношения (2) определим состояние x(1) = f(x0, u(0)). Продолжая этот процесс, найдем u(1) = υ1(x(1)), x(2) и т.д. Вообще имеем u(t) = υt(x), x(t + 1) = f(x(t), u(t)), x(0) = x0, t = 0, 1, …, N − 1. (9) Соотношения (9) определяют прямую процедуру и позволяют полностью рассчитать оптимальное управление и оптимальную траекторию. Минимальное значение критерия оптимальности, отвечающее этой траектории, J = S(x(0), 0). Замечание 8.4.1.. Как показано выше, попятная и прямая процедуры метода динамического программирования в совокупности дают способ решения поставленной задачи оптимального управления. Однако при реализации этого метода мы получили значительно более общий и универсальный результат. В ходе попятной процедуры построено оптимальное управление по обратной связи (8), то есть управление как функция текущего состояния системы υt(x). Теперь нетрудно дать решение задачи оптимального управления при любом начальном условии вида x(t) = x*: для этого нужно просто реализовать прямую процедуру для этого начального условия. Реализация прямой процедуры не представляет серьезных трудностей и сводится, согласно (9), к вычислению известных функций при конкретных значениях аргументов. Наибольшую сложность представляет попятная процедура, включающая минимизацию функций по m-мерному векторному аргументу u. Здесь нужно, согласно (6), выполнить N процедур минимизации функций от m переменных. Это, вообще говоря, значительно более простая задача, чем минимизация одной функции по Nm переменным, что требуется при стандартном подходе. Однако есть одно серьезное осложнение. Дело в том, что попятная процедура предусматривает построение функций S(x, t) и υt(x), зависящих от n-мерного вектора x. По этому вектору x не нужно выполнять операций минимизации, но даже простое табулирование и хранение функций n переменных представляют большие трудности. Если, к примеру, составлять таблицы, придавая каждой переменной 100 значений, то для хранения таблицы одной функции n переменных понадобится 100n ячеек памяти. Всего же попятная процедура, в которой участвуют функции S(x, t) и υt(x), потребует (m + 1)N × × 100n ячеек. Отсюда понятно, что вычислительная реализация метода динамического программирования сталкивается с большими трудностями. Эти трудности Р. Беллман назвал «проклятием размерности». Для преодоления этих трудностей были предложены подходы, позволяющие сократить объем вычислений и потребности в памяти при построении оптимального управления. При этом, однако, приходится либо существенно пожертвовать точностью вычислений, либо отказаться от построения управления, оптимального в глобальном смысле, и ограничиться нахождением управлений и траекторий, оптимальных в локальном смысле, то есть по отношению к малым (локальным) вариациям этих траекторий. Пример 8.4.1. Рассмотрим модельную задачу об оптимальном функционировании фермы по разведению скота или птицы. Пусть x – число животных (или птиц) на ферме в начале некоторого интервала времени. Из этого числа ux животных отправляется на продажу, а остальные животные приносят приплод, так что их число возрастает в q раз за рассматриваемый интервал. Уравнение (2) примет вид x(t + 1) = q[1 − u(t)]x(t), t = 0, 1, …, (10) где q > 1 – постоянный коэффициент, u – управляющее воздействие (доля животных, отправляемых на продажу). Ограничение (1) в данном случае имеет вид 0 ≤ u ≤ 1. Расходы на содержание животных примем пропорциональными их оставшемуся числу и равными a[1 − u(t)]x(t), где a > 0 – постоянная. Выручку от продажи считаем равной cu(t)x(t), где c – цена одного животного на рынке. Поставим задачу максимизации дохода фермы за N шагов по времени. Как отмечалось выше, эта задача эквивалентна минимизации убытка (то есть дохода со знаком минус). Критерий оптимальности имеет вид (4), где нужно принять в соответствии со сказанным выше R(x, u) = a(1 − u)x − cux, F(x) = −cx. (11) Последнее равенство (11) определяет (со знаком минус) стоимость животных на ферме в конце процесса. Учитывая соотношения (10) и (11), составим уравнение (6) для рассматриваемой задачи S(x, t) = min 0 ≤ u ≤ 1 [a(1 − u)x – cux + S(q(1 − u)x, t +1)]. (12) Условие (7) с учетом (11) примет вид S(x, N) = −cx. (13) Несложный анализ позволяет реализовать попятную процедуру и построить функции S(x, t) и соответствующие им управления υt(x) из (9) для задачи (12), (13). Приведем окончательные результаты: S(x, t) = a(qN - 1 − 1)(q − 1)-1x − cq N - 1x, υt(x) = 0 при a < c(q − 1); (14) S(x, t) = −cx, υt(x) = 1 при a > c(q − 1). В том, что функции S(x, t) из (14) удовлетворяют уравнению (12) и условию (13) при всех t, можно убедиться методом математической индукции, проводя ее в сторону убывания t и начиная с t = N. Решения (14) допускают простую интерпретацию. Если a < c(q − 1), то есть расходы на содержание животных сравнительно невелики, то имеет смысл не направлять животных на продажу (υt(x) = 0) и получить наибольший доход, сохранив все поголовье к концу процесса. Если же a > c(q − 1), то есть расходы на содержание велики, то целесообразно отправить на продажу сразу всех животных. В случае a = c(q − 1) оптимальное управление не единственно: в этом случае любое управление приводит к одному и тому же результату. Более сложные и более содержательные результаты получим, если учтем зависимость рыночной цены c от числа продаваемых животных x (цена убывает с ростом x), а также зависимость расходов на содержание одного животного a от числа животных. Вопросы для самоконтроля 1. Понятия многошагового и непрерывного процесса управления. 2. Постановка задачи оптимального управления многошаговым процессом. Критерий оптимальности. 3. В чем суть метода динамического программирования Беллмана ? 4. Понятия попятной и прямой процедур. 5. Укажите достоинства и недостатки метода динамического программирования. В чем суть термина «проклятие размерности» ? ЛЕКЦИЯ 9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (задача оптимального распределения инвестиций) Как уже отмечалось, динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне «статической» задачи. В этом случае многошаговость отражает искусственное разбиение принятия однократного решения на отдельные этапы и шаги («статическая» задача сводится к динамической). 9.1. Задача максимизации многомерной целевой функции Проиллюстрируем основную идею сведения «статической» задачи к динамической на примере максимизации многомерной аддитивной функции с ограничениями, предложенном самим Р. Беллманом. Рассмотрим задачу оптимизации F = f1(x1) + … + fN(xN) → max xi ≥ 0, x1 + x2 + … + xN = c, моделирующую оптимальное распределения средств между N предприятиями при условии, что fi(xi) означает дополнительную отдачу от вложения средств в размере xi в i-ое предприятие, а с – общий объем предназначенных для распределения средств. Используя «обратную» схему динамического программирования, рассмотрим сначала случай, когда все средства инвестируются в N-ое предприятие. Обозначим через FN(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x; FN(x) = fN(x). На каждом последующем шаге будем оптимизировать инвестирование в предприятия с (N – k)-го по N-ое так, что справедливо рекуррентное соотношение FN − k ( x ) = max { f N − k ( xN − k ) + FN − k +1 ( x − x N − k )}, 0 ≤ xN − k ≤ x где величина FN–k(x) определяет максимально возможный дополнительный доход на предприятиях с (N – k)-го по N-ое, соответствующий выделенной им сумме x. Таким образом, исходная многомерная задача оптимизации сведена к последовательности одномерных задач, образующих многошаговый процесс поиска оптимума. 9.2. Оптимальное распределение инвестиций Производственное объединение выделяет четырем входящим в него предприятиям кредит в сумме 100 млн. ден.ед. для расширения производства и увеличения выпуска продукции. По каждому предприятию известен возможный прирост выпуска продукции (в денежном выражении) в зависимости от выделенной ему суммы; см. Таблицу. Для упрощения вычислений выделяемые суммы кратны 20 млн. ден.ед. Предполагаем, что прирост продукции на предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения. Требуется найти распределение кредита между предприятиями, чтобы общий прирост выпуска продукции на производственном объединении был максимальным. Выделяемые средства x, (млн.ден.ед.) Предприятие №1 №2 №3 №4 20 Прирост fi (x) выпуска продукции на i-ом предприятии (млн. ден.ед.) 10 12 11 16 40 31 24 36 60 42 36 45 46 80 62 52 60 63 100 76 74 77 80 37 Решение. Используем метод динамического программирования. В соответствии с этим методом, нахождение оптимального решения разобъем на 4-е этапа (шага). Шаг 1. В соответствии с «попятной» схемой динамического программирования рассмотрим сначала случай, когда все имеющиеся средства выделяются на реконструкцию и модернизацию 4-го предприятия. Обозначим через F4(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что: F4(x) = f4(x). Шаг 2. Пусть теперь средства распределяются между двумя последними (в рамках рассматриваемой схемы) предприятиями – 3 и 4-ым. Если 3-му предприятию выделена сумма x3, то дополнительный доход на нем составит f3(x3). Оставшиеся 4-ому предприятию средства (x – x3) в зависимости от величины x3 (а значит, и x – x3) позволят увеличить дополнительный доход до максимально возможного значения F4(x – x3). При этом условии общий дополнительный доход на двух (3 и 4-ом) предприятиях: F3(x) = max {f3(x3) + F4(x – x3)}, 0 ≤ x ≤ 100 0 ≤ x3 ≤ x F3(0) = 0; F3(20) = max {f3(0) + F4(20 – 0), f3(20) + F4(20 – 20)} = = max (0 + 16, 11 + 0) = max (16, 11) = 16; F3(40) = max {f3(0) + F4(40 – 0), f3(20) + F4(40 – 20), f3(40) + F4(40 – 40)} = = max (0 + 37, 11 + 16, 24 + 0) = max (37, 27, 24) = 37; F3(60) = max {f3(0) + F4(60 – 0), f3(20) + F4(60 – 20), f3(40) + F4(60 – 40), f3(60) + F4(60 – 60)} = = max (0 + 46, 11 + 37, 36 + 16, 45 + 0) = max (46, 48, 52, 45) = 52; F3(80) = max {f3(0) + F4(80 – 0), f3(20) + F4(80 – 20), f3(40) + F4(80 – 40), f3(60) + F4(80 – 60), f3(80) + F4(80 – 80)} = = max (0 + 63, 11 + 46, 36 + 37, 45 + 16, 52 + 0) = = max (63, 57, 73, 61, 52) = 73; F3(100) = max {f3(0) + F4(100 – 0), f3(20) + F4(100 – 20), f3(40) + F4(100 – 40), f3(60) + F4(100 – 60), f3(80) + F4(100 – 80), f3(100) + F4(100 – 100)} = = max (0 + 80, 11 + 63, 36 + 46, 45 + 37, 60 + 16, 77 + 0) = = max (80, 74, 82, 82, 76, 77) = 82. Шаг 3. Пусть средства распределяются между тремя последними предприятиями (2 – 4-ым). Если 2-му предприятию выделена сумма x2, то дополнительный доход на нем составит f2(x2). Оставшиеся средства (x – x2) в зависимости от величины x2 (а значит, и x – x2) позволят увеличить дополнительный доход до максимально возможного значения F3(x – x2). При этом условии общий дополнительный доход на трех (2 – 4-ом) предприятиях: F2(x) = max {f2(x2) + F3(x – x2)}, 0 ≤ x ≤ 100 0 ≤ x2 ≤ x F2(0) = 0; F2(20) = max {f2(0) + F3(20 – 0), f2(20) + F3(20 – 20)} = = max (0 + 16, 12 + 0) = max (16, 12) = 16 F2(40) = max {f2(0) + F3(40 – 0), f2(20) + F3(40 – 20), f2(40) + F3(40 – 40)} = = max (0 + 37, 12 + 16, 36 + 0) = max (37, 27, 36) = 37; F2(60) = max {f2(0) + F3(60 – 0), f2(20) + F3(60 – 20), f2(40) + F3(60 – 40), f2(60) + F3(60 – 60)} = = max (0 + 52, 12 + 37, 24 + 16, 36 + 0) = max (52, 49, 40, 36) = 52; F2(80) = max {f2(0) + F3(80 – 0), f2(20) + F3(80 – 20), f2(40) + F3(80 – 40), f2(60) + F3(80 – 60), f2(80) + F3(80 – 80)} = = max (0 + 73, 12 + 52, 24 + 37, 36 + 16, 74 + 0) = = max (73, 64, 61, 52, 74) = 74; F2(100) = max {f2(0) + F3(100 – 0), f2(20) + F3(100 – 20), f2(40) + F3(100 – 40), f2(60) + F3(100 – 60), f2(80) + F3(100 – 80), f2(100) + F3(100 – 100)} = = max (0 + 82, 12 + 73, 24 + 52, 36 + 37, 52 + 16, 74 + 0) = = max (82, 85, 76, 73, 68, 74) = 85. Шаг 4. Пусть средства распределяются между всеми четырьмя предприятиями. Если 1-му предприятию выделена сумма x1, то дополнительный доход на нем составит f1(x1). Оставшиеся средства (x – x1) в зависимости от величины x1 (а значит, и x – x1) позволят увеличить дополнительный доход до максимально возможного значения F2(x – x1) . При этом условии общий дополнительный доход на четырех предприятиях: F1(x) = max (f1(x1) + F2(x – x1)), 0 ≤ x ≤ 100 0 ≤ x1 ≤ x F1(0) = 0; F1(20) = max {f1(0) + F2(20 – 0), f1(20) + F2(20 – 20)} = = max (0 + 16, 10 + 0) = max (16, 10) = 16; F1(40) = max {f1(0) + F2(40 – 0), f1(20) + F2(40 – 20), f1(40) + F2(40 – 40)} = = max (0 + 37, 10 + 16, 31 + 0) = max (37, 26, 31) = 37; F1(60) = max (f1(0) + F2(60 – 0), f1(20) + F2(60 – 20), f1(40) + F2(60 – 40), f1(60) + F2(60 – 60)} = = max (0 + 52, 10 + 74, 31 + 16, 42 + 0) = max (52, 84, 47, 42) = 84; F1(80) = max {f1(0) + F2(80 – 0), f1(20) + F2(80 – 20), f1(40) + F2(80 – 40), f1(60) + F2(80 – 60), f1(80) + F2(80 – 80)} = = max (0 + 74, 10 + 52, 31 + 37, 42 + 16, 62 + 0) = = max (74, 62, 68, 58, 62) = 74; F1(100) = max {f1(0) + F2(100 – 0), f1(20) + F2(100 – 20), f1(40) + F2(100 – 40), f1(60) + F2(100 – 60), f1(80) + F2(100 – 80), f1(100) + F2(100 – 100)} = = max (0 + 85, 10 + 74, 31 + 52, 42 + 37, 62 + 16, 76 + 0) = = max (85, 84, 83, 79, 78, 74) = 85. Составим сводную таблицу на основе расчетов: Выделяемые средства 20 40 60 80 100 F1 16 37 84 74 85 F2 16 37 52 74 85 F3 16 37 52 73 82 F4 16 37 46 63 80 Анализируя проделанные вычисления на шагах 2-4 находим, что суммарный дополнительный прирост продукции достигнет максимальной величины, равной 85 млн. ден.ед. при оптимальном плане распределения инвестиций между 4 предприятиями: x* = (x1*, x2*, x3*, x4*) = (0, 20, 40, 40). Действительно, максимум прибыли на шаге 4 достигается при f1(0) + F2(100) = 85, откуда следует, что x1* = 0. Максимальное значение F2(100) = 85 на шаге 3 достигается при f2(20) + F3(80) = 85, откуда следует, что x2* = 20. Максимум значения F3(80) = 73 на шаге 2 достигается при f3(40) + F4(40) = 73, откуда следует, что x3* = x4* = 40. Вопросы для самоконтроля 1. Как формулируется задача оптимального распределения инвестиций между предприятиями ? 2. Каким образом происходит сведение «статической» задачи к динамической ? 3. Опишите пошаговую процедуру решения задачи оптимального распределения инвестиций между предприятиями.