МАТЕМАТИЧНІ МЕТОДИ І МОДЕЛІ 24.07.2015 10:25
Міністерство освіти і науки України
Національний університет водного господарства та природокористування
Кафедра прикладної математики
100 – 62
МЕТОДИЧНІ ВКАЗІВКИ І ЗАВДАННЯ
для виконання контрольних та лабораторних робіт з дисципліни
“МАТЕМАТИЧНІ МЕТОДИ І МОДЕЛІ”
студентами спеціальностей “Землевпорядкування та кадастр” і “Геоінформаційні системи”
Рекомендовані до видання ме-тодичною комісією факультету землевпорядкування та геоінформатики
Протокол № 10
від 29 червня 2004 року
Рівне - 2004
Методичні вказівки і завдання для виконання контрольних та лабораторних робіт з дисципліни “Математичні методи і моделі” для студентів всіх форм навчання спеціальностей “Землевпорядкування та кадастр” і “Геоінформаційні системи” / П.М.Грицюк - Рівне, НУВГП, 2004. - 26 с.
Укладач: П.М.Грицюк, доцент кафедри прикладної математики
Відповідальний за випуск: А.П.Власюк, доктор технічних наук, завідувач кафедри прикладної математики
З М І С Т
1. Вступ……………………………………………………..........…………… 3
2. Тема 9. Задача лінійного програмування............................................... 4
3. Тема 10. Задача лінійного програмування: двоїстий симплекс - метод.……........................................................................................………. 10
4. Тема 11. Задача лінійного програмування: задача про розріз труб 16
5. Тема 12. Транспортна задача………………………… .......................... 19
Вступ
Дисципліна “Математичні методи і моделі” є однією з основних дисциплін, необхідних для формування навичок комп’ютерного моделювання у майбутніх інженерів-землевпорядників. Програма дисципліни формувалася з врахуванням важливості тих, чи інших математичних методів і моделей для геоінформатики. Цьому принципу відповідають і дані методичні вказівки. Основна увага в даних методичних вказівках приділена методам моделювання складних географічних систем, а також математичним методам дослідження отриманих моделей.
У методвказівках розглянуто чотири задачі, які утворюють другу частину циклу лабораторних робіт. Для кожного завдання здійснюється постановка задачі, наводиться коротка теоретична довідка або ж математична модель задачі, вказується метод розв’язування та основні розрахункові формули, наводиться рекомендований вигляд розрахункових таблиць. Всі задачі відносяться до розділу “Математичне програмування” і є характерними для математичного забезпечення ГІС. Розв’язування цих задач покликано поглибити розуміння деяких сторін математичного забезпечення геоінформатики. В якості ілюстрацій наводяться плани та схеми, які унаочнюють розв’язування задач. Для кожної з задач наводиться таблиця вихідних даних. Завдяки цьому методвказівки можуть використовуватися для виконання лабораторних, контрольних і самостійних робіт.
За результатами вивчення курсу “Математичні методи і моделі” студент – заочник повинен виконати контрольну роботу. Розглянуті нижче задачі можуть бути використані в якості завдань для неї. Дані для кожного завдання визначаються номером варіанта. Номер варіанта визначається двома останніми цифрами залікової книжки NN за формулами:
У контрольній роботі потрібно навести: умову кожної задачі (загальна умова + дані для свого варіанту), детальний розв’язок у табличній формі з необхідними поясненнями і графічними ілюстраціями. Студент допускається до іспиту лише при наявності позитивної рецензії на контрольну роботу і відмітки про допуск до співбесіди.
Тема 9
Задача лінійного програмування
9.1. Завдання. Побудувати математичну модель задачі лінійного програмування. Розв’язати задачу графічним методом. Звести задачу до канонічної форми. Розв’язати задачу табличним симплекс-методом. Дати економічну інтерпретацію розв’язку задачі.
9.2. Постановка задачі про оптимальний розподіл земельних ресурсів:
Сільськогосподарське підприємство вирощує дві культури P1 і P2, використовуючи три типи ресурсів (робоча сила, фінансові ресурси, рухомий склад), запаси яких дорівнюють b1, b2 i b3 відповідно. Прибуток з 1 гектара культури становить відповідно c1 і c2. Затрати ресурсів (на 1 гектар) на виробництво культур відомі і дорівнюють a11, a12, a21, a22, a31, a32. Необхідно знайти такий план розподілу площ під культури, який забезпечує максимальний прибуток від її реалізації.
9.3. Математична модель задачі у загальному вигляді
( 1 )
( 2 )
( 3 )
Тут x1 i x2 – площа, відведена під першу і другу культуру відповідно; c1 i c2 – прибуток з 1 гектара культури відповідно першого і другого типу; aij – затрати ресурсів і -го типу на 1 гектар культури j - го типу; bi – кількість виділених ресурсів для і - ої культури.
9.4. Приклад
Таблиця 1. Технологічна матриця ( затрати ресурсів на 1 га площі)
Ресурси Культура 1 Культура 2 Запаси ресурсів
Роб. сила 2 5 20
Фін. ресурси 5 3 30
Рух. склад 5 6 33
Прибуток ( тис. грн. з 1 га ) 2 1
9.5. Математична модель задачі 9.4
Позначимо x1 – площа під культурою 1, x2 – площа під культурою 2. Тоді отримаємо:
( 4 )
( 5 )
( 6 )
9.6. Геометричний спосіб розв’язування
Побудуємо симплекс. Для побудови прямої лінії необхідно мати дві опорних точки. Будемо шукати ці точки на осях. При цьому отримаємо такі результати:
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 симплекса і має вигляд:
9.7. Табличний симплекс-метод
9.7.1. Канонічна форма задачі
Введемо нові невід’ємні змінні . Отримаємо систему недоозначених рівнянь ( 3 рівняння, 5 невідомих ).
( 7 )
( 8 )
( 9 )
Складаємо симплекс – таблицю 1
симплекс-таблиця 1
Базис Ci P0 P1 P2 P3 P4 P5
2 1 0 0 0
P3 0 20 2 5 1 0 0
P4 0 30 5 3 0 1 0
P5 0 33 5 6 0 0 1
j 0 -2 -1 0 0 0
Тут - оцінка невідомого
( 10 )
9.7.2. Вибір розв’язуючого елемента
1. Розв’язуючий елемент повинен бути додатнім!
2. Розв’язуючий стовпець P1 знаходимо з умови min . min (-2;-1)=-2.
3. Розв’язуючий рядок – P4 знаходимо з умови min (P0/aij), тут i – номер розв’язуючого рядка. min ( 20/2; 30/5; 33/5) = 30/5.
4. Вектор P4 виходить з базису, Вектор P1 входить у базис.
5. Розв’язуючий елемент – число 5 – знаходиться на перетині розв’язуючого рядка P4 і розв’язуючого стовпця P1.
9.7.3. Алгоритм звичайного симплекс-методу
1. Розв’язуючий рядок P4 ділимо на розв’язуючий елемент – число 5;
2. Базисні стовпці P1, P3 i P5 повинні бути одиничними векторами;
3. Усі інші елементи таблиці (стовпці P0, P2, P4 крім рядка P4) перераховуються згідно правила прямокутника:
. ( 11 )
Тут розв’язуючий елемент; елемент, який перераховується.
симплекс-таблиця 2
Базис Ci P0 P1 P2 P3 P4 P5
2 1 0 0 0
P3 0 8 0 3.8 1 -0.4 0
P1 2 6 1 0.6 0 0.2 0
P5 0 3 0 3 0 -1 1
12 0 0.2 0 0.4 0
4. Оскільки всі 0, отримано оптимальний розв’язок задачі. Оптимальні значення параметрів x3, x1 i x5 знаходимо у стовпчику P0. Невідомі x2 i x4 яких немає у базисі є вільними і дорівнюють нулю. Якби серед оцінок були б від’ємні, довелось би будувати ще одну симплекс таблицю
Відповідь. Оптимальний розподіл земельних ресурсів має вигляд: x1 (площа під першу культуру) = 6 га; x2 (площа під другу культуру) = 0 га; x3 = 8; x4 = 0; x5 = 3; Fmax (прибуток) = 12 тис. грн.
Таблиця 2. В а р і а н т и з а в д а н ь д о т е м и 9
варіант a11 a12 b1 a21 a22 b2 a31 a32 b3 c1 c2
1 7 9 630 5 9 560 5 2 340 3 5
2 5 7 840 8 4 960 3 7 750 3 2
3 4 8 520 4 5 420 11 3 660 3 4
4 5 11 330 9 2 250 10 8 440 5 3
5 2 9 210 6 6 270 7 4 280 9 7
6 1 8 140 3 4 140 7 2 140 5 6
7 3 6 150 5 4 140 9 3 210 2 3
8 3 8 200 10 4 260 5 6 180 7 6
9 8 9 240 5 12 280 16 4 280 3 2
10 18 20 210 25 10 275 12 30 200 6 5
11 7 5 315 7 2 300 3 15 375 5 5
12 4 1 150 3 5 150 2 7 160 5 9
13 4 11 330 18 4 600 6 7 280 9 5
14 7 10 350 6 4 280 6 14 420 2 3
15 6 2 180 9 6 350 3 6 270 5 4
16 4 15 150 4 8 100 9 6 180 15 8
17 3 5 150 7 4 240 2 6 150 9 14
18 9 7 210 7 3 140 3 8 160 3 2
19 3 9 180 4 5 120 10 3 160 5 8
20 4 8 250 10 3 240 6 5 190 7 8
21 6 6 240 6 12 360 14 6 490 6 5
22 12 5 360 5 9 330 6 7 280 7 3
23 8 2 180 4 4 130 3 6 160 2 3
24 4 12 320 12 6 300 6 8 240 3 3
25 3 4 140 7 2 245 2 6 160 2 1
26 4 9 330 6 7 280 10 5 300 7 4
27 5 20 410 10 4 240 7 10 240 2 5
28 10 2 160 2 6 170 4 4 130 7 8
29 5 6 210 10 4 300 3 8 240 6 10
30 5 12 330 9 10 300 20 4 320 5 3
31 5 12 400 15 6 450 10 9 360 3 4
32 9 3 240 4 8 240 6 5 180 7 4
33 4 14 420 8 8 360 15 4 450 3 4
34 4 5 170 3 10 260 14 4 420 6 7
35 8 7 310 12 5 360 7 10 420 1 2
36 3 8 280 3 4 150 7 2 180 5 4
37 6 7 210 4 12 330 10 2 160 3 4
38 10 9 300 10 3 180 6 15 450 3 2
39 4 10 240 5 6 160 10 4 200 2 1
40 5 9 315 15 4 300 8 6 240 2 3
41 6 6 210 6 12 360 15 5 450 4 7
42 4 5 130 8 2 160 3 10 210 5 8
43 4 10 400 6 6 280 10 3 330 5 4
44 6 11 330 20 7 490 10 8 300 7 5
45 6 2 170 2 6 180 5 4 160 5 3
46 9 16 520 6 7 250 16 5 400 5 7
47 4 5 160 3 8 180 10 3 330 5 9
48 10 3 270 3 6 210 6 5 220 4 7
49 6 5 210 6 11 330 10 4 300 5 9
50 4 5 130 8 2 160 3 10 210 8 5
Тема 10
Задача лінійного програмування: двоїстий симплекс-метод
10.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.
10.2. Постановка задачі:
Для відгодівлі тварин фермер використовує чотири види корму P1, P2, P3, P4, кожен з яких містить поживні речовини B1, B2, B3. Добова потреба тварини у поживних речовинах дорівнює b1, b2 i b3 відповідно. Ціна корму становить відповідно c1, c2, c3, c4. Вміст поживних речовин у одиниці маси кожного корму відомий і становить a11, a12, a13, a14, a21, a22, a23, a24, a31, a32, a33, a34 ( тут перший індекс позначає номер поживної речовини, а другий – номер корму). Необхідно побудувати харчовий раціон (вказати щоденну кількість кожного корму), вартість якого мінімальна.
10.3. Математична модель задачі (для загального випадку)
( 12 )
( 13 )
( 14 )
Тут xj – кількість корму j - го типу; cj – ціна корму j - го типу; aij – вміст поживної речовини i – го типу у одиниці маси корму j-ого типу; bi – добова потреба у i –ій поживній речовині.
10.4. Приклад. Технологічна матриця задачі про оптимальний харчовий раціон
Таблиця 3. Технологічна матриця
P1 P2 P3 P4 Норма
B1 150 15 5 80 100
B2 150 - - 10 100
B3 25 80 120 500 300
Ціна 200 50 70 100
10.5. Математична модель задачі 10.4
Позначимо – кількість корму P1, – кількість корму P2, – кількість корму P3, – кількість корму P4. Тоді отримаємо математичну модель задачі:
( 15 )
( 16 )
( 17 )
10.6. Канонічна форма задачі
Домножуємо нерівності (15) і цільову функцію (17) на (-1)
Введемо нові невід’ємні змінні , і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 7 невідомих).
Складаємо симплекс – таблицю 1.
симплекс - таблиця 1
Базис Ci P0 P1 P2 P3 P4 P5 P6 P7
-200 -50 -70 -100 0 0 0
P5 0 -100 -150 -15 -5 -80 1 0 0
P6 0 -100 -150 0 0 -10 0 1 0
P7 0 -300 -25 -80 -120 -500 0 0 1
j 0 200 50 70 100 0 0 0
- оцінка невідомого .
10.7. Вибір розв’язуючого елемента
1. Розв’язуючий елемент повинен бути від’ємним!
2. Розв’язуючий рядок – P7 знаходимо з умови min (P0). min (-100;-100;-300) = -300.
3. Розв’язуючий стовпець – P4 знаходимо з умови min (|j/aij|), тут i – номер розв’язуючого рядка. min ( 200/25; 50/80; 70/120; 100/500) = 100/500.
4. Вектор P7 виходить з базису, Вектор P4 входить у базис.
5. Розв’язуючий елемент – число -500 – знаходиться на перетині розв’язуючого рядка P7 і розв’язуючого стовпця P4.
10.8. Алгоритм двоїстого симплекс-методу
1. Розв’язуючий рядок P7 ділимо на розв’язуючий елемент – число -500;
2. Базисні стовпці P5, P6 i P7 повинні бути одиничними векторами;
3. Усі інші елементи таблиці (стовпці P0 - P4 крім рядка P7) перераховуються згідно правила прямокутника:
. ( 18 )
Тут розв’язуючий елемент; елемент, який перераховується.
В результаті отримуємо наступну симплекс-таблицю 2.
симплекс - таблиця 2
Базис Ci P0 P1 P2 P3 P4 P5 P6 P7
-200 -50 -70 -100 0 0 0
P5 0 -52 -146 -2,2 14,2 0 1 0 -0,16
P6 0 -94 -149,5 1,6 2,4 0 0 1 -0,02
P4 -100 0,6 0,05 0,16 0,24 1 0 0 -0,002
j -60 195 34 46 0 0 0 0,2
План, який представлений у цій таблиці не є оптимальним, оскільки серед вільних членів P0 є від’ємні. За описаним вище алгоритмом знаходимо розв’язуючий рядок – P6 та розв’язуючи стовпець – P1. Змінна P6 виходить з базису, змінна P1 входить у базис. Застосовуючи алгоритм двоїстого симплекс-методу отримуємо наступну симплекс-таблицю 3.
симплекс - таблиця 3
Базис Ci P0 P1 P2 P3 P4 P5 P6 P7
-200 -50 -70 -100 0 0 0
P5 0 39.80 0.00 -3.76 11.86 0.00 1.00 -0.98 -0.14
P1 -200 0.63 1.00 -0.01 -0.02 0.00 0.00 -0.01 0.00
P4 -100 0.57 0.00 0.16 0.24 1.00 0.00 0.00 0.00
j -182.61 0.00 36.09 49.13 0.00 0.00 1.30 0.17
5. Оскільки всі P0 0, отримано оптимальний розв’язок задачі. Оптимальні значення параметрів x1, x4 i x5 знаходимо у стовпчику P0. Невідомі x2, x3, x6 i x7 яких немає у базисі є вільними і дорівнюють нулю.
Відповідь. Оптимальний харчовий раціон має вигляд: x1 = 0.63; x2 = 0; x3 = 0; x4 = 0.57; x5 = 39.8; x6 = 0; x7 = 0. Fmin (сумарна вартість) = 182,61.
Таблиця 4. В а р і а н т и з а в д а н ь д о т е м и 1 0
a11 a12 a13 a14 b1 a21 a22 a23 a24 b2 a31 a32 a33 a34 b3 c1 c2 c3 c4
1 6 15 5 12 450 16 7 10 5 480 12 9 8 9 420 1 7 2 5
2 10 8 7 9 450 3 12 4 10 360 15 4 12 3 300 1 7 2 5
3 10 4 8 3 400 7 8 6 9 360 3 9 2 5 225 6 6 1 5
4 7 6 5 8 280 3 7 2 5 210 12 5 9 4 330 4 2 4 4
5 4 12 3 8 300 10 4 7 3 320 5 6 6 8 240 6 8 3 6
6 7 8 6 9 315 3 8 2 5 210 14 5 10 4 420 6 8 3 6
7 20 8 16 5 480 8 20 5 14 560 10 11 9 8 440 7 7 3 5
8 9 4 8 3 320 4 12 3 9 300 5 8 5 7 280 6 9 4 7
9 7 10 6 9 350 10 5 12 4 450 6 18 4 12 360 6 9 4 7
10 15 8 16 5 480 10 12 8 10 450 8 20 5 14 490 7 9 4 6
11 9 15 10 12 450 15 8 12 6 525 6 20 4 15 500 5 6 1 6
12 10 15 9 12 450 10 3 9 2 300 4 12 3 7 350 5 7 4 1
13 7 2 9 3 280 6 8 7 9 270 3 9 4 6 225 2 5 6 2
14 3 12 4 7 280 5 7 6 8 240 10 4 11 3 330 2 5 5 2
15 3 7 2 5 210 9 3 10 4 360 12 16 10 15 480 4 3 8 2
16 7 3 6 2 210 5 6 4 5 200 7 21 6 12 525 6 9 5 2
17 8 25 7 15 600 12 11 9 10 495 9 3 8 2 540 6 9 5 2
18 5 8 4 6 240 3 12 2 8 300 11 3 9 4 275 3 7 2 4
19 11 4 10 3 275 4 12 3 8 320 7 9 5 6 315 3 9 3 4
20 21 6 12 5 525 9 15 10 12 420 6 20 5 12 480 3 8 3 3
21 5 8 6 7 245 5 12 3 8 320 10 3 7 4 315 7 6 5 4
22 16 5 12 3 420 4 16 5 10 400 9 10 7 8 360 1 5 6 3
23 3 10 2 7 245 7 8 6 5 280 10 3 4 2 240 1 8 2 6
24 4 12 3 8 270 12 3 7 2 280 6 7 5 7 245 2 7 3 6
25 8 10 6 9 330 4 12 5 10 360 18 4 10 3 360 2 7 3 6
26 5 10 3 8 280 5 8 4 6 240 12 4 10 3 300 7 4 5 6
27 5 20 6 15 450 8 4 9 2 270 5 7 6 5 420 1 9 4 7
N a11 a12 a13 a14 b1 a21 a22 a23 a24 b2 a31 a32 a33 a34 b3 c1 c2 c3 c4
28 6 8 7 5 280 2 8 3 6 210 10 4 11 3 330 1 9 4 7
29 8 2 6 3 240 7 9 6 8 300 3 9 2 7 225 4 3 5 7
30 3 12 4 9 300 6 9 5 6 270 10 4 8 3 320 2 11 5 8
31 4 15 4 12 420 12 4 15 3 360 7 8 6 10 350 2 11 5 8
32 6 15 3 12 420 8 10 6 7 350 12 5 10 4 400 7 8 2 6
33 6 20 5 12 540 20 7 15 6 560 6 7 4 5 210 6 5 4 1
34 18 7 12 4 480 10 15 8 9 450 7 20 4 12 560 5 6 2 3
35 7 24 6 16 600 12 10 9 15 510 18 7 16 5 540 2 5 4 3
36 10 25 8 20 750 30 10 20 8 640 15 18 12 16 600 7 1 5 4
37 20 8 15 4 510 7 21 5 14 525 8 10 9 12 420 4 9 3 5
38 9 3 6 2 210 7 24 8 16 560 12 16 10 15 480 3 6 5 4
39 3 10 2 7 210 9 3 7 2 630 12 16 10 15 540 5 10 4 6
40 3 9 2 6 240 8 3 7 2 210 12 15 10 16 600 5 6 4 2
41 12 4 10 3 300 4 12 3 7 280 5 7 6 8 280 6 8 5 3
42 8 10 6 9 360 12 6 10 4 420 6 16 5 10 400 6 7 5 2
43 15 8 12 5 450 9 12 8 10 420 8 20 6 15 480 3 4 2 5
44 18 4 10 3 450 5 16 3 12 400 8 9 7 10 360 4 8 1 7
45 15 4 10 3 600 10 15 12 15 495 8 25 4 15 600 5 7 1 6
46 3 10 4 9 315 6 8 5 7 280 12 4 10 3 300 5 4 3 6
47 15 4 12 5 360 8 9 7 10 315 5 15 3 12 450 4 9 2 8
48 6 20 4 15 450 10 12 8 9 420 20 6 15 5 480 5 9 2 7
49 16 5 10 4 400 4 15 5 12 360 7 12 8 10 315 7 4 1 8
50 7 10 6 8 350 16 5 15 4 400 5 12 3 9 360 6 3 1 2
Тема 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і В а р і а н т и
1 2 3 4 5 6 7
50 3.5 2 - - 1 1 - -
30 2.5 - 3 - 1 - 2 1
40 2.0 - - 3 - 2 1 2
Відходи 0.5 0 1.5 1.5 0 0.5 1.0
11.3.Математична модель задачі
Позначимо xі – кількість труб, розрізаних згідно і – го варіанту. Тоді отримаємо математичну модель задачі у наступному вигляді:
( 19 )
( 20 )
. ( 21 )
11.4. Канонічна форма задачі
Домножимо нерівності (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
Транспортна задача
12.1. Постановка задачі.
Три бригади за тиждень виробляють корми в кількостях a1, a2 i a3 відповідно. Їх необхідно розвезти на 5 ферм, згідно з поданими заявками, у кількостях b1, b2, b3, b4, b5. Вартість перевезення вважається пропорційною до кількості завантаженого корму xij і відстані від постачальника (бригади) до споживача (ферми) cij. Необхідно скласти такий план перевезень кормів, загальна вартість якого буде мінімальною. Необхідні для розрахунку параметри представлені у наступній Таблиці 7.
Таблиця 7. Технологічні параметри транспортної задачі.
Ферми Бригади
B1
B2
B3
B4
B5
Запаси
A1 4 3 2 2 4 140
A2 1 4 8 4 1 180
A3 9 7 3 7 2 160
Потреби 60 70 120 130 100 480
Необхідно скласти оптимальний план закріплення бригад за фермами з умовою мінімальної вартості перевезення кормів.
12.2. Математична модель транспортної задачі
Позначимо xij – кількість одиниць корму, який планується перевезти від i – го постачальника (сівозміни) до j – го споживача (ферми). Оскільки всі вантажі повинні бути вивезені, то мають місце такі рівності:
( 22 )
Оскільки всі потреби споживачів повинні бути задоволені, то мають місце такі рівності:
( 23 )
Оскільки вантажі перевозяться лише в одну сторону, очевидно, що:
( 24 )
Загальна вартість перевезення вважається пропорційною до кількості перевезених вантажів та відстані від постачальника до споживача і повинна бути мінімальною:
( 25 )
Якщо виконується умова , задача називається закритою.
12.3. Алгоритм розв’язування ТЗ
Потрібно:
1. скласти початковий опорний план задачі методом північно-західного кута;
2. скласти початковий опорний план задачі методом мінімального тарифа;
3. вибравши кращий з побудованих початкових планів, виконати його оптимізацію методом потенціалів за такою схемою:
3.1. скласти систему рівнянь (по базисних клітинах) для визначення потенціалів рядків Ui та стовпців Vj та, прийнявши U1=0, розв’язати отриману систему;
3.1.1. визначити характеристики вільних клітин за формулою
; ( 26 )
3.2. якщо всі характеристики є невід’ємні, завершити розв’язування задачі. Виписати оптимальний план перевезень у вигляді матриці, а також мінімальне значення вартості перевезень Fmin;
3.3. якщо не всі характеристики є невід’ємні, необхідно вибрати найбільшу додатну характеристику і побудувати для відповідної вільної клітини таблиці цикл. Позначити вершини циклу умовними знаками “+” (збільшити вантажо-потік) i “-” (зменшити вантажопотік). Початкова вільна вершина позначається знаком “+”, а всі інші – по черзі “-” i “+”; серед всіх вершин, позначених знаком “-”, вибрати найменше перевезення – m . Для всіх вершин, позначених знаком “+”збільшити перевезення на m, для вершин, позначених знаком “-” зменшити перевезення на m . Перейти до пункту 3.1
12.4. Побудова початкового опорного плану ТЗ
Таблиця 8. Метод північно – західного кута
B1 B2 B3 B4 B5 Запаси
A1 4 3 2 2 4 140
60 70 10
A2 1 4 8 4 1 180
110 70
A3 9 7 3 7 2 160
60 100
Потреби 60 70 120 130 100 480
F = 60*4 + 70*3 + 10*2 + 110*8 + 70*4 + 60*7 + 100*2 =
240 + 210 + 20 + 880 + 280 + 420 + 200 = 2250 – вартість перевезень
Таблиця 9. Метод мінімального тарифа
B1 B2 B3 B4 B5 Запаси
A1 4 3 2 2 4 140
10 130
A2 1 4 8 4 1 180
60 20 100
A3 9 7 3 7 2 160
50 110
Потреби 60 70 120 130 100 480
F = 10*2 + 130*2 + 60*1 + 20*4 + 100*1 + 50*7 + 110*3 =
20 + 260 + 60 + 80 + 100 + 350 + 330 = 1200 – вартість перевезень
12.5. Метод потенціалів
За основу виберемо план, складений по методу мінімального тарифа. Оптимізуємо даний план за методом потенціалів. Для кожного i – го рядка та j – го стовпця введемо певну їх ознаку – потенціал. Складаємо систему рівнянь (по базисних клітинках плану) для визначення потенціалів рядків і стовпців, використовуючи наступну формулу .
U1 + V3 = 2;
U1 + V4 = 2;
U2 + V1 = 1;
U2 + V2 = 4;
U2 + V5 = 1;
U3 + V2 = 7;
U3 + V3 = 3.
Приймемо U1 = 0. Тоді отримаємо наступний розв’язок системи:
U1 =0; V3 = 2;
U1 =0; V4 = 2;
U2 =-2; V1 = 3;
U2 =-2; V2 = 6;
U2 =-2; V5 = 3;
U3 =1; V2 = 6;
U3 =1; V3 = 2.
Для кожної вільної клітинки введемо поняття її характеристики , яку будемо обчислювати за формулою:
. ( 27 )
Тут та - потенціали відповідних рядка і стовпця, - тариф даного перевезення. Додатна характеристика вільної клітини свідчить про неоптимальність плану і є підставою для включення даної клітини в новий план. Обчислимо характеристики вільних клітин:
11 = u1 + v1 – c11 = 0 + 3 – 4 = -1;
12 = u1 + v2 – c12 = 0 + 6 – 3 = +3;
15 = u1 + v5 – c15 = 0 + 3 – 4 = -1;
23 = u2 + v3 – c23 = -2 + 2 – 8 = -8;
24 = u2 + v4 – c24 = -2 + 2 – 4 = -4;
31 = u3 + v1 – c31 = 1 + 3 – 9 = -5;
34 = u3 + v4 – c34 = 1 + 2 – 7 = -4;
35 = u3 + v5 – c35 = 1 + 3 – 2 = +2.
Характеристики 12 і 35 є додатніми. Це свідчить про неоптимальність плану. Клітинку A1B2 необхідно включити в план. Деяку клітинку необхідно виключити з базису. Для цього складаємо цикл вільної клітини. Клітина A1B2 буде початком циклу.
12.6. Перерозподіл вантажопотоків по вершинах циклу - 1
B1 B2 B3 B4 B5 Запаси
A1
4 + 3 - 2 2 4 140
10 130
A2 1 4 8 4 1 180
60 20 100
A3
9 - 7 + 3 7 2 160
50 110
Потреби 60 70 120 130 100 480
Будуємо цикл. Це є ламана лінія, вершини якої розташовані у клітинах таблиці, а ланки – вздовж рядків, чи стовпців. В кожній вершині циклу зустрічається дві ланки, одна з яких знаходиться у рядку, а друга у стовпці. Початковою вершиною завжди виступає вільна клітина. Всі інші вершини – це базисні клітини. Форма циклу – це прямокутник, “чобіт”, або ”вісімка”. Якщо ламана лінія, що утворює цикл перетинається, то точки самоперетину не є вершинами.
Початкову клітину циклу A1B2 помічаємо знак “+”. Всі інші кутові вершини циклу по черзі помічаємо знаками “-” i ”+”. В якості перерозподілюваного елемента вибираємо число 10 (мінімальний вантаж серед усіх клітин помічених знаком “-”). До клітинок помічених знаком “+” додаємо число 10, від клітин помічених знаком “-” віднімаємо число 10. Клітина A1B2 входить у базис, клітина A1B3 виходить з базису. Отримуємо новий план
Види циклів.
прямокутник “чобіт” ”вісімка”
12.7. Метод потенціалів. Другий крок
B1 B2 B3 B4 B5 Запаси
A1 4 3 2 2 4 140
10 130
A2 1 4 8 4 1 180
60 20 100
A3 9 7 3 7 2 160
40 120
Потреби 60 70 120 130 100 480
Вартість плану: F = 30 + 260 + 60 + 80 + 100 + 280 + 360 = 1170
Складаємо систему рівнянь для визначення потенціалів рядків і стовпців:
U1 + V2 = 3;
U1 + V4 = 2;
U2 + V1 = 1;
U2 + V2 = 4;
U2 + V5 = 1;
U3 + V2 = 7;
U3 + V3 = 3.
Приймемо U1 = 0. Тоді отримаємо наступний розв’язок системи:
U1 =0; V2 = 3;
U1 =0; V4 = 2;
U2 =1; V1 = 0;
U2 =1; V2 = 3;
U2 =1; V5 = 0;
U3 =4; V2 = 3;
U3 =4; V3 = -1.
Обчислимо характеристики вільних клітин:
11 = u1 + v1 – c11 = 0 + 0 – 4 = -4;
13 = u1 + v3 – c13 = 0 + (–1) – 2 = -3;
15 = u1 + v5 – c15 = 0 + 0 – 4 = -4;
23 = u2 + v3 – c23 = 1 + (-1) – 8 = -8;
24 = u2 + v4 – c24 = 1 + 2 – 4 = -1;
31 = u3 + v1 – c31 = 4 + 0 – 9 = -5;
34 = u3 + v4 – c34 = 4 + 2 – 7 = -1;
35 = u3 + v5 – c35 = 4 +0 – 2 = +2.
Характеристика 35 є додатною. Це свідчить про неоптимальність плану. Клітинку A3B5 необхідно включити в план. Деяку клітинку необхідно виключити з базису. Для цього складаємо цикл вільної клітини. Клітина A3B5 буде початком циклу.
12.8. Перерозподіл вантажопотоків по вершинах циклу - 2
B1 B2 B3 B4 B5 Запаси
A1 4 3 2 2 4 140
10 130
A2 1 +
4 8 4 -
1 180
60 20
100
A3 9 -
7 3 7 +
2 160
40 120
Потреби 60 70 120 130 100 480
Будуємо цикл A3B5 – A3B2 – A2B2 – A2B5. В якості перерозподілюваного елемента вибираємо число 40 (мінімальний вантаж серед усіх клітин помічених знаком “-”). До клітинок помічених знаком “+” додаємо число 40, від клітин помічених знаком “-” віднімаємо число 40. Клітина A3B5 входить у базис, клітина A3B2 виходить з базису. Отримуємо новий план
B1 B2 B3 B4 B5 Запаси
A1 4 3 2 2 4 140
10 130
A2 1 4 8 4 1 180
60 60 60
A3 9 7 3 7 2 160
120 40
Потреби 60 70 120 130 100 480
Вартість плану: F = 30 + 260 + 60 + 240 + 60 + 360 + 80 = 1090
Складаємо систему рівнянь для визначення потенціалів рядків і стовпців:
U1 + V2 = 3;
U1 + V4 = 2;
U2 + V1 = 1;
U2 + V2 = 4;
U2 + V5 = 1;
U3 + V3 = 3;
U3 + V5 = 2.
Висновок. Всі характеристики є недодатніми. Це свідчить про оптимальність плану. Оптимальний план має вигляд:
Fmin = 1090.
Таблиця 10. Технологічні параметри транспортної задачі
№ a1 a2 a3 b1 b2 b3 b4 b5 c11 c12 c13 c14 c15 c21 c22 c23 c24 c25 c31 c32 c33 c34 c35
1 130 105 50 55 25 90 35 80 10 8 3 9 14 14 4 10 5 2 7 13 5 1 10
2 90 30 135 75 35 50 10 85 14 2 5 3 10 9 7 12 14 1 6 13 7 1 5
3 100 125 40 40 65 80 50 30 3 11 4 10 7 14 3 1 4 13 5 13 11 14 4
4 55 75 150 80 25 15 70 90 10 7 14 2 12 13 11 6 10 2 1 14 10 6 8
5 135 90 50 40 65 55 95 20 5 8 10 12 9 14 4 7 1 12 7 14 12 4 1
6 130 70 90 90 70 45 60 25 3 5 9 12 7 7 10 12 3 11 1 13 2 10 3
7 105 135 70 40 50 60 90 70 6 2 4 13 8 3 6 14 8 12 13 10 8 4 1
8 60 25 175 45 70 35 85 25 14 1 3 9 4 2 10 6 14 12 12 6 11 5 7
9 15 65 200 90 60 45 70 15 12 1 13 5 8 5 12 10 14 1 1 6 3 9 11
10 100 125 20 15 55 70 25 80 9 14 12 2 8 2 9 4 13 1 13 1 7 10 14
11 75 20 175 85 10 60 75 40 13 6 2 12 10 1 10 7 9 13 8 3 10 1 6
12 80 45 65 10 25 55 35 65 3 13 2 4 10 6 8 13 9 14 13 2 8 14 4
13 75 50 135 80 25 55 35 65 5 11 2 10 13 1 6 13 7 2 10 13 4 2 6
14 45 65 125 95 20 10 35 75 2 10 1 14 11 10 5 8 6 2 5 12 4 10 7
15 110 20 135 65 25 10 75 90 2 13 1 14 5 14 1 4 11 13 4 6 14 8 1
16 125 30 160 75 100 60 45 35 2 11 5 10 4 10 8 1 5 14 5 14 9 12 1
17 35 85 130 55 15 85 25 70 2 6 1 13 11 13 3 7 4 6 10 14 3 1 9
18 105 30 125 45 65 15 35 100 5 13 4 14 6 8 1 10 6 14 14 7 2 12 4
19 135 55 100 20 95 35 60 80 10 6 2 8 12 7 9 13 2 8 12 1 7 14 4
20 45 25 185 80 35 50 70 20 2 13 6 14 8 13 3 11 8 4 6 9 1 4 12
21 95 30 140 65 90 10 25 75 10 12 5 2 9 4 9 12 8 6 7 4 8 12 14
22 80 105 45 40 95 30 10 55 10 8 13 1 6 7 13 4 6 10 2 10 1 14 3
23 25 65 185 50 70 85 60 10 4 8 12 3 9 14 5 8 6 3 6 1 4 12 14
24 95 25 115 10 85 45 25 70 14 1 12 2 8 10 8 6 13 2 3 12 9 5 14
25 65 45 145 65 45 35 25 85 3 1 6 9 14 9 7 1 3 5 14 12 10 7 1
26 115 55 90 45 35 90 25 65 5 12 6 2 7 11 5 10 8 13 2 10 3 13 4
27 90 45 115 20 65 35 85 45 7 10 3 11 5 13 4 12 3 14 9 12 1 8 10
28 50 25 220 75 40 90 65 25 1 3 9 11 2 8 13 1 6 10 4 8 11 9 6
29 35 80 110 15 80 40 65 25 2 8 14 12 4 12 5 7 4 10 6 1 10 7 13
30 40 15 225 55 40 90 25 70 7 10 4 9 3 11 13 7 14 9 2 6 11 3 5
31 65 15 195 95 60 25 85 10 8 3 11 7 4 5 7 4 11 13 11 13 8 5 7
32 15 80 190 35 50 25 95 80 7 1 13 4 10 11 7 3 10 6 4 13 6 2 12
33 60 85 35 45 35 60 25 15 5 13 3 8 11 2 10 7 11 5 8 1 13 5 14
34 35 65 175 50 80 10 100 35 9 2 8 12 1 6 12 1 4 8 1 4 6 9 12
35 75 130 40 45 65 35 20 80 13 4 10 2 11 8 13 7 14 6 4 10 14 8 3
36 50 25 145 50 60 25 15 70 1 12 10 3 7 11 8 14 9 12 14 5 2 6 3
37 115 30 145 95 25 75 35 60 13 1 11 6 12 3 6 8 1 5 7 10 13 9 1
38 55 20 160 10 85 40 75 25 12 8 2 13 5 8 1 12 7 9 1 11 5 3 12
39 110 55 130 20 80 90 40 65 2 9 7 12 14 14 3 10 8 1 10 12 4 2 5
40 90 110 65 80 65 55 45 20 6 9 7 12 1 12 5 2 9 11 9 11 5 1 14
41 90 20 155 85 40 60 70 10 9 4 2 10 5 6 12 10 1 9 11 6 4 14 2
42 125 80 55 90 45 65 25 35 13 10 7 12 14 9 7 13 6 3 3 1 9 2 11
43 20 115 135 50 35 15 75 95 3 1 11 7 10 8 12 1 4 6 14 8 4 10 1
44 95 20 125 10 85 25 50 70 8 5 1 10 4 2 8 13 7 11 10 12 9 2 7
45 65 35 170 95 35 65 50 25 4 13 9 3 1 10 6 3 13 11 13 11 14 8 6
46 130 35 160 80 95 35 70 45 2 5 12 7 3 13 2 8 10 14 6 8 4 14 11
47 60 20 105 35 70 50 20 10 6 3 1 11 7 2 13 8 14 11 13 7 11 9 2
48 35 130 110 75 45 65 35 55 1 8 12 2 7 4 14 2 8 12 13 2 14 5 9
49 15 60 155 50 70 10 60 40 9 14 5 7 2 13 10 1 14 9 3 1 13 4 6
50 45 95 120 35 55 85 65 20 10 1 13 2 12 13 5 2 7 1 7 13 6 11 14
