Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Транспортна задача. Метод потенціалів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №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, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми.
04.05.2012 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора