У вас вопросы?
У нас ответы:) SamZan.net

тематическая модель задачи

Работа добавлена на сайт samzan.net: 2015-07-10

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 5.4.2025

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

2.1 Математическая модель задачи. Нахождение оптимального плана х* и экстремального значения функции

Найти минимальное значение функции F(X)=-6X1-2X2-6X3 (max)

при следующих ограничениях:

0X1	+	2X2	-	6X3	=	-12
0X1	-	5X2	-	4X3	≥	-27
-4X1		-3X2	+	2X3	≤	-15
1X1	+	2X2	-	4X3	≤	-3

xj0 (j=1...3)

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

Для начала необходимо привести ограничения к виду равенств. Для этого необходимо ввести дополнительные переменные x4, x5, x6 и искусственную переменную R1.

0X1	+	2X2	-	6X3	+R1	=	-12
0X1	-	5X2	-	4X3	+X4	=	27
-4X1	-	3X2	+	2X3	+X5	=	-15
1X1	+	2X2	-	4X3	+X6	=	-3

xj0 (j=1...3)

Пусть R, x4, x5, x6 – базисные переменные, а x1, x2, x3 – небазисные. Функция цели F(X)= 3X1+0X2+2X3 -M·R1 (min)

Составим симплекс таблицу

Таблица 2.1

Базисные переменные	Свободные члены	X1	X2	X3
R1	-12	0	2	-6
X4	27	0	-5	-4
X5	-15	-4	-3	2
X6	-3	1	2	-4
F	42	6	2	6
M	12	0	-2	6

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-9). Ведущая строка - X5. В строке X5 так же найдем максимальный по модулю отрицательный свободный член (-5). Столбец X1- ведущий.
Пересчитаем таблицу

Базисные переменные	Свободные члены	X5	X2	X3
R1	-12	0	2	-6
X4	27	0	-5	-4
X1	3.75	-0.25	0.75	-0.5
X6	-6.75	0.167	1.25	-3.5
F	64.5	1.5	-2.5	9
M	12	0	-2	6

Базисные переменные	Свободные члены	X6	X2
Х3	2	0	-0.333
X4	35	0	-6.333
X1	4.75	-0.25	0.583
X6	0.25	0.167	0.083
F	46.5	1.5	0.5
M	0	0	0

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

Тогда решение данной задачи:

X1=4.75; x3 =2; x4=35; x6=0.25; Fmax=46.5.

2.2 Построение и решение задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач

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

(2.2)

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

Исходная задача:

Найти максимальное значение функции F(X)=-6X1-2X2-6X3 (max)

0X1	+	2X2	-	6X3	+R1	=	-12
0X1	-	5X2	-	4X3	+X4	=	27
-4X1	-	3X2	+	2X3	+X5	=	-15
1X1	+	2X2	-	4X3	+X6	=	-3

xj0 (j=1...3)

Строим двойственную задачу:

Так как в прямой задаче требуется найти минимум функции, то приведем первоначальное условие к виду
{F(x) = BT x| AT x≥C, xj ≥0, j = 1,m}

Для достижения нужного вида домножим 2-e неравенство на -1
В результате получим следующие матрицы:

Транспонируем матрицу A:

Поменяем местами вектора B и C:

Двойственная задача будет иметь 4 переменные, так как прямая содержит 4 ограничения. В соответствии запишем двойственную задачу в виде:

F(Y)=-12Y1+27Y2-15Y3-3Y4 (max)

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

Ограничения:

0Y1	+	0Y2	-	4Y3	+	1Y4	≥
2Y1	-	5Y2	-	3Y3	+	2Y4	≥
-6Y1	-	4Y2	+	2Y3	-	4Y4	≥

Y1	≥	0
Y2	≥	0
Y3	≥	0
Y4	≥	0

Введем дополнительные переменные Y5, Y6, Y7.
Ограничения примут вид:

0Y1	+	0Y2	-	4Y3	+	1Y4	+ Y5	≥	0
2Y1	-	5Y2	-	3Y3	+	2Y4	+ Y6	≥	0
-6Y1	-	4Y2	+	2Y3	-	4Y4	+ Y7	≥	0

Yi≥0
Составим симплекс-таблицу:

Базисные переменные	Свободные члены	Y1	Y2	Y3	Y4
Y5	-6	0	0	-4	1
Y6	-2	2	-5	-3	2
Y7	-6	-6	-4	2	-4
F	42	-12	27	-15	-3

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-3). Ведущая строка - Y6. В строке Y6 так же найдем максимальный по модулю отрицательный свободный член (-3). Столбец Y1- ведущий.

Пересчитаем таблицу

Базисные переменные	Свободные члены	Y7	Y2	Y3	Y4
Y5	-6	0	0	-4	1
Y6	-4	0.333	-6.333	-2.333	0.667
Y1	1	-0.167	-0.667	0.333	-0.667
F	54	-2	35	-19	5

Пересчитаем таблицу

Базисные переменные	Свободные члены	Y7	Y2	Y5	Y4
Y3	1.5	0	0	-0.25	-0.25
Y6	-0.5	0.333	-6.333	-0.583	0.084
Y1	-0.5	-0.167	-0.667	0.083	-0.584
F	82.5	-2	35	-4.75	0.25

Пересчитаем таблицу

Базисные переменные	Свободные члены	Y7	Y2	Y5	Y1
Y3	1.5	0	0	-0.25	-0.25
Y6	0.08	-0.053	-0.158	0.092	-0.013
Y4	-0.45	-0.2	0.11	0.144	-0.592
F	79.7	-0.16	5.53	-8.75	0.71

Пересчитаем таблицу

Базисные переменные	Свободные члены	Y7	Y2	Y5	Y4
Y3	1.69	0.08	-0.05	-0.31	-0.42
Y6	0.09	-0.049	-0.16	0.089	-0.022
Y1	0.76	0.338	-0.186	-0.243	-1.689
F	79.2	-0.4	5.66	-8.58	1.2

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-9). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. Столбец Y1- ведущий.

Y3=1.69; y6=0.9; y1=0.76; Fmin=79.2.

Fmax(x)=Fmin(y)=79.2

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

3.1 Построение ОДЗП, выбор начальной точки поиска

Целевая функция имеет вид:

F(x)= -3x12-6x22-4x1x2+1x1-3x2 (min).

3x1 -8x2 +8 0

x1+8x2-400

x1,2 0

x0=[3;2].

Построим ОДЗП:

Рисунок 3.1 - ОДЗП

Внутри области допустимых значений выбираем точку x0, которая в дальнейшем будет являться начальной в процессе поиска экстремума:

x0=(3;2).

3.2 Нахождение экстремального значения функции F(x) без учета ограничений на переменные

3.2.1 Метод наискорейшего спуска

F(x)= -3x12-6x22-4x1x2+1x1-3x2 (min).

3x1 -8x2 +8 0

x1+8x2-400

x1,2 0

x0=[3;2].

В методе наискорейшего спуска (подъема) очередная точка при поиске максимума функции вычисляется по формуле:

где направление движения задается вектором антиградиента функции F(x), вычисленном в точке , а величина шага перемещения определяется числовым параметром .

Найдем градиент :

Осуществляем движение из точки x 0 вдоль градиента F(x0) в новую точку x1.

Подставляем координаты точки x1 в функцию F(x),

Затем найдем , в которой функция F(x) будет иметь экстремум. Для этого найдем производную

В результате после первого шага координаты очередной точки

получаются равными:

Продолжаем поиск по тому же алгоритму.

Второй шаг:

x 2= x 1 +α1F(x 1)

Третий шаг:

Fmin = 0.793

3.2.2 Метод Ньютона-Рафсона

Условие задания:

F(x)= -3x12-6x22-4x1x2+1x1-3x2 (min).

x0=[3;2].

Очередная точка вычисляется в соответствии с выражением

x k+1= x k –H-1(x k)F(x k),

где H(x ) – матрица Гессе функции F(x);

H-1(x) – обратная по отношению к H(x) матрица.

Запишем матрицу Гессе:

Тогда AdjH=

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

detH = -6∙(-12) – (-4)∙(-4) = 72 – 16 = 56.

H-1 = ;

Найдем очередную точку x 1:

;

Fmax = 0.793;

Следовательно, в точке x 1 функция F(х) достигает минимума. Fmin = 0.793.

3.3 Нахождение экстремального значения функции F(x) с учетом системы ограничений задачи

3.3.1 Метод линейных комбинаций

F(x)= -3x12-6x22-4x1x2+1x1-3x2 (min).

3x1 -8x2 +8 0

x1+8x2-400

x1,2 0

x0=[3;2].

Первая итерация.

Зададимся точностью

Вычисляется вектор-градиент

Осуществляется линеаризация F(x) относительно точки x0 в соответствии с выражением

Решается задача ЛП

min{-25x1-39x2 |3x1 -8x2-8; x1+8x2 40;x1,20}.

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

БП	СЧ	НП
x1	x2
x3	-8	3	-8
x4	40	1	8
F	0	-25	-39

БП	СЧ	НП
X4	X2
X3	1	-0.375	-0.125
X1	32	4	1
F	39	-39.6	-4.875

БП	СЧ	НП
X4	X3
X2	4	-0.094	-0.031
X1	8	0.25	-0.25
F	355.8	9.9	5.025

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

Wmin=355.8; x=[8 4]

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

Или

Так как значение в шаге не может превышать 1 по абсолютному значению, то примем

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

F(x)= -3x12-6x22-4x1x2+1x1-3x2 (min).

3x1 -8x2 +8 0

x1+8x2-400

x1,2 0

x0=[3;2].

Прежде, чем составить функцию Лагранжа, нужно привести ограничения к нулевой правой части. Анализируем экстремум: так как в условии минимум, то будет минимум по x и максимум по λ.

Тогда и и

g1(x)= 3x1 -8x2+8 0

g2(x)= x1+8x2-400

Тогда L(x, λ)= -6x12-12x22-4x1x2+1x1-3x2 + λ1 (3x1 -8x2+8)+ λ2 (x1+8x2-40)

Найдем

-4x2-6x1+3λ1-8λ2 +1v1=0 4x2+6x1 -3λ1+8λ2 +v1=8

-12x1+4x2+λ1 +8λ2 -3v2=56 12x1+4x2-8λ1 +3λ2+v2=-40

3x1-8x2+w1=-8 3x1-8x2+w1=-8

x1+8x2+w2=40 x1+8x2+w2=40

СЛАУ с неизвестными x1, x2, λ1, λ2, v1, v2, w1, w2.

x1,2 0; λ1,20; v1,20; w1,20.

Решив эту систему с помощью симплекс-метода, мы можем найти допустимое базисное решение и то решение, которое удовлетворяет xTv=0 и λTw=0 или x1 v1= x2v2=0

λ1 w1=λ2w2=0

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

БП	СЧ	НП
x1	x2
v1	1	6	4	-3	8
v2	-3	12	4	-8	3
w1	-8	3	-8	0	0
w2	40	1	8	0	0

БП	СЧ	НП
x1	W1
v1	-3	7.5	0.5	-3	8
v2	-7	10.5	0.5	-8	3
X2	1	-0.375	-0.125	0	0
w2	32	4	1	0	0

БП	СЧ	НП
x1	W1	v2
v1	0	1.5	0.3	-0.375	6.9
	0.875	-1.3	-0.06	-0.125	-0.375
X2	1	-0.375	-0.125	0	0
w2	32	4	1	0	0

Таким образом, получили решение:

W2 = 0, v1 =0.875, v2 =1, x2= 32.

Исходя из полученного решения, определим экстремум функции:

Fmin = .

1. тематические методы в психологии Дискриминантный анализ
2. на тему- Авторское право Выполнил- студент гр
3. Реферат- О виски
4. Гректi~ ldquo;Хюдорrdquo; деген с~зi ~андай ма~ана бередi Су BАуа CАры~ DТе~iз E С~йы~
5. Личные права и свободы граждан
6. Тема 1 Робота з шаблонами документів Завдання- На основі стандартного шаблону Microsoft Excel 2007 створити шаблон п
7. 00 мин. Выберите правильный ответ и впишите его в таблицу в конце блока заданий максимум 15 баллов
8. наукового інституту права психології та економіки Львівського державного університету внутрішніх справ
9. Ответственность по гражданскому праву
10. тема правового регулювання земельного права України Земельне право України являє собою самостійну га

Материалы собраны группой SamZan и находятся в свободном доступе