Мурманський філія Петровського Коледжу
Курсова з дисципліни
«Комп'ютерне моделювання» на тему
«Транспортна задача»
Виконав: Ошкін Е.С.
Перевірив: Сергєєв А.В.
Мурманськ
2002р.
Опис Алгоритму програми
ПРОГРАМА НАПИСАНА НА BORLAND С + + версії 3.1
Програма вирішує Транспортну Завдання (ТЗ) 3 методами:
1. Північно-західним кутом
2. Північно-східним кутом
3. Методом мінімального елемента в рядку.
Програма складається з функцій:
1. Main ()
2. Data ()
3. Opplan ()
4. Sohran ()
5. Bas ()
6. Kost ()
7. Potenzial ()
8. Optim ()
9. Plmi ()
10. Abcikl ()
11. Cikl ()
12. Prpoisk ()
13. Levpoisk ()
14. Verpoisk ()
15. Nizpoisk ()
16. Pr ()
Головна функція main () невелика, але в ній відбувається обігфункцій, які виконують певні дії в процесі рішення ТЗ. Тутслід звернути особливу увагу на рядок програми if (! z) break; - якщоб не вона (вона показує, що після чергової перевірки базисного плану,якщо він оптимальний, що повертає значення з функції optim () дорівнює 0, щопризводить до виходу з нескінченного циклу поліпшення базисних планів). Інодівиникає ситуація, коли базисна змінна (один або декілька) дорівнюєнулю, і її слід відрізняти від інших базисних змінних. У матриці matr ()такі елементи я позначив як -2. Основні змінні я описав укоментарях в програмі.
Функція data () виробляє введення даних на ТЗ.
Функція opplan () виконує завдання зі складання початковогобазисного плану методом північно-Західно кута. У цій функції використовуютьсянаступні змінні:
Int * matr покажчик на матрицю базисних змінних
Int * po покажчик на вектор пунктів відправлення
Int * pn покажчик на вектор пунктів призначення
Int m кількість пунктів відправлення
Int n кількість пунктів призначення
Функція kost () робить висновок сумарної вартості перевезень попоточному базисного плану. Використовуються такі змінні:
Int * matr, m, n;
Int * st покажчик на матрицю вартостей.
Функція potenzial () виконує підрахунок потенціалів.
Використовує наступні змінні:
Int * pu покажчик на вектор потенціалів строк
Int * pv покажчик на вектор потенціалів стовпців
Int matr, m, n, * st;
Спочатку елементи векторів потенціалів * (pu + i) і * (pv + j)заповнюються мінімальними значеннями для цілих змінних = 32768,певних предпроцессорним оператором define MIN - 32768. Далі полога,що * pu = 0, і використовуючи структуру struct poten (...), елементи векторівпотенціалів набувають свої реальні значення.
Роботу цього модуля можна розділити на ці етапи:
. Виділення пам'яті під елемент структури top = (struct poten *) malloc (sizeof (struct poten)); заповнення полів елемента структури необхідною інформацією; встановлення зв'язків між елементами структури;
. Обчислення потенціалів рядків і стовпців з занесенням інформації в сектори pu і pv;
. Перевірка правильності заповнення векторів pu і pv, тобто встановлення не містять чи елементи цих векторів значення MIN. При необхідності, якщо існують такі елементи векторів, проводяться додаткові обчислення;
. Висновок векторів pu і pv;
Функція optim () перевіряє план на оптимальність, якщо він оптимальний,то функція відправляє в головну функцію main () значення 0, у противномувипадку, якщо він не оптимальний, то управління передається функції abcikl () іповернення головної функції main () значення -1. Функція optim () використовуєзмінні:
Int m, n, * pu, * pv, * matr, * st. Ланцюг будується щодо першій-ліпшійграфоклеткі, для якої ui + vj = cij, а не відносної характеристики.
У ході рішення ТЗ проміжні базисні плани відрізняються від тих, які япобудував, починаючи з координат графоклеткі з мінімальним значеннямнегативної характеристики, але врезультате оптимальний план буде той самий.
Функція abcicl () - використовує наступні змінні
Int * matr, m, n;
Int * matr2// покажчик на робочу (змінну) матрицю, по початку вонає копією оригінальною.
Int ik, jk;// координати графоклеткі, з якої починає будуватися ланцюг. Уцієї функції присвоюється графоклеткі, з якою буде відбуватися пошукциклу (ланцюг), значення -1.
Функція cikl () здійснює пошук щодо графоклеткі зі значенням
-1. Вона використовує наступні змінні:
Int * matr2, ik, jk;
Int ch;// лічильник кількості елементів у масивах * zi і * zj
Int * zi, * zj// покажчики на масиви індексів. Зберігають індекси елементівmatr, що підлягають перерозподілу.
Опції prpoisk (), levpoisk (), verpoisk (), nizpoisk ()-пошук,відповідно, вправо, вліво, вгору, вниз - щодо поточноїграфоклеткі. Пошук відбувається в масиві * matr2. Якщо ви знаєте рядок, товиконується пошук стовпця, тобто його індексу, якщо відомий стовпець-шукаєтьсярядок.
Дані функції повертають координати стовпця або рядка знайденоїграфоклеткі, або значення -1, якщо графоклетка в даному напрямку незнайдених.
Робота модуля cikl () полягає в наступному:
. Пошук потрібного елемента починається щодо графоклеткі з позначкою -1 в матриці matr2 (з координатами ik і jk згідно з вхідними даними) у можливих напрямках (по черзі);
. Якщо пошук успішний, то поля структури заповнюються інформацією, знайдений елемент структури включається до списку (роботу модуля підтримує лінійний список, в якому зберігається інформація про хід пошуку ланцюга), і за основу береться вже ця (поточна) графоклетка матриці matr2 (). Далі процедура пошуку повторюється:
. Якщо пошук на якомусь кроку не неуспешен по можливих напрямках, то знайдений елемент виключається зі списку і за основу береться останній елемент списку (після видалення). У робочій матриці matr2 () «обнуляється» елемент з координатами, який зберігав виключений елемент, що необхідно для того, щоб виключити повторне звернення до елемента matr2, не входящемму в ланцюг;
. Пошук циклу (ланцюга) буде закінчений, коли при проходженні по будь-якому напрямку ми знову наткнемося на елемент матриці matr2 зі значенням -1.
В кінці модуля елементи списку, тобто його поля з координатами, переписуються в вектори zi і zj.
Зовнішні змінні:
Int m, n, * matr2;
Вхідні дані:
Int i1, j1// координати поточної графоклеткі, щодо якоїбудується ланцюг.
Вихідні дані:
I (j) - координати рядка, стовпця, якщо мінлива знайдена;
Функція pr (), здійснює друк текстових повідомлень про хід пошуку вматриці; вона викликається з модуля cikl ().
Функція plmi () перерозподіляє поставки по ланцюгу, тобто покращує план.
Використовуються такі змінні:
Int zi, zj;
Int ch, chr;/змінні розмірності масивів zi, zj
Int matr/покажчик на матрицю базисних змінних
Робота з модулями виконується у декілька етапів. Якщо є нульовоюбазисний елемент (позначений як -2 в матриці matr) і індекс k Нечет длявекторів zi, zj, то елементи matr, помічені, як -1 і -2 (новий елементпозначений як -2 Обнуляємо), міняються місцями, в іншому випадку (якщо kпарна або немає нульових базисних елементів у matr) здійснюється:
Знаходження мінімального елемента в матриці базисних змінних:min = matr [i] [j], де i = zi [k]; j = zj [k]; k-непарне число;
Перерозподіл поставок: a) якщо k парне число, то matr [ i] [j] = matr [i] [j] + min, деi = zi [k]; j = zj [k]; b) якщо k непарне число, то matr [i] [j] = matr [i] [j]-min, деi = zi [k]; j = zj [k];
Модуль bas () підраховує кількість ненульових базисних змінних вматриці matr.
Модуль sohran () знаходить нульову базисну змінну в matr івстановлює її в -2.
Int basper;/кількість базисних змінних.
Функція opplan1 () побудова початкового плану методом північно -східного кута, а opplan2 () - методом вибору найменшого елемента в рядку.
Нижче наведено текст програми
# include// Підключення стандартних
# include// Бібліотек
# include
# include
# include
# define MIN -32768
int * po = NULL;// Покажчик на масив пунктів відправлення int * pn = NULL;// Покажчик на масив пунктів призначення int * st = NULL;// Покажчик на матрицю вартостей int * matr = NULL;// Покажчик на матрицю базисних змінних int * matr2 = NULL;// Покажчик на робочу матрицю int n, m;// Розмірність завдання int * pu, * pv;// Покажчики на масиви потенціалів int * zj , * zi;// Покажчик на масиви індексів int ch = 0, ch2 = 0;// Лічильники
FILE * fpdat;// Покажчик на вступної файл int iter = 0;// Счетчик ітерації
FILE * fil ;// Покажчик на вивідний файл int zen = -1;// Змінна для збереження вартості п-на int z = 1;// Прапор для виходу при оптимальному плані int basper;
// void exit ( int status);
void data (void)
(int i, j, t; printf ( "Введіть кількість складів:"); scanf ( "% d", & m) ; printf ( "Kolichestvo skladov ----->% d", m); printf ( "n Введіть кількість магазинів: n"); scanf ( "% d", & n); printf ( "n Kolichestvo magazinov --- >% d ", n);
//*********** Виділення пам'яті ****************** if ( (po = (int *) calloc (m, sizeof (int )))== NULL) abort (); if ((pn = (int *) calloc (n, sizeof (int )))== NULL) abort ( ); if ((st = (int *) calloc (n * m, sizeof (int )))== NULL) abort ();
printf ( "Введіть елементи матриці вартостей: n"); for (i = 0; iu)) = (top1-> b) - * (pv + j); i = (top1-> u); top1 -> zn = 0; break;
)
)
)
)
// ********** Продовження функції підрахунку потенціалів ******* **********
for (;;){ fl = 0; for (top = topnast; top! = NULL; top = top -> next) < p> (if ((top -> zn) == -1)
(if (* (pu + (top -> u))! = MIN)
(
* (pv + (top-> v)) = (top-> b) - * (pu + (top -> u)); fl = 1; top -> zn = 0; < p>) if (* (pv + (top-> v))! = MIN)
(
* (pu + (top-> u)) = (top-> b ) - * (pv + (top-> v)); fl = 1; top-> zn = 0;
)
)
) if ( ! fl) break;
) printf ( "n потенціалом по v:"); fprintf (fil, "n **** потенціалом по v:"); for (i = 0; ijck = jk ; ch + +; fprintf (fil, "nnДо Умови while fl3 =% dn", fl3); pr ( "top2", top2); fprintf (fil, "Весь цикл пошуку зараз почнеться, сподіваюся -
n що він буде не нескінченний або не даремний: (n "); printf (" Весь цикл пошуку зараз почнеться, сподіваюся - nщо він буде не нескінченний або не даремний: (n "); printf (" nt ttpress anykey to contunion "); getch (); while (fl3)
(fl3 = 0; fl = 0; if ((nst = prpoisk (ik, jk))> = 0)
(fprintf (fil, "nnВніманіе! n nst =% dn", nst); fprintf (fil, "Ща буде поік йти йому б ...: Pointfound! n "); printf (" І він пішов RIGHT: Point found! nr "); napr = 2; jk = nst; top2-> prnapr = 1;
) else if ((nstr = nizpoisk (ik, jk))> = 0)
(fprintf (fil, "DOWN: Point found! n"); printf ( "DOWN: Point found! nr"); napr = 3; ik = nstr; top2-> prnapr = 2;
)
else if ((nst = levpoisk (ik, jk))> = 0)
( fprintf (fil, "LEFT: Point found! n"); printf ( "LEFT: Point found! nr"); napr = 4; jk = nst; top2-> prnapr = 3;
)
// **************** Prodolzhenie 1 poiska *********************** else if ((nstr = verpoisk (ik, jk))> = 0)
(fprintf (fil, "UP: Point found! n"); printf ( "UP: Point found! nr") ; napr = 1; ik = nstr; top2-> prnapr = 4;
) else return (-1);
while (! fl | | * (matr2 + ik * n + jk)! =- 1)
(fl = 1; switch (napr)
(case 1: printf ( "Search to the right --->"); fprintf (fil, "Search to the right --->"); if ((nst = prpoisk (ik, jk))> = 0)
(printf (" foundednr "); fprintf (fil , "foundedn"); if ((top2 = (structcik *) malloc (sizeof (struct cik )))== NULL) abort (); if (! topnast1) topnast1 = top2; else top3 -> next = top2; top3 = top2; top2 -> next = NULL; top2 - > ick = ik; top2-> jck = jk; ch + +; top2-> prnapr = 1; pr ( "top2", top2); napr = 2; jk = nst; perpr = perlev = 0;
)// **** IF ******* else
(fprintf (fil, "Point not found! Changedirection to LEFTn "); napr = 3; perpr = 1;
) break;
//***************** PRODOLZHENIE 2 POISKA
****************************** Case 2: printf ( "Search to the down --->"); fprintf (fil , "Search to the down --->"); if ((nstr = nizpoisk (ik, jk))> = 0)
(if ((top2 = (struct cik *) malloc (sizeof (struct cik))) ==
NULL) abort (); printf ( "foundednr"); fprintf (fil, "foundedn"); if (! Topnast1) topnast1 = top2; else top3-> next = top2; top3 = top2; top2-> next = NULL; top2-> ick = ik; top2-> jck = jk; ch + +; top2-> prnapr = 2; pr ( "top2", top2); napr = 3; ik = nstr; perniz = perver = 0;
) //**** IF ******** else
(fprintf (fil, "Point not found! Changedirection to UPn "); napr = 4; perniz = 1;
) break;
case 3: printf (" Search to the left -->"); fprintf (fil , "Search to the left -->"); if ((nst = levpoisk (ik, jk))> = 0)
(if ((top2 = (structcik *) malloc (sizeof (struct cik))) == NULL) abort (); printf ( "foundednr");fprintf (fil, "foundedn"); if (! topnast1) topnast1 = top2; else top3-> next = top2; top3 = top2; top2-> next = NULL; top2-> ick = ik; top2-> jck = jk ; ch ++;
//************ PRODOLZHENIE 3 POISKA ************* top2-> prnapr = 3; pr ( " top2 ", top2); napr = 4; jk = nst; perlev = perpr = 0;
)// ******* IF ***** else (fprintf (fil," Point not found! Changedirection to RIGHTn "); napr = 1; perlev = 1;
) break; case 4: printf (" Search to the up --->"); fprintf (fil, "Search to the up --->"); if ((nstr = verpoisk (ik, jk))> = 0)
(if ((top2 = (struct cik *) malloc (sizeof (structcik )))== NULL) abort (); printf ( "foundednr"); fprintf (fil, "foundedn"); if (! topnast1) topnast1 = top2; else top3-> next = top2; top3 = top2; top2 -> next = NULL; top2-> ick = ik; top2-> jck = jk; ch + +; top2-> prnapr = 4; pr ( "top2", top2); napr = 1; ik = nstr; perver = perniz = 0;
)// ***** If ************** else
(fprintf (fil, "Point not found! Change direction to
DOWNn "); napr = 2; perver = 1;
) break;
)// ************ SWITCH ***** ***************
// ************** PRODOLZHENIE 4 POISKA ********* *********** if (perlev == 1 & & perpr == 1)
(
* (matr2 + ik * n + jk) = 0 ; ik = top3 -> ick; jk = top3 -> jck; napr = top3-> prnapr; top3 = topnast1; printf ( "Zerro 1nr ");
for (top2 = topnast1; top2-> next! = NULL; top2 = top2-> next) top3 = top2; top3 -> next = NULL; perlev = perpr = 0;// if (ch == 1) if (top2 == top3) < p> (fl3 = 1; break;
) else
(top3-> next = NULL; free (top2); ch -; printf ( "Viynimaem tochky:
(% d,% d) =% dn ", ik, jk, * (matr2 + ik * n + jk)); fprintf (fil," Viynimaem tochky:
(% d,% d) =% dn ", ik, jk, * (matr2 + ik * n + jk)); pr (" top2 ", top2);
) perpr = 0; perlev = 0;
)// IF
if (perver == 1 & & perniz == 1)
(
* ( matr2 + ik * n + jk) = 0; printf ( "Zerro 2nr"); ik = top3-> ick; jk = top3-> jck; napr = top3-> prnapr; top3 = topnast1;
for (top2 = topnast1; top2-> next! = NULL; top2 = top2-
> next) top3 = top2; perver = perniz = 0; if (top2 == top3)
(fl3 = 1; break;
) else
(top3-> next = NULL; free (top2); ch -;
// ******* PRODOLZHENIE 5 POISKA ************** ******* printf ( "Viynimaem tochky: (% d,% d) =
% dn ", ik, jk, * (matr2 + ik * n + jk)); fprintf (fil," Viynimaem tochky: (% d,% d) =
% dn ", ik, jk, * (matr2 + ik * n + jk ));
pr (" top2 ", top2);
) perver = 0; perniz = 0;
)// IF if (ch == 0)
(fl3 = 1; break;
)
)// while
)// while i = 0; if ((zi = (int *) calloc (ch, sizeof (int))) == NULL) abort (); if ((zj = (int *) calloc (ch, sizeof (int))) == NULL) abort (); printf ( "nr"); ch2 = ch; for (top2 = topnast1; top2! = NULL; top2 = top2-> next )
(
* (zi + i) = top2 -> ick;
* (zj + i) = top2 -> jck; i + +;
)
return (0);
)// *********** cikl ********* *******************
int prpoisk (int i1, int j1)
(int j;
for (j = j1 1; j = 0; j -)
(if ((* (matr2 + i1 * n + j))! = 0) return (j);
) return (-1);
) int verpoisk (int i1, int j1)
(int i;
for (i = i1-1; i> = 0; i -)
(if ((* (matr2 + i * n + j1))! = 0) return (i);
) return (-1);
)
int nizpoisk (int i1, int j1)
(int i; for (i = i1 1; iick, ptr-> jck); printf ( "Koordinatiy ytoplennoy tochki:% d and% dnr", ptr-
> ick, ptr-> jck); fprintf (fil, "and napravlenie"); printf ( "Napravlenie"); switch (ptr-> prnapr)
(case 1: fprintf (fil, "Vpravon "); printf (" Vpravonr "); break; case 2: fprintf (fil," Vnizn "); printf (" Vniznr "); break; case 3: fprintf (fil," Vlevon "); printf (" Vlevonr " ); break; case 4: fprintf (fil, "Vverhn"); printf ( "Vverhnr"); break; default: fprintf (fil, "Startn"); printf ( "Startnr"); break; < p>) fprintf (fil, "WORK MATRIXn"); for (i = 0; i
