Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
?граничениях.
- Основные понятия теории оптимизации
Говорят, что функция F(x) имеет в т. х*(х1,х2, … , хn) локальный максимум (минимум), если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F(x) ? F(x*) (F(x) ? F(x*)).
Необходимое условие экстремума: чтобы F(x) имела в т. х* экстремум необходимо, чтобы ?F(x*)/?xj = 0, .
Достаточное условие экстремума: если F(x) в т. х* имеет ?F(x*)/?xj = 0, , то чтобы в этой точке F(x) имела экстремум достаточно, чтобы квадратичная форма
была положительно (минимум) или отрицательно (максимум) определена.
Очевидно, что точки локального экстремума могут не давать наибольшего или наименьшего значений функции в некоторой области, кроме того, их может быть несколько. Большое значение в этой связи приобретает понятие выпуклости множества допустимых значений и выпуклости (вогнутости) функции.
Множество S называется выпуклым, если для любых двух точек этого множества оно содержит и отрезок, соединяющий эти точки:
Функция F(x), определенная на выпуклом множестве S, выпукла, если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:
Функция F(x), определенная на выпуклом множестве S, вогнута, если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:
Теорема 1: пересечение выпуклых множеств является выпуклым множеством.
Теорема 2: сумма выпуклых функций является выпуклой функцией, сумма вогнутых функций - вогнутой функцией.
Теорема 3 (основное свойство выпуклых задач):
Всякий локальный оптимум является глобальным.
Теорема Вейерштрасса:
Непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (минимума) по крайней мере в одной точке этого множества.
Из сказанного можно определить общий принцип решения задач оптимизации: максимум (минимум) F(x) при х, принадлежащих замкнутому допустимому множеству, если оно существует, является либо точкой экстремума, либо граничной точкой допустимого множества, либо и тем и другим одновременно.
При численных расчетах часто необходимо использовать еще два важных понятия.
Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции grad F(x) = (?F/?x1, … ,?F/?xn). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.
Линией уровня (или линией равного значения) функции F(x) называют геометрическое место точек, координаты которых удовлетворяют уравнению F(x) = Const. Линия уровня и вектор градиент в каждой точке взаимно перпендикулярны.
- Постановка ЗЛП, различные формы записи. Примеры экономических задач
Линейное программирование - раздел математического программирования, рассматривающий задачи оптимизации линейных функций многих переменных при линейных ограничениях на область изменения переменных.
Особенностью ЗЛП является то, что линейная целевая функция не имеет экстремума и достигает наибольшего или наименьшего значения на границе допустимой области.
Рассмотрим постановку ЗЛП на примере задачи и наилучшем использовании ресурсов. Имеется m видов ресурсов в ограниченном количестве b = (b1, b2, … , bm). Ресурсы используются предприятием для выпуска n видов продукции. Известна экономическая выгода производства каждого вида продукции, исчисляемая, например, ценой реализации С = (С1, С2, … , Сn). Известны технологические коэффициенты аij, соответствующие количеству i-го вида ресурса, необходимого для производства единицы j -го вида продукции - А = ( аij ). Необходимо составить план производства х = (х1,х2, … , хn), приносящий предприятию максимальную прибыль.
В общем виде математическую модель задачи (ЗЛП) можно записать следующим образом:
F(x) = C1x1 + C2x2 + … + Cnxn > max
a11x1 + a12x2 + … + a1nxn ? b1, xj ? 0, j= 21x1 + a22x2 + … + a2nxn ? b2,
… … … … m1x1 + am2x2 + … + amnxn ? bm.
Рассмотрим задачу о диете. Необходимо составить диету (рацион), содержащую определенные питательные вещества. Имеем n видов продуктов, каждый из которых сожержит необходимые m видов питательных веществ. Единица j-го продукта содержит аij единиц i-го питательного вещества. Для нормальной жизнедеятельности необходимо не менее bi единиц i-го вещества. Известна стоимость единицы каждого вида продукта С = (С1, С2, … , Сn). Необходимо составить диету минимальной стоимости.
Математическая модель задачи примет вид:
F(x) = C1x1 + C2x2 + … + Cnxn > min 11x1 + a12x2 + … + a1nxn ? b1, xj ? 0, j= 21x1 + a22x2 + … + a2nxn ? b2,
… … … … m1x1 + am2x2 + … + amnxn ? bm.
Здесь хj - количество j - го продукта в рационе.
В матричной форме общая ЗЛП выглядит так:
F(x) = CTx > max (min) ? (=,?) B ; x ? 0.
Кроме того, для записи ЗЛП можно использовать знак суммы:
F(x) = > max (min)
, .
&