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

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

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

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

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

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

от 25%

Подписываем

договор

Имя

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

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

Скидка 25% при заказе до 29.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. ДОБРАЧНОЕ ПОВЕДЕНИЕ И ГЕНДЕРНАЯ СПЕЦИФИКА ДОБРАЧНОГО ПОВЕДЕНИЯ СТУДЕНЧЕСКОЙ МОЛОДЕЖИ КАК ПРЕДМЕТ ТЕОРЕТИЧЕСКИХ ИССЛЕДОВАНИЙ
5. Бельгия1
6. Полносистемное карповое хозяйство.html
7. из чего все состоит является одним из главных в естествознании
8. Выплавка стали
9. советские газеты опубликовали последнее сообщение с фронтов гражданской войны- ldquo;Вследствие прекращения
10. тема и ее составные частиТеория двойственности памяти.html

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