Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Транспортна задача. Метод потенціалів.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ІКНІТ
Методичні вказівки до лабораторної роботи № 5,6
"Транспортна задача. Метод потенціалів "
з дисципліни
“Математичні методи дослідження операцій”
для студентів спеціальності 6.08.04 “Комп’ютерні науки”
Львів – 2002
Методичні вказівки до лабораторної роботи № 5,6 “Транспортна задача. Метод потенціалів" з дисципліни “Математичні методи дослідження операцій” для студентів спеціальності 6.08.04 “Комп’ютерні науки” /Укл. Дронюк І.М. – Львів: Національний університет «Львівська політехніка», 2002.
Укладач: Дронюк І.М., канд. фіз.-мат. наук, доц..
Відповідальний за випуск: Обельовська К.М., канд. техн. наук, доц.
Рецензент: Різник В.В., докт. техн. наук, проф.
Лабораторна робота № 5
Тема: Транспортна задача. Метод потенціалів
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel
Порядок роботи:
Заповнити початкову таблицю транспортної задачі лінійного програмування згідно заданого варіанту.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям методу потенціалів задачі лінійного програмування.
Знайти мінімальне значення цільової функції та оптимальний розв'язок.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком
назва роботи
мета роботи
порядок роботи
короткі теоретичні відомості
алгоритм розв'язку задачі
малюнки відповідних таблиць
аналіз отриманих результатів та висновки
Короткі теоретичні відомості
Постановка
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1 i m, 1 j n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Розв’язування
Умови Т-задачі записуються у вигляді
ai
С = EMBED Equation.3 EMBED Equation.3
bj b1 b2 b3 … bn
Введемо змінні хij 0, 1 i m, 1 j n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва в пункт споживання j.
Необхідно знайти множину значень змінних хij 0, мінімізуючи функцію
L = EMBED Equation.3 ,
з виконанням умов
EMBED Equation.3
Матрицю
Х = EMBED Equation.3
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута».
Визначаємо елементи матриці Х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{ EMBED Equation.3 }, де
EMBED Equation.3 .
Якщо EMBED Equation.3 , то заповнюється -ий рядок матриці, починаючи з (+1)-го елемента, нулями. Якщо EMBED Equation.3 , то заповнюється нулями -й стовбець, починаючи з (+1)-ї строки. При цьому
EMBED Equation.3
EMBED Equation.3
Приклад.
ai
С = EMBED Equation.3 EMBED Equation.3
bj 70 5 45 70
Перевіряємо умову балансу EMBED Equation.3 ; 190 = 190.
Будуємо початковий опорний план Х0:
Х0 = EMBED Equation.3
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 невироджений.
Метод потенціалів.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
Попередній етап.
Будується початковий опорний план Х0.
Обчислюється оціночна матриця
С1 = EMBED Equation.3 ,
де vj i ui – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова EMBED Equation.3 і хij 0. Для зручності вибирається u1 = 0. Позиція в матриці С1, яка відповідає базисному елементові плану Х0, буде зайнята нулем.
Якщо всі елементи матриці С1 – не від’ємні, то план Х0 – оптимальний. Якщо ні, то виконується наступна ітерація.
k + 1 ітерація.
Якщо в оціночній матриці С(к+1) всі елементи не від’ємні, то план Хк – оптимальний. Якщо ні, виконується наступний крок.
Вибирається найбільший по модулю від’ємний елемент EMBED Equation.3 і, починаючи з відповідного йому елемента EMBED Equation.3 в матриці Хк, будується замкнута послідовність, в яку входять елементи EMBED Equation.3 .Потім визначається - мінімальний елемент серед всіх непарних за порядком розміщення в послідовності, приймаючи першим елементом наступний за EMBED Equation.3 елемент.
Будується новий план Хк+1, додаванням до всіх парних елементів послідовності і відніманням від всіх непарних. Елементи матриці Хк, що не входять в послідовність, переносяться в матрицю Хк+1, без змін.
З матриці Ск будується оціночна матриця Ск+1 для нового плану Хк+1. Для цього підкреслюються в матриці Ск всі елементи, які відповідають ненульовим елементам матриці Хк+1 (вони обов’язково рівні нулю). В матриці Ск закреслюємо строку, яка містить елемент cst. Якщо в цьому рядку є підкреслені елементи, то закреслюються відповідні до цих елементів стовбці. Якщо в кожному закресленому стовбці є підкреслені елементи, то закреслюються відповідні до них рядки, і так до того моменту, доки описана процедура виконувана. Після того до всіх елементів закреслених рядків додається cst, а від елементів закреслених стовбців віднімається величина cst.
Якщо в матриці Ск+1 відсутні від’ємні елементи, то план Хк+1 – оптимальний, інакше перехід до наступної ітерації.
Продовження прикладу.
Для зручності обчислень потенціалів EMBED Equation.3 будується відповідний граф початкового опорного плану перевезень.
A4
A3
A2
A1
u1= 0 u2= -2 u3= -9 u4= -7
1 8 1
B4
B3
B2
B1
3 4 1 3
v1=1 v2=2 v3= -1 v4= -6
Будується оціночна матриця С1 з елементами
EMBED Equation.3 ;
EMBED Equation.3
………………………………………….
C1 = EMBED Equation.3
Оскільки в С1 є від’ємні елементи, то план Х0 - не оптимальний.
1-а ітерація. В матриці Х0, починаючи з елемента х32, відповідного в оціночній матриці до найбільшого від’ємного елемента, будуємо замкнену послідовність. Змінюючи елементи, які входять в послідовність, на величину = min{5,5} = 5,будуємо новий план перевезень Х1:
Х0 = EMBED Equation.3 , Х1 = EMBED Equation.3 .
Отриманий новий план Х1 є виродженим, через що (у випадку, коли необхідно обчислення Х2, Х3, ... і т.д.) один з нулів замкненої послідовності замінюється величиною 0. У випадку виродженості при побудові початкового опорного плану вводиться xij = по тій комунікації, яка необхідна для визначення потенціалів EMBED Equation.3 .
Отже отримуємо:
C1 = EMBED Equation.3 , C2 = EMBED Equation.3 .
В оціночній матриці C2 відсутні від’ємні елементи, отже, план
Х1 = EMBED Equation.3 є оптимальний, не дивлячись на те, що він вироджений.
Вартість перевезень в у.о. L = EMBED Equation.3 = 601 + 102 + 401 + 54 + 353 + 351 = 295.
Лабораторна робота № 6
Тема: Транспортна задача. Метод потенціалів
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навиками розвязання оптимізаційних задач в середовищі MathCad
Порядок роботи:
Заповнити початкову таблицю транспортної задачі лінійного програмування згідно заданого варіанту.
Використовуючи засоби MathCad ,розв’язати транспортну задачу лінійного програмування.
Знайти мінімальне значення цільової функції та оптимальний розв'язок.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком
назва роботи
мета роботи
порядок роботи
короткі теоретичні відомості
алгоритм розв'язку задачі
малюнки відповідних таблиць
аналіз отриманих результатів та висновки
Розв’язання транспортної задачі в системі Mathcad
Перевіряємо умову балансу: EMBED Equation.3
Вводимо:
цільову функцію;
початкові наближення;
систему обмежень;
граничні значення.
Після цього система Mathcad може визначити оптимальний розв’язок транспортної задачі та значення цільової функції при ньому.
EMBED Mathcad
Зауваження.
Щоб перенести многочлен, який складається з кількох доданків, потрібно натиснути комбінацію клавіш Ctrl+Enter.
При оформленні системи обмежень необхідно використати жирний знак рівності (=)на панелі інструментів Boolean або натиснути комбінацію клавіш Ctrl+=.
EMBED Mathcad
Завдання
ai
1. С = EMBED Equation.3 EMBED Equation.3 .
bj 15 15 40 30
ai
2. С = EMBED Equation.3 EMBED Equation.3 .
bj 20 34 16 10 25
ai
3. С = EMBED Equation.3 EMBED Equation.3 .
bj 40 30 30 50
ai
4. С = EMBED Equation.3 EMBED Equation.3 .
bj 35 20 55 30
ai
5. С = EMBED Equation.3 EMBED Equation.3 .
bj 140 130 90 140
ai
6. С = EMBED Equation.3 EMBED Equation.3 .
bj 40 30 35 15
ai
7. С = EMBED Equation.3 EMBED Equation.3 .
bj 45 35 30 60
ai
8. С = EMBED Equation.3 EMBED Equation.3 .
bj 30 25 18 20
ai
9. С = EMBED Equation.3 EMBED Equation.3 .
bj 40 60 70 25
ai
10. С = EMBED Equation.3 EMBED Equation.3 .
bj 15 40 30 15
ai
11. С = EMBED Equation.3 EMBED Equation.3 .
bj 30 25 35 20
ai
12. С = EMBED Equation.3 EMBED Equation.3 .
bj 25 34 46 20 25
ai
13. С = EMBED Equation.3 EMBED Equation.3 .
bj 110 50 30 80 100 90
ai
14. С = EMBED Equation.3 EMBED Equation.3 .
bj 2 3 3 16
ai
15. С = EMBED Equation.3 EMBED Equation.3 .
bj 70 5 45 70
ai
16. С = EMBED Equation.3 EMBED Equation.3 .
bj 16 18 12 15
ai
17. С = EMBED Equation.3 EMBED Equation.3 .
bj 25 30 40 15
ai
18. С = EMBED Equation.3 EMBED Equation.3 .
bj 20 60 55 45
ai
19. С = EMBED Equation.3 EMBED Equation.3 .
bj 20 18 44 75
ai
20. С = EMBED Equation.3 EMBED Equation.3 .
bj 10 40 20 60
ai
21. С = EMBED Equation.3 EMBED Equation.3 .
bj 35 80 25 70
ai
22. С = EMBED Equation.3 EMBED Equation.3 .
bj 25 30 40 15
ai
23. С = EMBED Equation.3 EMBED Equation.3 .
bj 110 30 30 70 110 90
СПИСОК ЛІТЕРАТУРИ
1. Долженков В.А., Колесников Ю.В. Microsoft Excel 2000. – СПб.: БХВ-Петербург, 2001. – 1088с.: ил.
2. Кудрявцев Е.М. Mathcad 2000 Pro. – М.: ДМК Пресс, 2001. – 576с.: ил.
3. Таха Хэмди А. Введение в исследование операций, 6-е издание: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912с.: ил.
МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Методичні вказівки до лабораторної роботи № 5,6
"Транспортна задача. Метод потенціалів"
з дисципліни
“Математичні методи дослідження операцій”
для студентів спеціальності 6.08.04 “Комп’ютерні науки”
Укладач: Дронюк Іванна Мирославівна, доцент, к.ф.-м.н.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора