Контрольные вопросы
В чем суть классического подхода к решению задач нахождения экстремума функций одной переменной?
Сформулировать общую схему нахождения экстремума функций одной переменной при помощи численных методов.
Методы равномерного и поразрядного приближения, в чем их суть?
Метод квадратичной интерполяции. Применение этого метода к решению задач нахождения экстремума функций одной переменной.
Метод золотого сечения. Постановка задачи.
Сравнить методы одномерной оптимизации.
Сформулировать общую схему нахождения экстремума функций многих переменных при помощи численных методов.
Метод координатного спуска и его реализация для функций многих переменных.
Метод наискорейшего координатного спуска, в чем его суть?
Содержание лабораторной работы «Численные методы решения экстремальных задач
1. Составить, отладить и протестировать программу для нахождения экстремума функций одной переменной на контрольном примере одним из следующих методов:
поразрядного приближения;
дихотомии;
квадратичной интерполяции;
золотого сечения.
2. Составить, отладить и протестировать программу для нахождения экстремума функций многих переменных на контрольном примере методом координатного спуска, для каждой переменной применяя методы, описанные в задании 1 данной лабораторной работы.
3. Составить, отладить и протестировать программу для нахождения экстремума функций многих переменных на контрольном примере методом наискорейшего спуска.
4. Записать в отчет название и цель работы, постановку задачи, текст программ и ответы.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Постановка задачи. Графический метод
Рассмотрим сначала несколько задач, которые привели к развитию целой отрасли математики – линейного программирования. Разумеется, в реальных задачах количество неизвестных и ограничений гораздо больше, но для понимания сути задачи и методов ее решения нам будет достаточно рассмотреть модельные ситуации с небольшим количеством неизвестных.
Пример 1 (транспортная задача)
На две товарные станции привезли по 30 комплектов мебели. Мебель необходимо развести по трем магазинам (по 20 комплектов в каждый). Известна стоимость перевозок с каждой станции в каждый магазин:
Магазин 1Магазин 2Магазин 3Станция 1758Станция 2396Требуется составить оптимальный (с наименьшими затратами) план перевозок.
Математическая постановка задачи:
Пусть х1, х2,...,х6- количество комплектов, которые надо перевезти со станций в магазины. Учитывая ограничения, получим для xi0 систему:
Получили систему из четырех уравнений с шестью неизвестными, у которой бесконечно много решений. Среди них надо выбрать такое, на котором целевая функция: f=7х1 + 3х2 + 5х3 + 9х4 + 8х5 + 6х6 достигает минимума.
Пример 2 (расчет рациона)
Имеются две питательные смеси, про которые известно, сколько белков, жиров и углеводов содержит одна единица каждой из них:
ЖирыБелкиУглеводыЦена1-я смесь2215772-я смесь161196Каждая корова должна получать не меньше 200 единиц жиров, 130 единиц белков и 75 единиц углеводов. Требуется подешевле накормить коров с учетом этих данных.
Математическая постановка задачи:
Пусть надо дать корове 1-ой смеси х1 единиц, 2-ой смеси- х2 единиц. Тогда
Среди решений данной системы надо выбрать такое, на котором достигается минимум целевой функции f=7x1+6x2.
Пример 3 (распределение ресурсов)
Предприятие производит два вида продукции из двух видов сырья, причем известны запасы обоих видов сырья, расход сырья на каждый вид продукции и доход с одной единицы каждой продукции:
Сырье 1Сырье 2Доход1-я продукция1520702-я продукция151050Запасы сырья9080Требуется получить максимальную прибыль.
Математическая постановка задачи:
Обозначим через х1 и х2 планируемый выпуск первой и второй продукции. Тогда система ограничений будет иметь вид:
Среди решений данной системы требуется найти такое, на котором достигается максимум целевой функции f=70x1+50x2.
Сходство математической постановки всех трех задач в том, что имеется целевая функция, у которой надо найти максимум или минимум, имеется система ограничений. При этом как ограничения, так и целевая функция являются линейными. Кроме того, во всех задачах есть требование неотрицательности переменных величин xi. Поскольку методы математического анализа для поиска экстремумов функций нескольких переменных для линейных функций не работают, то была создана теория линейного программирования, ориентированная на данный класс задач.
Задача линейного программирования в общем виде:
Дана система ограничений: АХ В, X 0, где А - матрица, Х и В - столбцы (возможно, разной длины). Дана линейная целевая функция: f = (с, х). Требуется определить компоненты вектора X, удовлетворяющие системе ограничений, при которых данная целевая функция принимает минимальное значение.
Определения. Решение называется допустимым в задаче линейного программирования, если оно удовлетворяет условиям: АХ В, Х 0.
Если существует хоть одно допустимое решение, то задача называется допустимой.
Вектор Х, который дает минимум целевой функции среди всех допустимых решений, называется оптимальным решением.
Если существует оптимальное решение, то говорят, что задача поставлена корректно.
Если в примере 2 умножить систему ограничений на -1, то вместо системы ограничений АХ В получим АХ В, т.е. получим задачу в общем виде.
В примере 1 вместо АХ В имеем АХ = В. Это частный случай.
В примере 3 вместо f = 70х1 + 50х2 -> max ищем f1 = -70х1 - 50х2 -> min.
(но не надо забывать в ответе поменять знак!)
Любую задачу линейного программирования можно свести к КАНОНИЧЕСКОМУ ВИДУ:
АХ = В, Х 0, f = (с, х) -> min.
Но при решении задачи нельзя механически заменять знак неравенства на знак равенства, т.к. после этого система, скорее всего, не будет иметь решения.
В задачах нет ограничения на количество неизвестных. За счет введения дополнительных неизвестных исходную систему неравенств легко свести к эквивалентной ей системе уравнений.
Например, задачу 3 можно так свести к канонической форме:
f = 70х1 + 50х2 -> max f1 = -70х1 - 50х2 -> min
А в примере 2 достаточно провести следующие преобразования:
и f = 7х1 + 6х2 -> min
Решим эти задачи двумя способами: пример 1- аналитически, пример 3- графически.
В задаче 1 имеем 4 уравнения и 6 неизвестных, т.е. 2 степени свободы. Чтобы описать пространство решений, надо выбрать 2 независимые (свободные) переменные и через них выразить остальные переменные. Например, в качестве СВОБОДНЫХ возьмем х1 и х4. Неизвестные х2, х3, х5, х6 называются БАЗИСНЫМИ. Выразим их через свободные переменные и подставим все в целевую функцию:
х2= 20 -х1; х3= 20 – х4; х5= 10 - х1 + х4; х6= 10 + х1 – х4;
f = 7х1 + 3(20 - х1) + 5(20-х4) + 9х4 + 8(10 - х1 +х4) + 6(10+ х1 – х4) = 300 + 2х1 + 6х4.
Таким образом, мы нашли общее решение системы уравнений. При этом х1 и х4- свободные переменные, они могут принимать любые неотрицательные значения. Среди всех решений надо выбрать оптимальное. Т.к. f =300 + 2х1 + 6х3, и должно быть хi0, то ясно, что в оптимальном решении х1=0,х4=0. Тогда х2 = 20, х3 =20, х5 = 10, х6 = 10, f=300.
|
