Методы решения транспортных задач


2. Описание методов решения транспортных задач

 

2.1 Математическая  постановка и общая характеристика  транспортных задач

 

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача ,определяеться широкий круг задач с единой математической моделью эти задачи относяться к задачам линейного программирования и могут быть решены оптимальным методом. Однако ,спец.метод решения транспортнои задачи позволяет существенно упростить её решение по скольку транспортная задача разрабатывалась для минимизирования стоимости перевозок .

 

2.2. Математические методы решения транспортных задач

 

История поиска методов решения.

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

Поиск начального решения.

Решение транспортной задачи начинается с поиска допустимого начального решения (плана перевозок), чтобы  все запасы поставщиков были распределены по потребителям. Допустимое начальное  решение не обязательно оказывается оптимальным, а метод его нахождения может быть как простейшим (метод северо-западного угла) или более сложным и приближенным к оптимальному решению (метод минимальных тарифов), или же вообще произвольным.

Метод северо-западного угла.

Допустимое (но не всегда оптимальное  с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно  перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г. и назван Чарнесом и Купером «правилом северо-западного угла».

 

Метод наименьшего  элемента.

Суть решения задачи методом минимального (наименьшего) элемента заключается в сведении к минимуму побочных перераспределений товаров между потребителями.

Алгоритм:

  1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
  2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
  3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

 

Алгоритм метода потенциалов:

Один из потенциалов  задается произвольно, скажем, полагается .

 

Рассматривается система  линейных уравнений вида для тех наборов индексов i , j , для которых , и находятся потенциалы и всех складов и всех пунктов потребления.

Для всех остальных наборов  индексов i , j (для которых ) проверяется условие.

Если это условие  выполняется для всех наборов  индексов i , j , для которых , то рассматриваемый план является оптимальным. Если же, хотя бы

для одной пары,  то план не оптимален.

 

3. Аналитическое решение задачи.

3.1 Решение в табличном процессоре MS Excel.

 

 

 

 

 

 

 

 

 

 

3.2 Ручной расчет.

    3.2.1 Метод северо-западного угла.

 

Дано:

 

Пункты

Запасы

12

14

32

20

3

54

8

10

12

24

12

32

6

8

12

24

18

85

10

18

4

8

9

162

Потребности

100

70

30

45

50

  

 

Запасы: 54+32+85+162=333

Потребности: 100+70+30+45+50=295

Запасы меньше потребностей, значит, добавляем столбец с разностью запасов и потребностей. Уравниваем:

 

Пункты

Запасы

12

14

32

20

3

0

54

8

10

12

24

12

0

32

6

8

12

24

18

0

85

10

18

4

8

9

0

162

Потребности

100

70

30

45

50

38

  

 

Вычисляем:

 

Пункты

Запасы

54

0

0

0

0

0

0

32

0

0

0

0

0

0

14

70

1

0

0

0

0

0

0

29

45

50

38

0

Потребности

0

0

0

0

0

0

  

 

F(x) =

 

 

F(x) = 12*54+8*32+6*14+70*8+12*1+4*29+8*45+9*50+)*38 =

= 648+256+84+560+12+116+360+450 = 2486

Ответ: F(x) = 2486.  

                                                           

 

3.2.1 Метод минимального элемента.

 

Дано:

 

Пункты

Запасы

12

14

32

20

3

54

8

10

12

24

12

32

6

8

12

24

18

85

10

18

4

8

9

162

Потребности

100

70

30

45

50

  

 

Запасы: 54+32+85+162=333

Потребности: 100+70+30+45+50=295

Запасы меньше потребностей, значит, добавляем столбец с разностью запасов и потребностей. Уравниваем:

 

Пункты

Запасы

12

14

32

20

3

0

54

8

10

12

24

12

0

32

6

8

12

24

18

0

85

10

18

4

8

9

0

162

Потребности

100

70

30

45

50

38

  

 

Решение:

 

Пункты

Запасы

0

0

0

0

16

38

0

15

17

0

0

0

0

0

85

0

0

0

0

0

0

0

53

30

45

34

0

0

Потребности

0

0

0

0

0

0

  

 

F(x) =

 

F(x) = 8*15+6*85+10*17+18*53+4*30+8*45+3*16+9*34+0*38 =

= 120+510+170+954+120+360+48+306 = 2588

 

Ответ: F(x) = 2588.

 

4.Заключение.

 

В результате выполнения курсового проекта был разработан алгоритм и написана программа для  решения транспортных задач с  использованием среды программирования C++ Builder 6.

 

 

5. Список литературы

  

5.1. Основная литература

5.1.1. Партыка Т.Л., Попов И.И. Математические методы. Гриф УМО МО РФ, 2009. – Изд-во: Форум. Серия: Профессиональное образование – 464 с.: ил.

5.1.2. Стрикалов А.И., Печенежская  И.А. экономико-математические методы  и модели: пособие к решению  задач. – Изд-во: Феникс, 2008 – 348 с.: ил.

5.1.3. Макаров С.И., Севастьянова  С.А. и др. Экономико-математические  методы и модели. Гриф УМО МО  РФ. Учебное пособие, 2009. – Изд-во: КноРус, 240 с.: ил.

5.1.4. Макаров С.И., Севастьянова  С.А. и др. Экономико-математические  методы и модели. Задачник.  Гриф УМО МО РФ., 2009. – Изд-во: КноРус, 202 с.: ил.

 

 

5.2. Электронные ресурсы

5.2.1. www.window.edu.ru

5.2.2. www.exponenta.ru

 

 

5.3. Нормативные документы

5.3.1. Стандарт организации  СТО НГТИ-1-2008. Курсовое проектирование. Новоуральск. Изд-во НГТИ, 2009. – 44 с.

5.3.2. Стандарт организации  СТО НГТИ-2-2007. Требования к оформлению  текстовой документации. Новоуральск.  Изд-во НГТИ, 2007. – 147 с.

5.3.3. ЕСПД ГОСТ 19.001-77, ГОСТ 19.002-80, ГОСТ 19.101-77, ГОСТ 19.102-77, ГОСТ 19.103-77.

5.3.4. Методические указания  к выполнению курсового проекта  по дисциплине «Математические  методы». Новоуральск. Изд-во УрПК  НГТИ, 2008. – 34 с.

 

6.Приложение A (обязательное). Блок-схема решения задачи

6.1 Функциональная  блок-схема.



 

 

 

 

 


 



 

 

 

 

 

 

 

 

 

6.2.Блок-схема метода северо-западного угла.



 


 



 



 


  


Да Нет


                  


                Да     Нет

 




 

 

 

 

 


 


 





Да            Нет



 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 


 


 


 


 

 

 

 

 

 

6.3.Блок-схема метода минимального элемента.


 

 



 

 

 

 


 

 

 


 




 


 

 

 

 

Да

 

 

 

Нет

 

 

Да

 

 

 

 

 

 Нет


 


 

 

 

 

 

 

 

 

 




 

 

 

 

 

 

 

 

 

 

 

 

 

       Да

 

7.Приложение Б (обязательное) Листинг программы

 

7.1. Листинг модуля menu

 

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

 

#include "menu.h"

#include "about.h"

#include "help1.h"

#include "sevzap1.h"

#include "minimal1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

Tmenu1 *menu1;

//---------------------------------------------------------------------------

__fastcall Tmenu1::Tmenu1(TComponent* Owner)

        : TForm(Owner)

{///////Заполнение таблицы  (Потребители)

StringGrid1->Cells[1][0]="B1";

StringGrid1->Cells[2][0]="B2";

StringGrid1->Cells[3][0]="B3";

StringGrid1->Cells[4][0]="B4";

StringGrid1->Cells[5][0]="B5";

StringGrid1->Cells[6][0]="B6";

StringGrid1->Cells[7][0]="Запасы";

///////Заполнение таблицы  (Поставщики)

StringGrid1->Cells[0][1]="A1";

StringGrid1->Cells[0][2]="A2";

StringGrid1->Cells[0][3]="A3";

StringGrid1->Cells[0][4]="A4";

StringGrid1->Cells[0][5]="Потребности";

///////Заполнение таблицы значениями  по столбцам

///1

StringGrid1->Cells[1][1]=12;

StringGrid1->Cells[1][2]=8;

StringGrid1->Cells[1][3]=6;

StringGrid1->Cells[1][4]=10;

///2

StringGrid1->Cells[2][1]=14;

StringGrid1->Cells[2][2]=10;

StringGrid1->Cells[2][3]=8;

StringGrid1->Cells[2][4]=18;

 

///3

StringGrid1->Cells[3][1]=32;

StringGrid1->Cells[3][2]=12;

StringGrid1->Cells[3][3]=12;

StringGrid1->Cells[3][4]=4;

///4

StringGrid1->Cells[4][1]=20;

StringGrid1->Cells[4][2]=24;

StringGrid1->Cells[4][3]=24;

StringGrid1->Cells[4][4]=8;

///5

StringGrid1->Cells[5][1]=3;

StringGrid1->Cells[5][2]=12;

StringGrid1->Cells[5][3]=18;

StringGrid1->Cells[5][4]=9;

 

///6

StringGrid1->Cells[6][1]=0;

StringGrid1->Cells[6][2]=0;

StringGrid1->Cells[6][3]=0;

StringGrid1->Cells[6][4]=0;

StringGrid1->Cells[6][5]=38;

/////////////Заполнение потребности  значениями

StringGrid1->Cells[1][5]=100;

StringGrid1->Cells[2][5]=70;

StringGrid1->Cells[3][5]=30;

StringGrid1->Cells[4][5]=45;

StringGrid1->Cells[5][5]=50;

/////////////Заполнение запасов значениями

StringGrid1->Cells[7][1]=54;

StringGrid1->Cells[7][2]=32;

StringGrid1->Cells[7][3]=85;

StringGrid1->Cells[7][4]=162;

////////////////////////////////////////////////////////////

stb=0;str=0;

}

//---------------------------------------------------------------------------

 

void __fastcall Tmenu1::N2Click(TObject *Sender)

{

about1->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall Tmenu1::N1Click(TObject *Sender)

{

help->Show();

}

//---------------------------------------------------------------------------

 

 

 

void __fastcall Tmenu1::Button1Click(TObject *Sender)

{

x=StringGrid1->ColCount-1;

y=StringGrid1->RowCount-1;

for(i=0;i<x;i++) {

sevzap->StringGrid1->Cells[i][j]=StringGrid1->Cells[i][j];

                                     }

                                    i=0;

for(j=0;j<y;j++){

sevzap->StringGrid1->Cells[i][j]=StringGrid1->Cells[i][j];

                                    }

                                    j=0;

stb=0;

str=0;

while(stb<x){

sevzap->StringGrid1->Cells[stb][y]=StringGrid1->Cells[stb][y];stb++;

        }

while(str<y){

sevzap->StringGrid1->Cells[x][str]=StringGrid1->Cells[x][str];str++;

        }

//////////////////////////////////////////////////////////////////////////////

menu1->Hide();

sevzap->Show();

}

//---------------------------------------------------------------------------

 

void __fastcall Tmenu1::Button2Click(TObject *Sender)

{

x=StringGrid1->ColCount-1;

y=StringGrid1->RowCount-1;

for(i=0;i<x+1;i++){

        for(j=0;j<y+1;j++){

minimal->StringGrid1->Cells[i][j]=StringGrid1->Cells[i][j];

                        }

                }

i=0;j=0;

////////////////////////////////////////////////////////////

for(i=0;i<x;i++) {

minimal->StringGrid2->Cells[i][j]=StringGrid1->Cells[i][j];

                                     }

                                    i=0;

for(j=0;j<y;j++){

minimal->StringGrid2->Cells[i][j]=StringGrid1->Cells[i][j];

                                    }

                                    j=0;

stb=0;

str=0;

while(stb<x){

minimal->StringGrid2->Cells[stb][y]=StringGrid1->Cells[stb][y];stb++;

        }

while(str<y){

minimal->StringGrid2->Cells[x][str]=StringGrid1->Cells[x][str];str++;

        }

//////////////////////////////////////////////////////////////////////////////

menu1->Hide();

minimal->Show();

}

//---------------------------------------------------------------------------

 

void __fastcall Tmenu1::BitBtn1Click(TObject *Sender)

{

Application->Terminate();

}

//---------------------------------------------------------------------------

 

7.2. Листинг модуля sevzap1

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

#include "menu.h"

#include "sevzap1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

Tsevzap *sevzap;

//---------------------------------------------------------------------------

__fastcall Tsevzap::Tsevzap(TComponent* Owner)

        : TForm(Owner)

{

//присваиваем значения по умолчанию

stb=1;

str=1;

r=0;

fx=0;

}

//---------------------------------------------------------------------------

void __fastcall Tsevzap::BitBtn2Click(TObject *Sender)

{

///присваиваем количество строк и столбцов для x y

x=StringGrid1->ColCount-1; ///столбец

y=StringGrid1->RowCount-1; ///строка

///ограничиваем решение цикла  для вывода результата

if((StringGrid1->Cells[x-1][y]!=0)&&(StringGrid1->Cells[x][y-1]!=0)){

///цикл для подсчета, когда запасы  больше потребностей

  if(StringGrid1->Cells[x][str].ToDouble()>StringGrid1->Cells[stb][y].ToDouble())

   {//присвоим минимальное из значений в целевую ячейку

   StringGrid1->Cells[stb][str]=StringGrid1->Cells[stb][y];

   //из большего вычитаем меньшее и присваиваем большей ячейке

   StringGrid1->Cells[x][str]=StringGrid1->Cells[x][str]-StringGrid1->Cells[stb][y];

   StringGrid1->Cells[stb][y]=0;//обнуляем  минимальный элемент

   //считаем F(x)

   r=StringGrid1->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

   fx=fx+r;

   r=0;//сбрасываем результат

   //

   stb++;//сдвигаемся на столбец

   return;//останавливаем выполнение

   }

///цикл для подсчета, когда запасы  меньше потребностей

  if(StringGrid1->Cells[x][str].ToDouble()<StringGrid1->Cells[stb][y].ToDouble())

   {//присвоим минимальное из значений в целевую ячейку

   StringGrid1->Cells[stb][str]=StringGrid1->Cells[x][str];

   //из большего вычетаем меньшее и присваеваем большей ячейке

   StringGrid1->Cells[stb][y]=StringGrid1->Cells[stb][y]-StringGrid1->Cells[x][str];

   StringGrid1->Cells[x][str]=0;//обнуляем минемальный элемент

   //считаем F(x)

   r=StringGrid1->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

   fx=fx+r;

   r=0;//сбрасываем результат

   //

   str++;//сдвигаемся на строку

   return;//останавливаем выполнение

   }

///цикл для подсчета, когда запасы равны потребностям

  if(StringGrid1->Cells[x][str].ToDouble()==StringGrid1->Cells[stb][y].ToDouble())

   {//присвоим любое из значений в целевую ячейку

   StringGrid1->Cells[stb][str]=StringGrid1->Cells[x][str];

   StringGrid1->Cells[stb][y]=0;//обнуляем сравневаемые ячейки

   StringGrid1->Cells[x][str]=0;

   //считаем F(x)

   r=StringGrid1->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

   fx=fx+r;

   r=0;//сбрасываем результат

   //

   stb++;str++;//перемещаемся на стб и стр по таблице

   return;//останавливаем выполнение

   }

          }

/////////////////////////////////////////////////////////////

else{///включаем кнопку для вывода результата,вкл эту

BitBtn2->Visible=false;

BitBtn3->Visible=true;

    }

}

//---------------------------------------------------------------------------

 

void __fastcall Tsevzap::BitBtn3Click(TObject *Sender)

{///убираем кнопки - выводим результат

Label2->Caption=fx;

Label2->Visible=true;

BitBtn3->Visible=false;

}

//---------------------------------------------------------------------------

 

 

 

void __fastcall Tsevzap::BitBtn1Click(TObject *Sender)

{

x=StringGrid1->ColCount-1;

y=StringGrid1->RowCount-1;

for(i=0;i<x+1;i++){

        for(j=0;j<y+1;j++){

StringGrid1->Cells[i][j]="";

                        }

                }

Label2->Visible=false;

stb=1;

str=1;

r=0;

fx=0;

BitBtn2->Visible=true;

menu1->Show();

sevzap->Close();

}

//---------------------------------------------------------------------------

 

 

7.3. Листинг модуля minimal1

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

 

#include "minimal1.h"

#include "menu.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

Tminimal *minimal;

//---------------------------------------------------------------------------

__fastcall Tminimal::Tminimal(TComponent* Owner)

        : TForm(Owner)

{

//присваиваем значения по умолчанию

stb=1;

str=1;

r=0;

fx=0;

i=1;

j=1;

}

//---------------------------------------------------------------------------

void __fastcall Tminimal::BitBtn1Click(TObject *Sender)

{

///действие вернуться  на главную форму

/////присваиваем переменным значения размера таблицы

x=StringGrid1->ColCount-1;

y=StringGrid1->RowCount-1;

/////очищаем первую  таблицу

for(i=0;i<x+1;i++){

        for(j=0;j<y+1;j++){

StringGrid1->Cells[i][j]="";

                        }

                }

//////очищаем вторую  таблицу

for(i=0;i<x+1;i++){

        for(j=0;j<y+1;j++){

StringGrid2->Cells[i][j]="";

                        }

                }

/////возвращаем начальные  значения переменным

stb=1;str=1;

r=0;fx=0;

i=1;j=1;

BitBtn3->Visible=true;

Label2->Visible=false;

//////////////переходим в  главное меню

menu1->Show();

minimal->Close();

}

//---------------------------------------------------------------------------

 

void __fastcall Tminimal::BitBtn3Click(TObject *Sender)

{

x=StringGrid1->ColCount-1;

y=StringGrid1->RowCount-1;

i=1;j=1;

min=StrToInt(StringGrid1->Cells[i][j]); //принемаем за минимум первый элемент

stb=1;str=1;////

for(int i = 1; i < StringGrid1->ColCount-1; i++) {

  for(int j = 1; j < StringGrid1->RowCount-1; j++) {

    if (min>StringGrid1->Cells[i][j]) {

      min=StringGrid1->Cells[i][j].ToInt();

      stb=i;str=j;///запоминаем координаты минимального элемента

                                      }

                                                   }

                                                 }

////когда минимальный  не равен, тогда выполняем решение

if (min != 999){

 

        if (StringGrid1->Cells[stb][y].ToDouble()<StringGrid1->Cells[x][str].ToDouble())

{///цикл для подсчета, когда запасы больше потребностей

StringGrid2->Cells[stb][str]=StringGrid1->Cells[stb][y];

StringGrid1->Cells[stb][str]=StringGrid1->Cells[stb][y];

StringGrid1->Cells[x][str]=StringGrid1->Cells[x][str]-StringGrid1->Cells[stb][y];

StringGrid2->Cells[x][str]=StringGrid1->Cells[x][str];

///считаем F(x)

r= StringGrid2->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

fx=fx+r;r=0; Label2->Caption=fx;

///замещаем столбец

for(int str = 1; str < y ; str++) {StringGrid1->Cells[stb][str]=999;}

StringGrid2->Cells[stb][y]=0;

StringGrid1->Cells[stb][y]=0;

return;

}

 

        if (StringGrid1->Cells[stb][y].ToDouble()>StringGrid1->Cells[x][str].ToDouble())

{/// цикл для подсчета, когда запасы меньше потребностей

StringGrid2->Cells[stb][str]=StringGrid1->Cells[x][str];

StringGrid1->Cells[stb][str]=StringGrid1->Cells[x][str];

StringGrid1->Cells[stb][y]=StringGrid1->Cells[stb][y]-StringGrid1->Cells[x][str];

StringGrid2->Cells[stb][y]=StringGrid1->Cells[stb][y];

///считаем F(x)

r= StringGrid2->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

fx=fx+r;r=0; Label2->Caption=fx;

/////замещаем строку

for(int stb = 1; stb < x ; stb++) {StringGrid1->Cells[stb][str]=999;}

StringGrid2->Cells[x][str]=0;

StringGrid1->Cells[x][str]=0;

return;

}

 

        if (StringGrid1->Cells[stb][y].ToDouble()==StringGrid1->Cells[x][str].ToDouble())

{///цикл для подсчета, когда запасы равны потребностям

StringGrid2->Cells[stb][str]=StringGrid1->Cells[x][str];

StringGrid1->Cells[stb][str]=StringGrid1->Cells[x][str];

StringGrid1->Cells[stb][y]=0;

StringGrid2->Cells[stb][y]=0;

StringGrid1->Cells[x][str]=0;

///считаем F(x)

r= StringGrid2->Cells[stb][str]*menu1->StringGrid1->Cells[stb][str];

fx=fx+r;r=0; Label2->Caption=fx;

/////замещаем строку  и столбец

for(int stb = 1; stb < x ; stb++) {StringGrid1->Cells[stb][str]=999;}

for(int str = 1; str < y ; str++) {StringGrid1->Cells[stb][str]=999;}

StringGrid2->Cells[x][str]=0;

return;

}

}

else {BitBtn4->Visible=true;BitBtn3->Visible=false;}

}

//---------------------------------------------------------------------------

Методы решения транспортных задач 📙 Курсовая → 🆔 129058

Методы решения транспортных задач 📙 Курсовая → 🆔 129058

Методы решения транспортных задач