Применение функции одной переменной в экономическом анализе. Задачи дробно-линейного программирования

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) ИНСТИТУТ ТЕХНОЛОГИЙ, ЭКОНОМИКИ И ПРЕДПРИНИМАТЕЛЬСТВА КАФЕДРА ЭКОНОМИКИ И ФИНАНСОВ Грошев Л.Н. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ КОНСПЕКТ ЛЕКЦИЙ для направления подготовки 521600 «ЭКОНОМИКА» Москва – 2010 ОГЛАВЛЕНИЕ 1. Применение функции одной переменной в экономическом анализе..........3 2. Линейное программирование (линейная оптимизация)..............................17 3. Взаимно двойственные задачи линейного программирования ..................38 4. Симплекс‐метод решения задач линейной оптимизации ............................57 5. Транспортная задача ........................................................................................64 6. Задачи дробно‐линейного программирования.............................................80 7. Решение задач линейной оптимизации с помощью EXCEL ..........................88 8. Решение транспортной задачи с помощью EXCEL .......................................104 9. Условный экстремум. Метод множителей Лагранжа .................................115 10. Производственные функции........................................................................130 11. Многокритериальная оптимизация............................................................150 12. Нелинейное программирование ................................................................162 Библиографический список ...............................................................................184 Страница 2 из 184 1. ПРИМЕНЕНИЕ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ В ЭКОНОМИЧЕСКОМ АНАЛИЗЕ 1.1. Величины, применяемые в экономике 1) Суммарная (абсолютная) величина ‐ это любая функция независимой переменной. Примеры. П(х) – прибыль в зависимости от количества выпускаемой продукции, R(х) – выручка, С(х) – затраты. 2) Средняя величина определяется отношением суммарной величины к независимой переменной. Пример. АП(х) = П (х) = П(х ) ‐ средняя прибыль. х 3) Предельная величина (маржинальная) ‐ это производная от суммарной величины. Пример. Предельная выручка R′(х) ≈ ΔR │ = ∆R. Из этой формулы Δх=1 Δx ясно, что предельную выручку R ′ (х) можно трактовать как изменение выручки при изменении объема выпуска товара на единицу. 1.1. Функции спроса и предложения Определение: Функция спроса (demand function) – это функция зависимости количества продукта, которое потребители в состоянии купить, от цены. Обозначим функцию спроса через D(p). Очевидно, что функция спроса ‐ убывающая функция. Её производная D ′ (p) < 0. Страница 3 из 184 Примеры функций спроса (Рис. 1а,б) : − Линейная. D(p) = a ‐ bp; а, b > 0 − Нелинейная (степенная). D(p) = 1/pα; α > 0 − Логарифмическая. D(p) = ln(1 + 1 ) р D D p D(p) =a ‐ bp D(p) =1/p p Рис. 1а, б Пример. При цене билета на футбольный матч 40 д.е.. На стадион пришли 30000 человек. Цена билета возросла до 90 д.е., число болельщиков сократилось до 5000 человек. Сколько болельщиков придут на стадион при цене билета в 20 д.е.? Считать функцию спроса линейной. Решение: По условию функция спроса D(p) = a‐bp. Подставляя данные задачи (в тысячах д.е.) в функцию D(p), получим систему: ⎧30 = a − 0,04b ⎨ ⎩5 = a − 0,09b → a = 50, b = 500. Страница 4 из 184 Следовательно, функция спроса имеет вид D(p) = 50 – 500p. Подставляя p = 0,02 тыс. д.е., получим D = 40 тыс. чел. Определение: Функция предложения (supply function) – это функция зависимости поставляемого на рынок товара от цены. Обозначим функцию предложения через S(p). Функция предложения ‐ возрастающая функция. Тогда её производная S´(p) > 0. Примеры функций предложения (Рис. 2а,б): − Линейная. S(p) = c+dp; − Нелинейная (степенная). S(p) = pα; α > 0, − Логарифмическая. S(p) = ln(1 + p). D D α D(p) = p p D(p ) =c + dp p Рис. 2а,б Определение. Состояние рынка, при котором спрос равен предложению, т.е. D(p) = S(p), называется равновесным, а цена, определяемая из этого равенства, называется равновесной (рыночной) ценой. Страница 5 из 184 Пример. Спрос и предложение в студенческой столовой описываются уравнениями: D(p) = 2400 – 100р; S(p) = 1000 + 250p, где D и S – количество обедов в день, р – цена обеда (д. ед.) Вычислим равновесную цену и количество обедов по этой цене. D(p) = S(p) → 2400 – 100р = 1000 + 250р → 350р = 1400→ р = 4 (ден. ед.) Спрос на обеды: D(4) = 2400 – 100 ⋅ 4 = 2400 – 400 = 2000. Если администрация установит цену, равную 3 д.е. за обед, то спрос будет равен D(3) = 2400 – 100⋅3 = 2400 – 300 = 2100, предложение S(3) = 1000 + 250⋅3 = 1000 + 750 = 1750. Дефицит обедов: 2100 – 1750 = 350. Вывод. Если не следовать законам рыночной экономики, можно наделать множество ошибок. Как в нашем примере, при установлении цены администрацией ниже рыночной, 350 студентов останутся без обеда. 1.3. Примеры экономико‐математических моделей Обозначим прибыль фирмы через П(х), выручку через через C(x), где x ‐ объём производства. Тогда прибыль фирмы: П(х) = R(x) – C(x). Из необходимого условия экстремума следует, что Страница 6 из 184 R(x), затраты П´(х) = 0. Следовательно, R´(x) = С´(х). Последнее равенство означает: в оптимальном режиме работы фирмы предельный доход равен предельным издержкам. Пример. Пусть выручка и затраты выражены функциями: R(x) = х – 3/2x2, С(х) = 4х – 5 x2 + 2/3x3 Найдем максимальное значение прибыли П(х). Из необходимого условия экстремума П´ (х) = ‐2 x2 + 7х – 3 = 0 → x1 = 0,5; x2 = 3. Получили две точки возможного экстремума. Применяя достаточное условие экстремума, находим, что П´´ = ‐4х + 7 и П´´(3) = ‐4⋅3 + 7 = ‐ 5 < 0, значит x2= 3 – точка максимума функции П(х). Отсюда max П(х) = П(3) = 4,5. Пример (введение налога). Пусть прибыль фирмы до введения акцизного налога выражена функцией П(х) = 120х – (2х – 10)2 , где x ‐ объём производства. Решая задачу максимизации прибыли, аналогично предыдущей, получим: max П(х) = П(20); х = 20. После введения налога: П(х,t) = 120х ‐ (2х – 10)2 – tx. Находим max П(х,t) и получаем, что максимальное значение прибыли x достигается при х = 20 – t/8. Страница 7 из 184 Требование налогового органа: найти ставку t, при которой величина взимаемого налога будет максимальна. Обозначим эту величину через N(t). Тогда N(t) = t ⋅ x(t) = t (20 – t/8). max N(t) достигается при t = 80 (д. ед.) т.е. налоговый орган должен установить ставку акцизного налога в 80 д.ед. 1.4. Эластичность Многие вопросы экономики приводят к необходимости выяснить, на сколько процентов изменится функция (результативный признак), если фактор изменить на 1%. Определение. Относительным приращением функции у = f(x) называется величина Δу , где у – первоначальное значение функции. у Определение. Эластичностью функции у = f(x) называется предел отношения относительных изменений переменных у и х. Именно: Еx (у) = Эластичность Δy Δx x / ) = lim y x Δх →0 y ( показывает lim Δх→0 приближенно, Δy x = ⋅ y′. y Δx на сколько процентов изменится значение функции при увеличении аргумента на 1%. Пример. Пусть выпуск продукции задается производственной функцией y = 2x ‐ 1, где y – выпуск продукции (например, в стоимостном выражении), x ‐ количество ресурса. Тогда эластичность выпуска по затратам Страница 8 из 184 Еx (у) = x x 2x ⋅ y′ = ⋅2= . y 2x − 1 2x − 1 При x = 2, Еx (у) = 4/3 = 1,3. Это означает, что при увеличении ресурса с 2 ед. до 2,02ед. (т.е. на 1%) выпуск продукции возрастет приблизительно на 1,3%. 1.5. Свойства эластичности Здесь мы дадим те свойства эластичности, которые наиболее часто применяются на практике. 1) Еbx (ay)= Ex (y), a, b – числа (независимость от единиц измерения); 2) Ex (y) = 1 ; E y (x) 3) Ex (uv)= Ex (u)+ Ex (v), где u(x) и v(x) – функции (например, функции спроса и предложения); 4) Ex (u+v)= uE Χ (u ) + vE Χ ( v) . u+v Доказательство свойств 1) – 4) следуют из определения эластичности. 1.6. Эластичность спроса и предложения относительно цены Эластичность спроса относительно цены выражается формулой ED= P D ′, D Страница 9 из 184 согласно определению где D(p) ‐ функция спроса в зависимости от цены р. Эластичность ED определяет приблизительно, на сколько процентов изменится спрос на товар, если цена на него увеличится на 1%. Так как D(p) убывающая функция, то D′ (р) < 0, следовательно, ED< 0. Ввиду отрицательности эластичности спроса по цене, часто используют вместо ED её абсолютную величину, т.е. |ED|, причем, если ED ∈ (‐ ∞ ;0], то |ED| ∈ [0; + ∞ ). Аналогично определяется эластичность предложения относительно цены. Именно: p E S= ⋅ S ′ ; S Так как S(p) возрастающая функция, то S′ (р) > 0, и, следовательно, ES > 0. Эластичность ES показывает приближенно на сколько процентов изменится объем предложения при увеличении цены на 1%. ES ∈ [0; ∞ ;). ‐α Примеры. 1) D(p) = p , ED = ‐ α; 3) D (p)=b‐ap; ED= − α 2) S(p)= p , α > 0, ES= α; ap . b − ap Ввиду важности первого примера, выведем соотношение ED = − α . Действительно, ED= P p D ′ = ‐ α αpα −1 = ‐ α. p D Страница 10 из 184 Аналогично выводится соотношение ES= α из второго примера. Из первых двух примеров следует, что степенные функции имеют постоянную эластичность равную показателю степени. 1.7. Дуговая эластичность Рассмотрим понятие дуговой эластичности на примере эластичности спроса по цене. По определению, имеем последовательно: ED = D − D1 P1 + P2 D −D P + P ΔD P D1 − D2 (P1 + P2 ) / 2 ⋅ ⋅ = = 1 2⋅ 2 1 =− 2 ⋅ , P2 − P1 D1 + D2 ΔP D P2 − P1 (D1 + D2 ) / 2 P2 − P1 D1 + D2 Т.е. D −D P +P ED = − 2 1 ⋅ 1 2 . P2 − P1 D1 + D2 Из определения следует, что это показатель средней реакции спроса на изменение цены товара т.к. вместо цены р и спроса D берем их среднее значение (p1 + p2)/2 и (D1 +D2)/2 соответственно. 1.8. Классификация товаров по эластичности а) Товары эластичного спроса (предметы роскоши) (|ED|>1). Для таких товаров повышение цены на 1% соответствует понижению спроса больше, чем на 1%. б) Товары неэластичного спроса (товары первой необходимости) (|ED|<1). Страница 11 из 184 Для таких товаров повышение цены на 1% соответствует понижению спроса меньше, чем на 1%. в) Товары нейтрального спроса. Для таких товаров |ED| = 1 (Рис. 3) Неэласт. спрос Эластичный спрос |ED| 1 Нейтральный спрос Рис. 3 1.9. Примеры моделей с эластичностью 1) Предельная выручка. Пусть известна функция спроса: D(p)=x(p), тогда выручка R=x⋅p, где x – объём продукции, p – цена единицы продукции. Предельная выручка – это производная от выручки по цене: R ′ = ( x ⋅ p) ′ = x + p ⋅ p dx = x (1 + ⋅ x ′) . dp x Отсюда выводим R' = x (1 + ED ) = x (1 ‐ |ED|). Из последней формулы следует, что если спрос эластичен, т.е (1+ED) < 0, тогда R' < 0 и выручка убывает с возрастанием цены. Если спрос неэластичен, т.е. (1+ED)>0, то R' > 0 и выручка возрастает с увеличением цены. Страница 12 из 184 Вывод. а) При неэластичном (жестком) спросе продавцам выгодно повышать цены. б) При эластичном спросе продавцам выгодно снижать цены. Каждой фирме выгодно, чтобы спрос на ее продукцию был неэластичным. Для этого нужно прилагать усилия для поддерживания спроса на ее товар (качество товара, хорошая реклама). Пример. Пусть функция предложения имеет вид S(p)= 0,05p2 + p. Эластично ли предложение по цене? Решение. p (0,1p + 1) p p 0,1p + 1 E S= ⋅ S ′ = ⋅ (0,1p + 1) = = >1 2 S p ( , 05 p + 1 ) , 05 p + 1 0,05p + p Ответ. Предложение эластично. Пример. Уравнение спроса имеет вид D(p) = 100 4 − p . Найти эластичность и выяснить, как повлияет увеличение цены на выручку, если спрос составляет 150 ед. Решение. Находим цену при спросе D = 150. Имеем: 150 = 100 4− p. Решая это уравнение, находим р = 7/4. Далее вычислим эластичность: E= p 100 4 − p (100 4 − p )' = ‐ p = ‐7/18. 2( 4 − p ) Выручка R' = x (1 ‐ 7/18) > 0, т.е. выручка увеличится. Страница 13 из 184 2) Связь цены и предельных издержек монополиста. Известно, что фирма, функционирующая в условиях совершенной конкуренции, устанавливает цену на свою продукцию, равную предельным издержкам, именно: pc = MC = C' Монополист назначает цену: pM > pC: pM= pC (1+α) = C'(1 + α), где α может быть равно 10%, 20%,…. Выберем величину этой надбавки из условия максимизации прибыли, т.е. когда предельная выручка равна предельным издержкам: R' =С'. Тогда R ′( x ) = (p ⋅ x ) ′ = p( x ) + xp ′( x ) = ⎛ ⎞ ⎜ ⎛ ⎛ ⎛ x ⎞ 1 ⎟ 1 ⎞ 1 ⎟ = p⎜ 1 + ⎟⎟ = p⎜⎜1 − = p⎜⎜1 + ⋅ p′ ⎟⎟ = p⎜1 + ⎜ p ⎜ ⎝ p ⎠ ⎝ ED ⎠ ⎝ | ED ⋅ x′ ⎟⎟ ⎜ ⎝ ⎠ x ⎞. ⎟ | ⎟⎠ Из условия R' =С' получаем p= C′ . 1 1− |ED | Отсюда α = 1/ (|ED| ‐ 1). То есть надбавка α к предельным издержкам в цене тем меньше, чем выше эластичность спроса. При |ED| = 1 цена оказывается неопределенной величиной, при |ED| < 1 цена меньше нуля. То и другое не имеет экономического смысла. Следовательно, монополист максимизирует прибыль только при |ED| > 1. Страница 14 из 184 Упражнения 2 1. Зависимость спроса от цены дана формулой D(p) = e −p . Определите, при каких значениях р спрос эластичен, неэластичен, нейтрален. 2. Какие функции спроса и предложения имеют постоянную эластичность? (Указание: примените определение эластичности). 3. Пусть p ‐ цена (в тыс.руб.), q ‐ количество товара (в тыс.шт.). Среди следующих зависимостей найти функции спроса и предложения. a) q = p – 1; b) p = 5 – q/8; c) q = (p ‐ 1)(p – 1‐ p2); d) q = (p ‐ 1)(p + 1 + p2). 4. Известно, что при бесплатном входе на футбольный матч придет 30 тыс. болельщиков, а увеличение цены билета на каждый рубль сокращает их число на 300 человек. Какую цену за билет должен установить организаторы, если они хотят максимизировать выручку? 5. Производители телевизоров перепрофилировали часть мощностей предприятий на выпуск компьютерных мониторов. Это привело к росту средней цены на телевизоры с 5000 до 5500 руб. По старым ценам производители еженедельно реализовывали 10000 телевизоров. Сколько Страница 15 из 184 телевизоров в неделю продается по новым ценам, если известно, что коэффициент ценовой эластичности спроса на телевизоры равен 2,5? 6. В регионе, где выращивалась половина всей пшеницы, из‐за плохих погодных условий урожай по сравнению с прошлым годом сократился на 20%. В других регионах урожай остался на прошлогоднем уровне. Как изменится совокупная выручка всех фермеров, если ценовая эластичность спроса на зерно составляет ‐0,5? Решение. Пусть q1 количество пшеницы, собранной в регионе. Тогда общий урожай пшеницы во всех регионах по сравнению с прошлым годом составит q2 = 1/2 q1 + 0,8q1 = 0,9q1, то есть урожай пшеницы сократился на 10%, ∆q = ‐ 0,1q1. Ценовая эластичность спроса равна –0,5. . Отсюда Δp −01 , Δq Δp = =02 ,. =−05 ,, p1 −05 , q1 p1 Цена пшеницы возросла на 20%, p2 = 1/2. Совокупная выручка фермеров стала равной R2 = 0,9 q1∙ 1,2 p1 = 1,08q1 p1 = 1,08R1, то есть выросла на 8%. Страница 16 из 184 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛИНЕЙНАЯ ОПТИМИЗАЦИЯ) 2.1. Примеры задач линейного программирования На практике постоянно встречаются такие ситуации, когда достичь какого‐то результата можно не одним, а многими различными способами. В такой ситуации может оказаться и предприятие и отрасль и даже народное хозяйство страны в целом. Решение в этом случае ищется в каком‐то смысле наилучшее, оптимальное с точки зрения поставленной задачи. Сформулируем задачу с математической точки зрения. Пусть, например, F(x)‐ выражает прибыль, или затраты ресурсов. Тогда задача в общем виде запишется следующим образом: F(x) → max (min), x ∈S, (1) где S ‐ допустимое множество задачи. Задача (1) называется задачей оптимизации, F(x)‐ целевая функция. В этой главе целевая функция линейная, т.е. имеет вид: F(x) = с1x1 + c2x2 + …+ cxn Множество, которому должны принадлежать переменные задачи, т.е. допустимое множество S, задаётся линейными неравенствами, например: Страница 17 из 184 ⎧a11x1 + a12 x2 + ... + a1n xn ≤ b1 ⎪a x + a x + ... + a x ≤ b ⎪ 21 1 22 2 2n n 2 ⎨ ⎪.............................................. ⎪⎩am1 x1 + am2 x2 + ... + amn xn ≤ bm Замечание: допустимое множество S, может задаваться линейными равенствами или тем и другим.. Далее рассмотрим конкретные экономико‐математические модели задач линейного программирования 1. Задачи планирования производства. Для изготовления двух видов продукции Р1 и Р2 используется четыре вида ресурсов S1, S2, S3, S4. Запасы и затраты ресурсов приведены в таблице: Вид ресурса Запас ресурса Число ресурсов, затрачиваемых на изготовление единицы продукции Р1 Р2 S1 18 1 3 S2 16 2 1 S3 5 1 S4 21 3 Прибыль, получаемая от единицы продукции Р1 и Р2 равна соответственно 2 и 3 д. ед. Необходимо составить такой план производства продукции, при котором прибыль от её реализации будет максимальна. Страница 18 из 184 Матрица ⎛1 ⎜ ⎜2 ⎜0 ⎜⎜ ⎝3 3 ⎞ ⎟ 1⎟ 1⎟ ⎟ 0 ⎟⎠ (столбцы 3 и 4 таблицы) называется технологической матрицей. Построение математической модели. Пусть х1 и х2 – это число единиц продукции Р1 и Р2. Для их изготовления потребуется ресурса: S1: x1 + 3x2 ≤ 18 S2: 2x1 + x2 ≤ 16 S3: x2 ≤ 5 (2) S4: 3x1 ≤ 21 x1 ≥ 0, x2 ≥ 0 Суммарная прибыль дается целевой функцией: F = 2x1 + 3x2 → max (3) Требуется найти такой план выпуска продукции Х = (х1, х2), удовлетворяющий неравенствам (2) и при котором целевая функция F из равенства (3) принимает максимальное значение. Задача (2) и (3) – задача линейного программирования. 2. Задача о банке. Собственные средства банка 100 млн.$ с депозитами. Часть этих средств, не менее 35 млн.$, должна быть размещена в кредитах. Но кредиты – это неликвидные активы банка. Поэтому, Страница 19 из 184 чтобы компенсировать эту неликвидность, банки покупают ценные бумаги, которые должны составлять не менее 30 % средств, размещенных в кредитах и ценных бумагах. Построение математической модели: Пусть х1 – средства (млн. долл.), размещённые в кредитах, х2 – средства вложенные в ценные бумаги. Тогда из условий задачи получим неравенства: х1 + х2 ≤ 100 – балансовые ограничения х1 ≥ 35 – кредитные ограничения (4) (5) х2 ≥ 0,3 (х1 + х2 ) – ликвидные ограничения (6) х1 ≥ 0; х2 ≥ 0. (7) Цель банка – получить максимальную прибыль от кредитов и ценных бумаг: F = с1х1 + с2х2 → max, (8) где с1 и с2 ‐ доход кредитов и доход ценных бумаг. Так как кредиты менее ликвидны, чем ценные бумаги, то с1 > с2. Задача с целевой функцией (8) и ограничениями (4) – (7) – задача линейного программирования. 2.2. Стандартная и каноническая формы ЗЛП Наиболее часто встречаются три разновидности задачи линейного программирования. Первая стандартная форма задачи линейного программирования (ЗЛП) имеет следующий вид: Страница 20 из 184 F(x) = c1x1 + c2x2+ ...+ cnxn → max ⎧a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b1 ⎪a x + a x + ... + a x ≤ b 22 2 2n n 2 ⎪⎪ 21 1 ⎨.............................................. ⎪a x + a x + ... + a x ≤ b m2 2 mn n m ⎪ m1 1 ⎪⎩x i ≥ 0, i = 1,..., n (9) Введём следующие обозначения: А = (аij) – матрица коэффициентов левой части ограничений, c = (с1 с2…сn) – вектор коэффициентов целевой функции, x = (х1….хn)' – вектор переменных, b = (b1…bn)' – вектор правых частей ограничений. транспонирование. Тогда задача (9) запишется в матричном вид ⎧F = c ⋅ x → max ⎪ ⎨Ax ≤ b ⎪x ≥ 0 ⎩ Вторая стандартная форма ЗЛП имеет вид: ⎧F = c ⋅ x → min ⎪ ⎨Ax ≥ b ⎪x ≥ 0 ⎩ Каноническая форма ЗЛП имеет следующий вид: ⎧F(x ) = c ⋅ x → min(max) ⎪ ⎨Ax = b ⎪x ≥ 0 ⎩ Страница 21 из 184 Знак « ' » означает Заметим, что в этом случае система ограничений, помимо тривиальных ограничений х ≥ 0 , включает в себя только уравнения. Множество S, удовлетворяющее ограничениям Ax ≥ 0 (x ≥0) или Ax ≤ 0 (x ≥0), ‐ допустимое множество задачи линейного программирования. Любой набор x = (х1…хn) ∈ S называется планом или допустимым решением ЗЛП. Множество всех планов образуют область допустимых решений. План, который доставляет экстремум целевой функции называется оптимальным планом или оптимальным решением задачи линейного программирования. Указанные три разновидности ЗЛП сводятся одна к другой. Для наших целей нужно уметь сводить первых две формы к каноническому виду. Для этого вводятся дополнительные (балансовые) переменные, число которых равно числу неравенств в системе ограничений исходной задачи. Вводимые переменные, как и основные, являются неотрицательными. При построении канонической формы задачи ее целевая функция остается неизменной. Далее, если мы имеем в системе ограничений исходной задачи неравенство вида « ≤ », то мы добавляем в левую часть неравенства дополнительную переменную со знаком «+», а знак неравенства заменяем знаком равенства. Если же имеем в системе ограничений исходной задачи неравенство вида « ≥ », то мы вычитаем из левой части неравенства дополнительную переменную, а знак неравенства заменяем знаком равенства. Рассмотрим процесс построения канонической формы на примере. Страница 22 из 184 Пример. Привести к канонической форме задачу: F = х1 + 2 x2 → max ⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎩⎪ x x x x 1 1 1 1 ≥ 1 − x 2 − 2x + x , x 2 2 ≤ 1 ≤ 3 2 ≥ 0 Решение. Введем дополнительные неотрицательные переменные х3, х4 , х5 и заменим неравенства равенствами: ⎧x 1 − x 2 − x 3 = 1 ⎪ ⎪x 1 − 2 x 2 + x 4 = 1 ⎨ ⎪x 1 + x 2 + x 5 = 3 ⎪x ≥ 0, i = 1,...,5 ⎩ i Целевая F функция остается прежней. Упражнения. Привести задачи к канонической форме. 1) F = х1 ‐ 2 x2 + 3x3 → min, ⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎪⎩ − 1 x + 2 1 − x − 1 x ,x 1 2 2 x x 2 x 3 2 x ≥ 0 + 3x = 8 2 ≥ 1 3 2) F = 2х1 + x2 ‐ 3x3 → max ≤ 5 ⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎪⎩ x x x 1 1 1 − 2 x + x 2 + 3x x , x 1 2 + x 2 − 3x 2 ≥ 0 3 3 + 2 x ≥ 4 ≤ 9 3 = 10 2.3. Графический метод решения задач линейного программирования Страница 23 из 184 Самым простым методом решения ЗЛП является графический метод. Однако практически этим методом можно решать задачи, имеющие только две переменные. Рассмотрим сначала схему решения ЗЛП этим методом. Пусть допустимая область решения задачи это выпуклая многоугольная область S, имеющая вид пятиугольника (Рис.3.1). Угловые точки области называются X2 A вершинами (это точки 0, А, В, С, Д). B Целевая функция C S F = c1x1 n + c2x2 . D Задача состоит в том, чтобы найти X1 экстремум функции F на допустимом Рис.3.1 множестве S. Для определенности будем искать максимум, т. е., F → max. Определение. Множество {x ∈ R2 : c1x1 + c2x2 = const} называется линией уровня функции f(x). Из теории известно, что градиент функции X2 показывает направление наискорейшего роста A B функции в данной точке и он перпендикулярен C линии S D X1 Рис.3.2 целевой функции. Следовательно, построив в точке (0;0) вектор n уровня градиента целевой функции (нормаль) n = (c1, c2) и двигая в направлении этого вектора линию уровня функции, мы будем получать все большие и большие значения функции. Ясно, что двигать линию уровня можно до тех пор, пока она не заденет последнюю точку допустимого Страница 24 из 184 множества S. Эта последняя точка и есть точка максимума целевой функции F. На Рис.3.1 это точка В. Координаты этой точки и есть оптимальное решение нашей задачи. Из геометрических соображений ясно, что если решение существует, то оно не может бать внутренней точкой множества S, а должно принадлежать его границе. Следовательно, решением может являться координаты одной вершины (Рис.3.1), или координаты двух вершин и все точки, лежащие между ними, т.е. выпуклая комбинация этих вершин. На Рис.3.2 оптимальным решением является отрезок ВС. Запишем эти выводы в виде теорем. Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования (множество S), является выпуклым, т.е. если x1 и x2 ∈ S, то x = α x1 + (1 ‐ α) x2 ∈ S , α ∈[0, 1]. Теорема 2. Если задача линейного программирования имеет оптимальное решение, то целевая функция принимает максимальное или минимальное значение в одной из вершин допустимого множества. Если целевая функция принимает экстремальное значение в двух вершинах, то она принимает экстремальное значение в любой точке отрезка, соединяющей эти вершины. 2.3.1. Графическое построение допустимого множества В задаче линейного программирования мы имеем m неравенств вида ai1x1 + ai2x2 ≥ bi i = 1,…m. Страница 25 из 184 Эти неравенства должны выполняться одновременно. Следовательно, область, определяемая этими неравенствами, геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями. Для построения допустимого множества нужно научиться изображать графически неравенства вида a11x1 + a12x2 ≥ b, (≤ b). Теорема. Множеством решений неравенства a11x1 + a12x2 ≥ b, (≤ b). является одна из полуплоскостей, на которые вся плоскость делится прямой a11x1 + a12x2 =b, включая эту прямую. Линейному уравнению a1x1 + a2x2 =b на плоскости соответствует прямая (Рис.3.3). Обратим прежде всего внимание на ограничения x1 ≥ 0, x2 ≥ 0. Из этих ограничений следует, что допустимое X2 располагаться координатной b a2 Рассмотрим множество в S будет первой четверти системы x10x2. теперь, какие области соответствуют неравенствам вида a1x1 + b a1 Рис.3.3 X1 a2x2 ≤ (≥) b . Сначала рассмотрим область, соответствующую равенству a1x1 + a2x2 = b . Графиком этого уравнения является прямая линия. Страница 26 из 184 Строить её проще всего по двум точкам. Пусть b ≠ 0. Полагая x1 = 0, находим x2 = b/a2. Полагая x2 = 0, находим x1 = b/a1. Через две найденные точки (0, b/a2) и (0, b/a1) проводим искомую прямую (Рис.3.3). Если b= 0, то прямая проходит через начало координат (0, 0), поэтому для нахождения второй точки можно взять любое отличное от нуля значение одной координаты, например, x1 = 1. Тогда x2 = ‐ a1 /a2. В этом случае прямая будет проходить через точки (0, 0) и (1, ‐ a1 /a2). Полученная прямая определяемые неравенствами делит плоскость на две полуплоскости, a1x1 + a2x2 > b и a1x1 + a2x2 < b. Для определения расположения полуплоскости относительно прямой a1x1 + a2x2 =0, возьмем, например, неравенство a1x1 + a2x2 > b . Если a2 > 0, то полуплоскость расположена выше прямой a1x1 + a2x2 =b, при a2 < 0 полуплоскость расположена ниже прямой a1x1 + a2x2 =b. Если полуплоскость определена неравенством a1x1 + a2x2 < b, то если a2 > 0, то полуплоскость расположена ниже прямой a1x1 + a2x2 = b, при a2 < 0 полуплоскость расположена выше прямой a1x1 + a2x2 =b. Другой метод определения полуплоскости относительно прямой заключается в следующем. Возьмем для испытания любую точку, явно принадлежащую одной из полуплоскостей. Если прямая не проходит через начало координат, то в качестве такой точки удобно брать начало координат. Координаты пробной точки подставляют в неравенство (например, в a11x1 + a12x2 ≥ b). Если неравенство выполняется, значит пробная точка лежит на искомой полуплоскости, иначе – на противоположной стороне от прямой. Пример. Построить полуплоскость, определяемую неравенством Страница 27 из 184 4x1 ‐ 6x2 ≤ 3. Решение. Строим прямую 4x1 ‐ 6x2 = 3. Для этого найдем две точки, через которые проходит наша прямая. При x1 = 0, x2 = ‐1/2, при x1.=3/4 = 0,75. X1 x2 = 0, Следовательно, прямая проходит через точки (0; ‐1/2 ) и (0,75; 0). 4x1‐6x2 <3 Так как коэффициент при x2 < 0, то полуплоскость 4x1 ‐ 6x2 < 3 расположена ‐0,5 0.75 X1 выше прямой 4x1 ‐ 6x2 обстоятельство Рис.3.4 Рис.3.4). указано = 3. (это стрелкой на Следовательно, неравенство 4x1 ‐ 6x2 ≤ 3 определяет множество, состоящее из прямой 4x1 ‐ 6x2 = 3 и полуплоскости, расположенной выше этой прямой (Рис.3.4). Применим изложенное выше для построения допустимого множества задачи линейного программирования. Пример. Найти допустимую область задачи линейного программирования, определяемую ограничениями ⎧− x 1 + x 2 ≤ 1 ⎪x − x ≤ 1 ⎪ 1 2 ⎨ ⎪x 1 + x 2 ≤ 3 ⎪⎩x 1 ≥ 0, x 2 ≥ 0. Решение. Рассмотрим прямую ‐x1 + x2 =1. При x1 = 0, x2 = 1. Если x2 = 0, x1 = ‐ 1. Таким образом, эта прямая проходит через точки (0,1) и (‐ 1,0). Учитывая, что коэффициент при x2 > 0, находим, что полуплоскость ‐x1 + x2 <1 расположена ниже прямой ‐x1 + x2 =1. Обозначим эту прямую на Страница 28 из 184 Рис.3.5 цифрой (1) и стрелкой вниз укажем расположение полуплоскости ‐x1 + x2 <1. Аналогично рассматриваются остальные два неравенства. Именно, прямая x1 ‐ 2x2 = 1 проходит через точки (0; ‐1/2) и (1;0), а полуплоскость x1 ‐ 2x2 <1 расположена выше прямой x1 ‐ 2x2 = 1. Отметим эту прямую на Рис.3.5 цифрой (2) и стрелкой вверх. Наконец, рассмотрим прямую x1 + x2 =3. Она проходит через точки (0,3) и (3,0) и так как коэффициент при x2 > 0 то интересующая нас полуплоскость лежит ниже прямой x1 + x2 =3. Обозначим эту прямую на Рис.3.5 цифрой (3) и стрелкой вверх. Находим допустимое множество как пересечение найденных полуплоскостей. Легко видеть, что это будет пятиугольник S. X2 (1) (3) 3 (2) S 1 ‐1 ‐1/2 1 3 X1 Рис.3.5 2.3.2 Алгоритм графического метода решения задач линейного программирования Алгоритм графического метода дадим на примере решения следующей задачи: Страница 29 из 184 F = 2x1 + x2 → max ⎧− x 1 + x 2 ≤ 1 ⎪x − x ≤ 1 ⎪ 1 2 ⎨ ⎪x 1 + x 2 ≤ 3 ⎪⎩x 1 ≥ 0, x 2 ≥ 0. 1. Строим допустимое множество задачи. Это множество S из предыдущего примера (см. Рис.3.5) X2 С S 1 n А X1 1 Рис.3.6 2. Строим линию уровня целевой функции F = 2x1 + x2 = C при С = 0. Уравнение линии уровня: 2x1 + x2 = 0 или x2 = ‐ 2 x1 . На Рис.3.6 линия уровня обозначена через С. 3. Если целевая функция имеет общий вид F = c1x1 + c2x2, то вектор градиента (нормаль) имеет своими координатами частные производные от функции F, т.е. n = ( ∂F / ∂x1 ; ∂F / ∂x 2 ) = (c1, c2). В нашем случае нормаль n = (2; 1). На Рис.3.6 она обозначена через n. Страница 30 из 184 Вектор градиента перпендикулярен линии уровня целевой функции и показывает направление, в котором значение функции возрастают. Поэтому в поисках максимума надо линию уровня двигать параллельно самой себе в направлении вектора n. 4. Последняя точка, по которой линия уровня будет пересекать допустимое множество и будет точкой максимума целевой функции. Координаты этой точки – оптимальное решение задачи. В нашем случае это точка А. Нам остается найти координаты этой точки и подставить их в целевую функцию. Так как точка А является пересечением прямых (3) и (2), то решая систему уравнений, определяющих прямые (2) и (3), получаем оптимальное решение: ⎧x 1 − x 2 = 1 ⎨ ⎩x 1 + x 2 = 3 → x1 = 2, x2 = 1. Следовательно, максимальное значение целевой функции реализуется в точке (х1*, х2* ) = (2, 1) и равно max F = F(2; 1) = 2 ∙ 2 + 1 = 5. Замечание. Если решается задача на минимум, то пункты 1. – 4. верны, за исключением того, что линию уровня нужно двигать в сторону, противоположную нормали n. Пример. Решим графическим методом поставленную ранее задачу о банке: х1 + х2 ≤ 100 х1 ≥ 35 х2 ≥ 0,3 (х1 + х2 ) Страница 31 из 184 (1) (2) (3) х1 ≥ 0; (4) х2 ≥ 0. (5) F = 0,15х1 + 0,1х2 → max, Решение. Строим допустимое множество задачи, заданное неравенствами 1) – 5), аналогично предыдущему примеру. В результате получаем допустимое множество в виде треугольника (выделен на Рис.3.7). X2 (1) (2) (3) А(70,30) С n 35 X1 Рис.3.7 Вектор градиента n = (0,15; 0,1). Двигая линию уровня целевой функции C по направлению вектора n, находим, что точка максимума А находится на пересечении прямых (1) и (3). Ее координаты получаются решением следующей системы уравнений: ⎧x 1 + x 2 = 100, → (х1, х2 ) = (70, 30). ⎨ x = 0,3(x + x ). ⎩ 2 1 2 Следовательно, оптимальный портфель активов имеет структуру Страница 32 из 184 (х1*, х2* ) = (70, 30). Максимальная прибыль составит Fmax = F(70, 30) = 0,15∙70 + 0,1∙30 = 13,5. Упражнения. I. Решить графическим методом следующие задачи: 1) Max F = 2x1 + 2x2 2) Max F = 3x1 + x2 3x1 – 2x2 ≥ ‐6 ; 2 x1 + 3x2 ≥ 12 ; 2x1 + x2 ≥ 3; –x1 + x2 ≤ 2; x1 ≤ 3; 2x1 – x2 ≤ 2; x1, x2 ≥ 0 x1, x2 ≥ 0. 3) Min F = 3x1 + 2x2 4) Max F = 3x1 + 5x2 x1 + 2x2 ≥ 12; x 1 + x2 ≤ 5 ; –2x1 – x2 ≥ 12; x1 + 3x2 ≤ 14 ; 3x1 + 2x2 ≤ 8; x1, x2 ≥ 0 x1, x2 ≥ 0 5) Min F = ‐x1 ‐ x2 6)Max F = 3x1 – 6x2 Страница 33 из 184 x1 + x2 ≥ 1 ; x1 – x2 ≥ 0 ; –x1 + x2 ≤ 1; –2x1 + x2 ≤ 6; – x1 + x2 ≥ – 1; x1 ≤ 2; x2 ≤ 2; 4x1 ≤ 7; x1, x2 ≥ 0. x1, x2 ≥ 0. 7) Max F = –2x1 – x2 x1 + 2 x 2 ≥ 2 ; 8) Max F = 3x1 + 3x2 x1 + x2 ≤ 8 ; –2x1 + x2 ≤ 0; 2x1 – x2 ≥1; – x1 + 2x2 ≥ 0; x1 – 2x2 ≤ 2 x1, x2 ≥ 0. x1, x2 ≥ 0. II. Построить математическую модель и решить графическим методом задачи: 1. Завод выпускает обычные станки и станки с программным управлением, затрачивая на один обычный станок 200 кг стали и 200 кг цветного металла, а на один станок с программным управлением 700 кг стали и 100 кг цветного металла. Завод может израсходовать в месяц до 46 тонн стали и до 22 тонн цветного металла. Сколько станков каждого типа должен выпустить за месяц завод, чтобы объем реализации был максимальным, если один обычный станок стоит 2000 д.е., а станок с программным управлением 5000 д.е. Страница 34 из 184 2. Для производства двух видов изделий А и В используется три типа технологического оборудования. На изготовление одного изделия А оборудование первого типа используется в течение 5 ч., второго ‐ в течение 3 ч. и третьего ‐ 2 ч. На производство одного изделия В, соответственно: 2 ч., 3 ч. и 3 ч. В плановом периоде оборудование первого типа может быть использовано в течение 505 ч., второго ‐ 394 ч. и третьего ‐ 348 ч. Прибыль от реализации одного изделия А равна 7 д.е., В ‐ 4 д.е. Составить план производства, максимизирующий прибыль предприятия. 3. Для изготовления изделий А и В предприятие использует три вида сырья. На производство одного изделия А требуется сырья первого вида 15 кг, второго ‐ 11 кг, третьего ‐ 9 кг, а на производство одного изделия В, соответственно, 4 кг, 5 кг, 10 кг. Сырья первого вида имеется 1095 кг, второго ‐ 865 кг, третьего ‐ 1080 кг. Составить план производства, максимизирующий прибыль, если прибыль от реализации единицы изделия А составляет 3 д.е., В ‐ 2 д.е. 4. Для производства изделий А и В используются три вида оборудования. При изготовлении одного изделия А оборудование первого вида занято 7 ч., второго ‐ 6 ч. и третьего ‐ 1 ч. При изготовлении одного изделия В, соответственно, 3 ч., 3 ч. и 2 ч. В месяц оборудование первого вида может быть занято 1365 ч., второго ‐ 1245 ч. и третьего ‐ 650 ч. Составить план производства, максимизирующий прибыль, если прибыль от реализации одного изделия А равна 6 д.е., изделия В ‐ 5 д.е. 5. Для изготовления изделий А и В используется три вида сырья. На изготовление одного изделия А требуется 9 кг сырья первого вида, 6 кг сырья второго вида и 3 кг сырья третьего вида. На изготовление одного изделия В требуется, соответственно, 4 кг, 7 кг и 8 кг сырья. Производство обеспечено сырьем первого вида в количестве 801 кг, второго ‐ 807 кг, третьего ‐ 703 кг. Прибыль от продажи изделия А равна 3 д.е., изделия В ‐ 2 д.е. Составить план производства, максимизирующий прибыль. 6. Завод выпускает два вида редукторов. На изготовление одного редуктора первого вида расходуется 4 тонны чугуна и 1 тонна стали, а на изготовление одного редуктора второго вида 2 тонны чугуна и 1 тонна стали. Завод располагает на месяц 160 тоннами чугуна и 120 тоннами стали. Страница 35 из 184 Составить месячный план производства редукторов, максимизирующий прибыль завода, если прибыль от продажи одного редуктора первого вида равна 400 д.е., а второго ‐ 200 д.е. 7. Для производства изделий А и В используются три вида станков. На производство одного изделия А требуется 6 ч. работы станка первого вида, 4 ч. работы станка второго вида и 3 ч. работы станка третьего вида. На производство одного изделия В требуется 2 ч. работы станка первого вида, 3 ч. работы станка второго вида и 4 ч. работы станка третьего вида. Месячный ресурс работы всех станков первого вида, имеющихся на заводе равен 600 ч., всех станков второго вида ‐ 520 ч. и всех станков третьего вида ‐ 600 ч. Прибыль от реализации одного изделия А равна 6 д.е., изделия В ‐ 3 д.е. Составить план производства на месяц, максимизирующий прибыль предприятия. 8. На ферме разводят нутрий и кроликов. В недельный рацион нутрий входят 17 кг белков, 11 кг углеводов и 5 кг жиров, а для кроликов эти нормы, соответственно, равны 13 кг, 15 кг и 7 кг. Доход от реализации одного кролика 20 д.е., а от реализации одной нутрии 25 д.е. Найти план разведения животных, максимизирующий доход фермы, если ферма не может расходовать в неделю более 184 кг белков, 152 кг углеводов и 70 кг жиров. 9. Для изготовления изделий А и В предприятие использует три вида сырья. На производство одного изделия А требуется 12 кг сырья первого вида, 10 ‐ второго и 3 ‐ третьего, а на производство одного изделия В, соответственно, 3 кг, 5 кг, 6 кг. Производство обеспечено сырьем первого вида в количестве 684 кг, второго ‐ 690 кг и третьего 558 кг. Одно изделие А дает предприятию 6 д.е. прибыли, изделие В ‐ 2 д.е. Составить план производства, максимизирующий прибыль предприятия. 10. Мастерская по покраске кузовов автомобилей рассчитана на покраску не более 160 кузовов в месяц. На покраску кузова “Москвича” краски расходуется 4 кг, а кузова “Волги” ‐ 7 кг. Мастерская располагает 820 кг краски на месяц. Составить месячный план покраски автомобилей, максимизирующий прибыль мастерской, если покраска одного “Москвича” дает 30 д.е. прибыли, а одной “Волги” ‐ 40 д.е. прибыли. Страница 36 из 184 Страница 37 из 184 3. ВЗАИМНО ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 3.1. Постановка взаимно двойственных задач С каждой задачей линейного программирования связана другая задача, двойственная по отношению к исходной. Совместное изучение данной задачи и двойственной к ней дает информации значительно больше, чем изучение каждой из них в отдельности. Рассмотрим производственную задачу, приводящую к понятию двойственной задачи. На предприятии возник вопрос о том, как поступить с остатками сырья после выполнения плана по выпуску некоторых изделий. Оказалось, что существуют две возможности: 1) можно наладить из этих остатков производство ширпотреба. 2) продать сырье. Рассмотрим эти две возможности. Для этого поставим следующую задачу: Имеем 2 вида сырья S1 и S2‐ 35 ед., 20 ед. соответственно. Из этих остатков можно наладить производство 3‐х видов товаров Т1, Т2, Т3. От реализации единицы каждого товара предприятие получит прибыль: 7 д.е., 6 д.е. и 18 д.е. соответственно. Норма расхода сырья на производство товаров Тi, запасы и прибыль даны в таблице. S1 S2 Страница 38 из 184 Прибыль Т1 1 2 7 Т2 1 1 6 Т3 5 2 18 Запасы 35 20 Первая возможность. Наладить выпуск товаров Т1, Т2, Т3. Пусть xi ‐ объём выпуска товара Тi. С помощью таблицы выписываем неравенства, которые определяют нормы расходования сырья S1 и S2 (по столбцам таблицы): ⎧x1 + x2 + 5x3 ≤ 35 : S1 ⎪ ⎨2x1 + x2 + 2x3 ≤ 20 : S2 ⎪x ≥ 0 ⎩ i (1 ) Прибыль от реализации товара в количестве (x1, x2, x3 ) будет равна: F = 7x1 + 6x2 + 18x3 В интересах предприятия максимизировать эту прибыль: F = 7x1 + 6x2 + 18x3→ max (2) Чтобы наилучшим образом использовать первую возможность, нужно решить задачу линейного программирования (2) при условии (1). Назовем задачу (1) и (2) задачей I. Страница 39 из 184 Вторая возможность. Продать сырье другой организации. Возникает вопрос, по каким ценам продать сырье? Обозначим эти цены через y1, y2. Очевидно, должны быть выполнены неравенства y1 ≥ 0, y2 ≥ 0. Требования со стороны предприятия: выручка от продажи сырья должна быть не меньше, чем прибыль от реализации готовой продукции. Это требование приводит к неравенствам (по строкам таблицы): ⎧ y 1 + 2y 2 ≥ 7 ⎪y + y ≥ 6 ⎪ 1 2 ⎨ ⎪5y 1 + 2y 2 ≥ 18 ⎪⎩ y i ≥ 0 (3) Например, первое неравенство означает, что выручка от продажи единицы сырья S1 и двух единиц S2 не меньше, чем прибыль, которую могло бы получить предприятие от продажи единицы товара Т1,если оно реализовало первую возможность. Аналогичный смысл имеют остальные два неравенства. Требования покупателя: сокращение до минимума расходов на покупку сырья. g(y1,y2) = 35y1 + 20y2 → min. Следовательно, для оптимального (4) использования второй возможности необходимо решить задачу (4) при условиях (3). Назовем задачу (3) и (4) задачей II. Запишем формулировки задач I и таблицы. Страница 40 из 184 II в виде Задача I Задача II ⎧x 1 + x 2 + 5x 3 ≤ 35, ⎪ ⎨2x 1 + x 2 + 2x 3 ≤ 20, ⎪x ≥ 0, x ≥ 0. 2 ⎩ 1 ⎧ y 1 + 2y 2 ≥ 7, ⎪ y + y ≥ 6, ⎪ 1 2 ⎨ ⎪5y 1 + 2y 2 ≥ 18, ⎪⎩ y 1 ≥ 0, y 2 ≥ 0. F = 7x1 + 6x2 + 18x3→ max g(y1,y2) = 35y1 + 20y2 → min. Задачи I и II называются двойственными друг другу. Каким образом решается поставленный выше производственный вопрос о том, какую из двух возможностей для реализации остатков сырья следует выбрать, рассмотрим ниже. 3.2. Связь между прямой и двойственной задачами. 1) Матрицы из коэффициентов в левых частях ограничений взаимно транспонированы. Действительно, в задаче I матрица из коэффициентов в ограничениях при x1, x2, x3 есть ⎛1 1 5 ⎞ ⎜⎜ ⎟⎟ , 2 1 2 ⎝ ⎠ Страница 41 из 184 В задаче II матрица из коэффициентов в ограничениях при y1, y2, есть ⎛1 2 ⎞ ⎜ ⎟ ⎜1 1 ⎟ ⎜5 2 ⎟ ⎝ ⎠ 2) Правые части ограничений каждой задачи образуют коэффициенты при неизвестных в целевой функции другой задачи. 3) Знаки неравенств меняются на противоположные, т.е. знак «≤» меняется на знак « ≥ » и знак « ≥ » на знак « ≤ ». 4) Если в одной задаче требуется найти максимум, то в другой минимум функции цели. Например, в задаче I требуется достичь максимума, а в задаче II – минимума. 3.3. Матричный вид задачи Запишем двойственные задачи I и II в более общей форме. Для этого рассмотрим задачу: F = c1x1 + c2x2 + c3x3 → max ⎧а11х1 + a12x2 + a13x3 ≤ b1 ⎨ ⎩a21x1 + a22x2 + a23x3 ≤ b2 Тогда задача I и II (5) формулируются в следующем виде: I II Страница 42 из 184 ‐ ⎧а 11 х 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ⎨ ⎩a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ⎧a 11 y 1 + a 21 y 2 ≥ c 1 ⎪ ⎨a 12 y 1 + a 22 y 2 ≥ c 2 ⎪a y + a y ≥ c 23 2 3 ⎩ 13 1 (6) F = c 1 x 1 + c 2 x 2 + c 3 x 3 → max (7) g = b 1 y 1 + b 2 y 2 → min Введем матрицу из коэффициентов при неизвестных в системе (6): А= ⎛ а 11 а 12 а 13 ⎞ ⎜⎜ ⎟⎟ . а а а ⎝ 21 22 23 ⎠ Тогда матрица А', составленная из коэффициентов при неизвестных yi в системе (7) есть транспонированная матрица А: ⎛ а11 а 21 ⎜ А' = ⎜ а12 а 22 ⎜а а ⎝ 13 23 ⎞ ⎟ ⎟ ⎟ ⎠ Введем также матрицы ‐ столбцы (знак « ' » означает транспонирование) ⎛ x1 ⎞ ⎜ ⎟ ⎛ b1 ⎞ В = (b1, b2)' = ⎜⎜ ⎟⎟ , X= (x1, x2, x3)' = ⎜ x 2 ⎟ , C= (c1, c2, c3) , ⎝b2 ⎠ ⎜x ⎟ ⎝ 3⎠ Y = (y1, y2). Тогда задачи I и II в матричных обозначениях запишутся в виде: I II AX ≤ B, YА ≥ C, Страница 43 из 184 X ≥ 0, Y ≥ 0, F = CX → max. g = YВ → min. В таком виде может быть задана любая пара взаимно двойственных задач линейного программирования. При этом задача I может иметь произвольные размеры m × n, а задача II – соответственно n × m. Пример. Построить двойственную задачу к следующей задаче линейного программирования: F = 5x1 + 2x2 + 3x3 + 10 → min. ⎧2х 1 + х 2 − х 3 ≤ 5, ⎪ ⎪х 1 + 2х 2 + х 3 ≥ 4, ⎨ ⎪х 1 + х 2 + 2х 3 ≥ 8, ⎪⎩х i ≥ 0. Решение. Приведем данную задачу ко второй стандартной форме. Для этого изменим знак неравенства у первого ограничения исходной задачи на противоположный (умножим это неравенство на (‐1)). Ограничения примут вид: ⎧− 2х 1 − х 2 + х 3 ≥ −5 ⎪х + 2х + х ≥ 4 ⎪ 1 2 3 ⎨ ⎪х 1 − х 2 + 2х 3 ≥ 8 ⎪⎩х i ≥ 0 Принимая во внимание пункты 1) – 4), записываем двойственную задачу: Страница 44 из 184 Ограничения: ⎧− 2у 1 + у 2 + у 3 ≤ 5 ⎪ ⎨− у 1 + 2у 2 − у 3 ≤ 2 ⎪ у + у + 2у ≤ 3 2 3 ⎩ 1 Целевая функция: g(y 1 ,y 2 ,y 3 ) = ‐5y 1 +4y 2 + 8y 3 + 10 → max. Нетрудно видеть, что задача, двойственная к двойственной задаче, есть прямая задача. программирования Обладающие называются таким свойством задачи линейного симметричными. Задачи (I) и (II) симметричные. В таких задачах система ограничений задается в виде неравенств и на переменные наложено условие неотрицательности. В нессимметричных задачах система ограничений прямой задачи задается равенствами, а в двойственной ‐ неравенствами, причем в последней переменные могут быть отрицательными. Так как систему неравенств при помощи вспомогательных переменных можно свести к системе равенств, то всякую пару симметричных задач можно представить в виде пары несимметричных. Правила построения двойственных задач и в этом случае остаются те же, за исключением того, что переменные двойственной задачи могут быть отрицательны. Пример. Рассмотрим прямую задачу: F = 7x1 + 2x2 + 8x3→ max при ограничениях 3x1 ‐ 4x2 + x3 ≤ 12, Страница 45 из 184 8x1 + 6x2 + 9x3 = 6, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Эта задача в канонической форме имеет вид: F = 7x1 + 2x2 + 8x3+ 0 x4 → max 3x1 ‐ 4x2 + x3 + x4 = 12, 8x1 + 6x2 + 9x3 + 0 x4 = 6, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0. Вспомогательная переменная x4 введена в первое ограничение и целевая функция от нее не зависит, поэтому x4, входит в F и во второе ограничение с коэффициентом 0. Используя правила 1) – 4), сформулируем двойственную задачу: g = 35y1 + 20y2 → min ⎧3y 1 + 8y 2 ≥ 7, ⎪- 4y + 6 y ≥ 2, ⎪ 1 2 ⎨ y + 9y ≥ 8, 2 ⎪ 1 ⎪⎩ y 1 + 0 y 2 ≥ 0, или y 1 ≥ 0. y2 не имеет ограничения в знаке. 3.4. Экономический смысл двойственной задачи Рассмотрим задачу линейного программирования в общем виде: Страница 46 из 184 n ∑c x F= j =1 j j → max, n ∑a j=1 ij x j ≤ bi, i = 1,2,…,m, (8) xj ≥ 0, j = 1,2,…,n.. С задачей (8) связана задача максимизации дохода при производстве некоторой продукции при наличии ограничения на ресурсы. Коэффициенты cj при переменных в целевой функции имеют смысл прибыли, получаемой при производстве единицы продукции j– го вида, а коэффициенты аij имеют смысл затрат i – го ресурса, расходуемого при производстве единицы продукции j– го вида. Двойственная к задаче (8) задача линейного программирования имеет вид: m g= ∑b y i =1 i i → min, m ∑a i =1 ij y i ≥ cj, j = 1,2,…,n, (9) yi ≥ 0, i = 1,2,…,m. Переменные у = (у1,…..,уm) двойственной задачи называются фиктивными или теневыми ценами ресурсов или оценкой ресурсов. Тогда Страница 47 из 184 m ∑b y i =1 i i = b1y1 + b2y2+…+ bmym цена ресурсов, то есть стоимость затрат. Экономический смысл двойственной задачи (9) можно сформулировать так: какую цену следует назначить единице каждого из ресурсов bi, чтобы при заданных величинах дохода сj от производства единицы каждого вида продукции минимизировать стоимость затрат. 3.5. Теоремы двойственности и их экономический смысл Теорема 1. Для любых допустимых решений х = (x1, x2,…,xn) и у = (у1,…..,уm) исходной и двойственной задач справедливо неравенство F(x) ≤ φ (y) или ∑ ci xi ≤ ∑ yj bj Экономический смысл производства х = (x1, x2,…,xn) теоремы: никакой допустимый план не может извлечь из запасенных ресурсов больше, чем их суммарная оценка, то есть больше, чем в них содержится. Теорема 2 (основная теорема двойственности). Если одна из взаимно двойственных задач (8) или (9) имеет оптимальное решение, то его имеет и другая. Причем оптимальные значения их целевых функций равны, то есть max F = min φ. Страница 48 из 184 Если хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения. Экономический смысл: Теорема утверждает, что только оптимальный план извлекает из ресурсов в точности столько, сколько в них содержится. С помощью теоремы 1 ответим на поставленный производственный вопрос – какую из двух возможностей для реализации остатков сырья следует использовать. Ответ: любую! Действительно, равенство max F = min φ означает, что максимальная прибыль, которую можно получить от изготовления остатков сырья продукции Т1, Т2, Т3, совпадает с выручкой от продажи сырья т.е. ∑ ci xi = ∑ yj bj. Далее сформулируем теорему существования оптимального решения и следствия из нее, которые позволят в некоторых случаях сводить задачу линейного программирования размерности больше двух к задаче размерности два, которую можно решить графическим методом. Теорема 3. Для того, чтобы векторы х = (x1, x2,…,xn) и у = (у1,…..,уm) были оптимальными решениями задач (8) и (9), необходимо и достаточно, чтобы выполнялись следующие равенства: m xj ( ∑ a i j y i ‐ cj ) = 0, j = 1,2,…,n; (10) i =1 n yi( ∑ a i j x j ‐ bi), i = 1,2,…,m.. (11) j =1 Условия (10) и (11) называются условиями дополняющей нежесткости. Страница 49 из 184 Пусть векторы х = (x1, x2,…,xn) и у = (у1,…..,уm) являются оптимальными решениями. Тогда: m Следствие 1. Если ∑a i =1 ij y i > cj , то xj = 0, j = 1,2,…,n; m и если xj > 0, то ∑a i =1 ij y i = cj, n Следствие 2. При выполнении неравенства ∑a j =1 ij x j < bi, получаем, что n yi = 0, i = 1,2,…,m, и при yi > 0, следует, что ∑a j =1 Следовательно, если в оптимальной точке ij x j = bi. некоторое ограничение выполняется как строгое неравенство, то соответствующая двойственная переменная равна нулю, а если в этой точке некоторая переменная двойственной задачи принимает положительное значение, то соответствующее ограничение прямой задачи выполняется как равенство. Экономический смысл следствий 1 и 2 следующий. n Пусть выполнено условие ∑a j =1 ij x j < bi. Это неравенство означает, что расход сырья Si строго меньше его запаса, т.е. сырье Si не дефицитно. В этом случае, согласно следствию 2, имеем yi = 0, т.е. продажная цена сырья Si должна равняться нулю. Мы видим, что величина yi выступает в роли «меры дефицитности» сырья Si. Отсюда и название для двойственной переменной yi – двойственные цены, или объективно обусловленные оценки. Страница 50 из 184 Можно показать, что если увеличить запас сырья Si , то это не окажет влияния на прибыль, т.е. на максимум целевой функции F. n Если yi > 0, то, согласно следствию 2, ∑a j =1 ij x j = bi , т.е. ресурс полностью израсходован, что означает его дефицитность. Пример. Решить задачу с помощью двойственной: F = 4x1 + 3x2 ‐ 30x3 → min, x1 ‐ 6 x3 ≥ 1, 2 ‐ x2 + 5x3 ≤ 0, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Решение. Запишем задачу в стандартном виде. Для этого умножим второе ограничение на (‐ 1) и двойку перенесем в правую часть неравенства. F = 4x1 + 3x2 ‐ 30x3 → min, x1 ‐ 6 x3 ≥ 1, x2 ‐ 5x3 ≥ 2, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Составим двойственную задачу: g = y1 + 2y2 → max, y1 ≤ 4, (11) y2 ≤ 3, (12) ‐ 6y1 ‐ 5y2 ≤ ‐ 30, Страница 51 из 184 (13) y1 ≥ 0, y2 ≥ 0, Решим эту задачу графическим методом. На рис.3.1 изображены область допустимых y2 решений задачи (выделенный треугольник), нормаль n = (2,1). Двигая линию уровня R Y=(4,3) целевой функции в сторону нормали 3 n до тех пор, пока она не заденет n последнюю R y1 4 точку множества, получим точку Y = (4,3). (Точка Y находится на Рис.3.1 допустимого пересечении прямой y1 = 4, y2 = 3). Координаты этой точки и определяют оптимальное решение двойственной задачи (4,3). Подставим Y* = оптимальное решение Y* = (4,3) в систему ограничений (11) – (13). Получим, что ограничение (13) выполняется как строгое неравенство: ‐6∙4 – 5∙3 = ‐ 39 < ‐ 30. Следовательно, согласно следствию 1 соответствующая переменная прямой задачи x3 = 0. Далее, т.к. y1 = 4 > 0, y2 = 3 > 0, из следствия 2 следует, ограничения прямой задачи есть равенства: x1 ‐ 6 x3 = 1, x2 ‐ 5x3 = 2, Прибавляя к этой системе уравнение x3 = 0, получим x1 = 1, x2 = 2. Ответ: min F = F(1,2,0) = 10. Страница 52 из 184 Пример. Имеется два вида сырья S1 и S2 в количествах 80ед. и 140ед. Из этого сырья можно изготовить три вида продукции Р1 и Р2 и Р3. Затраты на единицу изготовления каждого вида продукции даны в таблице. Рi Р1 Р2 Р3 S1 4 2 5 S2 2 6 6 сырье Цены реализации готовых изделий соответственно 8, 14 и 10д.е. Найти оптимальный план производства продукции. Решение. Составим математическую модель задачи. Ограничения по сырью дают следующие неравенства: 4x1 + 2x2 + 5x3 ≤ 80, (14) 2x1 + 6x2 + 5x3 ≤ 140. (15) Функция цели определяет прибыль: F = 8x1 + 14x2 + 10x3 → max (16) Неравенства (14) и (15) вместе с целевой функцией (16) определяет задачу линейного программирования с тремя переменными. Для ее решения составим двойственную задачу аналогично предыдущему примеру: g = 80y1 + 140y2 → min, Страница 53 из 184 4y1 + 2 y2 ≥ 8, (17) 2y1 + 6 y2 ≥ 14, (18) 5y1 + 5y2 ≥ 10, (19) y1 ≥ 0, y2 ≥ 0, Решим эту задачу графическим методом. На рис.3.2 область допустимых решений задачи S изображены (выделенное штрихом неограниченное множество), нормаль n = (80, 140) = (8, 14) = (4, 7). Двигаем линию уровня целевой функции сверху в сторону, противоположной нормали n до тех пор, пока она не заденет последнюю точку допустимого множества S. Это точка А, которая находится на пересечении прямых (17) и (18) . y2 S n А 2 7 (1) (3) Рис. 3.2 Страница 54 из 184 y1 (2) Координаты этой точки находятся из системы уравнений, определяющих прямые (1) и (2): 4y1 + 2 y2 = 8, 2y1 + 6 y2 = 14. Решая эту систему, находим оптимальное решение: y1 = 1, y2 = 2. Отсюда min g = g (1, 2) = 80∙1 + 140∙2 = 360. Далее, т.к. y1 = 1 > 0, y2 = 2 > 0, из следствия 2 следует, что ограничения (14) и (15) прямой задачи есть равенства: 4x1 + 2x2 + 5x3 = 80, (20) 2x1 + 6x2 + 5x3 =140. (21) Подставляя решение y1 = 1 и y2 = 2 в систему ограничений (17) – (19) двойственной задачи, получим, что ограничение (19) выполняется как строгое неравенство: 5∙1 + 5∙ 2 > 10. Следовательно, согласно следствию 1 соответствующая переменная прямой задачи x3 = 0. Добавляя это условие к системе (20) и (21), получаем оптимальное решение исходной задачи (оптимальный план производства): X* = (10, 20, 0). Подставляя полученное решение в целевую функцию исходной задачи, получаем, что при оптимальном плане производства максимальная прибыль составит Страница 55 из 184 max F = F (10, 20, 0) = 8∙10 + 14∙20 + 10∙0 = 360 д.е. Ответ: X* = (10, 20, 0), max F = 360 д.е. Упражнения. Решить задачи линейного программирования с помощью двойственной задачи: 1. F = ‐3x1 + 5x2 + x3 + x4 → max, 2. F = 9x1 + 13x2 + x3 + 2x4 → min, 3x1 + 8x2 + x3 + x4 ≤ 50 2x1 + 3x2 + x3 ≥ 50 5x1 ‐ 4x2 ‐ x3 + x4 ≥ 14, 3x1 + 2x2 ‐ x3 + x4 ≥ 4, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 Страница 56 из 184 4. СИМПЛЕКС­МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс‐метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое‐либо допустимое начальное (опорное) решение, т.е. какая‐либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции. Рассмотрим применение симплекс метода на конкретном примере. Пример. Фирма производит три вида продукции. Для изготовления каждого из них необходимо затратить рабочее и машинное время, сырьё. Затраты указанных ресурсов на единицу продукции приведены в следующей таблицы: Вид продукции Рабочее время ч/ед. продукции Машинное время ч/ед. продукции Страница 57 из 184 Сырьё ед.сырья/ед.прод-ии 1 2 2 4 2 4 3 2 3 2 3 1 В расчёте на один рабочий день имеются следующие ресурсы: рабочее время – 24 часа, машинное время – 12 часов, сырьё – 18 единиц. Единица первого вида продукции стоит 16 д.е., второго – 20д.е., третьего – 18д.е. Сколько продукции каждого вида нужно изготовить, чтобы максимизировать доход от произведённой за день продукции. Решение. Заметим, что по смыслу задачи ответ должен быть в целых числах. При разборе этой задачи мы пренебрежем этим требованием. (По поводу целочисленного решения см. главу о применении Excel). Если обозначить через Х1, Х2, Х3 число единиц первого, второго и третьего видов продукции, то математическая модель задачи примет вид: f = 16Х1 + 20Х2 + 18Х3 → max 2Х1 + 4Х2 + 2Х 3 ≤ 24, 2Х1 + 3Х2 + 3Х3 ≤ 12, (1) 4Х1+ 2Х2 + Х3 ≤ 18, Х1 ≥ 0; Х2 ≥ 0; Х3 ≥ 0. Шаг 1. Сведём задачу (1) к канонической форме. Для этого введём неотрицательные вспомогательные переменные Х4, Х5, Х6 ограничения задачи (1) в виде равенств: 2Х1 + 4Х2 + 2Х 3 + Х4 = 24, 2Х1 + 3Х2 + 3Х3 + Х5 =12, 4Х1+ 2Х2 + Х3 + Х6 =18, Хi ≥ 0; i = 1,…,6. Страница 58 из 184 (2) и получаем Разделим переменные на базисные и свободные. Число ограничений m = 3, число переменных n = 6, следовательно, должно быть n - m = 3 свободных и m = 3 базисных переменных. В качестве свободных переменных выбираем Х1, Х2, Х3, тогда Х4, Х5, Х6 – базисные, т.к. матрица при них единичная. Выражаем из ограничений (2) базисные переменные через свободные: Х4 = 24 - 2Х1 - 4Х2 - 2Х3 Х5 = 12 – 2Х1- 3Х2 - 3Х3, (3) Х6 = 18 - 4 Х1 - 2Х2 - Х3. Шаг 2. Определяем начальное допустимое базисное решение Х0, т.е. некоторую вершину допустимого множества. Полагая Х1 = Х2 = Х3 = 0, получим Х0 = (0; 0; 0; 24; 12; 18), Значение целевой функции на начальном допустимом решении: f (Х0) = 16 ·0 + 20· 0 + 18 · 0 = 0. Ясно, что целевая функция f (Х) значения. при Х0 не достигает максимального Шаг 3. Улучшим это решение, введя в базис одну из свободных переменных Х1, Х2 или Х3. Коэффициенты при базисных переменных Х4, Х5, Х6 в целевой функции нулевые, т.е. Св = (0; 0; 0), где Св - вектор коэффициентов при базисных переменных в целевой функции. Вычисляем симплекс-разности для свободных переменных: ∆j = Cj – ∑CB·aij. Если симплекс – разность ∆j положительна, то переходим к следующему пункту, если неположительна, то алгоритм закончен. Эти разности равны в Страница 59 из 184 данном случае коэффициентам функции цели. Например, - 0·4 = 16 и т.д. ∆1 = 16 - 0·2 - 0·2 - Вычисляя, получим, ∆1 = 16, ∆2 = 20, ∆3 = 18. Самая большая симплекс-разность у второй переменной Х2, поэтому вводим её в базис. Далее определим переменную, которую выводим из Для этого все свободные переменные, кроме Х2, принимаем базиса. равными нулю, тогда из равенств (2) получим: Х4 = 24 –4Х2, Х5 = 12 –3Х2 , (4) Х6 = 18 –2Х2. Так как Х4, Х5 и Х6 - неотрицательные, то из (4) видно, первой нулевой переменной будет переменная Х5, при этом Х2 = 4. Переменную Х5 удаляем из базиса. В результате на первой итерации получаем базисное решение: Х1= (0; 4; 0; 8; 0; 10), в котором базисными переменными являются Х2, Х4, Х6, свободными – Х1, Х3, Х5. Доход от применения этого решения равен 80 д.е. т.к. значение целевой функции на плане Х1 равно: f = 16·0 + 4·20 + 0·18 = 80. Остались неиспользованными 8 часов рабочего времени и 10 единиц сырья. Шаг 4. Для выполнения следующего шага (итерации) преобразуем уравнения так, чтобы коэффициенты при базисных переменных Х2, Х4, Х6 составили единичную матрицу. С этой целью разделим второе уравнение на коэффициент при Х2, а затем вычтем из первого и третьего уравнения второе, умноженное на коэффициенты при Х2 сначала первого, а затем третьего Страница 60 из 184 уравнений. Расставляя уравнения в порядке возрастания номеров базисных переменных, получим в результате: 0,67Х1 + Х2 + Х3 + 0·Х4 + 0,33Х5 + 0·Х6 = 4, - 0,67Х1 + 0·Х2 - 2·Х3 + Х4 - 1,33Х5 + 0·Х6 = 8, (5) 2,67Х1 + 0·Х2 – Х3 + 0·Х4 - 0,67Х5 + Х6 = 10. Аналогично шагу 3, находим симплекс-разности для свободных переменных Х1, Х3, Х5: ∆1 = С1 − Св · аi1 = 16 – (20; 0; 0) · (0,67; - 0,67; 2,67) = 16 – 20 · 0,67 = 2,67; ∆3 = С3 − Св · аi3 = 18 – (20; 0; 0) · (1; - 2; -1) = 18 – 20 = - 2; ∆5 = С5 − Св · аi5 = 0 – (20; 0; 0) · (0,33; - 1,33; - 0,67) = 0 – 6,67 = - 6,67. ∆1 = 2,67 > 0, следовательно, можно улучшить решение за счёт увеличения Х1. Эту переменную вводим в базис. В равенствах (5), полагая Х3 = Х5 = 0, получим: Х2 = 4 – 2/3Х1, Х4 = 8 + 2/3Х1, (6) Х6= 10 – 8/3Х1. Из равенств (6) видно, что первой нулевой переменной будет Х6. Следовательно, из базиса удаляем Х6. В результате на второй итерации получаем базисное решение: Х² = (3,75; 1,5; 0; 10,5; 0; 0), Значение целевой функции f (Х²) = 90. Базисные переменные – Х1 , Х2, Х4, свободные – Х3, Х5, Х5. Доход по сравнению с предыдущей итерацией увеличился на 10 д.е. и достиг 90д.е. Страница 61 из 184 Машинное время и сырьё использованы полностью, 10,5 часов рабочего времени осталось неиспользованным. Шаг 5. Проверим решение на оптимальность. Для этого преобразуем ограничения (5) так, чтобы коэффициенты при базисных переменных Х1, Х2 и Х4 составили единичную матрицу (см. шаг 4). В результате получим: Х1 + 0·Х2 - 0,375Х3+ 0·Х4 - 0,25Х5 + 0,375Х6 = 3,75, 0·Х1 + Х2 + 1,25Х3 + 0,5Х4 + 0,5Х5 - 0,25Х6 = 1,5, 0·Х1 + 0·Х2 - 2,25Х3 + Х4 - 1,4Х5 + 0,25Х6 = 10,5. Находим симплекс-разности для свободных переменных Х3, Х5, Х6: ∆3 = С3 - Св · аi3 = 18 – (16; 20; 0) · (-0,375; 1,25; -2,25) = 18 – 19 = -1 < 0; ∆5 = С5 - Св · аi5 = 0 – (16; 20; 0) · (-0,25; 0,5; 1,4) = 0 – 6 = -6 < 0; ∆6 = С6 - Св · аi6 = 0 – (16; 20; 0) · (0,375; -0,25; 0,25) = 0 – 1 = −1 < 0. Итак, все симплекс-разности оказались отрицательными, поэтому базисное решение Х* = Х² = (3,75; 1,5; 0) оптимально. Целевая функция f (Х*) = 90. Отсюда следует, что третий вид продукции производить нецелесообразно. Упражнения. Решить симплекс – методом: 1) f = -Х1 + 4Х2 + 6Х3 → max, 8Х1 + 7Х2 + Х 3 ≤ 16, Х1 + 2Х2 + Х3 ≤ 12, 2Х1+ Х2 + 4Х3 ≤ 12, Страница 62 из 184 Х1 ≥ 0; Х2 ≥ 0; Х3 ≥ 0. 2) f = 4Х1 + 3Х2 - 3Х3 → max Х1 + 3Х2 + Х 3 ≤ 15, 2Х1 - Х2 + 4Х3 ≤ 16, Х2 + Х3 ≤ 4, Х1 ≥ 0; Х2 ≥ 0; Х3 ≥ 0. Страница 63 из 184 5. ТРАНСПОРТНАЯ ЗАДАЧА 5.1. Постановка задачи Пусть имеется m поставщиков однородного продукта, которые могут поставить a1, a2, …, am единиц этого продукта, и имеется n потребителей с потребностями b1, b2, …, bn единиц. Известна стоимость cij перевозки единицы продукта от i– го поставщика к j ‐ му потребителю. Требуется спланировать перевозки этого продукта от поставщиков к потребителям так, чтобы удовлетворить потребности всех потребителей, а суммарные затраты на перевозки при этом были бы наименьшими. Следовательно, цель транспортной задачи состоит в минимизации стоимости перевозок известного количества товаров со складов потребителю. Рассмотрим закрытую (сбалансированную) транспортную задачу: общий объем товаров, готовых к отправлению равен объему товаров, который готовы принять потребители. Рассмотрим на примере простейшую транспортную задачу и метод ее решения, позволяющий свести эту задачу к задаче линейного программирования и решить ее графическим методом. Пример. Компания имеет 2 товарных склада и 3‐х оптовых покупателей. Общий объем запасов на складах составляет 300 000 единиц продукции и совпадает с общим объемом заказов покупателей. Данные о загруженности каждого из складов (тыс. ед.), потребности каждого покупателя (тыс. ед.) и стоимость перевозок (тыс. руб.) приведены в таблице. Страница 64 из 184 Стоимость перевозок Склады В1 В2 В3 А1 8 (х11) 5 (х12) 6 (х13) 120 А2 4 (х21) 9 (х22) 7 (х23) 180 Запрос 70 90 300 140 Наличие Прежде всего заметим, что данная задача закрытая: 70 + 140 + 90 = 120 + 180. Схематически задачу можно изобразить следующим образом: В А1 Ai В2 xij Bj А2 В3 Здесь Ai ‐ склады (поставщики), Bj – потребители, xij‐ количество товара, поставляемого со склада Ai потребителю Bj. 5.2. Экономико‐математическая модель Стоимость перевозок выразим в виде целевой функции, которую по условию задачи нужно минимизировать: Страница 65 из 184 F=8х11+5х12+6х13+4х21+9х22+7х23→ min. (1) Уравнение баланса каждой строки таблицы поставок: ⎧x 11 + x 12 + x 13 = 120 ⎨ ⎩x 21 + x 22 + x 23 = 180 (2) Удовлетворение спроса потребителя (уравнения по столбцам): ⎧x 11 + x 21 = 70 ⎪x + x = 140 ⎪ 12 22 ⎨ ⎪x 13 + x 23 = 90 ⎪x ij ≥ 0 ⎩ (3) (1), (2), (3)‐ это экономико‐математическая модель транспортной задачи. Решение. Выпишем полностью полученную математическую модель задач. F = 8x 11 + 5x 12 + 6x 13 + 4x 21 + 9x 22 + 7x 23 → min ⎧x 11 + x 12 + x 13 = 120 ⎨ ⎩x 21 + x 22 + x 23 = 180 ⎧x 11 + x 12 = 70 ⎪x + x = 140 ⎪ 12 22 ⎨ ⎪x 13 + x 23 = 90 ⎪x ij ≥ 0 ⎩ Для решения введем новые переменные x 11 = u; x 12 = v . Из системы ограничений получим: x 13 = 120 − u − v; x 21 = 70 − u; x 23 = 90 − x 13 = 90 − (120 − u − v) = u + v − 30; x 22 = 140 − v Страница 66 из 184 (4) Далее выразим целевую функцию через новые переменные u и v и xij ≥ 0. Получаем задачу линейного программирования с учтем, что все двумя переменными, которая допускает графический метод решения. F = 5u – 3v + 2050 → min ⎧120 − u − v ≥ 0 ⎪70 − u ≥ 0 ⎪⎪ ⎨140 − v ≥ 0 ⎪u + v − 30 ≥ 0 ⎪ ⎪⎩u, v ≥ 0 (5) Решая задачу (5) графическим методом, получим следующий результат: min F = F(0, 120) = 1690. Из равенств (4) находим xij: х11 = 0, х12 = 120, х13 = 0, х21 = 70, х22 = 20, х23 = 90. Задача решена. 5.3. Общая постановка транспортной задачи Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы m n F = ∑ ∑ c ij ⋅ x ij → min i =1 j =1 при ограничениях Страница 67 из 184 j = 1, n, ⎫ ⎪ i =1 ⎪ n ⎪ x ij = a i , i = 1, m, ⎬ , ∑ j =1 ⎪ x ij ≥ 0, i = 1, m, j = 1, n ,⎪ ⎪⎭ m ∑x ij = bj, где cij ‐ стоимость перевозки единицы продукции из пункта i в пункт j; xij – планируемая величина перевозок из пункта i в пункт j, bj ‐ потребности в продукте в пункте j; ai ‐ запасы в пункте i. Предполагается, что рассматривается модель закрытого типа: n m j =1 i =1 ∑bj = ∑ai Если имеем модель открытого типа: n ∑b j =1 m j ≠ ∑ai , i =1 то ее всегда можно привести к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления. Именно, n m j=1 i =1 если ∑b j < ∑a i , то введем b n +1 = ∑ a i − ∑ b j , n +1 тогда ∑ j =1 Если bj = m n i =1 j =1 m ∑ a , причем i ci,n+1 = 0. i =1 n m n m j =1 i =1 j =1 i =1 ∑ b j > ∑ a i , то введем a m +1 = ∑ b j − ∑ a i , Страница 68 из 184 тогда n m +1 j =1 i =1 ∑bj = ∑ai и ci,m+1 = 0. Транспортная задача представляет собой задачу линейного про‐ граммирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточ‐ нения оценок. В этом случае основная трудность связана с числом переменных задачи (m×n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относится, например, метод потенциалов. Алгоритм метода потенциалов начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо‐ западного угла или метод минимального элемента. 5.4. Метод северо‐западного угла Этот метод позволяет найти некоторый допустимый план перевозок. Составим таблицу некоторой транспортной задачи. В правом верхнем углу ячеек проставлена стоимость перевозки единицы продукции, ai поставщики, bj ‐ потребители. b1 bj b2 200 200 b3 b4 300 Страница 69 из 184 400 ‐ ai 4 3 2 1 a1 2 3 5 6 a2 9 12 a3 200 200 300 200 6 100 7 500 200 300 a4 100 100 В данном случае, имеем задачу открытого типа: ∑ ai = 1000 < ∑bj = 1100, т.е. суммарные запросы потребителей больше суммарных запасов поставщиков. В этом случае необходимо ввести фиктивного, четвертого поставщика с запасами a4 = 1100 – 1000 = 100 и нулевыми стоимостями перевозки груза (последняя строка таблицы). При построении плана должны учитывать, что сумма перевозок в столбце должна оказаться равной потребностям в данном пункте, а сумма перевозок в строке запасу в пункте, соответствующем данной строке. Заполнение начинается с левой верхней («северо‐западной») клетки таблицы. Величина перевозки устанавливается равной минимальной из Страница 70 из 184 величин: величины остатка запасов в пункте i или величины еще неудовлетворенного спроса в пункте j. Если ресурс в данной строке исчерпан, то ставим в этой строке прочерк и переходим к перевозке в следующей строке текущего столбца (на одну строку вниз). Если потребности для данного пункта (столбца) удовлетворены, то ставим в этом столбце прочерк и переходим к следующей перевозке текущей строки в следующем столбце. В ячейку (4, 3) проставляем объем перевозок , равным нулю, чтобы исключить третьего потребителя. В результате получаем, что затраты на перевозку по построенному плану равны: F = 200 ∙ 4 + 200 ∙ 3 + 100 ∙ 5 + 200 ∙ 9 + 300 ∙12 + 0∙ 0 + 0 ∙100 = 7300. Необходимо иметь ввиду, что метод северо‐западного угла не учитывает стоимость перевозок, поэтому найденный план может быть далек от оптимального. 5.5. Метод минимального элемента Чтобы получить улучшенный исходный опорный план перевозок, используют метод минимального элемента или минимальной стоимости. Суть этого метода состоит в том, чтобы в процессе построения плана всегда заполнять клетку с минимальным значением стоимости перевозки единицы продукции. Применим метод минимального элемента к предыдущей задаче: b1 b2 b3 b4 Страница 71 из 184 bj 200 200 300 400 ai 4 3 2 1 a1 200 200 2 3 5 6 a2 7 9 12 a3 300 200 100 6 500 100 300 100 a4 100 100 Имеем задачу открытого типа: ∑ ai = 1000 < ∑bj = 1100. Вводим фиктивного, четвертого поставщика с запасами a4 = 1100 – 1000 = 100 и нулевыми стоимостями перевозки груза (последняя строка таблицы). Алгоритм метода состоит из ряда однотипных шагов, на каждом из которых заполняется одна клетка таблицы, соответствующая минимальной стоимости перевозки (min (cij)). Поставщик исключается из рассмотрения, если его запасы заканчиваются, потребитель исключается из рассмотрения, если его запросы выполнены. Страница 72 из 184 В нашем случае min (cij) = c14 = 1. Записываем в эту клетку максимальную перевозку х14 = 200, и исключаем первого поставщика из рассмотрения (ставим в первой строке таблицы прочерк). В оставшейся матрице (cij) min (cij) = c21 = 2. Записываем в клетку (2,1) перевозку х14 = 200 и исключаем 1 – го потребителя (прочерк в 1‐ом столбце). Далее, аналогично, то есть min (cij) = с22 =3. Записываем перевозку х22= 100. Исключаем второго поставщика (прочерк во второй строке таблицы). Следующая минимальная стоимость, т.е. min cij = с32= 7. Записываем перевозку х32 = 100. Далее в клетке с33 записываем перевозку х33 = 300 и в клетку с34 записываем перевозку х34 = 100. И, наконец, запасы фиктивного поставщика записываем в с44. Проверяем правильность допустимого решения: число занятых клеток таблицы должно быть равно N = m + n – 1 = 4 + 4 – 1 = 7. Следовательно, полученное решение имеет 7 базисных переменных. Значение целевой функции на этом допустимом решении (стоимость перевозки): F(x) = 1∙200 + 2∙200 + 3∙100 + 7∙100 + 9∙300 + 12∙100 + 0∙100 = 5300. Однако утверждать, что это допустимое решение оптимально, нельзя. Для проверки оптимальности допустимого решения применим метод потенциалов. 5.6 Метод потенциалов Страница 73 из 184 Метод позволяет находить оптимальный план перевозок транспортной таблицы. В основе лежит следующая Теорема 1. Для того, чтобы допустимый план X = (xij) транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система m+n чисел u1, u2,…,um; v1, v2,…,vn для которой выполняются условия: vj ‐ ui ≤ cij , i = 1, … m, j = 1,…n, vj ‐ ui ≤ cij , для xij > 0. (6) (7) ui и vj называются потенциалами соответствующих пунктов отправления и пунктов назначения. Условия (6) и (7) называются условиями потенциальности. Допустимый план X будем называть потенциальным, если для него существует система ui и vj, удовлетворяющая (6), (7). Следовательно, всякий потенциальный план является оптимальным. Алгоритм метода потенциалов. 1. Вычисляем начальный допустимый план (например методом минимального элемента). 2. Определяем систему потенциалов, соответствующих допустимому решению. Для этого решаем систему уравнений ui + vj = cij для xij > 0. Страница 74 из 184 Эта система имеет бесконечное множество решений, поэтому для нахождения частного решения одному из потенциалов придают значение нуль (например u1 =0 ). 3. Проверяем условия оптимальности для свободных клеток таблицы с помощью формул ∆ ij = ui + vj = cij (∆ij = 0 для занятых клеток). Если ∆ ij ≤ 0, то решение оптимально. 4. Если существуют клетки с ∆ ij > 0, то среди них следует найти клетку с максимальным значением ∆ ij и построить из нее цикл. 5. Строим цикл, включающий в состав данную клетку и часть занятых клеток. В клетках цикла расставляют поочередно знаки «+» и «‐», начиная с «+» в клетке ∆ lk. (Цикл на рис.7.1 соответствует рассматриваемой задаче). Осуществляют сдвиг (перераспределение груза) по циклу на величину α = min ( x ij ) . Клетка со знаком «‐», в которой достигается min ( x ij ) , "−" "− " остается пустой. с22‐ α с24+ α с32+ α с34‐ α Рис.7.1 Если min достигается в нескольких точках, то одна из них остается пустой, а в остальных проставляются нули, чтобы число занятых клеток оставалось равным (m + n – 1). Получаем новый допустимый план. Затем переходим к п.2. Страница 75 из 184 Проиллюстрируем метод потенциалов на ранее рассмотренном примере. 1. В качестве начального допустимого плана используем решение, полученное методом минимальной стоимости. Запишем этот допустимый план в табл. 1. Vi i Ui ai / bj 200 200 200 300 400 4 3 2 200 1 2 100 3 5 6 500 6 100 7 300 9 100 12 100 0 100 300 200 Таблица 1. 2. Определяем систему потенциалов, соответствующих допустимому решению. Для этого решаем систему уравнений ⎧u1 + v 4 = 1 ⎪u + v = 2 ⎪ 2 1 ⎪u 2 + v 2 = 3 ⎪ ⎨u 3 + v 2 = 7 ⎪u + v = 9 3 ⎪ 3 ⎪u 3 + v 4 = 12 ⎪ ⎩u 4 + v 4 = 0 Страница 76 из 184 Система состоит из семи уравнений и имеет восемь переменных. Для ее решения полагаем u3 = 0 (т.к. в третьей строке больше заполненных клеток). В результате получим решение: u3 = 0; v2 = 7; v3 = 9; v4 = 12; u1 = ‐11; u1 = ‐12; u2 = ‐4; v1 = 6. Значения потенциалов записываем сверху и сбоку таблицы (таблица 2). 3. Проверяем решение на оптимальность, то есть вычисляем ∆ ij для незаполненных клеток таблицы: ∆ 11 = u1 + v1 – с11= ‐11 + 6 – 4 = ‐9 < 0, ∆ 13 = u1 + v3 – с13 = ‐11 + 9 – 2 = ‐4 < 0, ∆ 24 = 2 > 0, v1 = 6 ∆ 41 = ‐6 < 0, ∆ 43 = ‐3 < 0. v3 = 9 v2 = 7 4 3 v 4 = 12 2 1 u 1 = ‐11 200 2 ‐ 3 5 + 6 u 2 = ‐4 200 100 6 + 7 9 ‐ 12 u3 = 0 300 100 100 0 100 Таблица 2. Страница 77 из 184 0 u 4 = ‐12 4. Допустимое решение не является оптимальным, так как ∆24= 2 > 0. Переходим к новому допустимому решению. 5. Для клетки (2, 4) с ∆ 24 > 0 строим цикл. Ставим в клетку (2, 4) знак «+», присоединяем ее к занятым клеткам. Применяя метод вычеркивания (то есть вычеркиваем те строки и столбцы, которые содержат по одной занятой клетке), находим цикл (2, 4), (3, 4), (3, 2), (2, 2) (таблица 2). Осуществляем сдвиг груза α = min(100,100) = 100 по найденному "− " циклу. Получаем новое допустимое решение (таблица 3). Находим потенциалы для этого решения и вычисляем оценки: ∆ 11 = ‐7 < 0; ∆ 12 = ‐5 < 0; ∆ 13 = ‐2 < 0; ∆ 23 = 0; ∆ 31 = 0; ∆ 34 = ‐2 < 0; ∆ 41 = ‐4 < 0; ∆ 42 = ‐3 < 0; ∆ 43 = ‐1 < 0 v1 = 2 u 1 = ‐5 u2 = 0 200 v2 = 3 v3= 5 v4 = 6 4 3 2 200 1 2 3 5 100 6 u3= 4 6 u 4 = ‐6 200 7 300 9 12 100 Таблица 3. Все оценки ∆ij неположительные, следовательно, оптимальное. F(x) = 1*200 + 2*200 + 6*100 + 7*200 + 9*300 + 0*100 = 5200 Страница 78 из 184 решение Ответ: min F(x) = 5200 0 200 ⎞ ⎛ 0 ⎟ ⎜ При x = ⎜ 200 0 0 100 ⎟ ⎜ 0 200 300 0 ⎟ ⎠ ⎝ Упражнение: Решить ТЗ методом потенциалов: 11 7 8 4 9 2 5 8 1 16 8 3 9 2 5 7 4 6 3 bj ai Страница 79 из 184 6. ЗАДАЧИ ДРОБНО­ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Рассмотрим следующую задачу: Завод выпускает продукцию n‐видов: Р1, Р2,…,Рn, используя k‐видов сырья S1,…,Sk. Требуется составить производственный план так, чтобы обеспечить максимально возможную рентабельность производства. Данные приведены в таблице: Сырье Норма расхода продукция Удельные затраты Прибыль от на одно изделие реализации на одно изделие Р1 a11 a12 K a k1 b1 c1 Р2 a 21 a 22 K a k 2 b2 c2 M M M M Рn a1n a1n K a kn bn cn Запасы сырья a10 a 20 K a k 0 b0‐ условно‐ постоянные затраты Построение математической модели Пусть xi ‐ объемы выпуска продукции вида Pi, i = 1,…,n. Прибыль от реализации продукции: П(х)= ∑ n i =1 i Затраты на производство: C(x) = ∑i =1 b i x i + b 0 ; n Рентабельность: Страница 80 из 184 c xi ; F= ∑c x ∑b x i i + с0 i i + b0 → max; (1) Ограничения на затраты ресурсов: ⎧ a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ a 10 ; ⎪ a x + a x + ... + a x ≤ a ; 22 2 2n n 20 ⎪⎪ 21 1 ⎨.......... .......... .......... .......... ........ ⎪ a x + a x + ... + a x ≤ a ; k2 2 kn n k0 ⎪ k1 1 ⎪⎩ x i ≥ 0 , i = 1,..., n . (2) Целевая функция (1) и ограничения в виде неравенств (2) образуют математическую модель задачи. Задача (1) и (2) сводится к задаче линейного программирования и решается симплекс – методом, либо графически, если число переменных равно двум. Метод решения таких задач проведем на примере. Пример. Найти рентабельность производства, если данные, соответствующие таблице, следующие: ⎛1,8 2,55 ⎞ ⎟⎟ ‐ определяет нормы расхода сырья (тыс. руб), ⎝ 0,2 1,2 ⎠ Матрица А = ⎜⎜ Вектор b= (0,01; 0,04)‐ определяет удельные затраты на производство (млн. руб.), с= (0,012, 0,008)‐ условно‐ переменные затраты (млн. руб.), b0=1‐условно‐ постоянные затраты (млн. руб.), a0 = (20, 45)‐ запасы сырья (тыс. руб.). Страница 81 из 184 Математическая модель задачи в этом случае примет вид: F= 0,012 x1 + 0,008 x 2 → max, 0,01x1 + 0,04 x 2 + 1 (3) При ограничениях ⎧1,8 x1 + 0,2 x 2 ≤ 20; ⎪ ⎨2,55 x1 + 1,2 x 2 ≤ 45; ⎪ x ≥ 0. ⎩ i (4) Решение. Сведем задачу (3) (4) к задаче линейного программирования. Для этого введем новую переменную v= 1 > 0. 0,01x1 + 0,04 x 2 + 1 (5) Умножая неравенства (4) на v и учитывая (5) получим: F = 0,012x1v + 0,008x2 v → max ⎧1,8 x 1 v + 0 , 2 x 2 v ≤ 20 v ; ⎪ 2 ,55 x v + 1, 2 x v ≤ 45 v ; ⎪ 1 2 ⎨ ⎪ 0 , 01 x 1 v + 0 , 04 x 2 v + v = 1; ⎪⎩ x i ≥ 0 ; v > 0 . ⎧ y1 = x1v ⎩ y2 = x2 v Введем новые переменные: ⎨ Тогда задача запишется в виде: z = 0,012y1+0,008y2 → max (6) ⎧1,8 y1 + 0,2 y 2 − 20v ≤ 0; ⎪2,55 y + 1,2 y − 45v ≤ 0; ⎪ 1 2 ⎨ ⎪0,01y1 + 0,04 y 2 + v = 1; ⎪⎩ y i ≥ 0; v > 0. (7) Страница 82 из 184 Задача (6), (7) – задача линейного программирования. Решая ее симплексным методом, получим zmax = 0,14=14% при yопт = (5;10). Возвращаясь к исходным переменным, находим y1 5 = ≅ 9,1; v 0,55 x1 = Fmax = 0,14, x2 = y2 10 = ≅ 18,2 v 0,55 xопт = (9,1; 18,2). Графический метод решения Рассмотрим графический метод решения задач вида c1 x1 + c 2 x 2 → max (min); d1 x1 + d 2 x 2 (8) ⎧a i1 x1 + a i 2 x 2 ≤ bi , i = 1,..., m, ⎨ ⎩ x1 , x 2 ≥ 0. (9) z= Для решения задачи (8), (9) находим допустимое множество решений, определяемое ограничениями (9), затем из выражения (9) найдем x2: x2 = c1 − zd1 x1 , zd 2 − c 2 или x2 = k x1 , где k= c1 − zd1 . zd 2 − c2 x2 = k x1 ‐ прямая, проходящая через начало координат. При изменении значений z прямая x2 = k x1 будет поворачиваться вокруг начала координат. Страница 83 из 184 Установим, как будет вести себя угловой k коэффициент при монотонном возрастании z. Найдем производную от k по z. k z = (d1c2– d2c1) /(zd2 – c2)2. Знаменатель производной всегда положителен, а числитель от z не зависит. Следовательно, производная имеет постоянный знак и при увеличении z угловой коэффициент будет либо возрастать, либо убывать, при этом прямая будет поворачиваться вокруг начала координат. Эта прямая ‐ линия уровня целевой функции. Вращаем эту прямую до тех пор, пока она не заденет последнюю точку в допустимом множестве. Этой точкой является вершина или вершины допустимого множества, в которых функция принимает экстремальное значение. Пример. Предприятие использует три типа оборудования для производства изделий видов А и В. Время обработки одного изделия на каждом из типов оборудования и затраты на его обработку представлены в таблице. Время обработки 1 изделия, ч Тип оборудования А В 1 1 1 2 2 5 3 1 3 4 Затраты на обработку одного изделия, руб. Страница 84 из 184 Первый тип оборудования целесообразно использовать не менее 10 ч, оборудование 2 типа – не более 41 ч, 3 типа – не более 6 ч. Найти такой план производства, при которой себестоимость минимальна. Решение. Пусть x1 и x2 – количество обрабатываемых деталей видов А и В соответственно. Затраты на их обработку составят (3x1 + 4x2 ) руб., следовательно, себестоимость одного изделия равна u(x1 , x2) = 3x 1 + 4 x 2 . x1 + x 2 Математическая модель задачи имеет вид: u(x1 , x2) = 3x 1 + 4 x 2 . → min x1 + x 2 при ограничениях ⎧ x1 + x2 ≥ 10, ⎪2x + 5 x ≤ 41, ⎪ 1 2 ⎨ ⎪x1 ≤ 6, ⎪⎩x1 , x2 ≥ 0. Строим допустимое множество решений. На рисунке это треугольник АВС. Угловой коэффициент k = (3‐ u)/(u ‐ 4). x2 Найдем производную от от k по u: k u = 1 /(u – 4)2 > 0, т.е. прямая будет вращаться против часовой стрелки для А В нахождения С x1 Страница 85 из 184 максимума. Для нахождения минимума вращаем прямую, проходящую через начало координат, по часовой стрелке до тех пор, пока эта прямая не зацепит последнюю точку в допустимом множестве. Очевидно, это точка С. Найдем ее координаты из системы ⎧x 1 + x 2 = 10, → x1 = 6; ⎨ ⎩x 1 = 6 x2 = 4. umin = u(6; 4) = 3,4 руб. Ответ. Минимальная себестоимость, равная 3,4 руб. достигается при выпуске 6 изделий вида А и 4 изделий вида В. Упражнениия. 1. Для производства двух видов изделий А и В используется три типа технологического оборудования. Затраты времени и других ресурсов на производство единицы изделия каждого вида даны в таблице Нормы времени Ограничения по фонду времени Тип оборудования А В верхнее нижнее 1 2 8 26 ‐ 2 1 1 ‐ 4 3 12 3 39 ‐ Затраты на 2 3 ‐ ‐ Страница 86 из 184 производство Определить, сколько изделий каждого вида необходимо изготовить, чтобы себестоимость одного изделия была минимальной. (Задачи 2. и 3. решить симплексным методом). 2 x1 − x 2 → max, 2. F = x1 + 2 x 2 + 1 x −x +3 3. F = 1 2 → max, 2 x1 + 3x 2 + 1 при условиях при условиях ⎧ x1 − 2 x 2 + x3 = 2; ⎪ ⎨2 x1 + x 2 + x 4 = 6; ⎪ x ≥ 0. ⎩ i ⎧2 x1 + 3 x 2 ≤ 9; ⎪ ⎨ x1 + x 2 ≤ 6; ⎪ x ≥ 0. ⎩ i В задачах 4. и 5. найти максимум и минимум графическим методом. 4. F= 5. F = 2 x1 + 3x 2 , x1 + x 2 3x1 − x 2 x1 + x 2 при условиях при условиях Ответы: 1.Fmin = z(3; 1)=9/4); ⎧ x1 + 4 x 2 + ≤ 13; ⎪ x + x ≥ 4; ⎪ 1 2 ⎨ ⎪4 x 1 + x 2 ≤ 12; ⎪⎩ xi ≥ 0. ⎧ x1 + x 2 + ≥ 5; ⎪− x + 3 x ≤ 7; ⎪ 1 2 ⎨ ⎪3x 1 − x 2 ≤ 11; ⎪⎩ xi ≥ 0. 2.Fmax = z(2; 0; 0; 2); 3. Fmax = z(0; 0); 4. Fmax =F (3; 1)=9/4, Fmin =F (1; 3)=11/4;. 5. Fmax =F (4; 1)=11/5. Fmin =F (2; 3)=3/5. Страница 87 из 184 7. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ С ПОМОЩЬЮ EXCEL Задачи линейного программирования, независимо от формы постановки легко и просто решаются в надстройке Поиск решения. Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Ecли в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис⇒ Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения. После выбора команд Сервис ⇒ Поиск решения появится диалоговое окно Поиск решения. В диалоговом окне Поиск решения есть три основных параметра: • Установить целевую ячейку • Изменяя ячейки • Ограничения Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки Страница 88 из 184 возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение. Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек. Третий параметр, который нужно вводить, для Поиска решения – это ограничения. Для решения задачи необходимо: 1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). 2. Ввести исходные данные. 3. Ввести зависимость для целевой функции 4. Ввести зависимости для ограничений. 5. Запустить Поиск решений. 6. Назначить ячейку для целевой функции. 7. Ввести ограничения. 8. Ввести параметры для решения задачи линейного программирования. 9. 7.1. Решение задачи линейного программирования Страница 89 из 184 Рассмотрим решение задачи линейного программирования, на конкретном примере. Задача 1 (Задача о максимизации прибыли). Определить, в каком количестве надо выпускать продукцию четырех типов П1, П2, П3 и П4 с целью максимизации прибыли, если для изготовления этой продукции требуется ресурсы трех видов: трудовые, сырье и финансы. (Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода). Нормы расхода, наличие располагаемого ресурса, а также прибыль, получаемая от реализации каждого типа продукции, приведены в таблице: Экономико‐математическая модель задачи Введем следующие обозначения: хj – количество выпускаемой продукции j – го типа, j = 1,2,3,4; bi – количество располагаемого ресурса I – го вида, I = 1,2,3; aij – норма расхода I – го ресурса для выпуска единицы продукции j – го типа; cj – прибыль от реализации единицы продукции j – го типа. Для выпуска единицы продукции типа П1 требуется 6 единиц сырья, следовательно, для выпуска всей продукции П1 требуется 6х1 единиц сырья, Страница 90 из 184 где х1 ‐ количество выпускаемой продукции типа П1. Для других типов продукции зависимости аналогичны и, например, ограничение по сырью будет иметь вид: 6х1 + 5х2 + 4х3 + 3х4 ≤ 110. В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса. Составляя аналогичным образом ограничения для остальных ресурсов и выписывая выражение для целевой функции, которая выражает прибыль, получаем экономико‐математическую модель задачи: F = 60х1 + 70х2 + 120х3 + 130х4 → max. x1 + х2 + х3 + х4 ≤ 16, 6х1 + 5х2 + 4х3 + 3х4 ≤ 110, (1) 4х1 + 6х2 + 10х3 + 13х4 ≤ 100, xj ≥ 0, j = 1,2,3,4; Решение в EXCEL 1. Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Оптимальные значения вектора X = (х1, х2, х3 , х4) поместим в ячейки В3: Е3, оптимальное значение целевой функции поместим в ячейку F6. Страница 91 из 184 2. Введем исходные данные. Вводим исходные данные задачи, как показано на Рис.1. Оставляем ячейки B3, C3, D3, E3 за переменными х1, х2, х3, х4 соответственно (изменяемые ячейки). Рис.1 3. Вводим зависимости для целевой функции. • В ячейке F6 задаем целевую функцию. Для этого помещаем курсор в ячейку F6, произойдет выделение ячейки. • Помещаем курсор на кнопку Мастер функций, расположенный на панели инструментов. Вводим Enter. На экране диалоговое окно Мастер функций – Шаг 1 из 2. • В окне Категория выберите категорию Математические. • В окне Функции выберите строку СУММПРОИЗВ (Рис.2). Страница 92 из 184 появится • В строку Массив 1 введите B3:E3. • В строку Массив 1 введите B6:E6 (Рис.3). Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку (если перед буквой или номером стоит знак доллара, например $A$2, то ссылка на столбец или строку является абсолютной). Рис. 3. Рис. 2 Выбор функции Страница 93 из 184 Рис. 3 Введены данные для функции СУММПРОИЗВ 4. Вводим зависимости для ограничений. В ячейках F9, F10, F11 задаем, соответственно, левые части нетривиальных ограничений. Для этого вводим с помощью Мастера функций в ячейки F9, F10, F11 вводим функцию СУММПРОИЗВ с соответствующими аргументами (Рис. 4). Отметим, чтобы в этих ячейках были видны формулы, необходимо выбрать меню Сервис, Параметры, и в этом поле выбрать команду отображать формулы. Страница 94 из 184 Рис. 4 Содержимое ячеек F6, F9‐F11 5. Запустить команду Поиск Решения. В строке Меню вызвать Сервис и в развернутом меню выбрать команду Поиск решения (Рис 5). 6. Назначить ячейку для целевой функции. В нашем случае это ячейка F6. В этой ячейке находится значение целевой функции, которое необходимо либо максимизировать, либо минимизировать, либо сделать равным конкретному значению. В строку Установить целевую ячейку вводим адрес $F$6. Для этого щелкнем мышью по ячейке F6. Вокруг F6 появится движущийся пунктирный контур, а в поле окна – соответствующий адрес (Рис 5). Отметим, чему равна целевая функция, в нашем случае ‐ максимальному значению. Далее, поместим курсор в строку Изменяя ячейки и введем адреса $B$3:$E$3 (Рис.6) Страница 95 из 184 Рис. 5 Меню Поиск решения Рис. 6 Ввод адресов исходных переменных Страница 96 из 184 7. Ввести ограничения. Поместите курсор на кнопку Добавить. На экране появится диалоговое окно Добавление ограничения (Рис.7). Рис. 7 Диалоговое окно Добавление ограничений Ссылка на ячейку – определяет ячейку или интервал ячеек, чьи значения необходимо ограничить. Для примера мы взяли левую часть ограничения на трудовые ресурсы, которая находится в ячейке F9. Строка Ограничение определяет условие, налагаемое на содержимое строки Ссылка на ячейку. Вводим в эту строку адрес $H$9 (в этой ячейке находится число 16). Вводим знак ограничения <=. Помещаем курсор на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничений. Страница 97 из 184 Вводим остальные ограничения аналогичным образом. После того, как введены все ограничения, нажмите кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными условиями (Рис. 8). Рис. 8 Введены все условия задачи 8. Ввести параметры для решения задачи линейного программирования. В диалоговом окне Поиск Решения поместить курсор на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения. (Рис. 9). Параметры, используемые по умолчанию, подходят для большинства задач. Страница 98 из 184 В нашем случае необходимо: • установить флажок Линейная модель, что обеспечивает применение симплекс‐метода и Неотрицательные значения. • Поместите курсор на кнопку ОК. На экране появится диалоговое окно Поиск решения. • Поместите курсор на кнопку Выполнить. Запускается процесс решения задачи. Появится диалоговое окно Результаты поиска решения (Рис. 10) и исходная таблица с заполненными ячейками B3:E3 для значений xi и ячейкой F6 с максимальным значением целевой функции (Рис. 11). Рис. 9 Введение параметров Страница 99 из 184 Рис. 10 Решение найдено Диалоговое окно Результаты поиска решения выводит результаты последнего вычисления (итерации). Поясним смысл элементов окна Результаты поиска решения. Сохранить найденное решение – принимает решение, найденное Поиском решения, и подставляет найденные значения в соответствующие ячейки. Восстановить исходные значения – восстанавливает исходные значения в изменяемых ячейках. Страница 100 из 184 Рис. 11 Результаты найденного решения Тип отчета ‐ создает указанный тип отчета. Каждый отчет появляется на отдельном листе рабочей книги. • Результаты – перечисляет изменяемые ячейки и ячейку в окне Установить целевую ячейку вместе с исходным и конечным значением. Также показывает ограничения и информацию о них (Рис.12). • Устойчивость – показывает, насколько чувствительно решение к изменениям коэффициентов в целевой функции или правых частей ограничений. предоставляет Для нелинейных двойственные значения моделей отчет (нормированные градиенты и множители Лагранжа). Для линейных моделей отчет включает нормируемую стоимость, теневые цены и ограничения на изменение правой стороны равенства (Рис. 13). • Пределы – устанавливает верхние и нижние пределы и целевые значения. Нижний предел – это наименьшее значение, которое может находиться в изменяемой ячейке, если фиксировать остальные ячейки и удовлетворить все ограничения. Верхний предел – есть наибольшее значение. Целевое значение есть значение ячейки в окне Установить целевую ячейку, когда значение изменяемой ячейки наименьшего предела (Рис. 14). Страница 101 из 184 достигает наибольшего и Рис. 12 Отчет Результаты Рис. 13 Отчет Устойчивость Страница 102 из 184 Рис. 14 Отчет Пределы Ответ. В оптимальном решении следует выпускать продукцию типа П1 в количестве 10 усл.ед., продукцию типа П3 – в количестве 6 усл.ед. Продукцию остальных типов выпускать не следует. При этом максимальная прибыль составит 1320 ден. ед., а количество использованных ресурсов: трудовых – 16, сырья – 84, финансов – 100. Страница 103 из 184 8. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ С ПОМОЩЬЮ EXCEL Транспортная задача относится к двухиндексным задачам линейного программирования (ЛП), так как в результате ее решения необходимо найти матрицу. Двухиндексные задачи ЛП вводятся и решаются в EXCEL аналогично одноиндексным задачам. Специфика ввода условия двухиндексной задачи ЛП состоит лишь в удобстве матричного задания переменных задачи и коэффициентов целевой функции. Рассмотрим решение конкретной транспортной задачи. Определить оптимальный план поставки товара со складов в каждый магазин для удовлетворения их потребностей, чтобы суммарные транспортные издержки были минимальными. Стоимость перевозки единицы товара со складов в магазины (руб./шт.) данны в таблице: Тарифы, руб./шт 1‐й 2‐й магазин 3‐й магазин Запасы, шт. магазин 1‐й склад 2 9 7 25 2‐й склад 1 5 50 3‐й склад 5 4 100 35 4‐й склад 2 3 6 75 45 90 50 Потребности, шт. Экономико – математическая модель задачи Страница 104 из 184 Переменные: xij ‐ количество товара, поставляемого с i – го склада в j ‐ й магазин. Целевая функция – суммарные транспортные издержки, которые необходимо минимизировать: F(x) = 2x11 + 9x12 + 7x13 + x21 + 5x23 + 5x31 + + 4x32 + 100x33 + 2x41 + 3x42 + 6x43 → min; Ограничения: • по поставщикам x11 + x12 + x13 = 25, x21 + x22 + x23 = 50, x31 + x32 + x33 = 35, x41 + x42 + x43 = 75. • по потребителям x11 + x21 + x31 = 45, x12 + x22 + x32 = 90, x13 + x23 + x33 = 50. Кроме того, должно быть xij ≥ 0, xij ‐ целые для всех i = 1,2,3,4; j = 1,2,3. Страница 105 из 184 1. Указать адреса ячеек, в которые будет помещен результат решения. Изменяемые ячейки С3: Е6. В эти ячейки в результате решения задачи будут записаны оптимальные значения xij. 2. Ввести исходные данные. Вводим исходные данные задачи, как показано на рис. 1. Рис.1 3. Ввести зависимости для ограничений. Вводим ограничения по поставщикам: • Поместим курсор в ячейку F3. • Выберем функцию СУММ. • Выделим необходимые для суммирования ячейки С3:Е3. • Нажмите ОК (Рис. 2) Аналогичные действия выполните для ячеек F4, F5, F6. Вводим ограничения по запросам потребителей: Страница 106 из 184 • Поместим курсор в ячейку С7. • Выберем функцию СУММ. • Выделим необходимые для суммирования ячейки С3:C6. • Нажмите ОК для подтверждения ввода формулы для суммирования. Аналогичные действия выполните для ячеек D7, E7. После ввода функций в соответствующих ячейках отображаются функции, которые изображены в правой части таблицы. Например, в ячейке D7 отобразится функция «=СУММ (D3:D6)» и т.д. Объект математической модели Выражение в EXCEL Переменные задачи С3: Е6 Формула в целевой ячейке F15 =СУММПРОИЗВ(С3:Е6;C12:E15) =СУММ (C3:E3) Ограничения по строкам в =СУММ (C4:E4) ячейках F3, F4, F5, F6 =СУММ (C5:E5) (поставщики) =СУММ (C6:E6) =СУММ (C3:C6) Ограничения по столбцам в =СУММ (D3:D6) ячейках С7, D7, E7 =СУММ (E3:E6) (потребители) Суммарные запасы и потребности в ячейках H8, G9 Страница 107 из 184 =СУММ (H3:H6) =СУММ (C9:E9) Рис. 2 4. Ввести зависимость для целевой функции. Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку товара, зарезервируем ячейку F15 и введем туда формулу для вычислений. • Поместите курсор в ячейку F15 (после решения задачи в данной ячейке будет находится значение целевой функции). • Запустите Мастер функций (значок fx). • В окне Категория выберите Математические. • В окне Функция выберите СУММПРОИЗВ. • Нажмите ОК. Страница 108 из 184 • В окне СУММПРОИЗВ укажите адреса массивов, элементы которых обрабатываются этой функцией . В нашей задаче целевая функция представляет собой произведение затрат на доставку товара (ячейки С3:Е6) и объемов поставок для каждого потребителя (ячейки С12:Е15). • В поле Массив 1 укажите адреса С3:Е6. • В поле Массив 2 укажите адреса С12:Е15. • Нажмите ОК (рис. 3). Рис. 3 В поле ячейки F15 появится некоторое числовое значение 0 (Рис. 4). Страница 109 из 184 Рис. 4 После вставки функций «Сумм» и «Суммпроизв» 5. Запустить команду Поиск решений. 6. Назначить ячейку для целевой функции. • Поместить курсор в окно Установить целевую ячейку. • Введите адрес ячейки $F$15 (Рис. 5). • Отметьте, чему равна целевая функция – Минимальному значению. Страница 110 из 184 Рис.5 Запуск команды Поиск решения 7. Ввести ограничения. • Поместите курсор на кнопку Добавить. Появится диалоговое окно Добавление ограничения. • Введите условие целочисленности. Для этого следует выбрать опцию целое в списке Ограничение (Рис. 6). Третья и четвертая записи в группе Ограничения представляет собой ограничения по уровню спроса и по уровню запасов соответственно. • После ввода всех ограничений нажмите ОК. Страница 111 из 184 Рис.6 Введение ограничения целочисленности переменных Рис.7 Введены все ограничения задачи 8. Ввести параметры для решения. Страница 112 из 184 • Установите флажки Неотрицательное значение и Линейная модель. • Нажмите ОК. Опять появится окно Поиск решения. • Нажмите Выполнить. В результате появится окно Результаты поиска решения (Рис. 9). Рис. 8 Введение параметров Страница 113 из 184 Рис. 9 Решение найдено Ответ. Распределение товара по магазинам приведено на рис. 9 в ячейках С3 : Е6. Общие затраты на перевозку продукции составят 545 руб. Спрос магазинов на продукцию удовлетворен полностью. Страница 114 из 184 9. УСЛОВНЫЙ ЭКСТРЕМУМ. МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА Пусть y(x) = f(x1, x2,…, xn) и φi(x) = 0, i = 1,…,k ‐ – дважды непрерывно дифференцируемые функции. Требуется найти экстремум функции y(x) при условии, что аргументы xj, j = 1,…,n удовлетворяют системе ограничений φi(x) = 0, i = 1,…,k . (1) Условия (1) называют условиями связи. Итак, рассмотрим задачу на условный экстремум f (x) → extr, x = (x1, x2,…, xn) (2) φi(x) = 0, i = 1,…,k . Теорема 1. Пусть функции f и φi(x) имеют непрерывные частные производные, причем векторы grad φi (x) – линейно независимы (условие регулярности). Тогда если точка М0 (x10, x20, … , xn0) для функции f (x) является точкой возможного экстремума, то эта точка является точкой возможного экстремума и для функции Лагранжа L (x, λ) = f (x) + ∑ λi φi(x). Из теоремы 1 вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Теорема 2. (Необходимое условие экстремума задачи (2)). x* есть точка локального экстремума задачи (2), Пусть причем векторы grad φi(x) линейно независимы (условие регулярности). Тогда выполнены следующие условия: Страница 115 из 184 ∂L(x*, λ*)/∂ xj = 0, j = 1,…,n; φi(x*) = 0, i = 1,…,k . Рассмотрим пример исследования на экстремум функции двух переменных z = f(x, y) при условии, что переменные связаны одним уравнением ϕ(x, y) = 0. Замечание. В случае одного уравнения связи условие регулярности означает, что grad φ(x) ≠ 0. Пример. Найти условный экстремум функции z = x2 + y2 при условии, что x + y ‐ 1 = 0. Методы решения. 1) Метод подстановки. Из условия связи переменных выразим у через х и подставим в функцию z. В результате получим функцию одной переменной z = 2x2 ‐ 2x + 1. Из необходимого условия экстремума для функции одной переменной получим z 'x = 4x – 2 = 0; x = 1/2. Так как z′′ = 4 > 0, то из достаточного условия экстремума следует, что точка х = 1/2 является точкой минимума. zmin= (1/2)2 + (1/2)2 = 1/2 2) Метод множителей Лагранжа. В более сложных случаях не всегда удается разрешить уравнение связи относительно одной из переменных. Следовательно, описанный выше подход применим не ко всем задачам. Более универсальным методом решения задач отыскания условного экстремума является метод Лагранжа. Он основан на применении теоремы 1 и теоремы 2. Страница 116 из 184 Очевидно, что условие теоремы 2 для нашей задачи выполнено. Действительно, grad φi(x) = (1; 1) ≠ 0. Строим функцию Лагранжа L(x, y, λ) = f(x, y) + λ(ϕ(x, y)). Составляем и решаем систему уравнений: L 'x = 0, L 'y = 0, L 'λ = 0. Получаем стационарные точки, т.е. точки возможного экстремума. Далее с помощью геометрических соображений решаем вопрос о максимуме или минимуме в полученной стационарной точке. В нашем случае f(x, y) = x2 + y2, ϕ(x, y) = 1 ‐ x ‐ y. Функция Лагранжа имеет вид L(x, y, λ) = x2 + y2 + λ( 1 ‐ x ‐ y). Из системы уравнений ⎧Lx′ = 2x − λ = 0, ⎪ ⎨L′y = 2 y − λ = 0, ⎪ ′ ⎩Lλ = 1 - x - y = 0. находим точки возможного экстремума. В данном случае это одна точка (1/2, 1/2), λ = 1. Принимая z во внимание характер целевой функции и уравнения связи (параболоид вращения и пересекающая его вертикальная плоскость) Рис.1, (1/2,1/2) x+y‐1=0 x Рис.1 y заключаем, что точка минимума. Страница 117 из 184 (1/2, 1/2) является точкой Ответ. Min z = z(1/2; 1/2) = 1/2. В дальнейшем переменные будем обозначать через x1, x2,…,xn. Теорема 3. (необходимые условия экстремума второго порядка). Пусть x* ‐ регулярная точка локального минимума (максимума) задачи (2) и точка (x*, λ*) – решение системы ∂L(x*, λ*)/∂ xj = 0, j = 1,…,n; φi(x*) = 0, i = 1,…,k . (k < n ) (3) x* = (x*1, x*2,…,x*n). Тогда: 1) второй дифференциал функции Лагранжа вычисленный в точке (x*, λ*) неотрицателен (неположителен): d2L(x*, λ*) ≥ 0 (d2L(x*, λ*) ≤ 0) 2) dφi(x*) = ∑(∂φi(x*)/∂xi) dxi = 0, i = 1,…,k . Теорема 4. (достаточные условия экстремума). Пусть имеется точка (x*, λ*), удовлетворяющая системе (3). Если в этой точке d2L(x*, λ*) > 0 (d2L(x*, λ*) < 0) для всех ненулевых dx i ∈ Rn таких, что dφi(x*) = ∑(∂φi(x*)/∂xi) dxi = 0, i = 1,…,k . То точка является точкой локального минимума (максимума) в задаче (2). Страница 118 из 184 Алгоритм решения задачи на условный экстремум 1. Составить функцию Лагранжа: L (x, λ1,…,λk) = f (x) + λ1φ1(x) +…+ λkφk(x). 2. Записать необходимые условия экстремума первого порядка: ∂L(x*, λ*)/∂ xj = 0, j = 1,…,n; φi(x*) = 0, i = 1,…,k . 3. Решая систему из п.2, находим точки возможного экстремума. 4. Проверить достаточные условия. Для этого: а) записать выражение для второго дифференциала функции Лагранжа; б) записать систему dφi(x*) = ∑(∂φi(x*)/∂xi) dxi = 0, i = 1,…,k . в) из системы б) выразить любые k дифференциалов dxi через остальные (n ‐ k) и подставить в d2L(x*, λ*); г) если d2L(x*, λ*) > 0 при ненулевых dxi, то в точке x* ‐ условный локальный минимум. если d2L(x*, λ*) < 0 при ненулевых dx, то в точке x* ‐ условный локальный максимум. Если достаточные условия экстремума не выполняются, следует проверить выполнение необходимых условий второго порядка (Теорема 3.). Если они выполняются, то требуется дополнительное исследование, а если не выполняются, то в точке x* нет условного экстремума. 5. Вычислить значения функции в точках условного экстремума. Пример 1. Найти условный экстремум в задаче: Страница 119 из 184 f (x) = x21 + x22, φ(x) = x1 + x2 ‐ 2= 0. Решение. Проверим условие регулярности: grad φ(x) = (1,1) ≠ 0, т.е. условие регулярности выполняется. Далее действуем согласно алгоритму. 1. Составим функцию Лагранжа: L(x, λ) = x21 + x22+ λ( x1 + x2 ‐ 2). 2. Выпишем необходимые условия экстремума первого порядка ∂L(x, λ)/∂ x1 = 2x1 + λ = 0 → x1 = ‐ λ/2 , ∂L(x, λ)/∂ x2 = 2x2 + λ = 0 → x2 = ‐ λ/2. φ(x) = x1 + x2 ‐ 2= 0. 3. Решение системы: x*1 = x*2 = 1, λ = ‐ 2 – точка возможного экстремума. 4. Проверим достаточные условия экстремума: а) d2L(x*, λ*) = 2 dx21 + 2 dx22; б) dφ(x*) = dx1 + dx2; в) выразим дифференциал dx1 через dx2: dx1 = ‐ dx2; и подставим в d2L; г) так как d2L(x*, λ*) = 4dx22 > 0 при dx2 ≠ 0, то в точке x* = (1,1) – локальный минимум. Пример 2. Найти условный экстремум в задаче: f (x) = x1 + x2, φ(x) = x21 + x22 ‐ 2 = 0. Страница 120 из 184 Решение. Проверим условие регулярности: grad φ(x) = (2x1,2x2) ≠ 0, (т.к. хотя бы одна из переменных отлична от нуля) т.е. условие регулярности выполняется. Далее действуем согласно алгоритму. 1. Составим функцию Лагранжа: L(x, λ) = x1 + x2 + λ( x21 + x22 ‐ 2). 2. Выпишем необходимые условия экстремума первого порядка ∂L(x, λ)/∂ x1 = 1 + 2x1 λ = 0 → x1 = ‐ 1/(2λ) , ∂L(x, λ)/∂ x2 = 1 + 2x2 λ = 0 → x2 = ‐ 1/(2λ). φ(x) = x21 + x22 ‐ 2 = 0. 3. Решением системы являются две точки возможного экстремума: А: x*1 = x*2 = 1, λ = ‐1/2 ; В: x*1 = x*2 = ‐ 1, λ = 1/2. 4. Проверим достаточные условия экстремума: а) d2L(x*, λ*) = 2λ dx21 + 2λ dx22; б) dφ(x*) = 2x1dx1 +2x2dx2 = 0; в г) выразим дифференциал dx1 через dx2 в точке А: dx1 = ‐ dx2 и подставим в d2L, получим d2L(А) = ‐ dx21 ‐ dx22 = ‐ 2dx22 < 0 при dx2 ≠ 0. Поэтому в точке x* = (1,1) – локальный максимум. Исследуем точку В. Получаем dφ(В) = ‐2dx1 ‐ 2dx2 = 0, откуда dx1 = ‐ dx2. Подставим это соотношение в d2L, получим Страница 121 из 184 d2L(В) = dx21 + dx22 = 2dx22 > 0 при dx2 ≠ 0. Поэтому в точке x* = (‐1,‐1) – локальный минимум. 5. Значения функции в точках экстремума: f(A) = 2, f(B) = ‐ 2. Выше были решены примеры, когда выполнялось условие регулярности. Однако это не всегда так. Рассмотрим задачу, когда свойство регулярности не выполнено. Пример 3. Найти условный экстремум в задаче: f (x) = x21 + x22 , φ(x) = (x1 – 1) 2 + x22 ‐ 4 = 0. Решение. Проверим условие регулярности: grad φ(x) = (2(x1 – 1), 2x2). При x*= (1,0) условие регулярности не выполняется, т.е. grad φ(x) = (2(x1 – 1), 2x2) = 0 в этой точке. В этом случае используем алгоритм с обобщенной функцией Лагранжа. 1. Составим обобщенную функцию Лагранжа: L(x, λ0, λ1) = λ0 (x21 + x22)+ λ1((x1 – 1) 2 + x22 ‐ 4 ) = 0. 2. Выпишем необходимые условия экстремума первого порядка ∂L(x, λ0, λ1)/∂ x1 = 2λ0 x1 + 2λ1 (x1 ‐ 1) = 0, ∂L(x, λ0, λ1)/∂ x2 = 2λ0x2 + 2λ1x2 = 0, φ(x) = (x1 – 1) 2 + x22 ‐ 4 = 0. Страница 122 из 184 3. Решим систему для двух случаев. 1) λ0 = 0. Тогда 2λ0 x1 + 2λ1 (x1 ‐ 1) = 0, 2λ0x2 + 2λ1x2 = 0, (x1 – 1) 2 + x22 ‐ 4 = 0. Так как в этом случае λ1 ≠ 0, то из первых двух уравнений: x1 = 1, x2 = 0. Однако при этом ограничение не выполняется, т.е. система несовместна. 2) λ0 ≠ 0. Поделим систему из пункта 2 на λ0 с заменой λ1/λ0 на λ1: L(x, λ0, λ1)/∂ x1 = 2 x1 + 2λ1 (x1 ‐ 1) = 0, ∂L(x, λ0, λ1)/∂ x2 = 2x2 + 2λ1x2 = 0, φ(x) = (x1 – 1) 2 + x22 ‐ 4 = 0. Рассмотрим второе уравнение: 1) Если x2 = 0, то из третьего уравнения следует x1 = 3, x1 = ‐ 1, а из первого λ1 = ‐3/2, λ1 = ‐1/2 соответственно. 2) Если λ1 = ‐1, то первое уравнение имеет вид 2 = 0, т.е. система несовместна. Таким образом найдены две точки возможного экстремума: А: x*1 = 3, x*2 = 0, λ*1 = ‐3/2 ; В: x*1 = ‐1, x*2 = 0, λ*1 = ‐1/2. 4. Проверим достаточные условия экстремума: а) d2L(x*, λ*1) = 2(1 + λ*1)dx21 + 2(1 + λ*1) dx22; Страница 123 из 184 б) dφ(x*) = 2 (x*1 – 1)dx1 +2x*2dx2 = 0; в, г) выразим дифференциал dx1 через dx2 в точке А(3;0): dx1 = 0 и d2L(А) = ‐ dx21 ‐ dx22 = ‐ dx22 < 0 при dx2 ≠ 0. Поэтому в точке А – условный максимум. Исследуем точку В(‐1;0): dφ(В) = ‐2dx1 ‐ 2dx2 = 0, откуда dx1 = 0. Подставим это соотношение в d2L, получим d2L(В) = dx21 + dx22 = dx22 > 0 при dx2 ≠ 0. Поэтому в точке В – локальный минимум. 5. Значения функции в точках экстремума: f(A) = 9, f(B) = 1. Графическое решение задачи изображено на рис.2. На этом рисунке – концентрические окружности – линии уровня целевой функции. Множество допустимых решений – окружность (x1 – 1) 2 + x22 ‐ 4 = 0. Линии уровня касаются с этой окружностью в точках А(3, 0) и В(‐1,0). В точке А(3, 0) функция имеет максимум, т.к. при приближении к этой точке функция возрастает, а затем убывает (показано стрелками). Аналогичные рассуждения показывают, что в точке В(‐1,0) – минимум. Страница 124 из 184 φ(x)=(x1‐1)2+x22 ‐4=0 x2 f(x)=9 f(x)=4 f(x)=1 А В x1 В Рис.2 Мы рассмотрели задачи нелинейного программирования с ограничениями типа равенств. Рассмотрим задачу с ограничениями типа неравенств: найти min f(x) (4) при ограничениях φk (x) ≤ 0, k = 1,…,m . (5) Если ограничения (5) даны в форме φi (x) ≥ 0, то их нужно записать в виде − φk (x) ≤ 0. Справедлива следующая теорема. Теорема 5. ( Куна – Таккера). Если условия (5) задачи (4), (5) регулярны (т.е. найдется хотя бы одна точка x, для которой φi (x) < 0 для всех i = 1,..,k) и все функции задачи дифференцируемы, то для того, чтобы точка x* с неотрицательными координатами являлась оптимальным решением задачи, Страница 125 из 184 достаточно, чтобы существовал неотрицательный вектор λ*, удовлетворяющий следующим условиям: ∂L(x*, λ*)/∂ xi = ∂f/∂ xi + ∑(∂φk(x*)/∂xi) λk* ≥ 0, ∑ x*i(∂L(x*, λ*)/∂xi) = 0, i = 1,…,n, (6) ∂L(x*, λ*)/∂λk = φk (x*) ≤ 0, ∑λk* φk(x*) = 0, k = 1,…,m . Если задача (4), (5) является задачей выпуклого программирования, то эти условия являются необходимыми и достаточными условиями оптимальности такой задачи. Пример. Какую долю составляют ценные бумаги первого, второго и третьего видов в портфеле с наименьшим стандартным отклонением доходности, если доходности ценных бумаг разного вида не коррелируют, а дисперсии их доходностей равны 1/2, 1/4 и 1/8 соответственно. Решение. Пусть s2i – дисперсия доходности ценных бумаг вида i, (i = 1,2,3), xi – доля бумаг в портфеле. Тогда дисперсия доходности портфеля с учетом некоррелированности ценных бумаг равна s2 = s21 x12 + s22 x22 + s23 x32. (7) Очевидно, что x1 + x2+ x3 = 1, xi ≥ 0. (8) Получили задачу (7), (8) на условный минимум. Функция Лагранжа этой задачи имеет вид Страница 126 из 184 L = s21 x12 + s22 x22 + s23 x32 + λ(x1 + x2+ x3 ‐1). Необходимые условия экстремума дают систему уравнений: ∂L/ ∂x1= 2 s21 x1 + λ = 0; ∂L/ ∂x2 = 2 s22 x2 + λ = 0; ∂L/ ∂x3 = 2 s23 x3 + λ = 0; ∂L/ ∂λ = x1 + x2+ x3 – 1 =0. Решая эту систему, получим стационарную точку −2 ⎛ ⎞ s 31 s1−2 s −22 ⎜ ⎟ ; ; X* = ⎜ −2 −2 −2 −2 −2 −2 −2 −2 −2 ⎟ . + + + + + + s s s s s s s s s 2 3 1 2 3 1 2 3 ⎠ ⎝ 1 (9) Вследствие выпуклости (выпуклости вниз) функции L, точка X* является точкой глобального минимума, а значит и для функции s2 тоже. Очевидно, что X* > 0. Подставляя численные значения в формулу (3), получаем ответ: X* = (4/7; 2/7; 1/7). Упражнение: получите формулу (9) из решения системы уравнений. Однако в общем случае применение теоремы 5 не имеет практического значения, т.к. отыскание решений системы нелинейных уравнений и неравенств (6) весьма затруднительно. При решении таких задач применяются компьютерные программы (в частности EXCEL). Ниже мы на примерах рассмотрим решение некоторых конкретных задач нелинейного программирования c помощью EXCEL . Страница 127 из 184 Задачи Найти экстремумы функции: 1.f(x) = 2x1+ 4 x2, при условии x12 + 4 x22 = 8. (fmin = f(1,1) = 2) 2. f(x) = x12 + x22, при условии x12 + 2x22 – 8 = 0. (fmin1 = f(0,‐2) = 4; fmin2 = f(0,2) = 4. 3. f(x) = x1 ∙ x2, при условии x12 + x22 = 2. (fmax = f(1,1) = f(‐1,‐1) =1) 4. f(x) = x1 + x2, при условии x12 + x22 ‐ 8= 0. (fmin = f(‐2,‐2); fmax = f(2,2)) (Указание: рассмотреть линии уровня целевой функции и допустимое множество) 5. Рекламное объявление в газете стоит 10 д.е. Минута телерекламы ‐ 50 д.е. Недельный рекламный бюджет фирмы ‐ 550 д.е. Прибыль фирмы за неделю с учетом затрат на рекламу: П(х1, х2)= 20х1+ 80х2‐2х12‐4х2, где х1‐ число объявлений в газете, х2‐ рекламное время в минутах (на телевидении). Определить х1 и х2, обеспечивающие максимум функции прибыли за неделю. 6. Фирма производит два вида затрат С(x,y) = 10x + xy + 10y. товаров в количествах x и y. Функция Функции спроса на товары p1 = 50 – x + y, p2 = 30 + 2x – y соответственно. Квота фирмы на общий объём товаров равна 15. Найти максимальную прибыль. 7. Решить графически задачу 4. 8. Решить графическим методом следующую задачу: Страница 128 из 184 Найти максимум и минимум задачи: min f(x) = [ (х1‐ 4) 2 + (х2 ‐ 2) 2] При ограничениях 2x1 + 3x2 ≥ 6, 3x1 – 2x2 ≤ 18, ‐x1 + 2x2 ≤ 4, x1 ≥ 0, x2 ≥ 0. Ответ: min f(x) = f(4, 2) = 0; max f(x) = f(11; 7,5) = 79,25. Страница 129 из 184 10. ПРОИЗВОДСТВЕННЫЕ ФУНКЦИИ Производственная функция производства (ПФ) выражает зависимость результата от затрат ресурсов. При описании какой – либо производственной подсистемы экономики (например, предприятия) с помощью ПФ эта подсистема рассматривается как “черный ящик”, на вход которого поступают ресурсы x1,…,хn, а на выходе получается результат в виде годового объёма продукции Y, т.е. Y = f(x1,…,хn). X1,…,Xn Y ПФ По экономическому смыслу все переменные этой функции неотрицательны, следовательно, областью определения многоресурсной или многофакторной ПФ является множество n‐мерных векторов х, все координаты x1,…,хn которых неотрицательные числа. Для отдельного предприятия (фирмы), выпускающего однородный продукт, ПФ Y = f(x1,…,хn) может связывать объем выпуска с затратами рабочего времени по различным видам трудовой деятельности, различных видов сырья, комплектующих изделий, энергии, основного капитала. ПФ такого типа характеризуют действующую технологию предприятия (фирмы). При построении ПФ в качестве результата рассматривают валовой выпуск Y (либо валовой внутренний продукт, либо национальный доход). Если рассматривается предприятие, то в качестве результата берут выпуск продукции. Страница 130 из 184 В качестве ресурсов рассматривают производственные фонды (капитал) К и настоящий (живой) труд L – количество единиц затрачиваемого в течение года живого труда, измеряемые обычно в стоимостном выражении. Таким образом, строят двухфакторную ПФ Y=f(K,L). Пример. Для моделирования отдельного региона или страны в целом (то есть для решения задач на макроэкономическом, а также на микроэкономическом уровне) часто используется ПФ вида у = А⋅Kα Lβ, где А, α, β – параметры ПФ (положительные постоянные). Часто α, и β таковы, что α, + β ≤ 1, тогда ПФ такого вида называется ПФ Кобба‐Дугласа (ПФКД) по имени двух американских экономистов, предложивших ее использовать в 1929 г. Пример. Линейная ПФ имеет вид: y = a0 + a1x1 + a2x2 (двухфакторная) и y = a0 + a1x1 +…+anxn (многофакторная). Линейная ПФ принадлежит к классу так называемых аддитивных ПФ. Переход от мультипликативной ПФ к аддитивной осуществляется с помощью операции логарифмирования. Для двухфакторной мультипликативной ПФ a a y = a o x 1 1 x 22 этот переход имеет вид: lny = lna0 + a1lnx1 + a2lnx2. Относительно логарифмов получили линейную ПФ. Если сумма показателей степени в ПФ Кобба‐Дугласа равна единице, то ее можно записать в несколько другой форме: Страница 131 из 184 a 1 Y a o K a1 La2 a o K a1 a o K a1 ⎛K⎞ , т.е. a = = 1− a2 = = ⎟ ⎜ o L L L La1 ⎝L⎠ a 1 Y ⎛K⎞ = ao ⎜ ⎟ . L ⎝L⎠ Дроби Y/L = y и K/L = k называются соответственно средней производительностью труда и средней фондоворуженностью труда. Дробь Y ‐ средняя фондоотдача. K При построении ПФ научно‐технический прогресс (НТП) может быть учтен pt с помощью введения множителя НТП e , где параметр р (р>0) характеризует темп прироста выпуска под влиянием НТП: pt y(t) = e f(x1(t), x2 (t)) (t = 0,1,…,Т). Пример. ПФКД с учетом НТП: y( t ) = a o e pt x1 ( t ) α1 x 2 ( t ) α 2 . Расчет численных значений параметров такой функции проводится с помощью регрессионного анализа. Рассмотрим определенности основные свойства ограничимся производственных производственными функций. функциями Для двух переменных y = F(K,L). Прежде всего отметим, что такая производственная функция определена при K ≥ 0, L ≥ 0. ПФ y = F(K,L) удовлетворяет следующему ряду свойств: 1) при отсутствии хотя бы одного из ресурсов нет выпуска, т.е. F(0,0) = F(0,L) = F(K,0) = 0; 2) ∂F / ∂K ≥ 0 , ∂F / ∂L ≥ 0 , т.е. с ростом ресурсов выпуск растет; Страница 132 из 184 3) ∂ 2 F / ∂K 2 ≤ 0 , ∂ 2 F / ∂L2 ≤ 0 , т.е. с увеличением ресурсов скорость роста выпуска убывает (закон убывающей эффективности); 4) ПФ является однородной функцией степени p, т.е. F(αK, αL) = αp F(K,L); при р>1 имеем рост эффективности производства от роста масштаба производства; при р<1 имеем падение эффективности производства от роста масштаба производства; при р=1 имеем постоянную эффективность производства при росте его масштаба. Закон убывающей эффективности может быть сформулирован в виде следующей теоремы. Теорема. Матрица Гессе H производственной функции y = F(K,L) неположительно определена. Напомним, что матрица Гессе для функции y = F(K,L) имеет вид ⎛ ∂ 2F ∂ 2F ⎞ ⎜ 2 ⎟ ∂K∂L ⎟ ⎜ ∂K . ⎜ ∂ 2F ∂ 2F ⎟ ⎜ ⎟ ⎝ ∂L∂K ∂L2 ⎠ Ранее мы определили линии уровня ПФ, которые называют изоквантами. Возрастание одного фактора и уменьшение другого могут происходить таким образом, что общий объем производства остается на прежнем уровне. Изокванты как раз и определяют все возможные комбинации факторов производства, необходимых заданного уровня продукции. K Страница 133 из 184 для достижения Покажем, что для производственных функций вида α у = А⋅K Lβ, в системе координат L0K изоквантами являются степенные гиперболы. Действительно, по определению изокванты это множество (K, L) такое, что на этом множестве α А⋅K Lβ = С, где С – число. Тогда α ‐β ⋅K = (С/ А) L или K = (С/ А) L ‐β/α . Вычислим первую производную функции K = К(L): K′ = − β/α (С/ А) L Очевидно, что для всех K = К(L) L > 0, ‐β/α ‐1 . K′ < 0, следовательно, функция монотонно убывает в рассматриваемом промежутке. −β/α − 2 Далее, так как вторая производная K′L= С1L > 0, где С1 > 0 – число, то графиком этой функции являются монотонно убывающие кривые, выпуклые вниз. Следовательно, изоквантами функции семейство степенных гипербол (Рис. 4). Поскольку на изокванте F(K,L) = С, где С – число, то Страница 134 из 184 α у = А⋅K Lβ, являются dF = В этом соотношении ∂F ∂F dK + dL = 0. ∂K ∂L ∂F > 0, ∂K (1) ∂F >0, поэтому dK и dL имеют разные ∂L знаки. Если, например, dL < 0, что означает сокращение объемов труда, то dK > 0, т.е. выбывший в количестве dL труд замещается фондами в объеме dK. Поэтому естественно следующее определение, вытекающее из равенства (1). Предельной нормой замены труда фондами называется отношение SK = − dK ∂F / ∂L = , dL ∂F / ∂K Соответственно, предельная норма замены фондов трудом SL = − Пример. ПФ фирмы у = 10 dL ∂F / ∂K = . dK ∂F / ∂L х 11/ 3 х22/ 3 , где хi ‐ ресурсы Определить максимальный выпуск, если на ресурсы выделено 100 д. ед., цены на ресурсы 5 и 10 д. ед. Какова предельная норма замены одного занятого фондами в оптимальной точке? Решение. В главе () мы нашли, что оптимальные затраты ресурсов одинаково равны K* = L* = 20/3 ед. Следовательно, норма замены труда фондами в оптимальной точке (α = 1/3) SK = − 1 − α K∗ dK ∂F / ∂L = = ⋅ ∗ = 2 ⋅1 = 2 , L dL ∂F / ∂K α Страница 135 из 184 т.е., один работающий может быть заменен двумя единицами фондов. Далее рассмотрим пример, который решим сначала аналитически, а потом с помощью Excel. Пример. Производственная функция, связывающая выпуск готовой продукции данного предприятия с численностью рабочих x1 и производственными фондами x2, есть Y = 2 x1x2 . Общие затраты предприятия на заработную плату и покупку оборудования даются соотношением x1 + x2 = 120. Определить затраты предприятия, максимизирующие выпуск продукции. Решение. В математическом плане это задача на условный экстремум. Целевая функция этой задачи – это производственная функция Y = 2 x1 x2 . С помощью функции Лагранжа составляем математическую модель задачи: L(x, λ) = x1 x2 + λ (x1 + x2 ‐ 120), φ(x) = x1 + x2 – 120. Выпишем необходимые условия экстремума первого порядка: Страница 136 из 184 ∂L(x, λ)/∂ x1 = 2x2 + λ = 0, ∂L(x, λ)/∂ x2 = 2x1 + λ = 0, ∂L(x, λ)/∂λ = x1 + x2 – 120 = 0. Решая эту систему относительно x1, x2 и λ, получим следующий результат: x1 = x2 = 60, λ = ‐ 120. Итак, если есть экстремум, то он находится в точке (x1, x2) = (60; 60). Проверим достаточные условия экстремума. Для этого выпишем второй дифференциал для функции Лагранжа: d2L(x, λ) = L′′x1x1dx12 + 2L′′x1x2dx1 dx2 + L′′x2x2dx22. Учитывая, что L′′x1x1 = 0, L′′x2x2 = 0, L′′x1x2dx = 2, получаем: d2L(x, λ) = 4dx1 dx2 Далее, из условия связи x1 + x2 = 120 получим соотношение: dx1 = ‐ dx2 Подставим в d2L, получим d2L(А) = 4dx21dx22 = ‐ 4dx22 < 0 при dx2 ≠ 0. Поэтому в точке x = (60; 60) – максимум. Рассмотрим решение этой задачи с помощью Excel. 1. Экономико ‐ математическая модель задачи Переменные: x1 ‐ затраты предприятия на покупку оборудования; x2 ‐ расходы на заработанную плату. Целевая функция: y = 2 x1x2 . Страница 137 из 184 Ограничения: x1 + x2 = 120, x1, x2 ≥ 0. 2. Вводим условия задачи в Excel (более подробно см. часть I) (Рис. 1 ‐ 4). Рис. 1 Введение зависимостей для целевой функции и ограничений Страница 138 из 184 Рис.2 Ввод ограничений Рис.3 Ввод параметров для решения задачи (Обратите внимание на отсутствие флажка у параметра «Линейная модель») Страница 139 из 184 Рис.4 Все условия введены 3. Помещаем указатель мыши на кнопку «Выполнить». Появится диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками А1:В1 для значений xi и ячейка С2 с максимальным значением целевой функции (Рис.5) Рис.5 Решение получено Страница 140 из 184 Отчет по устойчивости содержит значения переменных и множитель Лагранжа (Рис. 6). Рис. 6 Отчет по устойчивости Страница 141 из 184 x2 120 (60; 60) 60 2x1x2 = 7200 x1 +x2 = 120 60 x1 120 Рис. 7 Оптимальная комбинация ресурсов На Рис.7 прямая x1 + x2 = 120 – изокоста, т.е. линия постоянных издержек, кривая 2 x1x2 = 7200 – изокванта, касающаяся изокосты в точке, соответствующей оптимальному набору факторов (60; 60). Упражнение. Производственная функция, связывающая выпуск готовой продукции данного предприятия с численностью рабочих x1 и производственными фондами x2, есть Y= 4 x11/ 2 x12/ 2. Общие затраты предприятия на заработную плату и покупку оборудования даются соотношением Страница 142 из 184 x1 + x2 = 100. Определить затраты предприятия, максимизирующие выпуск продукции. Задачу решить аналитически и с помощью Excel. Моделирование производственной функции по статистическим данным c помощью Excel Имеются следующие данные по некоторой отрасли, описывающие зависимость объема промышленного выпуска Y от факторов «труд» L и «капитал» K: Таблица 1 Год (условно) Объем выпуска Основной капитал Y, млн. руб. К, млрд. руб. Численность производственного персонала, L 1 90,8 0,2 5637 2 108,6 0,3 5630 3 220 400,0 1200,5 4568 4 296 000,0 1200,7 4587 5 475 900,0 1195,8 5473 6 325,2 2,4 4110 7 367,4 2,5 3900 Страница 143 из 184 8 475,8 2,4 3957 9 723,8 1.7 4100 Построить двухфакторную производственную функцию Кобба – Дугласа, соответствующую данным таблицы. Решение. Производственная функция Кобба – Дугласа имеет вид (): α β Y = А⋅K L , (1) Параметр А называют коэффициентом нейтрального технического прогресса. В модели (1) нужно определить А, α и β. Для этого применим методы регрессионного анализа, а именно, метод наименьших квадратов. Так как модель (1) нелинейна, то необходимо ее линеаризовать. Прологарифмируем обе части формулы (1), получим: lnY = lnA + α lnK + β lnL (2) Модель (2) линейна относительно логарифмов переменных. Следовательно, для расчета по методу наименьших квадратов, данные таблицы 1 нужно прологарифмировать. В результате получим таблицу (2). Таблица 2 lnY 4,51 4,69 12,30 12,60 13,07 5,78 5,91 6,17 6,58 lnK ‐1,61 ‐1,2 7,06 7,06 7,06 0,88 0,88 0,92 0,47 Страница 144 из 184 lnL 8,64 8,64 8,43 8,43 8,61 8,32 8,27 8,28 8,32 Решение модели (2) с помощью Excel. 1. Вводим исходные данные из таблицы 2 (Рис.8): Рис. 8 Ввод исходных данных 2. В главном меню последовательно выберите Сервиз/Анализ данных /Регрессия. В результате появится окно Анализ данных и в нем будет выделена инструмент анализа Регрессия. (Рис. 9) 3. Щелкните по кнопке ОК. Заполните окно ввода данных и параметров вывода как указано на Рис. 10. Страница 145 из 184 Рис. 9 Выбор инструмента анализа «Регрессия» Страница 146 из 184 Рис. 10 Ввод параметров («константа – 0» означает отсутствие свободного члена) Страница 147 из 184 Рис. 11 Результаты моделирования (модель без свободного члена) Уравнение регрессии будет иметь вид (коэффициент А полагаем равным единице): lnY = 0,982 lnK + 0,665 lnL. (3) Переходя к исходным переменным (потенцируя уравнение (3)), получим следующую производственную функцию: 0,982 0,665 Y= K L . При оценке качества полученной модели отметим, что все основные характеристики указывают на хорошее качество модели (Рис. 11). Так, например, коэффициент множественной детерминации равен 0,999, следовательно, практически 99,9% вариации зависимых переменных учтено в модели и обусловлено влиянием включенных факторов. Фактические Страница 148 из 184 значения – критерия (1739,33) и ‐ статистик (22,86 и 31,37) подтверждают хорошее качество модели. Упражнение. Имеются следующие данные за 10 лет о потреблении мяса птицы (y), среднедушевом доходе (x1) и стоимости 1 фунта птицы (x2), указанные в таблице 3: Таблица 3 t (номер года) Y X1 X2 1 30,8 459,7 39,5 2 31,2 492,9 37,3 3 33,3 528,6 38,1 4 35,6 560,3 39,3 5 36,4 624,6 37,8 6 36,7 666,4 38,4 7 38,4 717,8 40,1 8 40,4 768,2 38,6 9 40,3 843,3 39,8 10 41,8 911,6 39,7 Построить по данным таблицы функцию спроса и потребления вида: Y = А⋅(X1) α β (X2) . Страница 149 из 184 11. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ 11.1. Определения необходимых понятий В реальных экономических задачах наилучшее решение ищется таким образом, чтобы это решение удовлетворяло нескольким критериям. При этом часто эти критерии в той или иной степени противоречат друг другу. Например, максимальная доходность финансовой операции и ее минимальный риск. Другой пример: максимальная прибыль, максимальная эффективность вложенных средств и максимальный объем производства. Математически такая задача содержит область допустимых решений и несколько целевых функций. Рассмотрим для примера задачу оптимизации портфеля ценных бумаг. Пусть E(x)‐ эффективность портфеля (доходность), r(x) ‐ риск портфеля, где x = (x1,… ,xn) ‐ доли ценных бумаг в портфеле. Тогда задача оптимизации портфеля ценных бумаг выглядит следующим образом: E(x) → max r (x) → min (1) x∈S S ‐ допустимое множество решений задачи; Максимизация и минимизация целевых функций сводятся друг к другу умножением на (– 1), поэтому общий вид задачи многокритериальной оптимизации можно записать в виде: fi(x) → max, i = 1,2,…,k, (2) x ∈ S, x = (x1,… ,xn). В задаче (2), если ее рассматривать с математической точки зрения (не экономической), решения может и не быть, поскольку цели, выражаемые Страница 150 из 184 различными критериями, часто являются противоположными (см, например, задачу (1) ) Одним из основных понятий при решении таких задач является понятие оптимальности по Парето или эффективными решениями. Определение. Решение оптимально по Парето, если значения любого из критериев можно улучшить лишь за счёт ухудшения остальных критериев. Оптимальность по Парето отражает идею экономического равновесия: если состояние не является эффективным, то будет торговля, которая приводит к эффективному состоянию. Математически оптимальность по Парето можно сформулировать следующим образом. Определение. Допустимое решение x* ∈ S задачи (2) называется эффективным или оптимальным по Парето, если не существует x ∈ S, такого, что для него не выполняется хотя бы одно из условий: 1) для всякого i = 1,2,…,k fi (x*) ≥ fi (x); 2) существует j такое, что fj (x*) > fj (x) Приведем определение слабо эффективного решения, или решения, оптимального по Слейтеру. Определение. Допустимое решение x* ∈ S задачи (2) называется слабо эффективным или оптимальным по Слейтеру, если для всякого x ∈ S существует число i такое, что fi (x*) ≥ fi (x); Рассмотрим понятие оптимальности по Парето и по Слейтеру на примере задачи многокритериальной оптимизации. Z1 = 4x1+ 10x2 → max, Z2 = x1 + x2 → max, Z3 = x2 → max, Страница 151 из 184 (3) x1 + 2x2 ≤ 40, x2 ≤ 15, x1, x2 ≥ 0. Множество допустимых решений S этой задачи изображено на рис.1. Это четырехугольник ОАВС. Все точки множества S, за исключением точек ломаной АВС не являются оптимальными ни по Парето, ни по Слейтеру, т.к. существуют допустимые точки, лежащие выше их. Оптимальными по Парето являются точки отрезка ВС, а оптимальными по Слейтеру – точки ломаной АВС. x2 20 В А S С о 40 x1 Рис.1 11.2. Методы сведения многокритериальных задач к решению однокритериальных Излагаемые ниже методы решения многокритериальных задач справедливы для соизмеримых критериев, т.е. критериев, представленных в количественных шкалах и независимых по предпочтению. Рассмотрим на конкретных примерах три метода нахождения решений. Страница 152 из 184 1) Метод свертки критериев; 2) Метод главного критерия (один из критериев ‐ главный. По остальным задаются пороговые значения и эти остальные критерии становятся ограничениями); 3) метод последовательных уступок. 11.2.1 Метод свертки критериев Метод перехода от нескольких критериев f1, …, fk задаваемому новой функцией φ = k ∑ i =1 αifi, к одному, где αi ≥ 0 – весовые коэффициенты, определяющие относительную важность каждого критерия. Чем больше αi, тем больший вклад вносит оценка по i‐му критерию в целевую функцию φ. Пример. Если в качестве fi выступают объемы выпуска продукции разного вида, и их нужно максимизировать, то в качестве αi могут выступать цены продуктов, а свертка будет означать переход от натуральных к одному стоимостному показателю. Решение по методу обобщенного критерия основывается на следующей теореме. Теорема. Если оценка x* = (x*1,… ,x*n) доставляет максимум функции φ= k ∑ i =1 αifi, где все αi > 0, то оценка x* является Парето – оптимальной. Обратное утверждение не всегда справедливо. Пример: Решить двухкритериальную задачу, считая, что критерии равноправны: z1 = x1+3x2 → max, z2 = 3x1 + x2 →max, Страница 153 из 184 x1 + 2x2 ≤ 8, (4) x1 + x2 ≤ 4, x1, x2 ≥ 0 Решение. Если x1 и x2 – объёмы выпуска продукции, то α1 и α2 ‐ цены реализации продукции. Свернем два критерия в один: z = α1 x1+ α1 x2 → max. Так как критерии равноправны, то, полагая, α1 = α2 = 0,5, получаем целевую функцию (свертку) z = 0,5z1+ 0,5 z2 = 0,5( x1+3x2 ) + 0,5 (3x1 + x2 ) = 2x1+ 2x2 . Таким образом задача (4) свелась к обычной однокритериальной задаче: z = 2x1+ 2x2 → max, x1 + 2x2 ≤ 8, x1 + x2 ≤ 4, x1, x2 ≥0, решая которую, например, графическим методом, получим: max z = z(0; 4) = 8. Упражнение. Проследите, как меняется оптимальный выпуск в зависимости от цен α1 и α2 : а) α1=1, α2=2 ; б) α1 = 2, α2 =2; в) α1 = 2, α2 =1. 11.2.2 Метод главного критерия Пусть дана задача многокритериальной оптимизации fi(x) → max, i = 1,2,…,k, x ∈ S, x = (x1,… ,xn). Страница 154 из 184 Метод главного критерия состоит в том, что исходная многокритериальная задача сводится к задаче выбора по одному критерию, который называется главным, а остальные критерии рассматриваются как ограничения. Выбор главного критерия остается за лицом, принимающим решение (ЛПР). Пример. Решить методом главного критерия задачу. Оптимальное решение найти по первому критерию при уровне притязаний по второму в 1/7 от его максимума. z1= 4x1+5x2 → max, z2= 2x1+3x2 → max, x1+2x2 ≤ 4, x1+x2 ≤ 3, x1, x2 ≥0, Решение. Ищем оптимальное решение для второй целевой функции: z2= 2x1+3x2 → max, x1+2x2 ≤ 4, x1+x2 ≤ 3, x1, x2 ≥ 0. Страница 155 из 184 x2 3 А 2 n S о 3 4 x1 Рис.2 Решая графическим методом (Рис.2), получим max z2 = z(2; 1) = 7. Далее вычисляем 1/7 max z2 = 1/7 ∙7 = 1. Добавляем в ограничения неравенство 2x1+3x2 ≥ 1 и решаем задачу: z1= 4x1+5x2 → max, x1+2x2 ≤ 4, x1+x2 ≤ 3, 2x1+3x2 ≥ 1, x1, x2 ≥ 0. В результате получим окончательное решение max z1 = z(2; 1) = 13. 11.2.3. Метод последовательных уступок Применяется тогда, когда критерии могут быть упорядочены по их значимости. Выбор значимости каждого критерия остается за лицом, принимающим решение (ЛПР). Метод последовательных уступок на практике дает решения, близкие к оптимальным. «Уступки» дают возможность учесть дополнительные Страница 156 из 184 ограничения по другим, вспомогательным критериям. Однако заметим, что данный метод не всегда выявляет единственную эффективную альтернативу задачи на максимум и требует повторения процедуры с новой величиной уступки. Алгоритм метода: 1. Упорядочим критерии по их убывающей значимости и предположим, что экстремальные значения у всех критериях – max; 2. Находим f1max – экстремальное значение первого по значимости критерия, решив задачу: f1(x) → max, xЄS. 3. Решаем задачу линейного программирования для второго по значимости критерия: f2(x) → max, f1(x) ≥ f1max ‐ δ1, x Є S, где δ1 ‐ величина допустимого отклонения критерия f1. Величины δi задаются , исходя из практических соображений и принятой точности. 4. Решаем задачу линейного программирования для третьего по значимости критерия: f3(x) → max, f1(x) ≥ f1max ‐ δ1, f2(x) ≥ f2max – δ2, x Є S. И так далее. 5. Находим экстремальное значение последнего по важности критерия, при условии, что значение каждого из предыдущих критериев отличается на Страница 157 из 184 величину допустимой уступки. Полученное на последнем этапе решение считается оптимальным. Пример. Решить задачу методом последовательных уступок: f1= − x1+3x2→max; f2= 3x1+4x2→max; f3= 2x1 – x2 →max; x1+5x2 ≤ 25; x1+2x2 ≥ 12; 3x1+2x2 ≤ 24; x1, x2 ≥ 0, δ1 = 8/3, δ2 = 1. Решение. Следуя алгоритму, решаем задачу: f1= − x1+3x2→max; x1+5x2 ≤ 25; x1+2x2 ≥ 12; 3x1+2x2 ≤ 24; x1, x2 ≥ 0, δ1 = 8/3. Графическое решение задачи иллюстрирует Рис.1. множество решений задачи изображается треугольником АВС. находится в т. А: fmax 1 = f1 (A) = f1 (10/3;13/3)=29/3. Страница 158 из 184 Допустимое Решение x26 6 (3) 5 A 13/3 B (1) n1 (2) C 10/3 x1 Рис.1 Переходим к решению задачи x1+5x2 ≤ 25; x1+2x2 ≥ 12; f2 = 3x1+4x2 → max, при условиях 3x1+2x2 ≤ 24; и дополнительном ограничении, позволяющем учесть, что по критерию f1 нельзя уступить более, чем на δ1 =8/3. Так как f1max – δ1,= 29/3 – 8/3 = 7, то дополнительное ограничение имеет вид − x1+3x2 ≥ 7. Следовательно, решаем задачу: f2= 3x1+4x2→max; x1+5x2 ≤ 25; x1+2x2 ≥ 12; 3x1+2x2 ≤ 24; − x1+3x2 ≥ 7; x1, x2 ≥ 0, δ2 = 1. Графическое решение задачи иллюстрирует Рис.2. множество решений задачи изображается треугольником АDE. находится в т.D: fmax 2 = f2 (D) = f2 (5;4) = 31. Страница 159 из 184 Допустимое Решение x26 6 (3) 5 A D 13/3 B (1) n2 n1 (4) E (2) C 10/3 x1 Рис. 2 Наконец переходим к решению задачи f3= 2x1+x2 → max; при условиях x1+5x2 ≤ 25; x1+2x2 ≥ 12; 3x1+2x2 ≤ 24; − x1+3x2 ≥ 7; и дополнительном ограничении, позволяющем учесть, что по критерию f2 нельзя уступить более, чем на δ1 =8/3. Так как f2max – δ2,= 31 – 1 = 30, то дополнительное ограничение имеет вид 3x1+4x2 ≥ 30. Следовательно, решаем задачу: f3= 2x1 − x2 → max; x1+5x2 ≤ 25; x1+2x2 ≥ 12; 3x1+2x2 ≤ 24; − x1+3x2 ≥ 7; 3x1+4x2 ≥ 30; x1, x2 ≥ 0. Графическое решение задачи иллюстрирует Рис.3. множество решений задачи изображается треугольником АDF. находится в т.D: fmax 3 = f3 (D) = f3 (5;4) = 6. Страница 160 из 184 Допустимое Решение x26 6 (5) (3) 5 A D 13/3 n1 n2 E F (4) B (1) (2) C 10/3 n3 x1 Рис. 3 Ответ: Решение трехкритериальной задачи достигается в точке D(5;4). Соответствующие значения частных критериев при этом составляют: f1 (5;4) = 7, f2 (5;4) = 31, f3 (5;4) = 6. Задачи. Решить методом последовательных уступок: 1. f1= − x1+2x2→max; 2. f1= x1 → max; f2= 2x1+ x2→max; f2= x1 + x2→ max; f3= – x1 – 2x2 →max; f3= x1 + 2x2 →max; –x1+3x2 ≤ 9; x1+x2 ≤ 6; x1+ x2 ≤ 7; x2 ≥ 12; 2x1–‐ x2 ≤ 8; 3x1+2x2 ≤ 3; x1, x2 ≥ 0, δ1 = 2, δ2 = 5. Ответ: f1 (0; 3/2) = 3, 3/2, f3 (0; 3/2) = ‐3. f2 (0; 3/2) = x1, x2 ≥ 0, δ1 = 5, δ2 = 1. Ответ: f1 (3; 3) = 3, f3 (3; 3) = 9. Страница 161 из 184 f2 (3; 3) = 6, 12. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 12.1/ Экстремумы функции нескольких переменных 12.1.1. Квадратичные формы и матрица Гессе Для необходимо нахождения экстремума функции нескольких переменных ввести понятие квадратичной формы и условия ее положительной и отрицательной определенности. Определение. Функция n L(x1, x2,…, xn) = ∑ a ij x i x j (4) i, j =1 от n переменных называется квадратичной формой. Коэффициенты квадратичной формы aij ‐ действительные числа, причем aij = aji. В этом случае квадратичная форма (4) называется симметричной. Матрица А = (aij), составленная из коэффициентов квадратичной формы называется матрицей квадратичной формы (4). Примеры. (n = 2). 1. L(x1, x2) = a11 x1x1+ a12 x1x2 + a21 x2x1 + a22 x2x2 = a 11 x 12 + 2a 12 x 1 x 2 + a 22 x 22 . Матрица этой квадратичной формы есть ⎛a А = (aij) = ⎜⎜ 11 ⎝ a 21 a 12 ⎞ ⎟. a 22 ⎟⎠ 2. L(dx1, dx2) = zxx′′⋅dx2 + 2zxy′′⋅dx dy + zyy′′⋅dy2, Страница 162 из 184 Очевидно, что это дифференциал второго порядка функции z = f(x,y) Матрица этой квадратичной формы имеет вид: ⎛ ∂ 2f ⎜ 2 ⎜ ∂x 1 ⎜ ∂ 2f ⎜⎜ ⎝ ∂x 2 ∂x 1 ∂ 2f ⎞ ⎟ ∂x 1 ∂x 2 ⎟ ∂ 2f ⎟ ⎟ ∂ x 22 ⎟⎠ В матричной записи квадратичная форма имеет вид L = X A X′, где X = (x1, x2,…, xn) – матрица – строка, X′ = (x1, x2,…, xn)′ – матрица –столбец. Определение. Квадратичная форма L(x1,x2,…,xn) называется положительно (отрицательно) определенной, если при всех значениях переменных, из которых хотя бы одно отлично от нуля, L(x1, x2,…, xn) > 0, (L(x1, x2,…, xn) < 0). Квадратичная форма L(x1,x2,…,xn) называется неотрицательно (неположительно) определенной, если при всех значениях переменных, из которых хотя бы одно отлично от нуля, L(x1, x2,…, xn) ≥ 0, (L(x1, x2,…, xn) ≤ 0), и имеется отличный от нуля вектор x = (x1, x2,…, xn), для которого L(x1, x2,…, xn) = 0. Например, квадратичная форма L1 = y12 + 2 y 22 + 1,5 y 32 является положительно определенной, а форма отрицательно определенной. Страница 163 из 184 L2 = − y12 + 2 y1 y 2 − y 22 ‐ Замечание 1. Если квадратичная форма не является положительно или отрицательно определенной, то она называется знакопеременной. Пример. Применяя критерий Сильвестра, покажем, что форма L(x) = 5x 12 − 6 x 1 x 2 + 13x 22 является положительно определенной. Действительно, главные миноры матрицы Гессе для L(x) имеют вид: Δ1 = a11 = 5 > 0, Δ2 = На основании приведенной 5 −3 = 56 > 0. − 3 13 теоремы квадратичная форма L(x) является положительно определенной. Рассмотрим симметричную матрицу H(x) размером n×n, состоящую из вторых производных функции n переменных u = f(x1, x2,…,xn) ⎛ ∂ 2f ∂ 2f ∂ 2f ... ⎜ 2 ∂x1∂x n ⎜ ∂x 1 ∂x 1 ∂x 2 H (x) = ⎜ .................................. ⎜ 2 ∂ 2f ∂ 2f ⎜ ∂ f ... ⎜ ∂x ∂x ∂x ∂x ∂x n2 n 2 ⎝ n 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (6) Матрица H(x) называется матрицей Гессе. Такие матрицы широко применяются в экономических исследованиях. Матрица Гессе для функции u = f(x,y,z) записывается следующим образом: Страница 164 из 184 ⎛ u" u" u" ⎞ ⎜ xx xy xz ⎟ ⎜ ⎟ H (x) = ⎜ u " u " u " ⎟ . yx yy yz ⎜ ⎟ ⎜⎜ u " u " u " ⎟⎟ zy zz ⎠ ⎝ zx Заметим, что дифференциал второго порядка для функции u = f(x,y,z): d 2u = uxx′′⋅dx2 + uzz′′⋅dz2 + uyy′′dy2 +2uxy′′ dx dy + 2uxz′′⋅dx dz + 2uzy′′⋅dz dy. Следовательно, элементы матрицы Гессе для второго дифференциала состоят из коэффициентов при дифференциалах независимых переменных. Из условия симметричности матрицы элементы, расположенные симметрично относительно главной диагонали, равны, например, uxy′′ = uyx′′. Матрица (6) состоит из коэффициентов второго дифференциала функции u = f(x1, x2,…,xn) n переменных. Чтобы определить знак квадратичной формы или матрицы Гессе, применяется критерий Сильвестра. Определение. Угловыми минорами матрицы А = (aij) называются определители Δ1 = a11, a Δ2 = 11 a 21 a ... a 11 1n a 12 , …, Δ n = ............... a 22 a n 1 ... a n n Определение. Определители m – го порядка (m ≤ n), получающиеся из определителя матрицы Н(x) вычеркиванием каких‐либо (n ‐ m) строк и (n ‐ m) столбцов с одними и теми же номерами, называются главными минорами. Страница 165 из 184 Справедливо следующее утверждение относительно знакоопределенности матрицы Гессе (верно и для квадратичных форм): Теорема (критерий Сильвестра). 1. Для того, чтобы матрица Гессе Н(x) была положительно определенной, необходимо и достаточно, чтобы все угловые миноры определителя матрицы Гессе были положительны, т.е. Δ1 > 0, Δ2 > 0, …, Δ n > 0. 2. Для того, чтобы матрица Гессе Н(x) была отрицательно определенной, необходимо и достаточно, чтобы знаки угловых миноров определителя матрицы Гессе чередовались, причем 3. Для того, чтобы матрица Гессе Н(x) Δ1 < 0. была неотрицательно определенной, необходимо и достаточно, чтобы знаки главных миноров определителя матрицы Гессе были неотрицательны. 4. Для того, чтобы матрица Гессе Н(x) была неположительно определенной, необходимо и достаточно, чтобы все главные миноры четного порядка определителя матрицы Гессе были неотрицательны. а все главные миноры нечетного порядка неположительны. 12.1.2. Необходимые и достаточные условия экстремума Пусть дана дважды непрерывно дифференцируемая функция f(x), определенная на множестве Rn. Исследуем эту функцию на экстремум, т.е. определим точки ее локальных минимумов и максимумов на Rn. Для решения поставленной задачи сначала находим стационарные точки (точки возможного экстремума) с помощью необходимых условий Страница 166 из 184 первого и второго порядка (порядок условий определяется порядком производных), затем исследуем полученные точки с помощью достаточных условий. Сформулируем соответствующие определения и теоремы. Определение. Точки, в которых первые частные производные функции f(x1, x2,…,xn) равны нулю, т.е. f x' 1 = 0, …, f x' n = 0, называются стационарными точками или точками возможного экстремума. Теорема 2.1 (необходимое условие экстремума первого порядка). Пусть x* ∈ R n ‐ точка экстремума функции f(x), x ∈ Rn и функция f(x) дифференцируема в точке x*. Тогда первые частные производные функции f(x) в точке x* равны нулю, т.е. f x' 1 = 0, …, f x' n = 0. Теорема 2.2 (достаточное условие экстремума). Пусть функция f(x) в точке x* ∈ Rn дважды дифференцируема, и ее первые частные производные равны нулю т.е. f x' 1 = 0, …, f x' n = 0, а матрица Гессе является положительно определенной (отрицательно определенной), т.е. Н(x*) > 0 (Н(x*) < 0). Тогда точка является точкой локального минимума (максимума) функции f(x) на множестве Rn. Условия теоремы 2.2 могут быть не выполнены. Для этого случая сформулируем необходимые условия экстремума второго порядка. Теорема 2.3 (необходимое условие экстремума второго порядка). 1) Для того, чтобы точка x* ∈ Rn может быть являлась точкой локального Страница 167 из 184 минимума дважды дифференцируемой функции f(x), x ∈ Rn, необходимо, чтобы матрица Гессе была неотрицательно определенной (Н(x*) ≥ 0), т.е. все главные миноры определителя матрицы Гессе были неотрицательны. 2) Для того, чтобы точка x* ∈ Rn может быть являлась точкой локального максимума дважды дифференцируемой функции f(x), x ∈ Rn, необходимо, чтобы матрица Гессе была неположительно определенной (Н(x*) ≤ 0), т.е. все главные миноры четного порядка были неотрицательны, а все главные миноры нечетного порядка – неположительны. Пример. Найти экстремум функции u = x2 + у2 + z2 –2x – 6y – 4z. Решение. Находим стационарные точки (необходимые условия первого порядка, теорема 2.1): u 'x = 2x – 2 = 0, u 'y = 2y – 6 = 0, ' u z = 2z – 4 = 0, Решая эту систему, получим точку возможного экстремума (1,3,2). Проверим выполнение достаточных условий и необходимых условий второго порядка. Для определения знака матрицы Гессе применим критерий Сильвестра. Матрица Гессе для данной функции имеет вид ⎛2 0 0⎞ ⎜ ⎟ ⎜0 2 0⎟ ⎜0 0 2⎟ ⎝ ⎠ . Определим знаки угловых миноров матрицы: Страница 168 из 184 20 = 4 > 0, 02 a11 = 2 > 0, 2 0 0 0 2 0 0 2 = 8 > 0. Следовательно, матрица Гессе является положительно определенной. Согласно теореме 2.2, в точке (1,3,2) функция u (x,y,z) имеет (глобальный) минимум. Ответ. min u(x,y,z) = u(1,3,2) = ‐14. Для функции двух переменных необходимое условие экстремума аналогично. Достаточное условие обычно формулируется следующим образом. Теорема 2.4 (достаточное условие экстремума для функции двух переменных). Пусть функция z = f(x,y) в некоторой окрестности стационарной точки (x0,y0) имеет непрерывные частные производные второго порядка, причем z 'x = 0, z 'y = 0. ′ (x0, y0), Обозначим А = z ′xx ′ (x0, y0), В = z ′xy ′ (x0, y0). С = z ′yy Тогда справедливы следующие утверждения: 1. если АС ‐ В2 > 0, то функция z = f(x, y) имеет в точке (x0, y0) экстремум, причем если А < 0 ‐ максимум, А > 0 ‐ минимум; 2. если АС ‐ В2 < 0, функция экстремума не имеет; 3. если АС ‐ В2 = 0, то вопрос об экстремуме остается открытым. Алгоритм решения задачи на безусловный экстремум 1. Записать необходимые условия экстремума первого порядка в виде: Страница 169 из 184 f x' 1 = 0, f x' = 0, … , f x' n = 0. 2 Из этой системы уравнений находим стационарные точки (точки возможного экстремума) (теорема 2.1). 2. В найденных стационарных точках достаточных условий проверяем выполнение (теорема 2.2). Если они не выполняются, то проверяем необходимые условия экстремума второго порядка (теорема 2.3). 3. Вычисляем значения функции в точках экстремума. Пример. Найти экстремум функции f(x) = x12 ‐ x22 на множестве Rn. Решение. Находим стационарные точки (теорема 2.1): f 'x = 2 x1 = 0, f 'x = ‐ 2 x2 = 0, 1 2 Решая эту систему, получим точку возможного экстремума (0,0). Проверим выполнение достаточных условий и необходимых условий второго порядка. Матрица Гессе для данной функции имеет вид ⎛2 0 ⎞ ⎟⎟ . ⎝ 0 − 2⎠ H(x) = ⎜⎜ Так как Δ1 = 2 > 0, Δ2 = 2 0 0 −2 = ‐4 < 0, то достаточные условия экстремума не выполнены (теорема 2.2). Проверим выполнены ли необходимые условия экстремума второго порядка. Главные миноры первого порядка (m = 1) Страница 170 из 184 получаются из Δ2 в результате вычеркивания n – m = 2 – 1 = 1 строки и столбца с одинаковыми номерами. Получаем: – 2 и 2. Главный минор второго порядка (m = 2) получаются из Δ2 в результате вычеркивания n – m = 2 – 2 = 0 строк и столбцов, т.е. совпадает с Δ2 = ‐ 4. Отсюда следует, что необходимые условия экстремума второго порядка не выполняются (теорема 2.3). Вывод: в точке (0,0) нет экстремума. Пример. Найти экстремум функции u = x3 + у2 + z2 + yz – 3x + 6y + 2. Решение. Находим стационарные точки (теорема 2.1): u 'x = 2 x2 – 3 = 0, u 'y = 2y + z + 6 = 0, ' u z = 2z + y = 0, Решая эту систему, получим две точки возможного экстремума (1,‐4,2), (‐ 1,‐4, 2). Проверим выполнение достаточных условий и необходимых условий второго порядка. Матрица Гессе имеет вид H(x) = ⎛ 6x 0 0 ⎞ ⎟ ⎜ ⎜ 0 2 1⎟ . ⎜ 0 1 2⎟ ⎠ ⎝ Исследуем точку А1 = (1,‐4,2). H(А1) = ⎛6 0 0⎞ ⎟ ⎜ ⎜0 2 1⎟ . ⎜ 0 1 2⎟ ⎠ ⎝ Страница 171 из 184 Так как Δ1 = 6 > 0, Δ2 = 6 0 0 2 = 12 > 0, Δ3 = 18 > 0, о точка А1 является точкой локального минимума. Исследуем точку А2 = (‐1,‐4,2). H(А2) = Так как Δ1 = ‐ 6 < 0, −6 0 0 2 Δ2 = ⎛- 6 0 0⎞ ⎟ ⎜ ⎜ 0 2 1⎟ . ⎜ 0 1 2⎟ ⎠ ⎝ = ‐ 12 < 0, Δ3 = ‐ 18 < 0, то достаточные условия экстремума не выполняются (теорема 2.2). Согласно алгоритму проверим необходимые условия второго порядка. Главные миноры первого порядка Главные миноры первого порядка (m = 1) получаются из Δ3 в результате вычеркивания n – m = 3 – 1 = 2 строки и 2 столбца с одинаковыми номерами. Получаем: – 6, 2, 2. Главные миноры второго порядка (m = 2) получаются из Δ3 в результате вычеркивания n – m = 3 – 2 = 1 строк и столбцов с одинаковыми номерами: 3, ‐ 12, ‐ 12. Главный минор третьего порядка (m = 3) получаются из Δ2 в результате вычеркивания n – m = 3 – 3 = 0 строк и столбцов, т.е. совпадает с Δ3 = ‐ 18. Отсюда следует, что необходимые условия второго порядка не выполняются. Вывод: в точке А2 = (‐1,‐4,2) нет экстремума. Ответ. min u(x,y,z) = u(1,‐4,2) = ‐12. Упражнения. Найти экстремумы функций: 1. u = 3x2 + 5у2 + 4z2 + 6x – 8y + 2z. (umax = u(‐1; 4/5; ‐1/4)=247/5) Страница 172 из 184 2. z = 2x3 – 2xy + y2 (zmin = z(1/3;1/3) =‐1/27) 3. u = ‐ x2 ‐ у2 ‐ z2 + yx + 2y + 3(z. – 1) (umax = u(2/3;4/3;3/2)=0,583) 4. u = ‐ x2 ‐ у2 ‐ z2 + y + y z. (umax = u(0;2/3;1/3)=0,333) 5. z = x3 + у2 ‐ xy – 2x + 3y ‐ 4. ((zmin = z(1/2;‐5/4)) 12.1.3. Выпуклые функции В экономических приложениях выпуклые функции играют большую роль. Поэтому выясним, при каких условиях функция нескольких переменных будет выпуклой. Определение. Подмножество D n–мерного пространства называется выпуклым, если для любых двух точек А и B принадлежащих D, отрезок, соединяющий эти точки, также принадлежит D. Примеры выпуклых множеств: прямая, отрезок, круг, шар, пирамида. Наиболее естественными примерами выпуклых множеств является плоскость R2 в случае двух переменных и пространство R3 в случае трех переменных и их сектора, заданные условиями x ≥ 0, y ≥ 0, z ≥ 0. Определение. Функция z = f(x), где x = z (x1, x2,…, xn ) заданная на множестве D, называется M1 векторов x и y и любого числа t ∈ (0; 1) y выполняется неравенство (x2,y2) M2 Рис.10.4 (x1,y1) выпуклой вниз (выпуклой), если для любых двух P x выпуклом Страница 173 из 184 t f(x) + (1 ‐ t)f(y) ≥ f((1 ‐ t)x + ty) , (1) и выпуклой вверх (вогнутой), если t f(x) + (1 ‐ t)f(y) ≤ f((1 ‐ t)x + ty). (2) Для функции двух переменных z = f(x,y) эти неравенства можно представить в более простом виде (Рис. 10.4) (t = 0,5): f (x1, y1) + f (x2, y2) ⎛x +x y +y ⎞ f⎜ 1 2 , 1 2 ⎟ ≥ 2 ⎠ 2 ⎝ 2 f (x1, y1) + f (x2, y2) ⎛x +x y +y ⎞ f⎜ 1 2 , 1 2 ⎟ ≤ . 2 ⎠ 2 ⎝ 2 Если неравенства (1) или (2) выполняются как строгие неравенства, то функция z = f(x) называется строго выпуклой или строго вогнутой соответственно на выпуклом множестве D. Геометрически условие выпуклости вниз графика функции z = f(x,y) на множестве D означает, что точки графика этой функции, отвечающие точкам отрезка, соединяющие любые точки множества (x1, y1) и (x2, y2) (например, точка Р на рис.10.4), лежат не выше хорды, соединяющей точки (x1, f(x1)) и (x2, f(x2)) указанного графика (точка М1 на Рис.10.4). Пример. Рассмотрим производственную функцию Кобба – Дугласа: y=A x1L1x2L2 (0 0, Δ2 = 16 0 = 192 > 0. 0 12 Страница 175 из 184 Следовательно, матрица Гессе положительно определена, значит данная функция (строго) выпукла вниз. Из необходимых условий экстремума находим точку возможного экстремума: x = 1/8, y = ‐ 1/3. В силу выпуклости вниз функции z точка (1/8, ‐1/3) является точкой глобального минимума. Пример. Рассмотрим функцию u(x,y,z) = ‐4х2 ‐ 3у2 ‐ 5z2 + 6x ‐ 7y + 12z. Угловые миноры матрицы Гессе для функции u имеют вид: −8 0 −8 0 Δ1 = a11 = ‐8 < 0, Δ2 = = 48 > 0, Δ3 = 0 − 6 0 = ‐192 < 0. 0 −6 0 −4 Следовательно, матрица Гессе отрицательно определена, значит функция u выпукла вверх (вогнутая). Из необходимых условий экстремума находим точку возможного экстремума: x = 3/4, y = ‐ 7/6, z = 6/5. В силу выпуклости вверх точка (3/4, ‐7/6, 6/5) является точкой глобального максимума. Пример. Применяя критерий Сильвестра, покажем, что функция f(x,y,z) = x2 +5y2 +16z2 + 4xy + 8yz является выпуклой и найдем ее экстремум. Решение. Действительно, матрица Гессе для функции f имеет вид: Страница 176 из 184 ⎛1 ⎜ ⎜2 ⎜0 ⎝ 2 5 4 0⎞ ⎟ 4 ⎟. 16 ⎟⎠ Находим главные миноры: Δ1 = 1 > 0, Δ2 = На основании теоремы 2.5 1 2 2 5 1 2 = 1 > 0. Δ3= 2 5 4 = 0. 0 4 16 заключаем, что матрица Гессе является неотрицательно определенной, следовательно, функция f выпуклая вниз функция. Из необходимых условий экстремума находим точку возможного экстремума: x = 0, y = 0, z = 0. В силу выпуклости вниз функции f точка (0, 0, 0) является точкой глобального минимума. Задачи. 1. Определить направление выпуклости функции и найти ее экстремум. u= 2(x – 1)2 + y2 + z2 – x(y – 1) – xz – y(z – 1). (min (1,1/3,2/3)) 2. Определить направление выпуклости функции полезности u (x1 , x 2 ) = x1α x2β , α > 0, β > 0; α + β < 1. (выпуклая вверх) 3. Определить направление выпуклости функции z = x2 – 4xy + 4y2 (Матрица Гессе неотрицательно определена, выпуклость вверх) Страница 177 из 184 12.1.4. Производная по направлению. Градиент Дана функция z = f(x, y ), которая определена y в окрестности точки M0(x0, y0). M(x, y) β Для приложений интересен вопрос о αа M0(x0, y0) том, x в каком функции Рис.10.2 направлении наибольшее изменение (возрастание или убывание). Далее, нужно указать это направление и вычислить скорость изменения функции в этом направлении. Для выяснения этого вопроса введем понятие производной по направлению и градиента функции. Рассмотрим вектором: некоторое направление, задаваемое единичным a(cos α, cos β), ⎜a⎜ = cos 2 α + cos 2 ( π / 2 − α) = 1. Проведем в направлении вектора a из точки M0(x0, y0) ось n и возьмем на ней точку ⎜M0 M⎜ = n. Тогда M(x, y) (см. Рис.10.2), причем x = x0 + n cos α , y = y0 + n cos β и (2) функция z = f(x, y) на данной оси является сложной функцией от n. Покажем, что производная по n, которая называется производной по направлению n функции z = f(x, y) задается выражением ∂z ∂n = z 'x cos α + z 'y sin α Страница 178 из 184 (3) Действительно, так как функция z = f(x, y) является сложной функцией от n, то ее производная по n ∂z ∂z dx ∂z dy = + . ∂n ∂x dn ∂y dn (4) Из формул (2) выводим dx dy = cos α, = sin α. dn dn Подставляя это в (4), получаем формулу (3). Определение. Градиентом функции z = f(x, y) называется вектор с координатами ( z 'x , z 'y ). Обозначение: grad z, ∇z . Рассмотрим скалярное произведение градиента и вектора n: (∇z, n) = z 'x cos α + z 'y sin α = z 'n . Следовательно, z 'n = (∇z, n ) = |∇z | |n| cos ϕ = |∇z | cos ϕ. Очевидно, что производная по направлению будет максимальна при ϕ = 0, т.е. если направление совпадает с градиентом. Отсюда (zn ) max = |∇z |. Следовательно, градиент функции в данной точке характеризует направление и величину максимального роста функции в этой точке. Пример. Найти максимальную скорость возрастания функции z = x1/2y1/2 в точке М(1,1) и определить характер ее изменения в направлении n(1,2). Страница 179 из 184 Решение. z′x = 1/2(y/x)1/2, z′y = 1/2(x/y)1/2. Следовательно, градиент ∇z = (1/2(y/x)1/2, 1/2(x/y)1/2)|M = (1/2,1/2). Величина скорости изменения функции в направлении градиента |∇z | = (1/2) 2 + (1 / 2) 2 = 1/√2. Вычислим производную по направлению n(1,2) в точке М(1,1): cos α = 1/ |n| = 1/ 12 + (2) 2 = 1/ 5 ; sin α = 2 / 12 + (2) 2 = 2 / 5 . z 'n = z 'x cos α + z 'y sin α = 1/2 ⋅ 1/ 5 + 1/2 ⋅ (2 / 5 ) = 3/(2 5 ). Очевидно, что скорость возрастания функции точке М(1,1) в направлении градиента больше, чем в направлении n(1, 2). Теорема. Пусть задана дифференцируемая функция z = f(x, y) и пусть в точке M(x0, y0) градиент отличен от нуля: grad z ≠ 0. Тогда градиент перпендикулярен линии уровня функции z = f(x, y), проходящей через данную точку. Докажем этот факт. Действительно, уравнение линии уровня есть f(x, y) = C, где С ‐ число. Разрешим это уравнение относительно y т.е. y = v(x). Уравнение касательной к графику y = v(x) в точке М запишется в виде: y = y0 + v' (x0)(x – x0). (2) Из математического анализа известно, что производная v(x) выражается через частные производные функции f(x, y) в точке М формулой v'(x) = f x' / f y' Страница 180 из 184 . Подставив это выражение в формулу (2), получим уравнение касательной к линии уровня: f x' (x – x0) + f y' (y – y0) = 0. Из аналитической геометрии известно, что вектор коэффициентов при x и y, т.е. ( f x' , f y' ) в уравнении прямой перпендикулярен к данной прямой. Теорема доказана. Упражнения. 1. Покажите, что касательная к линии уровня функции z = x y перпендикулярна градиенту в любой точке плоскости x > 0, y > 0. 2. Найти максимальную скорость возрастания функции z = x1/4 y1/4 в точке М(1,1) и определить характер ее изменения в направлении n(1,2). 3. Найти производную функции u = xy2z + yz2 – 3z в точке М1(0;1;2) по направлению от точки М1 к точке М2(– 2;3; – 1). (√17/17) 12.1.5. Частная эластичность и линии уровня функции Рассмотрим производственную функцию Кобба – Дугласа (ПФКД) у = А⋅Kα Lβ, где К – объем фондов, L – объем трудовых ресурсов, у ‐ выпуск продукции в стоимостном выражении. Пусть текущее состоянии фирмы (K, L), выпуск продукции равен y(K, L). Если нанять еще одного работника, то Δу = у (K, L + 1) – y (K, L) ≈ y′L ΔL. Так как ΔL = 1, то Δу ≈ y ′L (K, L). Страница 181 из 184 Следовательно, производная выпуска по труду приближенно равна добавочной стоимости продукции, произведенной еще одним дополнительным работником, поэтому y′L = А⋅β⋅αKα Lβ ‐1 ‐ предельная производительность труда y′k = А⋅α⋅Kα ‐1 Lβ ‐ предельная фондоотдача. Часто возникает вопрос, на сколько процентов изменится выпуск продукции, если число работников увеличится на 1%, или если фонды вырастут на 1 %? Ответом на этот вопрос служит величина, определяемая следующим образом: E Ly = y′L y/L ; E Ky = y′K ; y/K Для ПФКД эти величины равны соответственно EK(AKαLβ) = α, EL(AKαLβ) = β. Эти величины называются эластичностью выпуска по труду и эластичностью выпуска по фондам соответственно. Для приложений и для образного представления функции z = f(x, y) введем понятие линий заданного уровня С, где С – число. Определение: Линией уровня С функции z = f(x, y) множество {x, y} такое, что на этом множестве f(x, y) = С. Примеры: 1) Для функции z = х2 + у2, при С = 4, получим линию уровня Страница 182 из 184 называется х2 + у2 = 4 – это окружность с радиусом r = 2. Следовательно, линиями z = х2 + у2, уровня функции являются семейство концентрических окружностей с центром в начале координат. 2) Линии уровня функции z = xy гипербол y= 3) Для функции при С = k, (k – число) это семейство k . x α β z = А x1 x 2 линиями уровня являются степенные гиперболы. Линии уровня производственной функции называются изоквантами. Следовательно, изокванты производственной функции – это линии постоянного выпуска. Упражнения. 1. Построить линии уровня для функций: а) z = х2 + у2 – 2y; б) z = х2 +2x + у2. 2. Изобразите графики линий уровня функций в примерах 1 и 2 в плоскости XOY. 2. Постройте график линии уровня для функции z = x 1 x 2 при С = 2. 3. Покажите, что для ПФКД EK(AKαLβ) = α, EL(AKαLβ) = β. Страница 183 из 184 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н.Высшая математика для экономических специальностей: учебник и практикум, под ред. Н.Ш. Кремера. – М.: Высшее образование, 2009. 2. Грошев Л.Н. Математика: Учебное пособие.‐ М.: Издательство МЭИ, 2003. 3. Солодовников А.С. и др. Математика в экономике: Учебник: В 2‐х ч. Ч.1. М.: Финансы и статистика, 2006. 4. Орлова И.В., Половников В.А. Экономико‐математические методы и модели: компьютерное моделирование: Учеб.пособие. – М.: Вузовский учебник, 2008. 5. Плотников А.Д. Математическое программирование: экспресс‐курс – Мн.: Новое знание, 2006. 6. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах: Учеб. Пособие‐ М.: Высш. Шк., 2008. 7. Математические методы и модели исследования операций: учебник для студентов вузов/ под ред. В.А. Колемаева. – М.: ЮНИТИ‐ДАНА, 2008. 8. Корнеенко В.П. Методы оптимизации: Учебник – М.: Высш. шк., 2007. Страница 184 из 184