Выразим из формулы общей площади параметр 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 - Условная оптимизация
Если целевая функция и все ограничения в задаче оптимизации являются линейными функциями, то такая задача носит название линейного программирования. В общем случае она имеет вид:
Если в общей модели присутствуют ограничения 3-х видов, то задачи, в которых есть только ограничения первого вида, не считая ограничений на знаки переменных, называются задачами распределительного типа.
Они широко распространены, поэтому будут подробно рассматриваться в рамках данного курсового проекта.
Понятно, что ограничения определяют область допустимых значений переменных, поэтому любое x из этой области являются допустимым решением, а x* - оптимальное решение, если:
Те ограничения, которые принимают вид равенства, называются активными ограничениями; соответствующий этому ограничению ресурс называется дефицитным.
Стандартная форма записи задачи линейного программирования имеет вид:
Система уравнений является базисной, то есть ранг матрицы равняется L-числу строк. Понятно, что L<N, где N - число переменных. Если же L =N, то при условии базисности допустимая область превращается в точку.
Исходная задача линейного программирования млжет быть сформулирована так, что ограничения имеют вид равенств. Можно показать, что от формы записи в виде равенств можно перейти к форме записи в виде неравенств.
Рассмотрим ограничения:
В базисной системе число неизвестных больше, чем число переменных. Следовательно, любые L переменных могут быть выражены через оставшиеся N - L свободные переменные. При этом такая система имеет единственное решение из-за базисности системы. Выбор свободных и базисных переменных произволен.
Запишем базисную систему в виде:
Поскольку Rang (AБ) = L, то можно сказать, что матрица
Тогда
является решением матричного уравнения
Если
Если множество
Также можно показать, что допустимое базисное решение является крайней точкой
Если
Оно не превышает
Целевая функция достигает своего максимума в крайней точке.
Если же 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.