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

 

Министерство образования Республики беларусь

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет прикладной математики и информатики

Кафедра компьютерных технологий и систем

Кафедра методов оптимального управления

Курсовой проект

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ ЗАДАЧ СЕТЕВОЙ ОПТИМИЗАЦИИ

студентки 3 курса 10 группы

КРИВОРОТ МАРГАРИТА ИВАНОВНА

Минск 2012

Аннотация

Криворот М.И. Технология программирования задач сетевой оптимизации. Курсовой проект / Минск: БГУ, 2012 - 49 с.

Изложены методы решения разреженных недоопределенных систем линейных алгебраических уравнений с помощью эффективных алгоритмов, основанных на декомпозиции линейных систем и учете их сетевых свойств, рассмотрены примеры решения таких задач и продемонстрировано использование встроенных методов пакета Mathematica и объектно-ориентированного языка программирования JAVA.

M.I. Technology of programming network optimization problems Course project / Minsk. BSU, 2012 - 49 p.methods of solving systems of linear underdetermined algebraic equations using effective algorithms, based on decomposition of linear system and using systems network properties, are explored in this project. Also there are examples, which display solving such kinds of systems using embedded methods of system packet Mathematica and object oriented programming language JAVA.

Анатацыя

Крыварот М.І. Тэхналогія праграмавання задач сеткавай аптымізацыі. Курсавы праект / Мiнск: БДУ, 2012 - 49 с.

Выкладзены метады рашэння разрэджаных недавызначаных сiстэм лiнейных алгебраiчных раўнанняў з дапамогай эфектыўных алгарытмаў, заснаваных на дэкампазіцыі лiнейных сістэм і ўліку сеткавых уласцівасцяў , разгледжаны прыклады рашэння такiх задач i прадэманстравана выкарыстанне для гэтага ўбудаваных метадаў пакета Mathematica i аб'ектна арыентаванай мовы праграмавання JAVA.

Реферат

Курсовой проект, 49 с., 20 рис., 5 табл., 6 источников.

Ключевые слова: ЛИНЕЙНАЯ СИСТЕМА, НЕДООПРЕДЕЛЁННАЯ СИСТЕМА, НЕДООПРЕДЕЛЕННЫЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, КОНЕЧНАЯ ОРИЕНТИРОВАННАЯ СВЯЗНАЯ СЕТЬ, ОПОРА СЕТИ, ХАРАКТЕРИСТИЧЕСКИЕ ВЕКТОРЫ, ЦИКЛ, ДЕТЕРМИНАНТ ЦИКЛА, ДЕКОМПОЗИЦИЯ СИСТЕМЫ.

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

Цель работы - изучить компьютерную техническую систему Mathematica и объектно-ориентированный язык программирования Java на примере нахождения решения разреженных недоопределенных систем линейных алгебраических уравнений.

Методы исследования - методы матричного анализа, вычислительные методы алгебры и методы линейного программирования.

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

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

Оглавление

Введение

Часть 1. Разреженные недоопределенные системы8

.1 Общий вид системы

.2.1 Критерий опорности

.2.2 Характеристические векторы

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

Часть 2. Разреженные недоопределенные системы (обобщенная сеть)

.1 Общий вид недоопределенной системы (обобщенная сеть)

.2 Сетевая часть системы

.2.1 Критерий опорности обощенной сети

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

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

Заключение

Приложение А

Приложение В

Введение

Задачей данного проекта является рассмотрение технологии программирования задач сетевой оптимизации. Для этого необходимо решение разреженных недоопределенных систем линейных алгебраических уравнений, выделение из бесконечного множества решений одного, оправданного с математической точки зрения, и предложение алгоритма его поиска. Для построения решения в данном проекте используются такой пакет прикладных программ, как КТС Mathematica, и средства объектно-ориентированного языка программирования JAVA. Также анализируются неоднородные задачи потокового программирования с взаимосвязью потоков различных типов и учетом ограничений на пропускные способности дуг.

Пакеты прикладных программ (аббр. ППП, англ. Software package) - комплекс взаимосвязанных программ, предназначенных для решения задач определенного класса конкретной предметной области. Служат программным инструментарием решения функциональных задач и являются самым многочисленным классом программных продуктов.

Объектно-ориентированный язык программирования (ОО-язык) - язык, построенный на принципах объектно-ориентированного программирования. В основе концепции объектно-ориентированного программирования лежит понятие объекта - некой субстанции, которая объединяет в себе поля (данные) и методы (выполняемые объектом действия).

Mathematica - система компьютерной алгебры компании Wolfram Research. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение дву- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.

Java - объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems (в последующем приобретённой компанией Oracle). Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине (JVM) вне зависимости от компьютерной архитектуры. Достоинство подобного способа выполнения программ - в полной независимости байт-кода от операционной системы и оборудования, что позволяет выполнять Java-приложения на любом устройстве, для которого существует соответствующая виртуальная машина. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы полностью контролируется виртуальной машиной.

Часть 1. Разреженные недоопределенные системы

.1 Общий вид системы

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

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

Рассмотрим линейную недоопределенную систему вида:

где ,,; - вектор неизвестных.

Рассмотрим построения системы (1) - (3) на рисунке 1.

Рисунок 1. - Пример системы (1) - (3)

Матрица системы (1) - (3) имеет следующую блочную структуру:

(4)

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

1.2 Сетевая часть системы

Построение решения системы (1) - (3) начнем с рассмотрения сетевой части системы.

Определение 1.2.1. Система называется сетевой частью системы - . Системы называются дополнительной частью системы -

Прежде чем начать построение решения системы , укажем необходимые и достаточные условия существования решения (теорема Кронекера - Капелли):

Теорема 1.2.1. Ранг матрицы системы равен

Доказательство. Поскольку матрица M системы имеет вид , где - диагональный блок матрицы M, , и то =

Замечание 1.2.1. Предположим, без ограничения общности, что ранг системы равен , где - число уравнений дополнительной части

Поскольку матрица системы имеет блочно-диагональную структуру, разбиваем систему на независимых систем, каждая из которых соответствует отдельному блоку для фиксированного и имеет следующий вид:

1.2.1 Критерий опорности

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

имеет только тривиально решение для , но нетривиальное решение для ,

Сформулируем сетевой критерий опорности.

Теорема 1.2.2. Множество является опорой сети для системы тогда и только тогда, когда для каждого множество дуг является покрывающим (остовным) деревом сети .

Доказательство. Следует непосредственно из [5] для случая и блочно-диагональной структуры матрицы системы

.2.2. Характеристические векторы

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

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

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

Определение 1.2.3. Дуга , где фиксировано, называется прямой дугой цикла , если направление дуги совпадает с направление дуги в цикле. Аналогично дуга , где фиксировано, называется обратной дугой цикла , если направление дуги противоположно направлению дуги в цикле

Обозначим знак дуги в цикле через :

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

Приведем конструктивное определение характеристического вектора, порожденного некоторой дугой.

Определение 1.2.4. Характеристический вектор, порожденный дугой относительно покрывающего дерева , есть вектор , где фиксировано, построенный по следующим правилам:

·Добавить дугу к множеству , которое составляет покрывающее дерево сети ; в результате создан единственный цикл .

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

·Для прямых дуг цикла положим .

·Для обратных дуг цикла положим

·Положим , .

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

Примеры характеристических векторов, порожденных дугами , на рисунке 2:

В двух следующих леммах приводятся основные свойства характеристических векторов.

Лемма 1.2.1. Характеристический вектор , порожденный дугой , где фиксировано, является решением однородной системы

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

Рассмотрим вектор , компоненты которого являются неизвестными системы

Положим . Система имеет вид

где множество определяет все узлы цикла .

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

Алгоритмически, положив , проходим от узла к узлу по дугам цикла , последовательно устанавливая значения соответствующих неизвестных равным знакам дуг цикла . Направление в цикле определяется дугой , которая его порождает и является прямой. Заметим, что построенный вектор удовлетворяет всем условиям определения 1.2.4 характеристического вектора, порожденного дугой , и, следовательно, = - решение однородной линейной системы (8). Лемма доказана.

Пример разрешения системы вида с помощью характеристического вектора на рисунке 2:

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

Доказательство. По лемме 1.2.1 каждый характеристический вектор является решением системы (8).

Согласно теореме 1.2.2, для фиксированного множество - покрывающее дерево сети , следовательно, . Таким образом, число характеристических векторов во множестве равно.

Докажем, что векторы множества линейно независимы. Каждый характеристический вектор , порожденный некоторой дугой, всегда имеет хотя бы одну компоненту, соответствующую дуге из множества , которая равна 1. Эта компонента, равная 1, соответствует дуге , которая порождает этот вектор. Все остальные компоненты, которые соответствую дугам , равны нулю 0. Это означает, что два любых характеристических вектора, порожденных различными дугами, линейно независимы.

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

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

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

как сумму общего решения однородной системы и некоторого частного решения неоднородной системы (5); - коэффициенты линейной комбинации характеристических векторов в (11).

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

(13)

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

Замечание . На практике при построении частного решения системы будем полагать , и решаем систему

Таким образом, формула принимает вид:

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

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

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

Подставим общее решение системы для каждого в

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

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

Определение 1.3.1. Назовем число

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

Обозначим

Рисунок 8. - Вычисление

Уравнения согласно , примут вид:

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

Применим аналогичные рассуждения к системе Заметим, что систему можно рассматривать как частный случай системы с , равными 0 или 1.

Для каждого подставим общее решение системы в уравнение :

Или

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

Где

Таким образом, уравнения примут вид

где

Пример вычисления на рисунке 7:

Рисунок 9. - Вычисление

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

Запишем уравнения и в матричной форме. Для этого введем произвольную нумерацию дуг множеств. Обозначим номер дуги во введенной нумерации элементов множества , и пусть - номер циклической дуги . Другими словами, пронумеруем уравнения системы (3) или (27) и переменные, соответствующие множеству циклический дуг . Заметим, что введенная нумерация циклических дуг эквивалентна нумерации элементов множества циклов, порожденных дугами , относительно покрывающих деревьев сетей

Итак, уравнения и могут быть представлены следующим образом:

(28)

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

Правая часть системы имеет вид:

(29)

Пример вектора и матриц и на рисунках 8 и 9:

В случае невырожденной матрицы из (1.3.14) находим искомые неизвестные соответствующие множествуциклических дуг:

.(30)

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

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

Таким образом, определены все неизвестные системы (1) - (3):

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

Кратко изложим наиболее важные аспекты метода. Хотя строгие оценки сложности алгоритма здесь не рассматриваются, следует обратить внимание на то, что описанный подход осуществлен на надлежащих структурах данных, что ведет к эффективному алгоритму: часть вычислений выполнена на небольших подмножествах дуг, например на изолированных циклах или покрывающих (остовных) деревьях . использование сетевой структуры ограничений позволяет выполнить декомпозицию опоры, и, следовательно , декомпозицию системы, и, наконец, выполняется обращение матрицы размера, намного меньшего ,чем размер исходной системы кроме этого, независимые результаты, полученные для каждого типа потока k из множества K, например теорема 1.2.2, леммы 1.2.1 и 1.2., формулы дают возможность строить решения больших недоопределенных систем линейных уравнений в параллельной среде.

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

Часть 2. Разреженные недоопределенные системы (обобщенная сеть)

.1 Общий вид недоопределенной системы (обобщенная сеть)

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

Введем подмножество множества , и для каждой дуги из множества определим подмножество , такое, что.

Сеть может быть представлена в виде объединения сетей ,где .

Рассмотрим линейную недоопределенную систему вида:

где ,, параметры системы, . Условия существования решения системы (2.1.1) следуют из теоремы Кронекера-Капелли [15].

Предположим, что . В дальнейшем будем называть сетевой частью и дополнительной частью системы

Матрица системы имеет следующую блочную структуру:

(4)

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

2.2 Сетевая часть системы

Теорема 2.2.1. Ранг матрицы системы для сети равен .

Доказательство. Поскольку матрица M системы (1) имеет вид где - диагональный блок матрицы M, и rankто выполняются соотношения:

Теорема доказана.

Замечание 2.2.1. Предположим, без ограничения общности, что ранг матрицы А системы равен

Поскольку матрица системы имеет блочно-диагональную структуру, мы разбиваем систему на независимых систем, каждая из которых соответствует отдельному блоку для фиксированного и имеет следующий вид:

2.2.1 Критерий опорности обощенной сети

Определим опору сети для системы Определение 2.2.1. Опорой сети для системы (2.1.1) назовем множество дуг для которого система

имеет только тривиально решение для , но имеет нетривиальное решение для множества дуг ,

Сформулируем сетевой критерий опорности.

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

Доказательство. Следует из свойств для однородного потока в обобщенной сети и блочно-диагональной структуры матрицы системы

2.2.2 Характеристические векторы

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

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

Проанализируем структуру сети, полученную в результате добавления дуги , где фиксированно, к опоре . Поскольку опора сети для системы - это объединение связных компонент , каждая компонента связности содержит единственный невырожденный цикл [5,6,18,19], то в результате добавления дуги , где фиксированно, к опоре будет получена сеть, структура которой подробно описана в [18].

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

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

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

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

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

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

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

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

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

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

.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.4 Решение недоопределенной линейной системы средствами КТС MATHEMATICA и языка программирования Java

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

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

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

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

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

Таблица 1

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

Таблица 2

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

Таблица 3

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

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

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

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

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

Таблица 4

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

-2- 1319702- 6174453511- 2

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

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

Таблица 5

Значения

-1- 1001

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Приложение А

System={,2-x15,1?3,

x11,2-x15,2-x14,2?-15,,2-x15,4?-8,,1+x15,4+x15,2?20,

,2-x24,1?0,

x21,2+x22,3?-6,

x22,3-x24,3?-5,,1+x24,3-x25,4?7,,4?4,

,2-x34,1-x35,1?-10,

x31,2-x34,2?-10,

x34,3?-7,,1+x34,3+x34,2-x35,4?9,,1+x35,4?18,

x11,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,

x11,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,

x11,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,

,4+x35,4?13

};

?15,1=Join[Solve[

{x11,2-x15,1?0,

x11,2-x15,2-x14,2?0,,2-x15,4?0,,1+x15,4+x15,2?0

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

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

?15,2=Join[Solve[

{x11,2-x15,1?0,

x11,2-x15,2-x14,2?0,,2-x15,4?0,,1+x15,4+x15,2?0

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

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

?24,1=Join[Solve[

{x21,2-x24,1?0,

x21,2+x22,3?0,

x22,3-x24,3?0,,1+x24,3-x25,4?0,,4?0

}/.(?={x24,1?1}),

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

?34,1=Join[Solve[

{x312-x341-x351?0,

x312-x342?0,

x343?0,+x343+x342-x354?0,+x354?0

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

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

?35,1=Join[Solve[

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

x31,2-x34,2?0,

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

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

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

[" ?15,1 = ",?15,1];Print[" ?15,2 = ",?15,2];Print[" ?24,1=",?24,1];Print[" ?34,1=",?34,1];Print[" ?35,1=",?35,1];

={x11,2-x15,1?0,

x11,2-x15,2-x14,2?0,

?0,,2-x15,4?0,,1+x15,4+x15,2?0

};={5,4,2,1};={0,1,0,2,4};={0,1,0,-1,-1};a=system1;a[[5]]=system1a[[5]]/.{x15,1?1};a[[1]]=system1a[[1]]/.{x15,1?1};a[[5]]=system1a[[5]]/.{x15,2?0};a[[2]]=system1a[[2]]/.{x15,2?0};

?15,1={x15,1?1,x15,2?0};

[i=1,i?3,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system1a[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system1a[[ p[[ t[[i]] ]] ]]/.?];

?15,1=Join[?15,1,?];

}];

b=system1;b[[5]]=system1b[[5]]/.{x15,1?0};b[[1]]=system1b[[1]]/.{x15,1?0};b[[5]]=system1b[[5]]/.{x15,2?1};b[[2]]=system1b[[2]]/.{x15,2?1};

?15,2={x15,1?0,x15,2?1};

[i=1,i?3,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system1b[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,b[[ p[[ t[[i]] ]] ]]=system1b[[ p[[ t[[i]] ]] ]]/.?];

?15,2=Join[?15,2,?];

}];

={x21,2-x24,1?0,

x21,2+x22,3?0,

x22,3-x24,3?0,,1+x24,3-x25,4?0,,4?0

};={5,4,3,2,1};={0,1,2,3,4};={0,1,1,-1,-1};a=system2;a[[4]]=system2a[[4]]/.{x24,1?1};a[[1]]=system2a[[1]]/.{x24,1?1};

?24,1={x24,1?1};

[i=1,i?4,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system2a[[ t[[i]] ]],x2t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system2a[[ p[[ t[[i]] ]] ]]/.?];

?24,1=Join[?24,1,?];

}];

={x31,2-x34,1-x35,1?0,

x31,2-x34,2?0,

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

};={5,3,4,2,1};={0,1,4,2,4};={0,1,1,-1,-1};a=system3;a[[4]]=system3a[[4]]/.{x34,1?1};a[[1]]=system3a[[1]]/.{x34,1?1};a[[5]]=system3a[[5]]/.{x35,1?0};a[[1]]=system3a[[1]]/.{x35,1?0};

?34,1={x34,1?1,x35,1?0};

[i=1,i?4,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system3a[[ t[[i]] ]],x3t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system3a[[ p[[ t[[i]] ]] ]]/.?];

?34,1=Join[?34,1,?];

}];

b=system3;b[[4]]=system3b[[4]]/.{x34,1?0};b[[1]]=system3b[[1]]/.{x34,1?0};b[[5]]=system3b[[5]]/.{x35,1?1};b[[1]]=system3b[[1]]/.{x35,1?1};

?35,1={x34,1?0,x35,1?1};

[i=1,i?4,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system3b[[ t[[i]] ]],x3t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,b[[ p[[ t[[i]] ]] ]]=system3b[[ p[[ t[[i]] ]] ]]/.?];

?35,1=Join[?35,1,?];

}];

Частное решение={x11,2-x15,1?3,

x11,2-x15,2-x14,2?-15,

?0,,2-x15,4?-8,,1+x15,4+x15,2?20

};={5,4,2,1};={0,1,0,2,4};={0,1,0,-1,-1};a=system1;a[[5]]=system1a[[5]]/.{x15,1?0};a[[1]]=system1a[[1]]/.{x15,1?0};a[[5]]=system1a[[5]]/.{x15,2?0};a[[2]]=system1a[[2]]/.{x15,2?0};

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

[i=1,i?3,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system1a[[ t[[i]] ]],x1t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system1a[[ p[[ t[[i]] ]] ]]/.?];

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

=Join[,?];

}];

={x21,2-x24,1?0,

x21,2+x22,3?-6,

x22,3-x24,3?-5,,1+x24,3-x25,4?7,,4?4

};={5,4,3,2,1};={0,1,2,3,4};={0,1,1,-1,-1};a=system2;a[[4]]=system2a[[4]]/.{x24,1?0};a[[1]]=system2a[[1]]/.{x24,1?0};

={x24,1?0};

[i=1,i?4,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system2a[[ t[[i]] ]],x2t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system2a[[ p[[ t[[i]] ]] ]]/.?];

=Join[,?];

}];

={x31,2-x34,1-x35,1?-10,

x31,2-x34,2?-10,

x34,3?-7,,1+x34,3+x34,2-x35,4?9,,1+x35,4?18

};={5,3,4,2,1};={0,1,4,2,4};={0,1,1,-1,-1};a=system3;a[[4]]=system3a[[4]]/.{x34,1?0};a[[1]]=system3a[[1]]/.{x34,1?0};a[[5]]=system3a[[5]]/.{x35,1?0};a[[1]]=system3a[[1]]/.{x35,1?0};

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

[i=1,i?4,++i,

{[d[[ t[[i]] ]]?1,

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

?=Solve[ system3a[[ t[[i]] ]],x3t[[i]],p[[ t[[i]] ]]][[1]]];[p[[ p[[ t[[i]] ]] ]]?0,a[[ p[[ t[[i]] ]] ]]=system3a[[ p[[ t[[i]] ]] ]]/.?];

=Join[,?];

}];

["= ",];["= ",];["= ",];

,1=7x11,2+9x14,2+9x15,1+9x15,4/.?15,1;,1=6x11,2+5x14,2+10x15,1+9x15,4/.?15,1;,1=2x11,2+3x14,2+8x15,1+2x15,4/.?15,1;

,2=7x11,2+9x14,2+5x15,2+9x15,4/.?15,2;,2=6x11,2+5x14,2+8x15,2+9x15,4/.?15,2;,2=2x11,2+3x14,2+8x15,2+2x15,4/.?15,2;

,1=4x21,2+8x22,3+9x24,1+2x24,3+3x25,4/.?24,1;,1=7x21,2+3x22,3+7x24,1+0x24,3+5x25,4/.?24,1;,1=x21,2+5x22,3+2x24,1+3x24,3+4x25,4/.?24,1;

,1=2x31,2+9x34,1+4x34,2+5x34,3+7x35,4/.?34,1;,1=6x31,2+0x34,1+2x34,2+2x34,3+7x35,4/.?34,1;,1=5x31,2+6x34,1+0x34,2+2x34,3+8x35,4/.?34,1;

,1=2x31,2+4x34,2+5x34,3+9x35,1+7x35,4/.?35,1;,1=6x31,2+2x34,2+2x34,3+7x35,1+7x35,4/.?35,1;,1=5x31,2+0x34,2+2x34,3+x35,1+8x35,4/.?35,1;

,1=0x11,2+0x14,2+0x15,1+x15,4/.?15,1;,2=0x11,2+0x14,2+0x15,2+x15,4/.?15,2;,1=0x21,2+0x22,3+0x24,1+0x24,3+0x25,4/.?24,1;,1=0x31,2+0x34,1+0x34,2+0x34,3+x35,4/.?34,1;

,1=0x31,2+0x34,2+0x34,3+0x35,1+x35,4/.?35,1;

=({

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

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

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

});= {{R415,1 , R415,2 ,R424,1 , R434,1}};= Join [D1,D2];["Матрица DD = ",MatrixForm[DD]];

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

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

x15,2+9x15,4+3x25,4+7x35,4)/././.;=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+

x25,4+7x35,4)/././.;=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)/././.;

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

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

?2=A2-(R235,1 x35,1);

?3=A3-(R335,1 x35,1);

?4=A4-(R435,1 x35,1);

? = Transpose [{{?1 ,?2 , ?3, ?4}}];["Вектор ? = ",MatrixForm[?] ];

= LinearSolve [DD ,?];=Simplify[Inverse[DD].({

{?1},

{?2},

{?3},

{?4}

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

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

={x11,2?x15,1(x11,2/.?15,1)+x15,2(x11,2/.?15,2)+(x11,2/.),,2?x15,1(x14,2/.?15,1)+x15,2(x14,2/.?15,2)+(x14,2/.),,4?x15,1(x15,4/.?15,1)+x15,2(x15,4/.?15,2)+ (x15,4/.),,2?x24,1(x21,2/.?24,1)+(x21,2/.),,3?x24,1(x22,3/.?24,1)+(x22,3/.),,3?x24,1(x24,3/.?24,1)+(x24,3/.),,4?x24,1(x25,4/.?24,1)+(x25,4/.),

,2?x34,1(x31,2/.?34,1)+x35,1(x31,2/.?35,1)+

(x31,2/.),,2?x34,1(x34,2/.?34,1)+x35,1(x34,2/.?35,1)+

(x34,2/.),,3?x34,1(x34,3/.?34,1)+x35,1(x34,3/.?35,1)+

(x34,3/.),,4?x34,1(x35,4/.?34,1)+x35,1(x35,4/.?35,1)+

(x35,4/.)

};

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

[Simplify[System/.solution]];

[solution];

[{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"*)

?15,1 = {x11,2?1,x14,2?-1,x15,4?-1,x15,1?1,x15,2?0};

?15,2 = {x11,2?0,x14,2?-1,x15,4?-1,x15,1?0,x15,2?1};={5,4,2,1};={0,1,0,2,4};={0,1,0,-1,-1};["Характеристика леса покрывающих (остовных) деревьев"];["Thread = ", thread];["Pred = ", pred];["Direction = ", dir];["Лес покрывающих деревьев для потока №1"];[{5?4,4?2,1?2,3?3}, Left, 1, SelfLoopStyle?None, DirectedEdges?True, VertexLabeling?True]["Добавленная дуга - x15,1 "];["Соответствующий характеристический вектор ?15,1 = ",?15,1];[{5?4, 5?1, 4?2, 1?2, 3?3}, Top, 1, SelfLoopStyle?None, DirectedEdges?True, VertexLabeling?True]["Добавленная дуга - x15,2 "];["Соответствующий характеристический вектор ?15,2 = " ,?15,2];[{5?4, 5?2, 4?2, 1?2, 3?3}, Top, 1, SelfLoopStyle?None, VertexLabeling?True, DirectedEdges?True]

(*system2*)

?24,1 = {x21,2?1,x24,3?-1,x22,3?1,x25,4?0,x24,1?1};["Характеристика леса покрывающих (остовных) деревьев"];={5,4,2,1};={0,1,0,2,4};={0,1,0,-1,-1};["Thread = ", thread];["Pred = ", pred];["Direction = ", dir];={5,4,3,2,1}={0,1,2,3,4}={0,1,1,-1,-1}["Лес покрывающих деревьев для потока №2"];[{5?4,4?3,2?3,1?2},Top, 1, DirectedEdges?True, VertexLabeling?True]["Добавленная дуга - x24,1 "];["Соответствующий характеристический вектор ?24,1 = ",?24,1];[{5?4,4?3,2?3,1?2,4?1}, Top, 1, DirectedEdges?True, VertexLabeling?True]

(*system3*)

?34,1 ={x31,2?1,x34,2?-1,x34,3?0,x35,4?0,x34,1?1,x35,1?0};

?35,1 ={x31,2?1,x34,2?-1,x34,3?0,x35,4?-1,x34,1?0,x35,1?1};={5,3,4,2,1};={0,1,4,2,4};={0,1,1,-1,-1};["Характеристика леса покрывающих (остовных) деревьев"];["Thread = ", thread];["Pred = ", pred];["Direction = ", dir];["Лес покрывающих деревьев для потока №3"];[{1?2,4?2,4?3,5?4},Top, 1, DirectedEdges?True, VertexLabeling?True]["Добавленная дуга - x34,1 "];["Соответствующий характеристический вектор ?34,1 = ",?34,1];[{1?2, 4?1, 4?2, 4?3, 5?4},Top, 1, DirectedEdges?True, VertexLabeling?True]["Добавленная дуга - x35,1 "];["Соответствующий характеристический вектор ?35,1 = ",?35,1];[{1?2,5?1,4?2,4?3,5?4}, Top, 1, DirectedEdges?True, VertexLabeling?True]

Приложение В

java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

public class Testing {

public static void main(String[] args) {sc;

int f;

int [] d = new int [6];

int [] p = new int [6];

int [] t = new int [6];

int [] Solve = new int[6];[] files = {"D:\\System_1.txt", "D:\\System_2.txt", "D:\\System_3.txt"};filename;

for (f = 0; f<3; f++){= files[f];

try {= new Scanner(new File(filename));

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

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

int x = sc.nextInt();[i] = x;

}.out.println();

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

{

int x = sc.nextInt();[i] = x;

}

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

{

int x = sc.nextInt();[i] = x;

}

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

{

int x = sc.nextInt();[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)++;

}

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

{

int index = sc.nextInt();

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

int number = sc.nextInt();

if (number == 0){= sc.nextInt();= sc.nextInt();

}

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

int a = sc.nextInt();

int b = sc.nextInt();

int c = sc.nextInt();[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; }

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

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

int a = sc.nextInt();

int b = sc.nextInt();

int c = sc.nextInt();.out.print("X(" + a + "," + b + ")=" + c + ". ");[a][b] =c;[a][b] =c;[a][b] =c;[a][b] =c;[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++)

{= sys[i][j];

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

{a1 = i; b1 = j; }

}

}[a1][b1] = Solve [num]/sys[a1][b1];[a1][b1] = sys[a1][b1];= 2;= 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; }[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;}

}

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

int a3 = 0; int b3 = 0;= 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; }[a2][b2]*=x[a2][b2];[a1][b1]*=x[a1][b1];

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

{

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

{= sys[i][j];

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

{a3 = i; b3 = j;}

}

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

= 4;

int a4 = 0; int b4 = 0;= 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; }[a3][b3]*=x[a3][b3];[a2][b2]*=x[a2][b2];[a1][b1]*=x[a1][b1];

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

{

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

{= 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){[a4][b4] = (Solve[num] - sys[a3][b3] -sys[a2][b2] - sys[a1][b1] )/ sys[a4][b4];[a4][b4] = sys[a4][b4];

}

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

{

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

{= x[i][j];

if (ff != 0){.out.print("X(" + i + "," + j + ")=" + x[i][j] + ". ");

}

}

}.out.println();

}

catch (FileNotFoundException e) {.out.print(" ");

}

}

}

}

Министерство образования Республики беларусь БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и информатики Кафедра компьюте

Больше работ по теме: