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

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

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

Реализация метода состоит в выполнении следующих шагов.

Шаг 1. Целевая функция и область ограничений задачи (4.1)-(4.2) проверяются на обладание свойствами, приведенными в таблице 1.1. В случае отрицательного заключения реализация метода заканчивается – он неприменим к данной задаче (что не означает, что задача не имеет решений! – возможно, она может быть решена другими методами). В случае положительного заключения делается переход на шаг 2.

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

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

.

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

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

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

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

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

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

Из первых 3-х уравнений имеем , , , причем . Поэтому из 4-го уравнения получаем

откуда сразу следует

Функция вогнута в области определения, поэтому условия Куна-Таккера являются достаточными для существования экстремума. Согласно теореме о единственности экстремума строго выпуклой функции найденная точка является единственной точкой глобального максимума. Соответствующий набор товаров имеет полезность

.

4.3. Задачи

105. если

106. если

107. если

108. если

109. если

110. если

111. если

112. если

113. если

114. если

115. если

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

,

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

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

,

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

118. Прибыль от реализации двух видов продукции имеет вид , где и – количество единиц произведенной продукции 1-го и 2-го видов соответственно. Затраты сырья каждого вида на единицу продукции каждого вида и запасы сырья заданы в таблице:

Виды сырья	Расход сырья на единицу продукции		Запасы сырья
	Продукция 1	Продукция 1
Сырье 1	2	3	6
Сырье 2	3	2	6

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

119. Полезность набора из двух товаров определяется формулой , где и – количество единиц 1-го и 2-го товаров соответственно. Вес и цена единицы товара каждого вида заданы в таблице:

Виды товара	Характеристики товаров
	Вес единицы товара	Цена единицы товара
Товар 1	7	3
Товар 2	5	2

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

120. Фирма, производящая продукцию на трех заводах, решила выпускать в месяц не менее 210 единиц продукции при наименьших суммарных затратах. Пусть , и – количество продукции, производимой на первом, втором и третьем заводах соответственно, а функции издержек заводов имеют вид:

; ; .

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

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

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

,

где , и – значения факторов производства. Количество изготовленных изделий 1-го вида равно , а количество изделий 2-го вида равно . Определить значения задающие общие минимальные издержки при условии, что изделий 1-го вида должно быть не менее 120, а 2-го – не менее 100.