Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Житомирський державний технологічний університет
Кафедра: ПЗОТ
Група: ЗПІК 09-1
Курс: 5
№ залікової: 4309018
Курсова робота
з предмету
Математичні методи дослідження операцій
Житомир, 2012 р.
Зміст
Вступ
Робота
Теоретичні відомості
Керівництво програміста
Висновки
Література
Вступ
Розвиток сучасного суспільства характеризується підвищенням технічного рівня, ускладненням організаційної структури виробництва, поглибленням суспільного поділу праці, пред'явленням високих вимог до методів планування і господарського керівництва. У цих умовах тільки науковий підхід до керівництва економічним життям суспільства дозволить забезпечити високі темпи розвитку народного господарства. Одним з необхідних умов подальшого розвитку економічної науки є застосування точних методів кількісного аналізу, широке використання математики. В даний час новітні досягнення математики і сучасної обчислювальної техніки знаходять все більш широке застосування в економічних дослідженнях і плануванні. Цьому сприяє розвиток таких розділів математики, як математичне програмування, теорія ігор, теорія масового обслуговування, а також бурхливий розвиток швидкодіючої електронно-обчислювальної техніки. Уже накопичено достатній досвід постановки та вирішення економічних задач за допомогою математичних методів. Особливо успішно розвиваються методи оптимального планування, які й становлять сутність математичного програмування. Однією з основних стає завдання створення єдиної системи оптимального планування та управління народним господарством на базі широкого застосування математичних методів і електронно-обчислювальної техніки в економіці. В даний час лінійне програмування є одним з найбільш вживаних апаратів математичної теорії оптимального прийняття рішень. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих обсягів. Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі прикладної математики. Лінійне програмування - це наука про методи дослідження та відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування ставляться до завдань на умовний екстремум функції. За типом розв'язуваних задач методи поділяються на універсальні і спеціальні. За допомогою універсальних методів можуть вирішуватися будь-які завдання лінійного програмування (ЗЛП). Спеціальні методи враховують особливості моделі завдання, її цільової функції і системи обмежень. Особливістю задач лінійного програмування є те, що екстремуму цільова функція досягає на кордоні області допустимих рішень. Класичні ж методи диференціального обчислення пов'язані з перебуванням екстремумів функції у внутрішній точці області допустимих значень. Звідси - необхідність розробки нових методів. Лінійне програмування являє собою найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання: 1. раціонального використання сировини та матеріалів; 2. завдання оптимального розкрою; 3. оптимізації виробничої програми підприємств; 4. оптимального розміщення і концентрації виробництва; 5. складання оптимального плану перевезень, роботи транспорту (транспортні завдання); 6. управління виробничими запасами; 7. і багато інших, що належать сфері оптимального планування
Робота
Дана програма реалізована на мові С++ .
Програма виводить на екран розвязок задачі яка виконується 4 чисельними методами одновимірної оптимізації, функції 2x^3-6x^2+6x-1. (методи: Фібеначі, золотий переріз, дихотомії і найпростішого перебору )
Програма запускається в середовищі BORLAND C++
Потрібно відкрити файл main.cpp для запуску програми .
Нижче приведемо код програми для знаходження 4 методів одновимірної оптимізації реалізований в С++.
#include <stdio.h>
#include <math.h>
unsigned int mas_stepen[5];
long double mas_koef[6];
unsigned int kx = 2;
double eps = 0.1;
double a,b;
unsigned int chisla_fibonachi(unsigned int chislo)
{
unsigned int sum = 0;
if(chislo == 0 || chislo == 1)
return 1;
sum = chisla_fibonachi(chislo-2) + chisla_fibonachi(chislo-1);
return sum;
}
long double run(long double x)
{
//функція 2x^3-6x^2+6x-1
return 2*x*x*x-6*x*x+6*x-1;
}
void fibonachi(double a0, double b0, double epsilon)
{
long double fib = 0.0, z =0.0 , y = 0.0, f_z = 0.0, f_y = 0.0;
unsigned int i = 0, n = 0, k = 0;
double a = 0, b = 0,fibonachi_n, fibonachi_n1, fibonachi_n2;
printf("Метод Фібоначчі\n");
fib = (b0 - a0)/epsilon;
do
{
i++;
if ((chisla_fibonachi(i+1)<=fib) && (fib<=chisla_fibonachi(i+2)))
{
n=i;
break;
}
}while(1);
printf("Кількість ітерацій = %d\n",n);
fibonachi_n = (double)chisla_fibonachi(n);
fibonachi_n1 = (double)chisla_fibonachi(n+1);
fibonachi_n2 = (double)chisla_fibonachi(n+2);
k++;
y=a0+fibonachi_n/fibonachi_n2*(double)(b0-a0);
f_y=run (y);
z=a0+fibonachi_n1/fibonachi_n2*(double)(b0-a0);
f_z=run (z);
if (f_y<=f_z)
{
a=a0;
b=z;
}
else
{
a=y;
b=b0;
}
for(k=2;k<=n;k++)
{
if (f_y<=f_z)
{
z=y;
f_z=f_y;
y=a+(double)chisla_fibonachi(n-k+1)/fibonachi_n2*(double)(b0-a0);
f_y=run (y);
}
else
{
y=z;
f_y=f_z;
z=a+(double)chisla_fibonachi(n-k+2)/fibonachi_n2*(double)(b0-a0);
f_z=run (z);
}
if (f_y<=f_z)
{
a=a;
b=z;
}
else
{
a=y;
b=b;
}
}
if (f_y<=f_z)
printf("Відповідь:x= %Lf f(x)= %Lf\n",y,f_y);
else
printf("Відповідь:x= %Lf f(x)= %Lf\n",z,f_z);
printf("<---------------------------------------->\n");
}
void golden_ration(double a0, double b0, double epsilon)
{
long double c = 0.0, z =0.0 , y = 0.0, f_z = 0.0, f_y = 0.0;
unsigned int k = 0;
double a = 0, b = 0;
printf("Метод Золотого перерізу\n");
c = (3 - sqrt(5))/2;
k = 1;
y = a0 + c * (b0-a0);
f_y = run(y);
z = a0+(1-c)*(b0-a0);
f_z = run(z);
if (f_y<=f_z)
{
a=a0;
b=z;
}
else
{
a=y;
b=b0;
}
if(b-a>epsilon)
{
do
{
k++;
if (f_y<=f_z)
{
z=y;
f_z=f_y;
y=a+c*(b-a);
f_y=run (y);
}
else
{
y=z;
f_y=f_z;
z=a+c*(b-a);
f_z=run (z);
}
if (f_y<=f_z)
{
a=a;
b=z;
}
else
{
a=y;
b=b;
}
}while(b-a>epsilon);
printf("Кількість ітерацій = %d\n",k);
if (f_y<=f_z)
printf("Відповідь:x= %Lf f(x)= %Lf\n",y,f_y);
else
printf("Відповідь:x= %Lf f(x)= %Lf\n",z,f_z);
}
else
{
printf("Кількість ітерацій = %d\n",k);
if (f_y<=f_z)
printf("Відповідь:x= %Lf f(x)= %Lf\n",y,f_y);
else
printf("Відповідь:x= %Lf f(x)= %Lf\n",z,f_z);
}
printf("<-------------------------------------------->\n");
}
void brute_force(double a0, double b0, double epsilon)
{
long double x =0.0 , xl = 0.0,x0 = 0.0, f_x = 0.0, f_xl = 0.0, h = 0.0;
unsigned int k = 0;
double a = 0, b = 0;
printf("Метод найпростішого перебору\n");
x0=a0;
do
{
if(h==0)
h=1;
else
h=h/2;
k=0;
xl=x0+k*h;
f_xl=run(xl);
do
{
f_xl=run(xl);
k++;
x=x0+k*h;
f_x=run(x);
if (f_x<f_xl)
xl=x;
else
{
if(k>1)
x0=x0+(k-2)*h;
}
}while(f_x<f_xl);
a=xl; b=x;
}while(h>eps);
x=(a+b)/2;
f_x=run(x);
printf("Кількість ітерацій = %d\n",k);
printf("Відповідь:x= %Lf f(x)= %Lf\n",x,f_x);
printf("<------------------------------------>\n");
}
void dichotomy(double a0, double b0, double epsilon)
{
long double x = 0.0, y = 0.0, z = 0.0, f_x = 0.0, f_y = 0.0, f_z = 0.0;
unsigned int k = 0;
double a = 0, b = 0, sigma = 0.001;
printf("Метод дихотомії\n");
while(epsilon <= sigma)
{
sigma = sigma/10;
}
a=a0;
b=b0;
do
{
k++;
y=(b+a-sigma)/2;
z=(b+a+sigma)/2;
f_y=run(y);
f_z=run(z);
if (f_y<=f_z)
{
x=y;
f_x=f_y;
a=a;
b=z;
}
else
{
x=z;
f_x=f_z;
a=y;
b=b;
}
}while(b-a>epsilon);
k++;
y=(b+a-sigma)/2;
z=(b+a+sigma)/2;
f_y=run(y);
f_z=run(z);
if (f_y<=f_z)
{
x=y;
f_x=f_y;
a=a;
b=z;
}
else
{
x=z;
f_x=f_z;
a=y;
b=b;
}
printf("Кількість ітерацій = %d\n",k);
printf("Відповідь:x= %Lf f(x)= %Lf\n",x,f_x);
printf("<------------------------------------>\n");
}
int main()
{
printf("Розв’язання задачі чотирма чисельними методами одновимірної оптимізації\n");
printf("функція 2x^3-6x^2+6x-1\n");
printf("Точність обрахунків 0.1\n");
printf("Початок відрізку 0\n");
printf("Кінець відрузку 4\n");
eps=0.1;
a=0;
b=4;
fibonachi(a, b, eps);
golden_ration(a, b, eps);
brute_force(a, b, eps);
dichotomy(a, b, eps);
return (0);
}
Теоретичні відомості
Розглянемо детально методи розв’язування одновимірних задач, а саме: метод дихотомії, метод золотого перерізу і метод Фібоніччі.
Одновимірна оптимізація полягає в знаходженні точки , в якій цільова функція приймає максимальне або мінімальне значення. Часто в постановках задач може бути заданий відрізок , в якому знаходиться оптимальне рішення.
Функція має локальний мінімум в точці , якщо при довільному існує окіл такий, що для всіх значень в цьому околі . Функція має глобальний мінімум в точці , якщо для всіх х справедлива рівність .
Відповідно функція має локальний максимум в точці , якщо при довільному існує окіл такий, що для всіх значень в цьому околі . Функція має глобальний мінімум в точці , якщо для всіх х справедлива рівність .
Класичний підхід до задачі знаходження екстремумів функції полягає в пошуку умов, яким вони повинні задовольняти. Необхідною умовою екстремуму в точці являється рівність нулю першої похідної (теорема Ферма), тобто вимагається розв’язати рівняння: . Даному рівнянню задовольняють як локальні та глобальні екстремуми, так і точки перегину функції, тому приведена умова є лише необхідною умовою, але не достатньою.
З метою отримання достатніх умов вимагається обчислення значень других похідних в точках, що задовольняють рівняння . При цьому доведено, що мінімуму функції відповідає додатне значення другої похідної, тобто , а максимуму – від’ємне, тобто . Однак, якщо друга похідна дорівнює 0, ситуація залишається невизначеною і необхідно досліджувати вищі похідні. При цьому якщо перша вища похідна не рівна нулю має парний порядок, то екстремум існує, в іншому випадку – ні.
Дамо визначення унімодальної функції при пошуку мінімуму.
Неперервна функція називається унімодальною на відрізку якщо:
точка локального мінімуму функції належить відрізку ;
для довільних двох точок відрізка х1 і х2, взятих по одну сторону від точки мінімуму, точці х1 більш близькій до точки мінімуму відповідає менше значення функції, тобто при або при справедлива нерівність .
Достатня умова унімодальності функції на відрізку ґрунтується на наступній теоремі:
Якщо функція двічі диференційована на відрізку і в будь-якій точці цього відрізка, то - унімодальна функція на відрізку .
Відмітимо, що умова визначає множину точок, на якій функція являється опуклою вниз. Умова ж визначає опуклу вгору функцію, яка на відрізку має максимум і також являється унімодальною.
Метод половинного ділення, який також називається методом дихотомії, являється процедурою послідовного пошуку мінімуму фунуції. Нехай визначено відрізок , якому належить точка локального мінімуму х, і функція являється унімодальною на цьому відрізку. Далі для звуження проміжку унімодальності використовуються дві точки і , розташовані симетрично на відстані від середини відрізка:
;
.
Константа повинна бути меншою допустимої кінцевої довжини відрізка, Δk= bk- ak > 0.
Потім обчислюють значення функції в цих точках y1=f(x1) і y2=f(x2) і в залежності від їх співвідношення нові межі відрізка унімодальності [a1, b1] будуть наступні:
• y1 < y2, a1=a0 і b1=x2 ;
• y1 > y2, a1=x1 і b1=b0 ;
• y1 = y2, a1=x1 і b1= x2 .
В цьому звуженому проміжку [a1, b1] знову розраховуються дві точки х1(1) і х2(1), симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова Δk = bk-ak ≤ ε, де ε – точність пошуку, і тоді в якості точки локального мінімуму можна наближено прийняти середину відрізку .
Назва методу половинного ділення мотивована тим, що якщо величина ε достатньо мала, то довжина відрізка унімодальності (b – a) зменшується майже вдвічі.
Наступним методом знаходження екстремуму для задач одновимірної оптимізації є метод золотого перерізу.
Термін “золотий переріз” ввів Леорандо да Вінчі. Точка х1 являється золотим перерізом відрізка , якщо відношення довжини b-a всього відрізка до довжини b-х1 більшої частини дорівнює відношенню довжини більшої до довжини х1-а меншої частини, тобто х1 – золотий переріз, якщо справедлива рівність: . Аналогічно, точка х2 симетрична точці х1 відносно середини відрізка , являється другим золотим перерізом цього відрізка.
Відмітимо властивість золотого перерізу: точка х1 одночасно являється золотим перерізом відрізка , а друга точка х2 – золотим перерізом відрізка .
Суть методу золотого перерізу заклечається в наступному. Спочатку на вихідному відрізку знаходяться точки х1 і х2 по наступним формулам:
- коефіцієнт зжимання.
Потім обчислюють значення функції в точках х1 і х2, тобто . При цьому можливі два випадки:
, в цьому випадку новий відрізок буде рівним і . На цьому відрізку знову обираються дві точки
, тоді новий відрізок будуть становити: . На новому відрізку також обираються дві точки
І в першому і в другому випадках розраховується лише одна нова точка (друга відома). В новій точці обчислюється значення функції і знову відбувається порівняння в двох точках, і в залежності від цього обирається новий відрізок. Процедура виконується до тих пір, доки не буде виконуватись умова , де - точність пошуку.
Розглянемо також метод Фібоначчі для розв’язування одновимірних задач . Цей метод названий так зважаючи на появу при пошуку проміжків унімрдальності чисел Фібоначчі і використовується, якщо кількість ітерації обмежена . Суть методу в тому, що на кожному кроці точка наступного обчислення обирається симетрично відносно середини відрізка локалізації до точки, що лежить всередині цього відрізку, уже проведеного обчислення. Тобто в процесі пошуку інтервалу (x1; x3) з точкою х2, вже лежачою в цьому інтервалі, наступна точка х4 завжди вибирається так, що х3–х4 = х2–х1 або х4-х1 = х3-x2, тобто x4=х1-х2+х3.
Керівництво програміста
C++ (Сі-плюс-плюс або Сі-плас-плас) — мова програмування високого рівня з підтримкою декількох парадигм програмування: об'єктно-орієнтованої, узагальненої та процедурної. Розроблена Б'ярном Страуструпом (англ. Bjarne Stroustrup) в AT&T Bell Laboratories (Мюррей-Хілл, Нью-Джерсі) у 1979 році та названа «Сі з класами». Страуструп перейменував мову у C++ у 1983 р. Базується на мові С. Визначена стандартом ISO/IEC 14882:2003.[1]
У 1990-х роках С++ стала однією з найуживаніших мов програмування загального призначення. Мову використовують для системного програмування, розробки програмного забезпечення, написання драйверів, потужних серверних та клієнтських програм, а також для розробки розважальних програм таких як відео ігри. С++ суттєво вплинула на інші, популярні сьогодні, мови програмування: С# та Java.
Особливості мови
При створенні С++ прагнули зберегти сумісність з мовою С. Більшість програм на С справно працюватимуть і з компілятором С++. С++ має синтаксис, заснований на синтаксисі С.
Нововведеннями С++ порівняно з С є:
підтримка об'єктно-орієнтованого програмування через класи;
підтримка узагальненого програмування через шаблони;
доповнення до стандартної бібліотеки;
додаткові типи даних;
обробка винятків;
простори імен;
вбудовані функції;
перевантаження операторів;
перевантаження імен функцій;
посилання і оператори управління вільно розподіленою пам'яттю.
У 1998 році ратифіковано міжнародний стандарт мови С++: ISO/IEC 14882 «Standard for the C++ Programming Language». Поточна версія цього стандарту — ISO/IEC 14882:2003.
Приклад С++
#include <iostream>
int main() {
std::cout << "Hello, world!" << std::endl;
return 0;
}
Переваги мови C++
Швидкодія. Швидкість роботи програм на С++ практично не поступається програмам на С, хоча програмісти отримали в свої руки нові можливості і нові засоби.
Масштабованість. На мові C++ розробляють програми для найрізноманітніших платформ і систем.
Можливість роботи на низькому рівні з пам'яттю, адресами, портами. (Що, при необережному використанні, може легко перетворитися на недолік.)
Можливість створення узагальнених алгоритмів для різних типів даних, їхня спеціалізація, і обчислення на етапі компіляції, з використанням шаблонів.
Підтримуються різні стилі та технології програмування, включаючи традиційне директивне програмування, ООП, узагальнене програмування, метапрограмування (шаблони, макроси).
Недоліки мови C++
Наявність безлічі можливостей, що порушують принципи типобезпеки приводить до того, що в С++ програми може легко закрастися важковловима помилка. Замість контролю з боку компілятора розробники вимушені дотримуватися вельми нетривіальних правил кодування. По суті, ці правила обмежують С++ рамками якоїсь безпечнішої підмови. Більшість проблем типобезпеки С++ успадкована від С, але важливу роль в цьому питанні грає і відмова автора мови від ідеї використовувати автоматичне управління пам'яттю (наприклад, збірку сміття). Так візитною карткою С++ стали вразливості типу «переповнювання буфера».
Погана підтримка модульності. Підключення інтерфейсу зовнішнього модуля через препроцесорну вставку заголовного файлу (#include) серйозно уповільнює компіляцію, при підключенні великої кількості модулів. Для усунення цього недоліку, багато компіляторів реалізують механізм прекомпіляциі заголовних файлів (англ. Precompiled Headers).
Недостача інформації про типи даних під час компіляції (CTTI).
Мова C++ є складною для вивчення і для компіляції.
Деякі перетворення типів неінтуїтивні. Зокрема, операція над беззнаковим і знаковим числами видає беззнаковий результат.
Препроцесор С++ (успадкований від C) дуже примітивний. Це приводить з одного боку до того, що з його допомогою не можна (або важко) здійснювати деякі завдання метапрограмування, а з іншою, в наслідку своєї примітивності, він часто приводить до помилок і вимагає багато дій з обходу потенційних проблем. Деякі мови програмування (наприклад, Scheme і Nemerle) мають набагато могутніші і безпечніші системи метапрограмування (також звані макросами, але макроси С/С++ вони мало нагадують).
Висновоки:
В рамках даної курсової роботи була представлена програма для вирішення 4 методів одновимірної оптимізації це дасть змогу нам усунути непиємності які зв’язані з підвищенням технічного рівня, ускладненням організаційної структури виробництва, поглибленням суспільного поділу праці, пред'явленням високих вимог до методів планування і господарського керівництва для поліпшення умов праці, затрати на час виконання певної роботи та іншого.
Список використаної літератури
Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 912с.: ил. – Парал. тит. англ.
Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации: учеб. пособие-2-ое изд.-М.:ФИЗМАТЛИТ, 2005
Н. И. Глебов, Ю. А. Кочетов, А. В. Плясунов. Методы оптимизации: учебное пособие. - Новосибирск: Новосибирский государственный университет, 2000. – 105 с.
Васильев Ф. П. Методы оптимизации. – М.: Издательство «Факториал Пресс», 2002. – 824 с.
Волков И. К., Загоруйко Е. А. Исследование операций-М.: МГТУ
им. Н. Э. Баумана, 2000
6. Бейко И.В. и др. Методы и алгоритмы решения задач оптимизации. К: Высш.шк., 1983. – 513с
7. Ю. А. Кочетов, А. В. Плясунов. Методы оптимизации: учебное пособие. - Новосибирск: Новосибирский государственный университет, 2000. – 105 с.
Міністерство освіти і науки, молоді та спорту України
Житомирський державний технологічний університет
Кафедра: ПЗОТ
Група: ЗПІК 09-1
Курс: 5
№ залікової: 4309022
Курсова робота
з предмету
Математичні методи дослідження операцій
Виконав: Крот В. С.
Перевірив: ________________
Житомир, 2012 р.
13.01.2013 15:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора