48798 (Решение задач нелинейного программирования)

Министерство науки и образования Республики Казахстан

Талдыкорганский политехнический колледж

Курсовая работа

По предмету:

«Моделирование производственных и экономических процессов»

На тему:

«Решение задач нелинейного программирования»

г. Талдыкорган 2007 г.

Введение

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x₁, x₂,…, x_n) при ограничениях g_i (x₁, x₂,…, x_n) b_i, где g_i – функция, описывающая ограничения, а b_i – действительное число, i = 1,…, m. Функция f называется функцией цели (целевой функцией).

В общем, виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x₁, x₂, …, x_n) при условии, что ее переменные удовлетворяют соотношениям:

где f и g – некоторые известные функции n переменных, а b_i – заданные числа.

В результате решения задачи будет определена точка Х^*= (x₁^*, x₂^*, …, x_n^*), координаты которой удовлетворяют соотношениям и такая, что для всякой другой точки Х= (x₁, x₂, …, x_n), удовлетворяющей условиям, выполняется неравенство f (x₁^*, x₂^*, …, x_n^*) ≥ f (x₁, x₂, …, x_n) [f (x₁^*, x₂^*, …, x_n^*) ≥ f (x₁, x₂, …, x_n)].

Если f и g_i – линейные функции, то задача является задачей линейного программирования.

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

В евклидовом пространстве Е_n система ограничений определяет область решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Если определена область допустимых решений, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наименьшего) уровня: f (x₁, x₂, …, x_n) = h. Указанная точка может находиться как на границе области допустимых решений, так и внутри неё.

Процесс нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации включает следующие этапы:

1. Находят область допустимых решений задачи, определяемую соотношениями (если она пуста, то задача не имеет решения).

2. Строят гиперповерхность f (x₁, x₂, …, x_n) = 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;

X₁ – трудовые ресурсы в человеко-днях;

Х₂ – денежно-материальные средства, в тенге;

У_i – получаемый продукт

Х₁ = а₁х₁ + b₁x₂ + c₁x₃

Х₂ = а₂х₁ + b₂x₂ + c₂x₃

Найти все неотрицательные базисные решения и определить оптимальный план F = y₁ + y₂ + y₃.

Известно, что продукт для производства j – того вида затрачивается a_ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10

Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.

2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица:

3. По столбцу c – на 3 строке находим с₁=6, α₁=0,6

4. По столбцу d – на 5 строке определяем с₂=5, α₂=0,5

5. По столбцу e – по 4 строке установим, что с₃=8, α₃=0,4.

6. И наконец по столбцу f – в 1 строке найдем Т_{чел.дней} =1000, П_тенге = 280000

Для производства имеются трудовые ресурсы Т_{чел.дней} и денежно-материальные средства П_тенге.

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

Второй этап – составление математической модели задачи

1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:

Через Х₁ обозначим ресурсы I вида.

Через Х₂ обозначим ресурсы II вида.

2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.

8Х₁ + 4Х₂ + 6Х₃ ≤ 1000

240Х₁+ 200Х₂ + 160Х₃ ≤ 280000

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

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

Для решения задачи линейного программирования применяется симплекс – метод.

Третий этап – выбор метода решения полученной математической задачи

Решение

1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:

8Х₁ + 4Х₂ + 6Х₃ + Х₄= 1000

240Х₁+ 200Х₂ + 160Х₃ + Х₅= 280000

2. Составляем таблицу и определяем все неотрицательные базисные решения системы.

А) Нашли некоторое неотрицательное базисное решение: Х₄ =1300, Х₅ = 190000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₂. Соответственно вся строка делится на 8, а все остальные элементы находятся по правилу прямоугольника.

Б) Нашли некоторое неотрицательное базисное решение: Х₂ =325/2, Х₅ =157500. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₁. Соответственно вся строка делится на 3/4, а все остальные элементы находятся по правилу прямоугольника.

В) Нашли некоторое неотрицательное базисное решение: Х₁ =650/3, Х₅ =138000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₃. Соответственно вся строка делится на 2/3, а все остальные элементы находятся по правилу прямоугольника.

Г) Нашли некоторое неотрицательное базисное решение: Х₅ =138000, Х₃ =325. Найдены все неотрицательные базисные решения.