Курсовая работа: Сравнительный анализ методов оптимизации

Таким образом, к предложенному объему были применены оба метода решения задачи условной оптимизации. Результат рабочей программы представлен на рисунке 21, а листинг - в приложении Г.

Рисунок 21 - Условная оптимизация

4. Линейное программирование

Если целевая функция и все ограничения в задаче оптимизации являются линейными функциями, то такая задача носит название линейного программирования. В общем случае она имеет вид:

Если в общей модели присутствуют ограничения 3-х видов, то задачи, в которых есть только ограничения первого вида, не считая ограничений на знаки переменных, называются задачами распределительного типа.

Они широко распространены, поэтому будут подробно рассматриваться в рамках данного курсового проекта.

Понятно, что ограничения определяют область допустимых значений переменных, поэтому любое x из этой области являются допустимым решением, а x* - оптимальное решение, если:

Те ограничения, которые принимают вид равенства, называются активными ограничениями; соответствующий этому ограничению ресурс называется дефицитным.

Стандартная форма записи задачи линейного программирования имеет вид:

Система уравнений является базисной, то есть ранг матрицы равняется L-числу строк. Понятно, что L <N, где N - число переменных. Если же L =N, то при условии базисности допустимая область превращается в точку.

Исходная задача линейного программирования млжет быть сформулирована так, что ограничения имеют вид равенств. Можно показать, что от формы записи в виде равенств можно перейти к форме записи в виде неравенств.

Рассмотрим ограничения:

.

В базисной системе число неизвестных больше, чем число переменных. Следовательно, любые L переменных могут быть выражены через оставшиеся N - L свободные переменные. При этом такая система имеет единственное решение из-за базисности системы. Выбор свободных и базисных переменных произволен.

Запишем базисную систему в виде:

Поскольку Rang (AБ) = L, то можно сказать, что матрица  существует.

Тогда

, а  

является решением матричного уравнения  при любых .

Если , где  - N-мерный ноль, то полученное решение называется допустимым. Если при этом , т.е. , то решение называется базисным. Если, к тому же, , то решение называется допустимым базисным.

Если множество  не пусто, то область допустимых значений выпукла, и базисные решения существуют.

Также можно показать, что допустимое базисное решение является крайней точкой .

Если  замкнута, то число крайних точек ограничено.

Оно не превышает

.

Целевая функция достигает своего максимума в крайней точке.

Если же max достигается в нескольких крайних точках, то значение функции в этих точках одинаково. Такое же значение функция принимает во всех точках выпуклой и линейной комбинации этих крайних точек.

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

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

Если в задаче N переменных и L ограничений (), то целевая функция имеет вид:

Разделим Г на 2 части: Г (ГБГS). Тогда целевая функция будет выглядеть как:

В начальной допустимой базисной точке, как известно, YS=0. Следовательно,

Идея симплекс-метода заключается в том, что при переходе к новому допустимому базисному решению второе слагаемое должно быть положительным. Среди положительных выбирается наибольшее. В скалярном виде:

.

Метод выбора столбца, вводимого в базис и выбора строки переменной, выводимой из базиса, сведем в так называемую симплекс-таблицу.

Рассмотрим следующую задачу:

Параметр k в этом случае - подбираемый коэффициент, величина которого оказалась: k=7.

Рассмотрим геометрический способ решения задачи линейного программирования. Запишем для данного случая:

Тогда на рисунке можно увидеть, что область допустимых значений, ограниченная указанными прямыми, принимает вид пятиугольника:

Оптимальное решение соответствует прямой, параллельной fнач. и проходящей через самую дальнюю от fнач. точку допустимого множества. Из графика видно, что оптимальная точка x* (1.8, 1.14375) находится на пересечении g1 (x1) и g2 (x2). Значение функции в этой точке: f (x*) =15.375.

Для решения данной задачи с помощью симплекс-таблиц перепишем исходную систему в следующем виде:

Тогда симплекс-таблица на 0-й итерации примет вид:

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9