Основні етапи комп’ютерного моделювання

№1

 Катер за 4 год. пройшов 24 км. за течією річки і 20 км. проти течії. Знайти швидкість течії, якщо власна швидкість катера дорівнює 12 км/год. 
Розв’язання. Нехай х – швидкість течії. Тоді за течією катер йшов   год., проти течії   год., а всього 4 год. Отже,   
 
х2=144                132-х=144-х2 
х=+/- 12                х2-х-12=0 
D=1+48=49          
 
не задовольняє 
умові 
Відповідь: 4 км/год.

Завдання 2

Записати двоїсту задачу до поставленої задачі лінійного  програмування. Розв’язати одну із задач  симплексним методом і визначити  оптимальний план іншої задачі. Оптимальні результати перевірити графічно.

 

 

 

 

Розв’язок

Розв’яжемо задачу лінійного  програмування симплексним методом.

Визначимо мінімальне значення цільової функції F(X) = 4x1+2x2 при наступних  умовах-обмежень.

x1-x2≤4

x1+3x2≤6

x1+2x2≥2

Для побудови першого опорного плану систему нерівностей приведемо  до системи рівнянь шляхом введення додаткових змінних.

Оскільки маємо змішані  умови-обмеження, то введемо штучні змінні x.

1x1-1x2 + 1x3 + 0x4 + 0x5 = 4

1x1 + 3x2 + 0x3 + 1x4 + 0x5 = 6

1x1 + 2x2 + 0x3 + 0x4-1x5 = 2

Для постановки задачі на мінімум  цільову функцію запишемо так:

F(X) = 4x1+2x2 - Mx6 => max

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний  план:

 

План	Базис	В	x1	x2	x3	x4	x5	х6
0	х3	4	1	-1	1	0	0	0
	x4	6	1	3	0	1	0	0
	х6	2	1	2	0	0	-1	1
Індексний рядок	F(X0)	0	0	0	0	0	0	0

Переходимо до основного  алгоритму симплекс-методу.

 

План	Базис	В	x1	x2	x3	x4	x5	x6	min
1	x3	4	1	-1	1	0	0	0	0
	x4	6	1	3	0	1	0	0	2
	x6	2	1	2	0	0	-1	1	1
Індексний рядок	F(X1)	0	0	0	0	0	0	0	0

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

 

План	Базис	В	x1	x2	x3	x4	x5	x6	min
2	x3	5	1.5	0	1	0	-0.5	0.5	3.33
	х4	3	-0.5	0	0	1	1.5	-1.5	0
	x2	1	0.5	1	0	0	-0.5	0.5	2
Індексний рядок	F(X2)	0	0	0	0	0	0	0	0

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

 

План	Базис	В	x1	x2	x3	x4	x5	x6	min
3	x3	2	0	-3	1	0	1	-1	2
	X4	4	0	1	0	1	1	-1	4
	X1	2	1	2	0	0	-1	1	0
Індексний рядок	F(X3)	0	0	0	0	0	0	0	0

 

План	Базис	В		x1		x2	x3	x4		x5		x6		min
4	х5	2		0		-3	1	0		1		-1		0
	X4	2		0		4	-1	1		0		0		0.5
	X1	4		1		-1	1	0		0		0		0
Індексний рядок	F(X4)	0		0		0	0	0		0		0		0
План	Базис		В		x1		x2		x3		x4		x5	х6
5	х5		3.5		0		0		0.25		0.75		1	-1
	х2		0.5		0		1		-0.25		0.25		0	0
	х1		4.5		1		0		0.75		0.25		0	0
Індексний рядок	F(X5)		0		0		0		0		0		0	0

Оптимальний план можна записати так:

x5 = 3.5

x2 = 0.5

x1 = 4.5

F(X) = 4*4.5 + 2*0.5 = 19

Складемо двоїсту задачу до поставленої задачі лінійного  програмування.

y1+y2+y3≥4

-y1+3y2+2y3≥2

4y1+6y2+2y3 => min

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстої задачі дає  оптимальну оцінок ресурсів. Використовуючи останню інтиграцію прямої задачі знайдемо,оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.

Сформуємо матрицю A із компонентів  векторів, які входять в оптимальний  базис.

 

Визначивши обернену матрицю  А-1 через алгебраїчне доповнення, отримаємо:

 

Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.

Тоді Y = C*A-1 =

Запишемо оптимальний  план двоїстої задачі:

        y1 = 2.5

y2 = 1.5

y3 = 0

Z(Y) = 4*2.5+6*1.5+2*0 = 19

                                                                                                                                                                     

Приклад  3 пункту А в пункт В виїхав велосипедист і ручався зі швидкісно 20 км/год. а через півгодини услід за ним виїхав мотоцикліст і рухався зі швидкістю 36 км/год. Через скільки часу після виїзду велосипедиста його наздожене мотоцикліст?

 

Можна побудувати ріїні математичні моделі ііігі іадачі Побудушо математичну модель та допомогою графіків функцій * За 11 од велосипедист проїде 20г км. а мотоциклет. рухаючись на 0.51 од менше, іа (1-0.5) год проїде V*/ - 0.51 км На рисунку 66 юбражено ірафіки функшй і=20/ й * = 36< г — 0.5 >. ікі виражлоіь іалежність шляхів, пройдених велосипедистом і мотоциклістом, від часу руху велосипедиста. Щоб відповісти на іапиіання іадачі. потрібно шийіи абсцису точки персти-ну ірафіків ф\ пісній. 'З рисунка »находимо. що г* 1.1 гол. Отже. мотоцикліст наздожене велосипедиста приблизно через 1.1 гол після виїзду вс.іосинслиста.

 

 

Основні етапи комп’ютерного моделювання.

Етап 1. Постановка задачі та її аналіз.

Етап 2. Побудова інформаційної моделі.

Етап 3. Розробка методу й алгоритму дослідження моделі.

Етап 4. Розробка комп’ютерної моделі.

Етап 5. Проведення комп’ютерного експерименту.\

 

Розглянемо сутність цих етапів на прикладі задачі Робіна Гуда.

 

 

Рис. 53.1. Задача Робіна Гуда.

 

Робіну  Гуду  потрібно  передати

записку  другу,  якого  заточили  у

в’язницю  замку Ноттінгем.  Замок

оточений  високою  стіною.  Записку

можна тільки закинути разом із каменем

у  вікно  в’язниці,  але  кидати  камінь

потрібно  так,  щоб  він  пролетів  крізь

бійницю в стіні (рис. 53.1).

   6

====53.5. Постановка задачі та її аналіз=========================================

Метою  етапу  є  конкретизація  й  уточнення  задачі моделювання. Для цього  виконуються

такі дії:

·    з’ясовується, з якою метою створюється модель;

·    уточнюється, які саме результати і в якому вигляді потрібно одержати;

·    визначається, які дані потрібні для створення моделі;

·    установлюється, чи є обмеження на вхідні дані, тобто за яких умов можна одержати

потрібні результати, а за яких — ні.

Для  нашої  задачі  метою складання  моделі  є  визначення,  чи  можна  закинути  камінь  до

в’язниці,  а якщо  так,  то  як  має  діяти  Робін  Гуд.  Результатом моделювання  повинна  бути

відповідь  на  поставлене  запитання  і,  якщо  вона  позитивна, — рекомендації  для Робіна  Гуда.

Для  побудови моделі  потрібні  дані  про геометрію  споруд (відстань  стіни  від  замку,  товщина

стіни, висота й розміри бійниці, висота й розміри вікна в’язниці)  і про Робіна Гуда — який він

на  зріст,  з  якою  найбільшою  силою може  кинути  камінь. Що  саме  ми  будемо  моделювати?

Траєкторію каменя на тлі споруд.

====53.6. Побудова інформаційної моделі=======================================

Метою  етапу  є  встановлення  та  опис  взаємозалежностей  між  параметрами моделі.На

цьому етапі:

·    визначаються параметри моделі й виявляються взаємозв’язки між ними;

·    оцінюється,  які  з  параметрів  є  впливовими  і  мають  бути  враховані  при побудові

моделі, а якими можна нехтувати. Такий аналіз здійснюється з огляду на поставлену

задачу  і має на меті максимальне спрощення моделі. Разом з тим, це спрощення не

може бути надмірним, щоб модель не втратила адекватності;

·    уводиться  система  умовних  позначень,  і  в цих  позначеннях  здійснюється  опис

залежностей  між  параметрами моделі.  У  результаті  отримується  знакова

інформаційна модель.

Побудуємо  інформаційну  модель  для нашої  задачі.  Геометричні  параметри  споруд

позначимо,  як  показано  на  рис.  53.1.  Вважатимемо,  що  рух  каменя  відбувається  в одній

площині. Позначимо  її XOY з початком координат в основі зовнішньої сторони стіни. Силу, з

якою Робін Гуд кидає камінь, подамо через початкову швидкість каменя v0. Кут до горизонту,

під  яким  робиться  кидок, позначимо  через a. Будемо нехтувати  опором повітря  і  залежністю

прискорення  вільного  падіння  g  від  висоти. Камінь  вважатимемо матеріальною  точкою,  його

траєкторію будемо визначати як залежність координат x, y від часу t.

Робін Гуд кидає  камінь  з  висоти  свого  зросту  r,  знаходячись на відстані  l1  від  стіни. На

траєкторію каменя впливають початкова швидкість каменя v0 і кут a. Як відомо із фізики, 

x = - l1 + V0 t cos α;  y = r + V0 t sin α – gt

2

/2

Це і є математична модель нашої задачі. 

====53.7. Розробка методу й алгоритму дослідження моделі=========================

Метою етапу є складання алгоритму дій для одержання потрібних результатів. З поняттям

алгоритму ми далі познайомимося детальніше.

На цьому етапі:

·    з огляду на інформаційну модель добирається або розробляється метод одержання

потрібних результатів;

·    за вибраним методом складається детальний план розв’язання задачі, розробляється

алгоритм одержання результатів.

Модель  нашої  задачі  є  простою,  координати  каменя  обчислюються  за  формулами.

Траєкторію каменя будемо будувати на тій самій площині, де відображено і споруди. Висновки

про результат кидання каменя визначатимемо візуально.   7

====53.8. Розробка комп’ютерної моделі========================================

Метою  етапу  є  одержання  комп’ютерної моделі,  придатної  для дослідження. Для цього

здійснюються:

·    вибір засобів реалізації моделі на комп’ютері. Серед багатства існуючих засобів

добираємо найбільш зручні з огляду на поставлену задачу та її інформаційну модель;

·    створення комп’ютерної моделі;

·    перевірка правильності створеної комп’ютерної моделі.

 

Ця  перевірка  здійснюється  для знаходження  і  вилучення  помилок, що  були  допущені  у

процесі  розробки моделі.  Іноді може  з’ясуватися, що помилку  було припущено не на  даному

етапі,  а раніше.  Наприклад,  невдало  вибрано  метод,  припущено надмірні  спрощення  при

моделюванні  тощо. У  такому  разі  треба повернутися  до  відповідного  етапу,  внести  потрібні

корективи й повторити наступні етапи побудови моделі.

Для  нашої  задачі  комп’ютерну  модель  найбільш  зручно  побудувати  в середовищі

електронних  таблиць Excel або  засобами мови програмування, наприклад Паскаль,  з якою ми

познайомимося пізніше.

====53.9. Проведення комп’ютерного експерименту===============================

Метою  етапу  є  дослідження  моделі  та  з’ясування  на  цій  основі  властивостей  об’єкта

моделювання.

Етап складається з таких дій:

·    розробка плану дослідження;

·    проведення комп’ютерного експерименту на базі створеної моделі;

·    аналіз отриманих результатів.

Результати проведеного експерименту  характеризують властивості комп’ютерної моделі.

Проте  її  адекватність  об’єкту  дослідження  дає  підставу  для того, щоб  важати  ці  властивості

притаманними самому об’єкту. 

У ході експерименту може виникнути потреба скоригувати план дослідження, наприклад,

поглибити його в деякому напрямку. Іноді отримані результати можуть виявитися сумнівними,

що вимагатиме вибору  іншого методу дослідження, або уточнення моделі, або навіть внесення

змін у постановку задачі, і тоді весь процес починається знову.