Національний університет водного господарства та природокористування

Національний університет водного господарства та природокористування

Кафедра прикладної математики

100 – 62

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

Для виконання контрольних та лабораторних робіт з дисципліни

“МАТЕМАТИЧНІ МЕТОДИ І МОДЕЛІ”

студентами спеціальностей “Землевпорядкування та кадастр” і “Геоінформаційні системи”

Рекомендовані до видання ме-тодичною комісією факультету землевпорядкування та геоінформатики Протокол № 10 від 29 червня 2004 року

 

 

Рівне - 2004

 

Методичні вказівки і завдання для виконання контрольних та лабораторних робіт з дисципліни “Математичні методи і моделі” для студентів всіх форм навчання спеціальностей “Землевпорядкування та кадастр” і “Геоінформаційні системи” / П.М.Грицюк - Рівне, НУВГП, 2004. - 26 с.

Укладач: П.М.Грицюк, доцент кафедри прикладної математики

Відповідальний за випуск: А.П.Власюк, доктор технічних наук, завідувач кафедри прикладної математики

 

 

З М І С Т

1. Вступ……………………………………………………..........…………… 3

2. Тема 9. Задача лінійного програмування............................................... 4

3. Тема 10. Задача лінійного програмування: двоїстий симплекс - метод.……........................................................................................………. 10

Тема 11. Задача лінійного програмування: задача про розріз труб 16

5. Тема 12. Транспортна задача………………………….......................... 19

 

Вступ

Дисципліна “Математичні методи і моделі” є однією з основних дисциплін, необхідних для формування навичок комп’ютерного моделювання у майбутніх інженерів-землевпорядників. Програма дисципліни формувалася з врахуванням важливості тих, чи інших математичних методів і моделей для геоінформатики. Цьому принципу відповідають і дані методичні вказівки. Основна увага в даних методичних вказівках приділена методам моделювання складних географічних систем, а також математичним методам дослідження отриманих моделей.

У методвказівках розглянуто чотири задачі, які утворюють другу частину циклу лабораторних робіт. Для кожного завдання здійснюється постановка задачі, наводиться коротка теоретична довідка або ж математична модель задачі, вказується метод розв’язування та основні розрахункові формули, наводиться рекомендований вигляд розрахункових таблиць. Всі задачі відносяться до розділу “Математичне програмування” і є характерними для математичного забезпечення ГІС. Розв’язування цих задач покликано поглибити розуміння деяких сторін математичного забезпечення геоінформатики. В якості ілюстрацій наводяться плани та схеми, які унаочнюють розв’язування задач. Для кожної з задач наводиться таблиця вихідних даних. Завдяки цьому методвказівки можуть використовуватися для виконання лабораторних, контрольних і самостійних робіт.

За результатами вивчення курсу “Математичні методи і моделі” студент – заочник повинен виконати контрольну роботу. Розглянуті нижче задачі можуть бути використані в якості завдань для неї. Дані для кожного завдання визначаються номером варіанта. Номер варіанта визначається двома останніми цифрами залікової книжки NN за формулами:

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

 

Тема 9

Задача лінійного програмування

9.1. Завдання. Побудувати математичну модель задачі лінійного програмування. Розв’язати задачу графічним методом. Звести задачу до канонічної форми. Розв’язати задачу табличним симплекс-методом. Дати економічну інтерпретацію розв’язку задачі.

9.2. Постановка задачі про оптимальний розподіл земельних ресурсів:

Сільськогосподарське підприємство вирощує дві культури P₁ і P₂, використовуючи три типи ресурсів (робоча сила, фінансові ресурси, рухомий склад), запаси яких дорівнюють b₁, b₂ i b₃ відповідно. Прибуток з 1 гектара культури становить відповідно c₁ і c₂. Затрати ресурсів (на 1 гектар) на виробництво культур відомі і дорівнюють a₁₁, a₁₂, a₂₁, a₂₂, a₃₁, a₃₂. Необхідно знайти такий план розподілу площ під культури, який забезпечує максимальний прибуток від її реалізації.

 

Приклад

Таблиця 1. Технологічна матриця (затрати ресурсів на 1 га площі)

Ресурси	Культура 1	Культура 2	Запаси ресурсів
Роб. сила
Фін. ресурси
Рух. склад
Прибуток (тис. грн. з 1 га)

Геометричний спосіб розв’язування

Побудуємо симплекс. Для побудови прямої лінії необхідно мати дві опорних точки. Будемо шукати ці точки на осях. При цьому отримаємо такі результати:

А лінія 2-а лінія 3-я лінія

Знайдемо координати вершин симплекса. Координати вершин O, A, D вже відомі і становлять: O(0;0), A(0;4), D(6;0). Для знаходження координат вершини B необхідно розв’язати систему двох лінійних рівнянь, які відповідають першій і третій лінії:

В результаті отримаємо B(3.46; 2.62).

Для знаходження координат вершини С необхідно розв’язати систему двох лінійних рівнянь, які відповідають другій і третій лінії:

В результаті отримаємо С(5.40; 1.00).

Обчислимо значення цільової функції у вершинах симплекса, використовуючи формулу .

Отримаємо F(O)=0.00; F(A)=4; F(B)=9.54; F(C)=11.8; F(D)=12.00.

Отже оптимальний розв’язок відповідає вершині D симплекса і має вигляд:

Табличний симплекс-метод

Канонічна форма задачі

Введемо нові невід’ємні змінні . Отримаємо систему недоозначених рівнянь (3 рівняння, 5 невідомих).

(7)

(8)

(9)

Складаємо симплекс – таблицю 1

симплекс-таблиця 1

Базис	Ci	P0	P1	P2	P3	P4	P5
P3
P4
P5
D j			-2	-1

Тут - оцінка невідомого

(10)

Таблиця 2. В а р і а н т и з а в д а н ь д о т е м и 9

варіант	a11	a12	b1	a21	a22	b2	a31	a32	b3	c1	c2

 

 

Тема 10

Задача лінійного програмування: двоїстий симплекс-метод

10.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.

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

Для відгодівлі тварин фермер використовує чотири види корму P₁, P₂, P₃, P₄, кожен з яких містить поживні речовини B₁, B₂, B₃. Добова потреба тварини у поживних речовинах дорівнює b₁, b₂ i b₃ відповідно. Ціна корму становить відповідно c₁, c₂, c₃, c₄. Вміст поживних речовин у одиниці маси кожного корму відомий і становить a₁₁, a₁₂, a₁₃, a₁₄, a₂₁, a₂₂, a₂₃, a₂₄, a₃₁, a₃₂, a₃₃, a₃₄ (тут перший індекс позначає номер поживної речовини, а другий – номер корму). Необхідно побудувати харчовий раціон (вказати щоденну кількість кожного корму), вартість якого мінімальна.

 

Таблиця 3. Технологічна матриця

	P1	P2	P3	P4	Норма
B1
B2		-	-
B3
Ціна

Канонічна форма задачі

Домножуємо нерівності (15) і цільову функцію (17) на (-1)

Введемо нові невід’ємні змінні , і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 7 невідомих).

Таблиця 4. В а р і а н т и з а в д а н ь д о т е м и 1 0

a11

a12

a13

a14

b1

a21

a22

a23

a24

b2

a31

a32

a33

a34

b3

c1

c2

c3

c4

N

a11

a12

a13

a14

b1

a21

a22

a23

a24

b2

a31

a32

a33

a34

b3

c1

c2

c3

c4

 

 

Тема 11

Задача лінійного програмування: задача про розріз труб

11.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум відходів). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.

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

В обробку поступила партія труб довжиною L = 7.5 м кожна. Необхідно розрізати труби, отримавши N1= 50 заготовок довжиною L1 = 3.5 м, N2= 30 заготовок довжиною L2 = 2.5 м і N3= 40 заготовок довжиною L3 = 2.0 м. Побудувати оптимальний план розрізу при якому сумарна довжина відходів буде мінімальною.

Таблиця 5. Таблиця варіантів розрізу

N	Lі	В а р і а н т и
	3.5		-	-			-	-
	2.5	-		-		-
	2.0	-	-		-
Відходи	0.5		1.5	1.5		0.5	1.0

Математична модель задачі

Позначимо x _і – кількість труб, розрізаних згідно і – го варіанту. Тоді отримаємо математичну модель задачі у наступному вигляді:

(19)

(20)

. (21)

Канонічна форма задачі

Домножимо нерівності (19) і цільову функцію (21) на (-1). Введемо нові невід’ємні змінні і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 10 невідомих).

Задача розв’язується двоїстим симплекс – методом.

Таблиця 6. В а р і а н т и з а в д а н ь д о т е м и 1 1

Варіант	L	L1	L2	L3	N1	N2	N3
1	120	50	40	55	35	45	40
2	110	35	50	45	30	50	20
3	110	40	30	55	45	20	25
4	110	50	45	30	25	30	35
5	120	50	45	65	30	40	25
6	125	40	60	55	45	30	20
7	125	50	60	35	30	45	50
8	95	40	30	50	20	25	30
9	125	45	65	50	40	30	50
10	105	30	35	50	40	30	50
11	100	30	40	55	50	20	35
12	120	35	45	50	30	50	40
13	100	40	35	45	25	45	35
14	100	40	55	35	25	40	30
15	105	40	50	35	30	40	20
16	115	45	35	55	50	30	45
17	130	65	45	50	40	30	50
18	105	40	55	30	60	50	40
19	105	55	40	30	20	35	40
20	115	45	50	60	30	10	40
21	115	50	40	45	20	45	30
22	115	45	55	65	50	30	40
23	125	45	50	35	40	30	50
24	115	45	55	40	25	30	40
25	110	45	60	35	30	40	50
26	115	50	40	55	25	35	40
27	115	65	30	45	10	30	40
28	125	55	60	40	40	30	45
29	120	50	35	60	45	35	40
30	115	40	50	30	30	20	50
31	125	50	35	45	45	30	25
32	115	40	45	30	35	30	25
33	135	50	45	65	40	30	25
34	130	35	50	55	45	20	30
35	125	40	60	35	40	45	20
36	95	40	30	35	40	25	30
37	135	45	65	50	30	30	40
38	110	35	30	50	50	30	20
39	105	30	40	50	30	20	45
40	130	35	45	50	40	50	30
41	95	40	35	25	45	25	35
42	110	50	40	35	35	20	30
43	125	40	50	65	20	40	30
44	115	40	35	55	25	30	45
45	125	45	65	40	50	30	20
46	105	35	55	40	30	50	40
47	115	55	45	30	40	35	30
48	125	45	50	60	35	10	40
49	120	45	55	65	20	30	40
50	130	35	50	45	50	30	40

Тема12

Транспортна задача

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

Три бригади за тиждень виробляють корми в кількостях a₁, a₂ i a₃ відповідно. Їх необхідно розвезти на 5 ферм, згідно з поданими заявками, у кількостях b₁, b₂, b₃, b₄, b₅. Вартість перевезення вважається пропорційною до кількості завантаженого корму x_ij і відстані від постачальника (бригади) до споживача (ферми) c_ij. Необхідно скласти такий план перевезень кормів, загальна вартість якого буде мінімальною. Необхідні для розрахунку параметри представлені у наступній Таблиці 7.

Таблиця 7. Технологічні параметри транспортної задачі.

Ферми® Бригади¯	B1	B2	B3	B4	B5	Запаси
A1		4		3		2		2		4
A2		1		4		8		4		1
A3		9		7		3		7		2
Потреби	60	70	120	130	100	480

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

 

12.2. Математична модель транспортної задачі

Позначимо x_ij – кількість одиниць корму, який планується перевезти від i – го постачальника (сівозміни) до j – го споживача (ферми). Оскільки всі вантажі повинні бути вивезені, то мають місце такі рівності:

(22)

Оскільки всі потреби споживачів повинні бути задоволені, то мають місце такі рівності:

(23)

Оскільки вантажі перевозяться лише в одну сторону, очевидно, що:

(24)

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

(25)

Якщо виконується умова , задача називається закритою.

 

12.3. Алгоритм розв’язування ТЗ

Потрібно:

1. скласти початковий опорний план задачі методом північно-західного кута;

2. скласти початковий опорний план задачі методом мінімального тарифа;

3. вибравши кращий з побудованих початкових планів, виконати його оптимізацію методом потенціалів за такою схемою:

3.1. скласти систему рівнянь (по базисних клітинах) для визначення потенціалів рядків U_i та стовпців V_j та, прийнявши U₁=0, розв’язати отриману систему;

3.1.1. визначити характеристики вільних клітин за формулою

; (26)

3.2. якщо всі характеристики є невід’ємні, завершити розв’язування задачі. Виписати оптимальний план перевезень у вигляді матриці, а також мінімальне значення вартості перевезень F_min;

3.3. якщо не всі характеристики є невід’ємні, необхідно вибрати найбільшу додатну характеристику і побудувати для відповідної вільної клітини таблиці цикл. Позначити вершини циклу умовними знаками “+” (збільшити вантажо-потік) i “-” (зменшити вантажопотік). Початкова вільна вершина позначається знаком “+”, а всі інші – по черзі “-” i “+”; серед всіх вершин, позначених знаком “-”, вибрати найменше перевезення – m. Для всіх вершин, позначених знаком “+”збільшити перевезення на m, для вершин, позначених знаком “-” зменшити перевезення на m. Перейти до пункту 3.1

 

12.4. Побудова початкового опорного плану ТЗ

Таблиця 8. Метод північно – західного кута