|
|
Достаточность условий Куна-Таккера в задачах выпукло-вогнутого программированияУсловия Куна-Таккера для задачи (4.1)-(4.2) оказываются достаточными, если целевая функция Таблица 4.1
Нетрудно показать, что множество
Свойства выпуклости и вогнутости являются настолько значимыми, что порождают два широко распространенных класса задач нелинейного программирования. Задачей выпуклого программирования называется ЗНЛП
если целевая функция Задачей вогнутого программирования называется ЗНЛП
если целевая функция Следующая теорема позволяет обосновать изложенный ниже метод решения задачи выпукло-вогнутого программирования (метод Куна-Таккера).
Теорема о единственности экстремума строго выпуклой (вогнутой) функции. Строго выпуклая (строго вогнутая) функция Метод Куна-Таккера решения задачи выпукло-вогнутого программирования Полученные в разделе 2.1 необходимые условия Куна-Таккера существования стационарной точки и теорема о единственности экстремума строго выпуклой (вогнутой) функции лежат в основе следующего метода решения задачи выпукло-вогнутого программирования (метода Куна-Таккера). Схема реализации метода Куна-Таккера Реализация метода состоит в выполнении следующих шагов. Шаг 1. Целевая функция и область ограничений задачи (4.1)-(4.2) проверяются на обладание свойствами, приведенными в таблице 1.1. В случае отрицательного заключения реализация метода заканчивается – он неприменим к данной задаче (что не означает, что задача не имеет решений! – возможно, она может быть решена другими методами). В случае положительного заключения делается переход на шаг 2. Шаг 2. Выписываются условия Куна-Таккера и находится какое-либо удовлетворяющее всем этим условиям решение. Если целевая функция является строго выпуклой (строго вогнутой), то это решение определяет единственное искомое решение исходной задачи.
Пример 4.1. Функция полезности набора из трех товаров в количестве
Цены товаров равны соответственно 10, 20 и 30 у.е. Требуется найти набор товаров максимальной полезности при условии, что его стоимость будет не более 900 у.е. Решение. Необходимо решить следующую задачу:
Реализуем метод Куна-Таккера. Шаг 1. Функция логарифма является строго вогнутой на любом интервале. Следовательно, целевая функция Шаг 2. Составим функцию Лагранжа
Условия Куна-Таккера:
Из первых 3-х уравнений имеем
откуда сразу следует Функция
Задачи 105. 106. 107. 108. 109.
110.
111.
112.
113.
114.
115.
116. Производственная функция
где 117. Производственная функция определяется как
где
118. Прибыль от реализации двух видов продукции имеет вид
Требуется найти оптимальный план производства, то есть значения
119. Полезность набора из двух товаров определяется формулой
Требуется найти оптимальный набор товаров, максимальной полезности при условии, что его общая стоимость не превысит 150, а вес будет не более 210. 120. Фирма, производящая продукцию на трех заводах, решила выпускать в месяц не менее 210 единиц продукции при наименьших суммарных затратах. Пусть
Сколько продукции ежемесячно следует выпускать на каждом заводе? 121. Функция издержек некоторого производства имеет вид 122. Совокупные издержки производства изделий 2-х видов определяются формулой
где   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
и область ограничений 
обладают определенными свойствами, связанными с выпуклостью и вогнутостью, и указанными в таб. 4.1.
является выпуклым множеством при условии, что функция 
выпукла на 
. Поскольку пересечение выпуклых множеств является выпуклым множеством, то достаточным условием выпуклости области ограничений в задаче (4.1)-(4.2) является условие выпуклости всех функций ограничений. В частности, в случае линейных ограничений допустимое множество всегда будет выпуклым (а именно – выпуклым многогранником).
(4.10)
есть выпуклое множество.
(4.11)
не может иметь более одной точки глобального минимума (максимума).
и 
единиц соответственно, определяется как
.
, 
, 
, причем 
. Поэтому из 4-го уравнения получаем
является единственной точкой глобального максимума. Соответствующий набор товаров имеет полезность
.
если 
если 
если 
если 
если
если
если
если
если 
если
,
затраты ресурсов. Цена покупки фирмой единицы ресурсов 
равна 5 и 10 у.е. соответственно. Фирма не может потратить на покупку ресурсов более 1000 у.е. Технология производства такова, что 
. Каков наибольший выпуск?
,
значения факторов производства, себестоимости единицы которых равны соответственно, 20, 5 и 10 у.е. Найти максимальное значение выхода готовой продукции при условии, что ее себестоимость будет не больше 6000, а значения каждого из факторов производства не превысят 200.
, где 
и 
– количество единиц произведенной продукции 1-го и 2-го видов соответственно. Затраты сырья каждого вида на единицу продукции каждого вида и запасы сырья заданы в таблице:
, обеспечивающие максимальную прибыль, при условии имеющихся запасов сырья.
, где 
, 
и 
; 
; 
.
, где 
. Решить задачу минимизации издержек при условии выполнения плана по количеству готовых изделий, которых должно быть не менее 140. Сколько продукции ежемесячно следует выпускать на каждом заводе?
,
, а количество изделий 2-го вида равно 
. Определить значения 
задающие общие минимальные издержки при условии, что изделий 1-го вида должно быть не менее 120, а 2-го – не менее 100.