11768

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

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

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

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

Украинкский

2013-04-11

609.85 KB

95 чел.

на тему

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

Мета роботи: ознайомлення з задачами нелінійного програмування, набуття навиків їх розв’язку та аналізу графічним методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Е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.


 

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

49189. КОНСТРУИРОВАНИЕ ОДЕЖДЫ 271.29 KB
  Конструирование одежды Проектирование серии изделий на базе одной конструктивной основы Заключение Список литературы Введение История возникновения одежды уходит далеко в глубь веков к самым ранним ступеням развития человечества. Материалистическая точка зрения связывает происхождение одежды с климатическими условиями а её развитие –с...
49190. Расчет прочности рабочей лопатки, диска и определение частоты и формы изгибных колебаний одиночной лопатки и пакета лопаток, связанных бандажом 433.68 KB
  Расчет прочности рабочей лопатки. Расчет прочности лопатки и выбор материала рабочей лопатки. Определение частот и форм колебаний одиночной турбинной лопатки и пакета лопаток связанных бандажом.
49192. Природа і сутність політичної влади 51.21 KB
  Все життя людей нерозривно повязана з владою, яка є найбільш потужним засобом захисту людських інтересів, втілення планів людей, врегулювання їх протиріч і конфліктів. Ключова різновид влади - влада політична - має колосальними конструюють здібностями, представляє самий потужний джерело розвитку суспільства, знаряддя соціальних перетворень і трансформацій.
49193. Направленные микрофоны 7.61 MB
  Общие понятия о направленных микрофонах. Принцип работы микрофона заключается в том что давление звуковых колебаний воздуха воды или твердого вещества действует на тонкую мембрану микрофона. В свою очередь колебания мембраны возбуждают электрические колебания; в зависимости от типа микрофона для этого используются явление электромагнитной индукции изменение ёмкости конденсаторов или пьезоэлектрический эффект. Наибольшая чувствительность при этом достигается на пути вдоль оси микрофона когда источник размещен прямо перед...
49194. Пути повышение рентабельности предприятия общественного питания 752.37 KB
  Понятие рентабельности Виды рентабельности. Система показателей рентабельности. Анализ рентабельности предприятия.
49195. Сучасні проблеми податкової системи України та шляхи їх подолання 81.23 KB
  Сутність структура та основні принципи побудови податкової системи. Практика та проблематика ефективного функціонування податкової системи в Україні. Основні напрямки реформування податкової системи України.
49196. ПРОЕКТИРОВАНИЕ АНАЛОГО-ЦИФРОВОГО ПРЕОБРАЗОВАТЕЛЯ С USB ВЫХОДОМ 2.14 MB
  Аналого-цифровой преобразователь АЦП согласующий усилитель СУ фильтр нижних частот ФНЧ конвертор преобразователь DCDC гальваническая развязка операционный усилитель ОУ. В ходе курсовой работы необходимо нарисовать функциональную и принципиальную схему аналого-цифрового преобразователя АЦП выбрать микросхему АЦП в соответствии с вариантом тип конвертора USB преобразователи DCDC и микросхемы гальванической изоляции. Задание на курсовую работу В ходе курсового проектирования необходимо разработать функциональную и...