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