Методы оптимизации. Алгоритмы. Линейное программирование - Контрольная работа

Оптимизируемую функцию называют целевой функцией, функцией цели или критерием задачи (критерием эффективности).Познакомимся с понятием выпуклого множества, дадим определение выпуклой функции, рассмотрим некоторые свойства выпуклых функций, приведем критерии выпуклости функций.Определение 2.1. Выпуклой комбинацией двух точек называется точка.Определение 2.4. Пусть функция определена на выпуклом множестве X . Теорема 2.3.Определение 3.1. Задачей линейного программирования называют задачу оптимизации линейной функции в области, задаваемой линейными ограничениями-неравенствами и (или) линейными ограничениями-равенствами. Говорят, что задача ЛП имеет каноническую форму, если все ограничения являются равенствами и все входящие в задачу переменные ограничены по знаку: , , (3.2).Область допустимых решений (ОДР) задачи линейного программирования X есть многогранное замкнутое выпуклое множество. Доказательство основывается на том, что, во-первых, все предельные точки принадлежат этому множеству, и, во-вторых, выпуклая комбинация любых двух точек из этого множества так же принадлежит ему. Базисным решением системы называется точка , если она является решением этой системы, и ее ненулевым координатам соответствуют линейно-независимые столбцы матрицы . Координаты базисного решения можно всегда разбить на 2 группы так, что в одной группе все координаты будут равны нулю, а координатам другой группы будут отвечать линейно-независимые столбцы матрицы .Симплексный метод предназначен для решения задач линейного программирования. Его реализация предполагает поиск оптимального решения среди опорных решений (вершин). Поэтому при изложении метода остановимся на способе описания опорного решения и соответствующем ему представлении системы уравнений в виде симплексной таблице.Если ограничения имеют вид равенств в жордановой форме с неотрицательными числами в правых частях или элементарно приводятся к такому виду эквивалентными преобразованиями, то построение начальной симплекс-таблицы не вызывает трудностей. Переменные, составляющие вектор , - это небазисные переменные, а переменные, составляющие вектор , - базисные.Определение 4.1. Парой симметричных двойственных задач называются задачи. Задачи (4.1), (4.2) являются взаимно двойственными задачами. Для построения двойственной задачи рекомендуется выполнить действия: 1) Если в исходной задаче требуется максимизировать целевую функцию, то все ограничения-неравенства преобразовать к виду « ». Задача 4.1 Переменные, соответствующие ограничениям задачи 4.1. В случае разрешимости оптимальные значения целевых функций этих задач равны.5.1 Задача условной оптимизации с ограничениями-равенствами (задача Лагранжа). Построим функцию, которую назовем функцией Лагранжа, , (5.2) переменные , называют множителями Лагранжа.Рассмотрим задачу, в которой ограничения являются нестрогими неравенствами. Функция Лагранжа для этой задачи: , где переменные , - множители Лагранжа. Точка , где , называется седловой точкой функции Лагранжа, если в этой точке выполняются неравенства для всех . Для седловой точки выполняется неравенство , или для любого .Определение 5.2. Задачей выпуклого программирования называется задача минимизации выпуклой функции на выпуклом множестве, или преобразуемая в таковую эквивалентными преобразованиями. Очевидно, что задача (5.3) является задачей выпуклого программирования при условии, что все входящие в нее функции - выпуклые. Но, несмотря на это, функция Лагранжа не имеет седловую точку.Обратите внимание: ограничения на знак переменных в постановке задачи не выделены в отдельные ограничения, и поэтому они могут быть в задаче (тогда они рассматриваются наравне с остальными ограничениями), а могут отсутствовать. Общая схема метода возможных направлений.