Решение задач нелинейного программирования
Министерство науки и образования Республики Казахстан Талдыкорганский политехнический колледж Курсовая работа По предмету: «Моделирование производственных и экономических процессов» На тему: «Решение задач нелинейного программирования» г. Талдыкорган 2007 г. Введение Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x1, x2,…, xn) при ограничениях gi (x1, x2,…, xn) bi, где gi - функция, описывающая ограничения, а bi - действительное число, i = 1,…, m. Функция f называется функцией цели (целевой функцией). В общем, виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x1, x2, …, xn) при условии, что ее переменные удовлетворяют соотношениям: где f и g - некоторые известные функции n переменных, а bi - заданные числа. В результате решения задачи будет определена точка Х*= (x1*, x2*, …, xn*), координаты которой удовлетворяют соотношениям и такая, что для всякой другой точки Х= (x1, x2, …, xn), удовлетворяющей условиям, выполняется неравенство f (x1*, x2*, …, xn*) ? f (x1, x2, …, xn) [f (x1*, x2*, …, xn*) ? f (x1, x2, …, xn)]. Если f и gi - линейные функции, то задача является задачей линейного программирования. Соотношения образуют систему ограничений и включают в себя условия не отрицательности переменных, если такие условия имеются. Условия неотрицательности переменных могут быть заданы и непосредственно. В евклидовом пространстве Еn система ограничений определяет область решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой. Если определена область допустимых решений, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наименьшего) уровня: f (x1, x2, …, xn) = h. Указанная точка может находиться как на границе области допустимых решений, так и внутри неё. Процесс нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации включает следующие этапы: 1. Находят область допустимых решений задачи, определяемую соотношениями (если она пуста, то задача не имеет решения). 2. Строят гиперповерхность f (x1, x2, …, xn) = h. 3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функций сверху (внизу) на множестве допустимых решений. 4. Находят точку области допустимых решений, через которую проходит гиперповерхности наивысшего (наинизшего) уровня, и определяют в ней значение функции. Или приводят задачу нелинейного программирования к задаче линейного программирования и решают нижеизложенными способами. Задача является задачей линейного программирования, а следовательно, ее решение можно найти известными методами: 1) графический; 2) табличный (прямой, простой) симплекс - метод; 3) метод искусственного базиса; 4) модифицированный симплекс - метод; 5) двойственный симплекс - метод. 1. Табличный симплекс-метод Для его применения необходимо, чтобы знаки в ограничениях были вида «меньше либо равно», а компоненты вектора b - положительны. Алгоритм решения сводится к следующему: 1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам. 2. Если в исходной системе ограничений присутствовали знаки» равно "или" больше либо равно», то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума. 3. Формируется симплекс - таблица. 4. Рассчитываются симплекс - разности. 5. Принимается решение об окончании либо продолжении счёта. 6. При необходимости выполняются итерации. 7. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана - Гаусса или каким-нибудь другим способом. 2. Метод искусственного базиса Данный метод решения применяется при наличии в ограничении знаков «равно» больше либо равно» меньше либо равно и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами, а в задачи минимизации - с положительными. Таким образом, из исходной задачи получается новая задача. Если в оптимальном решении - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима. 3. Модифицированный симплекс-метод В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы. В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m. В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс - разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана - Гаусса. Особенности заключаются в наличии двух таблиц - основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул. Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи. Таким образом, процесс нахождения решения задачи нелинейного программирования включает следующие этапы: 1. Первоначальную задачу сводят к задаче линейного программирования. 2. Находят решение линейной задачи Используя соотношения, определяют оптимальный план исходной задачи и находят максимальное значение целевой функции нелинейной задачи. Первый этап: Получение задания к курсовой работе 1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра: 9 5 5 8 7 2 Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде: 9 5 5 8 7 2 а b c d e f из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а - том столбце в строке 9, b - том столбце в строке 5, c - том столбце в строке 5, d - том столбце в строке 8, e - том столбце в строке 7и f - том столбце в строке 2. По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания. В моем случае для цифры 9 соответствует вариант 9. На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами: где Сi и - постоянные величины, i = 1, 2, 3; X1 - трудовые ресурсы в человеко-днях; Х2 - денежно-материальные средства, в тенге; Уi - получаемый продукт Х1 = а1х1 + b1x2 + c1x3 Х2 = а2х1 + b2x2 + c2x3 Найти все неотрицательные базисные решения и определить оптимальный план F = y1 + y2 + y3. Известно, что продукт для производства j - того вида затрачивается aij единиц i - того ресурса. Эти затраты даются в таблицах 3.9.1. - 3.9.10 Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11. 2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица: |
Продукты ресурсы | 1 | 2 | 3 | | I | 8 | 4 | 6 | | II | 160 | 240 | 200 | | |
3. По столбцу c - на 3 строке находим с1=6, ?1=0,6 4. По столбцу d - на 5 строке определяем с2=5, ?2=0,5 5. По столбцу e - по 4 строке установим, что с3=8, ?3=0,4. 6. И наконец по столбцу f - в 1 строке найдем Тчел.дней =1000, Птенге = 280000 Для производства имеются трудовые ресурсы Тчел.дней и денежно-материальные средства Птенге. Требуется найти оптимальный план выпуска продукции, при котором выпускаемый продукт будет наибольшим. Второй этап - составление математической модели задачи 1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица: |
Продукты ресурсы | 1 | 2 | 3 | | | I | 8 | 4 | 6 | 1000 | | II | 160 | 240 | 200 | 280000 | | |
Через Х1 обозначим ресурсы I вида. Через Х2 обозначим ресурсы II вида. 2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений. 8Х1 + 4Х2 + 6Х3 ? 1000 240Х1+ 200Х2 + 160Х3 ? 280000 Таким образом, получили задачу нелинейного программирования. Такие задачи называются задачами нелинейного программирования. Решение задач нелинейного программирования осуществляется приведением их к задачам линейного программирования. Для решения задачи линейного программирования применяется симплекс - метод. Третий этап - выбор метода решения полученной математической задачи Решение 1. Для решения задач линейного программирования симплекс - методом задача приводиться к каноническому виду: 8Х1 + 4Х2 + 6Х3 + Х4= 1000 240Х1+ 200Х2 + 160Х3 + Х5= 280000 2. Составляем таблицу и определяем все неотрицательные базисные решения системы. |
Базисные переменные | Х1 | Х2 | Х3 | Х4 | Х5 | Свободный член | | Х4 | 8 | 4 | 6 | 1 | 0 | 1000 | | Х5 | 240 | 200 | 160 | 0 | 1 | 280000 | | |
Страницы: 1, 2
|