Градиентный метод решения задач выпуклого программирования.

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

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

Пусть необходимо найти на множестве . Для отыскания выбирают последовательность векторов , , …, , … таких, что и . Если строго выпукла на , то из при можно ожидать, что . Поэтому, обрывая последовательность на некотором шаге, получим для достаточно малого заданного оценку . Число характеризует точность решения .

Алгоритм решения задачи выпуклого программирования.

Пусть функция выпуклая на множестве . Необходимо найти

,

при линейных ограничениях

, .

1 шаг. С помощью какого-либо способа задаем: а) начальную точку , б) точность решения .

2 шаг. Для любой заданной точки :

1. Находим значение функции .

2. Вычисляем градиент функции .

3. В окрестности точки функцию заменяем линейной функцией

4. Переходим к решению задачи линейного программирования. Найти

,

при ограничениях

, .

Пусть решением задачи будет вектор .

5. Следующую точку находим на отрезке, соединяющем точки и , т.е. , или

,

Параметр t находим из условия на указанном отрезке.

6. Проверяем условие . Если оно выполняется, то прекращаем решение, при этом точку и соответствующее значение функции считаем приближенным решением задачи . Если условие не выполняется, то переходим к первому пункту шага 2 принимая в качестве точки точку

Пример:

Предприятие выпускает два вида изделий А и Б. Нормы расхода на производство каждого вида изделия приведены в таблице. При этом известно, что сырья имеется 12 т, а оборудования – 30 станко-часов.

Определить оптимальный план реализации продукции обеспечивающий максимум прибыли предприятию, если себестоимость одного изделия соответственно равна ( руб. и ( руб., где и - план выпуска изделия А и Б.

Решение: Прибыль предприятия при плане равна . Тогда математическая модель задачи будет окончательно иметь вид:

Определим градиент функции .

Задаем начальные значения и . Тогда )=6,8.

Первая итерация. Определим градиент функции в точке

Составим функцию . Находим, что точка максимума есть (1,5; 3,75). Применяя соотношение (*), получим

Запишем функцию

Максимум этой функции найдем из условия равенства нулю первой производной этой функции:

Так как , то возьмем максимальное допустимое значение , чтобы не выйти из области X. Тогда ), и .

Вторая итерация. Определим градиент функции в точке

Составим функцию . Находим, что точка максимума есть (4; 0). Применяя соотношение (*), получим

Запишем функцию

Максимум этой функции найдем из условия равенства нулю первой производной этой функции:

Тогда , и .

Ответ: Оптимальный план с точностью .

Задачи для закрепления материала:

Решить соответствующий вариант задачи методом градиентов, сделав две итерации.

Предприятие выпускает изделия двух видов, при изготовлении которых используется сырье 1 и 2. Известны запасы сырья , нормы его расхода на единицу изделия, оптовые цены за единицу изделия и себестоимость . Составить план выпуска изделий, дающий предприятию максимальную прибыль.

Вариант
											0,1
											0,2
											0,2
											0,1
											0,3
											0,2
											0,2
											0,3
											0,3
											0,3

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: