11768

НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД

Практическая работа

Математика и математический анализ

на тему НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД. Мета роботи: ознайомлення з задачами нелінійного програмування набуття навиків їх розв’язку та аналізу графічним методом вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel вивчення т

Украинкский

2013-04-11

609.85 KB

93 чел.

на тему

 НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД.

Мета роботи: ознайомлення з задачами нелінійного програмування, набуття навиків їх розв’язку та аналізу графічним методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad.

Порядок роботи:

  1.  Короткі теоретичні відомості.

  1.  Розв’язати графічно задану задачу нелінійного програмування.

  1.  Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям графічного методу нелінійного програмування.

  1.  Використовуючи засоби MathCad , розв’язати задану нелінійного програмування.

  1.  Змінити умову задачі таким чином, щоб центр функції мети знаходився в області визначення і повторити пп. 2-4.   

  1.  Проінтерпретувати отримані результати для вихідної задачі.

Хід Роботи

  1.  Короткі теоретичні відомості

Неліні́йне програмува́ння (NLPангл. NonLinear Programming) — випадок математичного програмування, у якому цільовою функцією чи обмеженнями є нелінійна функція.

Задача нелінійного програмування ставиться як задача знаходження оптимуму певної цільової функції  при виконанні умов

,

де  — параметри,  — обмеження, n — кількість параметрів, s — кількість обмежень.

На відміну від задачі лінійного програмування в задачі нелінійного програмування оптимум не обов'язково лежить на границі області, визначеної обмеженнями.

Методи розв'язування задачі

Одним із методів, які дозволяють звести задачу нелінійного програмування до розв'язування системи рівнянь є метод невизначених множників Лагранжа.

Якщо цільова функція F є лінійною, а обмеженим простором є політоп, то задача є задачею лінійного програмування, яка може бути розв'язана за допомогою добре відомих рішень лінійного програмування.

Якщо цільова функція є угнутою (задача максимізації), або опуклою (задача мінімізації) і множина обмежень є опуклою, то задачу називають опуклою і в більшості випадків можуть бути використані загальні методи опуклої оптимізації.

Якщо цільова функція є відношенням увігнутих і опуклих функцій (у разі максимізації) і обмеження опуклі, то задача може бути перетворена в задачу опуклої оптимізації використанням технікдробового програмування.

Існують декілька методів для розв'язування неопуклих задач. Один підхід полягає у використанні спеціальних формулювань задач лінійного програмування. Інший метод передбачає використання методів гілок і меж, де задача поділяється на підкласи, щоби бути розв'язаною з опуклими (задача мінімізації) або лінійними апроксимаціями, які утворюють нижню межу загальної вартості у межах поділу. При наступних поділах у певний момент буде отримано фактичний розв'язок, вартість якого дорівнює найкращій нижній межі, отриманій для будь-якого з наближених рішень. Цей розв'язок є оптимальним, хоча, можливо, не єдиним. Алгоритм можна також припинити на ранній стадії, з упевненістю, що оптимальний розв'язок знаходиться в межах допустимого відхилення від знайденої кращої точки; такі точки називаються ε-оптимальними. Завершення біля ε-оптимальних точок, як правило, необхідне для забезпечення скінченності завершення. Це особливо корисно для великих, складних задач і задач з невизначеними витратами або значеннями, де невизначеність може бути оцінена з відповідної оцінки надійності.

Графічний метод рішення задач нелінійного програмування

Графічний метод можна використовувати для вирішення задачі НЛП, яка містить дві змінні х1 і х2, наприклад завдання такого вигляду:

Z = f(x1x2) → min (max);

gi(x1x2) ≤ bi.

Щоб знайти її оптимальне рішення, потрібно виконати наступні дії:

1. Знайти ОДЗ, яка визначається обмеженнями завдання. Якщо виявиться, що ця область порожня, то це означає, що задача не має рішення.

2. Побудувати сімейство ліній рівня цільової функції f (х1, х2) = C  при різних значеннях числового параметра С.

3. При виконанні завдання на мінімум визначити напрямок зменшення, а для задачі на максимум - напрям зростання ліній рівня ЦФ.

4. Знайти точку ОДЗ, через яку проходить лінія рівня з найменшим в задачі на мінімум (відповідно, найбільшим в завдання на максимум) значенням параметра С. Ця точка буде оптимальним рішенням. Якщо ЦФ не обмежена знизу в задачі на мінімум (зверху - в задачі на максимум), то це означає, що задача не має оптимального рішення.

5. Знайти координати точки оптимуму і визначити в ній значення ЦФ.

Відзначимо, що на відміну від завдання ЛП точка оптимуму в задачі НП не обов'язково знаходиться на границі ОДЗ. Нею також може бути внутрішня точка цієї множини.

Постановка задачі

Розв’язати задачу дробово-лінійного програмування графічно і симплексним методом.

Варіант 48

  1.  F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 min, max ;

3x1 +  2x2    6,

x1 + x2  7,

11x1 + 5x2  55,

x1  0, x2  0.

2. Розв’язати графічно задану задачу нелінійного програмування.

2.1

Областю допустимих значень є багатокутник ABCDE , який обмежений відрізками прямих.

 L1-  3x1 +  2x2  = 6,

L2- x1 + x2 = 7

L3- 11x1 + 5x2 = 55

 

x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)

 

Для h>0 F=h визначає на площині  x1Ox2 еліпс.

Ln : F= 4 (x1 - 9 )2 + 2 (x2 - 8)2 = h

Центр еліпса знаходиться в точці Q(9,8) , а півосі дорівнюють h/4 і h/2 відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується .

Знайдемо hmin

F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2  =h  (1)

X1=7-x2      (2)

Підставивши 2 рівність в 1 отримаєм :

4 ((7-x2) - 9 )2 + 2 (x2 - 8)2  =h

4 ((7-x2) 22(7-x2)*9+81 ) + 2 (x2 - 8)2  =h

4 (4+4x2+x22)+ 2 (x22   - 16x2+64)2  =h

 16+16x2+6x22 -32x2+128=h

142-16x2+6x2 =h

 x1=x1’ =3,596

x2=x2’ =3,088

отже  точка С має такі координати  С(3,596; 3,088)

Звідси підставивши значення у цільову функцію можна побачити що

hmin =165.052

Тепер можна знайти hmax підставивши всі інші значення в цільову функцію.

hmax= (81*4+50)=374 тобто максимум досягається у точці A(0,3).

Розвязок даної задачі з розясненнями в Exel і MatCad подані у розділах 3 , 4.

2.2 Змінюю умову задачі таким чином, щоб центр функції мети знаходився в області визначення .

 

 

Для h>0 F=h визначає на площині  x1Ox2 еліпс.

Ln : F= 4 (x1 - 3 )2 + 2 (x2 - 2)2 = h

x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)

Центр еліпса знаходиться в точці Q(3,2) , а півосі дорівнюють h/4 і h/2 відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується .

Обчислюю по тому самому алгоритму що і  в 2.1

Знайдемо hmin 

  точка С має такі координати   С(3,596; 3,088)

Звідси підставивши значення у цільову функцію можна побачити що

hmin =3.7883

Тепер можна знайти hmax підставивши всі інші значення в цільову функцію.

hmax= 4*(0-3)^2+ 2*(7-2)^2 = 86 тобто максимум досягається у точці A(0,7).

Розвязок даної задачі з розясненнями в Exel і MatCad подані у розділах 3 , 4.

3. Розв’язання за допомогою MS Exel.

3.1

Алгоритм розвязку задачі в Exel

  1.  Вписую в певні комірки свої рівняння.
  2.  Відділяю певні комірки під певні точки перетину для наглядності.
  3.  Створюю графік за домогою майстра графіків у MS Office 2010
  4.  Знаходжу max I min значення підставивши у певні комірки точки перетину і висначаю значення по визначеній формулі наприклад (=4*(K9-3)^2+ 2*(L9-2)^2)

 Рис 1 Задача з еліпсом який знаходиться за границями ОДЗ

Рис 2 Задача з еліпсом який знаходиться в ОДЗ

4. Розв’язання за допомогою математичного пакету програм  MathCad

4.1 Задача в якій центр функції мети знаходиться за границями ОДЗ.

Записуємо умову:

Умова:

F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 min, max ;

3x1 +  2x2    6,

x1 + x2  7,

11x1 + 5x2  55,

x1  0, x2  0.

Перетворення:

x2 = 2 – 3/2*x1

x2 = 7 – x1;

x2 = 11 –11/5*x1;   

Алгоритм розвязку в MatCad

  1.  Cпочатку потрібно вести рівняння обмежуючих пямих в область розвязку.
  2.  Далі на панелі інструментів вибрати інструмент graph.
  3.  Зробити межі по x і по y .
  4.  Вийти в область і натиснути Пробіл на клавіатурі.
  5.  За допомогою функцій обчислення задач НЛП які вбудовані в Matcad вписати цільову функцію .
  6.  За допомогою «given» в Matcad  і обмежуючих прямих знайти значення які потрібні (за допомогою функцій «minimize» або «maximize»).

Графіки обмежуючих прямих:

 

Рис 1 Задача з еліпсом який знаходиться за границями ОДЗ .

Отже, мінімальне значення цільова функція досягає в точці з координатами 

 min (3,596 ; 3,088), а максимальне – в точці  (0; 3)

4.2 Задача в якій центр функції мети знаходиться в ОДЗ.

Рис 2 Задача з еліпсом в ОДЗ

Отже, мінімальне значення цільова функція досягає в точці з координатами (3;2), а максимальне – в точці (0; 7)

Висновок:  я ознайомився  з задачами нелінійного програмування, набув навиків їх розв’язку та аналізу графічним методом, вивчив  та оволодів навичками адресації та роботи з формулами в таблицях в Еxcel, вивчив та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad.


 

А также другие работы, которые могут Вас заинтересовать

15287. Налагодження програми мовою Асемблер з використанням логічних операцій 76 KB
  Налагодження програми мовою Асемблер з використанням логічних операцій Лабораторна робота № 14 Тема: Технологія та прийоми програмування мовою Асемблера. Мета роботи: Набути навичок застосування логічних команд при програмуванні мов...
15288. Налагодження програми мовою Асемблер з використанням підпрограм 104 KB
  Налагодження програми мовою Асемблер з використанням підпрограм Лабораторні роботи № 15 16 Тема: Технологія та прийоми програмування мовою Асемблер. Мета роботи: Набути навичок роботи з підпрограмами. Навчитися передавати параметри з осно...
15289. Налагодження програми мовою Асемблер з використанням екранних операцій 132.5 KB
  Налагодження програми мовою Асемблер з використанням екранних операцій Лабораторна робота Тема: Переривання та введення/виведення інформації. Мета роботи: Набути навичок роботи з функціями введення/виведення інформації. ...
15290. Налагодження програми мовою Асемблер з використанням макросів 99 KB
  Налагодження програми мовою Асемблер з використанням макросів Лабораторна робота № 18 Тема: Технологія та прийоми програмування мовою Асемблер. Мета роботи: Набути навичок роботи з макросами при програмуванні мовою Асемблера. Навчитися с
15291. Компьютерная графика в визуальном программировании 1.18 MB
  Данные методические указания предназначены для самостоятельной работы студентов всех специальностей и используются при выполнении лабораторных и контрольных работ по курсам Информатика и Алгоритмизация и программирование на языке Visual Basic.
15292. Використання адресної арифметики для роботи з вказівниками 62 KB
  Використання адресної арифметики для роботи з вказівниками Лабораторна робота Тема: Використання адресної арифметики для роботи з вказівниками Мета роботи: Навчитись створювати вказівники описувати їх і задавати; оволодіти основними с
15293. Изучение свойств Р-N перехода и определение запрещенной зоны проводника 77 KB
  Отчёт по лабораторной работе № 36. Изучение свойств РN перехода и определение запрещенной зоны проводника. Расчетная формула для измерения величины ...
15294. Изучение радиоактивного излучения 80 KB
  В данной лабораторной работе мы исследовали ослабление излучения защитными материалами, а так же исследовали элементы дозиметрии излучения. Измеряли и рассчитывали величину фона, экспозиционную дозу, поглощенную дозу и эквивалентную дозу для случаев
15295. Изучение эффекта холла 49 KB
  В данной работе я изучил эффект холла, получив при этом конкретные значения холловского коэффициента и концентрации свободных электронов. При выполнении работы я пользовался гальванометром, амперметром