Лабораторна робота 7-8. Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт з Математичні методи дослідження операцій. Робота № 525419

Перехід до торгівельного партнера Binance

Лабораторна робота 7-8

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКНІ

Факультет:

Комп’ютерні науки

Кафедра:

Не вказано

Інформація про роботу

Рік:

2011

Тип роботи:

Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт

Предмет:

Математичні методи дослідження операцій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ Національний університет “Львівська політехніка” ІКНІТ Методичні вказівки до лабораторної роботи № 7-8 "Транспортна задача. Метод потенціалів " з дисципліни “Математичні методи дослідження операцій” для студентів бакалаврського напряму “Комп’ютерні науки” Львів – 2011 Лабораторна робота № 7-8. Транспортна задача. Метод потенціалів Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми. Короткі теоретичні відомості Постановка транспортної задачі В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n. Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами. Розв’язування транспортної задачі 1.2.1. Умови Т-задачі записуються у вигляді ai С = bj b1 b2 b3 … bn Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ). Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію L = , з виконанням умов Матрицю Х = називають планом перевезень Т-задачі. 1.2.2.Визначення початкового опорного плану. 1.2.2.1. Метод «північно-західного кута» (ПЗК). Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута. Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n. Припустимо, що вже виконано t кроків. Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай ( + ( = t + 2. Знаходимо x(( = min{}, де . Якщо , то заповнюється (-ий рядок матриці, починаючи з ((+1)-го елемента, нулями. Якщо , то заповнюється нулями (-й стовбець, починаючи з ((+1)-ї строки. При цьому ; 1.2.2.2. Приклад визначення початкового опорного плану методом «північно-західного кута» (ПЗК). Записуються умову Т-задачі ai С = bj 70 5 45 70 Перевіряємо умову балансу ; 190 = 190. Будуємо початковий опорний план Х0: Х0 = x11 = min{60,70} = 60; x21 = min{55,70-60} = 10; x22 = min{5, 55-10} = 5; x23 = min{45,55-10-5} = 40; x33 = min(40, 45-40} = 5; x34 = min{70,40-5} = 35; x44 = 35. Отриманий початковий опорний план Х0 невироджений ( m + n - 1 = 4+4-1 = 7). Вартість перевезень в у.о. L0= = 60(1 + 10(3 + 5(4 + 40(1 + 5(8 + 35(3 + 35(1 = 330. 1.2.3.Метод потенціалів розв’язування транспортної задачі. Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій. 1.2.3.1. Попередній етап. 1. Будується початковий опорний план Х0. 2. Обчислюється оціночна матриця Δ1 = , де ui i vj – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова для хij ( 0 (базових клітин). Для зручності вибирається u1 = 0. Позиція в матриці Δ1, яка відповідає базисному елементові плану Х0, буде зайнята нулем. Якщо всі елементи матриці Δ1 – не додатні, то план Х0 – оптимальний. Якщо ні, то виконується наступна ітерація. k + 1 ітерація. 1. Якщо в оціночній матриці Δ (к+1) всі елементи не додатні, то план Хк – оптимальний. Якщо ні, виконується наступний крок. 2. Вибирається з Δ (к+1) найбільший додатний елемент і, починаючи з відповідного йому елемента в матриці Хк, будується замкнута послідовність, в яку входять елементи . Потім визначається ( - мінімальний елемент серед всіх непарних за порядком розміщення в послідовності, приймаючи першим елементом наступний за елемент. 3. Будується новий план Хк+1, додаванням до всіх парних елементів послідовності і відніманням від всіх непарних. Елементи матриці Хк, що не входять в послідовність, переносяться в матрицю Хк+1, без змін. 4. З матриці Δк будується оціночна матриця Δк+1 для нового плану Хк+1. Для цього підкреслюються в матриці Δк всі елементи, які відповідають ненульовим елементам матриці Хк+1 (вони обов’язково рівні нулю). В матриці Δк закреслюємо рядок, який містить елемент cst. Якщо в цьому рядку є підкреслені елементи, то закреслюються відповідні до цих елементів стовбці. Якщо в кожному закресленому стовбці є підкреслені елементи, то закреслюються відповідні до них рядки, і так до того моменту, доки описана процедура може виконуватися. Після цього до всіх елементів закреслених рядків додається (cst(, а від елементів закреслених стовбців віднімається величина (cst(. Якщо в матриці Δк+1 відсутні від’ємні елементи, то план Хк+1 – оптимальний, інакше перехід до наступної ітерації. 1.2.3.3. Продовження прикладу п. 1.2.2.2. Для зручності обчислень потенціалів будується відповідний граф початкового опорного плану перевезень. u1= 0 u2= 2 u3= 9 u4= 7 1 4 8 1 3 1 3 v1=1 v2=2 v3= -1 v4= -6 Будується оціночна матриця Δ1 з елементами ; …………………………………………. Δ 1 = Оскільки в Δ1 є від’ємні елементи, то план Х0 - не оптимальний. 1-а ітерація. Починаючи з елемента х32 в матриці Х0, що відповідає в оціночній матриці Δ1 найбільшому додатному елементу 7, будуємо замкнену послідовність. Змінюючи елементи, які входять в послідовність, на величину ( = min{5,5} = 5,будуємо новий план перевезень Х1: Х0 = , Х1 = . Отриманий новий план Х1 є виродженим, через що (у випадку, коли необхідно обчислення Х2, Х3, ... і т.д.) один з нулів замкненої послідовності замінюється величиною ( ( 0. У випадку виродженості при побудові початкового опорного плану вводиться xij = ( по тій комунікації, яка необхідна для визначення потенціалів . Отже отримуємо: Δ1 = , Δ2 = . В оціночній матриці Δ2 відсутні додатні елементи, отже, план Х1 = є оптимальний, не дивлячись на те, що він вироджений. Вартість перевезень в у.о. L1= = 60(1 + 10(3 + 45(1 + 5(4 + 35(3 + 35(1 = 295. Розв’язування транспортної задачі засобами Еxcel. Перевірка рішення в Excel Завантажте шаблон для перевірки в Excel (посилання наведена нижче) Відкрийте його в MS Excel Мишкою або за допомогою клавіатури перейдіть до комірки B16 Виконайте команду Сервіс / Пошук рішення У діалоговому вікні вкажіть:в поле Рівної: мінімального значеннямв поле змінюючи осередки: $B$9:$E$12в поле Обмеження додайте задані обмеженняПоле повинно мати такий зміст:$B$9:$E$12>=0$F$9:$F$12<=$G$9:$G$12$B$13:$E$13=$B$14:$E$14 Натисніть на кнопку Виконати Значення змінних Xi може різнитися, але цільова функція F(x) повинна мати таке ж значення. Розв’язання транспортної задачі в системі Mathcad Перевіряємо умову балансу: Вводимо: цільову функцію; початкові наближення; систему обмежень; граничні значення. Після цього система Mathcad може визначити оптимальний розв’язок транспортної задачі та значення цільової функції при ньому. Зауваження. Щоб перенести многочлен, який складається з кількох доданків, потрібно натиснути комбінацію клавіш Ctrl+Enter. При оформленні системи обмежень необхідно використати жирний знак рівності (=)на панелі інструментів Boolean або натиснути комбінацію клавіш Ctrl+=. Порядок роботи: Номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100. 1. Знайти базове рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язати транспортну задачу методом потенціалів. 2. Знайти базове рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язати транспортну задачу методом потенціалів. 3. Отримати умову для відкритої ТЗ від завдання закритої, замінивши a1 = a1+10 – для непарних варіантів або b1 = b1+10 – для парних варіантів. Збалансувати відкриту ТЗ, додавши відповідно додатковий стовпець або рядок. З найти базове рішення шляхом найменшої вартості (НВ) і розв’язати транспортну задачу методом потенціалів. Заповнити початкову таблицю транспортної задачі лінійного програмування відповідно до свого варіанту. Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям методу потенціалів задачі лінійного програмування. Знайти оптимальний план перевезень та мінімальне значення цільової функції. Заповнити початкову таблицю транспортної задачі лінійного програмування відповідно до свого варіанту. Використовуючи засоби MathCad , розв’язати транспортну задачу лінійного програмування. Знайти оптимальний план перевезень та мінімальне значення цільової функції. Заповнити початкову таблицю транспортної задачі лінійного програмування відповідно до свого варіанту. Використовуючи один із математичних пакетів (наприклад, Optimal 1_4), розв’язати транспортну задачу лінійного програмування. Знайти оптимальний план перевезень та мінімальне значення цільової функції. Розробити оригінальну програму. Використовуючи розроблену програму, розв’язати транспортну задачу лінійного програмування. Знайти оптимальний план перевезень та мінімальне значення цільової функції. Подати у звіті алгоритм розв'язку задачі (програми), лістинг та порядок використання програми. Проінтерпретувати отримані результати для вихідної задачі. СПИСОК ЛІТЕРАТУРИ 1. Барінський А.Ф. і ін. Математичне програмування та дослідження операцій. – Л.: Інтелект- Захід, 2008. – 588с.: іл. 2. Барінський А.Ф. і ін. Математичне програмування. – Л.: Інтелект-Захід, 2004. – 448с.: іл. 3. Зайченко Ю.П. Дослідження операцій. – К.: ДМК Пресс, 2006. – 576с.: іл. 4. Долженков В.А., Колесников Ю.В. Microsoft( Excel 2000. – СПб.: БХВ-Петербург, 2001. – 1088с. 5. Кудрявцев Е.М. Mathcad 2000 Pro. – М.: ДМК Пресс, 2001. – 576с. 6. Таха Хэмди А. Введение в исследование операций, 6-е издание: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912с.: ил. Індивідуальні завдання Номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100. 1. Знайти базове рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язати транспортну задачу методом потенціалів. 2. Знайти базове рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язати транспортну задачу методом потенціалів. 3. Отримати умову для відкритої ТЗ від завдання закритої, замінивши a1 = a1+10 – для непарних варіантів або b1 = b1+10 – для парних варіантів. Збалансувати відкриту ТЗ, додавши відповідно додатковий стовпець або рядок. З найти базове рішення шляхом найменшої вартості (НВ) і розв’язати транспортну задачу методом потенціалів. ai 1. С = bj 15 15 40 30 ai 2. С = bj 20 34 16 10 25 ai 3. С = bj 40 30 30 50 ai 4. С = bj 35 20 55 30 ai 5. С = bj 140 130 90 140 ai 6. С = bj 40 30 35 15 ai 7. С = bj 40 30 30 50 ai 8. С = bj 30 25 15 20 ai 9. С = bj 40 60 70 25 ai 10. С = bj 15 40 30 15 ai 11. С = bj 30 25 35 20 ai 12. С= bj 30 80 65 35 40 ai 13. С = bj 110 50 30 80 100 90 ai 14. С = bj 30 40 30 55 ai 15. С = bj 70 5 45 70 ai 16. С = bj 16 18 12 15 ai 17. С = bj 10 35 15 25 35 ai 18. С = bj 110 30 50 80 90 ai 19. С = bj 25 30 40 30 ai 20. С = bj 20 30 55 45 ai 21. С = bj 25 30 40 15 ai 22. С = bj 30 40 20 60 ai 23. С = bj 30 80 20 70 ai 24. С = bj 25 30 40 15 ai 25. С = bj 15 15 40 30 ai 26. С = bj 20 34 16 10 25 ai 27. С = bj 40 30 30 50 ai 28. С = bj 35 20 55 30 ai 29. С = bj 140 130 90 140 ai 30. С = bj 40 30 35 15 ai 31. С = bj 40 30 30 50 ai 32. С = bj 30 25 15 20 ai 33. С = bj 40 60 70 25 ai 34. С = bj 15 40 30 15 ai 35. С = bj 30 25 35 20 ai 36. С= bj 30 80 65 35 40 ai 37. С= bj 110 50 30 80 100 90 ai 38. С = bj 30 40 30 55 ai 39. С = bj 70 5 45 70 ai 40. С = bj 16 18 12 15 ai 41. С = bj 10 35 15 25 35 ai 42. С = bj 110 30 50 80 90 ai 43. С = bj 25 30 40 30 ai 44. С = bj 20 30 55 45 ai 45. С = bj 20 10 45 75 ai 48. С = bj 25 30 40 15 ai 47. С = bj 30 80 20 70 48. С = bj 20 10 45 75 ai 49. С = bj 15 15 40 30 ai 50. С = bj 20 34 16 10 25 ai 51. С = bj 40 30 30 50 ai 52. С = bj 35 20 55 30 ai 53. С = bj 140 130 90 140 ai 54. С = bj 40 30 35 15 ai 55. С = bj 40 30 30 50 ai 56. С = bj 30 25 15 20 ai 57. С = bj 40 60 70 25 ai 58. С = bj 15 40 30 15 ai 59. С = bj 30 25 35 20 ai 60. С= bj 30 80 65 35 40 ai 61. С = bj 110 50 30 80 100 90 ai 62. С = bj 30 40 30 55 ai 63. С = bj 70 5 45 70 ai 64. С = bj 16 18 12 15 ai 65. С = bj 10 35 15 25 35 ai 66. С = bj 110 30 50 80 90 ai 67. С = bj 30 40 20 60 ai 68. С = bj 20 30 55 45 ai 69. С = bj 20 10 45 75 ai 70. С = bj 25 30 40 30 ai 71. С = bj 30 80 20 70 ai 72. С = bj 25 30 40 15 ai 73. С = bj 15 15 40 30 ai 74. С = bj 20 34 16 10 25 ai 75. С = bj 40 30 30 50 ai 76. С = bj 35 20 55 30 ai 77. С = bj 140 130 90 140 ai 78. С = bj 40 30 35 15 ai 79. С = bj 40 30 30 50 ai 80. С = bj 30 25 15 20 ai 81. С = bj 40 60 70 25 ai 82. С = bj 15 40 30 15 ai 83. С = bj 30 25 35 20 ai 84. С= bj 30 80 65 35 40 ai 85.С = bj 110 50 30 80 100 90 ai 86. С = bj 30 40 30 55 ai 87. С = bj 70 5 45 70 ai 88. С = bj 16 18 12 15 ai 89. С = bj 10 35 15 25 35 ai 90. С = bj 110 30 50 80 90 ai 91. С = bj 25 30 40 30 ai 92. С = bj 20 30 55 45 ai 93. С = bj 20 10 45 75 ai 94. С = bj 30 40 20 60 ai 95. С = bj 30 80 20 70 ai 96. С = bj 25 30 40 15 ai 97. С = bj 15 15 40 30 ai 98. С = bj 20 34 16 10 25 ai 99. С = bj 40 30 30 50 ai 100. С= bj 200 250 180 200 300 250

Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт Математичні методи дослідження операцій

tinysinjka

27.12.2013 02:12-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись