11768

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

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

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

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

Украинкский

2013-04-11

609.85 KB

103 чел.

на тему

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

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


 

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

50021. Становление личности. Проблемы самоидентификации и самоактуализации 16.08 KB
  Становление личности есть процесс социализации человека, который состоит в освоении им своей родовой, общественной сущности; это освоение всегда осуществляется в конкретно-исторических обстоятельствах жизни человека. Становление личности связано с принятием индивидом выработанных в обществе социальных функций и ролей
50022. Нечеткая логика 67 KB
  Согласно заданным вариантам разработать программу на любом алгоритмическом языке, способную: А. Различать степени изменения лингвистической переменной в трех степенях – «Очень – Нормально – Слабо» Б. Изменять порог чувствительности
50023. Определение отношения теплоёмкости газа 91 KB
  Цель работы Измерение отношения теплоемкости воздуха при постоянном давлении и при постоянном объеме. Расчетная формула Отношение определяется по расчетной формуле: где h1 разность уровней в коленах манометра после первой установки давления h2 разность уровней в коленах манометра после второй установки давления Среднее значение для искомого отношения находится по формуле: Выполнение работы № опыта h1 см h2 см 16 10 106 122 08 107 104 07 107 13 14...
50024. Изучение работы источника напряжения 88 KB
  Изучение работы источника напряжения Цель: Изучение работы источника напряжения. Краткие теоретические сведения Принципиальная схема работы любого источника напряжения приведена на рис. 1 где e ЭДС источника r его внутреннее сопротивление R сопротивление внешней цепи нагрузка. 2 Выражая из 1 сопротивление R и подставляя в 2 получим зависимость напряжения на нагрузке от силы тока в цепи...
50025. Измерение сопротивления мостом постоянного тока 39 KB
  Измерение сопротивления мостом постоянного тока Цель работы: ознакомиться с методом измерения сопротивления с помощью моста постоянного тока. Краткие теоретические сведения Одним из распространенных методов определения сопротивления является метод моста постоянного тока. В другие плечи включаются два резистора с известными сопротивлениями R1 и R2 и магазин сопротивлений RМ. Подключить последовательно сопротивления Rx1 и Rx2.
50026. Исследование процессов заряда и разрядки конденсатора и определение емкости конденсатора 255.5 KB
  Исследование процессов заряда и разрядки конденсатора и определение емкости конденсатора Цель работы: изучить временную зависимости напряжения на конденсаторе при подключении или отключении источника постоянной ЭДС и определить емкость конденсатора. Краткие теоретические сведения Рассмотрим процессы заряда и разрядки конденсатора при подключении или отключении источника постоянной ЭДС e0 в схеме представленной на рис. При включении ЭДС появлении импульса ток при заряде конденсатора протекает по внутреннему сопротивлению источника r и...
50027. Темперамента у подростков 235 KB
  Период отрочества характеризуется динамичными изменениями всех физиологических систем и психических функций. Одновременно с этим, подростку приходится осваивать новые социальные роли и функции, перестраивать отношения с окружающим миром, изменять представления о себе как о личности.
50028. Наближене обчислення визначених інтегралів. Методичні вказівки 192 KB
  Загальна квадратурна формула має вигляд: 1. Формула прямокутників Якщо в формулі НьютонаКортеса взяти n=0 то одержимо квадратну формулу методу прямокутників.Кожна з цих сум є інтегральною сумою для на відрізку і тому наближено виражають визначений інтеграл: 1 2 Ці формули називаються формулами прямокутників.1 видно що якщо додатна і зростаюча функція то формула 1 виражає площу ступінчатої фігури що складена із â внутрішніхâ прямокутників а формула 2...
50029. ЧИСЕЛЬНІ МЕТОДИ В ІНФОРМАТИЦІ. МЕТОДИЧНІ ВКАЗІВКИ 74.5 KB
  Розвязування системи лінійних алгебраїчних рівнянь методом Гауса. Мета роботи: вивчити і засвоїти Методи Гауса і Жордана Гауса розвязування СЛАР. Метод Гауса полягає в зведенні квадратної системи 1 до трикутного вигляду з використанням алгоритму послідовного виключення невідомих. Алгоритм методу Гауса складається з двох етапів: Триангуляція матриці 2 Обчислення розвязку системи рівнянь...