Технологии программирования задач сетевой оптимизации

   =Join[,d];

   }];

 

 

system2={x21,2-x24,1Š0,

   -x21,2+x22,3Š-6,

   -x22,3-x24,3Š-5,

   x24,1+x24,3-x25,4Š7,

   x25,4Š4

   };

t={5,4,3,2,1};

p={0,1,2,3,4};

d={0,1,1,-1,-1};

system2a=system2;

system2a[[4]]=system2a[[4]]/.{x24,1®0};

system2a[[1]]=system2a[[1]]/.{x24,1®0};

={x24,1®0};

 

For[i=1,i£4,++i,

  {

   If[d[[ t[[i]] ]]Š1,

    d=Solve[ system2a[[ t[[i]] ]],x2p[[ t[[i]] ]],t[[i]]][[1]],

    d=Solve[ system2a[[ t[[i]] ]],x2t[[i]],p[[ t[[i]] ]]][[1]]];

   If[p[[  p[[ t[[i]] ]] ]]¹0,

    system2a[[ p[[ t[[i]] ]] ]]=system2a[[ p[[ t[[i]] ]] ]]/.d];

   =Join[,d];

   }];

 

 

system3={x31,2-x34,1-x35,1Š-10,

   -x31,2-x34,2Š-10,

   -x34,3Š-7,

   x34,1+x34,3+x34,2-x35,4Š9,

   x35,1+x35,4Š18

   };

t={5,3,4,2,1};

p={0,1,4,2,4};

d={0,1,1,-1,-1};

system3a=system3;

system3a[[4]]=system3a[[4]]/.{x34,1®0};

system3a[[1]]=system3a[[1]]/.{x34,1®0};

system3a[[5]]=system3a[[5]]/.{x35,1®0};

system3a[[1]]=system3a[[1]]/.{x35,1®0};

={x34,1®0,x35,1®0};

 

For[i=1,i£4,++i,

  {

   If[d[[ t[[i]] ]]Š1,

    d=Solve[ system3a[[ t[[i]] ]],x3p[[ t[[i]] ]],t[[i]]][[1]],

    d=Solve[ system3a[[ t[[i]] ]],x3t[[i]],p[[ t[[i]] ]]][[1]]];

   If[p[[  p[[ t[[i]] ]] ]]¹0,

    system3a[[ p[[ t[[i]] ]] ]]=system3a[[ p[[ t[[i]] ]] ]]/.d];

   =Join[,d];

   }];

 

Print["= ",];

Print["= ",];

Print["= ",];

 

 

R115,1=7x11,2+9x14,2+9x15,1+9x15,4/.d15,1;

R215,1=6x11,2+5x14,2+10x15,1+9x15,4/.d15,1;

R315,1=2x11,2+3x14,2+8x15,1+2x15,4/.d15,1;

 

R115,2=7x11,2+9x14,2+5x15,2+9x15,4/.d15,2;

R215,2=6x11,2+5x14,2+8x15,2+9x15,4/.d15,2;

R315,2=2x11,2+3x14,2+8x15,2+2x15,4/.d15,2;

 

R124,1=4x21,2+8x22,3+9x24,1+2x24,3+3x25,4/.d24,1;

R224,1=7x21,2+3x22,3+7x24,1+0x24,3+5x25,4/.d24,1;

R324,1=x21,2+5x22,3+2x24,1+3x24,3+4x25,4/.d24,1;

 

R134,1=2x31,2+9x34,1+4x34,2+5x34,3+7x35,4/.d34,1;

R234,1=6x31,2+0x34,1+2x34,2+2x34,3+7x35,4/.d34,1;

R334,1=5x31,2+6x34,1+0x34,2+2x34,3+8x35,4/.d34,1;

 

R135,1=2x31,2+4x34,2+5x34,3+9x35,1+7x35,4/.d35,1;

R235,1=6x31,2+2x34,2+2x34,3+7x35,1+7x35,4/.d35,1;

R335,1=5x31,2+0x34,2+2x34,3+x35,1+8x35,4/.d35,1;

 

 

R415,1=0x11,2+0x14,2+0x15,1+x15,4/.d15,1;

R415,2=0x11,2+0x14,2+0x15,2+x15,4/.d15,2;

R424,1=0x21,2+0x22,3+0x24,1+0x24,3+0x25,4/.d24,1;

R434,1=0x31,2+0x34,1+0x34,2+0x34,3+x35,4/.d34,1;

 

R435,1=0x31,2+0x34,2+0x34,3+0x35,1+x35,4/.d35,1;

 

D1=({

    {R115,1, R115,2, R124,1, R134,1},

    {R215,1, R215,2, R224,1, R234,1},

    {R315,1, R315,2, R324,1, R334,1}

   });

D2 = {{R415,1 , R415,2  ,R424,1 , R434,1}};

DD = Join [D1,D2];

Print ["Матрица DD = ",MatrixForm[DD]];

 

A1=556-(7x11,2+4x21,2+2x31,2+8x22,3+9x24,1+9x34,1+

        9x14,2+4x34,2+2x24,3+5x34,3+9x15,1+9x35,1+

        5x15,2+9x15,4+3x25,4+7x35,4)/././.;

A2=501-(6x11,2+7x21,2+6x31,2+3x22,3+7x24,1+5x14,2

        +2x34,2+2x34,3+10x15,1+7x35,1+8x15,2+9x15,4+

        5x25,4+7x35,4)/././.;

A3=307-(2x11,2+x21,2+5x31,2+5x22,3+2x24,1+6x34,1+3x14,2

        +3x24,3+2x34,3+8x15,1+x35,1+8x15,2+2x15,4+4x25,4

        +8x35,4)/././.;

 

A4=13-(x15,4+x35,4)/././.;

 

b1=A1-(R135,1 x35,1);

b2=A2-(R235,1 x35,1);

b3=A3-(R335,1 x35,1);

b4=A4-(R435,1 x35,1);

 

b = Transpose [{{b1 ,b2 ,  b3, b4}}];

Print ["Вектор b  = ",MatrixForm[b] ];

 

y = LinearSolve [DD ,b];

y=Simplify[Inverse[DD].({

      {b1},

      {b2},

      {b3},

      {b4}

     })];

MatrixForm[Inverse[DD]]

Print["вектор неизвестных = ",MatrixForm[y]];

 

rule1={x15,1®y[[1]][[1]],x15,2®y[[2]][[1]],x24,1®y[[3]][[1]],x34,1®y[[4]][[1]],x35,1®x35,1};

 

rule2={x11,2®x15,1(x11,2/.d15,1)+x15,2(x11,2/.d15,2)+(x11,2/.),

   x14,2®x15,1(x14,2/.d15,1)+x15,2(x14,2/.d15,2)+(x14,2/.),

   x15,4®x15,1(x15,4/.d15,1)+x15,2(x15,4/.d15,2)+ (x15,4/.),

   x21,2®x24,1(x21,2/.d24,1)+(x21,2/.),

   x22,3®x24,1(x22,3/.d24,1)+(x22,3/.),

   x24,3®x24,1(x24,3/.d24,1)+(x24,3/.),

   x25,4®x24,1(x25,4/.d24,1)+(x25,4/.),

  

   x31,2®x34,1(x31,2/.d34,1)+x35,1(x31,2/.d35,1)+

     (x31,2/.),

   x34,2®x34,1(x34,2/.d34,1)+x35,1(x34,2/.d35,1)+

     (x34,2/.),

   x34,3®x34,1(x34,3/.d34,1)+x35,1(x34,3/.d35,1)+

     (x34,3/.),

   x35,4®x34,1(x35,4/.d34,1)+x35,1(x35,4/.d35,1)+

     (x35,4/.)

   };

 

solution=Simplify[Join[rule1,rule2/.rule1]];

 

Print[Simplify[System/.solution]];

 

Print[solution];

 

GraphPlot[{1→2,4→2,5→4,5→2,1→2,2→3,4→3,5→4,4→1,1→2,4→2,5→4,5→3,5→1},VertexLabeling→True,DirectedEdges→True]

 

(* system1"*)

d15,1 = {x11,2®1,x14,2®-1,x15,4®-1,x15,1®1,x15,2®0};

d15,2 = {x11,2®0,x14,2®-1,x15,4®-1,x15,1®0,x15,2®1};

thread={5,4,2,1};

pred={0,1,0,2,4};

dir={0,1,0,-1,-1};

Print ["Характеристика леса покрывающих (остовных) деревьев"];

Print ["Thread = ", thread];

Print["Pred = ", pred];

Print ["Direction = ", dir];

Print ["Лес покрывающих деревьев  для потока №1"];

TreePlot[{5®4,4®2,1®2,3®3}, Left, 1, SelfLoopStyle®None, DirectedEdges®True, VertexLabeling®True]

Print ["Добавленная дуга  - x15,1  "];

Print ["Соответствующий характеристический  вектор d15,1 = ",d15,1];

TreePlot[{5®4, 5®1, 4®2, 1®2, 3®3}, Top, 1, SelfLoopStyle®None, DirectedEdges®True, VertexLabeling®True]

Print ["Добавленная дуга  -  x15,2  "];

Print ["Соответствующий характеристический  вектор d15,2 = " ,d15,2];

TreePlot[{5®4, 5®2, 4®2, 1®2, 3®3}, Top, 1, SelfLoopStyle®None, VertexLabeling®True, DirectedEdges®True]

 

(*system2*)

d24,1 = {x21,2®1,x24,3®-1,x22,3®1,x25,4®0,x24,1®1};

Print ["Характеристика леса покрывающих (остовных) деревьев"];

thread={5,4,2,1};

pred={0,1,0,2,4};

dir={0,1,0,-1,-1};

Print ["Thread = ", thread];

Print["Pred = ", pred];

Print ["Direction = ", dir];

thread={5,4,3,2,1}

pred={0,1,2,3,4}

dir={0,1,1,-1,-1}

Print ["Лес покрывающих деревьев для потока №2"];

TreePlot[{5®4,4®3,2®3,1®2},Top, 1, DirectedEdges®True, VertexLabeling®True]

Print ["Добавленная дуга  -  x24,1 "];

Print ["Соответствующий характеристический  вектор d24,1 = ",d24,1];

TreePlot[{5®4,4®3,2®3,1®2,4®1}, Top, 1, DirectedEdges®True, VertexLabeling®True]

 

(*system3*)

d34,1 ={x31,2®1,x34,2®-1,x34,3®0,x35,4®0,x34,1®1,x35,1®0};

d35,1 ={x31,2®1,x34,2®-1,x34,3®0,x35,4®-1,x34,1®0,x35,1®1};

thread={5,3,4,2,1};

pred={0,1,4,2,4};

dir={0,1,1,-1,-1};

Print ["Характеристика леса покрывающих (остовных) деревьев"];

Print ["Thread = ", thread];

Print["Pred = ", pred];

Print ["Direction = ", dir];

Print ["Лес покрывающих деревьев  для потока №3"];

TreePlot[{1®2,4®2,4®3,5®4},Top, 1, DirectedEdges®True, VertexLabeling®True]

Print ["Добавленная дуга  -  x34,1 "];

Print ["Соответствующий характеристический  вектор d34,1 = ",d34,1];

TreePlot[{1®2, 4®1, 4®2, 4®3, 5®4},Top, 1, DirectedEdges®True, VertexLabeling®True]

Print ["Добавленная дуга  -  x35,1 "];

Print ["Соответствующий характеристический  вектор d35,1  = ",d35,1];

TreePlot[{1®2,5®1,4®2,4®3,5®4}, Top, 1, DirectedEdges®True, VertexLabeling®True]

Null

 

 

Приложение В

 

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

 

public class Testing {

public static void main(String[] args) {

Scanner sc;

 int f;

 int [] d = new int [6];

 int [] p = new int [6];

 int [] t = new int [6];

 int [] Solve = new int[6];

String [] files = {"D:\\System_1.txt", "D:\\System_2.txt", "D:\\System_3.txt"};

String filename;

 for (f = 0; f<3; f++){

filename = files[f];

 try {

sc = new Scanner(new File(filename));

//System.out.print("direction : ");

for (int i = 1; i < 6; i++) {

         int x = sc.nextInt();

         d[i] = x;

 }        

   System.out.println();

for (int i = 1; i < 6; i++)

{

      int x = sc.nextInt();

      t[i] = x;

}        

for (int i = 1; i < 6; i++)

{

      int x = sc.nextInt();

      p[i] = x;

}  

for (int i = 1; i < 6; i++)

{

      int x = sc.nextInt();

      Solve [i] = x;

}

int x[][] = new int [6][6];

  int system1 [][] = new int [6][6];

int system2 [][] = new int [6][6];

int system3 [][] = new int [6][6];

int system4 [][] = new int [6][6];

  int system5 [][] = new int [6][6];

int peremenn = 0;

for (int i = 0; i < t.length; i++)

{

if(t[i]!=0)

peremenn++;

}

for (int j = 0; j < peremenn ; j++)

{

int index = sc.nextInt();

int sys1 [][] = new int [6][6];

int number = sc.nextInt();

if (number == 0){

index = sc.nextInt();

number = sc.nextInt();

}

for (int i = 0; i < number; i++){

int a = sc.nextInt();

int b = sc.nextInt();

int c = sc.nextInt();

sys1 [a][b] = c;

}

switch (index) {

case 1: {system1 = sys1; }break;

case 2: {system2 = sys1; }break;

case 3: {system3 = sys1; }break;

case 4: {system4 = sys1; }break;

case 5: {system5 = sys1; }break;

default: break; }

}

System.out.print(" Частное решение:  ");

while (sc.hasNext()!= false){

 int a = sc.nextInt();

 int b = sc.nextInt();

 int c = sc.nextInt();

System.out.print("X(" + a + "," + b + ")=" + c + ". ");

system1 [a][b] =c;

system2 [a][b] =c;

system3 [a][b] =c;

system4 [a][b] =c;

system5 [a][b] =c;

}

 int ff = 0;

 int I = 1;

 int num = t[I];

 int sys [][] = new int [6][6];

 switch (num) {

 case 1: {sys = system1; }break;

 case 2: {sys = system2; }break;

 case 3: {sys = system4; }break;

 case 4: {sys = system4; }break;

 case 5: {sys = system5; }break;

 default: break; }

 int a1 = 0; int b1 = 0;

 for (int i = 0; i < 6; i++)

{

for (int j = 0; j < 6; j++)

{

ff = sys[i][j];

 if ( sys[i][j] != 0)

{a1 = i; b1 = j; }

}

}

sys[a1][b1]  = Solve [num]/sys[a1][b1];

x[a1][b1] = sys[a1][b1]; 

I = 2;

num = t[I];

 switch (num) {

 case 1: {sys = system1; }break;

 case 2: {sys = system2; }break;

 case 3: {sys = system3; }break;

 case 4: {sys = system4; }break;

 case 5: {sys = system5; }break;

 default: break; }

sys[a1][b1]*=x[a1][b1];

 int a2 = 0; int b2 = 0;

 for (int i = 0; i < 6; i++)

{

 for (int j = 0; j < 6; j++)

{ff = sys[i][j];

 if ((sys [i][j]!=0)&&(sys[i][j]!= sys[a1][b1]))

{a2 = i; b2 = j;}

}

}

sys [a2][b2]  = (Solve[num] - sys[a1][b1])/ sys[a2][b2];

x[a2][b2] = sys[a2][b2];

I = 3;

 int a3 = 0; int b3 = 0;

num = t[I];

 switch (num) {

 case 1: {sys = system1; }break;

 case 2: {sys = system2; }break;

 case 3: {sys = system3; }break;

 case 4: {sys = system4; }break;

 case 5: {sys = system5; }break;

 default: break; }

sys[a2][b2]*=x[a2][b2];

sys[a1][b1]*=x[a1][b1];

 for (int i = 0; i < 6; i++)

{

 for (int j = 0; j < 6; j++)

{

ff = sys[i][j];

  if ((ff != 0)&&(ff != sys[a2][b2])&&(ff != sys[a1][b1]))

{a3 = i; b3 = j;}

}

}

sys[a3][b3]  = (Solve[num] - sys[a2][b2] - sys[a1][b1])/ sys[a3][b3];

x[a3][b3] = sys[a3][b3];

 

I = 4;

 int a4 = 0; int b4 = 0;

num = t[I];

 switch (num) {

 case 1: {sys = system1; }break;

 case 2: {sys = system2; }break;

 case 3: {sys = system4; }break;

 case 4: {sys = system4; }break;

 case 5: {sys = system5; }break;

 default: break; }

sys[a3][b3]*=x[a3][b3];

sys[a2][b2]*=x[a2][b2];

sys[a1][b1]*=x[a1][b1];

 for (int i = 0; i < 6; i++)

 {

 for (int j = 0; j < 6; j++)

{

ff = sys[i][j];

 if ((ff != 0)&&(ff != sys[a3][b3])&&(ff != sys[a2][b2])&&(ff != sys[a1][b1])) 

{a4 = i; b4 = j;}

}

}

 if (sys[a4][b4]!=0){

sys[a4][b4]  = (Solve[num] - sys[a3][b3] -sys[a2][b2] - sys[a1][b1] )/ sys[a4][b4];

x[a4][b4] = sys[a4][b4];

} 

 for (int i = 0; i < 6; i++)

{

 for (int j = 0; j < 6; j++)

{

ff = x[i][j];

if (ff != 0){

System.out.print("X(" + i + "," + j + ")=" + x[i][j] + ". ");

}  

}

}

System.out.println();

}

 catch (FileNotFoundException e) {

System.out.print(" ");

}

}

}

}