Мурманский филиал Петровского Колледжа
Курсовая
по дисциплине
«Компьютерное моделирование»
на тему
«Транспортная задача»Выполнил: Ошкин Е.С.
Проверил: Сергеев А.В.Мурманск
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 <stdio.h> //Подключение стандартных
#include <alloc.h> // Библиотек
#include <conio.h>
#include <process.h>
#include <stdlib.h>
#define MIN -32768int *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(«
Введите количество магазинов:
«);
scanf(«%d»,&n);
printf(«
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(«Введите элементы матрицы стоимостей:
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(«Введите [%d][%d]
«,i,j);
scanf(«%d»,&t);
*(st+i*n+j)=t;}
}
printf(«
«);
fprintf(fil,»
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(«%5d»,*(st+i*n+j));
fprintf(fil,»%5d»,*(st+i*n+j));
}
printf(«
«);
fprintf(fil,»
«);
}
printf(«Введите количество запасов на каждом
складе:
«);
for(i=0;i<m;i++)
{
printf(«
«);
scanf(«%d»,po+i);
printf(«%5d»,*(po+i));
}
printf(«
«);
printf(«Введите потребности:
«);
for(j=0;j<n;j++)
{
printf(«
«);
scanf(«%d»,pn+j);
printf(«%5d»,*(pn+j));
}
return;
}//**** data//************* SOZDANIE OPORNOGO PLANA ********************
//************* METHOD NORD-WEST YGLA **********************
void opplan(void)
{
int i,j,ch1 = 0;
//*************** ВЫДЕЛЕНИЕ ПАМЯТИ *************************
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();// ЦИКЛ ПРОСТОГО РАСПРЕДЕЛЕНИЯ ПОТРЕБНОСТЕЙ по ячейкам рабочей матрицы
for(i=0;i<m;i++)
{
for(j=ch1;j<n;j++)
{
if(*(po+i)<*(pn+j))
{
*(matr+i*n+j)=*(po+i);
*(pn+j)-=*(po+i);
*(po+i)=0;
break;
}
*(matr+i*n+j)=*(pn+j);
*(po+i) -= *(pn+j);
*(pn+j)=0;
ch1++;
}
}
//********* ПРОВЕРКА И ВЫвод получившейся матрицы ***********************
printf(«PROVERKA
«);
fprintf(fil,»PROVERKA MATRIX — Северо заподный УГОЛ,просмотр получившегося распределения в матрице
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(«%5d»,*(matr+i*n+j));
fprintf(fil,»%d»,*(matr+i*n+j));
}
printf(«
«);
fprintf(fil,»
«);
}
fprintf(fil,»********************
«);
return;
} // opplanvoid kost(void)
{
int i,j, *matr1,rez=0;
//выделение памяти
if((matr1=(int*)calloc(n*m,sizeof(int))) == NULL)
abort();
//присвоение новой матрице значения базисной(старой)
матрицы
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
*(matr1+i*n+j) = *(matr+i*n+j);
}
}// Подсчет стоимости базисной матрицы (созданного
массива)
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr1+i*n+j)>0)
rez += (*(matr1+i*n+j))
*(*(st+i*n+j));
}
}
printf(«
Rezultat : %d»,rez);
printf(«
«);
fprintf(fil,»%s %5d»,» Rezultat : «,rez);
fprintf(fil,»
«);
getch();
free(matr1);
if(zen == rez)
{
z=0;
}
zen = rez;
return;
}
//************* KOST()//************* PODSCHET POTENCIALOV ********************
void potenzial(void)
{
struct poten
{
int v;
int u;
int zn;
struct poten *next;
int b;
} *topnast = NULL,
*top = NULL,
*top1 = NULL;int i,j;
int fl;//********** ВЫДЕЛЕНИЕ ПАМЯТИ *******************8
if((pu=(int*)calloc(m,sizeof(int)))==NULL) abort();
if((pv=(int*)calloc(n,sizeof(int)))==NULL) abort();
// ПРИСВОЕНИЕ ВСЕМ ПОТЕНЦИАЛАМ ЗНАЧЕНИЯ MIN
for(i=0;i<m;i++)
*(pu+i) = MIN;for(j=0;j<n;j++)
*(pv+j) = MIN;
// Выделение памяти под структуру и заполнение её значениями
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if((*(matr+i*n+j) > 0) || (*(matr+i*n+j)==-2))
{
if((top=(struct poten*)malloc(sizeof(struct
poten)))==NULL)
abort();
fprintf(fil,»top = %d»,top);
if(!topnast){
topnast = top;
fprintf(fil,»topnast = top = %d»,top);
}
else top1 -> next=top;
top1=top;
top -> next=NULL;
top -> b = *(st+i*n+j); //Стоимости
top -> v = j;
top -> u = i;
top -> zn = -1;
}
}
}
*pu = 0;
i=0; j = -1;
for(top = topnast;top!=NULL;top = top -> next)
{
if((top -> u) == i && (top -> v)!=j)
{
*(pv+(top -> v)) = (top -> b) — *(pu+i);
j = (top->v);
top -> zn = 0;
}
else{
for(top1 = topnast;top1 != NULL;top1 = top1-
>next)
{
if((top1->v) == j && (top1->u)!=i)
{
*(pu+(top1->u))=(top1->b) — *(pv+j);
i = (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(«
ПОТЕНЦИАЛЫ ПО v:»);
fprintf(fil,»
**** ПОТЕНЦИАЛЫ ПО v:»);
for(i = 0;i<n;i++)
{
printf(«%d»,*(pv+i));
fprintf(fil,»%5d»,*(pv+i));
}
getch();
printf(«
ПОТЕНЦИАЛЫ ПО u: «);
fprintf(fil,»
**** ПОТЕНЦИАЛЫ ПО u: «);
for(i=0;i<m;i++)
{
printf(«%d»,*(pu+i));
fprintf(fil,»%5d»,*(pu+i));
}
fprintf(fil,»
«);
for(top = topnast;top!=NULL;top = top->next)
free(top);
return;
} // potenzial// ****** PROVERKA PLANA NA OPTIMALNOST' ************************
void abcikl(int ik,int jk);
int cikl(int ik,int jk);
void pr(char pr[],void *st); // Предварительно
int prpoisk(int i1,int j1); // Объявлены
int levpoisk(int i1,int j1); //ЭТИ
int verpoisk(int i1,int j1); //Функции
int nizpoisk(int i1,int j1);
int optim(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
// ИЩЕМ ОПТИМАЛЬНОЕ РЕШЕНИЕ В НАШЕЙ МАТРИЦЕ И ЕСЛИ ЕГО НЕ НАЙДЕМ
// ТО ПО СЛЕДУЮЩЕМУ УСЛОВИЮ ПРИСВОИМ ГРАФОКЛЕТКЕ С КООРДИНАТАМИ
// ik,jk ЗНАЧЕНИЕ -1
if(( *(pu+i)+ *(pv+j))>(*(st+i*n+j))&&((*(matr+i*n+j)) ==
0))
{
abcikl(i,j);
fprintf(fil,»optim(): План не оптимален, функции
main() возвращаем -1,
а abcikl() параметры i,j «);
return(-1);
}
}
}
fprintf(fil,»Plan optimalen»);
return(0);
} // ******* optim() ***************// ************** UPGRADE PLAN **************************
void abcikl(int ik,int jk)
{
int i,j;
fprintf(fil,»Мы в abcikl()»);
if((matr2=(int*)calloc(n*m,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
*(matr2+i*n+j) = *(matr+i*n+j); // Создаем копию рабочей
матрицы
}
}
*(matr2+ik*n+jk) = -1;
// значению матрицы с параметрами ik,jk присваеваем -1
printf(«
«);
printf(«Поиск Цепи:«);
fprintf(fil,»Поиск Цепи:«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,»%5d»,*(matr2+i*n+j));
printf(«%5d»,*(matr2+i*n+j));
}
fprintf(fil,»
«);
printf(«
«);
}
fprintf(fil,»Переходим в Сраную, Мать её, Функцию
cikl(ik,jk)
«);
getch();
cikl(ik,jk);return;
} // abcikl// ********* FUNKCION POISKA CIKLA **************************
int cikl(int ik,int jk)
{
int nst,nstr,i,j,
perlev = 0,
perpr = 0;
int perver = 0,
perniz = 0,
fl = 0,
fl3 = 1;
int napr;struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *topnast1 = NULL,
*top2 = NULL,
*top3 = NULL;
ch = 0;
if((top2 = (struct cik*)malloc(sizeof(struct cik))) ==
NULL)
abort();if(!topnast1)
{
topnast1=top2;
top3=top2;
top3->ick=ik;
top3->jck=jk;
}
else
top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
fprintf(fil,»До Условия while fl3 =%d
«,fl3);
pr(«top2»,top2);
fprintf(fil,»Весь цикл поиска сейчас начнется, надеюсь —что он будет не бесконечный или не бесполезный 🙁
«);
printf(«Весь цикл поиска сейчас начнется, надеюсь —что он будет не бесконечный или не бесполезный 🙁
«);
printf(«
press anykey to contunio
«);
getch();
while(fl3)
{
fl3=0;
fl = 0;
if((nst = prpoisk(ik,jk))>=0)
{
fprintf(fil,»Внимание!!!
nst = %d
«,nst);
fprintf(fil,»Ща будет поик идти ему бы…:Point
found!
«);
printf(«И он пошел RIGHT:Point found !
«);
napr = 2;
jk = nst;
top2->prnapr = 1;
}
else if((nstr = nizpoisk(ik,jk))>=0)
{
fprintf(fil,»DOWN: Point found !
«);
printf(«DOWN: Point found !
«);
napr = 3;
ik = nstr;
top2->prnapr = 2;
}else if((nst=levpoisk(ik,jk))>=0)
{
fprintf(fil,»LEFT:Point found !
«);
printf(«LEFT:Point found !
«);
napr = 4;
jk = nst;
top2->prnapr = 3;
}
// **************** Prodolzhenie 1 poiska ***********************
else if((nstr = verpoisk(ik,jk))>=0)
{
fprintf(fil,»UP:Point found !
«);
printf(«UP:Point found !
«);
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(«founded
«);
fprintf(fil,»founded
«);
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 LEFT
«);
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(«founded
«); fprintf(fil,»founded
«);
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 UP
«);
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(«founded
«);
fprintf(fil,»founded
«);
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 RIGHT
«);
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(«founded
«); fprintf(fil,»founded
«);
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
DOWN
«);
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 1
«);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)=%d
«,ik,jk,*(matr2+ik*n+jk));
fprintf(fil,»Viynimaem tochky:
(%d,%d)=%d
«,ik,jk,*(matr2+ik*n+jk));
pr(«top2»,top2);
}
perpr = 0;
perlev = 0;
} // IFif(perver == 1 && perniz == 1)
{
*(matr2+ik*n+jk)=0;
printf(«Zerro 2
«);
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) =
%d
«,ik,jk,*(matr2+ik*n+jk));
fprintf(fil,»Viynimaem tochky: (%d,%d) =
%d
«,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(«
«);
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<n;j++)
{
if((*(matr2+i1*n+j))!=0)
return(j);
}
return(-1);
}
int levpoisk(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;i<m;i++)
{
if((*(matr2+i*n+j1))!=0)
return(i);
}
return(-1);
}// ************* FUNCTION SEARCH
********************
void pr(char pr[],void *st)
{
struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *ptr;
int i,j;ptr = (struct cik *)st;
fprintf(fil,»Koordinatiy ytoplennoy tochki : %d and %d»,ptr-
>ick,ptr->jck);
printf(«Koordinatiy ytoplennoy tochki : %d and %d
«,ptr-
>ick,ptr->jck);
fprintf(fil,»and napravlenie»);
printf(«Napravlenie»);
switch(ptr->prnapr)
{
case 1:
fprintf(fil,»Vpravo
«);
printf(«Vpravo
«);
break;
case 2:
fprintf(fil,»Vniz
«);
printf(«Vniz
«);
break;
case 3:
fprintf(fil,»Vlevo
«);
printf(«Vlevo
«);
break;
case 4:
fprintf(fil,»Vverh
«);
printf(«Vverh
«);
break;
default:
fprintf(fil,»Start
«);
printf(«Start
«);
break;
}
fprintf(fil,»WORK MATRIX
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,»%5d»,*(matr2+i*n+j));
}
fprintf(fil,»
«);
}
fprintf(fil,»************************************
«);
return;
}// **************** UPGRADE PLAN *********************************//
void plmi(void)
{
int i,j,k,min,i1,j1,flagok;
ch = ch2;
flagok = 0;
i1=*zi;
j1 = *zj;
for(k=1;k<ch;k+=2){
i=*(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2){
*(matr+i1*n+j1) = *(matr+i*n+j);
*(matr+i*n+j) = 0;
flagok = 1;
break;
}
} // for
if(!flagok){
for(k=2;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2)
*(matr+i*n+j) = 0;
} // for
i = *(zi+1);
j = *(zj+1);
min = *(matr+i*n+j);
for(k=3;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
if(*(matr+i*n+j)<min)
min = *(matr+i*n+j);
}
if(min == -2) min = 0;
for(k=0;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
*(matr+i*n+j) += min;
}
for(k=1;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
*(matr+i*n+j)-=min;
}
} //if
// ***************** PROVERKA **************************//printf(«PROVERKA
«);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(«%5d»,*(matr+i*n+j));
}
printf(«
«);
}
free(matr2);free(zi);free(zj);free(pu);free(pv);
return;
}void Bas(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)!=0) basper++;
}
}
return;
}void sohran(void)
{
// Sravnenie
int i,j,k;
for(k=0;k<ch;k++)
{
i=zi[k];
j=zj[k];
if((*(matr+i*n+j) == 0) && (basper < m+n-1))
{
*(matr+i*n+j) = -2;
basper++;
}//if
}
return;
}
// ************ SOZDANIE OPORNOGO PLANA **************************
// ************ METODOM SEVERNO-ZAPADNOGO YGLA *******************
void opplan1(void)
{
int i,j, ch1 = n-1;
//**************** Viydelenie pamyty *************************
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=ch1;j>=0;j—)
{
if(*(po+i)<*(pn+j))
{
*(matr+i*n+j)=*(po+i);
*(pn+j)-=*(po+i);
*(po+i)=0;
break;
}
*(matr+i*n+j)=*(pn+j);
*(po+i)-=*(pn+j);
*(pn+j)=0;
ch1—;
}
}
//*************** Proverka *************************
printf(«Proverka
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(«%5d»,*(matr+i*n+j));
}
printf(«
«);
}
fprintf(fil,»matrix
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,»%5d»,*(matr+i*n+j));
}
fprintf(fil,»
«);
}
fprintf(fil,»*****************
«);
return;
}//******** opplan1//************** SOZDANIE OPORNOGO PLANA ********************
//*************** METHOD NORD-WEST YGOL *********************void opplan2(void)
{
int i,j,k_i,k_j=0, min = 32767, *kontr,fl;
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
if((kontr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++){
for(j=0;j<n;j++){
*(kontr+i*n+j) = 0;
}
}
for(i=0;i<m;i++){
fl = 0;
while(!fl){
for(j=0;j<n;j++){
if(*(st+i*n+j)<min){
if(*(kontr+i*n+j) == 0) {
min = *(st+i*n+j);
k_i = i; k_j = j;
}
}
}
*(kontr+k_i*n+k_j) = 1;
if(*(po+k_i)<*(pn+k_j)) {
min = 32767;
*(matr+k_i*n+k_j)=*(po+k_i);
*(pn+k_j)=*(po+k_i);
*(po+k_i)=0;
break;
}
else {
*(matr+k_i*n+k_j)=*(pn+k_j);
*(po+k_i)-=*(pn+k_j);
*(pn+k_j)=0;
min = 32767;
if(*(po+k_i) == 0) fl = 1;
}
}
}
printf(«Proverka
«); // proverka
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(«%5d»,*(matr+i*n+j));
}
printf(«
«);
}
fprintf(fil,» matr
«);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
fprintf(fil,»%5d»,*(matr+i*n+j));
}
fprintf(fil,»
«);
}
fprintf(fil,»*********************************
«);
return;
}// opplan2void main()
{
int i,j,met;
int flagok;
fil = fopen(«otchet.txt»,»w»);
clrscr();
gotoxy(1,3);
printf(«WARNING USERS —->«);
printf(«Решение закрытой трансп.задачи«);
printf(«Базисные переменные,равные нулю, помечаются -2;
«);
printf(«Графоклетка, относительно которой строится цепь
«);
printf(«помечается -1
«);
gotoxy(1,22);
printf(«press anykey to contunio…
«);
getch();
clrscr();
data();
printf(«press anykey to contunio…
«);
getch();
clrscr();
gotoxy(1,3);
printf(«
YOU selest method building first plan:
«);
printf(«1-method NORD-WEST ygol
«);
printf(«2-method NORD-EST ygol
«);
printf(«3-method minimum element to string
«);
scanf(«%d»,&met);
gotoxy(1,22);
printf(«press anykey, to contunie…
«);
getch();
//void opplan(void);
//void opplan1(void);
//void opplan2(void);
clrscr();
switch(met)
{
case 1: opplan();
break;
case 2: opplan1();
break;
case 3: opplan2();
break;
default: printf(«неверно выбран МЕТОД
«); exit(-1);
}
basper = 0;
Bas();
flagok = 0;
if(basper<m+n-1)
{
//Если в первоначальном плане количество базисных
//переменных, отличных от нуля, меньше, чем M+N-1
while(!flagok)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)==0)
{
*(matr+i*n+j) = -2;
flagok = 1;
basper++;
break;
} //if
}
if(flagok) break;
}
if(basper<m+n-1) flagok = 0;
}//while
}//if
for(;;)
{
fprintf(fil,»*********** Начало ДОЛБАНУТОЙ
Итерации**********
«);
basper = 0;
Bas();
//void sohran(void);
if(iter>0)
{
//Количество базисных ненулевых переменных <m+n-1
if(basper <m+n-1) sohran();
}
kost(); //****** Вывод общей стоимости******
potenzial(); //*******Подсчет потенциалов********
ch2 = 0;
z = optim();
if(!z) break;
plmi();
iter++;
fprintf(fil,»%d ШАГ ДОСТАВШЕЙ ДО СЪЕХАВШЕЙ КРЫШИ
ИТЕРАЦИИ»,iter);
}
//************* ПРОВЕРКА************
printf(«OPTIMAL PLAN :
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(«%5d»,*(matr+i*n+j));
}
printf(«
«);
}
fprintf(fil,»optimal PLAN :
«);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,»%5d»,*(matr+i*n+j));
}
fprintf(fil,»
«);
}
kost(); //************ВЫВОД общей
стоимости***********
fclose(fil);
clrscr();
printf(«Отчет о проделанной работе ПРОГРАММЫ в файле
otchet.txt»);
getch();
return;
} // main
