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.


 

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

25596. Гештальт-Психология 44.5 KB
  ГештальтПсихология Возникла одновременно с бихевиоризмом когда все хотели пересмотреть предмет психологии вообще общее недовольство типа 1910год Были против структурализма и функционализма. Вертгеймер открыл фифеномен через щель пропускали свет с различными интервалами времени – возникало восприятие движения использовал стробоскоп вращение изображений создает иллюзию их движения Вывод: в сознании есть целостные образы гештальты неразложимые на элементы. Понятие инсайта изза переструктурирования гештальта Опыт Келера с курами:...
25597. Зарождение Фрейдизма, его основные разделы, положения и критика 96.5 KB
  Зарождение Фрейдизма его основные разделы положения и критика. Фрейда 1856 1939 формировался в условиях и под воздействием политического и социального развития Австрии конца прошлого начала нынешнего столетия. Фрейд Толкование сновидений Автобиография и др. Фрейда его понимание человека согласно которому под напором инстинктов сексуальности и в силу бессознательности психических процессов признавалось что Я не хозяин в собственном доме объективно отражали кризис буржуазной личности типичное самоощущение индивида в...
25598. Неофрейдизм 60.5 KB
  Эти трудности отразились в судьбе каждого человека. Хорни 1885 1952 выступила с социологизированным вариантом фрейдизма в котором поставила проблему социальной в терминологии Хорни культурной обусловленности формирования характера человека и неврозов. Эти защитные механизмы формируются с детства и становятся той бессознательной основой на которой строятся представления человека о самом себе. При этом задача воспитания сводится к социальной адаптации человека.
25599. Возникновение гуманистической психологии 34 KB
  Возникновение гуманистической психологии. был основан Журнал гуманистической психологии и создана Ассоциация за гуманистическую психологию. состоялась конференция положившая начало гуманистической психологии. Непосредственными предпосылками явились исследования по психологии личности конца 30х гг.
25600. Маслоу и его концепция самоактуализирующейся личности 48 KB
  Маслоу и его концепция самоактуализирующейся личности. Маслоу окончил Висконсинский университет и получил степень доктора психологических наук в 1934 г. Именно этот ученый его личность стиль жизни и творчества навели Маслоу на мысль о самоактуализировавшейся личности. Собственная теория Маслоу которую ученый разработал к 50м годам изложена им в книгах К психологии бытия 1968 Мотивация и личность 1970 и др.
25601. Роджерс и его личностно-ориентировананный подход в психологии и психиатрии 66.5 KB
  Этот мир создаваемый человеком может совпадать или не совпадать с реальной действительностью так как не все предметы в окружении человека осознаются им. Говоря о структуре Я Роджерс пришел к выводу о том что внутренняя сущность человека его Самость выражается в самооценке которая является отражением истинной сути данной личности его Я. Тем не менее уже в раннем возрасте она руководит поведением человека помогая понять и отобрать из окружающего то что присуще именно данному индивиду интересы профессию общение с определенными...
25602. Когнитивное направление в современной зарубежной психологии 51.5 KB
  Когнитивное направление в современной зарубежной психологии Работы Пиаже и Брунера во многом способствовали появлению нового направления появившегося уже в 60х годах XX в. когнитивной психологии. В когнитивной психологии психика рассматривается как система когнитивных реакций и постулируется связь этих реакций не только с внешними стимулами но и с внутренними переменными например с самосознанием когнитивными стратегиями селективностью внимания и т. Серьезное достоинство когнитивной психологии точность и конкретность полученных...
25603. Начало марксистско-ленинской перестройки в отечественной психологии 26.5 KB
  Корнилов 18791957. Используя идею диалектического единства Корнилов надеялся преодолеть как агрессивную односторонность рефлексологии Бехтерева и Павлова она претендовала на единственно приемлемое для материалиста объяснение поведения так и субъективизм интроспективного направления лидером которого в России был Г. Основным элементом психики Корнилов предложил считать реакцию. Став директором бывшего челпановского института Корнилов предложил сотрудникам изучать психические процессы в качестве реакций восприятия памяти воли и т.
25604. Рубенштейн и разработка им философских основ психологии в 30 и в послевоенные годы 27 KB
  Маркса он обосновал принцип единства сознания и деятельности который позволил дать новаторскую трактовку сознания не как внутреннего мира познаваемого субъектом только посредством самонаблюдения а как высшего уровня организации психической деятельности предполагающего включенность личности в контекст ее жизненных связей с объективным миром. Предполагалось что природа сознания является изначально социальной обусловленной общественными отношениями. На основе принципа единства сознания и деятельности Рубинштейном был проведен большой цикл...