Автор: Пользователь скрыл имя, 09 Июня 2013 в 15:57, курсовая работа
В качестве проектных параметров могут быть, в частности, значения линейных размеров объекта, массы, температуры и т.п. число n проектных параметров x1,x2,…,xn характеризует размерность ( и степень сложности) задачи оптимизации.
Выбор оптимального решения или сравнение двух альтернативных решений проводится с помощью некоторой зависимой величины (функции), определяемой проектными параметрами.
Введение………………………………………………………………………………………4
1. Основные понятия………………………………………………………………………….5
1.1 Определения……………………………………………………………………………...5
1.2 Задачи оптимизации……………………………………………………………………..6
2. Одномерная оптимизация…………………………………………………………………7
2.1 Задачи па экстремум……………………………………………………………………..7
2.2 Методы поиска…………………………………………………………………………...8
2.3 Метод золотого сечения…………………………………………………………………8
2.4 Метод Ньютона………………………………………………………………………….12
3. Многомерные задачи оптимизации……………………………………………………...14
3.1 Минимум функции нескольких переменных………………………………………….14
3.2 Метод покоординатного спуска……………………………………………………….15
3.3 Метод градиентного спуска……………………………………………………………16
4. Задачи с ограничениями…………………………………………………………………..18
4.1 Линейное Программирование………………………………………………………….18
4.2 Геометрический метод…………………………………………………………………..18
4.3 Задача о ресурсах……………………………………………………………………….20
5. Заключение……….............................................................................................................24
Список литературы…………………………………………………………………………..25
Областью решений системы является пересечение конечного числа полуплоскостей, описываемых каждым отдельным неравенством вида (4.4). Это пересечение представляет собой многоугольную область . Она может быть как ограниченной, так и неограниченной и даже пустой.
Область решений обладает важным свойством выпуклости. Область называется выпуклой, если произвольные две ее точки можно соединить отрезком, целиком принадлежащим данной области.
Опорной прямой называется прямая, которая имеет с областью по крайней мере одну общую точку, при этом вся область расположена но одну сторону от этой прямой.
Аналогично можно дать геометрическую интерпретацию системы неравенств с тремя переменными. В этом случае каждое неравенство описывает полупространство, а вся система — пересечение полупространств, т. е. многогранник, который также обладает свойством выпуклости. Здесь опорная плоскость проходит через вершину, ребро или грань многогранной области.
Основываясь на введенных понятиях, рассмотрим геометрический метод решения задачи линейного программирования. Пусть заданы линейная целевая функция двух независимых переменных, а также некоторая совместная система линейных неравенств, описывающих область решений . Требуется среди допустимых решений найти такое, при котором линейная целевая функция принимает наименьшее значение.
Положим функцию равной некоторому постоянному значению . Это значение достигается в точках прямой, удовлетворяющих уравнению
При параллельном переносе этой прямой в положительном направлении вектора нормали линейная функция будет возрастать, а при переносе прямой в противоположном направлении — убывать.
Действительно, пусть при параллельном переносе точка , принадлежащая прямой (4.5), переходит в точку , принадлежащую новой прямой, т. е. параллельный перенос производится в направлении вектора . Тогда уравнение новой прямой будет иметь вид
Поскольку
Если вектор сонаправлен с вектором , то и , а если направлен противоположно, то .
Предположим, что прямая, записанная в виде (4.5), при параллельном переносе в положительном направлении вектора первый раз встретится с областью допустимых решений в некоторой ее вершине, при этом значение целевой функции равно , и прямая становится опорной. Тогда значение будет минимальным, поскольку дальнейшее движение прямой в том же направлении приведет к увеличению значения .
Если в задаче оптимизации нас интересует максимальное значение целевой функции, то параллельный перенос прямой (4.5) осуществляется в направлении, противоположном , пока она не станет опорной. Тогда вершина многоугольника, через которую проходит опорная прямая, соответствовать максимуму функции . При дальнейшем переносе прямой целевая функция будет убывать.
Таким образом, оптимизация линейной целевой функции на многоугольнике допустимых решений происходит в точках пересечения этого многоугольника с опорными прямыми, соответствующими данной целевой функции. При этом пересечение может быть в одной точке (в вершине многоугольника) либо в бесконечном множестве точек (на ребре многоугольника). В последнем случае имеется бесконечное множество оптимальных решений.
В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м2 стекла, 160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовить два наименования изделий: А и Б. Цена одного изделия А -1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м2 стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1,2 тыс. для его изготовления необходимо 5 кг металла, 1 м2 стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.
Сначала сформулируем задачу математически. Обозначим через и количество изделий А и Б, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени зададим в виде ограничений-неравенств:
Полная стоимость
Таким образом, мы имеем задачу линейного программирования, которая состоит в определении оптимальных значений проектных параметров являющихся целыми неотрицательными числами, удовлетворяющих линейным неравенствам (4.6) и дающих максимальное значение линейной целевой функции (4.7).
Вид сформулированной задачи не является каноническим, поскольку условия (4.6) имеют вид неравенств, а не уравнений. Как уже отмечалось выше, такая задача может быть сведена к канонической путем введения дополнительных переменных по количеству ограничений- неравенств (4.6). При этом выбирают эти переменные такими, чтобы при их прибавлении к левым частям соотношений (4.6) неравенства превращались в равенства. Тогда ограничения примут вид
При этом очевидно, что . Заметим, что введение дополнительных неизвестных не повлияло на вид целевой функции (4.7), которая зависит только от параметров . Фактически будут указывать остатки ресурсов, не использованные в производстве. Здесь мы имеем задачу максимизации, т. е. нахождения максимума целевой функции. Если функцию (4.7) взять со знаком минус и принять целевую функцию в виде
то получим задачу минимизации для этой целевой функции.
Примем переменные в качестве базисных и выразим их через свободные переменные из уравнений (4.8). Получим
В качестве опорного решения возьмем такое, которое соответствует пулевым значениям свободных параметров:
Этому решению соответствует нулевое значение целевой функции (4.9):
Исследуя полученное решение, отмечаем, что оно не является оптимальным, поскольку значение целевой функции (4.9) может быть уменьшено по сравнению с (4.11) путем увеличения свободных параметров.
Положим и будем увеличивать переменную до тех пор, пока базисные переменные остаются положительными. Из (4.10) следует, что можно увеличить до значения , поскольку при большем его значении переменная станет отрицательной (отношение 100/(-2) является наименьшим по модулю среди отношений 300/(-4),100/(-2),160/(-2)).
Таким образом, полагая , , получаем новое опорное решение (значения переменных найдем по формулам (4.10)):
Значение целевой функции (4.9) при этом будет равно
Новое решение (4.12), следовательно, лучше, поскольку значение целевой функции уменьшилось по сравнению с (4.11).
Следующий шаг начнем с выбора нового базиса. Примем ненулевые переменные в (4.12) в качестве базисных, а нулевые переменные в качестве свободных. Из системы (4.8) найдем
Выражение для целевой функций
запишем через свободные
Отсюда следует, что значение целевой функции по сравнению с (4.13) можно уменьшить за счет увеличения поскольку коэффициент при этой переменной в (4.15) отрицательный. При этом увеличение недопустимо, поскольку это привело бы к возрастанию целевой функции; поэтому положим .
Максимальное значение переменной определяется соотношениями (4.14). Быстрее всех нулевого значения достигнет переменная при . Дальнейшее увеличение поэтому невозможно. Следовательно, получаем новое опорное решение, соответствующее значениям , и определяемое соотношениями (4.14):
При этом значение целевой функции (4.15) равно
Покажем, что полученное решение является оптимальным. для проведения следующего шага ненулевые переменные в (4.16), т. е. , нужно принять в качестве базисных, а нулевые переменные - в качестве свободных переменных. В этом случае целевую функцию можно записать в виде
Поскольку коэффициенты при положительные, то при увеличении этих параметров целевая функция возрастает. Следовательно, минимальное значение целевой функции соответствует нулевым значениям параметров , и полученное решение является оптимальным.
Таким образом, ответ на поставленную задачу об использовании ресурсов следующий: для получения максимальной суммарной стоимости продукции при заданных ресурсах необходимо запланировать изготовление изделий А в количестве 35 штук и изделий Б в количестве 30 штук. Суммарная стоимость продукции равна 71 тыс, р. При этом все ресурсы стекла и рабочего времени будут использованы, а металла останется 10 кг.
Заключение
При написании курсовой работы был доказан целый ряд важнейших теорем, были изучены основные понятия и определения, методы решения задач по методам оптимизации. Изложенные в курсовой работе методы решений дают нам понять, существует достаточное количество способов решений задач. В каждом методе показывается полноценный ход решения. Каждый из методов имеет свою специфику и предназначен для определенного применения в том или ином случае.