|
|
Градиентный метод решения задач выпуклого программирования.В случае, когда применение точных методов решения задач выпуклого программирования затруднительно в связи со сложностью границы множества допустимых решений или система ограничений имеет громоздкий вид, применяют численные (приближенные) методы решения. Однако данные методы в случае задач нелинейного программирования не обеспечивают нахождение глобального экстремума. Рассмотрим градиентные метод решения задач выпуклого программирования, когда ограничения задаются линейными неравенствами. Пусть необходимо найти
Алгоритм решения задачи выпуклого программирования. Пусть функция
при линейных ограничениях
1 шаг. С помощью какого-либо способа задаем: а) начальную точку 2 шаг. Для любой заданной точки 1. Находим значение функции 2. Вычисляем градиент функции 3. В окрестности точки
4. Переходим к решению задачи линейного программирования. Найти
при ограничениях
Пусть решением задачи будет вектор 5. Следующую точку
Параметр t находим из условия 6. Проверяем условие Пример: Предприятие выпускает два вида изделий А и Б. Нормы расхода на производство каждого вида изделия приведены в таблице. При этом известно, что сырья имеется 12 т, а оборудования – 30 станко-часов.
Определить оптимальный план реализации продукции обеспечивающий максимум прибыли предприятию, если себестоимость одного изделия соответственно равна ( Решение: Прибыль предприятия при плане
Определим градиент функции Задаем начальные значения Первая итерация. Определим градиент функции в точке
Составим функцию
Запишем функцию
Максимум этой функции найдем из условия равенства нулю первой производной этой функции:
Так как Вторая итерация. Определим градиент функции в точке
Составим функцию
Запишем функцию
Максимум этой функции найдем из условия равенства нулю первой производной этой функции:
Тогда Ответ: Оптимальный план Задачи для закрепления материала: Решить соответствующий вариант задачи методом градиентов, сделав две итерации. Предприятие выпускает изделия двух видов, при изготовлении которых используется сырье 1 и 2. Известны запасы сырья
  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
на множестве 
. Для отыскания 
выбирают последовательность векторов 
, 
, …, 
, … таких, что 
и 
. Если 
строго выпукла на 
при 
можно ожидать, что 
. Поэтому, обрывая последовательность 
на некотором шаге, получим для достаточно малого заданного 
оценку 
. Число 
характеризует точность решения 
.
,
, 
.
, б) точность решения 
:
.
.
функцию 
заменяем линейной функцией
,
.
находим на отрезке, соединяющем точки 
и 
, или
, 
на указанном отрезке.
. Если оно выполняется, то прекращаем решение, при этом точку 
. Если условие не выполняется, то переходим к первому пункту шага 2 принимая в качестве точки 
руб. и (
руб., где 
и 
- план выпуска изделия А и Б.
равна 
. Тогда математическая модель задачи будет окончательно иметь вид:
.
и 
. Тогда 
)=6,8.
. Находим, что точка 
максимума 
есть (1,5; 3,75). Применяя соотношение (*), получим
, то возьмем максимальное допустимое значение 
, чтобы не выйти из области X. Тогда 
), 
и 
.
. Находим, что точка 
максимума 
есть (4; 0). Применяя соотношение (*), получим
, 
и 
.
с точностью 
, нормы его расхода 
на единицу изделия, оптовые цены 
за единицу изделия и себестоимость 
. Составить план выпуска изделий, дающий предприятию максимальную прибыль.
