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

Теорема 2.2.3. Множество { характеристических векторов, где фиксировано, составляет базис пространства решений однородной системы

Теорема 2.2.4. Общее решение системы для фиксированного может быть представлено в следующем виде:

 

 

 

где – любое частное решение системыдля фиксированного ; – независимые переменные, соответствующие дугам .

 

Доказательство. Обозначим через   общее решение системы , и пусть – некоторое частное решение системы (5). Поскольку по теореме множество характеристических векторов составляет базис пространства решений однородной системы (6), то представим общее решение в следующей векторной форме:

 

как сумму общего решения однородной системы 6) и некоторого частного решения неоднородной системы – коэффициенты линейной комбинации характеристических векторов в

Представим в компонентной форме:

 

      

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

 

Замечание 2.2.2. На практике при построении частного решения  системы будем полагать , для дуг,  и тогда система (5) для нахождения частного решения представима в виде:

 

В этом случае  формула (9) имеет вид:

 

 

В дальнейшем будем использовать формулу (13).

 

2.3. Декомпозиция системы

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

Таким образом, , где – непересекающиеся множества дуг.

Подставим общее решение (9) системы (5) в уравнение (2):

 

 

 

 

Изменим порядок суммирования в (14) :

 

 

В уравнениях (15) группируем переменные, соответствующие множествам дуг 

:

 

Определение 2.3.1. Число

 

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

 

Обозначим

 

Уравнения в соответствии сформулами (17), (18) имеют вид:

 

В уравнениях группируем переменные, соответствующие множествам

 

Выполним аналогичные преобразования системы  Заметим, что уравнения системы являются частным случаем системы с коэффициентами , равными 0 или 1.

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

        

 

где – бицикл, порожденный дугой   Подставим общее решение для каждого в уравнение :

 

 

Изменив порядок суммирования, получим

 

 

 

Заметим, что для каждой дуги , которая порождает бицикл , сумма   равна :

 

   

Обозначим через правую часть в

 

Итак, в соответствии с уравнения примут вид:

 

В (24) группируем переменные, соответствующие множествам , где – множество бициклических дуг, :

 

Итак, уравнения (20) и (27) могут быть представлены в следующей матрично-векторной форме:

     

где , – номер дуги , .

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

.

Здесь

 

и для каждой дуги

 

 

 

 

 

 

В случае невырожденной матрицы из системы вычислим вектор , компоненты которого соответствуют множеству бициклических дуг:

 

Замечание 2.3.1. В общем случае, из-за произвольного выбора дуг множества невырожденность матрицы не гарантируется. В случае? если необходимо выбрать другие дуги в состав множества и заново вычислить системы

Обозначим Представим в компонентной форме

 

 

 

Замечание 2.3.2. Компоненты вектора – частное решение системы построены в соответствии с правилами замечания 2.2.2.

 

 

2. Решение недоопределенной линейной системы средствами КТС MATHEMATICA и языка программирования Java

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

 

Рассмотрим пример (1а) – (3а) (представлен на рисунке 1) построения системы (1) – (3) для сети . Множество  состоит из трех типов потока: множества дуг, по которым транспортируются потоки трех типов Исходная сеть представлена в виде  объединения сетей (рисунок 16).

 

Рисунок 16. – Сеть

 

Рассмотрим решение системы, что представлена на рисунке 1.

 

 

 

Выберем некоторую опору , = {1,2,3} сети для системы (1а). пусть выбранная опора состоит из покрывающих деревьев (или леса покрывающих деревьев) , :

Построим множество характеристических векторов относительно выбранного покрывающего дерева для каждого = {1,2,3}.

 

Рисунок 17. – Лес покрывающих деревьев, составляющих опору :

 

 

Рисунок 18. – Покрывающее дерево, составляющее опору :

 

 

Рисунок 19. – Покрывающее дерево, составляющее опору :

 

Таблица 1.

Характеристические вектора относительно :

 

Таблица 2.

Характеристические вектора относительно :

 

Таблица 3.

Характеристические вектора относительно :

 

Построим частное решение системы (1а) для каждого = {1,2,3}: , (рисунки 5, 6).

 

Сформируем множество циклических дуг. Построим множество . Структуры, представляющие объединение множеств , представлены на рисунке 2.

      

          

 

 

 

Рисунок 20. – Множества для сетей

Согласно формуле (18)

 

вычислим детерминанты циклов  , порожденных дугами , для каждого = {1,2,3}, относительно уравнений (2а) с номерами p =1,2,3 (таблица 4).

 

Таблица 4.

Детерминанты циклов , порожденных дугами , = {1,2,3},

	-2	- 13	19	7	0
	2	- 6	17	4	4
	5	3	5	11	- 2

 

По формуле  (24)

 

 

вычислим значения  для системы (1а) – (3а),

 

 Таблица 5.

Значения

	-1	- 1	0	0	1

 

Для построения матрицы системы  (28),  пронумеруем дуги множества : Нумерация множества тривиальна : .

 

Формируем матрицу детерминантов циклов , порожденных дугами , выбирая соответствующие столбцы из таблицы 4:

 

Аналогично, выбирая соответствующие столбцы из таблицы 5, формируем матрицу :

 

Таким образом, объединив и , получим матрицу системы (28):

 

Посчитаем вектор правой части (28)

где

Итак, построен вектор 

Так как матрица невырожденная, применим формулу (30) для нахождения решения системы (28):

 

Окончательно, используя формулы (30) – (31), получим общее решение системы (1а) – (3а) с независимой переменной

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

1) изучены общие теоретические вопросы по теме «Метод приращения в пространстве состояний»;

2) с помощью КТС Mathematica построены решения задачи о заменен оборудования;

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

5) изучены основные требования по подготовке отчетных документов.

 

 

 

Приложение А

 

System={

   x11,2-x15,1Š3,

   -x11,2-x15,2-x14,2Š-15,  

   x14,2-x15,4Š-8,

   x15,1+x15,4+x15,2Š20,

  

   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,

  

   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,

  

   7x11,2+4x21,2+2x31,2+8x22,3+9x24,1+9x34,1+9x14,2+

     + 4 x34,2+2x24,3+5x34,3+9x15,1+9x35,1+5x15,2+9x15,4+3x25,4+7x35,4Š556,

  

   6x11,2+7x21,2+6x31,2+3x22,3+7x24,1+5x14,2+2x34,2+

     + 2 x34,3+10x15,1+7x35,1+8x15,2+9x15,4+5x25,4+7x35,4Š501,               

                                        

   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Š307,

  

   x15,4+x35,4Š13                        

   };

 

d15,1=Join[Solve[

     {x11,2-x15,1Š0,

       -x11,2-x15,2-x14,2Š0,

       x14,2-x15,4Š0,

       x15,1+x15,4+x15,2Š0

       }/.(d={x15,1®1,x15,2®0}),

     {x11,2,x14,2,x15,4}][[1]],d];

 

d15,2=Join[Solve[

     {x11,2-x15,1Š0,

       -x11,2-x15,2-x14,2Š0,

       x14,2-x15,4Š0,

       x15,1+x15,4+x15,2Š0

       }/.(d={x15,1®0,x15,2®1}),

     {x11,2,x14,2,x15,4}][[1]],d];

 

d24,1=Join[Solve[

     {x21,2-x24,1Š0,

       -x21,2+x22,3Š0,

       -x22,3-x24,3Š0,

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

       x25,4Š0

       }/.(d={x24,1®1}),

     {x21,2,x24,3,x22,3,x25,4}][[1]],d];

 

d34,1=Join[Solve[

     {x312-x341-x351Š0,

       -x312-x342Š0,

       -x343Š0,

       x341+x343+x342-x354Š0,

       x351+x354Š0

       }/.(d={x341®1,x351®0}),

     {x312,x342,x343,x354}][[1]],d];

 

d35,1=Join[Solve[

     {x31,2-x34,1-x35,1Š0,

       -x31,2-x34,2Š0,

       -x34,3Š0,

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

       x35,1+x35,4Š0

       }/.(d={x34,1®0,x35,1®1}),

     {x31,2,x34,2,x34,3,x35,4}][[1]],d];

 

Print[" d15,1 = ",d15,1];Print[" d15,2 = ",d15,2];Print[" d24,1=",d24,1];Print[" d34,1=",d34,1];Print[" d35,1=",d35,1];

 

system1={x11,2-x15,1Š0,

   -x11,2-x15,2-x14,2Š0,

   0Š0,

   x14,2-x15,4Š0,

   x15,1+x15,4+x15,2Š0

   };

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

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

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

system1a=system1;

system1a[[5]]=system1a[[5]]/.{x15,1®1};

system1a[[1]]=system1a[[1]]/.{x15,1®1};

system1a[[5]]=system1a[[5]]/.{x15,2®0};

system1a[[2]]=system1a[[2]]/.{x15,2®0};

d15,1={x15,1®1,x15,2®0};

 

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

  {

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

    d=Solve[ system1a[[ t[[i]] ]],x1p[[ t[[i]] ]],t[[i]]][[1]],

    d=Solve[ system1a[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];

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

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

   d15,1=Join[d15,1,d];

   }];

 

 

system1b=system1;

system1b[[5]]=system1b[[5]]/.{x15,1®0};

system1b[[1]]=system1b[[1]]/.{x15,1®0};

system1b[[5]]=system1b[[5]]/.{x15,2®1};

system1b[[2]]=system1b[[2]]/.{x15,2®1};

d15,2={x15,1®0,x15,2®1};

 

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

  {

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

    d=Solve[ system1b[[ t[[i]] ]],x1p[[ t[[i]] ]],t[[i]]][[1]],

    d=Solve[ system1b[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];

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

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

   d15,2=Join[d15,2,d];

   }];

 

 

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

   -x21,2+x22,3Š0,

   -x22,3-x24,3Š0,

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

   x25,4Š0

   };

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®1};

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

d24,1={x24,1®1};

 

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];

   d24,1=Join[d24,1,d];

   }];

 

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

   -x31,2-x34,2Š0,

   -x34,3Š0,

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

   x35,1+x35,4Š0

   };

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®1};

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

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

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

d34,1={x34,1®1,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];

   d34,1=Join[d34,1,d];

   }];

 

 

system3b=system3;

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

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

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

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

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

 

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

  {

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

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

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

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

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

   d35,1=Join[d35,1,d];

   }];

 

 

Частное решение

system1={x11,2-x15,1Š3,

   -x11,2-x15,2-x14,2Š-15,

   0Š0,

   x14,2-x15,4Š-8,

   x15,1+x15,4+x15,2Š20

   };

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

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

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

system1a=system1;

system1a[[5]]=system1a[[5]]/.{x15,1®0};

system1a[[1]]=system1a[[1]]/.{x15,1®0};

system1a[[5]]=system1a[[5]]/.{x15,2®0};

system1a[[2]]=system1a[[2]]/.{x15,2®0};

={x15,1®0,x15,2®0};

 

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

  {

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

    d=Solve[ system1a[[ t[[i]] ]],x1p[[ t[[i]] ]],t[[i]]][[1]],

    d=Solve[ system1a[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];

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

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

   (*соединили массивы решений*)