Контрольная работа на тему Исследование операций 3
Работа добавлена на сайт bukvasha.net: 2014-07-03Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
Челябинск
2004 г.
Содержание
Задание 1 3
Задание 2 6
Задание 3 9
Задание 4 11
Литература 17
Задание 1
Задача 9
Условие:
Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.
Решение:
Составим математическую модель задачи.
Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.
Тогда, целевая функция будет
L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min
Система ограничений:
_ EMBED Equation.3 ___
Приведем систему ограничений к виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.
L’=0-(5n1+ 6n2+7n3) →max
_ EMBED Equation.3 ___
Выберем n1, n2, n3 свободными переменными, а n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L’=0-(5n1+ 6n2+7n3)
_ EMBED Equation.3 ___
Составим симплекс-таблицу.
Это решение не опорное, т.к. свободные члены не положительны.
Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).
Таблица 1.1
Меняем n1 и n5.
Таблица 1.2
Меняем n5 и n6.
Таблица 1.3
Меняем n4 и n6.
Таблица 1.4
Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.
Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,
где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,
(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).
Решение:
Составим систему:
_ EMBED Equation.3 ___
Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3 ___
Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3 ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
Меняем x2 и x6.
Таблица 2.2
Меняем x5 и x8.
Таблица 2.3
Меняем x5 и x1.
Таблица 2.4
Получили оптимальное решение, т.к. все коэффициенты положительны.
Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица 1
Решение:
Составим таблицу транспортной задачи.
Таблица 2
Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
Это будет опорный план.
Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
Вариант 9
_Челябинск
2004 г.
Содержание
Задание 1 3
Задание 2 6
Задание 3 9
Задание 4 11
Литература 17
Задание 1
Задача 9
Условие:
Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.
Вещество | Количество единиц вещества, содержащегося в 1 кг сырья | ||
1 | 2 | 3 | |
А | d11 | d12 | d13 |
В | d21 | d22 | d23 |
С | d31 | d32 | d33 |
Цена 1 кг сырья | D1 | D2 | D3 |
№ вар. | d11 | d12 | d13 | d21 | d22 | d23 | d31 | d32 | d33 |
9 | 1 | 1 | 0 | 2 | 0 | 3 | 1 | 2 | 4 |
D1 | D2 | D3 | а | b | c |
5 | 6 | 7 | 26 | 30 | 24 |
Составим математическую модель задачи.
Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.
Тогда, целевая функция будет
L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min
Система ограничений:
_ EMBED Equation.3 ___
Приведем систему ограничений к виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.
L’=0-(5n1+ 6n2+7n3) →max
_ EMBED Equation.3 ___
Выберем n1, n2, n3 свободными переменными, а n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L’=0-(5n1+ 6n2+7n3)
_ EMBED Equation.3 ___
Составим симплекс-таблицу.
Это решение не опорное, т.к. свободные члены не положительны.
Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).
Таблица 1.1
b | n1 | n2 | n3 | ||||||
L’ | 0 | 5 | 6 | 7 | |||||
-75 | 2,5 | 0 | -8 | ||||||
n4 | -26 | -1 | -1 | 0 | 26/1=26 | ||||
15 | -1 | 0 | 1,5 | ||||||
n5 | -30 | -2 | 0 | -3 | 30/2=15min | ||||
15 | -1 | 0 | 1,5 | ||||||
n6 | -24 | -1 | -2 | -4 | 24/1=24 | ||||
15 | -1 | 0 | 1,5 |
Таблица 1.2
b | n5 | n2 | n3 | ||||||
L’ | -75 | 2,5 | 6 | -0,5 | |||||
-45 | 5 | -10 | 25 | ||||||
n4 | -11 | -0,5 | -1 | 1,5 | 11/0,5=22 | ||||
9 | -1 | 2 | -5 | ||||||
n1 | 15 | -0,5 | 0 | 1,5 | |||||
9 | -1 | 2 | -5 | ||||||
n6 | -9 | -0,5 | -2 | -2,5 | 9/0,5=18min | ||||
18 | -2 | 4 | 5 |
Таблица 1.3
b | n6 | n2 | n3 | |||||
L’ | -120 | 5 | -4 | 25 | ||||
-10 | 5 | 5 | -18 | |||||
n4 | -2 | -1 | 1 | -4 | ||||
2 | -1 | -1 | 2,5 | |||||
n1 | 24 | -1 | 2 | -3 | ||||
2 | -1 | -1 | 3,5 | |||||
n5 | 18 | -2 | 4 | 5 | ||||
4 | -2 | -2 | 7 |
Таблица 1.4
b | n4 | n2 | n3 | |||||
L’ | -130 | 5 | 1 | 7 | ||||
| | | | |||||
n6 | 2 | -1 | -1 | 3,5 | ||||
| | | | |||||
n1 | 26 | -1 | -1 | 0 | ||||
| | | | |||||
n5 | 22 | -2 | 2 | 12 | ||||
| | | |
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.
Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,
где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,
(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).
№ вар. | С1 | с2 | с3 | с4 | с5 | с6 | b1 | b2 | b3 | |
29 | 0 | 5 | 1 | –1 | 1 | 0 | 2 | 2 | 10 |
Знаки ограничений | a11 | a12 | a13 | a14 | ||
1 | 2 | 3 | ||||
£ | £ | £ | –1 | 1 | 1 | 0 |
a15 | a16 | a21 | a22 | a23 | a24 | a25 | a26 |
0 | 0 | 1 | –2 | 0 | 1 | 0 | 0 |
a31 | a32 | a33 | a34 | a35 | a36 | Тип экстрем. |
2 | 1 | 1 | 1 | 2 | 0 | max |
Составим систему:
_ EMBED Equation.3 ___
Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3 ___
Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3 ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
b | x1 | x2 | x3 | x4 | x5 | ||||||||
Q | 0 | 0 | -5 | -1 | 1 | -1 | |||||||
10 | -5 | 5 | 5 | 0 | 0 | ||||||||
x6 | 2 | -1 | 1 | 1 | 0 | 0 | 2/1=2min | ||||||
2 | -1 | 1 | 1 | 0 | 0 | ||||||||
x7 | 2 | 1 | -2 | 0 | 1 | 0 | |||||||
4 | -2 | 2 | 2 | 0 | 0 | ||||||||
x8 | 10 | 2 | 1 | 1 | 1 | 2 | 10/2=5 | ||||||
-2 | 1 | -1 | -2 | 0 | 0 |
Таблица 2.2
b | x1 | x6 | x3 | x4 | x5 | ||||||||
Q | 10 | -5 | 5 | 4 | 1 | -1 | |||||||
4 | 1,5 | -1 | -1 | 0,5 | 0,5 | ||||||||
x2 | 2 | -1 | 1 | 1 | 0 | 0 | |||||||
0 | 0 | 0 | 0 | 0 | 0 | ||||||||
x7 | 6 | -1 | 2 | 2 | 1 | 0 | |||||||
0 | 0 | 0 | 0 | 0 | 0 | ||||||||
x8 | 8 | 3 | -1 | -1 | 1 | 2 | |||||||
4 | 6 | -2 | -2 | 2 | 0,5 | ||||||||
Меняем x5 и x8.
Таблица 2.3
b | x1 | x6 | x3 | x4 | x8 | |||||||
Q | 14 | -3.5 | 4,5 | 3,5 | 1,5 | 0,5 | ||||||
21 | 5,25 | -2,625 | -2,625 | 2,625 | 2,625 | |||||||
x2 | 2 | -1 | 1 | 1 | 0 | 0 | ||||||
8/3 | 2/3 | -1/3 | -1/3 | 1/3 | 1/3 | |||||||
x7 | 6 | -1 | 2 | 2 | 1 | 0 | ||||||
8/3 | 2/3 | -1/3 | -1/3 | 1/3 | 1/3 | |||||||
x5 | 4 | 1,5 | -0,5 | -1 | 0,5 | 0,5 | ||||||
8/3 | 2/3 | -1/3 | -1/3 | 1/3 | 1/3 |
Таблица 2.4
b | x5 | x6 | x3 | x4 | x8 | |
Q | 35 | 5,25 | 1,875 | 0,875 | 4,125 | 3,125 |
x2 | 14/3 | 2/3 | 2/3 | 2/3 | 1/3 | 1/3 |
x7 | 26/3 | 2/3 | 5/3 | 5/3 | 4/3 | 1/3 |
x1 | 8/3 | 2/3 | -1/3 | -1/3 | 1/3 | 1/3 |
Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица 1
№вар. | а1 | а2 | а3 | b1 | b2 | b3 | b4 | b5 | с11 | с12 | с13 |
9 | 300 | 700 | 1000 | 200 | 100 | 400 | 600 | 200 | 23 | 40 | 10 |
с14 | с15 | с21 | с22 | с23 | с24 | с25 | с31 | с32 | с33 | с34 | с35 |
12 | 21 | 25 | 21 | 20 | 50 | 18 | 15 | 30 | 32 | 25 | 50 |
Составим таблицу транспортной задачи.
Таблица 2
B1 | B2 | B3 | B4 | B5 | a | |
A1 | ||||||
23 | 40 | 10 | 12 | 21 | 300 | |
A2 | ||||||
25 | 21 | 20 | 50 | 18 | 700 | |
A3 | ||||||
15 | 30 | 32 | 25 | 50 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 |
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | ||||||
23 | 40 | 10 | 12 | 21 | 0 | 300 | |
A2 | 100 | 200 | 200 | 200 | |||
25 | 21 | 20 | 50 | 18 | 0 | 700 | |
A3 | 200 | 300 | 500 | ||||
15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___
Таблица 4
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
Таблица 5
Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800
Ответ:
Задание 4
Задача 54
Условие:
Определить экстремум целевой функции вида
( = (11(12+(22(22+(12(1(2+(1(1+(2(2
при условиях:
(11(1+(12(2<=>(1
(21(1+(22(2<=>(2 .
Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
Составить функцию Лагранжа.
Получить систему неравенств в соответствии с теоремой Куна-Таккера.
Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
1. Дать ответ с учетом условий дополняющей нежесткости.
2.
Решение:
1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min
Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max
Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ →_ EMBED Equation.3 ___
Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):
_ EMBED Equation.3 ___→ _ EMBED Equation.3 ___→ _ EMBED Equation.3 ___
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:
F’11 (х10, х20) = -8 < 0
F’12 (х10, х20) = -1,5
F’21 (х10, х20) = -1,5
F’22 (х10, х20) = 4
_ EMBED Equation.3 ___
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F’(x)+u1g1(x)+u2g2(x)=
=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3 ___)+u2(_ EMBED Equation.3 ___)
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
_ EMBED Equation.3 ___ i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А:
_ EMBED Equation.3 ___
Система В:
_ EMBED Equation.3 ___
Перепишем систему А:
_ EMBED Equation.3 ___
4)Введем новые переменные
V={v1,v2}≥0; W={w1,w2}≥0
в систему А для того, чтобы неравенства превратить в равенства:
_ EMBED Equation.3 ___
Тогда
_ EMBED Equation.3 ___.
Значит , система В примет вид:
_ EMBED Equation.3 ___ - это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
_ EMBED Equation.3 ___
Затем создадим псевдоцелевую функцию Y=My1+My2→min
Y’=-Y= -My1-My2→max.
Пусть свободные переменные: х1, х2, v1, v2, u1, u2;
а базисные y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
Решим с помощью симплекс-таблицы. Найдем опорное решение:
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | 300 | |||||
23 | 40 | 10 | 12 | 21 | 0 | ||
A2 | | 100 | 200 | | 200 | 200 | 700 |
25 | 21 | 20 | 50 | 18 | 0 | ||
A3 | 200 | 300 | 500 | 1000 | |||
15 | 30 | 32 | 25 | 50 | 0 | ||
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
Таблица 5
β1=2 | β2=8 | β3=7 | β4=12 | β5=6 | β6=-13 | a | |
α1=0 | 300 | 300 | |||||
23-2>0 | 40-8>0 | 10-7>0 | 12-12=0 | 21-6>0 | 0-(-13)>0 | ||
α2=13 | 100 | 200 | 200 | 200 | 700 | ||
25-13-2>0 | 21-8-13=0 | 20-7-13=0 | 50-12-13>0 | 18-6-13=0 | 0-13+13=0 | ||
α2=13 | 200 | 300 | 500 | 1000 | |||
15-13-2=0 | 30-13-8>0 | 32-13-7>0 | 25-13-2=0 | 50-13-6>0 | 0-13+13=0 | ||
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Тогда сумма всех перевозок:
L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800
Ответ:
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | ||||||
23 | 40 | 10 | 12 | 21 | 0 | 300 | |
A2 | 100 | 200 | 200 | 200 | |||
25 | 21 | 20 | 50 | 18 | 0 | 700 | |
A3 | 200 | 300 | 500 | ||||
15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Задание 4
Задача 54
Условие:
Определить экстремум целевой функции вида
( = (11(12+(22(22+(12(1(2+(1(1+(2(2
при условиях:
(11(1+(12(2<=>(1
(21(1+(22(2<=>(2 .
Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
Составить функцию Лагранжа.
Получить систему неравенств в соответствии с теоремой Куна-Таккера.
Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
1. Дать ответ с учетом условий дополняющей нежесткости.
2.
№ | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 | Знаки огр. 1 2 | |
31 | –7 | –2 | 4 | 1.5 | –2 | min | –2 | 1.5 | 4 | –3 | 18 | 9 | £ | ³ |
1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min
Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max
Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ →_ EMBED Equation.3 ___
Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):
_ EMBED Equation.3 ___→ _ EMBED Equation.3 ___→ _ EMBED Equation.3 ___
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:
F’11 (х10, х20) = -8 < 0
F’12 (х10, х20) = -1,5
F’21 (х10, х20) = -1,5
F’22 (х10, х20) = 4
_ EMBED Equation.3 ___
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F’(x)+u1g1(x)+u2g2(x)=
=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3 ___)+u2(_ EMBED Equation.3 ___)
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
_ EMBED Equation.3 ___ i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А:
_ EMBED Equation.3 ___
Система В:
_ EMBED Equation.3 ___
Перепишем систему А:
_ EMBED Equation.3 ___
4)Введем новые переменные
V={v1,v2}≥0; W={w1,w2}≥0
в систему А для того, чтобы неравенства превратить в равенства:
_ EMBED Equation.3 ___
Тогда
_ EMBED Equation.3 ___.
Значит , система В примет вид:
_ EMBED Equation.3 ___ - это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
_ EMBED Equation.3 ___
Затем создадим псевдоцелевую функцию Y=My1+My2→min
Y’=-Y= -My1-My2→max.
Пусть свободные переменные: х1, х2, v1, v2, u1, u2;
а базисные y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
Решим с помощью симплекс-таблицы. Найдем опорное решение:
b | x1 | x2 | u1 | u2 | v1 | v2 | |||||||||
Y'/M | -9 | -9,5 | 2,5 | 0,5 | 1 | 1 | 1 | ||||||||
8,3125 | 1,1875 | 1,7813 | -2,375 | -4,75 | -1,188 | 0 | |||||||||
y1 | 7 | 8 | 1,5 | -2 | -4 | -1 | 0 | ||||||||
0,875 | 0,125 | 0,1875 | -0,25 | -0,5 | -0,125 | 0 | |||||||||
y2 | 2 | 1,5 | -4 | 1,5 | 3 | 0 | -1 | ||||||||
-1,313 | -0,188 | -0,281 | 0,375 | 0,75 | 0,1875 | 0 | |||||||||
w1 | 18 | -2 | 1,5 | 0 | 0 | 0 | 0 | ||||||||
1,75 | 0,25 | 0,375 | -0,5 | -1 | -0,25 | 0 | |||||||||
w2 | 9 | -4 | 3 | 0 | 0 | 0 | 0 | ||||||||
3,5 | 0,5 | 0,75 | -1 | -2 | -0,5 | 0 | |||||||||
b | y1 | x2 | u1 | u2 | v1 | v2 | |||||||||
Y'/M | -0,69 | 1,1875 | 4,2813 | -1,875 | -3,75 | -0,188 | 1 | ||||||||
0,6875 | -0,188 | -4,281 | 1 | 3,75 | 0,1875 | -1 | |||||||||
x1 | 0,875 | 0,125 | 0,1875 | -0,25 | -0,5 | -0,125 | 0 | ||||||||
0,0917 | -0,025 | -0,571 | 0,1333 | 0,025 | -0,133 | ||||||||||
y2 | 0,688 | -0,188 | -4,281 | 1,875 | 3,75 | 0,1875 | -1 | ||||||||
0,3667 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | |||||||||
w1 | 19,75 | 0,25 | 1,875 | -0,5 | -1 | -0,25 | 0 | ||||||||
0,1833 | -0,05 | -1,142 | 0,2667 | 1 | 0,05 | -0,267 | |||||||||
w2 | 12,5 | 0,5 | 3,75 | -1 | -2 | -0,5 | 0 | ||||||||
0,3667 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | |||||||||
b | y1 | x2 | y2 | u2 | v1 | v2 | |||||||||
Y'/M | 0 | 1 | 0 | 1 | 0 | 0 | 0 | ||||||||
x1 | 0,967 | 0,1333 | |||||||||||||
u1 | 0,367 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | ||||||||
w1 | 19,93 | 0,2667 | |||||||||||||
w2 | 12,87 | 0,5333 | |||||||||||||
б) Условия дополняющей нежесткости выполняются (u2w2=0), значит решения исходной задачи квадратичного программирования существует.
ОТВЕТ: существует.
Литература
Курс лекций Плотникова Н. В.