Оптимизация программы "диспетчер-кодировщик"

(Множество допустимых решений {1,2,3,4,5,6,7,8,9,10})

Кол-во каналов n	D(n)	Q(n)	D(n)/ Dmax
1	645,52579	0,1455	0,54772
2	1022,88169	0,29016	0,8679
3	1178,57647	0,43154	1
4	1163,63188	0,56531	0,98732
5	1037,92631	0,68574	0,88066
6	859,33383	0,78713	0,72913
7	668,22719	0,86578	0,56698
8	479,72827	0,92148	0,40704
9	289,87136	0,95738	0,24595
10	88,68203	0,97848	0,07525

В множестве допустимых решений  выделим подмножество П - множество  парето-оптимальных решений. Решение  х принадлежит множеству Парето, если оно принадлежит исходному  множеству допустимых решений (Х), и  в Х не существует решения, которое было бы по всем критериям не хуже данного и хотя бы по одному лучше.

При помощи программы было получено множество Парето. (Парето-оптимальное множество {3,4,5,6,7,8,9,10})

В него не вошли точки W₁ = (645,52579; 0,1455) и    W₂ = (1022,88169; 0,29016):

Кол-во каналов n	D(n)	Q(n)	D(n)/ Dmax
3	1178,57647	0,43154	1
4	1163,63188	0,56531	0,98732
5	1037,92631	0,68574	0,88066
6	859,33383	0,78713	0,72913
7	668,22719	0,86578	0,56698
8	479,72827	0,92148	0,40704
9	289,87136	0,95738	0,24595
10	88,68203	0,97848	0,07525

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

 

Метод линейной свертки:

Используя ту же программу, получили:

 

	S(n)
3	624,84835
4	616,99059
5	550,42324
6	455,81688
7	354,56733
8	254,68908
9	154,08179
10	47,46136

 

- есть искомое оптимальное значение n=n_опт числа модулей, непосредственно занятых обслуживанием запросов. Т.е. это будет третья точка W₃(1178,57647; 0,43154).

 

 Метод идеальной точки:

    Ищем такое оптимальное решение - точку в пространстве критериев, которая находилась бы ближе всего к идеальной точке (1;1):  (W_опт , W^*) = S_min

То решение, для которого величина r окажется наименьшей в методе идеальной точки, и будет искомым оптимальным значением n=n_опт числа модулей, непосредственно занятых обслуживанием запросов.

 

Используя ту же программу, получили:

 

	S(n)
3	0,56846
4	0,43487
5	0,33616
6	0,34451
7	0,45334
8	0,59814
9	0,75525
10	0,925

 

 

 

 

Методом идеальной точки получили n_опт = arg min {S(n)} = 5.

Т.е. это точка W₅(1037,92631; 0,68574).

 

Заключение

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

 

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

 

1. Г.В.Данилов, Г.С.Филиппов, Я.И.Якумайте “Некоторые вероятностные задачи "о встрече" в моделях массового обслуживания.” ВИНИТИ, N 8166, 1988.
2. “Системный анализ и исследование операций”. Конспект лекций
3. Г.В. Данилов. Оптимизация работы блока выполнения запросов в автоматизированной информационной системе. Индивидуальные задания и методические указания к выполнению курсовой работы. Ухта, 1999

 

Интерфейс программы

Зелёными квадратиками показаны точки, входящие в Парето-оптимальное множество (т. 3-10).

Красными квадратиками показаны точки, невходящие в Парето-оптимальное  множество (т. 1-2).

Жёлтым кружочком показана лучшая точка, полученная методом линейной свёртки (т. 3).

Черным квадратиком показана лучшая точка, полученная методом идеальной точки (т. 5)

Черным квадратиком показана идеальная  точка (1;1) – она соединена с  лучшей точкой,полученной методом идеальной  точки (т. 5)

 

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

unit Unit1;

 

interface

 

uses

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

  Dialogs, ComCtrls, StdCtrls, ExtCtrls, XPMan, Grids, TeEngine, Series,

  TeeProcs, Chart;

 

type

  TForm1 = class(TForm)

    Edit1: TLabeledEdit;

    UpDown1: TUpDown;

    Button1: TButton;

    SG1: TStringGrid;

    Button2: TButton;

    Chart1: TChart;

    SG2: TStringGrid;

    SG3: TStringGrid;

    Label1: TLabel;

    SG4: TStringGrid;

    Label2: TLabel;

    Button3: TButton;

    Button4: TButton;

    pom: TPointSeries;

    Button5: TButton;

    mls: TPointSeries;

    graf: TPointSeries;

    mit: TLineSeries;

    Button6: TButton;

    Shape1: TShape;

    Shape2: TShape;

    Shape3: TShape;

    Shape4: TShape;

    Shape5: TShape;

    Shape6: TShape;

    Shape7: TShape;

    Shape8: TShape;

    Shape9: TShape;

    Shape10: TShape;

    Timer1: TTimer;

    Label3: TLabel;

    Label4: TLabel;

    procedure Button1Click(Sender: TObject);

    function fact(x:integer):real;

    function _t(x:real):string;

    procedure Button2Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure Button3Click(Sender: TObject);

    procedure Button4Click(Sender: TObject);

    procedure Button5Click(Sender: TObject);

    procedure Button6Click(Sender: TObject);

 

  private

    { Private declarations }

  public

    { Public declarations }

 

    lambda, f1,f2,f3,f4, d,e1,e2, T, N,M, Rd,Rq, uy, P,R, Pnm, p0, Ro, k, Ksr:real;

    Lsys, Wsys, hiN, Locher, Dmax:real;

    nvar,imin:integer;

    Doh, Qops, Sn:array [1..10] of real;

 

  end;

 

var

  Form1: TForm1;

 

implementation

 

{$R *.dfm}

 

uses math;

 

procedure TForm1.Button1Click(Sender: TObject);

var i,j,imax, index:integer;

    max,per,min:real;

begin

graf.Clear;

pom.Clear;

mls.Clear;

mit.Clear;

 

imax:=0;

nvar:=strtoint(edit1.Text);

Dmax:=0;

 

for i:=0 to 10 do

  for j:=1 to 10 do

    begin

      sg1.Cells[i,j]:='';

      sg2.Cells[i,j]:='';

      sg3.Cells[i,j]:='';

      sg4.Cells[i,j]:='';

    end;

 

F1:=nvar;

F2:=0.001*nvar;

F3:=0.1*nvar;

F4:=0.01*nvar;

 

k:=10;

uy:=0.93+F2;

 

if uy>1 then

  R:=1

else

  R:=k*power(uy,k - 1)*(1 -(k - 1)/k*uy);

 

P:=1-R;

 

lambda:=R*100;

T:=0.08;                //время

ro:=lambda*T;

 

d:=100+F3;              //доход за один запрос

e1:=1000+F3;            //штраф за единицу времени

e2:=50+F3;              //убытки от неучастия в течение единицы времени одного модуля

 

n:=10;                  //количество каналов

m:=3;                   //количество заявок в очереди

 

Rd:=0.5+F4;

Rq:=1-Rd;

 

for i:=1 to 10 do

    begin

     hiN:=ro/i;

     p0:=1;

 

     for j:=1 to i do

     p0:=p0 + power(ro,j)/fact(j);

 

     p0:=1/(p0 + power(ro,i + 1)*(1 - power(hiN,m))/(i*fact(i)*(1 - hiN)));

     pnm:= p0*power(ro,i + m)/(power(i,m)*fact(i));

     Qops[i]:=1-pnm;

     Ksr:=ro*(1-pnm);

     Locher:=Power(ro,i + 1)*p0*(1 - (m + 1)*Power(hiN,m) + m*Power(hiN,m + 1))/

           (i*fact(i)*(1 - hiN)*(1 - hiN));

     Lsys:=Locher+Ksr;

     Wsys:=lsys/lambda;

     Doh[i]:=(d-e1*Wsys)*lambda*Qops[i]-e2*power(i,3/2);

 

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

     SG1.Cells[1,i]:=_t(Doh[i]);

     SG1.Cells[2,i]:=_t(Qops[i]);

    end;

 

max:=-10000000;

for i:=1 to 10 do

  if max<strtofloat(sg1.Cells[1,i]) then

    begin

      max:=strtofloat(sg1.Cells[1,i]);

      Dmax:=max;

      imax:=i;

    end;

 

for i:=1 to 10 do

begin

  per:=strtofloat(sg1.Cells[1,i])/max;

  sg1.Cells[3,i]:=_t(per);

end;

 

index:=1;

for i:=1 to 10 do

if i>=imax then

  begin

    SG2.Cells[0,index]:=SG1.Cells[0,i];

    SG2.Cells[1,index]:=SG1.Cells[1,i];

    SG2.Cells[2,index]:=SG1.Cells[3,i];

    inc(index);

  end;

 

max:=-1000000;

for i:=imax to 10 do

  begin

    Sn[i]:=rd*Doh[i]+rq*Qops[i];

    sg3.Cells[0,i-imax+1]:=sg1.Cells[0,i];

    sg3.Cells[1,i-imax+1]:=_t(Sn[i]);

    if max<Sn[i] then

      begin

        max:=Sn[i];

        imax:=i;

      end;

    if sg3.Cells[0,i-imax+1]='10' then break;

  end;

label1.Caption:='Метод линейной свертки: точка '+inttostr(imax);

 

for i:=imax to 10 do

begin

  if strtofloat(sg1.Cells[0,i])<=10 then

    begin

      sn[i]:=sqrt(sqr(1-strtofloat(sg1.Cells[3,i]))+sqr(1-strtofloat(sg1.Cells[2,i])));

      sg4.Cells[0,i-imax+1]:=_t(i);

      sg4.Cells[1,i-imax+1]:=_t(sn[i]);

    end

  else

    break;

end;

 

min:=1000000;

imin:=0;

for i:=imax to 10 do

  if min>strtofloat(sg4.Cells[1,i-imax+1]) then

  begin

    min:=strtofloat(sg4.Cells[1,i-imax+1]);

    imin:=i;

  end;

label2.Caption:='Метод идеальной точки: '+inttostr(imin);

 

button2.Enabled:=true;

button3.Enabled:=true;

button4.Enabled:=true;

button5.Enabled:=true;

end;

 

function TForm1.fact(x: integer): real;

var i, per:integer;

begin

per:=1;

for i:=1 to x do

  per:=per*i;

fact:=per;

end;

 

procedure TForm1.Button2Click(Sender: TObject);

var i:integer;

begin

 

for i:=1 to 10 do

  graf.AddXY(strtofloat(sg1.Cells[3,i]),strtofloat(sg1.Cells[2,i]))

end;

 

procedure TForm1.FormCreate(Sender: TObject);

begin

sg1.Cells[0,0] := 'n';

sg1.Cells[1,0] := 'D(n)';

sg1.Cells[2,0] := 'Q(n)';

sg1.Cells[3,0] := 'D(n)/Dmax';

sg2.Cells[0,0] := 'n';

sg2.Cells[1,0] := 'D(n)';

sg2.Cells[2,0] := 'D(n)/Dmax';

sg3.Cells[0,0] := 'n';

sg3.Cells[1,0] := 'S(n)';

sg4.Cells[0,0] := 'n';

sg4.Cells[1,0] := 'S(n)';

end;

 

function TForm1._t(x: real): string;

//var per:string;

begin

//per:=floattostr(x);

_t:=FormatFloat('0.#####',x)

end;

 

procedure TForm1.Button3Click(Sender: TObject);

var index, i:integer;

begin

pom.Clear;

index:=strtoint(sg3.Cells[0,1]);

for i:=index to 10 do

  pom.AddXY(strtofloat(sg1.Cells[3,i]),strtofloat(sg1.Cells[2,i]))

end;

 

procedure TForm1.Button4Click(Sender: TObject);

var index:integer;

begin

mls.Clear;

index:=strtoint(sg3.Cells[0,1]);

mls.AddXY(strtofloat(sg1.Cells[3,index]),strtofloat(sg1.Cells[2,index]))

end;

 

procedure TForm1.Button5Click(Sender: TObject);

var index:integer;

begin

mit.Clear;

mit.AddXY(strtofloat(sg1.Cells[3,imin]),strtofloat(sg1.Cells[2,imin]));

mit.AddXY(1,1);

end;

 

procedure TForm1.Button6Click(Sender: TObject);

begin

form1.Close;

end;

 

end.