Линейное программирование (лп). Геометрическая интерпретация задачи лп.

Общий вид:

Задана ф

@ - любые знаки

Канонический вид:

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

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

Любое неотриц. решения системы наз-ся допустимы решение, из этих допустимых решений выбираем min(max) и оно наз-ся оптимальным решением. Оптимальное решение не обязательно единственное.

Суть ЛП: из множ-ва допустимых решений выбрать то, к-е обращает линейную форму минимум.

Задачу нахождения оптимальной ф-ции ЛП можно интерпретировать геометрически. Для этого все ограничения представляют в виде неравенств, тогда каждое нер-во в n-мерном пространстве определяет полупространство расположенное по одну сторону от плоскости, к-е записывается:

- полупространство

- плоскость

Геометрический смысл ЛП – отыскание в многоугольнике Ω точки, к-я наиболее (наименее) уклонена от z=0.

 

Нелинейное программирование (НП). Аналитические условия решения задач НП. Типы методов НП. Методы решения задач одномерной минимизации. Метод дихотомии. Метод золотого сечения. Методы решения задач многомерной оптимизации. Метод случайного поиска. Метод деформируемого многогранника Нелдера-Мида.

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

В краткой форме задачу н. п. можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0, где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

Решение задачи НП (глобальный макс или мин) может принадл либо границе, либо внутренней части допустимого множества. Задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при к-х достигается макс (или мин) данной ф-и. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейны; и целевая функция, и ограничения нелинейны.

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