Оптимизация транспортных издержек автопарка деревообрабатывающего завода

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

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

Продукция ДЗ поставляется в строительные организации ближайших регионов. Заготовки на ДЗ поставляются с нескольких сырьевых БАЗ.

Известны все расстояния между ДЗ и потребителями, а так же между ДЗ и сырьевыми базами.

Известны объемы поставок (эквивалентные 20 кубам) для каждого потребителя и соответственно объемы необходимого сырья из условия, что на каждые 20 м³ готовой продукции расходуется 30 м³ сырья.

Известно кол-во транспортных средств каждого типа в составе автопарк.

Известно количество расходуемого топлива на каждые 100 км при средней скорости перевозки 70 км/ч для каждого транспортного средства, тип топлива (А-80) и его стоимость.

Необходимо минимизировать транспортные издержки автопарка ДЗ при условии полной поставки продукции и необходимого сырья.

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

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

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

В составе завода имеются транспортные средства r типов ()

Для формальной записи задачи введем переменные булевого типа:

1, если используется k-e транспортное средство типа r для доставки сырья от i-го

Xirk = поставщика;

0, в противном случае

1, если используется k-e транспортное средство типа r для доставки готовой продукции до j-го потребителя;

Yjrk =

0, в противном случае Также известны технические характеристики транспортных средств каждого типа:

количество транспортных средств данного типа: Kr;

грузоподъемность: Gr;

расход топлива на каждые 100 километров пути: Zr;

цена 1л. топлива: Lr.

Оптимизационная модель может быть записана в следующем виде:

В качестве критерия оптимизации возьмем следующую функцию:

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

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

1) на объем необходимого сырья

Сырья

2) на объем вывозимой продукции

Продукции

3) на использование транспортных средств

4) на количество обслуживаемых потребителей Метод решения: Метод ветвей и границ на основе двухэтапного симплекс метода Так как некоторые переменные являются булевыми и принимают фиксированные значения: 0 и1, то это задача целочисленного линейного программирования (далее ЦЛП). Поэтому методом решения выбран метод ветвей и границ. Суть метода:

Метод ветвей и границ.

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

Если мы получим оптимальные целочисленные решения задачи ЛП — 0, то они являются также и оптимальными решениями задачи ЦЛП.

Если мы не получим целочисленных решений, то целевая функция f0 задачи ЛП — 0 становится верхней границей возможных оптимальных значений f задачи ЦЛП, потому что значение целевой функции f при введении в дальнейшем новых ограничений для получения оптимальных целочисленных решений уменьшается (увеличивается).

Затем производится ветвление по одному из нецелочисленных оптимальных решений задачи ЛП — 0, целью которого является разбиение множества допустимых решений на 2 подмножества путем построения дополнительных ограничений таким образом, чтобы исключить нецелочисленную точку x0* и сделать решение, по крайней мере одной из задач, целочисленным по одной выбранной координате xk.

Ограничения, введенные при ветвлении, добавляются к ограничениям задачи ЛП — 0. В каждой из вершин находим оптимальные решения полученных путем добавления новых ограничений задач ЛП — 1 и ЛП — 2. Если ни у одной из них мы не получили целочисленных оптимальных решений, то мы выбираем ту вершину, в которой получено наибольшее значение целевой функции и производим дальнейшее ветвление. Так продолжается до получения целочисленного оптимального решения одной из задач ЛП.

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

Контрольный пример Количество поставщиков сырья: I = 2

Количество потребителей: J = 4

Количество типов транспортных средств: R = 3

Транспортные средства для поставки готовой продукции

Транспортные средства для поставки сырья

Расчет:

Таким образом, автопарку ДЗ необходимо развести 280 м³ продукции и завести 420 м³ сырья.

Критерий:

Ограничения:

на объем необходимого сырья на объем вывозимой продукции

на использование транспортных средств

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

Подставим константы:

В критерий:

В ограничения:

Результат расчета контрольного примера:

Листинг программы контрольного примера

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, Grids;

const

EPS = 1E-6;

MaxSizeArray = 40;

MaxDouble = 1.7E+308;

MaxIteration = 10 000;

type

TForm1 = class (TForm)

Label1: TLabel;

Edit1: TEdit;

SG1: TStringGrid;

Label2: TLabel;

Edit2: TEdit;

SG2: TStringGrid;

Label3: TLabel;

SG3: TStringGrid;

Button1: TButton;

Label4: TLabel;

Label5: TLabel;

Edit3: TEdit;

Edit4: TEdit;

procedure FormCreate (Sender: TObject);

procedure SG2KeyPress (Sender: TObject; var Key: Char);

procedure Button1Click (Sender: TObject);

procedure SG3KeyPress (Sender: TObject; var Key: Char);

procedure Edit1Change (Sender: TObject);

procedure Edit2Change (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

TArr = array[1.5,1.5] of Real;

TMatr = array [0.MaxSizeArray, 0. MaxSizeArray] of double;

var

Form1: TForm1;

I, J: Integer;

R: array [1.3] of integer;

Vprod, Vsir: integer;

C: TArr;

n, n1, n2: word; // Число строк, номер строки (i)

m, m1: word; // Число столбцов, номер столбца (j)

A, a1, a2: TMatr;

X, x1, x2: TArr; // Коэффициенты целевой функции

CB: array [1.MaxSizeArray] of double; // Коэффициенты базисных переменных

NB: array [1.MaxSizeArray] of word; // Номера базисных переменных

Z: array [1.MaxSizeArray] of double; // Строка оценок

mi, mj: word; // Ключевые строка и столбец

min: double;

it: integer;

sign: array [1.MaxSizeArray] of boolean;

NN, MM, PP, LL, FF, TT: word;

implementation

{$R *.dfm}

procedure TForm1. FormCreate (Sender: TObject);

Var

u:integer;

begin

I:=StrToInt (Edit1.Text);

For u:=1 to I do

SG1.Cells[0,u]: =IntToStr (u);

SG1.Cells[0,0]:='№';

SG1.Cells[1,0]:='Расстояние, км.';

SG1.Cells[2,0]: ='Объем сырья, м3';

SG1.Cells[1,1]: ='70';SG1.Cells[1,2]:='110';

SG1.Cells[2,1]:='100';SG1.Cells[2,2]:='350';

J:=StrToInt (Edit2.Text);

For u:=1 to J do

SG2.Cells[0,u]: =IntToStr (u);

SG2.Cells[0,0]:='№';

SG2.Cells[1,0]:='Расстояние, км.';

SG2.Cells[2,0]: ='Объем поставки, м3';

SG2.Cells[1,1]: ='92';SG2.Cells[1,2]:='240';SG2.Cells[1,3]:='170';SG2.Cells[1,4]:='210';

SG2.Cells[2,1]:='40';SG2.Cells[2,2]:='100'; SG2. Cells[2,3]: ='60';SG2.Cells[2,4]:='80';

For u:=1 to 3 do

SG3.Cells[0,u]: =IntToStr (u);

SG3.Cells[0,0]:='№';

SG3.Cells[1,0]:='Количество';

SG3.Cells[2,0]:='Грузоподъемность, м3';

SG3.Cells[3,0]: ='Расх. топл. на 100 км';

SG3.Cells[4,0]: ='Цена 1л. топлива, руб.';

SG3.Cells[1,1]: ='2';SG3.Cells[1,2]:='6';SG3.Cells[1,3]:='14';

SG3.Cells[2,1]:='20';SG3.Cells[2,2]:='40';SG3.Cells[2,3]:='30';

SG3.Cells[3,1]:='20';SG3.Cells[3,2]:='22.5';SG3.Cells[3,3]:='28.3';

SG3.Cells[4,1]:='13.5';SG3.Cells[4,2]:='13.5'; SG3. Cells[4,3]: ='13.5';

Vprod:=0;

for u:=1 to j do

VProd:=Vprod + StrToInt (SG2.Cells[2,u]);

edit3.Text:=IntToStr (VProd);

VSir:=Round (3/2*VProd);

edit4.Text:=IntToStr (Vsir);

For u:=1 to 3 do

R[u]: =StrToInt (SG3.Cells[1,U]);

end;

procedure TForm1. SG2KeyPress (Sender: TObject; var Key: Char);

var

u: integer;

begin

Vprod:=0;

for u:=1 to j do

Begin

if SG2. Cells[2,u]='' then SG2. Cells[2,u]: ='0';

VProd:=Vprod + StrToInt (SG2.Cells[2,u]);

end;

edit3.Text:=IntToStr (VProd);

VSir:=Round (3/2*VProd);

edit4.Text:=IntToStr (Vsir);

end;

procedure Simplex (var d: TMatr; var y: TArr); // Симплекс метод

var

i, j: word;

cba: double;

begin

for i:=1 to n do

begin

if sign[i] then d[i, m+i]: =-1

else d[i, m+i]: =1; // Введем дополнительные переменные

NB[i]: =m+i; // и занесем номер базисной переменной

CB[i]: =0;

end;

m:=m+n; // Изменим размерность массива на кол-во доп. переменных

it:=0;

repeat

// ListScore;

for j:=1 to m do

begin

cba:=0;

for i:=1 to n do cba:=cba+CB[i]*d[i, j];

end;

min:=0; // Поиск ключевого столбца

mj:=0;

for j:=1 to m do

if min>Z[j] then

begin

min:=Z[j];

mj:=j;

end;

if mj=0 then break; // Ключевой столбец не найден — Некуда идти

min:= MaxDouble; // Поиск ключевой строки

mi:=0;

for i:=1 to n do

begin

if (d[i, mj]<>0) and (min>abs (d[i, 0]/d[i, mj])) and (nb[i]>m-n) then

begin

min:=d[i, 0]/d[i, mj];

mi:=i;

end;

end;

if mi=0 then break; // Ключевая строка не найдена — Некуда идти

min:=d[mi, mj];

// JordanGauss (d);

for i:=1 to n do

for j:=0 to m DO

if (i<>mi) and (j<>mj) then

d[i, j]: =d[i, j]-d[i, mj]*d[mi, j]/d[mi, mj];

for j:=0 to m do d[mi, j]: =d[mi, j]/min;

for i:=1 to n do if i<>mi then d[i, mj]: =0;

NB[mi]:=mj;

inc (it);

until it>MaxIteration-1;

end;

function CheckForFrac (x: TArr): integer;

var

i: integer;

begin

Result := 0;

for i := 1 to n1 do

if Frac (x[i, 1]) <> 0 then result := i;

end;

function Func (x: TArr): Real;

var

i: integer;

begin

Result := 0;

for i := 1 to n1 do

Result := result + c[i, 2]*x[i, 1];

end;

procedure correction (var x: TArr);

var

i: integer;

begin

for i := n1-MM-NN+1to n1 do

if x[i, 1] > 0 then x[i, 1] := 1;

end;

procedure MVG;

var

p: integer;

b: TMatr;

begin

n2 := n;

n1 := n;

m1 := m;

b := a;

simplex (a, x);

correction (x);

while CheckForFrac (x) <> 0 do

begin

a := b;

p := CheckForFrac (x);

inc (n2);

n := n2;

m := m1;

a2 := a;

a2[n, 0] := int (a[p, 0])+1;

a2[n, p] := 1;

sign[n] := true;

simplex (a2, x2);

a1 := a;

a1[n, 0] := int (a[p, 0]);

a1[n, p] := 1;

sign[n] := false;

simplex (a1, x1);

if (CheckForFrac (x1)=0) or (CheckForFrac (x1)=0)then

begin

if (CheckForFrac (x1)=0) then x := x1

else x := x2;

exit;

end

else

if (CheckForFrac (x1)>CheckForFrac (x2)) then

begin

a := a1;

x := x1;

end

else

begin

a := a2;

x := x2;

end;

correction (x);

end;

end;

procedure TForm1. Button1Click (Sender: TObject);

var

u:integer;

k3:Array [1.100] of integer;

min, min2: Real;

NK:integer;

i1,i2:integer;

ok:Boolean;

summa:Real;

flag:Boolean;

KM1,KM2: integer;

begin

summa:=0;

For u:=1 to I do

summa:=summa+Round (StrToInt (SG1.Cells[2,u])/30−0.4);

if (summa>StrToInt (SG3.Cells[1,3]))

and (StrToInt (SG3.Cells[1,3])*30

Begin

Application.MessageBox ('Нехватка транспортных средств для сырья','Error');

Exit;

End;

min2:=0;

For u:=1 to I do

C[u, 3]: =StrToInt (SG1.Cells[1,U])*28.3*13.5/100;

min:=1 000 000;

NK:=0;

FillChar (k3,sizeOf (k3), 0);

repeat

if nk<=R[3] then

Begin

ok:=true;

For i2:=1 to I do

if k3[i2]*StrToInt (SG3.Cells[2,3])>StrToInt (SG1.Cells[2,i2])

then ok:=false;

if ok then

begin

summa:=0;

For i2:=1 to I do

summa:=summa+k3[i2]*StrToInt (SG3.Cells[2,3]);

if summa>=VSir then // ОГРАничение на объем сырья

begin

summa:=0;

For i2:=1 to I do

summa:=summa+k3[i2]*C[i2,3];

if min>summa then min:=summa;

end;

end;

End;

i1:=1;

inc (nk);

inc (k3[1]);

While k3[i1]=R[3]+1 do

Begin

k3[i1]: =0;

i1:=i1+1;

inc (k3[i1]);

nk:=nk-R[3];

End;

Until NK=R[3]*I;

if min=1 000 000 then

begin

Application.MessageBox ('Объем сырья у поставщиков меньше необходимого','Error');

exit;

End;

min2:=min;

// к потребителям

For u:=1 to J do

Begin

C[u, 1]: =StrToInt (SG2.Cells[1,U])*20*13.5/100;

C[u, 2]:=StrToInt (SG2.Cells[1,U])*22.5*13.5/100;

End;

min:=1 000 000;

FillChar (k3,sizeOf (k3), 0);

repeat

if nk<=(R[1]+R[2]) then

Begin

// ограничение на использование транспортных средств

Flag:=false;

KM1:=0;

KM2:=0;

For i2:=1 to j do

KM1:=KM1+K3[i2];

For i2:=j+1 to j*2 do

KM2:=KM2+K3[i2];

if (KM1=StrToInt (SG3.Cells[1,1]))

and (KM2=StrToInt (SG3.Cells[1,2]))

then Flag:=true;

if flag then

begin

// ОГРАничение на объем продукции

ok:=true;

For i2:=1 to j do

begin

if k3[i2]*StrToInt (SG3.Cells[2,1])+k3[i2+j]*StrToInt (SG3.Cells[2,2])

<>StrToInt (SG2.Cells[2,i2])

then ok:=false;

end;

if ok then

begin

summa:=0;

For i2:=1 to J do

summa:=summa+k3[i2]*C[i2,1]+k3[i2+j]*C[i2,2];

if min>summa then min:=summa;

end;

end;

End;

i1:=1;

inc (nk);

inc (k3[1]);

While k3[i1]=R[1]+R[2]+1 do

Begin

k3[i1]: =0;

i1:=i1+1;

inc (k3[i1]);

nk:=nk-(R[1]+R[2]);

End;

Until NK=(R[1]+R[2])*j*2;

if min=1 000 000 then

begin

Application.MessageBox ('Нехватка транспортных средств для развозки продукции','Error');

Exit;

End;

min2:=min2+min;

Application.MessageBox (PAnsiChar (FloatToStr (min2)),'Минимальные затраты, руб.')

end;

procedure TForm1. SG3KeyPress (Sender: TObject; var Key: Char);

var

u:integer;

begin

For u:=1 to 3 do

R[u]: =StrToInt (SG3.Cells[1,U]);

end;

procedure TForm1. Edit1Change (Sender: TObject);

var

u:integer;

begin

if Edit1. Text='' then Edit1. Text:='0';

if StrToInt (Edit1.Text)=0 then sHOWmESSAGE ('Количество поставщиков не может быть равным нолю')

else

BEGIN

SG1.RowCount:=StrToInt (Edit1.Text)+1;

I:=StrToInt (Edit1.Text);

For u:=1 to I do

SG1.Cells[0,u]: =IntToStr (u);

end;

end;

procedure TForm1. Edit2Change (Sender: TObject);

var

u:integer;

begin

if Edit2. Text='' then Edit2. Text:='0';

if StrToInt (Edit2.Text)=0 then sHOWmESSAGE ('Количество потребителей не может быть равным нолю')

else

Begin

SG2.RowCount:=StrToInt (Edit2.Text)+1;

J:=StrToInt (Edit2.Text);

For u:=1 to J do

SG2.Cells[0,u]: =IntToStr (u);

End;

end;

end.