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

Министерство образования республики Беларусь

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»

Институт информационных технологий

КОНТРОЛЬНАЯ РАБОТА

по курсу: «Оптимальная модель линейного и нелинейного программирования»

Студент-заочник 2 курса

Группы № 082424

Милашевский Владимир Сергеевич

Минск, 2012



Содержание

1. Линейное программирование

2. Нелинейное программирование

Список использованной литературы



1. Линейное программирование

1) Найти оптимальный план x* и экстремальное значение функции F(x).

2) Построить задачу, двойственную к исходной, решить её и сравнить решения прямой и двойственной задач.

3) Если решение не является целочисленным, получить целочисленное решение путём введения дополнительных ограничений по методу Гомори.

Вариант 18.

Условия задачи:

F(x) = 3x₁ + x₂ -6x₃ (max)

4) Математическая модель выглядит следующим образом:

max{F(x) = 3x₁ + x₂ - 6x₃ | -6x₁ - x₂ - 6x₃ ? -39; 2x₁ - 3x₂ + 5x₃ ? 12;

-x₁ + 5x₂ + 4x₃ ? 24; x_1,2,3 ? 0}.

Для удобства заполнения симплекс-таблицы приведем ограничения к виду «?», умножив обе части неравенства на «-1».



Приведем ограничения к виду равенств, введя дополнительные переменные со знаком «+», т.к. ограничения вида «?»:

Матрицы A, Bи C^Tвыглядят следующим образом:

A=;B = ;С^T = ;

Если дополнительная переменная со знаком «-», то все коэффициенты перед переменными x_i и свободный член b_j заносятся с противоположным знаком.

Если цель минимизация, то коэффициенты функции цели заносятся без изменения знака.

Таблица: Симплекс-таблица выглядит следующим образом

БП	СЧ	НП
		x1	x2	x3
x4 x5 x6	39 12 24	6 2 -1	1 -3 5	6 1 4
Fmax	0	-3	-1	6

двойственная задача переменная экстремальная функция

За базисные переменные принимаем дополнительные переменные x₄, x₅,x₆. А переменные x₁, x₂,x₃ будут являться небазисными.

Свободные члены определяют решение задачи.

1 шаг: Производится поиск базисного решения. Т.к. все свободные члены положительны, значит, решение является допустимым. Переходим сразу к шагу 5 для нахождения оптимального решения.

5 шаг: Признаком оптимальности является не отрицательность переменных в F-строке. c₁, c₂ < 0. Следовательно, решение не является оптимальным.

В базис будет включаться та из небазисных переменных, которая находится в столбце с элементом c_l, которому соответствует максимальное абсолютное значение.

В данной задаче это элемент c₁ = -3< 0.Ведущий столбец x₁.

Выбор ведущей строки определяется минимальным симплексным отношением . Следует рассматривать только положительные симплексные отношения.

В данной задаче минимальное симплексное отношение получается в строке x₅ = 6.

Таким образом, ведущая строка x₅. Ведущий элемент a₂₁ = 2.

Производим пересчет симплекс-таблицы:

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

Таблица: Новая симплекс-таблица выглядит следующим образом

БП	СЧ	НП
		x5	x2	x3
x4 x1 x6	3 6 30	-3	10	3
Fmax	18

БП	СЧ	НП
		x5	x4	x3
x2 x1 x6
Fmax

БП	СЧ	НП
		x6	x4	x3
x2 x1 x5
Fmax

F_max = .

Оптимальный план:

x₂ =

x₁ =

x₅ =

5) Выводим условия двойственной задачи:

F(x) = 3x₁ + x₂ -6x₃ (max)

Так как задача максимизации, то условия приводим к виду «?»:

Матрицы A^T, Bи Cвыглядят следующим образом:

A^T= ;B = ;С =;

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

Тогда A^TY ? C примет вид:

Функция цели F(y) = B^TY = = 39y₁ + 12y₂ + 24y₃ (min)

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

Далее решение производится симплекс-методом.

Вводим дополнительные переменные и приводим ограничения к виду равенств.



Так как цель минимизация, коэффициенты функции цели заносятся в таблицу без изменения знака.

БП	СЧ	НП
		y1	y2	y3
y4 y5 y6	-3 -1 6	-6 -1 -6	-2 3 -5	1 -5 -4
Fmin	0	39	12	24

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

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

2шаг: Производим пересчет симплекс-таблицы:

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

Пусть это будет b₁= -3 < 0.Просматриваем строку, в которой находится этот элемент, и выбираем любой отрицательный элемент.

Пусть это будет a₁₁ = -6 < 0.

Если в строке нет отрицательных элементов, то задача не имеет решения.

Приоритетом в выборе элементов является максимальное абсолютное значение модуля элемента.

Таким образом, ведущим элементом будет являться элемент a₁₁ = -6. Ведущая строка y₄, ведущий столбец - y₁. Из базиса исключается переменная y₄, в базис вводится переменная y₁.

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

Таблица: Новая симплекс-таблицы выглядит следующим образом

БП	СЧ	НП
		y4	y2	y3
y1 y5 y6	9	-1	-3	-5
Fmin			-1

БП	СЧ	НП
		y4	y2	y5
y1 y3 y6
Fmin

Оптимальное решение найдено.

F_min = .

Оптимальный план:

y₁ = .

y₃ = .

y₆ = .

Решения прямой и двойственной задачи совпадают.

6) Решение задачи без условия целочисленности приведено в пункте 1.

Составим дополнительное ограничение по строке, соответствующей переменной x₂, так как у неё наибольшая дробная часть {x₂} = .

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

x₆ +x₄ +x₃ ?

или

x₆ +x₄ +x₃ ?

Приведем к виду равенства, введя дополнительную переменную x₇ и домножим обе части неравенства на «-1»:

x₆ x₄ x₃ +x₇ = -

Расширенная симплекс-таблица выглядит следующим образом:

БП	СЧ	НП
		x6	x4	x3
x2 x1 x5 x7
Fmax

БП	СЧ	НП
		x7	x4	x3
x2 x1 x5 x6	5	1	0	0 0 -1 5
Fmax	22

2. Нелинейное программирование

1) Построить область допустимых значений переменных.

2) Найти максимальное значение функции F(x) без учета ограничений на переменные, используя:

а) метод наискорейшего спуска

б) метод Ньютона

Процесс оптимизации начинать с точки x0.

3) Найти максимальное значение функции F(x) с учетом системы ограничений задачи, используя:

а) метод допустимых направлений Зойтендейка

б) условия теоремы Куна-Таккера

Процесс оптимизации начинать с точки x0.

Вариант 18.

F(x) = +5+4+5+7

x_1,2? 0

x⁰ = [3;2]

x1	0	7	-7
x2	2	4	0

1) x₂ ?

x1	0	7	6,2
x2	-31	4	0

x₂ ?

а) Находим составляющие вектора градиента функции:

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

1 шаг: Движение осуществляется из x⁰вдоль в новую точку x¹:

Градиент в точке x⁰равен:

Координаты точки x¹определяются выражением:

Величину шага определим из условия:

=

В результате точка x¹:

2 шаг:

Градиент в точке x¹равен:

Координаты точки x² определяются выражением:

Величину шага определим из условия:

В результате точка x²:

3 шаг:

Градиент в точке x²равен:

Координаты точки x³ определяются выражением:

Величину шага определим из условия:



В результате точка x³:

В точке х³ функция достигает значения

F_max = -5,91;

Метод наискорейшего спуска неэффективен при приближении к точке экстремума, поэтому существует погрешность.

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

H^-1= , где detH- определитель матрицы H.

detH = 2•10 - 4•4 = 20 - 16 = 4.

AdjH - присоединенная к H матрица (транспонированная матрица алгебраических дополнений).

Найдем алгебраические дополнения элементов матрицы H:

, тогда:

Тогда AdjH=; H^-1 = ;

;

F_max = -8,5;

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

3) Учитывая, что экстремум функции будет являться её минимумом, будем использовать градиент с противоположным знаком.

Градиент в точке х⁰ равен:

Выбираем наиболее сильные условия:

Находим значение как в методе наискорейшего спуска. . Данное значение не принадлежит найденному интервалу, поэтому .

Точка х¹ равна:

Таким образом, точка попадает на ограничение х₂ = 0.

Градиент в точке х¹ равен:

Движение в этом направлении выводит за пределы ОДЗП, поэтому очередная точка поиска будет производиться в направлении S¹:

Координаты новой точки определятся выражением:



Определим интервал изменения параметра при котором x² принадлежит области допустимых значений переменных:

=>

Выбираем наиболее сильные условия: -2 ? ? 4,2

Находим величину , которая обеспечит максимум функции F(x) в направлении S¹:

Для этого в функцию цели подставляем координаты точки x²:

F() =

;

Значение = -4,5 не принадлежит найденному интервалу, поэтому принимаем значение равным граничному значению, .

Градиент в точке x² равен:

Его направление перпендикулярно направлению вектора S¹. Следовательно, данная точка является оптимальным решением.

Функция достигает экстремума в точке . Точка экстремума лежит на пересечении ограничивающих прямых и .

F_min = 0.



б) Составим функцию Лагранжа:

Так как экстремум функции будет являться минимумом, то производная , а производная .

Запишем условия теоремы Куна-Таккера:

БП	СЧ	НП
		x1	x2	л1	л2
v1 v2 w1 w2	5 7 14 31	-2 -4 -2 5	-4 -10 7 -1	2 -7 0 0	-5 1 0 0

Решение, определяемое последней таблицей, соответствует допустимому базисному решению v₁= 5; v₂= 7; w₁=14; w₂=31; x₁=x₂= л ₁= л₂= 0.

Выполняется условие x₁•v₁=x₂•v₂ = л₁•w₁=л₂•w₂ = 0, поэтому является оптимальным решением задачи.

При этом F_min= 0.



Список использованной литературы

1. Полный конспект лекций. Павлова А. В. БГУИР.

2. Математические основы теории систем, алгебраические структуры и матричные методы. Авторы: Ушаков, Хабалов, Дударенко, СПбГУ ИТМО 2005г.

3. Математические основы теории систем: Элементы теории и практикум: Учебное пособие. Ушаков А.В., Хабалов В.В., Дударенко Н.А., Москва, 2007 г.

Размещено на Allbest.ru