Методы решения транспортной задачи (метод потенциалов)

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

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

Замечание 2. Под величинами , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой, является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

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

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

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

2.1 Диагональный  метод, или метод северо-западного  угла

 

При этом методе на каждом шаге построения первого опорного плана  заполняется левая верхняя клетка (северо-западный угол) оставшейся части  таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок (приложение 3).

Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным  . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .

Теперь переходим к  заполнению клетки для неизвестного и т.д.

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

Общий объем перевозок  в тонно-километрах для этого  плана составит

 

.

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

 

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

Пример

Составить первоначальный опорный  план методом минимального элемента для транспортной задачи вида:

 

2	3	4	15
11	6	10	1
8	9	3	3
4	1	2	21
10	20	10

 

Решение:

Задача сбалансирована.

Строим первоначальный опорный  план методом минимального элемента.

1. Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;
4. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

 

10	5	0
0	1	0
0	3	0
0	11	10

 

2.3 Метод  наименьшей стоимости

 

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

 

 

 

Пример

Пункты отправления	Пункты назначения										Запасы
		70		50		15		80		70	300
	20				100				180
		80		90		40		60		85	150
	150
		50		10		90		11		25	250
			110				120		20
Потребности	170		110		100		120		200		700

 

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

 

.

 

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

.

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

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

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

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

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

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

 

 

 

 

 

 

 

2.4 Скриншоты курсового  программного продукта

 

Рисунок 1 – Результат  вычисления программы, по введённым  данным.

Рисунок 2 – По нажатию  кнопки «Задать размер» открывается  окно «Количество», в котором пользователь может задать размер таблицы.

 

 

2.5 Листинг программы

unit p1;

 

interface

 

uses

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

  Dialogs, StdCtrls, Grids, Math, ComCtrls, ExtCtrls;

 

const

  fFigSize: integer = 10;

 

type

  TFigure = class

    public

      x,y: integer;

      num: integer;

      flag: integer;

      val: integer;

      p: integer;

  end;

 

  TLine = class

    public

      i1, i2: integer;

      val: integer;

  end;

 

  TData = class

    public

      Width, Height: integer;

 

      Arr: array [0..99, 0..99] of integer;

      Left, Top: array[0..99] of integer;

 

      constructor Create;

                          

      procedure Reset;

 

      procedure Assign( data: TData );

      procedure AssignLT( data: TData );

 

      function NoNulls: integer;

      function Min: integer;

  end;

 

  TEquation = record

    p1, p2: integer;

    sum: integer;

    solved: boolean;

  end;

 

  TVar = record

    v: integer;

    solved: boolean;

  end;

 

  TEqSolve = class

    public

      Eq: array [0..100] of TEquation;

      fV: array [0..100] of TVar;

 

      fEqCount, fVarCount, fH: integer;

 

      function GetU( index: integer ): TVar;

      function GetV( index: integer ): TVar;

 

      procedure AddEq( p1, p2, s: integer );

     

 

      constructor Create( h, v_c: integer );

      procedure Solve;

 

      property U[index: integer]: TVar read GetU;

      property V[index: integer]: TVar read GetV;

  end; {}

 

  TForm1 = class(TForm)

    Memo1: TMemo;

    PageControl1: TPageControl;

    TabSheet1: TTabSheet;

    TabSheet2: TTabSheet;

    Button1: TButton;

    Button3: TButton;

    StringGrid1: TStringGrid;

    Button2: TButton;

    Panel1: TPanel;

    PaintBox1: TPaintBox;

    Button6: TButton;

    Button7: TButton;

    Button8: TButton;