Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Група:
КН-21
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
із лабораторної роботи №9
«НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ. ОСНОВНІ МЕТОДИ ЇХ РОЗВ’ЯЗУВАННЯ ТА АНАЛІЗУ»
з дисципліни
“Математичні методи дослідження операцій”
Львів – 2012
Мета роботи: ознайомлення з задачами дробово-лінійного програмування, набуття навиків їх розв’язку та аналізу, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку задач дробово-лінійного програмування за допомогою математичних пакетів та розробки оригінальної програми.
Порядок роботи:
1. Теоретичні відомості.
2. Розв’язати графічно задану задачу дробово-лінійного програмування. Звести задану задачу до задачі лінійного програмування.
3. Хід розв’язування задачі симплексним методом(SimplexWin).
4. Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям графічного методу задачі дробово-лінійного програмування.
5. Використовуючи засоби MathCad , розв’язати задану задачу дробово-лінійного програмування.
6. Розробити оригінальну програму. Використовуючи розроблену програму, розв’язати задачу дробово-лінійного програмування.Подати у звіті алгоритм розв'язку задачі (програми), лістинг та порядок використання програми.
Індивідуальне завдання
F(x1, x2) = ( 3x1 - 2x2 ) / ( (-2)x1 +3 x2) max;
2x1 – x28,
x1+ x2 4,
-3x1 + 2x23,
x1 0,x2 0.
Короткі теоретичні відомості
1.1. Економічна і математична постановка задачі дробово-лінійного програмування
Розв’язуючи економічні задачі, часто як критерії оптимальності беруть рівень рентабельності, продуктивність праці тощо. Ці показники математично виражаються дробово-лінійними функціями. Загальну економіко-ійатематичну модель у цьому разі записують так (розглянемо задачу визначення оптимальних обсягів виробництва продукції):
позначимо через прибуток від реалізації одиниці -го виду продукції, тоді загальний прибуток можна виразити формулою:;
якщо — витрати на виробництво одиниці -го виду продукції, то — загальні витрати на виробництво. У разі максимізації рівня рентабельності виробництва цільова функція має вигляд:
(1.1)
за умов виконання обмежень щодо використання ресурсів:
; (1.2)
. (1.3)
Передбачається, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю.
Очевидно, що задача (1.1) — (1.3) відрізняється від звичайної задачі лінійного програмування лише цільовою функцією, що дає змогу застосовувати для її розв’язування за певного модифікування вже відомі методи розв’язання задач лінійного програмування.
1.2. Геометрична інтерпретація задачі дробово-лінійного програмування
У разі, коли задача дробово-лінійного програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом.
Нехай маємо таку задачу:
(1.4)
за умов:
(1.5)
, (1.6)
Спочатку, як і для звичайної задачі лінійного програмування будуємо геометричне місце точок системи нерівностей (1.5), що визначає деякий багатокутник допустимих розв’язків.
Допустимо, що , і цільова функція набуває деякого значення:
.
Після елементарних перетворень дістанемо:
або. (1.7)
Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х1 та х2.
Розглянемо кутовий коефіцієнт нахилу прямої (1.7), що виражає цільову функцію:
. (1.8)
Отже, кутовий коефіцієнт є функцію від Z.
Для визначення умов зростання (спадання) функції (1.8) дослідимо зміну знака її похідної:
(1.9)
Використовуючи формулу (1.9), можна встановити правила пошуку максимального (мінімального) значення цільової функції:
а) якщо , то функція (1.8) є зростаючою, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) також збільшується. Тому у разі, якщо , то для відшукання точки максимуму необхідно повертатипряму, що описує цільову функцію, навколо початку системи координат у напрямку протигодинниковоїстрілки;
б) якщо , то функція (1.8) є спадною, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) зменшується. Тому у разі, якщо , то для відшукання точки максимуму необхідно повертатипряму, що описує цільову функцію, навколо початку системи координат у напрямку загодинниковоюстрілкою.
При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки:
- багатокутник розв’язківзадачі обмежений, - і максимальне та мінімальне значення досягаються у його кутових точках;
- багатокутник розв’язківзадачі необмежений, - однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції;
- багатокутник розв’язків задачі необмежений, - і досягається лише один із екстремумів;
- багатокутник розв’язківзадачі необмежений, - і точки екстремумів визначити неможливо.
Розв’язання графічно задачі дробово-лінійного програмування. Зведення до задачі лінійного програмування.
За допомогою замін у0 = 1 / ( х1 + х2), уі = у0 хі, хі = уі / у0, і = 1,2 та співвідношення у1 + у2 = 1 (1.12) отримаємо F = (3у1 - 2у2) →max
2у1 - у2 ≤ 8 у0,
у1 + у2 ≤ 4у0,
3у1 -2у2 ≤ -3у0,
у1 + у2 = 1
у0 ≥ 0, у1≥ 0, у2 ≥ 0,
-8у0 + 2у1-у2 ≤0,
4у0 ≤ 1,
-3у0 + 3у1 -2у2 ≤ 0,
у1 + у2 = 1
у0 ≥ 0, у1≥ 0, у2 ≥ 0,
Розв’язання задачі лінійного програмування симплекс-методом(SimplexWin).
Крок 0
Базис
БП
y0
y1
y2
x 4
x 5
x 6
z 1
x4
0
-8
2
-1
1
0
0
0
x5
1
4
0
0
0
1
0
0
x6
0
-3
3
-2
0
0
1
0
z1
1
0
1
1
0
0
0
1
ИС
-1M
0
-M-3
-M+2
0
0
0
0
Крок 1
Базис
БП
y0
y1
y2
x 4
x 5
x 6
z 1
y1
0
-4
1
-1/2
1/2
0
0
0
x5
1
4
0
0
0
1
0
0
x6
0
9
0
-1/2
-3/2
0
1
0
z1
1
4
0
3/2
-1/2
0
0
1
ИС
-1M
-4M-12
0
-3/2M+1/2
1/2M+3/2
0
0
0
Крок 2
Базис
БП
y0
y1
y2
x 4
x 5
x 6
z 1
y1
0
0
1
-13/18
-1/6
0
4/9
0
x5
1
0
0
2/9
2/3
1
-4/9
0
y0
0
1
0
-1/18
-1/6
0
1/9
0
z1
1
0
0
31/18
1/6
0
-4/9
1
ИС
-1M
0
0
-31/18M-1/6
-1/6M-1/2
0
4/9M+4/3
0
Крок 3
Базис
БП
y0
y1
y2
x 4
x 5
x 6
z 1
y1
13/31
0
1
0
-3/31
0
8/31
13/31
x5
27/31
0
0
0
20/31
1
-12/31
-4/31
y0
1/31
1
0
0
-5/31
0
3/31
1/31
y2
18/31
0
0
1
3/31
0
-8/31
18/31
ИС
3/31
0
0
0
-15/31
0
40/31
M+3/31
Крок 4
Базис
БП
y0
y1
y2
x 4
x 5
x 6
z 1
y1
11/20
0
1
0
0
3/20
1/5
2/5
x4
27/20
0
0
0
1
31/20
-3/5
-1/5
y0
1/4
1
0
0
0
1/4
0
0
y2
9/20
0
0
1
0
-3/20
-1/5
3/5
ИС
-3/7
0
0
0
0
3/4
1
M
4. Розв’язання задачі засобами Excel.
У комірки А5-А7 записати цільову функцію та обмежувальні рівняння.
Визначити точку перетину прямих з осями, записати у відповідні комірки.
Побудувати графіки обмежуючих прямих за допомогою «Знаряддя для діаграм».
За допомогою функції MINVERSE(Опис: Повертає обернену матрицю для матриці, яка зберігається в масиві. Синтаксис: MINVERSE(масив). Синтаксис функції MINVERSE має такі аргументи. Значення, яке надає відомості для дій, подій, методів, властивостей, функцій або процедур.:
Масив – обов’язковий аргумент. Числовий масив із рівною кількістю рядків і стовпців.
Примітки
Масив може бути заданий діапазоном клітинок, наприклад A1:C3; масивом констант, наприклад {1,2,3;4,5,6;7,8,9}; або іменем того чи іншого.
Якщо будь-яка із клітинок у масиві пуста або містить текст, функція MINVERSE повертає значення помилки #VALUE!.
Функція MINVERSE також повертає значення помилки #VALUE!, якщо кількість рядків у масиві не дорівнює кількості стовпців.
Формули, які повертають масиви, слід вводити як формули масивів.
Обернені матриці, такі як визначники, зазвичай використовуються для розв’язання систем математичних рівнянь із кількома змінними. Добуток матриці та оберненої до неї матриці є одиничною матрицею — квадратним масивом, у якому діагональні значення рівні 1, а всі інші значення рівні 0.
Для прикладу обчислення матриці із двох рядків і двох стовпців припустимо, що діапазон A1:B2 містить букви a, b, c і d, які відповідають будь-яким чотирьом цифрам. У наведеній нижче таблиці показано обернену матрицю до A1:B2.
Функція MINVERSE обчислюється з точністю приблизно до 16 цифр, які можуть призвести до незначної числової помилки в разі незавершеного скасування.
Деякі квадратні матриці не можна обернути, і для них функція MINVERSE повертає значення помилки #NUM!. Визначник матриці, яку не можна обернути (виродженої), дорівнює 0.)обчислити точки перетину.
Знайти значення цільової функції у кожній точці.
Знайти максимум з п.5
5. Розв’язання задачу дробово-лінійного програмування засобами MathCad.
MathCAD – це могутнє і в той же час просте універсальне середовище для розв’язку задач у різних галузях науки та техніки, фінансів і економіки, фізики і астрономії, математики і статистики, організації виробництва і управління тощо. На сьогодні MathCAD – одна із найпопулярніших математичних систем.
Записати всі можливі попарні комбінації обмежувальних рівнянь.
Записати відповідні матриці стовпці вільних членів.
Обчислити добуток кожної оберненої матриці коефіцієнтів рівнянь та матриці стовпчика вільних членів.
Відкинути точки, що не входять до області ОДЗ.
Для побудови ОДЗ зробити перетворення рівнянь.
Побудувати графіки функцій у правій частині робочої області, записуючи рівняння через кому.
Записати цільову функцію
Обчислюємо значення цільової функції в крайніх точках.
6. Розроблення оригінальної програми.
Інструкція користувачеві:
Програма написана в середовищі програмування Borland C++ на мові C.
Дана програма будує задачу лінійного програмування з задачі лінійно-дробового програмування. Для цього користувач вводить необхідні значення цільової функції та обмежень, керуючись підказками в середовищі.
Лістинг програми:
#include <stdio.h>
#include <conio.h>
#define N 7
#define M 7
int main(void){
int mas[M][N];
int mas1[M+1][N+1];
int b[M];
int d[3];
int i,j,m,n;
puts("Vvedit koeficientu funkcii metu");
printf("d1=");
scanf("%d",&d[0] );
printf("d2=");
scanf(" %d",&d[1] );
puts("Vvedit kilkist rivnyny");
scanf("%d",&m);
puts("Vvedit kilkist zminnuh");
scanf("%d",&n);
puts("Vvedit koeficientu obmegen:");
for(int i=0;i<m;i++){
for (int j=0;j<n; j++)
scanf("%d",&mas[i][j]) ;
}
puts("Vvedit vilni zminni");
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
for(int i=0;i<m;i++){
for (int j=0;j<n; j++)
mas1[i][j]=mas[i][j] ;
}
for(int i=0;i<m;i++)
mas1[i][n]=-b[i];
printf("Funkciya metu:\n %dy1%+dy2->max\n",d[0],d[1]);
puts("Peretvorena zadacha");
for(int i=0;i<m;i++){
for (int j=0;j<n+1;j++){
if(j==0){printf("%dy1",mas1[i][j]) ;}
else{
if(j==n ){printf("%+dy%d",mas1[i][j],0);}
else{
printf("%+dy%d",mas1[i][j],j+ 1) ;}
if(j==n ){printf("<=0;\n");}
} } } printf("y1+y2=1;");
getch();
return 0;
}
Скріншот виконання програми:
Висновок: У даній роботі я ознайомився з задачами дробово- лінійного програмування, набув навиків їх розв’язку та аналізу, оволодів навичками адресації та роботи з формулами в таблицях в Еxcel, оволодів навиками розв’язання оптимізаційних задач в середовищі MathCad, набув навиків розв’язку задач дробово-лінійного програмування за допомогою математичних пакетів та розробки оригінальної програми.
29.11.2012 17:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора