Математичні методи оптимізації та дослідження операцій
Розробка математичної моделі задачі оптимізації, розв’язання її засобами "Пошук рішення" в MS Excel. Класичні методи дослідження функцій на оптимум. Графічне розв’язання задачі лінійного програмування. Метод штучного базису. Двоїстий симплекс-метод.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 26.12.2011 |
| Размер файла | 755,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ
Контрольна робота
”Математичні методи оптимізації та дослідження операцій”
студента групи ЗІнф. IVск
шифр спеціальності 6.080401
Мельника Сергія Анатолійовича
Викладач
Київ 2009
Задания
Завдання №1
Побудова математичної моделі задачі оптимізації
Мета: Навчитися розробляти математичну модель задачі за словесним описом та розв'язувати її засобами “Пошук рішення" в Excel.
Підприємство виготовляє вироби типів В1, В2, В3 для замовника. Потреба в них становить 300, 500 і 400 одиниць відповідно. Запаси сировини на вироби В1 обмежені і тому їх можна виготовити не більш ніж 350 одиниць. Всі вироби послідовно виготовляються на станках С1, С2 і С3. Норма часу обробки, планова собівартість оптова ціна підприємства на вироби приведені в таблиці.
Плановий фонд часу роботи станків є відповідно 6048, 6048 та 3932 години.
|
Показники |
Вироби та способи обробки |
|||||||||
|
В1 |
В2 |
В3 |
||||||||
|
Норма обробки в годинах: на с1 на с2 на с3 |
1 |
2 |
3 |
1 |
2 |
3 |
1 |
2 |
3 |
|
|
3 2 7 |
7 3 5 |
0 6 6 |
8 3 9 |
4 2 3 |
5 0 6 |
4 2 5 |
3 3 6 |
2 1 3 |
||
|
Планова собівартість |
13 |
15 |
11 |
26 |
20 |
25 |
19 |
20 |
18 |
|
|
Оптова ціна підприємства (у. о.) |
16 |
25 |
20 |
Побудуйте модель, на основі якої можна сформулювати екстремальну задачу знаходження плану завантаження станків, що забезпечить максимальний прибуток від продажу готової продукції.
Розв'яжіть задачу за допомогою засобів EXCEL “Пошук рішення”.
Розв'язання
Нехай х1 - деталей типу В1 оброблено першим способом, х2 - деталей типу В1 оброблено другим способом, х3 - деталей типу В1 оброблено третім способом, y1 - деталей типу В2 оброблено першим способом, y2 - деталей типу В2 оброблено другим способом, y3 - деталей типу В2 оброблено третім способом, z1 - деталей типу В3 оброблено першим способом, z2 - деталей типу В3 оброблено другим способом, z3 - деталей типу В3 оброблено третім способом. За умовою задачі
x1+x2+x3>=300
y1+y2+y3>=500
z1+z2+z3>=400
x1+x2+x3<=350
На станку с1 буде затрачено часу на обробку деталей:
3x1+7x2+0x3+8y1+4y2+5y3+4z1+3z2+2z3
На станку с2 буде затрачено часу на обробку деталей:
2x1+3x2+6x3+3y1+2y2+0y3+2z1+3z2+1z3
На станку с3 буде затрачено часу на обробку деталей:
7x1+5x2+6x3+9y1+3y2+6y3+5z1+6z2+3z3
Так, як є обмеження на фонд робочого часу станків, то повинні виконуватися нерівності:
3x1+7x2+0x3+8y1+4y2+5y3+4z1+3z2+2z3<=6048
2x1+3x2+6x3+3y1+2y2+0y3+2z1+3z2+1z3<= 6048
7x1+5x2+6x3+9y1+3y2+6y3+5z1+6z2+3z3<=3932
Прибуток від реалізації виробів становитиме:
16 (x1+x2+x3) - 13x1-15x2-11x3+25 (y1+y2+y3) - 26y1-20y2-25y3+20 (z1+z2+z3) - 19z1-20z2-18z3= 3x1+x2+5x3-y1+5y2+z1+2z3
Таким чином, отримали наступну екстремальну задачу: Знайти максимум функції
F= 3x1+x2+5x3-y1+5y2+z1+2z3max при наступних обмеженнях:
x1+x2+x3>=300
y1+y2+y3>=500
z1+z2+z3>=400
x1+x2+x3<=350
3x1+7x2+0x3+8y1+4y2+5y3+4z1+3z2+2z3<=6048
2x1+3x2+6x3+3y1+2y2+0y3+2z1+3z2+1z3<= 6048
7x1+5x2+6x3+9y1+3y2+6y3+5z1+6z2+3z3<=3932
x1>=0, x2>=0, x3>=0
y1>=0, y2>=0, y3>=0
z1>=0, z2>=0, z3>=0
Заповнюємо клітини таблиці так, як показано на малюнку
В клітину В15 заносимо формулу:
=B5*B13+C5*C13+D5*D13+E5*E13+F5*F13+ G5*G13+H5*H13+I13*I5+J13*J5
В клітину В16 заносимо формулу:
=B6*B13+C6*C13+D6*D13+E6*E13+F6*F13+ G6*G13+H6*H13+I6*I13+J13*J6
В клітину В17 заносимо формулу:
=B7*B13+C7*C13+D7*D13+E7*E13+F7*F13+ G7*G13+H7*H13+I13*I7+J13*J7
В клітину К13 заносимо формулу:
=B10*B13+C10*C13+D10*D13+E10*E13+F10*F13+G10*G13+H10*H13+I10*I13+J10*J13
В решта клітинах формули показані повністю
Викликаємо команду меню Сервис-Поиск решения.
Встановлюємо параметри пошуку розв'язку так, як показано на малюнках. Додавання нових обмежень здійснюємо через кнопку Добавить. Кнопкою Параметри встановлюємо наступні параметри роботи моделі
Для знаходження розв'язку натискаємо кнопку Выполнить. Отримали:
Видно, що задача розв'язку немає.
З таблиці видно, що не виконується обмеження на випуск виробів типу В2
|
x1 |
x2 |
x3 |
y1 |
y2 |
y3 |
z1 |
z2 |
z3 |
F |
|
|
0 |
300 |
0 |
0 |
410,667 |
0 |
0 |
0 |
400 |
3153 |
|
|
4542,7 |
<= |
6048 |
300 |
>= |
300 |
|||||
|
2121,3 |
<= |
6048 |
300 |
<= |
350 |
|||||
|
3932 |
<= |
3932 |
410,667 |
>= |
500 |
|||||
|
400 |
>= |
400 |
Завдання №2
Класичні методи дослідження функцій на оптимум
Мета: навчитися знаходити оптимум нелінійної функції методами класичної математики за допомогою першої та другої похідної
завдання виконуються без використання комп'ютера.
Розв'язання
1. Знайдемо стаціонарні точки:
Розв'язком системи рівнянь є точка (x1*, x2*, x3*) = (0.5; 0; 0).
2. Матриця других похідних має вигляд:
3. Перевіримо кутові мінори:
4. Так, як кутові мінори мають різні знаки, то в стаціонарній точці (x1*, x2*, x3*) = (0.5; 0; 0) немає екстремуму.
Завдання №3
Рішення задачі безумовної оптимізації
Мета:
1) набуття навичок знаходження оптимуму задачі безумовної одновимірної оптимізації наближеними методами без використання інформації про похідну:
методом повного перебору;
методом рівномірного пошуку;
методом дихотомічного пошуку;
методом золотого перерізу;
методом Фібоначчі.
2) набуття навичок знаходження оптимуму задачі безумовної одновимірної оптимізації наближеними методами з використанням інформації про похідну:
методом ділення навпіл;
методом Ньютона.
Розв'язання
Завдання 3 (3- (1) - пункт (1)) - рішення задачі безумовної оптимізації методом повного перебору, потребує розробки програми для знаходження оптимуму функції,
методом повного перебору;
Текст програми
program perebor;
Uses wincrt;
Const xp=-0.5; xk=2;
Var h, y, x, xmin, ymin, ymax, xmax: real;
begin
write ('Введіть крок: ');
readln (h);
x: =xp;
ymin: =0.5*x*x*x-13*sqr (x) +6*x-2;
ymax: =ymin;
xmin: =x;
xmax: =x;
x: =x+h;
while x<=xk do
begin
y: =0.5*x*x*x-13*sqr (x) +6*x-2;
if y>ymax then begin ymax: =y; xmax: =x; end;
if y<ymin then begin ymin: =y; xmin: =x; end;
x: =x+h;
end;
writeln ('При х=',xmin: 8: 4,' ymin=',ymin: 10: 5);
writeln ('При х=',xmax: 8: 4,' ymax=',ymax: 10: 5);
end.
Результат:
Завдання 3 (3- (1) - пункти (2-5)) - рішення задачі безумовної оптимізації, потребує розробки програми для знаходження оптимуму функції, причому студент досліджує свою функцію одним з самостійно обраних методів з пунктів (2-5) без використання інформації про похідну
методом дихотомічного пошуку;
Знайдемо максимум функції при
Текст програми
Const xp=-0.5; xk=2.0; eps=0.001; L=0.01;
Var yk, zk, ak, bk, yy, yz: real;
k: integer;
begin
ak: =xp; bk: =xk;
k: =0;
writeln (' ak bk yk zk yy yz'); while bk-ak>L do
begin
yk: = (ak+bk) /2-eps;
zk: = (ak+bk) /2+eps;
yy: =0.5*yk*yk*yk-13*sqr (yk) +6*yk-2;
yz: =0.5*zk*zk*zk-13*sqr (zk) +6*zk-2;
if - yy<-yz then bk: =zk
else ak: =yk;
k: =k+1;
writeln (ak: 8: 4,bk: 8: 4,yk: 8: 4,zk: 8: 4,yy: 9: 5,yz: 9: 5);
end;
yk: = (ak+bk) /2;
yy: =0.5*yk*yk*yk-13*sqr (yk) +6*yk-2;
writeln ('При х=',yk: 8: 4,' ymax=',yy: 10: 5,' k=',k);
end.
Результат:
Завдання 3 (3- (2) - пункти (1-2)) - рішення задачі безумовної оптимізації, потребує розробки програми для знаходження оптимуму функції, студент досліджує свою функцію одним з двох обраних методів з використанням інформації про похідну.
методом Ньютона.
Знайдемо першу та другу похідну для функції y:
На всьому проміжку [-0,5; 2] друга похідна не дорівнює нулю
Текст програми
program nuton;
Uses wincrt;
Const xp=-0.5; xk=2.0; eps=0.001;
Var y1p, y2p, ak, bk, y, x1, x2: real;
k: integer;
begin
ak: =xp; bk: =xk;
k: =0;
writeln (' k x1 y1p y2p x2 abs (x1-x2) y');
x2: = (xp+xk) /2;
repeat
x1: =x2;
y1p: =1.5*sqr (x1) - 26*x1+6;
y2p: =3*x1-26;
x2: =x1-y1p/y2p;
k: =k+1;
writeln (k: 3,x1: 8: 4,y1p: 9: 4,y2p: 9: 4,x2: 8: 4,abs (x1-x2): 9: 5,0.5*x2*x2*x2-13*sqr (x2) +6*x2-2: 10: 5);
until abs (x2-x1) <eps;
end.
Результат:
Завдання №4
Графічне розв'язання задачі лінійного програмування
Мета - опанувати ідею розв'язання задачі лінійного програмування та набути навиків розв'язування їх графічним методом
Розв'язання
Розв'яжемо задачу графічним способом. Для цього в системі координат Х10Х2 побудуємо рівняння прямих: x1+x2=3; x1-x2=3; - 6x1+4x2=12; x1=1, x2=4. Відмітимо стрілками ті півплощини, які задовільняють кожній відповідній нерівності системи нерівностей стандартній формі запису задачі. Перетин півплощин - чотирикутник АBСD, який є областю допустимих розв'язків задачі. Далі будуємо вектор F (6,1) і перпендикулярно до нього пряму, яка проходить через точку (0,0). Пересуваємо цю пряму в напрямку вектора F до тих пір, поки вона не доторкнеться першої точки області допустимих значень. Це точка B.
Координати точки B знаходимо з рівнянь x1+x2=3 та x1=1. Маємо x1=1 x2=2;. В цій точці функція F набуває свого найменшого значення
6*1+1*2+3=10.
Завдання №5
Симплекс-метод
Мета - навчитися знаходити початковий опорний план, здійснювати перехід до іншого опорного плану та обчислювати оптимальний план задачі лінійного програмування за критерієм оптимальності.
Розв'язання. Розв'язання задачі здійснюється поетапно. Етап 1. Знайдемо початковий опорний план. Для цього за допомогою додаткових змінних зведемо задачу до канонічної форми. Оскільки цільова функція прямує до мінімуму, то її запишемо у вигляді: . Обмеження: нерівності зведемо до рівностей введенням додаткових змінних . Задача в канонічній формі має такий вигляд:
Запишемо систему обмежень у векторній формі:
де - - вимірний вектор-стовпець коефіцієнтів при (j=1,…,6) - - вимірний вектор-стовпець вільних членів системи
; ; ; ; ; ; .
Вектори A4, A5, A6 - одиничні і лінійно-незалежні між собою вектори. Вони утворюють базис. Змінні x4, x5, x6 називаються базисними, змінні x1, x2, x3 - вільними і прирівнюються до нуля. У результаті отримуємо
або
Оскільки праворуч стоять всі невід'ємні коефіцієнти, а вектори A4, A5, A6 - лінійно-незалежні одиничні, то отримаємо початковий опорний план:
Етап 2. Складаємо симплекс-таблицю (табл.1) і перевіряємо цей план на оптимальність.
Таблиця 1
|
і |
Базис |
Сбаз |
A0 |
C1=2 |
C2=-1 |
C3=3 |
||||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A4 |
0 |
8 |
3 |
0 |
-1 |
1 |
0 |
0 |
|
|
2 |
A5 |
0 |
6 |
2 |
1 |
-3 |
0 |
1 |
0 |
|
|
3 |
A6 |
0 |
1 |
-1 |
1 |
4 |
0 |
0 |
1 |
|
|
m+1 |
1=-2 |
2=1 |
3=-3 |
4=0 |
5=0 |
6=0 |
Перший стовпець містить номер рядка (обмеження), другий - базисні вектори. Оскільки x4, x5, x6 - базисні змінні, то відповідні їм вектори A4, A5, A6 - базисні. Третій стовпець Сбаз - коефіцієнти цільової функції при базисних векторах c4=0, c5=0, c6=0. Стовпець A0 - коефіцієнти опорного рішення. Оскільки x4, x5, x6 дорівнюють правим частинам обмежень, то ці значення записуємо у стовпець A0. В перший рядок табл.1 записуємо значення цільової функції c1=2, c2=-1, c3=3, c4=0, c5=0, c6=0
У стовпцях A1, A2, A3, A4, A5, A6 записуємо відповідні коефіцієнти в обмеженнях задачі при невідомих x1, x2, x3, x4, x5, x6.
У (m+1) рядку підраховуємо значення цільової функції на даному опорному плані. Значення дорівнює скалярному добутку вектора на вектор A0:
Оцінки в (m+1) рядку обчислюються за формулою
тобто від скалярного добутку вектора на вектор віднімаємо значення коефіцієнта цільової функції . Так,
Зазначимо, що в (m+1) рядку базисним змінним завжди відповідають оцінки . Тому далі на відповідних позиціях можна ставити нулі.
Оскільки серед оцінок є від'ємні числа, то опорний план (0; 0; 0; 8; 6;
1) не є оптимальним і необхідно перейти до наступного опорного плану.
Етап 3. Для збільшення значення цільової функції (задача, яку розв'язуємо на максимум) серед оцінок треба вибрати найменшу - це . Стовпець A3 тепер називаємо розв'язуваним (напрямним) і A3 вводимо в базис.
Далі визначаємо розв'язуваний рядок. Для цього обчислюємо відношення компонент вектора A0 до додатних компонент вектора, який вводимо в базис (A3), і серед них обираємо найменше значення
Рядок, який відповідає мінімальному відношенню, називається розв'язувальним. Вектор A6 виводимо з базису.
Елемент, що стоїть на перетині розв'язуваного рядка і розв'язуваного стовпця, називається розв'язуваним елементом.
Далі, використовуючи жорданові виключення, перераховуємо всі елементи таблиці. Знаходимо новий опорний план у новому базисі (табл.2).
Таблиця 2
|
і |
Базис |
Сбаз |
A0 |
C1=2 |
C2=-1 |
C3=3 |
||||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A4 |
0 |
8,25 |
2,75 |
0,25 |
0 |
1 |
0 |
0,25 |
|
|
2 |
A5 |
0 |
6,75 |
1,25 |
1 |
0 |
0 |
1 |
0,75 |
|
|
3 |
A3 |
3 |
0,25 |
-0,25 |
0,25 |
1 |
0 |
0 |
0,25 |
|
|
m+1 |
0,75 |
-2,75 |
1,75 |
0 |
0 |
0 |
0,75 |
У табл.2 в стовпці “Базис” замість A6 записуємо вектор A3.
У стовпці проти A3 записуємо значення коефіцієнта цільової функції с3 = 3.
У стовпцях A3, A4, A5, які відповідають базисним векторам, записуємо одиничні вектори. Підраховуємо елементи нової симплекс-таблиці.
Всі елементи розв'язуваного рядка (крім ) ділимо на розв'язуваний елемент. Інші елементи табл.2 перераховуємо за формулою жорданових виключень за правилом прямокутника.
Стовпці: ,
,
,
Далі обчислюємо коефіцієнти (m+1) рядка.
В табл.2 в рядку <0, і тому новий опорний план також не є оптимальним, його можна поліпшити за рахунок введення в базис вектора A1. Тепер розв'язуваний стовпець - A1.
Визначимо розв'язуваний рядок. Для цього обчислимо . Отже, 2,75 є розв'язуваним елементом, перший рядок - розв'язуваний, вектор A4 слід вивести з базису.
Аналогічно здійснюємо розрахунки симплекс-таблиць. Результати наведено табл.3.
Таблиця 3
|
і |
Базис |
Сбаз |
A0 |
C1=2 |
C2=-1 |
C3=3 |
||||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A1 |
2 |
3 |
1 |
0,09091 |
0 |
0,36364 |
0 |
0,09091 |
|
|
2 |
A5 |
0 |
3 |
0 |
1,63636 |
0 |
-0,4545 |
1 |
0,63636 |
|
|
3 |
A3 |
3 |
1 |
0 |
0,27273 |
1 |
0,09091 |
0 |
0,27273 |
|
|
m+1 |
9 |
0 |
2 |
0 |
1 |
0 |
1 |
Оскільки всі оцінки , то отриманий опорний план є оптимальним. Максимальне значення цільової функції . Оскільки початкова задача була на мінімум цільової функції, то .
Завдання №6
Розв'язання задачі лінійного програмування з використанням методу штучного базису
Мета - навчитися розв'язувати задачу лінійного програмування з використанням штучного базису
Розв'язання
Зведемо задачу до канонічної форми:
Запишемо систему обмежень у векторній формі:
де
Кількість обмежень . Оскільки серед векторів немає ще двох одиничних векторів, то складаємо розширену задачу і вводимо штучні змінні .
де - деяке досить велике додатне число, конкретне значення якого не задається.
Вектори і одиничні, вони утворюють базис. Змінні і - базисні, змінні - вільні і прирівнюються до нуля. Опорний план розширеної задачі буде мати вигляд:
Xоп= (x1=0; x2=0; x3=0; x4=0; x5=2; x6=0; x7=5; x8=3;).
Використовуючи симплекс-метод для розширеної задачі, поступово вводимо в базис основні змінні замість штучних.
Після обмеженого числа ітерацій всі штучні змінні повинні бути виведені з базису.
Побудуємо симплекс-табл.4.
Таблиця 4
|
i |
Базис |
A0 |
C1=-5 |
C2=-2 |
C3=3 |
C4=-1 |
C5=0 |
C6=0 |
C7=-M |
C8=-M |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
|||||
|
1 |
A7 |
-М |
5 |
2 |
-1 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
2 |
A5 |
0 |
2 |
1 |
1 |
-1 |
1 |
1 |
0 |
0 |
0 |
|
|
3 |
A8 |
-M |
3 |
5 |
-8 |
2 |
4 |
0 |
-1 |
0 |
1 |
|
|
m+1 |
0 |
5 |
2 |
-3 |
1 |
0 |
0 |
0 |
0 |
|||
|
m+2 |
-8 |
-7 |
9 |
-3 |
-5 |
0 |
M |
0 |
0 |
Обчислимо і :
У рядок записуємо числа без , а в рядок записуємо коефіцієнти при М.
Оскільки в рядку серед величин є від'ємні, то початковий опорний план розширеної задачі не є оптимальним. Треба перейти до наступного опорного плану. Обчислення виконуємо за допомогою симплекс-методу, однак розв'язуваний стовпець обираємо серед елементів рядка. Розв'язуваний стовпець відповідає найбільшому за абсолютною величиною від'ємному елементу рядка - це - 7. Вектор, який вводиться, - . Знаходимо величину Розв'язуваний рядок - третій. Розв'язуваний елемент дорівнює 5.
Отже, з базису виведемо штучний вектор , коефіцієнти якого далі перераховувати не потрібно, а в базис вводимо вектор .
Використовуючи жорданові виключення перерахуємо елементи (табл.5).
Таблиця 5
|
i |
Базис |
A0 |
C1=-5 |
C2=-2 |
C3=3 |
C4=-1 |
C5=0 |
C6=0 |
C7=-M |
C8=-M |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
|||||
|
1 |
A7 |
-М |
3,8 |
0 |
2,2 |
0,2 |
-0,6 |
0 |
0,4 |
1 |
||
|
2 |
A5 |
0 |
1,4 |
0 |
2,6 |
-1,4 |
0,2 |
1 |
0,2 |
0 |
||
|
3 |
A1 |
-5 |
0,6 |
1 |
-1,6 |
0,4 |
0,8 |
0 |
-0,2 |
0 |
||
|
m+1 |
-3 |
0 |
10 |
-2,6 |
-3 |
0 |
1 |
0 |
||||
|
m+2 |
-3,8 |
0 |
-2,2 |
-0,2 |
-0,6 |
0 |
-0,4 |
0 |
Найбільше за абсолютною величиною від'ємне число рядка - 2,2. Вектор, який вводиться, - A2. Знаходимо величину Розв'язуваний рядок - другий. Розв'язуваний елемент дорівнює 2,6. Отже, з базису виведемо вектор A5.
Використовуючи жорданові виключення перерахуємо елементи (табл.6).
Таблиця 6
|
i |
Ба-зис |
A0 |
C1=-5 |
C2=-2 |
C3=3 |
C4=-1 |
C5=0 |
C6=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A7 |
-М |
2,615385 |
0 |
0 |
1,38462 |
-0,7692 |
-0,8462 |
0,23077 |
|
|
2 |
A2 |
-2 |
0,538462 |
0 |
1 |
-0,5385 |
0,07692 |
0,38462 |
0,07692 |
|
|
3 |
A1 |
-5 |
1,461538 |
1 |
0 |
-0,4615 |
0,92308 |
0,61538 |
-0,0769 |
|
|
m+1 |
-2,7 |
0 |
0 |
0,38 |
-3,77 |
-3,846 |
0,23 |
|||
|
m+2 |
-2,6 |
0 |
0 |
-1,38 |
-0,76 |
0,84 |
-0,23 |
Найбільше за абсолютною величиною від'ємне число рядка - 1,38. Вектор, який вводиться, - A3. Знаходимо величину Розв'язуваний рядок - перший. Розв'язуваний елемент дорівнює 1,38462. Отже, з базису виведемо вектор A7, коефіцієнти якого далі перераховувати не потрібно. Використовуючи жорданові виключення перерахуємо елементи (табл.7).
Таблиця 7
|
i |
Базис |
A0 |
C1=-5 |
C2=-2 |
C3=3 |
C4=-1 |
C5=0 |
C6=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A3 |
3 |
1,88889 |
0 |
0 |
1 |
-0,5556 |
-0,6111 |
0,16667 |
|
|
2 |
A2 |
-2 |
1,55556 |
0 |
1 |
0 |
-0,2222 |
0,05556 |
0,16667 |
|
|
3 |
A1 |
-5 |
2,33333 |
1 |
0 |
0 |
0,66667 |
0,33333 |
0 |
|
|
m+1 |
-9,1111 |
0 |
0 |
0 |
-3,5556 |
-3,6111 |
0,16667 |
|||
|
m+2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Найбільше за абсолютною величиною від'ємне число (m+1) рядка - 3,61. Вектор, який вводиться, - A4. Знаходимо величину . Розв'язуваний рядок - третій. Розв'язуваний елемент дорівнює 0,33333.
Отже, з базису виведемо вектор A1. Використовуючи жорданові виключення перерахуємо елементи (табл.8).
Таблиця 8
|
i |
Ба-зис |
A0 |
C1=-5 |
C2=-2 |
C3=3 |
C4=-1 |
C5=0 |
C6=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||||
|
1 |
A3 |
3 |
6,166667 |
1,83333 |
0 |
1 |
0,66667 |
0 |
0,16667 |
|
|
2 |
A2 |
-2 |
1,166667 |
-0,1667 |
1 |
0 |
-0,3333 |
0 |
0,16667 |
|
|
3 |
A5 |
0 |
7 |
3 |
0 |
0 |
2 |
1 |
0 |
|
|
m+1 |
16,16667 |
10,8333 |
0 |
0 |
3,66667 |
0 |
0,16667 |
|||
|
m+2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
У табл.8 всі . Опорний план Xоп= (0; 1,166667; 6,166667; 0; 7; 0).
Xоп= (0; 1,166667; 6,166667; 0; 7; 0) є оптимальним планом задачі і . Оскільки початкова задача була на мінімум цільової функції, то .
Завдання №7
Розв'язання задачі двоїстим симплекс-методом
Мета - навчитися будувати двоїсті задачі, розуміти економічну інтерпретацію двоїстих задач та визначати початковий опорний план двоїстим симплекс - методом.
Розв'язання. Запишемо двоїсту задачу до заданої. Для цього:
1. Всі нерівності системи обмежень є виду " ? "
2. Складемо цільову функцію двоїстої задачі
Число змінних двоїстої задачі дорівнює числу обмежень прямої.
3. Запишемо матрицю А коефіцієнтів при змінних отриманої системи і транспонуємо її.
;
4. Запишемо систему обмежень двоїстої задачі:
; .
Розв'яжемо пряму задачу. Для цього зведемо її до канонічної форми:
при обмеженнях
Запишемо систему обмежень у векторній формі:
де ; ; ; ; ;
Розв'язання задачі будемо здійснювати двоїстим симплекс-методом поетапно.
метод оптимізація симплекс математичний
Етап 1. Знайдемо псевдоплан прямої задачі, зведеної до канонічної форми. Помножимо перше і друге рівняння системи обмежень на (-1) і отримаємо таку задачу:
при обмеженнях
Вектор є розв'язком системи лінійних рівнянь, але цей розв'язок не може бути оптимальним планом задачі, оскільки серед його компонент є від'ємні числа. Такий розв'язок (план) називається псевдопланом задачі.
Етап 2. Складаємо симплекс-таблицю (табл.9)
Таблиця 9
|
i |
Базис |
A0 |
C1=-8 |
C2=-8 |
C3=-20 |
C4=0 |
C5=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
|||||
|
1 |
A4 |
0 |
-2 |
-1 |
4 |
-2 |
1 |
0 |
|
|
2 |
A5 |
0 |
-1 |
2 |
-1 |
-2 |
0 |
1 |
|
|
m+1 |
0 |
8 |
8 |
20 |
0 |
0 |
З табл.9 бачимо, що планом двоїстої задачі є вектор Y (0,0) Компоненти оптимального плану двоїстої задачі збігаються з відповідними числами рядка симплекс-таблиці розв'язку прямої задачі. Ці числа стоять у стовпцях векторів, які відповідають додатковим змінним. Значення цільової функції на цьому плані
Оскільки в рядку від'ємних чисел немає, а серед чисел стовпця вектора A0 є два від'ємних числа (-2 і -1), то згідно з двоїстим симплекс-методом можна перейти до повної симплекс-таблиці. В нашому прикладі це можна зробити, оскільки в рядках векторів A4 і A5 є від'ємні числа. Якщо в цих рядках всі числа додатні, то задача розв'язку немає.
Етап 3. Щоб перейти до наступного псевдоплану, треба вибрати розв'язуваний рядок і розв'язуваний стовпець. Вектор, що підлягає виведенню з базису, визначаємо так: серед від'ємних чисел стовпця A0 вибираємо найбільше за абсолютною величиною значення. В нашому прикладі це 2. Таким чином, з базису виводимо вектор A4. Рядок A4 є розв'язуваним, його вилучаємо з базису.
Далі визначаємо, який вектор треба ввести в базис. Обчислюємо відношення компонент (m+1) рядка до відповідних від'ємних компонент вектора, який вводимо в базис A4, і серед них обираємо найменше значення за абсолютною величиною
для всіх <0.
Маємо
Стовпець, який відповідає мінімальному відношенню, є вектор A3, його вводимо в базис. Використовуючи жорданові виключення переходимо до нової симплекс-таблиці (табл.10).
Таблиця 10
|
i |
Базис |
A0 |
C1=-8 |
C2=-8 |
C3=-20 |
C4=0 |
C5=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
|||||
|
1 |
A3 |
-20 |
1 |
0,5 |
-2 |
1 |
-0,5 |
0 |
|
|
2 |
A5 |
0 |
1 |
3 |
-5 |
0 |
-1 |
1 |
|
|
m+1 |
-20 |
-2 |
48 |
0 |
10 |
0 |
З табл.10 видно, що отримано новий план двоїстої задачі Y (10; 0). Значення цільової функції на цьому плані Отже, двоїстий симплекс-метод дає можливість здійснювати перехід від одного плану двоїстої задачі до іншого.
В стовпці немає від'ємних чисел, але в рядку оцінок є одне від'ємне число. Зробимо перетворення таблиці звичайним симплекс-методом (табл.11).
Таблиця 11
|
i |
Базис |
A0 |
C1=-8 |
C2=-8 |
C3=-20 |
C4=0 |
C5=0 |
||
|
A1 |
A2 |
A3 |
A4 |
A5 |
|||||
|
1 |
A3 |
-20 |
0,83333 |
0 |
-1,1667 |
1 |
-0,3333 |
-0,1667 |
|
|
2 |
A1 |
-8 |
0,33333 |
1 |
-1,6667 |
0 |
-0,3333 |
0,33333 |
|
|
m+1 |
-19,333 |
0 |
44,6667 |
0 |
9,33333 |
0,66667 |
Оскільки, всі оцінки а в стовпці немає від'ємних чисел, то в табл.11 знайдено оптимальний план прямої та двоїстої задач. = (1/3, 0, 5/6, 0, 0) та = (28/3; 2/3). На цих планах значення цільових функцій прямої та двоїстої задач рівні:
Шукане мінімальне значення задачі буде
Змінні двоїстої задачі, як зазначалось вище, позначають умовні двоїсті оцінки, які визначають дефіцитність.
Застосування двоїстого симплекс-методу особливо ефективне під час аналізу моделі на чутливість.
Завдання №8
Розв'язання задачі цілочислового програмування
Мета - навчитися будувати відсікання Гоморі та знаходити оптимальний план задачі цілочислового лінійного програмування за критерієм оптимальності
Розв'язання
Симплекс-методом знаходимо оптимальний план задачі, не враховуючи вимоги цілочисельності змінних. Для цього зведемо її до канонічної форми веденням додаткових змінних:
; , x1, x2 - цілі.
Складаємо симплекс-таблицю (табл.12) і проводимо в ній розрахунки.
Таблиця 12
|
І |
Базис |
Сбаз |
А0 |
С1=2 |
С2=1 |
С3=0 |
С4=0 |
||
|
А1 |
А2 |
А3 |
А4 |
||||||
|
1 |
А3 |
0 |
7 |
1 |
1 |
1 |
0 |
7 |
|
|
2 |
А4 |
0 |
5 |
4 |
-5 |
0 |
1 |
5/4 |
|
|
m+1 |
0 |
-2 |
-1 |
0 |
0 |
||||
|
1 |
А3 |
0 |
23/4 |
0 |
9/4 |
1 |
-1/4 |
23/9 |
|
|
2 |
А1 |
2 |
5/4 |
1 |
-5/4 |
0 |
1/4 |
||
|
m+1 |
5/2 |
0 |
-7/2 |
0 |
0,5 |
||||
|
1 |
А2 |
1 |
23/9 |
0 |
1 |
4/9 |
-1/9 |
||
|
2 |
А1 |
2 |
40/9 |
1 |
0 |
5/9 |
1/9 |
||
|
m+1 |
103/9 |
0 |
0 |
14/9 |
1/9 |
З табл.12 видно, що в (m+1) рядку всі Аj0, критерій оптимальності виконується. Оптимальний план задачі має вид Хопт = (23/9; 40/9; 0; 0).
Цей план містить дробові компоненти і не задовольняє умові цілочисельності задачі.
Оскільки у компоненти x2 дробова частина більше ніж у x1, то для неї складаємо додаткове обмеження Гоморі. З останньої симплекс-таблиці 12 маємо:
Дописуємо це обмеження в таблицю і отримуємо табл.13.
Таблиця 13
|
І |
Базис |
Сбаз |
А0 |
С1=2 |
С2=1 |
С3=0 |
С4=0 |
С5=0 |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
|||||
|
1 |
А2 |
1 |
23/9 |
0 |
1 |
4/9 |
-1/9 |
0 |
|
|
2 |
А1 |
2 |
40/9 |
1 |
0 |
5/9 |
1/9 |
0 |
|
|
3 |
А5 |
0 |
-5/9 |
0 |
0 |
-4/9 |
-8/9 |
1 |
|
|
m+1 |
103/9 |
0 |
0 |
14/9 |
1/9 |
0 |
|||
|
1 |
А2 |
1 |
21/8 |
0 |
1 |
1/2 |
0 |
-1/8 |
|
|
2 |
А1 |
2 |
35/8 |
1 |
0 |
1/2 |
0 |
1/8 |
|
|
3 |
А4 |
0 |
5/8 |
0 |
0 |
1/2 |
1 |
-9/8 |
|
|
m+1 |
91/8 |
0 |
0 |
14/9 |
1/9 |
0 |
Оскільки в стовпчику А0 є від'ємна компонента - 5/9, то опорний план Х= (x1=40/9; x2=23/9; x3=0; x4=0; x5=-5/9) є псевдопланом і згідно з двоїстим симплекс-методом вектор А5, виводимо з базису, а на його місце вводимо в базис вектор А4 згідно з мінімумом відношення
Перераховуємо елементи симплекс-таблиці (табл.13), використовуючи елемент - 8/9 як розв'язувальний елемент.
Оскільки у компоненти x2 дробова частина більше ніж у x1, то для неї складаємо додаткове обмеження Гоморі. З останньої симплекс-таблиці 13 маємо:
Дописуємо це обмеження в таблицю і отримуємо табл.14.
Таблиця 14
|
І |
Базис |
Сбаз |
А0 |
С1=2 |
С2=1 |
С3=0 |
С4=0 |
С5=0 |
С6=0 |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
|||||
|
1 |
А2 |
1 |
21/8 |
0 |
1 |
1/2 |
0 |
-1/8 |
0 |
|
|
2 |
А1 |
2 |
35/8 |
1 |
0 |
1/2 |
0 |
1/8 |
0 |
|
|
3 |
А4 |
0 |
5/8 |
0 |
0 |
1/2 |
1 |
-9/8 |
0 |
|
|
4 |
А6 |
0 |
-5/8 |
0 |
0 |
-1/2 |
0 |
-7/8 |
1 |
|
|
m+1 |
103/9 |
0 |
0 |
14/9 |
1/9 |
0 |
0 |
|||
|
1 |
А2 |
1 |
19/7 |
0 |
1 |
4/7 |
0 |
0 |
-1/7 |
|
|
2 |
А1 |
2 |
30/7 |
1 |
0 |
3/7 |
0 |
0 |
1/7 |
|
|
3 |
А4 |
0 |
10/7 |
0 |
0 |
8/7 |
1 |
0 |
-9/7 |
|
|
4 |
А5 |
0 |
5/7 |
0 |
0 |
4/7 |
0 |
1 |
-8/7 |
|
|
m+1 |
79/7 |
0 |
0 |
10/7 |
0 |
0 |
1/7 |
Далі виконуємо аналогічні дії
Таблиця 15
|
І |
Базис |
Сбаз |
А0 |
С1=2 |
С2=1 |
С3=0 |
С4=0 |
С5=0 |
С6=0 |
С7=0 |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|||||
|
1 |
А2 |
1 |
19/7 |
0 |
1 |
4/7 |
0 |
0 |
-1/7 |
0 |
|
|
2 |
А1 |
2 |
30/7 |
1 |
0 |
3/7 |
0 |
0 |
1/7 |
0 |
|
|
3 |
А4 |
0 |
10/7 |
0 |
0 |
8/7 |
1 |
0 |
-9/7 |
0 |
|
|
4 |
А5 |
0 |
5/7 |
0 |
0 |
4/7 |
0 |
-1 |
-8/7 |
0 |
|
|
5 |
А7 |
0 |
-5/7 |
0 |
1 |
-4/7 |
0 |
0 |
-6/7 |
1 |
|
|
m+1 |
79/7 |
0 |
0 |
10/7 |
0 |
0 |
1/7 |
0 |
|||
|
1 |
А2 |
1 |
17/6 |
0 |
1 |
2/3 |
0 |
0 |
0 |
-1/6 |
|
|
2 |
А1 |
2 |
25/6 |
1 |
0 |
1/3 |
0 |
0 |
0 |
1/6 |
|
|
3 |
А4 |
0 |
15/6 |
0 |
0 |
2 |
1 |
0 |
0 |
-9/6 |
|
|
4 |
А5 |
0 |
10/6 |
0 |
0 |
4/3 |
0 |
1 |
0 |
-8/6 |
|
|
5 |
А6 |
0 |
5/6 |
0 |
0 |
2/3 |
0 |
0 |
1 |
-7/6 |
|
|
m+1 |
67/6 |
0 |
0 |
4/3 |
0 |
0 |
0 |
1/6 |
|||
Таблиця 15
|
І |
Базис |
Сбаз |
А0 |
С1=2 |
С2=1 |
С3=0 |
С4=0 |
С5=0 |
С6=0 |
С7=0 |
С8=0 |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
А8 |
|||||
|
1 |
А2 |
1 |
17/6 |
0 |
1 |
2/3 |
0 |
0 |
0 |
-1/6 |
0 |
|
|
2 |
А1 |
2 |
25/6 |
1 |
0 |
1/3 |
0 |
0 |
0 |
1/6 |
0 |
|
|
3 |
А4 |
0 |
15/6 |
0 |
0 |
2 |
1 |
0 |
0 |
-9/6 |
0 |
|
|
4 |
А5 |
0 |
10/6 |
0 |
0 |
4/3 |
0 |
1 |
0 |
-8/6 |
0 |
|
|
5 |
А6 |
0 |
5/6 |
0 |
0 |
2/3 |
0 |
0 |
1 |
-7/6 |
0 |
|
|
6 |
А8 |
0 |
-5/6 |
0 |
0 |
-2/3 |
0 |
0 |
0 |
-5/6 |
1 |
|
|
m+1 |
67/6 |
0 |
0 |
4/3 |
0 |
0 |
0 |
1/6 |
0 |
|||
|
1 |
А2 |
1 |
3 |
0 |
1 |
0,8 |
0 |
0 |
0 |
0 |
-0,2 |
|
|
2 |
А1 |
2 |
4 |
1 |
0 |
0,2 |
0 |
0 |
0 |
0 |
0,2 |
|
|
3 |
А4 |
0 |
4 |
0 |
0 |
3,2 |
1 |
0 |
0 |
0 |
-1,8 |
|
|
4 |
А5 |
0 |
3 |
0 |
0 |
2,4 |
0 |
1 |
0 |
0 |
-1,6 |
|
|
5 |
А6 |
0 |
2 |
0 |
0 |
1,6 |
0 |
0 |
1 |
0 |
-1,4 |
|
|
6 |
А7 |
0 |
1 |
0 |
0 |
0,8 |
0 |
0 |
0 |
1 |
-1,2 |
|
|
m+1 |
11 |
0 |
0 |
1,2 |
0 |
0 |
0 |
0 |
0,2 |
3 таблиці 15 бачимо, що початкова задача цілочислового програмування має оптимальний план:
Хопт=
На цьому плані значення цільової функції дорівнює Fmax=11.
Завдання №9
Розв'язання задачі лінійного програмування за допомогою модифікованого симплекс-методу
Мета - навчитися використовувати модифікований симплекс-метод та знаходити оптимальний план задачі цілочислового лінійного програмування за критерієм оптимальності
F = 5x1 + 2 x2 - 3 x3 + x4 min
2 x1 - x2 + x3 + x4 = 5
x1 + x2 - x3 + x 4 ? 2
5 x1 - 8x2 + 2 x3 + 4 x4 ?3
x1,…,x4 ? 0.
Розв'язання
Етап 1. Знайдемо псевдоплан прямої задачі, зведеної до канонічної форми.
при обмеженнях
Симплекс-методом знаходимо оптимальний план задачі, не враховуючи вимоги цілочисельності змінних. Для цього зведемо її до канонічної форми веденням додаткових змінних: x1, x2, x3, x4 - цілі.
Складаємо симплекс-таблицю (табл.16) і проводимо в ній розрахунки.
Таблиця 16
|
І |
Базис |
Сбаз |
А0 |
С1=-5 |
С2=-2 |
С3=3 |
С4=-1 |
С5=0 |
С6=0 |
С7=0 |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|||||
|
1 |
А5 |
0 |
5 |
2 |
-1 |
1 |
1 |
1 |
0 |
0 |
|
|
2 |
А6 |
0 |
2 |
1 |
1 |
-1 |
1 |
0 |
1 |
0 |
|
|
3 |
А7 |
0 |
-3 |
-5 |
8 |
-2 |
-4 |
0 |
0 |
1 |
|
|
m+1 |
0 |
5 |
2 |
-3 |
1 |
0 |
0 |
0 |
|||
|
1 |
А5 |
0 |
4,25 |
0,75 |
1 |
0,5 |
0 |
1 |
0 |
0,25 |
|
|
2 |
А6 |
0 |
1,25 |
-0,25 |
3 |
-1,5 |
0 |
0 |
1 |
0,25 |
|
|
3 |
А4 |
-1 |
0,75 |
1,25 |
-2 |
0,5 |
1 |
0 |
0 |
-0,25 |
|
|
m+1 |
-0,75 |
3,75 |
4 |
-3,5 |
0 |
0 |
0 |
0,25 |
|||
|
1 |
А5 |
0 |
3,5 |
-0,5 |
3 |
0 |
-1 |
1 |
0 |
0,5 |
|
|
2 |
А6 |
0 |
3,5 |
3,5 |
-3 |
0 |
3 |
0 |
1 |
-0,5 |
|
|
3 |
А3 |
3 |
1,5 |
2,5 |
-4 |
1 |
2 |
0 |
0 |
-0,5 |
|
|
m+1 |
4,5 |
12,5 |
-10 |
0 |
7 |
0 |
0 |
-1,5 |
|||
|
1 |
А2 |
-2 |
7/6 |
-1/6 |
1 |
0 |
-1/3 |
1/3 |
0 |
1/6 |
|
|
2 |
А6 |
0 |
7 |
3 |
0 |
0 |
2 |
1 |
1 |
0 |
|
|
3 |
А3 |
3 |
37/6 |
11/6 |
0 |
1 |
2/3 |
4/3 |
0 |
1/6 |
|
|
m+1 |
97/6=16,17 |
65/6 |
0 |
0 |
11/3 |
10/3 |
0 |
1/6 |
Оптимальний план задачі має вид Хопт = (0; 7/6; 37/6; 0; 0; 7; 0).
Цей план містить дробові компоненти і не задовольняє умові цілочисельності задачі.
Візьмемо змінну x2 і множину допустимих розв'язків розіб'ємо на дві та . З першого обмеження маємо відповідно і .
Якщо х2=1, то х3=6, Точка С' (0; 1; 6; 0) задовольняє всім обмеженням; F (C') =-16.
Обчислене значення і є найменшим цілим значенням розв'язку задачі.
Завдання №10
Метод покоординатного сходження для розв'язання задач нелінійного програмування
Мета: набуття навичок знаходження оптимуму задачі безумовної багатовимірної оптимізації наближено методом покоординатного сходження
f (x1, x2) = (x1 - 3 x2) 4 + (2x2 - x1) 2 min
Розв'язання
Завдання 10 - знаходження оптимуму задачі безумовної багатовимірної оптимізації наближено одним з методів (покоординатного сходження або градієнтним) за вибором, потребує розробки програми для знаходження оптимуму функції.
Текст програми
program maxkoo;
uses wincrt;
const eps=0.001;
x1p=1; x2p=1;
h1p=0.5; h2p=0.5;
function detf1 (x1,x2: real): real;
begin
detf1: =4*sqr (x1-3*x2) * (x1-3*x2) - 2* (2*x2-x1);
end;
function detf2 (x1,x2: real): real;
begin
detf2: =-12*sqr (x1-3*x2) * (x1-3*x2) +4* (2*x2-x1);
end;
function ff (x1,x2: real): real;
begin
ff: =sqr (x1-3*x2) *sqr (x1-3*x2) +sqr (2*x2-x1);
end;
var h1, h2: real;
x10,x1, x20,x2: real;
f1, f2: real;
df: real;
k,k1: integer;
begin
clrscr;
x10: =x1p; x20: =x2p;
k: =0;
repeat
f1: =ff (x10,x20);
h1: =2*h1p; h2: =2*h2p;
k1: =0;
repeat
h1: =h1/2;
x1: =x10-h1*detf1 (x10,x20);
f2: =ff (x1,x20);
k1: =k1+1;
until ( (f2-f1) <=0) or (k1>20);
x10: =x1;
f1: =f2;
k1: =0;
repeat
h2: =h2/2;
x2: =x20-h2*detf2 (x10,x20);
f2: =ff (x10,x2);
writeln (x2: 10: 4,f2: 15: 5);
k1: =k1+1;
until ( (f2-f1) <=0) or (k1>20);
x20: =x2;
k: =k+1;
writeln (k);
until (abs (f2-f1) <eps) or (k>20);
writeln (x1: 10: 4,x2: 10: 4, f1: 10: 4,f2: 10: 4);
end.
Результат
При x1=3,2234 та x2=1,2735 функція f (x1, x2) набуває свого найменшого значення 0,5846
Завдання №11
Градієнтний метод розв'язання задач нелінійного програмування
Мета: набуття навичок знаходження оптимуму задачі умовної оптимізації наближено градієнтним методом
Розв'язання
Завдання 11 - знаходження оптимуму задачі безумовної багатовимірної оптимізації наближено одним з методів (покоординатного сходження або градієнтним) за вибором, потребує розробки програми для знаходження оптимуму функції.
Текст програми
program maxgrad;
uses wincrt;
const eps=0.0001;
x1p=2; x2p=1.5;
h1p=0.4; h2p=0.4;
function detf1 (x1,x2: real): real;
begin
detf1: =1;
end;
function detf2 (x1,x2: real): real;
begin
detf2: =-2* (x2-1);
end;
function ff (x1,x2: real): real;
begin
ff: =x1-sqr (x2-1);
end;
var h1, h2: real;
x10,x1, x20,x2: real;
f1, f2: real;
df: real;
k,k1: integer;
begin
clrscr;
x1: =x1p; x2: =x2p;
k: =0;
h1: =h1p; h2: =h2p;
f2: =ff (x10,x20);
repeat
k: =k+1;
h1: =h1/2;
h2: =h2/2;
x10: =x1;
x20: =x2;
f1: =f2;
x1: =x10+h1*detf1 (x10,x20);
x2: =x20+h2*detf2 (x10,x20);
f2: =ff (x1,x2);
writeln (k: 3, x1: 8: 3, x2: 8: 3, f1: 10: 4,f2: 10: 4);
until (abs (f2-f1) <eps) or (k>20);
end.
Результат
Завдання №12
Метод множників Лагранжа для розв'язання задач нелінійного програмування
Мета: набуття навичок знаходження оптимуму задачі умовної багатовимірної оптимізації наближено методом множників Лагранжа.
Розв'язання
Складемо функцію Лагранжа. Оскільки за умовою тільки два обмеження, то множників Лагранжа буде два.
.
Знайдемо частинні похідні по :
Прирівнюючи похідні до нуля, отримаємо систему рівнянь для визначення стаціонарних точок:
З першого, четвертого і п'ятого рівнянь визначимо x2 та x1
1) x2=-2 - не задовільняє початковим умовам.
2)
Підставимо знайдені значення другого випадку у функціонал та отримаємо:
Знайдемо стаціонарну точку цієї функції
Стаціонарної точки не існує для невід'ємних значень змінних.
Завдання №13
Мета: навчитися використовувати симплекс-метод для розв'язання задач нелінійного квадратичного програмування.
Розв'язання
Функція є опуклою, оскільки являє собою суму лінійної функції (яку також можна розглядати як опуклою) і квадратичної форми , яка є достатньо визначеною і тому також є опуклою функцією. Система обмежень задачі містить лише лінійні рівняння. Отже, можна застосувати теорему Куна-Таккера. З цією метою запишемо функцію Лагранжа
Запишемо необхідні і достатні умови існування сідлової точки побудованої функції Лагранжа:
Запишемо першу систему обмежень наступним чином:
Зведемо нерівності системи до рівностей шляхом введення невід'ємних змінних :
Враховуючи дані рівності, можемо записати:
.
Для знаходження базисного розв'язку системи лінійних рівнянь застосовуємо метод штучного базису. Для цього в друге і третє рівняння системи вводимо додаткові невід'ємні змінні і розв'яжемо задачу лінійного програмування
при обмеженнях
Таблиця 17
|
x1 |
x2 |
x3 |
1 |
2 |
v1 |
v2 |
v3 |
w1 |
w2 |
z1 |
z2 |
|||||
|
|
Ба-зис |
Сбаз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-М |
-М |
||
|
i |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
|||
|
1 |
A6 |
0 |
2 |
2 |
0 |
0 |
-1 |
-2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 |
A11 |
-М |
1 |
0 |
-2 |
0 |
2 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
|
3 |
A12 |
-М |
0 |
0 |
2 |
0 |
-3 |
-1 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
|
4 |
A9 |
0 |
1 |
2 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
5 |
A10 |
0 |
2 |
1 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
M+1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
M+2 |
0 |
2 |
-2 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|||
|
1 |
A6 |
0 |
2 |
2 |
0 |
0 |
-1 |
-2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 |
A11 |
-М |
1 |
0 |
-2 |
0 |
2 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
|
3 |
A3 |
0 |
0 |
0 |
0 |
1 |
-1,5 |
-0,5 |
0 |
0 |
-0,5 |
0 |
0 |
0 |
0,5 |
|
|
4 |
A9 |
0 |
12 |
1 |
2 |
0 |
4,5 |
1,5 |
0 |
0 |
1,5 |
1 |
0 |
0 |
-1,5 |
|
|
5 |
A10 |
0 |
6 |
2 |
1 |
0 |
1,5 |
0,5 |
0 |
0 |
0,5 |
0 |
1 |
0 |
-0,5 |
|
|
m+1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
m+2 |
-1 |
0 |
2 |
0 |
-2 |
-1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|||
|
1 |
A6 |
0 |
2,5 |
2 |
-1 |
0 |
0 |
-1,5 |
1 |
-0,5 |
0 |
0 |
0 |
0,5 |
0 |
|
|
2 |
A4 |
0 |
0,5 |
0 |
-1 |
0 |
1 |
0,5 |
0 |
-0,5 |
0 |
0 |
0 |
0,5 |
0 |
|
|
3 |
A3 |
0 |
0,75 |
0 |
-1,5 |
1 |
0 |
0,25 |
0 |
-0,75 |
-0,5 |
0 |
0 |
0,75 |
0,5 |
|
|
4 |
A9 |
0 |
9,75 |
1 |
6,5 |
0 |
0 |
-0,75 |
0 |
2,25 |
1,5 |
1 |
0 |
-2,25 |
-1,5 |
|
|
5 |
A10 |
0 |
5,25 |
2 |
2,5 |
0 |
0 |
-0,25 |
0 |
0,75 |
0,5 |
0 |
1 |
-0,75 |
-0,5 |
|
|
m+1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
m+2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
x3 |
1 |
2 |
v1 |
v2 |
v3 |
w1 |
w2 |
z1 |
z2 |
Як видно з таблиці 17, розв'язком задачі є
Оскільки , то є сідловою точкою функції Лагранжа задачі. Отже, - оптимальний план задачі і .
Размещено на Allbest.ru
Подобные документы
Багатокритеріальність, існуючі методи розв’язку задач лінійного програмування. Симплекс метод в порівнянні з графічним. Вибір методу розв’язання багатокритеріальної задачі лінійного програмування. Вирішення задачі визначення максимального прибутку.
курсовая работа [143,7 K], добавлен 15.12.2014Дослідження операцій - наука про моделі і методи оптимального управління. Використання методу лінійного програмування - двоїстий симплекс. Алгоритм рішення задачі. Висновок і дослідження моделі на чутливість. Дослідження програми для великих розмірностей.
курсовая работа [3,2 M], добавлен 25.05.2015Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера". Класифікація задач дослідження операцій. Вибір методу розв’язання транспортної задачі; алгоритмічне і програмне забезпечення, тести і документи.
курсовая работа [807,7 K], добавлен 07.12.2013Побудування математичної моделі задачі. Розв'язання задачі за допомогою лінійного програмування та симплексним методом. Наявність негативних коефіцієнтів в індексному рядку. Основний алгоритм симплексного методу. Оптимальний план двоїстої задачі.
контрольная работа [274,8 K], добавлен 28.03.2011Максимальна негативна кількість та індексний рядок. Розв'язання задачі лінійного програмування симплексним методом. Побудова першого опорного плану системи нерівностей. Метод штучного базису та матриця коефіцієнтів. Основний алгоритм симплекс-методу.
контрольная работа [302,8 K], добавлен 28.03.2011Загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування Економіко–математична модель конкретної задачі, алгоритм її вирішення за допомогою Exel.
контрольная работа [109,7 K], добавлен 24.11.2010Складання математичної моделі задачі. Побудова симплексної таблиці. Розв’язок задачі лінійного програмування симплексним методом. Рішення двоїстої задачі та складання матриці. Знаходження графічним методом екстремумів функцій, визначеній нерівностями.
контрольная работа [239,0 K], добавлен 28.03.2011Загальна економіко-математична модель задачі лінійного програмування. Основні форми запису задач. Оптимальний та допустимий розв'язок. Геометрична інтерпретація, властивості розв'язків та графічний метод розв'язування задач лінійного програмування.
презентация [568,4 K], добавлен 10.10.2013Складання математичної моделі задачі комівояжера. Її розв'язок за допомогою електронних таблиць Microsoft Excel. Знаходження оптимального плану обходу міст комівояжером за заданими критеріями. Інтерпретація графічно отриманого розв’язку даної задачі.
контрольная работа [244,8 K], добавлен 24.09.2014Математична модель задачі лінійного програмування та її розв’язок симплекс-методом. Опорний план математичної моделі транспортної задачі. Оптимальний план двоїстої задачі. Рішення графічним методом екстремумів функції в області, визначеній нерівностями.
контрольная работа [290,0 K], добавлен 28.03.2011
