МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Транспортная задача

    Транспортная задача

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

    Курсовая

    по дисциплине

    «Компьютерное моделирование»

    на тему

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

    Выполнил: Ошкин Е.С.

    Проверил: Сергеев А.В.

    Мурманск

    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;i0)

    rez += (*(matr1+i*n+j))

    *(*(st+i*n+j));

    }

    }

    printf("\n Rezultat : %d",rez);

    printf("\n");

    fprintf(fil,"%s %5d"," Rezultat : ",rez);

    fprintf(fil,"\n");

    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 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("\n ПОТЕНЦИАЛЫ ПО v:");

    fprintf(fil,"\n **** ПОТЕНЦИАЛЫ ПО v:");

    for(i = 0;inext)

    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(*(st+i*n+j))&&((*(matr+i*n+j)) ==

    0))

    {

    abcikl(i,j);

    fprintf(fil,"optim(): План не оптимален, функции

    main() возвращаем -1,\n а 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;iick=ik;

    top3->jck=jk;

    }

    else

    top3->next=top2;

    top3=top2;

    top2->next=NULL;

    top2->ick = ik;

    top2->jck = jk;

    ch++;

    fprintf(fil,"\n\nДо Условия while fl3 =%d \n",fl3);

    pr("top2",top2);

    fprintf(fil,"Весь цикл поиска сейчас начнется, надеюсь -

    \n что он будет не бесконечный или не бесполезный :( \n");

    printf("Весь цикл поиска сейчас начнется, надеюсь - \n

    что он будет не бесконечный или не бесполезный :( \n");

    printf("\n \t \t\tpress anykey to contunio\n");

    getch();

    while(fl3)

    {

    fl3=0;

    fl = 0;

    if((nst = prpoisk(ik,jk))>=0)

    {

    fprintf(fil,"\n\nВнимание!!!\n nst = %d \n",nst);

    fprintf(fil,"Ща будет поик идти ему бы...:Point

    found!\n");

    printf("И он пошел RIGHT:Point found !\n\r");

    napr = 2;

    jk = nst;

    top2->prnapr = 1;

    }

    else if((nstr = nizpoisk(ik,jk))>=0)

    {

    Страницы: 1, 2


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.