Сравнительный анализ методов оптимизации (стр. 6 из 7)
Выразим из формулы общей площади параметр h2:
.Подставим полученное выражение в формулу объема, получим:
Обозначим r=3 и h=1. Затем следует провести двумерную оптимизацию. Ниже на рисунке 21 приведена рабочая форма программы, реализующая двумерную оптимизацию для первого случая и трехмерную - для штрафных функций по методу координатного спуска.
Для указанного случая V=260.799603505204 при r*=4.06250000000002 и h*=0.975.
Случай со штрафными функциями в общем виде можно записать как:
где с -площадь.
Таким образом, следует провести трехмерную оптимизацию для следующей функции:
Изменяемыми параметрами в данном случае являлись r- радиус цилиндра и сферы, h- высота сегмента и h2 - высота цилиндра.
Для второго случая V=260.778443852174 при r*=4.44999999999999, h*=1.025 и h2*=4.05.
Таким образом, к предложенному объему были применены оба метода решения задачи условной оптимизации. Результат рабочей программы представлен на рисунке 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-й итерации примет вид:
| Значение | y1 | y2 | y3 | y4 | y5 | |
| y3 | 8 | 1 | 4 | 1 | 0 | 0 |
| y4 | 12 | 6 | 1 | 0 | 1 | 0 |
| y5 | 7 | 2 | 3 | 0 | 0 | 1 |
| -f | 0 | 6 | 4 | 0 | 0 | 0 |
Суть симплекс-метода в том, что происходит замена одной переменной в базисе так, чтобы значение целевой функции возрастало. Поэтому в качестве переменной для ввода в базис выбирается та из yS, которой соответствует наибольшее положительное значение симплекс-разности.
Под симплекс-разностью понимаются элементы, стоящие в строке -f на пересечении с соответствующей переменной yi. В данном случае наибольшую положительную симплекс-разность, равную 6, имеет переменная y1.
Далее выбираем ту переменную, которая выводится из базиса. Выбирается та переменная из базиса, у которой элемент на пересечении строки базисной переменной или столбца вводимой в базис переменной (y1) положителен.
Для данного случая это переменные y3,y4,y5.
Проведем сравнение отношений элемента столбца y1 к соответствующему элементу столбца значений:
- наибольшее отношение.Следовательно, из базиса выводится переменная y4.