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

Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшими могут быть совершенно разные решения. Все зависит от выбранного или заданного критерия. На практике оказывается, что в большинстве случаев понятие «наилучший» может быть выражено количественными критериями - минимум затрат, минимум времени, максимум прибыли и т.д. Поэтому возможна постановка математических задач отыскания оптимального (optimum - наилучший) результата, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются задачами оптимизации. Оптимальный результат, как правило, находится не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. Чтобы решить практическую задачу надо перевести ее на математический язык, то есть составить ее математическую модель.

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

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

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

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

Целью данной курсовой работы является изучение методов решения транспортной задачи: методы составления опорного плана и дальнейшая оптимизация перевозок. Рассмотрен пример решения транспортной задачи методом потенциалов. Задача реализована на языке программирования Object Pascal в визуальной среде разработки Delphi 6.0.

Глава 1. Теоретические основы задачи

1.1 Математическая постановка задачи

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

Транспортная задача ставится следующим образом: имеется n пунктов отправления А₁, А₂, А₄ ..., A_n. B которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a₁, а₂, ..., а_m единиц. Имеется m пунктов назначения B₁, В₂, …, В_n, подавшие заявки соответственно на b₁, b₂, ..., b_n единиц груза. Известны стоимости С_ij перевозки единицы груза от каждого пункта отправления A_i до каждого пункта назначения B_j. Все числа С_ij, образующие прямоугольную таблицу заданы (таблица 1). Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Таблица 1

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

Т.е. a_i = b_j (1)

Пусть X_ij - количество запасов, отправленных со склада i в магазин j, а C_ij - стоимость перевозки одного груза со склада i в магазин j. Очевидно, что X_ij ? 0 и C_ij ? 0.

В силу ограничений на возможность поставки товара со склада и спрос в магазинах величина X ij должна удовлетворять следующим условиям:

X_ij = a_{i ;} X_ij = b_j (2,3)

Z= C_ij X_ij > min (4)

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

(5).

Система (5) и будет служить в дальнейшем критерием оптимальности плана.

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

1.2 Нахождение опорного плана

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

Метод последовательной максимальной загрузки. Строим опорный план исходя из формулы:

X_ij=min (a_i, b_j) (6)

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

Общая схема построения начального опорного плана по методу максимальной загрузки такова:

1) Выбираем коммуникацию, которую можно больше всего загрузить.

2) Максимально ее загружаем в соответствии с формулами (2).

3) Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки производства и потребления:

a_i= a_i-X_ij; b_j= b_j-X_ij ;

4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления:

если a_i = 0 - вычеркиваем i-тую строку;

если b_j = 0 - вычеркиваем j-тый столбец;

5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты все строки или столбцы.

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

, I - множество номеров пунктов производства;

, J - множество номеров пунктов потребления;

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

1.3 Транспортная задача с неправильным балансом

В предыдущих случаях рассматривалась только такая задачу о перевозках, в которой сумма запасов равна сумме заявок:

a_i=b_j;

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

Баланс транспортной задачи может нарушаться в 2-х направлениях:

1. Сумма запасов в пунктах отправлении превышает сумму поданных заявок

a_i>b_j;

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

a_i<b_j;

Условимся первый случай называть "Транспортной задачей с избытком запасов", а второй -- "Транспортной задачей с избытком заявок".

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов. В пунктах А₁ A₂, ..., A_n имеются запасы груза a₁, а₂, ..., а_n, пункты B₁, В₂, ..., В_m подали заявки b₁, b₂, ..., b_m, причём

a_i>b_j;

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые -- остаются равенствами.

X_i,j a_i (i=1 …, n ).

X_i,j = b_j (j=1 …, m ).

Мы умеем решать задачу линейного программирования, в какой бы форме -- равенств или неравенств ни были бы заданы её условия. Поставленная задача может быть решена, например, обычным симплекс-методом. Однако задачу можно решить проще, если искусственным приемом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся m пунктов назначения B₁, В₂, ..., В_m, введём ещё один, фиктивный, пункт назначения В_m+1 которому припишем фиктивную заявку, равную избытку запасов над заявками,

B_m+1 = a_i - b_j;

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b_m+1 будем считать равным нулю. Введением фиктивного пункта назначения В_m+1 с его заявкой b_m+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A_n+1 с запасов a_n+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

1.4 Метод потенциалов

Если план действительно оптимален, то система (5) будет выполняться, т.е.:

1) для каждой занятой клетки транспортной таблицы сумма потенциалов должна быть равна С_ij для этой клетки;

2) для каждой незанятой клетки сумма потенциалов не больше (меньше или равно) C_ij.

Число r=m+n-1, равное рангу системы (1) , называется рангом транспортной задачи. Если число заполненных клеток (X_ij ? 0) в таблице равно r, то план называется невырожденным, а если это число меньше r, то план вырожденный - в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r.

Построим для каждой свободной переменной плана числа («невязки» или «косвенные тарифы») и они должны быть положительны. Так как число потенциалов равно 9, а система состоит из 8 уравнений, то для нахождения какого-либо решения этой системы необходимо первому из потенциалов придать произвольное значение (например: ). Далее последовательно находим значения всех потенциалов.

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

1) одна клетка пустая, все остальные занятые;

2) любые две соседние клетки находятся в одной строке или в одном столбце;

3) никакие 3 соседние клетки не могут быть в одной строке или в одном столбце.

Что характерно, для этой точки (впрочем как и для других) мы можем построить только один цикл. Каждой клетке цикла приписываем определенный знак: поочередно «+» и «-» с начала цикла. В клетках с “+” - увеличиваем загрузку, а в клетках с “-” - уменьшаем. Величина, на которую увеличиваем или уменьшаем всегда одна и она определяется из условия:

, где - содержимое клеток со знаком “-”.

1.5 Пример решения задачи

Даны 4 поставщика с запасами груза А=(15, 20, 10, 25) и 5 потребителей с объемами заявок В=(5, 18, 17, 22, 8). Стоимости перевозки от поставщиков к потребителям указаны в таблице 2.

Таблица 2.

Целевая функция в данной задаче выглядит следующим образом: Z=25•X₁₁+30•X₁₂+40•X₁₃+15•X₁₄+10•X₁₅+20•X₂₁+18•X₂₂+5•X₂₃+27•X₂₄+35•X₂₅+15•X₃₁+25•X₃₂+33•X₃₃+16•X₃₄+3•X₃₅+10•X₄₁+7•X₄₂+28•X₄₃+12•X₄₄+8•X₄₅

Найдем опорный план при помощи метода минимальных затрат

Таблица 4.

Римскими цифрами указан порядок итераций:

I. ; ; ; - 5 столбец исключен.

II. ; ; ; - 3 столбец исключен.

III. ; ; ; - 2 столбец исключен.

IV. ; ; ; - 1 столбец исключен.

V. ; ; ; - 1 строка исключена.

VI. ; ; ; - 3 строка исключена.

VII. ; ; ; - 4 строка исключена.

VIII. ; ; ; - 2 строка и 4 столбец исключены.

В результате получили следующий опорный план:

Целевая функция при данном плане поставок

Определяем значения всех потенциалов, предположив, что U₁=0

После того, как все потенциалы найдены, можно искать :

Видно, что и меньше нуля, значит существующий опорный план можно улучшить. Поскольку , нужно ввести в базис вектор, соответствующий клетке (2; 1), для чего загрузить ее некоторым количеством единиц груза. Но, так как мы, увеличивая загрузку (2; 1), нарушаем баланс строк и столбцов распределительной таблицы, то следует изменить объемы поставок в ряде других занятых клеток. А чтобы число базисных переменных осталось прежним, необходимо вывести из базиса одну переменную. Выводится обычно та переменная, у которой загрузка в цикле минимальна.

(2; 1) - начальная точка цикла;

Каждой клетке цикла приписываем определенный знак: (2;1)-“+”, (4;1)-“-”, (4;4)-“+” (2;4)-“-”.

Таблица 5.

, а значит из базиса будет выведена (2; 4), где в процессе реализации цикла загрузка уменьшится до 0.

Перейдем к новому опорному плану.

Таблица 6.

Находим значения каждого потенциала для этого плана:

Определяем

Все больше 0, следовательно выполнено условие оптимальности (5).

.

Целевая функция при этом плане:

Задача решена.

Глава 2. Программное обеспечение

2.1 Конструирование формы

Рис. 1.

Таблица 7. Описание формы (Form1)

Рис. 2.

Таблица 8. Конструирование формы (fmRezult)

2.2 Содержимое обработчиков событий

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, Grids;

type

Matrix=array [1..10] of array [1..10] of integer;

TForm1 = class(TForm)

sgC: TStringGrid;

Button1: TButton;

Label1: TLabel;

edA: TEdit;

Label2: TLabel;

edB: TEdit;

sgA: TStringGrid;

sgB: TStringGrid;

Label3: TLabel;

Label4: TLabel;

Button2: TButton;

Button3: TButton;

Button4: TButton;

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

function SummRow(a:Matrix; r:integer):integer;

function SummCol(a:Matrix; r:integer):integer;

var

Form1: TForm1;

a,b:array[1..10] of integer;

c,x: matrix;

m,n:integer;

implementation

uses Unit2;

{$R *.dfm}

function SummRow(a:Matrix; r:integer):integer;

var

i,k:Integer;

begin

k:=0;

for i:=1 to 10 do

k:=k+a[r,i];

Result:=k

end;

function SummCol(a:Matrix; r:integer):integer;

var

i,k:Integer;

begin

k:=0;

for i:=1 to 10 do

k:=k+a[i,r];

Result:=k

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

try

n:=StrToInt(edA.Text);

m:=StrToInt(edB.Text);

except

ShowMessage('Введите числа от 1 до 10');

Exit;

end;

sgA.Visible:=true;

sgA.Width:=sgA.DefaultColWidth*n+20;

sgA.ColCount:=n;

sgB.Width:=sgB.DefaultColWidth*m+20;

sgB.Visible:=true;

sgB.ColCount:=m;

end;

procedure TForm1.Button3Click(Sender: TObject);

var

i,j:integer;

begin

sgC.Visible:=true;

sgC.Width:=sgC.DefaultColWidth*(m+1)+20;

sgC.Height:=sgC.DefaultRowHeight*(n+1)+20;

sgC.ColCount:=m+1;

sgC.RowCount:=n+1;

for i:=1 to n do

begin

try

a[i]:=StrToInt(sgA.Cells[i-1,0]);

except

on EConvertError do

begin

ShowMessage('Введите числа без пробелов');

Exit

end

end;

sgC.Cells[0,i]:=IntToStr(a[i]);

end;

for j:=1 to m do

begin

b[j]:=StrToInt(sgB.Cells[j-1,0]);

sgC.Cells[j,0]:=IntToStr(b[j])

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i,j,Xn,Xm,

k,t,Row,Col,min,

p,q:integer;

Z,SSS:longint;

Cx:matrix;//флаг заполнения

U,V:array [1..10] of integer; //потенциалы

Uf,Vf:array [1..10] of Boolean;//флаг нахождения потенциалов

label EndPoisk,EndPoisk1,EndCikl,Opti;

begin

sss:=0;

for i:=1 to n do

for j:=1 to m do

c[i,j]:=StrToInt(sgC.Cells[j,i]) ;

{проверка на открытую модель}

Xm:=0;Xn:=0;

for i:=1 to n do

Xn:=Xn+a[i];

for j:=1 to m do

Xm:=Xm+b[j];

if Xm<>Xn then

begin

if Xm>Xn then

begin

inc(n);

a[n]:=Xm-Xn;

for i:=1 to m do

c[n,i]:=0;

end;

if Xm<Xn then

begin

inc(m);

b[m]:=Xn-Xm;

for j:=1 to n do

c[j,m]:=0;

end;

end;

{заполнение методом минимальных затрат}

for i:=1 to n do

for j:=1 to m do

Cx[i,j]:=0;

for i:=1 to n do

Uf[i]:=false;

for j:=1 to m do

Vf[j]:=false;

Z:=0;

for i:=1 to n do

for j:=1 to m do

if c[i,j]>Z then Z:=c[i,j];

repeat

for i:=1 to n do

if a[i]-SummRow(x,i)=0 then Uf[i]:=true;

for j:=1 to m do

if b[j]-SummCol(x,j)=0 then Vf[j]:=true;

min:=Z;

for i:=1 to n do

for j:=1 to m do

if (c[i,j]<min) and (Cx[i,j]<>1) and (a[i]-SummRow(x,i)>0)

and (b[j]-SummCol(x,j)>0) then

begin

min:=c[i,j];

Row:=i;

Col:=j;

end;

if a[Row]-SummRow(x,Row)<b[Col]-SummCol(x,Col) then

begin

x[Row,Col]:=a[Row]-SummRow(x,Row);

end

else

x[Row,Col]:=b[Col]-SummCol(x,Col);

sss:=0;

for i:=1 to n do

for j:=1 to m do

if x[i,j]>0 then

begin

sss:=sss+x[i,j];

Cx[i,j]:=1;

end;

until sss>=Xn;

{вывод опорного плана}

fmResult.Show;

with fmResult do

begin

sgResult.ColCount:=m+1;

sgResult.RowCount:=n+1;

for i:=1 to n do

begin

sgResult.Cells[0,i]:=IntToStr(a[i]);

for j:=1 to m do

begin

sgResult.Cells[j,0]:=IntToStr(b[j]);

sgResult.Cells[j,i]:=IntToStr(x[i,j])

end;

end;

end;

Opti:

{метод потенциалов}

{проверка на вырожденность}

k:=0;

for i:=1 to n do

for j:=1 to m do

begin

Cx[i,j]:=0; //Считаем заполненые ячейки

if x[i,j]>0 then

begin

Cx[i,j]:=1;

inc(k);

end;

end;

if k<m+n-1 then //если план вырожденный

for t:=1 to m+n-1-k do

begin

for i:=1 to n do

for j:=1 to m do

if (Cx[i,j]=1) and (SummRow(Cx,i)+SummCol(Cx,j)<=2) then

begin

for Row:=1 to n do

if Cx[Row,j]=0 then

begin

Cx[Row,j]:=1;

goto EndPoisk1;

end;

end;

EndPoisk1:;

end;

{нахождение потенциалов}

for i:=1 to n do

Uf[i]:=false; //обнуляем флаги потенциалов

for j:=1 to m do

Vf[j]:=false;

U[1]:=0;

Uf[1]:=true;

repeat

for i:=1 to n do

for j:=1 to m do

begin

if (Uf[i])and (not Vf[j]) and (Cx[i,j]=1) then

begin

V[j]:=C[i,j]-U[i];

Vf[j]:=true;

end;

if (Vf[j]) and (not Uf[i]) and (Cx[i,j]=1) then

begin

U[i]:=C[i,j]-V[j];

Uf[i]:=true;

end;

end;

k:=0;

for i:=1 to n do //подсчет

if Uf[i] then inc(k); //найденных

for j:=1 to m do //потенциалов

if Vf[j] then inc(k);

until k=m+n;

{определяем косвенные тарифы}

k:=0;

for i:=1 to n do

for j:=1 to m do

if (Cx[i,j]=0) and (U[i]+V[j]>C[i,j]) then

begin //строим цикл пересчета

for q:=1 to m do

if (Cx[i,q]=1) and (q<>j) then

for p:=1 to n do

if (Cx[p,q]=1) and (p<>i) then

if (Cx[p,j]=1) and (c[p,j]<>0) then

begin

if x[i,q]<=x[p,j] then Min:=x[i,q]

else Min:=x[p,j];

x[i,j]:=x[i,j]+Min;

x[p,j]:=x[p,j]-min;

x[p,q]:=x[p,q]+min;

x[i,q]:=x[i,q]-min;

k:=1;

Cx[i,j]:=1;

if x[p,j]=0 then Cx[p,j]:=0;

if x[i,q]=0 then Cx[i,q]:=0;

goto EndCikl;

end;

end;

EndCikl:if k=1 then

begin

//k:=0;

inc(sss);

if sss>1000 then Exit;

goto Opti;

end

else

begin

z:=0;

for i:=1 to n do

for j:=1 to m do

Z:=Z+C[i,j]*StrToInt(fmResult.sgResult.Cells[j,i]);

fmResult.Label1.Caption:='Целевая функция: '+IntToStr(Z);

end;

end;

end.

unit Unit2;

interface

uses

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

Dialogs, Grids, StdCtrls;

type

TfmResult = class(TForm)

sgResult: TStringGrid;

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

fmResult: TfmResult;

i,j:integer;

implementation

uses Unit1;

{$R *.dfm}

procedure TfmResult.Button1Click(Sender: TObject);

var

z:integer;

begin

with fmResult do

begin

sgResult.ColCount:=m+1;

sgResult.RowCount:=n+1;

for i:=1 to n do

begin

sgResult.Cells[0,i]:=IntToStr(a[i]);

for j:=1 to m do

begin

sgResult.Cells[j,0]:=IntToStr(b[j]);

sgResult.Cells[j,i]:=IntToStr(x[i,j])

end;

end;

end;

Label2.Caption:='Оптимальный план перевозок';

z:=0;

for i:=1 to n do

for j:=1 to m do

Z:=Z+C[i,j]*x[i,j];

fmResult.Label1.Caption:='Целевая функция: '+IntToStr(Z);

end;

end.

2.3 Форма с результатами работы приложения

Заключение

Мы изучили методы решения транспортной задачи, рассмотрели случаи открытой модели, был приведен пример решения. В результате выполнения курсовой работы была создана программа, реализующая алгоритм решения транспортной задачи на языке Object Pascal в среде программирования Delphi. Цели данной курсовой работы достигнуты, задача решена.

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

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

1. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 2003

Гласс Р. Руководство по надежному программированию. М.: Финансы и статистика, 2000.

Касьянов В.Н. Методы оптимизации программ: Учеб. пособие. Новосибирск. Изд. НГТУ, 2001.

Кузнецов Ю. Н., Кузубов В. И., Волощеноко А. В. Математическое программирование. М., Высшая школа, 2002.

Размещено на Allbest.ru