Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ. ОСНОВНІ МЕТОДИ ЇХ РОЗВ’ЯЗУВАННЯ ТА АНАЛІЗУ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра автоматизованих систем управління
Лабораторна робота №9
з дисципліни “Математичні методи дослідження операцій”
на тему
«НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ. ОСНОВНІ МЕТОДИ ЇХ РОЗВ’ЯЗУВАННЯ ТА АНАЛІЗУ»
Львів – 2012
Мета роботи: ознайомлення з задачами дробово-лінійного програмування, набуття навиків їх розв’язку та аналізу, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку задач дробово-лінійного програмування за допомогою математичних пакетів та розробки оригінальної програми.
Порядок роботи:
Розв’язати графічно задану задачу дробово-лінійного програмування.
Звести задану задачу до задачі лінійного програмування. Хід розв’язування задачі симплексним методом навести в таблиці.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям графічного методу задачі дробово-лінійного програмування.
Використовуючи один із математичних пакетів ( наприклад, SimplexWin ), розв’язати задачу дробово-лінійного програмування.
Розробити оригінальну програму. Використовуючи розроблену програму, розв’язати задачу дробово-лінійного програмування. Подати у звіті алгоритм розв'язку задачі (програми), лістинг та порядок використання програми.
Проінтерпретувати отримані результати для вихідної задачі.
Короткі теоретичні відомості
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) зменшується. Тому у разі, якщо , то для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку за годинниковою стрілкою.
При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки:
- багатокутник розв’язків задачі обмежений, - і максимальне та мінімальне значення досягаються у його кутових точках;
- багатокутник розв’язків задачі необмежений, - однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції;
- багатокутник розв’язків задачі необмежений, - і досягається лише один із екстремумів;
- багатокутник розв’язків задачі необмежений, - і точки екстремумів визначити неможливо.
1.Постановка задачі
Розв’язати задачу дробово-лінійного програмування графічно і симплексним
методом.
Варіант 67:
F(x1, x2) = ( 3x1 + 3x2 ) / ( 2x1 - 3x2) max ;
4x1 + 2x2 12,
x1 + 2x2 10,
2x1 + 2x2 = 6,
x1 0, x2 0.
Зведення задачі до задачі лінійного програмування.
За допомогою замін
max ;
уі = у0* хі,
хі = уі / у0, і = 1,2
у1 + у2 = 1
отримаємо
F= ( 3y1 + 3y2) max ;
-12 y0 + 4y1 + 2y2 0,
-10 y0 + y1 + 2y2 0,
-6 y0 + 2y1 + 2y2 = 0,
-14 y0+2y1 + y2 = 0,
0y0 +2y1 -3 y2 =1
2.Розв’язання задачі симплекс-методом:
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Оскільки в правій частині присутні негативні значення, помножимо відповідні рядки на (-1).
Визначимо максимальне значення цільової функції F (X) = x 1 + x 2 при наступних умовах-обмежень.
- 3x 1 + 2x 2 ≤ 6
x 1 + 2x 2 ≥ 3
x 1 ≤ 3
x 2 ≤ 5
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).
-3x 1 + 2x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 5
Введемо штучні змінні x: в 2-м рівність вводимо змінну x 7;
-3x 1 + 2x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 + 0x 7 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 + 1x 7 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 + 0x 7 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 + 0x 7 = 5
Для постановки задачі на максимум цільову функцію запишемо так:
F (X) = x 1 + x 2 - Mx 7 → max
З рівнянь виражаємо штучні змінні:
x 7 = 3-x 1-2x 2 + x 4
які підставимо в цільову функцію:
F (X) = (1 +1 M) x 1 + (1 +2 M) x 2 + (-1M) x 4 + (-3M) → max
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
-3
2
1
0
0
0
0
1
2
0
-1
0
0
1
1
0
0
0
1
0
0
0
1
0
0
0
1
0
Вирішимо систему рівнянь щодо базисних змінних:
x 3, x 7, x 5, x 6,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,6,0,3,5,3)
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 3
6
-3
2
1
0
0
0
0
x 7
3
1
2
0
-1
0
0
1
x 5
3
1
0
0
0
1
0
0
x 6
5
0
1
0
0
0
1
0
F (X0)
-3M
-1-1M
-1-2M
0
1M
0
0
0
Переходимо до основного алгоритму симплекс-метода.
Ітерація № 0.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 2, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i2
і з них виберемо найменше:
Отже, 2-ий рядок є провідною.
Дозволяє елемент дорівнює (2) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min
x 3
6
-3
2
1
0
0
0
0
3
x 7
3
1
2
0
-1
0
0
1
1 1/2
x 5
3
1
0
0
0
1
0
0
-
x 6
5
0
1
0
0
0
1
0
5
F (X1)
-3M
-1-1M
-1-2M
0
1M
0
0
0
0
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 3
3
-4
0
1
1
0
0
-1
x 2
1 1/2
1/2
1
0
-1 / 2
0
0
1/2
x 5
3
1
0
0
0
1
0
0
x 6
3 1/2
-1 / 2
0
0
1/2
0
1
-1 / 2
F (X1)
1 1/2
-1 / 2
0
0
-1 / 2
0
0
1/2 +1 M
Ітерація № 1.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 4, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i4
і з них виберемо найменше:
Отже, 1-а рядок є провідною.
Дозволяє елемент дорівнює (1) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min
x 3
3
-4
0
1
1
0
0
-1
3
x 2
1 1/2
1/2
1
0
-1 / 2
0
0
1/2
-
x 5
3
1
0
0
0
1
0
0
-
x 6
3 1/2
-1 / 2
0
0
1/2
0
1
-1 / 2
7
F (X2)
1 1/2
-1 / 2
0
0
-1 / 2
0
0
1/2 +1 M
0
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 4
3
-4
0
1
1
0
0
-1
x 2
3
-1 1/2
1
1/2
0
0
0
0
x 5
3
1
0
0
0
1
0
0
x 6
2
1 1/2
0
-1 / 2
0
0
1
0
F (X2)
3
-2 1/2
0
1/2
0
0
0
1M
Ітерація № 2.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 1, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i1
і з них виберемо найменше:
Отже, 4-й рядок є провідною.
Дозволяє елемент дорівнює (1 1/2) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min
x 4
3
-4
0
1
1
0
0
-1
-
x 2
3
-1 1/2
1
1/2
0
0
0
0
-
x 5
3
1
0
0
0
1
0
0
3
x 6
2
1 1/2
0
-1 / 2
0
0
1
0
1 1/3
F (X3)
3
-2 1/2
0
1/2
0
0
0
1M
0
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 4
8 1/3
0
0
-1 / 3
1
0
2 2/3
-1
x 2
5
0
1
0
0
0
1
0
x 5
1 2/3
0
0
1/3
0
1
-2 / 3
0
x 1
1 1/3
1
0
-1 / 3
0
0
2/3
0
F (X3)
6 1/3
0
0
-1 / 3
0
0
1 2/3
1M
Ітерація № 3.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 3, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i3
і з них виберемо найменше:
Отже, 3-а рядок є провідною.
Дозволяє елемент дорівнює (1/3) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min
x 4
8 1/3
0
0
-1 / 3
1
0
2 2/3
-1
-
x 2
5
0
1
0
0
0
1
0
-
x 5
1 2/3
0
0
1/3
0
1
-2 / 3
0
5
x 1
1 1/3
1
0
-1 / 3
0
0
2/3
0
-
F (X4)
6 1/3
0
0
-1 / 3
0
0
1 2/3
1M
0
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 4
10
0
0
0
1
1
2
-1
x 2
5
0
1
0
0
0
1
0
x 3
5
0
0
1
0
3
-2
0
x 1
3
1
0
0
0
1
0
0
F (X4)
8
0
0
0
0
1
1
1M
Кінець ітерацій: індексна рядок не містить негативних елементів - знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 4
10
0
0
0
1
1
2
-1
x 2
5
0
1
0
0
0
1
0
x 3
5
0
0
1
0
3
-2
0
x 1
3
1
0
0
0
1
0
0
F (X5)
8
0
0
0
0
1
1
1M
Оптимальний план можна записати так:
x 4 = 10
x 2 = 5
x 3 = 5
x 1 = 3
F (X) = 1 • 5 + 1 • 3 = 8
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнюю таблиці, що відповідають ітераціям графічного методу задачі дробово-лінійного програмування.
4.Використовуючи один із математичних пакетів (SimplexWin),
розв’язую задачу дробово-лінійного програмування.
Ввід даних:
Обчислення:
5.Розв’язання задачі за допомогою власної програми
Дана програма здійснює перехід до лінійного вигляду задачі, що дозволяє розв’язувати її вже відомими методами лінійного прграмування.
Текст програми:
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
setlocale (LC_ALL, ".1251");
cout<<"Програма реалізована Саврук С.С."<<endl;
int n,i;
cout<<"Введiть кiлькiсть змiних: ";
cin>>n;
if (n>5) return 0;
double kofz[5], kofch[5];
cout<<"Введiть коефiцiєнти чисельника"<<endl;
for (i=0;i<n;i++)
{
cout<<i+1<<": ";
cin>>kofch[i];
}
cout<<"Введiть коефiцiєнти знаменика"<<endl;
for (i=0;i<n;i++)
{
cout<<i+1<<": ";
cin>>kofz[i];
}
cout<<"Введiть кiлкiсть рiвнянь обмежень:";
int m,j;
cin>>m;
if (m>9) return 0;
double obmkof[9][6];
for (j=0;j<m;j++)
{
cout<<"Введiть коефiцiєнти рiвняня обмежень "<<j+1<<": ";
for (i=0;i<n;i++)
cin>>obmkof[j][i];
cout<<"Введiть знак нерiвностi: ";
char znak;
cin>>znak;
cout<<"Введiть значення нерiвностi: ";
cin>>obmkof[j][n];
if (znak=='>')
for (i=0;i<=n;i++)
obmkof[j][i]=obmkof[j][i]*(-1);
}
//Перетворення
cout<<"Цiльова функцiя:"<<endl<<"F(y)=";
for (i=0;i<n;i++)
printf("%+0.2lf*y%i",kofch[i],i+1);
cout<<endl<<"Обмеження:"<<endl;
for (j=0;j<m;j++)
{cout<<j+1<<": ";
printf("%+0.2lf*y0",-obmkof[j][n]);
for (i=0;i<n;i++)
printf("%+0.2lf*y%i",obmkof[j][i],i+1);
cout<<"<0"<<endl;
}
for(i=1;i<n;i++)
cout<<"y"<<i<<"+";
cout<<"y"<<n<<"=1"<<endl;
cout<<"xi=yi/y0; y0=1/";
for(i=0;i<n;i++)
printf("%+0.2lf*x%i",kofz[i],i+1);
cin>>i;
return 0;
}
Результат виконання програми:
Результат використаємо в подальшому ході роботи для розв’язування за допомогою програми SimplexWin.
Висновок: на цій лабораторній роботі я ознайомився з задачами дробово-лінійного програмування, набув навиків їх розв’язку та аналізу, оволодів навичками адресації та роботи з формулами в таблицях в Еxcel, набув навиків розв’язку задач дробово-лінійного програмування за допомогою математичних пакетів та розробки оригінальної програми.
04.05.2012 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора