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

№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. Будемо нехтувати  опором повітря  і  залежністю