METODY_REShENIYa_ZNLP

4. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИ-

РОВАНИЯ ПРИ ОГРАНИЧЕНИЯХ-НЕРАВЕНСТВАХ

ограничений.

4.1. Обобщенный метод множителей Лагранжа

Идея обобщенного метода множителей Лагранжа состоит в том, что если точка безусловного экстремума целевой функции не удовлетворяет всем ограничениям задачи, то тогда решение задачи с ограничениями должно достигаться (если оно есть) в граничной точке области ограничений (см. теорему Вейерштрасса). Отсюда следует, что одно или несколько ограничений в (4.2) должны выполняться как точные равенства.

Схема реализации обобщенного метода множителей Лагранжа

Реализация метода состоит в выполнении следующих шагов. Шаг 1. Параметр k (число учитываемых ограничений задачи) по-

лагается равным нулю. Исходная задача решается без учета ограничений. Если найденная экстремальная точка удовлетворяет всем ограничениям исходной задачи, то она запоминается. Параметр k увеличивается на единицу: k : k 1 . Переход на шаг 2.

Шаг 2. Формируется система из k ограничений-равенств текущей задачи: произвольные k ограничений-неравенств исходной задачи делаются «активными» посредством замены знака неравенства на знак равенства и включаются в формируемую систему ограничений. Переход на шаг 3.

41

Шаг 3. Полученная на предыдущем шаге текущая задача с исходной целевой функцией и системой «активных» ограниченийравенств решается каким-либо подходящим методом (например, обычным методом множителей Лагранжа). Если найденная экстремальная точка удовлетворяет ограничениям исходной задачи, то она запоминается. Переход на шаг 4.

Шаг 4. а) Если k m (число активных ограничений меньше числа ограничений исходной задачи), то формируется такая система из k активных ограничений, которая еще ни разу не присутствовала в решаемых перед этим задачах, после чего производится переход на шаг 3. В том случае, когда все возможные наборы из k активных ограничений перед этим рассмотрены, а соответствующие задачи решены, параметр k увеличивается на единицу: k : k 1 . Переход на шаг 2.

б) Если k m , то вычисления заканчиваются. В качестве решения исходной задачи берется та из запомненных на предыдущих шагах экстремальных точек, которая дает наибольшее (наименьшее) значение целевой функции. При отсутствии запомненных экстремальных точек делается вывод об отсутствии решения исходной ЗНЛП.

Замечание 4.1. Возможности применения метода для решения практических задач без применения компьютера ограничены, поскольку для его реализации требуется вместо одной исходной задачи решать большое число задач с ограничениями-равенствами. Например, если число ограничений в (4.2) m 5 , а число активных ограничений k 3 , то тогда на шаге 2 надо будет решить

задач с тремя ограничениями-равенствами.

4.2. Условия Куна-Таккера

Получим условия Куна-Таккера, позволяющие идентифицировать стационарные точки в задаче (4.1)-(4.2). Указанные условия являются необходимыми, однако оказываются также и достаточными, если целевая функция и функции ограничений обладают некоторыми специальными свойствами.

42

4.2.1. Необходимость условий Куна-Таккера

Преобразуем ограничения-неравенства в (4.2) к виду ограниче- ний-равенств. Для этого к левым частям каждого j -го неравенства

u j s2j 0 , подобранные таким образом, что все ограничения исходной задачи предстают в виде ограничений-равенств.

ЗНЛП (4.1)-(4.2) принимает вид

f (x) max(min);

В развернутой форме она записывается следующим образом:

Полученную ЗНЛП с ограничениями-равенствами можно решить

Необходимым условием существования экстремума целевой функции при ограничениях-равенствах является наличие стационарной точки функции Лагранжа. В стационарной точке все производные функции Лагранжа равны нулю, поэтому из (4.6) следует, что стационарной точкой является любое решение системы уравнений

43

Из уравнений второй строки системы (4.7) следует

Условие (4.8) называется условием дополняющей нежесткости. Покажем, что необходимым условием существования экстремума целевой функции в задаче (4.1)-(4.2) является условие

yi 0, i 1, m , в задаче максимизации (когда f (x) max ) и усло-

то есть множители Лагранжа выражают скорость изменения целе-

вой функции f (x) по отношению к изменениям правой части огра-

значений аргумента x , то это означает, что значение максимума целевой функции не уменьшится при таком увеличении, то есть

yi 0, i 1, m . Совершенно аналогично показывается, что условием существования экстремума целевой функции в задаче минимизации является условие yi 0, i 1,m .

Таким образом, объединяя (4.7) и (4.8) с условиями неотрицательности (неположительности) множителей Лагранжа, получаем систему условий существования экстремума функции при ограни- чениях-неравенствах, которые можно сформулировать в виде следующей теоремы.

44

Замечание 4.2. Из 1-го и 3-го условий Куна-Таккера следует, что либо множитель Лагранжа равен нулю, либо соответствующее ограничение выполняется как точное равенство, либо и то и другое выполняются одновременно.

4.2.2. Достаточность условий Куна-Таккера в задачах выпукловогнутого программирования

Условия Куна-Таккера для задачи (4.1)-(4.2) оказываются доста-

свойствами, связанными с выпуклостью и вогнутостью, и указанными в таб. 4.1.

выпуклым множеством при условии, что функция gi (x) выпукла

на Rn . Поскольку пересечение выпуклых множеств является выпуклым множеством, то достаточным условием выпуклости области ограничений в задаче (4.1)-(4.2) является условие выпуклости всех функций ограничений. В частности, в случае линейных ограничений допустимое множество всегда будет выпуклым (а именно – выпуклым многогранником).

45

Свойства выпуклости и вогнутости являются настолько значимыми, что порождают два широко распространенных класса задач нелинейного программирования.

если целевая функция f (x) является выпуклой функцией, а область ограничений D есть выпуклое множество.

если целевая функция f (x) является вогнутой функцией, а область

ограничений D есть выпуклое множество.

Следующая теорема позволяет обосновать изложенный ниже метод решения задачи выпукло-вогнутого программирования (метод Куна-Таккера).

Теорема о единственности экстремума строго выпуклой (во-

гнутой) функции. Строго выпуклая (строго вогнутая) функция

на выпуклом множестве D Rn не может иметь более од- f (x)

ной точки глобального минимума (максимума).

4.2.3. Метод Куна-Таккера решения задачи выпукло-вогнутого программирования

Полученные в разделе 2.1 необходимые условия Куна-Таккера существования стационарной точки и теорема о единственности экстремума строго выпуклой (вогнутой) функции лежат в основе следующего метода решения задачи выпукло-вогнутого программирования (метода Куна-Таккера).

Схема реализации метода Куна-Таккера

Реализация метода состоит в выполнении следующих шагов. Шаг 1. Целевая функция и область ограничений задачи (4.1)-

(4.2) проверяются на обладание свойствами, приведенными в таблице 1.1. В случае отрицательного заключения реализация метода заканчивается – он неприменим к данной задаче (что не означает,

46

что задача не имеет решений! – возможно, она может быть решена другими методами). В случае положительного заключения делается переход на шаг 2.

Шаг 2. Выписываются условия Куна-Таккера и находится какоелибо удовлетворяющее всем этим условиям решение. Если целевая функция является строго выпуклой (строго вогнутой), то это решение определяет единственное искомое решение исходной задачи.

Пример 4.1. Функция полезности набора из трех товаров в количестве x1, x2 и x3 единиц соответственно, определяется как

u f (x) ln(x1x2 x3 ) .

Цены товаров равны соответственно 10, 20 и 30 у.е. Требуется найти набор товаров максимальной полезности при условии, что его стоимость будет не более 900 у.е.

Решение. Необходимо решить следующую задачу:

f (x) ln x1 ln x2 ln x3 max; 10x1 20x2 30x3 900.

Реализуем метод Куна-Таккера.

Шаг 1. Функция логарифма является строго вогнутой на любом

интервале. Следовательно, целевая функция f (x) также вогнута как

сумма вогнутых функций. Область ограничений является выпуклым множеством (выпуклым многогранником).

Шаг 2. Составим функцию Лагранжа

Из первых 3-х уравнений имеем x1 101 y , x2 201 y , x3 301 y , причем y 0 . Поэтому из 4-го уравнения получаем

900 10x1 20x2 30x3 900 3y 0.

47

Функция f (x) вогнута в области определения, поэтому условия

Куна-Таккера являются достаточными для существования экстре-

мума. Согласно теореме о единственности экстремума строго вы-

единственной точкой глобального максимума. Соответствующий набор товаров имеет полезность

48

функция выражает объем выпускаемой фирмой продукции) имеет следующий вид:

где x1 , x2 затраты ресурсов. Цена покупки фирмой единицы ресурсов x1 , x2 равна 5 и 10 у.е. соответственно. Фирма не может потратить на покупку ресурсов более 1000 у.е. Технология производства такова, что x1 2x2 . Каков наибольший выпуск?

118. Производственная функция определяется как

1/ 3 1/ 3 1/ 3

f (x) 3x y z ,

где x, y, z значения факторов производства, себестоимости едини-

цы которых равны соответственно, 20, 5 и 10 у.е. Найти максимальное значение выхода готовой продукции при условии, что ее себестоимость будет не больше 6000, а значения каждого из факторов производства не превысят 200.

119. Прибыль от реализации двух видов продукции имеет вид

f (x) ln(x1x2 ) , где x1 и x2 – количество единиц произведенной

продукции 1-го и 2-го видов соответственно. Затраты сырья каждого вида на единицу продукции каждого вида и запасы сырья заданы в таблице:

Требуется найти оптимальный план производства, то есть значения x1 , x2 , обеспечивающие максимальную прибыль, при условии имеющихся запасов сырья.

120. Полезность набора из двух товаров определяется формулой

f (x) x1x2 , где x1 и x2 – количество единиц 1-го и 2-го товаров

соответственно. Вес и цена единицы товара каждого вида заданы в таблице:

49

Требуется найти оптимальный набор товаров, максимальной полезности при условии, что его общая стоимость не превысит 150, а вес будет не более 210.

121. Фирма, производящая продукцию на трех заводах, решила выпускать в месяц не менее 210 единиц продукции при наименьших суммарных затратах. Пусть x1 , x2 и x3 – количество продукции,

производимой на первом, втором и третьем заводах соответственно, а функции издержек заводов имеют вид:

Сколько продукции ежемесячно следует выпускать на каждом заводе?

водства. Количество изготовленных изделий выражается функцией

(x) x1 2x2 3x3 . Решить задачу минимизации издержек при

условии выполнения плана по количеству готовых изделий, которых должно быть не менее 140. Сколько продукции ежемесячно следует выпускать на каждом заводе?

123. Совокупные издержки производства изделий 2-х видов определяются формулой

условии, что изделий 1-го вида должно быть не менее 120, а 2-го – не менее 100.

50