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

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

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

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

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

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

Найти минимальное значение функции F(X)=-6X₁-2X₂-6X₃ (max) при следующих ограничениях:

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

Для начала необходимо привести ограничения к виду равенств. Для этого необходимо ввести дополнительные переменные x₄, x₅, x₆ и искусственную переменную R₁.

Пусть R, x₄, x₅, x₆ - базисные переменные, а x₁, x₂, x₃ - небазисные. Функция цели F(X)= 3X₁+0X₂+2X₃ -M·R₁ (min)

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

Таблица 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). Ведущая строка - X₅. В строке X₅ так же найдем максимальный по модулю отрицательный свободный член (-5). Столбец X₁- ведущий. Пересчитаем таблицу 2.

Таблица 2

Базисные переменные	Свободные члены	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

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

Таблица 3

Базисные переменные	Свободные члены	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

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

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

X₁=4.75; x₃ =2; x₄=35; x₆=0.25; F_max=46.5.

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

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

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

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

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



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

Так как в прямой задаче требуется найти минимум функции, то приведем первоначальное условие к виду {F(x) = B^T x| A^T x?C, x_j ?0, j = 1,m}

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

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

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

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

F(Y)=-12Y₁+27Y₂-15Y₃-3Y₄ (max)

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

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

Введем дополнительные переменные Y₅, Y₆, Y₇. Ограничения примут вид:

Y_i?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). Ведущая строка - Y₆. В строке Y₆ так же найдем максимальный по модулю отрицательный свободный член (-3). Столбец Y₁- ведущий.

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

Базисные переменные	Свободные члены	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

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

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

Базисные переменные	Свободные члены	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

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

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

Базисные переменные	Свободные члены	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

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

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

Базисные переменные	Свободные члены	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). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. Столбец Y₁- ведущий.

Y₃=1.69; y₆=0.9; y₁=0.76; F_min=79.2.

F_max(x)=F_min(y)=79.2

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

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8 0

x₁+8x₂-400

x_1,2 0

x⁰=[3; 2].

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

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

Внутри области допустимых значений выбираем точку x⁰, которая в дальнейшем будет являться начальной в процессе поиска экстремума: x0=(3;2).

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min)

3x₁ -8x₂ +8 0

x₁+8x₂-400

x_1,2 0

x⁰=[3; 2].

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

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

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

.

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



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

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

=

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

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

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

Второй шаг:

x ²= x ¹ +б¹F(x ¹)

=

Третий шаг:

=

F_min = 0.793

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min)

x⁰=[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 ¹:

;

F_max = 0.793;

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

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8 0

x₁+8x₂-400

x_1,2 0

x⁰=[3; 2].

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

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

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

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

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

min{-25x₁-39x₂ |3x₁ -8x₂-8; x₁+8x₂ 40;x_1,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 по абсолютному значению, то примем



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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8 0

x₁+8x₂-400

x_1,2 0

x⁰=[3;2].

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

Тогда и и

g₁(x)= 3x₁ -8x₂+8 0

g₂(x)= x₁+8x₂-400

Тогда L(x, л)= -6x₁²-12x₂²-4x₁x₂+1x₁-3x₂ + л₁ (3x₁ -8x₂+8)+ л₂ (x₁+8x₂-40)

Найдем



СЛАУ с неизвестными x₁, x₂, л₁, л₂, v₁, v₂, w₁, w₂.

x_1,2 0; л_1,20; v_1,20; w_1,20.

Решив эту систему с помощью симплекс-метода, мы можем найти допустимое базисное решение и то решение, которое удовлетворяет x^Tv=0 и л^Tw=0 или x₁ v₁= x₂v₂=0; л₁ w₁=л₂w₂=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

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

W₂ = 0, v₁ =0.875, v₂ =1, x₂= 32.

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

F_min = .

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