Транспортне завдання

Мурманський філія Петровського Колледжа.

Курсова по дисциплине.

«Комп'ютерне моделювання» на тему.

«Транспортна задача».

Виконав: Ошкин Е.С.

Перевірив: Сергєєв А.В.

Мурманск.

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) заповнюються мінімальними значеннями для цілих змінних = 32 768, певних предпроцессорным оператором define MIN — 32 768. Далі положиста, що *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 -32 768.

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); і = (top1->u); top1 ->zn = 0; break;

}.

}.

}.

} // ********** Продовження функції підрахунку потенціалів *****************.

for (;;){ fl = 0; for (top = topnast;top≠NULL;top =top -> next).

{ if ((top -> zn) == -1).

{ if (*(pu+(top ->u)) ≠MIN).

{.

*(pv+(top->v))=(top->b) — *(pu+(top ->u)); fl = 1; top -> zn = 0;

} 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 =%d n », fl3); pr («top2 », top2); fprintf (fil, «Весь цикл пошуку почнеться, сподіваюся — n що він не нескінченний або некорисний :(n »); printf («Весь цикл пошуку почнеться, сподіваюся — n що він не нескінченний або некорисний :(n »); printf («n t ttpress anykey to contunion »); getch (); while (fl3).

{ fl3=0; fl = 0; if ((nst = prpoisk (ik, jk))>=0).

{ fprintf (fil, «nnВнимание!!!n nst = %d n », nst); fprintf (fil, «Зара буде поик йти йому бы…:Point found! 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=(struct cik*)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 ! Change direction 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 ! Change direction 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=(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++;

//************ PRODOLZHENIE 3 POISKA ************* top2->prnapr = 3; pr («top2 », top2); napr = 4; jk = nst; perlev = perpr = 0;

} // ******* IF ***** else{ fprintf (fil, «Point not found ! Change direction 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 (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 = 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).

{ 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 і; 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;

} fprintf (fil, «WORK MATRIXn »); for (i=0;i.