МІНІСТЕРСТВО ОСВІТИ І НАУКИ  УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

 

До друку та в світ

дозволяю на підставі

«Єдиних правил»,

п.2.6.14

Заступник першого проректора-                      В.Б. Юскаєв

начальник організаційно-методичного

управління

2718 МЕТОДИЧНІ ВКАЗІВКИ

до практичного заняття на тему

“Метод простого випадкового пошуку рішень, наближених до оптимального”

з дисципліни „Методологія та організація наукових досліджень”

для магістрів  факультету електроніки та інформаційних технологій

 

Усі цитати, цифровий,

фактичний матеріал

та бібліографічні                             

відомості перевірені,                                  

запис одиниць                                 

відповідає                                        

стандартам

 

Укладач                                                                     В.В. Авраменко

                                                                  

Відповідальний за випуск                                      А.С. Довбиш

Декан факультету електроніки

та інформаційних технологій                                С.І. Проценко

 

Суми

Видавництво СумДУ

2009

 

Міністерство освіти і науки України

Сумський державний університет

 

 

 

 

 

 

 

 

 2718 МЕТОДИЧНІ ВКАЗІВКИ

до практичного заняття на тему

“Метод простого випадкового пошуку рішень, наближених до оптимального”

 

з дисципліни "Методологія та організація наукових досліджень”

для магістрів  факультету електроніки та інформаційних технологій

 

 

 

 

 

 

 

 

 

 

 

 

 

Суми

Видавництво СумДУ

2009

 

Методичні вказівки до практичних занять на тему “Метод простого випадкового пошуку рішень, наближених до оптимального”. Укладач В.В.Авраменко. – Суми: Вид-во СумДУ, 2009. - 12 с.

 

            Кафедра інформатики

 

Зміст

                                                                                                            С.

1 Загальні вказівки. 4

2 Варіанти    завдань. 7

3 Приклад виконання роботи. 8

4 Комп'ютерна програма. 9

5 Порядок    виконання    роботи. 11

6 Зміст  звіту. 11

7  Контрольні запитання. 12

Список літератури. 12

                У практичній діяльності часто з багатьох можливих рішень задачі необхідно вибрати оптимальне. Наприклад, з декількох варіантів перевезення сировини споживачам потрібно вибрати найбільш дешевий, але який враховує обмеження  на припустимі строки поставок; з можливих планів розкрою матеріалу вибрати такий, котрий дозволяє виконати план при найменшій кількості відходів  і т.д.

У багатьох випадках задача пошуку оптимального рішення може бути формалізована і вирішена чи точно, чи приблизно відомими методами. Одним з найбільш простих і універсальних методів одержання рішень, наближених до оптимального, є метод простого випадкового пошуку. Мета роботи - ознайомлення студентів з даним методом.

Передбачена можливість одержати уявлення про його точність. Для цього підібрані задачі, які легко можна розв'язати  методом множників Лагранжа. Поставлену задачу студент повинен вирішити точно вручну методом множників Лагранжа і приблизно на ПЕОМ методом простого випадкового пошуку. Результати варто порівняти.

 

1 ЗАГАЛЬНІ ВКАЗІВКИ

 

 Задачі пошуку оптимальних рішень  зводяться до відшукання екстремуму (мінімуму або максимуму) так званої  функції цілі  за умови, що на параметри, від яких вона залежить, накладені обмеження. Так, наприклад, можуть бути задані обмеження a_i ≤ x_i ≤A_i   ( ), що вказують припустимі межі зміни  x_i  . Тут –       a_i,, A_i - відповідно мінімальне і максимальне значення параметра x_i .

Можуть також накладатися обмеження на співвідношення деяких параметрів, наприклад,       і інші. Якщо функція цілі або хоча б одне з обмежень є нелінійними виразами стосовно невідомих змінних, то розглянута задача відноситься до класу задач нелінійного програмування.

Вектор Х = (x₁, x₂,... x_n) , координатами якого є конкретні значення невідомих змінних, називається рішенням або планом.

Рішень може бути нескінченно багато. Ті з них, які задовольняють всім обмеженням, наведеним у даній задачі, називаються д о п у с т и м и м и.    Серед допустимих рішень є оптимальне, при якому функція цілі досягає шуканого екстремуму (мінімуму або максимуму).

Приклад. Знайти екстремум - максимум функції цілі 

φ= x₁x₂ х₃                                                                                (1) 

 при обмеженнях :

2x₁x₂ + 2x₁x₃ +2 x₂ х₃ = 54,                                                               (2)

x₁ > 0 ,     x₂ >0,      х₃ > 0.                                                                   (3)

Узяте навмання рішення   Х=(1,10,5) не є допустимим, тому що при   x₁= 1, x₂ = 10,  х₃= 5   не задовольняється обмеження, задане рівнянням (2). Очевидно, що й інше рішення Х= (100,-10,100) також недопустиме. А от рішення Х=(3,  3,  3) є допустимим,  тому що задовольняє всім обмеженням. Легко переконатися, що воно і оптимальне.

Існує багато способів рішення задач нелінійного програмування. Випадковий пошук дозволяє знайти оптимальне рішення приблизно. Відомі різні методи випадкового пошуку: простий пошук, пошук із самонавчанням і ін. У даній роботі використаний простий випадковий пошук оптимального рішення.

Він полягає в такому.

1 Вводиться кількість випробувань N. Вводять також нижні  та верхні  обмеження для змінних (i=1,2,…n)  і інші вхідні дані.

2 Присвоюється  найкращому на даний момент  значенню функції цілі  найгірше значення.  Наприклад, треба знайти екстремум-максимум. Позначимо  найкраще на даний момент значення функції цілі через . Тоді треба присвоїти , тобто   . І навпаки, якщо ставиться за мету знайти екстремум-мінімум, можна вважати, що найгіршим початковим значенням буде .

3 Беруться випадкові значення невідомих змінних. Якщо задані межі для кожної із змінних, тобто a_i ≤ x_i ≤A_i ( ), то випадкові значення беруться в цих межах. Для цього викликають функцію для  ПЕОМ, що генерує випадкове число  ζ    на відрізку від  0  до 1  з рівномірним законом розподілу. Комп'ютер генерує так звані псевдовипадкові  числа. Щоразу, коли потрібно одержати значення псевдовипадкового числа ζ на інтервалі (0 , 1) з рівномірним законом розподілу, викликається стандартна підпрограма або функція. Конкретно для Турбо-Паскаля   

ζ: =random;    а   для Cі    ζ =random (32767)/32767.  ; (Зверніть увагу на крапку після 32767). Це число використовується  для обчислення випадкової змінної       :

.

    Знову викликають функцію для генерації випадкового числа і, одержавши вже інше значення   ζ  , обчислюють x₂= а₂+(А₂ – а₂ ) ζ. Так повторюють  n   раз. У результаті одержують вектор Х = (x₁, x₂,… x_n), що  задовольняє частину обмежень, накладених на невідомі змінні.

4  Перевіряють, чи задовольняють отримані  x₁, x_2,,...x_n  іншим обмеженням ( тобто чи є отримане випадкове рішення допустимим).  Якщо "ні",  то переходять до   п.3, якщо "так" - до п.5.

Примітка: якщо є обмеження у вигляді рівнянь, то їх можна використати для визначення значення однієї із змінних за умови, що інші вже задані. Це полегшує одержання допустимих рішень. Наприклад, якщо на  і  накладені обмеження  ,   0 ≤  x_i ≤  D  (i= 1,2), то значення  можна одержати за допомогою функції генерації випадкового числа відповідно до виразу   =D*ζ , а  x₂  обчислити по формулі    .

5.  Допустиме рішення Х = () підставляють   у вираз для функції цілі і одержують значення   φ ( X) .
6. Порівнюють φ ( X) із . Якщо воно краще, ніж, то присвоюється . Також запам'ятовуються відповідні значення параметрів   , при яких  досягнуто дане значення функції цілі. Тобто треба присвоїти , де .. Після цього  знову генерують нове випадкове рішення, тобто переходять до п.3.

Процес припиняється  після заданого числа N  випробувань. Вектор із знайдених значень     береться як рішення, наближене до оптимального, а . – відповідне значення функції цілі. Їх виводять на екран або у файл.

 

2 ВАРІАНТИ    ЗАВДАНЬ

 

1) Опір балки прямокутного поперечного перерізу   на стискання пропорційний площі цього перетину. Які повинні бути розміри перетину балки, вирізаної із круглої колоди із заданим діаметром D, щоб її опір на стискання був найбільшим? Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.

2. Потрібно виготовити відкритий циліндричний бак заданого об'єму V   . Вартість квадратного метра матеріалу, з якого виготовляється дно бака, дорівнює    Р₁  грн., а вартість квадратного метра матеріалу, що йде на стінки – Р₂  грн.  Знайти значення радіуса і висоти бака, при яких витрати грошей на матеріал будуть найменшими. Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.
3. Опір балки прямокутного поперечного перерізу на вигинання пропорційний добутку ширини цього перетину на квадрат його висоти. Які повинні бути розміри перетину балки, вирізаної із круглої колоди із заданим діаметром D  , щоб її опір на вигинання був максимальним? Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.
4. Намет із заданим об'ємом V  має форму прямого кругового конуса. Якими повинні бути значення висоти  Н  конуса і  радіуса R  основи, щоб бічна поверхня була мінімальною?

Об'єм   , бічна поверхня  .

Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку.    Зіставити результати.

5) Стріла прогину балки прямокутного поперечного перерізу обернено пропорційна добутку  цього перетину на куб  його висоти. Які повинні бути розміри перетину балки, вирізаної із круглої колоди із заданим діаметром D   , щоб стріла прогину була найменшою? Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.

6) Знайти значення радіуса і висоти циліндра із заданим об'ємом V, у якого найменша повна поверхня. Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.

7) Із всіх трикутників з однаковим периметром  2р  визначити той, у якого найбільша площа. Вираз для площі

,

де ,  ,  - довжини сторін трикутника. Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.

8. Знайти прямокутний паралелепіпед, що має найбільший об'єм при заданій повній поверхні S . Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.
9. Знайти прямокутний паралелепіпед, що має найменшу повну поверхню при заданому об'ємі V . Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.
10. Спроектувати відкритий резервуар у вигляді прямокутного паралелепіпеда, що при заданій сумарній площі дна і стінок має максимальний об'єм. Задачу вирішити методом множників Лагранжа і методом простого випадкового пошуку. Зіставити результати.

3 ПРИКЛАД ВИКОНАННЯ РОБОТИ

 

            Методом простого випадкового пошуку знайти прямокутний паралелепіпед, що має найменшу повну поверхню при заданому об'ємі V. Відповідь, отримана методом множників Лагранжа, свідчить, що це повинен бути куб.

Приводиться  комп’ютерна програма мовою Сі . У ній  використані ідентифікатори, наведені в таблиці 1.

 

Таблиція1

 

Позначення в виразі	Ідентифікатор	Пояснення
N	N	Кількість випробувань
v	v	Об'єм
	fie
	fi
	i=0,1,2
,	a[i] ,  A[i]
	znam	x[0]*x[1]

 

4 КОМП'ЮТЕРНА ПРОГРАМА

 

#include<stdio.h>

#include<math.h>

#include<conio.h>

#include<stdlib.h>

void main()

{

double x[3],xe[3],a[3],A[3];

double v,fi,fie=1e38;// fie присвоєно найгірше значення

double znam;

int i;

long int j,N;

clrscr();

puts("Enter v  ");

scanf("%lf",&v);

for(i=0;i<3;i++)

{

printf("\n Enter a[%i] A[%i] ",i,i);

scanf("%lf%lf",&a[i],&A[i]);//нижні та верхні граничні значення

}

puts("Enter N=");//кількість випробувань

scanf("%li",&N);

for(j=0;j<N;j++)

{

for(i=0;i<2;i++)

x[i]=a[i]+(A[i]-a[i])*random(32767)/32767.;//розіграли значення x[0] x[1]

znam=x[0]*x[1];

if(znamen)

{

x[2]=v/(x[0]*x[1]);//обчислили x[2] із умови заданого об’єма v

if(x[2]>=a[2] && x[2]<=A[2])//перевірка допустимості значення x[2]

{

fi=2*(x[0]*x[1]+x[0]*x[2]+x[1]*x[2]);//обчис-лення функції цілі

if(fi<fie)//порівняння із  fie

{

fie=fi;// занесення нового поточного «рекордного» значення функції цілі

for(i=0;i<3;i++)//та параметрів, при яких воно досягнуто

xe[i]=x[i];

}

}

}

}

printf("fie=%lf\n",fie);//виведення досягнутого за N випробувань значення fie

for(i=0;i<3;i++)// та відповідних параметрів (тобто рішення, близького до оптим.)

printf("xe[%i]=%lf\n",i,xe[i]);

}

 

5  ПОРЯДОК  ВИКОНАННЯ  РОБОТИ

1 Одержати у викладача варіант завдання.

2 Скласти математичну модель задачі.

3 Вирішити задачу методом невизначених множників Лагранжа.

4 Задатися самостійно вихідними даними і одержати для них оптимальне рішення, а також відповідне значення функції  цілі.

5. Доповнити математичну модель обмеженнями на межі зміни невідомих змінних.

6 Скласти блок-схему алгоритму рішення задачі методом простого випадкового пошуку.

7 Скласти і відлагодити комп’терну програму.

8 Одержати рішення задачі за допомогою приведеної вище програми для тих же вихідних даних, які  використовувалися в п.З. Кількість випробувань збільшувати до тих пір, доки не будуть досягнуті постійні результати.

9 Оцінити погрішності результатів, отриманих методом випадкового пошуку порівняно з тими, що були знайдені методом множників Лагранжа. Зробити висновки.

 

6 ЗМІСТ  ЗВІТУ

1 Постановка задачі.

2 Математична модель.

3 Рішення задачі методом множників Лагранжа.

4 Доповнення до математичної моделі.

5 Блок - схема алгоритму.

6 Комп’ютерна програма.

7 Результати, отримані обома способами.

8 Розрахунок погрішностей.

9 Висновки.

 

7  КОНТРОЛЬНІ ЗАПИТАННЯ

 

1 Привести визначення задачі математичного програмування.

2 Які задачі відносяться до класу задач нелінійного програмування?

3 Що собою являє  рішення або план?

4 Яке рішення називається  допустимим?

5 Яке рішення називається оптимальним?

6 У чому полягає сутність методу простого випадкового пошуку?

7 Які його переваги і недоліки?

8 У чому полягає сутність методу множників Лагранжа? Які його переваги і недоліки?

 

СПИСОК ЛІТЕРАТУРИ

1 Реклейтис Г. и др. Оптимизация в технике. Кн. 1. -М.: Мир, 1986. -с.196-202, 284-296.

2 Хог Э., Арора Я. Прикладное оптимальное проектирование. - М.:  Мир, 1983. - 478 с.

3 Акулич И. Л. Математическое программирование в примерах и задачах. -М.:  Высш. шк., 1986. - с. 257-262.