Практическое занятие № 7

Наименование работы: Решение задач нелинейного программирования графическим методом

Цель работы: Научиться решать задачи нелинейного программирования

Подготовка к занятию: Повторить теоретический материал по теме «Нелинейное программирование»

Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2013г.

2. Агальцов В.П. Математические методы в программировании, 2010г.

Перечень необходимых приборов, инструментов, материалов:ПЭВМ

Задание на занятие:

Графически и аналитически решить задачу нелинейного программирования. Полученные результаты проверить с помощью математической системы Mathcad. Исходные данные необходимо выбрать из таблицы в соответствии со своим вариантом.

Вариант	Целевая функция	Ограничения
1	Z = (x1 – 8)²+(х2 – 4)²	х1 + х2 ≥ 4 2х1 + х2 ≤ 16 -х1 + х2 ≤ 2 0,25х1 + х2 ≥ 4 х1≥0, х2≥0
2	Z = (x1 – 16)²+(х2 – 8)²	х1 + х2 ≤ 16 х1 - х2 ≥ 4 4х1 + х2 ≥ 32 х1≥0, х2≥0
3	Z = (x1 – 4)²+(х2 – 6)²	х1 + х2 ≤ 16 х1 - х2 ≤ 4 4х1 + х2 ≥ 32 х1≥0, х2≥0
4	Z = (x1 – 10)²+(х2 – 12)²	х1 + х2 ≤ 16 х1 - х2 ≤ 4 4х1 + х2 ≥ 32 х1≥0, х2≥0
5	Z = (x1 – 6)²+(х2 – 4)²	х1 + х2 ≤ 8 х1 + х2 ≥ 2 - х1 + х2 ≤ 2 х1 - х2 ≤ 4 х1≥0, х2≥0
6	Z = (x1 – 1)²+(х2 – 4)²	х1 + х2 ≤ 8 х1 + х2 ≥ 2 - х1 + х2 ≤ 2 х1 - х2 ≤ 4 х1≥0, х2≥0
7	Z = (x1 – 4)²+(х2 – 2)²	х2≤4 2х1+х2 ≤ 8 х1+х2 ≥4 х1≥0, х2≥0
8	Z = (x1 – 10)²+(х2 – 2)²	х1 - х2 ≥ 6 х1 + х2 ≤ 10 х1 + 2х2 ≥ 8 х1≥0, х2≥0
9	Z = (x1 – 4)²+(х2 – 2)²	2х1+х2 ≥ 16 х1+2х2 ≤ 16 х1≥0, х2≥0
10	Z = (x1 – 4)²+(х2 – 6)²	х1-х2 ≤ 2 х1+х2 ≤ 6 х1+2х2 ≥ 4 х1≥0, х2≥0

Порядок проведения занятия:

1. Получить допуск к работе.

2. Выполнить задание в соответствии со своим вариантом.

3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. Сформулируйте задачу нелинейного программирования в общем виде.

2. Чем отличаются задачи нелинейного программирования от задач линейного программирования?

3. Перечислите основные этапы решения задачи нелинейного программирования графическим способом.

4. Где может быть расположена точка экстремума в задачах нелинейного программирования?

ПРИЛОЖЕНИЕ

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

Рассмотрим пример графического и аналитического решения задачи нелинейного программирования. Найдем минимум целевой функции: Z = (х₁-7)² + (х₂-4)² с ограничениями:

х₁+х₂ ≤ 10,

2х₁+х₂ ≥ 12,

х₁-х₂ ≥ 2,

х₁-х₂ ≤ 4

х₁≥ 0, х₂≥ 0

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

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

Область, удовлетворяющая всем четырем неравенствам, будет областью допустимых решений (трапеция ABCD).

.

Теперь необходимо построить график ЦФ. Для этого следует отметить центр окружности. В данном примерех₁ = 7их₂ = 4. Затем с помощью циркуля нужно построить несколько окружностей, увеличивая радиус до тех пор, пока окружность не коснется какой либо точки ОДР. В этой точке будет минимум ЦФ. Далее следует найти наиболее удаленную от центра окружности точку ОДР. В этой точке будет максимум ЦФ.

Из рисунка видно, что минимум ЦФ находится в точке F, а максимум – в точкеD. Определим приближенно координаты точкиF:х₁= 6,5, х₂= 3,5. Значение целевой функции в этой точке Z = 0,5. Приближенные значения координат точкиD:х₁= 5,3, х₂= 1,4. Приближенное значение ЦФ в этой точке Z = 9,65.

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

На основании приближенного графического решения задачи НПР найдём аналитически точный ответ. Для этого, из уравнения целевой функции Z = (х₁-7)²+(х₂-4)² найдем частные производные пох₁их₂:

Производная по х₁: Z^|= 2(х₁-7) + 2(х₂-4)²∙х₂^| . Приравняем Z^| =0. Затем выразим из этого уравнения производнуюх₂^| :х₂^| = -(х₁-7/х₂-4).

Определим тангенс угла наклона (производную) для прямой х₁+х₂= 10

х₂^| = -1

-(х₁-7/х₂-4) = - 1

х₁-7 =х₂-4

Решим систему уравнений

-х₁+х₂= 3

х₁+х₂= 10

2х₁₌13,

х₁= 6,5

х₂= 3,5

Полученные значения х₁их₂подставляем в ЦФ Z = (х₁-7)²+(х₂-4)²

Таким образом, минимальное значение ЦФ Z=0,5.

Решение с помощью системы Mathcad

Зададим ЦФ:

Z(x1,x2):= (х1-7)²+ (х2-4)²

Зададим произвольные начальные значения переменным:

x1 := 0

x2 := 0

Начало блока вычислений

Given

Опишем ограничения:

х1 + х2 ≤ 10

2х1 + х2 ≥ 12

х1 – х2 ≥ 2

х1 – х2 ≤ 4

х1 ≥ 0

х2 ≥ 0

Выполним операцию минимизации:

P: = Minimize (Z, x1, x2)

Выведем на экран значения найденных переменных:

Вычислим целевую функцию:

Z(P₀,P₁) = 0.5

Итак, оптимальные значения переменных:

х1 = 6,5, х2 = 3,5. Значение ЦФ Z= 0,5