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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет информационных технологий и робототехники

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

КУРСОВОЙ ПРОЕКТ

по дисциплине: "Методы и алгоритмы принятия решений"

на тему: "Программное обеспечение для решения задач нелинейного и линейного программирования"

Выполнил: ст. гр. 107329 Назаров М.П.

Руководитель: ст. преподаватель

Михалевич А.П.

Минск - 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ЗАДАЧА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1 Постановка задачи нелинейного программирования

1.2 Определение стационарных точек и их типа

1.3 Построение линий уровней, трехмерного графика целевой функции и ограничения

1.4 Алгоритм решения задачи

1.5 Схема алгоритма

1.6 Описание программного обеспечения

1.7 Руководство пользователя

1.8 Результаты выполнения программы

1.9 Листинг

2. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Постановка задачи линейного программирования

2.2 Графическое решение задачи

2.3 Аналитическое решение задачи

2.4 Решение задачи с использованием процедуры "Поиск решения"

ВЫВОДЫ

СПИСОК ЛИТЕРАТУРЫ



ВВЕДЕНИЕ

линейное программирование функция графический

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

Линейное программирование - область математики, разрабатывающая теорию и численные методы нахождения экстремума линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования является симплекс-метод.

Нелинейное программирование - случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция. В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями. Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений, является метод модифицированной функции Лагранжа.

В ходе курсового проекта были изучены такие методы оптимизации, как метод модифицированной функции Лагранжа и симплекс-метод.



1. ЗАДАЧА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1 Постановка задачи нелинейного программирования

Минимизировать

при ограничениях

a1	b1	d1	a2	b2	d2
7	3	5	3	5	4

Условие окончания поиска ||?x|| <0,1.

1.2 Определение стационарных точек и их типа

Найдем стационарные точки функции .

Частные производные по x1 и x2 равны:

В стационарной точке обе эти производные равны 0. Приравнивая полученные выражения к 0, получаем систему линейных уравнений. C помощью MathCad 13 найдем решения этой системы уравнений:

Следовательно, система имеет единственное решение, а функция f(x) - единственную стационарную точку .

Для проверки, является ли стационарная точка максимумом или минимумом, найдём вторые производные функции:

Матрица Гессе для этой функции имеет вид:

Матрица Гессе определена положительно, следовательно точка А - точка экстремума, и так как , то это точка минимума.



1.3 Построение линий уровней, трехмерного графика целевой функции и ограничения

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

Для построения линий уровня функции были выбраны точки, координаты которых находятся в диапазонах ; . Результаты построения в Excel представлены на рисунке 1.1.

Рисунок 1.1 - Линии уровней функции f(x)

При условном форматировании точки, попадающие в различные диапазоны значений функции, были закрашены в различные цвета:

- малиновый;

- голубой;

- темно-розовый;

- светло-зеленый;

- белый.

Трехмерный график данной функции представлен на рисунке. 1.2.

Рисунок 1.2 - Трехмерный график функции f(x)

1.4 Алгоритм решения задачи

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

минимизировать f (x)

при ограничениях h (x) = 0

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

Обозначим через точку минимума функции, используемой на t-той итерации, то есть функции

При переходе к (t+1)-й итерации пересчитывается по формуле:

.

1.5 Схема алгоритма

На основании алгоритма решения задачи можно построить схему алгоритма, которая будет использоваться для написания программного обеспечения. Построенная схема представлена на рисунке 1.3

Рисунок 1.3 - Блок-схема алгоритма

1.6 Описание программного обеспечения

Окно реализованного программного средства состоит из трех главных областей, показанных на рисунке 1.4:

область ввода начальных данных;

таблица отображения результатов, полученных в ходе выполнения программы;

кнопка «Выполнить», по нажатию на которую запускается процесс нахождения результатов.

Рисунок 1.4 - Главное окно приложения

В области ввода начальных данных пользователь вводит коэффициенты функции, а также условие окончания поиска. Все эти данные необходимы для корректного нахождения результата, и отображения его в область 2. В эту таблицу помещаются значения каждого витка цикла выполнения поиска результата. Как только разница в значениях h(x) t-го и (t-1) шага становится меньше введенного пользователем условия окончания поиска, вычисления останавливаются, результат определен.

1.7 Руководство пользователя

Для выполнения поиска результатов оптимизации методом модифицированной функции Лагранжа пользователь должен ввести коэффициенты функции f(x), а также условие окончания поиска. Поля для ввода этих значений располагаются в области «Параметры» главного окна приложения, показанного на рисунке 1.5.

Рисунок 1.5 - Главное окно приложения

Для запуска процесса нахождения результатов используется кнопка «Выполнить». По его окончании на главный экран в область «Результаты» выводится ход выполнения поиска, и его итог. Отображение происходит в виде таблицы с колонками , каждая строка которой отображает виток цикла выполнения поиска результата.



1.8 Результаты выполнения программы

Результат выполнения программы с исходными данными по умолчанию представлен на рисунке 1.6.

Рисунок 1.6 - Результат выполнения программы при значениях по умолчанию

Изменив условие окончания поиска, получим результат, представленный на рисунке 1.7, а подставив новые значения коэффициентов функции f(x), можно получит результат, представленный на рисунке 1.8.

Рисунок 1.7 - Результат выполнения программы при изменении условия окончания поиска

Рисунок 1.8 - Результат выполнения программы при измененных значения коэффициентов

1.9 Листинг

//Класс, реализующий минимизацию методом модифицированной функции Лагранжа

class Lagrange

{

//Коэффиценты функции f(x)

private int A1 { set; get; }

private int B1 { set; get; }

private int D1 { set; get; }

private int A2 { set; get; }

private int B2 { set; get; }

private int D2 { set; get; }

//Условие окончания поиска

private double Delta { set; get; }

//Конструктор класса

public Lagrange(int a1, int b1, int d1, int a2, int b2, int d2, double delta)

{

A1 = a1;

B1 = b1;

D1 = d1;

A2 = a2;

B2 = b2;

D2 = d2;

Delta = delta;

}

//Метод выполения поиска результатов

public List<List<double>> Method()

{

var mas = new List<List<double>>();

var del = Delta;

double t = 0;

double tau = 0;

double x1 = 0;

double x2 = 0;

double h = 0;

while (del >= Delta)

{

var list = new List<double>(7) {t};

if (t == 0)

{

list.Add(tau);

}

else

{

tau = x1 - (x2 + 3) - 5 + tau;

list.Add(tau);

}

double znam = 2*A1*B1 + 2*A2*B2 + A2*A2*A1*A1 + B1*B1*B2*B2 + B1*B1 - 2*A1*B1*A2*B2 + A2*A2 + A1*A1 +

B2*B2;

x1 = -(-8*A1*B1 + A1*B1*tau - A1*D1 - A1*D1*A2*A2 + A1*B1*A2*D2 - B1*D1 - 8*B1*B1 + A2*B2*B1*D1 -

- A2*D2 + A2*B2*tau - 8*A2*A2 - 8*A2*B2 - B2*D2 + tau*B1*B1 + tau*A2*A2 - B2*D2*B1*B1)/znam;

x2 = (-8*A1*A1 - 8*B2*B2 + B2*D2 + A2*D2*A1*A1 + B1*D1*B2*B2 + A2*D2 + tau*B2*B2 - 8*A2*B2 -

- 8*A1*B1 + tau*A1*A1 + B1*D1 - A1*B1*B2*D2 - A2*B2*A1*D1 + A1*B1*tau + A2*B2*tau + A1*D1)/znam;

double f = (A1*x1 + B1*x2 - D1)*(A1*x1 + B1*x2 - D1) + (A2*x2 + B2*x1 - D2)*(A2*x2 + B2*x1 - D2);

double p = f + x1 - (x2 + 3) - 5;

double h1 = h;

h = x1 - (x2 + 3) - 5;

list.Add(x1);

list.Add(x2);

list.Add(f);

list.Add(p);

list.Add(h);

t++;

del = Math.Abs(h - h1);

mas.Add(list);

}

return mas;

}

}



2. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Постановка задачи линейного программирования

Максимизировать

6	5

при ограничениях

Область допустимых решений задана координатами вершин многоугольника: O(0,0), A(4,15), B(8,8), C(13,0).

Метод оптимизации - симплекс-метод.

2.2 Графическое решение задачи

Необходимо найти максимальное значение целевой функции при системе ограничений:

(1)
(2)
(3)
	(4)
(5)

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом), изображенную на рисунке 2.1.

Рисунок 2.1 - Построенные прямые, и определяющие ими полуплоскости

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

Рисунок 2.2 - Область многоугольника решений

Рассмотрим целевую функцию задачи . Построим прямую, отвечающую значению функции . Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике рисунка 2.3 эта прямая обозначена пунктирной линией.

Рисунок 2.3 - Процесс передвижения прямой функции f(х)

Прямая пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

-

Решив систему уравнений, получим:Откуда найдем максимальное значение целевой функции:



2.3 Аналитическое решение задачи

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

Определим максимальное значение целевой функции F(X) = 6x1+5x2 при следующих ограничениях.

(1)
(2)
(3)
	(4)
(5)

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5.

-3.75x1 + 1x2 + 1x3 + 0x4 + 0x5 = 0

1.75x1 + 1x2 + 0x3 + 1x4 + 0x5 = 22

1.6x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20.8



Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных x3, x4, x5.Полагая, что свободные переменные равны 0, получим первый опорный план х1 = (0,0,0,22,20.8)

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

Базис	В	x1	x2	x3	x4	x5
x3	0	-3.75	1	1	0	0
x4	22	1.75	1	0	1	0
x5	20.8	1.6	1	0	0	1
F(X0)	0	-6	-5	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №1.

Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен 1.75 и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	min
x3	0	-3.75	1	1	0	0	-
x4	22	1.75	1	0	1	0	12.57
x5	20.8	1.6	1	0	0	1	13
F(X1)	0	-6	-5	0	0	0	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5
x3	47.14	0	3.14	1	2.14	0
x1	12.57	1	0.57	0	0.57	0
x5	0.69	0	0.0857	0	-0.91	1
F(X1)	75.43	0	-1.57	0	3.43	0

Итерация №2.

Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (0.09) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	min
x3	47.14	0	3.14	1	2.14	0	15
x1	12.57	1	0.57	0	0.57	0	22
x5	0.69	0	0.0857	0	-0.91	1	8
F(X2)	75.43	0	-1.57	0	3.43	0	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5
x3	22	0	0	1	35.67	-36.67
x1	8	1	0	0	6.67	-6.67
x2	8	0	1	0	-10.67	11.67
F(X2)	88	0	0	0	-13.33	18.33

Итерация №3.

Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.

Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai4 и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (35.67) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	min
x3	22	0	0	1	35.67	-36.67	0.62
x1	8	1	0	0	6.67	-6.67	1.2
x2	8	0	1	0	-10.67	11.67	-
F(X3)	88	0	0	0	-13.33	18.33	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5
x4	0.62	0	0	0.028	1	-1.03
x1	3.89	1	0	-0.19	0	0.19
x2	14.58	0	1	0.3	0	0.7
F(X3)	96.22	0	0	0.37	0	4.63

Итерация №4.

Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Оптимальный план можно записать так:

x4 = 0.62

x1 = 3.89

x2 = 14.58

F(X) = 6*3.89 + 5*14.58 = 96.22



2.4 Решение задачи с использованием процедуры "Поиск решения"

Для решения задачи с использованием процедуры «Поиск решения» создается таблица, в которой задаются все известные параметры. Затем вызывается диалоговое окно «Поиск решения», в котором:

задается ячейка с функцией для оптимизации;

выбирается, до какого значения будет оптимизирована функция;

вводятся ячейки, данные в которых можно изменять;

вводятся ограничения, представленные на рисунке 2.4.

Рисунок 2.4 - Диалоговое окно «Поиск решений»

Результатом поиска решения является таблица с результатами поиска, представленная на рисунке 2.5.

Рисунок 2.5 - Результат выполнения процедуры «Поиск решений»

ВЫВОДЫ

В ходе выполнения данного курсового проекта были затронуты такие задачи линейного и нелинейного программирования, как метод модифицированной функции Лагранжа и симплекс-метод.

Метод оптимизации очень нагляден и позволяет найти решение с помощью простого алгоритма с любой степенью точности. Суть симплекс-метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

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



СПИСОК ЛИТЕРАТУРЫ

Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005. - 128 с.

Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. -- М.: Изд-во «Факториал», 1998. -- 172 с.

Банди Б. Основы линейного программирования: Пер. сангл. -- М.: Радио и связь, 1989. - 176 с

Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. - М.: Мир, 1972, - 316 с.

Размещено на www.allbest.ru