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

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

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

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

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

По предмету:

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

На тему:

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

г. Талдыкорган 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 т.е. следующая таблица:

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 обозначим ресурсы 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. Составляем таблицу и определяем все неотрицательные базисные решения системы.

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

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

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

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

2. Находим получаемый продукт.

Х1= 6*0+8*0+4*0=0

Х2=240*0+200*0+160*0=0

У1=3*00,4*00,6=0

У2=5*00,5*00,5=0

У3=8*00,6*00,4=0

F1=0+0+0=0

Х1= 6*0+8*325/2+4*0=1300

Х2=240*0+200*325/2+160*0=32500

У1=3*13000,4*325000,6=26904,728

У2=5*13000,5*325000,5=32500

У3=8*13000,6*325000,4=37688,542

F2=26904,728 +32500 +37688,542 = 97093,27

Х1= 6*650/3+8*0+4*0=1300

Х2=240*650/3+200*0+160*0=52000

У1=3*13000,4*520000,6=35699,794

У2=5*13000,5*520000,5=41109,610

У3=8*13000,6*520000,4=45483,862

F3= 35699,794+ 41109,610+ 45483,862= 122263,266

Х1= 6*0+8*0+4*325=1300

Х2=240*0+200*0+160*325=52000

У1=3*13000,4*520000,6=35699,794

У2=5*13000,5*520000,5=41109,610

У3=8*13000,6*520000,4=45483,862

F3= 35699,794+ 41109,610+ 45483,862= 122263,266

F1 < F2

F2 < F3

F3 = F4

Ответ: Fmax= 122263,266