Транспортна задача. Метод потенціалів. Лабораторна робота з Математичні методи дослідження операцій. Робота № 516970

Транспортна задача. Метод потенціалів

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра автоматизованих систем управління

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

Рік:

2012

Тип роботи:

Лабораторна робота

Предмет:

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

Група:

КН

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління / Лабораторна робота №7-8 з дисципліни “Математичні методи дослідження операцій” на тему « Транспортна задача. Метод потенціалів» Львів – 2012 Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми. План Короткі теоретичні відомості. Постановка задачі Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів. Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів. Знайти базове рішення відкритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів. Розв’язання за допомогою пакету програм MS Exel. Розв’язання за допомогою пакету програм Optimal 1_4 Розв’язання за допомогою власної програми. Хід роботи 1. Короткі теоретичні відомості Постановка транспортної задачі В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n. Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами. Умови Т-задачі записуються у вигляді ai С = bj b1 b2 b3 … bn Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ). Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію L = , з виконанням умов Матрицю Х = називають планом перевезень Т-задачі. Визначення початкового опорного плану. Метод «північно-західного кута» (ПЗК). Визначаємо елементи матриці Х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. Будується початковий опорний план Х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 – оптимальний, інакше перехід до наступної ітерації. 2. Постановка задачі Номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100. Варіант 32 32. С = bj 30 25 15 20 2.1 Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів. Математична модель транспортної задачі: F = ΣΣc ij x ij, (1) за умов: Σx ij = a i, i = 1,2, ..., m, (2) Σx ij = b j, j = 1,2, ..., n, (3) Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів 1 2 3 4 Запаси 1 1 2 6 4 40 2 3 1 3 2 30 3 5 7 5 1 20 Потреби 30 25 15 20 Перевіримо необхідна і достатня умова розв'язання задачі. Σa = 40 + 30 + 20 = 90 Σb = 30 + 25 + 15 + 20 = 90 Занесемо вихідні дані в розподільну таблицю. 1 2 3 4 Запаси 1 1 2 6 4 40 2 3 1 3 2 30 3 5 7 5 1 20 Потреби 30 25 15 20 Етап I. Пошук першого опорного плану. 1. Використовуючи метод північно-західного кута, побудуємо перший опорний план транспортної задачі. 1 2 3 4 Запаси 1 1 [30] 2 [10] 6 4 40 2 3 1 [15] 3 [15] 2 30 3 5 7 5 1 [20] 20 Потреби 30 25 15 20 2. Підрахуємо число зайнятих клітин таблиці, їх 5, а має бути m + n - 1 = 6. Отже, опорний план є виродженим. Будуємо новий план. Значення цільової функції для цього опорного плану одно: 1 2 3 4 Запаси 1 1 [15] 2 [25] 6 4 40 2 3 [15] 1 3 [15] 2 30 3 5 7 5 1 [20] 20 Потреби 30 25 15 20 2. Підрахуємо число зайнятих клітин таблиці, їх 5, а має бути m + n - 1 = 6. Отже, опорний план є виродженим. Будуємо новий план. Значення цільової функції для цього опорного плану одно: 1 2 3 4 Запаси 1 1 [25] 2 6 [15] 4 40 2 3 [5] 1 [25] 3 2 30 3 5 7 5 1 [20] 20 Потреби 30 25 15 20 2. Підрахуємо число зайнятих клітин таблиці, їх 5, а має бути m + n - 1 = 6. Отже, опорний план є виродженим. Будуємо новий план. Значення цільової функції для цього опорного плану одно: 1 2 3 4 Запаси 1 1 [20] 2 6 4 [20] 40 2 3 [10] 1 [20] 3 2 30 3 5 7 [5] 5 [15] 1 20 Потреби 30 25 15 20 В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі. 2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m + n - 1 = 6. Отже, опорний план є невиродженим. Значення цільової функції для цього опорного плану одно: Етап II. Поліпшення опорного плану. Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали u i, v i. по зайнятих клітинам таблиці, в яких u i + v i = c ij, вважаючи, що u 1 = 0. v 1 = 1 v 2 = -1 v 3 = -3 v 4 = 4 u 1 = 0 1 [20] 2 6 4 [20] u 2 = 2 3 [10] 1 [20] 3 2 u 3 = 8 5 7 [5] 5 [15] 1 Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких u i + v i> c ij Вибираємо максимальну оцінку вільної клітини (3, 4): 1 Для цього в перспективну клітку (3, 4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». 1 2 3 4 Запаси 1 1 [20] [+] 2 6 4 [20] [-] 40 2 3 [10] [-] 1 [20] [+] 3 2 30 3 5 7 [5] [-] 5 [15] 1 [+] 20 Потреби 30 25 15 20 Цикл наведено в таблиці (3,4; 3,2; 2,2; 2,1; 1,1; 1,4;). З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 5. Додаємо 5 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 5 з Х ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. 1 2 3 4 Запаси 1 1 [25] 2 6 4 [15] 40 2 3 [5] 1 [25] 3 2 30 3 5 7 5 [15] 1 [5] 20 Потреби 30 25 15 20 Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали u i, v i. по зайнятих клітинам таблиці, в яких u i + v i = c ij, вважаючи, що u 1 = 0. v 1 = 1 v 2 = -1 v 3 = 8 v 4 = 4 u 1 = 0 1 [25] 2 6 4 [15] u 2 = 2 3 [5] 1 [25] 3 2 u 3 = -3 5 7 5 [15] 1 [5] Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких u i + v i> c ij Вибираємо максимальну оцінку вільної клітини (2, 3): 3 Для цього в перспективну клітку (2, 3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». 1 2 3 4 Запаси 1 1 [25] [+] 2 6 4 [15] [-] 40 2 3 [5] [-] 1 [25] 3 [+] 2 30 3 5 7 5 [15] [-] 1 [5] [+] 20 Потреби 30 25 15 20 Цикл наведено в таблиці (2,3; 2,1; 1,1; 1,4; 3,4; 3,3;). З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 1) = 5. Додаємо 5 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 5 з Х ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. 1 2 3 4 Запаси 1 1 [30] 2 6 4 [10] 40 2 3 1 [25] 3 [5] 2 30 3 5 7 5 [10] 1 [10] 20 Потреби 30 25 15 20 Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали u i, v i. по зайнятих клітинам таблиці, в яких u i + v i = c ij, вважаючи, що u 1 = 0. v 1 = 1 v 2 = 6 v 3 = 8 v 4 = 4 u 1 = 0 1 [30] 2 6 4 [10] u 2 = -5 3 1 [25] 3 [5] 2 u 3 = -3 5 7 5 [10] 1 [10] Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких u i + v i> c ij Вибираємо максимальну оцінку вільної клітини (1, 2): 2 Для цього в перспективну клітку (1, 2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». 1 2 3 4 Запаси 1 1 [30] 2 [+] 6 4 [10] [-] 40 2 3 1 [25] [-] 3 [5] [+] 2 30 3 5 7 5 [10] [-] 1 [10] [+] 20 Потреби 30 25 15 20 Цикл наведено в таблиці (1,2; 1,4; 3,4; 3,3; 2,3; 2,2;). З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 4) = 10. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Х ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. 1 2 3 4 Запаси 1 1 [30] 2 [10] 6 4 40 2 3 1 [15] 3 [15] 2 30 3 5 7 5 [0] 1 [20] 20 Потреби 30 25 15 20 Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали u i, v i. по зайнятих клітинам таблиці, в яких u i + v i = c ij, вважаючи, що u 1 = 0. v 1 = 1 v 2 = 2 v 3 = 4 v 4 = 0 u 1 = 0 1 [30] 2 [10] 6 4 u 2 = -1 3 1 [15] 3 [15] 2 u 3 = 1 5 7 5 [0] 1 [20] Опорний план є оптимальним, тому всі оцінки вільних клітин задовольняють умові u i + v i <= c ij. Мінімальні витрати складуть: F (x) = 1 * 30 + 2 * 10 + 1 * 15 + 3 * 15 + 1 * 20 = 130 3. Розв’язання з допомогою пакету програм MS Exel Для того щоб отримати розв’язок необхідно зробити наступні дії : 4. Розв’язання з допомогою пакету програм Optimal 1_4 Ввід даних : / Знаходження опорного плану / Кінцевий результат виконання для двох підходів методу потенціалів. / Ввід даних для методу потенціалів відкритої ТЗ. / Результат : / 5 Розв’язання за допомогою власної програми Код програми мовою С++ (Visual studio) #include <iostream> #include <iomanip> #include <conio.h> #include <time.h> using namespace std; const int MAX = 100; struct destination { char name[20]; int need; int copy_need; int has; int tariff[MAX]; int extra; } receive[MAX]; struct transportation { char name[20]; int recource; } starr[MAX]; int enter_numberOf( int *a, int *b ) { printf("Vvedit kilkist postachalnykiv : "); scanf("%d",&*a); printf("Vvedit kilkist spozhyvachiv : "); scanf("%d",&*b); return *a, *b; } int main() { int number_of_corporations; int number_of_destinations; enter_numberOf(&number_of_corporations, &number_of_destinations); int total_has =0, total_need = 0; int focus = 0; int S = 0; int i,j; printf("Vvedit dani : \n"); for ( i = 0; i < number_of_corporations; i++ ) { printf("Vvedit nazvu %d postachalnyka:\n", i + 1); scanf("%s",&starr[i].name); printf("Kilkist resursiv:\n -> "); scanf("%d",&starr[i].recource); total_has += starr[i].recource; } printf("Vvedit dani pro punkty pryznachennja:\n"); for ( i = 0; i < number_of_destinations; i++ ) { printf("Punkt pryznachennja %d. Vvedit nazvu \n", i + 1); scanf("%s",&receive[i].name); printf("Skilky odynycj tovaru potribno \n"); scanf("%d",&receive[i].need); total_need += receive[i].need; receive[i].copy_need = receive[i].need; receive[i].has = 0; for ( j = 0; j < number_of_corporations; j++ ) { printf("\tVvedit taryf dlja %s Corp.\n",starr[j].name); scanf("%d",&receive[i].tariff[j]); } } if ( total_has < total_need ) { printf("Vsioho resursiv : %d , neobhidno : %d ",total_has,total_need); printf("Nedostatnio resursiv.\n"); printf("continue? (y/n) "); int choice = getch(); if ( choice == 'n' || choice != ('y') ) return NULL; } system("cls"); for ( i = 0; i < number_of_destinations; i++ ) { printf("%-15s",receive[i].name); } printf("\nPotribno:"); for ( i = 0; i < number_of_destinations; i++ ) { printf("%-15d",receive[i].need); } int k = 0; focus = k; printf("\nVyrishennja:\n"); total_has = 0; for ( i = 0; i < number_of_corporations; i++ ) { if ( focus == k ) printf("\nTovary z pidpryjemstva \"%s\" budutj dostavljatysj do ",starr[i].name); if ( starr[i].recource != 0 ) { if ( receive[k].has != receive[k].copy_need ) { if ( receive[k].need < starr[i].recource ) { int tmp; tmp = receive[k].need; receive[k].has += tmp; receive[k].need -= tmp; starr[i].recource -= tmp; printf("%s (%d); ",receive[k].name,tmp); focus = k; S += receive[k].tariff[i] * tmp; if ( receive[k].has == receive[k].copy_need ) { k++; } if ( starr[i].recource != 0 ) i--; } else if ( receive[k].need >= starr[i].recource ) { int tmp; tmp = starr[i].recource; receive[k].has += tmp; receive[k].need -= tmp; starr[i].recource -=tmp; printf("%s (%d); ",receive[k].name,tmp); focus = k; S += receive[k].tariff[i] * tmp; if ( receive[k].has == receive[k].copy_need ) { k++; } } } else k++; } total_has = 0; for ( int number = 0; number < number_of_corporations; number++ ) total_has += starr[i].recource; if ( i == number_of_corporations-1 && total_has == NULL ) { printf("\nNedostatno resursiv dlja "); for ( int number1 = k; number1 < number_of_destinations; number1++ ) printf("%s; ",receive[number1].name); } } printf("\n"); int S_add = 0; srand(time(NULL)); int extra_resources = 0; for ( i = 0; i < number_of_corporations; i++ ) extra_resources += starr[i].recource; if ( extra_resources ) { printf("\nZalyshylys resursy tomu vvodymo \ndodatkovoho korystuvacha Microsoft Corporation\n"); receive[number_of_destinations].has = 0; printf("Taryf mikrosoft для\n"); for ( i = 0; i < number_of_corporations; i++ ) { receive[number_of_destinations].tariff[i] = 1 + rand()%20; printf("\t-> %s stanowytyme %d\n",starr[i].name,receive[number_of_destinations].tariff[i]); receive[number_of_destinations].has += starr[i].recource; S_add += starr[i].recource * receive[number_of_destinations].tariff[i]; starr[i].recource -= starr[i].recource; } } printf("Vytraty na dostavku do osnovnyh %d punktiv pryznachennja stanovytyme :\n\t-> %d у.е\n",number_of_corporations,S); if ( S_add != NULL ) printf("Zalyshkovi resursy (%d) budut vidpravleni Microsoft , sho stanovytyme :\n\t-> %d у.е\n",receive[number_of_destinations].has,S_add); printf("\n"); getch(); return 0; } / / Висновок: виконуючи цю лабораторну роботу я набув навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми.

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

savruksergiy

04.05.2012 18:42

Коментарі

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

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

поділитись