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

 

 

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

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