Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Група:
КН-21
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
із лабораторної роботи №10
«НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД»
з дисципліни
“Математичні методи дослідження операцій”
Мета роботи: ознайомлення з задачами нелінійного програмування, набуття навиків їх розв’язку та аналізу графічним методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad.
Порядок роботи:
Номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100.
Розв’язати графічно задану задачу нелінійного програмування.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям графічного методу нелінійного програмування.
Використовуючи засоби MathCad , розв’язати задану нелінійного програмування.
Змінити умову задачі таким чином, щоб центр функції мети знаходився в області визначення і повторити пп. 1-3.
Проінтерпретувати отримані результати для вихідної задачі.
Індивідуальне завдання:
F(x1, x2) = -2х1 + x2 min;
2*x1 – 3*x2 8,
x1 + x2 5,
-3*x1 + 2*x2 3,
x1 0, x2 0.
Короткі теоретичні відомості
Як ми вже пересвідчилися на прикладі задач дробово-лінійного програмування, лінійні моделі можуть виявитися недостатніми для вивчення реальних економічних процесів. Такі показники, як прибуток собівартість, капітальні затрати на виробництво та інші нелінійно залежать від обсягу виробництва, витрат ресурсів. Це приводить до необхідності побудови нелінійних економіко-математичних моделей, їх вивченням займаються в розділі «Нелінійне програмування». Перейдемо до загальних формулювань.
Надалі розглядатимемо простір / елементами якого є послідовності, складені з n дійсних чисел / Елементи простору R" називатимемо також точками простору або векторами (n-вимірними) і позначатимемо /
Нехай в просторі R" задана функція /
Загальною задачею математичного програмування називається задача, в якій потрібно знайти найбільше (або найменше) значення функції F,
/
у припущенні, що на змінні х1, ...,хn накладені обмеження
/
Крім зв'язків (4.15), у задачах математичного програмування на змінні xj можуть також накладатися обмеження на знаки аргументів. Деколи ці обмеження не виділяють окремо, а включають в систему обмежень (4.15).
Система співвідношень (4.15) визначає в просторі Rn множину, яка називається областю допустимих розв'язків або множиною обмежень задачі (4.14), (4.15). Точку / яка належить множині обмежень, називають допустимим розв'язком задачі (4.14), (4.15)- Допустимий розв'язок задачі / для якого функція F набуває найбільшого (найменшого) значення, називається розв'язком або оптимальним розв'язком задачі (4.14), (4.15); а / - оптимальним значенням функції F.
Якщо цільова функція F і всі функції / в обмеженнях є лінійними, то задача (4.14), (4.15) називається лінійною або задачею лінійного програмування (див. розділ 1); такі задачі ми вивчали в попередніх розділах. Якщо хоча б одна з функцій F або g, є нелінійною, то ця задача називається нелінійною або задачею нелінійного програмування.
Область допустимих розв'язків нелінійної задачі може бути не опуклою множиною, якщо серед функцій gj в (4.15) є нелінійні функції.
Якщо в n-вимірному просторі Rn визначено множину обмежень, що відповідає системі співвідношень (4.15), то розв'язування задачі (4.15) зводиться до відшукання в множині М такої точки = / (оптимальної точки, або розв'язку), через яку проходить поверхня / найвищого рівня (в задачі на максимум), yайнижчого рівня (в задачі на мінімум). Оптимальна точка X* може знаходитися як на границі, так і всередині множини М.
До розв'язування задачі (4.14), (4.15) можна застосувати такий фізичний (геометричний) підхід:
1. Знайти область М допустимих розв'язків задачі, яка визначається нерівностями (4.14); якщо М - порожня множина, то задача розв'язку не має;
2. Побудувати гіперповерхню / для деякого значення h;
3. Змінюючи значення h, знайти гіперповерхню найвищого (найнижчого) рівня, яка має хоча б одну спільну точку з множиною М; Якщо виявиться, що функція F не обмежена зверху (знизу) на множині, то відповідна задача на максимум (мінімум) не має розв'язку.
4. Якщо розв'язок задачі існує, то кожна точка / , яка належить гіперповерхні найвищого(найнижчого) рівня, є оптимальною, відповідне значення функції / - оптимальним.
Розв’язання графічно задану задачу дробово-лінійного програмування.
Областю допустимих значень є багатокутник ABCDE , який обмежений відрізками прямих.
L1- 2x1 – x2 = 8,
L2- x1 + x2 = 5
L3- -3x1 + x2 = 3
x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)
/
Центр еліпса знаходиться в точці Q(7,7) , а півосі дорівнюють √h і √h відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується .
Підсставивши значення точок ОДЗ знаходимо мінімум і максимум функції.
F(min) = 150 в точці (4;0)
F(max) = 374 в точці (0;0)
Розв’язок даної задачі з роз’ясненнями в Exel і MatCad подані у розділах 3 , 4.
Розв’язання задачі засобами Excel.
2.1 Центр функції мети знаходився поза областю визначення.
У комірки А5-А7 записати цільову функцію та обмежувальні рівняння.
Рівняння
F(x1, x2) = -2 (x1) + x2-> min, max ;
2x1 + x2 <= 8
← (1)
x1 + x2 => 5
← (2)
3x1 - x2 <= -3
← (3)
x >= 0
y >= 0
Визначити точку перетину прямих з осями, записати у відповідні комірки.
Точки перетину
X
Y
4
0
6
4
0
5
5
0
0
1,5
3
6
Побудувати графіки обмежуючих прямих за допомогою «Знаряддя для діаграм».
/
Для позначення множини допустимих розв'язків записати всі комбінації коефіцієнтів двох рівнянь.
Знайти значення цільової функції у кожній точці та знайти максимум та
мінімум.
Точки перетину
Значення функції
Тип
X
Y
0
0
374
MAX
0
1
356
MIN
4,333
0,666
124,690668
1,4
3,6
234,96
4
0
150
MIN
2.2 Центр функції мети знаходився в області визначення.
У комірки А5-А7 записати цільову функцію та обмежувальні рівняння.
Рівняння
F(x1, x2) = -2 (x1) + x2-> min, max ;
2x1 + x2 <= 8
← (1)
x1 + x2 => 5
← (2)
3x1 - x2 <= -3
← (3)
x >= 0
y >= 0
Визначити точку перетину прямих з осями, записати у відповідні комірки.
Точки перетину
X
Y
0
2
3
0
0
7
7
0
0
11
5
0
Побудувати графіки обмежуючих прямих за допомогою «Знаряддя для діаграм».
/
Для позначення множини допустимих розв'язків записати всі комбінації коефіцієнтів двох рівнянь.
Точки перетину
Значення функції
Тип
X
Y
0
0
44
MAX
0
1
38
4,333
0,666
10,66667
MIN
1,4
3,6
15,36
4
0
12
Розв’язання задачу дробово-лінійного програмування засобами MathCad.
MathCAD – це могутнє і в той же час просте універсальне середовище для розв’язку задач у різних галузях науки та техніки, фінансів і економіки, фізики і астрономії, математики і статистики, організації виробництва і управління тощо. На сьогодні MathCAD – одна із найпопулярніших математичних систем.
3.1 Центр функції мети знаходився поза областю визначення.
1. Відриваємо робочу область MATHCAD;
2. Ініціалізуємо X та Y;
3. Ініціалізуємо цільову функцію;
4. Після ключового слова Given задаємо обмеження;
Використовуємо функції Minimize або Maximize для знаходження оптимального розв’язку;
/
/
/
/
/
/
/
/
/
/
/
Розв’язання задачі за допомогою власної програми.
Програма написана в середовищі програмування Qt Creator на мові C++. Авторські права належать мені.
Програма визначає максимум заданої функції задачі дробово-лінійного програмування методом перебору всіх точок.
/
Лістинг
// Лабораторна робота з ММДО. Славич Юрій
#include <iostream>
#include <cmath>
using namespace std;
struct Line
{
double x;
double y;
char sign;
double b;
};
void findPoint(struct Line*, double &, double &);
bool isRight( double, double); //перевірка ОДЗ
void addLimit (double, double ,char , double);
void solution (struct Line &);
struct Line mainA[10];
struct Line max;
unsigned size = 0;
double r1, r2, c1, c2; //коефіціенти при функції
int main(int argc, char* argv[])
{
struct Line arrLine[2];
struct Line maxIn;
struct Line max;
setlocale(LC_ALL, ".1251");
cout << "Розмiрнiсть матрицi: ";
cin >> size;
if (size < 2 || size > 5)
{
cout << "Вихiд за дiапазон.";
return -1;
}
cout << "Введiть матрицю А: " << endl;
for (int i = 0; i < size; i++)
cin >> mainA[i].x >> mainA[i].y >> mainA[i].sign >> mainA[i].b;
addLimit (1, 0, '>', 0);
addLimit (0, 1, '>', 0);
cout << "Радіуси r1 та r2: ";
cin >> r1 >> r2;
cout << "Центр: ";
cin >> c1 >> c2;
solution (max);
cout << "X = " << max.x << endl;
cout << "Y = " << max.y << endl;
cout << "F(max) = " << max.b << endl;
cin.get();
cin.get();
cin.get();
return 0;
}
void solution(struct Line &max)
{
struct Line arrLine[2];
double x, y;
double maxF;
max.b = 0;
for (int i = 0; i < size; i++)
{
arrLine[0] = mainA[i];
for (int j = i + 1; j < size; j++)
{
arrLine[1] = mainA[j];
findPoint(arrLine, x, y);
//cout << x << " " << y << endl;
if (isRight(x, y)&& max.b < (maxF = r1* pow(static_cast<double> (x - c1),2)
+ r2 * pow(static_cast<double> (y - c2),2)))
{
max.x = x;
max.y = y;
max.b = maxF;
}
}
}
}
void findPoint(struct Line* a, double &x, double &y)
{
double det = a[0].x * a[1].y - a[1].x * a[0].y;
double inverseMatr[2][2];
inverseMatr[0][0] = a[1].y / det;
inverseMatr[0][1] = - a[0].y / det;
inverseMatr[1][0] = - a[1].x / det;
inverseMatr[1][1] = a[0].x / det;
x = inverseMatr[0][0] * a[0].b + inverseMatr[0][1] * a[1].b;
y = inverseMatr[1][0] * a[0].b + inverseMatr[1][1] * a[1].b;
x = floor(x * 10000) / 10000;
y = floor(y * 10000) / 10000;
}
void addLimit(double x, double y, char sign, double limit)
{
mainA[size].x = x;
mainA[size].y = y;
mainA[size].sign = sign;
mainA[size].b = limit;
size++;
}
bool isRight(double x, double y)
{
if (x < 0 || y < 0)
return false;
for (int i = 0; i < size; i++)
{
if (mainA[i].sign == '<')
{
if (!(mainA[i].x * x + mainA[i].y * y <= mainA[i].b))
return false;
}
else
if (!(mainA[i].x * x + mainA[i].y * y >= mainA[i].b))
return false;
}
return true;
}
Висновок: на цій лабораторній роботі я ознайомився з задачами нелінійного програмування, набув навиків їх розв’язку та аналізу, оволодів навичками адресації та роботи з формулами в таблицях в Еxcel, оволодів навиками розв’язання оптимізаційних задач в середовищі MathCad.
29.11.2012 17:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора