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.


 

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

35020. Операции банка 25 KB
  Операции банка делятся на пассивные по привлечению свободных денежных средств в банк и активные по размещению ссуд и кредитованию клиентов. Процент за предоставленные кредиты бывает выше чем за привлеченные вклады что представляет одну из составляющих прибыли банка. Кроме того банк организует операции по учету векселей. Банк покупает вексель удерживая из обозначенной на нем суммы учетный процент что также составляет прибыль банка на этой операции.
35021. Мультипликатор Депозитный 18.33 KB
  Денежные агрегаты Показателями структуры денежной массы являются денежные агрегаты. Денежными агрегатами называются виды денег и денежных средств отличающиеся друг от друга степенью ликвидности возможностью быстрого превращения в наличные деньги. В разных странах выделяются денежные агрегаты разного состава. Денежные агрегаты представляют собой иерархическую систему каждый последующий агрегат включает в свой состав предыдущий.
35022. Денежно-кредитная (или монетарная) политика 16.22 KB
  Воздействие на макроэкономические процессы инфляцию экономический рост безработицу осуществляется посредством денежнокредитного регулирования. Обычно денежнокредитная политика ЦБ направлена на достижение и сохранение финансовой стабилизации в первую очередь укрепление курса национальной валюты и обеспечение устойчивости платежного баланса страны. Денежнокредитное регулирование это совокупность конкретных мероприятий центрального банка направленных на изменение денежной массы в обращении объема кредитов уровня процентных ставок и...
35023. Федеральные финансы 23.5 KB
  Главное место в системе финансов государства занимает государственный бюджет являющийся мощным рычагом регулирования национальной экономики средством воздействия стимулирующего или сдерживающего на хозяйственную конъюнктуру экспорт ноимпортный баланс и т. С одной стороны федеральный бюджет это детально разработанный многоплановый документ сводный план доходов и расходов государства. С другой стороны федеральный бюджет представляет собой централизованный фонд денежных средств которыми располагает высшая исполнительная власть для...
35024. Введение в систему MathCad 308.68 KB
  Целью работы является ознакомление с системой MathCad, изучение ее интерфейса и произведение требуемых расчетов, а так же изучение встроенных функций MathCad
35025. Датчики случайных чисел 811.54 KB
  В ряде шифровальных алгоритмов используется бесконечная гамма случайных чисел, обладающих рядом качеств и параметров (диапазон изменений, максимальное и минимальное значение, частотность и другие).
35026. Система шифрования Цезаря 1.09 MB
  Криптография представляет собой совокупность методов преобразования данных, направленных на то, чтобы сделать эти данные бесполезными для противника. Такие преобразования позволяют решить две главные проблемы защиты данных: проблему обеспечения конфиденциальности (путем лишения противника возможности извлечь информацию из канала связи)
35027. Алгоритм шифрования XOR 131.96 KB
  XOR – это функция булевой алгебры, носящей название «исключающее или», данная функция используется для работы с данными представленными в двоичной системе исчисления. Основным достоинством, позволяющим использовать эту функцию в шифровальных алгоритмах является ее обратимость, при отсутствии потери информации.