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

Министерство  образования Российской Федерации

Санкт-Петербургский  Промышленно - Экономический Колледж

 

 

 

 

 

 

 

Курсовая  работа

По  предмету: Методы математического анализа  экономической деятельности предприятия.

 

На  тему: Транспортная задача.

 

 

 

 

 

 

 

 

Работу выполнил:

Гончаров Дмитрий Николаевич.

Студент группы: 442-00

Преподаватель:

Бондарчук Галина Андриановна

Оценка: ______________________

 

 

 

 

 

 

Мурманск 2005 г.

Содержание

Введение 

 

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

  1.1   Постановка задачи 

1.2   Закрытая  и открытая модели транспортной задачи

1.3   Опорный  план 

 

2.  Решение транспортных задач.

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

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

2.3  Метод  аппроксимации  

    1. Потенциалы.
    2. Критерий оптимальности плана

 

 

3.  Программа

3.1 Инструкция по эксплуатации программы (Delphi 7)

3.2 Код программы

3.3 Разработка  программы при помощи MS Excel.

 

4.  Практическое применение методов. 

Заключение 

 

Список  использованной литературы.

 

Введение

При появлении мощных ЭВМ стало  возможным проведение сложных и емких расчетов, следовательно, появилась возможность реализовать на практике многие придуманные ранее теории. Одной из таких теорий является решение «транспортных задач». В связи с ростом промышленности и грузообороте без математической системы оптимизации обойтись было нельзя.  Данные методы стали, применятся в промышленности, транспорте и др. областях.

В данной работе я поставил себе задачу:

Изучить  методы решения транспортной задачи.

Написать программу  вычисляющую, одним из способов, решение Т.З.

 

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

    1. Постановка задачи.

 

Допустим, есть товар, находящийся в разных количествах  на нескольких складах. Необходимо доставить  этот товар в некоторых количествах  нескольким потребителям, причем известна стоимость доставки единицы груза от склада к потребителю.

Необходимо  составить план перевозок, позволяющий  вывезти все товары, полностью  удовлетворить потребности потребителей и иметь минимальную стоимость  затрат на перевозку.

  

 Условия  задачи можно записать в виде  таблицы.

Таблица    1

СКЛАДЫ

  

ПОТРЕБИТЕЛИ

    

ЗАПАСЫ

A1

C11

x11

C12

x12

 

...

C1n

x1n

а1

A2

C21

x21

C22

x22

...

C2n

x2n

а2

…

        

…

AN

Cm1

xm1

Cm2

xm2

 

...

Cmn

xmn

N

Потребности

B1

B2

…

BN


 

 

  Так как от  поставщика к  потребителю запланирован к перевозке  груз, то стоимость перевозки составит.

Оценка стоимости всего  плана выразится  суммой:

     Z  =  .

 

 

 

 

 

Ограничений получаем из следующих  условий задачи:

 а) все грузы должны  быть вывезены, т.е. 

 б) все потребности должны быть удовлетворены, т.е. 

 

ММ транспортной задачи имеет  следующий вид:

  

 Z =                

  ,

i = 1, 2, ..., m,             

 ,

j = 1,2,3,...,n ,                

Суммарные запасы равны суммарным потребностям,

    

Такая модель называется закрытой, т. е.  линейная функция ограничена на множестве планов транспортной задачи.

 

C¢¢ M ≤ Z ≤ C¢ M ,

 

1.2 Открытая  модель транспортной задачи

     Задача, в которой сумма запасов и потребностей совпадают, называется закрытой моделью;  в противном случае ¾ открытой. Для открытой модели может быть два случая:

 

суммарные запасы превышают суммарные потребности;

 

суммарные потребности  превышают суммарные запасы.

 

Открытая  модель решается приведением к закрытой модели.

 

В случае, когда  суммарные запасы превышают суммарные  потребности, вводится фиктивный потребитель Bn+1, потребности которого  bn+1 = .

В случае, когда  суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  Am+1, запасы которого am+1 = .

Задача принимает  вид закрытой модели и решается обычным  способом. При равных стоимостях перевозки  единицы груза от поставщиков  к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика. Стоимость перевозки единицы груза, как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.

 

Для начало необходимо определить, к какой модели  принадлежит  задача, и только после этого готовить таблицу для ее решения.

 

1.3   Построение  опорного плана.          

 Система  ограничений (2) и (3) транспортной  задачи содержит m´n неизвестных и m+n уравнений. Если сложить почленно уравнения отдельно подсистемы  (2) и отдельно подсистемы (3), то получим два одинаковых уравнения. В таблице такое сложение равнозначно соответственно по членному сложению столбцов и почленно сложению строк. Если условие транспортной задачи и ее опорный план записаны в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, а остальные - незанятыми.

 Клетки будучи  заполненными соответствуют неизвестным,  и для невырожденного опорного  плана их количество равно 

m+n-1. Если ограничения транспортной задачи записаны в виде (2) и (3) то, как известно, базисным неизвестным, включенным в опорный план, соответствует система линейно независимых векторов.

План транспортной задачи, содержащий более m+n-1  занятых клеток, не являются опорным, так как ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл, с помощью которого уменьшают число занятых клеток до m+n-1. Циклом называется набор клеток, в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая.  Если к занятым клеткам, определяющим опорный невырожденный план, следовательно, и ацикличный, присоединить какую-либо незанятую клетку, то план становится не опорным, появляется единственный цикл, все вершины которого, за исключением одной, лежат в занятых клетках.

     Когда составляется первоначальный опорный план, методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях с помощью ЭВМ. Стоимости планов, полученных методами минимальной стоимости и аппроксимации Фогеля меньше стоимости плана, полученного методом северно-западного угла, значит они ближе к  оптимальному плану.

       
2. Решение транспортных задач.

2.1 Построение исходного опорного плана (метод северо-западного угла)

Для решения транспортной задачи необходим исходный опорный план.

При нахождении опорного плана транспортной задачи методом Северо-западного угла, на каждом шаге рассматривают первый из оставшихся пунктов отправления.

Заполнение  клеток таблицы условно начинается с левой верхней клетки. Для  неизвестного Х 1, 1 (СЗУ) и заканчивается  клеткой для неизвестного Х мин. т.е. идет по диагонали таблицы.

Пример:

На три базы: А 1, А 2, А 3 поступил однородный груз в соответствующем количестве: 140, 180, 160 единиц.

Этот груз требуется  перевести в пять пунктов назначения: В 1, В 2, В 3, В 4, В 5,  соответственно в  количествах 60,  70,  120,  130,  100.

Тарифы перевозок  единицы груза с каждого из пунктов отправления в соответствующий пункт назначения указаны в таблице. Тарифы обозначим Х.

Представим  это в виде таблицы,

Х

Х

Х

Х

Х

А 1

Х

Х

Х

Х

Х

А 2

Х

Х

Х

Х

Х

А3

В 1

В 2

В 3

В 4

В 5

  

 

Где в столбце  справа указаны запасы, в строке снизу потребности, а пустые клетки оставлены для будущего плана перевозок.

Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла".

2       60

3

4

2

4

140

8

4

1

4

1

180

9

7

3

7

2

160

60

70

120

130

100

  

 

Тогда, запланировав перевозку из первого склада в первый пункт потребления, мы полностью удовлетворим его потребности. Перевозить туда больше будет ничего не надо, поэтому остальные перевозки туда будут равны нулю.

Обратите внимание на то, что оставшаяся незаполненной часть таблицы  вновь по структуре та же, что и исходная таблица, только в ней на один столбец меньше.

Ну, а дальше все можно повторить, продолжая  заполнять оставшуюся часть таблицы  перевозок, начиная с левого верхнего, "северо-западного" угла, пока не будут исчерпаны запасы всех складов  и не удовлетворены потребности всех пунктов потребления. В итоге у нас получится:

 

2      60

3       70

4      10

2

4

140

8

4

1      110

4      70

1

180

9

7

3

7      60

2      100

160

60

70

120

130

100

  

 

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

2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380

     При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального.

 

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

Выбор пункта отправления  и назначения целесообразно производить, ориентируясь на тарифы перевозок:

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

Рассмотрим  этот метод на предыдущей задаче:

2      

3

4

2

4

140

8

4

1

4

1

180

9

7

3

7

2

160

60

70

120

130

100

  

 

 

В итоге получится:

2        10

3

4

2       130

4

140

8

4

1       120

4

1       60

180

9        50

7       70

3

7

2       40

160

60

70

120

130

100

  

 

Итоговый результат получаем по тому же принципу, как и в первом примере.

2*10+2*130+1*120+1*60+9*50+7*70+2*40=1480

 

2.3 Метод аппроксимации 

На каждой итерации по всем столбцам и строкам находят  разность между двумя записанными  в них минимальными тарифами. Эти разности, записывают в  отведенных для этого, в строке и в столбце таблице условий задачи. Среди указанных разностей выбирают наибольшую. В строке или столбце, которой эта разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной  итерации.

Если минимальный  тариф одинаков для нескольких данных строк или столбца, то для заполнения выбирают ту клетку, которая расположена  в столбце или строке соответствующей  наибольшей разности между двумя  минимальными тарифами, находящимися в данной строке или столбце.

Пример:

На три базы: А 1, А 2, А 3 поступил однородный груз в  соответствующем количестве: 220, 330, 250 единиц.

Этот груз требуется  перевести в пять пунктов назначения: В 1, В 2, В 3, В 4,  соответственно в количествах 160,  220,  130,  290.

Тарифы перевозок  единицы груза с каждого из пунктов отправления в соответствующий  пункт назначения указаны в таблице.

Рассмотрим  пример решения данной задачи:

6

6

3

5

220

        

4

5

3

2

330

        

6

3

5

4

250

        

160

220

130

290

290

        
                 
                 
                 
                 

После проведения первой итерации мы получим:

6

6

3

5

220

2

      

4

5

3

2     290

330

1

      

6

3

5

4

250

2

      

160

220

130

290

290

        

2

2 

0 

2 

          
                 
                 
                 

После проведения таким же образом всех последующих  итераций получается такая таблица:

6      90

6

3    130

5

220

2

3

1

Х

4      40

5    

3

2     290

330

1

2

1

Х

6      30

3     220

5

4

250

1

2

3

Х

160

220

130

290

          

2

2

0

2

          

2

2

0

Х

          

2

2

Х

Х

          

2

Х

Х

Х

          

 

Итоговый результат получаем по тому же принципу, как и в первом примере.

6*90+4*40+6*30+3*220+3*130+2*290=2510.

 

 

2.4 Потенциалы

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

Каждому поставщику (Ai), т.е. в каждой строке поставим в соответствии некоторое число Di, называемое потенциалом Ai, а каждому потребителю Bj – Bj . 

Для каждой заполненной клетки, т.е. для каждой базисной переменной строится соотношение, где. С и J тарифы, стоящие в заполненных клетках таблицы.

Количество m+n-1 уравнений с m+n неизвестными. Такая система имеет множество решений, и любое из них будет содержать искомые потенциалы. Чтобы найти одно из решений, значения одного из потенциалов задается произвольно, обычно считают, что D1=0 и находят значения остальных потенциалов.

  Для каждой незаполненной клетки находим числа:

Aij = Bj – Ai –Ci и заносят их в таблицу.

Затем проверяем полученный план на оптимальность. Если  Aij <= 0 то план не является оптимальным, и переходим к другому базисному плану, путем перемещения перевозки в клетку соответствующую условию. Если таких клеток больше одной, то перевозку помещают в первую по порядку. Выбранная клетка помещается в таблицу. Переменная, стоящая в этой клетке вводится в базис.

Для правильного перемещения  перевозок, чтобы не нарушить ограничений, строится цикл. Вычеркиваются все строки  и  столбцы, содержащие ровно одну заполненную клетку.

Все остальные заполненные клетки составляют цикл и лежат в его углах. В  каждой клетке цикла. Проставляем поочередно знаки +, -. В незап. +. В клетках  со знаком – выбирается минимальная  величина, новый базисный план получается путем сложения выбранной величины с величинами стоящими в клетках со знаком +. Вычитаем из этой величины стоящей в клетках со знаком  – и. Выбранная минимальная величина будет соответствовать переменной выводимой из базиса. Если таких величин более 1, то из базиса выводятся любая из переменных соответствующих ей. Значение переменных после описанной корректировки переносятся в новую таблицу. Все остальные переменные заносятся в новую таблицу без изменений. Затем повторяем все вышеперечисленные действия, пока не выполнится условие задачи…

 

2.5 Критерий оптимальности плана

Оптимальный опорный план транспортной задачи.

Согласно  теореме двойственности, должно выполняться  условие

Это и позволяет  проверить оптимальность любого опорного плана.

Сам алгоритм выглядит следующим  образом:

  1. Один из потенциалов задается произвольно, скажем, полагается .
  2. Рассматривается система линейных уравнений вида для тех наборов индексов i , j , для которых , и находятся потенциалы и всех складов и всех пунктов потребления.
  3. Для всех остальных наборов индексов i , j (для которых ) проверяется условие

.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Описание  программы.

3.1 Инструкция  по эксплуатации (Описание программы).

Для воплощения транспортной задачи средствами ЭВМ, я выбрал среду  разработки – Delphi 7. Так как считаю, ее более доступной и простой, а так же имеющей для этого все средства.

Программа, разработанная мною, считает транспортные задачи методом СЗУ.

Интерфейс программы  воплощен на небольшой форме, в него входят кнопки управления и поля для  ввода данных, а так же поля, которых  при запуске программы выдается ответ.

Для начала работы с программой ее необходимо запустить, запустить EXE файл программы.

Появится рабочая форма, представляющая интерфейс программы.

Ввести поставщиков  в поля А1, А2, А3 и А4.

Ввести заказчиков в  поля В1, В2, В3.

Ввести тарифные ставки в поля, где прописаны нули.

Нажать кнопку «Подсчет»

Если  А1+А2+А3+А4= В1+В2+В3, тогда программа показывает оптимальный  план (по СЗУ), дает конечную сумму в  окне «сумма».

При этом становятся активными 2 кнопки на форме:

Сброс - полная очистка  всех окон от получившихся и исходных данных.

Исправить - возможность внести изменения в исходные данные и вновь запустить программу.

Если  А1+А2+А3+А4 не =  В1+В2+В3, тогда программа выдает сообщение:

Сумма А не равна сумме  В. И предоставляется возможность  исправить исходные данные.

При завершении работы с программой нужно нажать кнопку «закрыть приложение - Х».

Программа не требует  от ПК больших ресурсов и может  запускаться даже на очень слабых машинах. Необходимо наличие любого Windows, т.к. программа создана, как приложение для Windows.

Тексты программы представлены ниже:

 

 

 

unit Unit1;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls;

 

type

  TForm1 = class(TForm)

    Edit1: TEdit;

    Edit2: TEdit;

    Edit3: TEdit;

    Edit4: TEdit;

    Edit5: TEdit;

    Edit6: TEdit;

    Edit7: TEdit;

    Edit8: TEdit;

    Edit9: TEdit;

    Edit10: TEdit;

    Edit11: TEdit;

    Edit12: TEdit;

    Edit13: TEdit;

    Edit14: TEdit;

    Edit15: TEdit;

    Edit16: TEdit;

    Edit17: TEdit;

    Edit18: TEdit;

    Edit19: TEdit;

    Button1: TButton;

    Button2: TButton;

    Edit20: TEdit;

    Label1: TLabel;

    Edit21: TEdit;

    Edit22: TEdit;

    Edit23: TEdit;

    Edit24: TEdit;

    Edit25: TEdit;

    Edit26: TEdit;

    Edit27: TEdit;

    Edit28: TEdit;

    Edit29: TEdit;

    Edit30: TEdit;

    Edit31: TEdit;

    Edit32: TEdit;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Label6: TLabel;

    Label7: TLabel;

    Edit33: TEdit;

    Label9: TLabel;

    Label10: TLabel;

    Button3: TButton;

    Bevel1: TBevel;

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var a1,a2,a3,a4: integer;

    b1,b2,b3: integer;

    w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12: integer;

begin //начальный

button1.Enabled:=false;

button2.Enabled:=true;

button3.Enabled:=true;

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

    if edit13.Text=('') then

    begin

    showmessage('Введите данные a1');

    edit13.Text:=inttostr(0);

    edit13.Color:=clred;

    end;

    if edit14.Text=('') then

    begin

    showmessage('Введите данные a2');

    edit14.Text:=inttostr(0);

    edit14.Color:=clred;

    end;

    if edit15.Text=('') then

    begin

    showmessage('Введите данные a3');

    edit15.Text:=inttostr(0);

    edit15.Color:=clred;

    end;

    if edit16.Text=('') then

    begin

    showmessage('Введите данные a4');

    edit16.Text:=inttostr(0);

    edit16.Color:=clred;

    end;

    if edit17.Text=('') then

    begin

    showmessage('Введите данные b1');

    edit17.Text:=inttostr(0);

    edit17.Color:=clred;

    end;

    if edit18.Text=('') then

    begin

    showmessage('Введите данные b2');

    edit18.Text:=inttostr(0);

    edit18.Color:=clred;

    end;

    if edit19.Text=('') then

    begin

    showmessage('Введите данные b3');

    edit19.Text:=inttostr(0);

    edit19.Color:=clred;

    end;

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

  begin

  a1:=strtoint(edit13.Text);

  a2:=strtoint(edit14.Text);

  a3:=strtoint(edit15.Text);

  a4:=strtoint(edit16.Text);

  b1:=strtoint(edit17.Text);

  b2:=strtoint(edit18.Text);

  b3:=strtoint(edit19.Text);

  end;

    begin

    edit20.Text:=inttostr(b1+b2+b3);

    end;

    if (a1+a2+a3+a4)<>(b1+b2+b3) then

    begin

    showmessage('сумма "а"  не равна сумме "в"');

    edit20.Color:=clred;

    edit20.Text:=('');

    end;

if (a1+a2+a3+a4)=(b1+b2+b3) then

begin  //начало подсчета

edit1.Text:=inttostr(a1);

  if strtoint(edit1.Text)<=b1 then

  begin

  edit4.Text:=inttostr(a2);

    if strtoint(edit1.Text)+strtoint(edit4.Text)<=b1 then

    begin

    edit7.Text:=inttostr(a3);

      if strtoint(edit1.Text)+strtoint(edit4.Text)+strtoint(edit7.Text)<=b1 then

      begin

      edit10.Text:=inttostr(b1-(strtoint(edit1.Text)+strtoint(edit4.Text)+strtoint(edit7.Text)));

      edit11.Text:=inttostr(b2);

      edit12.Text:=inttostr(b3);

      end;

      if strtoint(edit1.Text)+strtoint(edit4.Text)+strtoint(edit7.Text)>b1 then

      begin

      edit7.Text:=inttostr(b1-(strtoint(edit1.Text)+strtoint(edit4.Text)));

      edit8.Text:=inttostr(a3-(strtoint(edit7.Text)));

        if strtoint(edit8.Text)<=b2 then

        begin

        edit11.Text:=inttostr(b2-strtoint(edit8.Text));

        edit12.Text:=inttostr(b3);

        end;

        if strtoint(edit8.Text)>b2 then

        begin

        edit8.Text:=inttostr(b2);

        edit9.Text:=inttostr(a3-(strtoint(edit7.Text)+strtoint(edit8.Text)));