русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Теорема о магистрали Моришимы.


Дата добавления: 2015-09-15; просмотров: 1880; Нарушение авторских прав


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

,

– известный начальный запас.

Обозначим

, , , .

где , , – матрицы . Тогда задача сводится к задаче линейного программирования

.

Размерность задачи (матрицы ): .

Задачу, двойственную к , можно записать в виде:

Определение 2.6. Неотрицательную матрицу A назовем примитивной, если ее векторы Фробениуса образуют одномерное подпространство.

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

Замечание 2.3. В данном случае векторы Фробениуса матрицы различаются только длиной, все они задают одну и ту же магистраль.

Лемма 2.3. Пусть – устойчивая матрица, – ненулевой неотрицательный вектор. Если , то – правый вектор Фробениуса матрицы , причем для каждого найдется , такое что при выполняется условие .

Для доказательствадостаточно применить свойство функции , состоящее в том, что из условия следует .

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

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

Доказательство. Отметим, что в силу примитивности матрицы для всех последовательности относительно функции имеют "одинаковый предел" т.е. .

По лемме 2.3 для и векторов найдутся , такие что при справедливо . Обозначим .

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



Лемма 2.5. Если вектор Фробениуса устойчивой неотрицательной матрицы не содержит нулевых элементов, то найдется число , такое что для всех ненулевых неотрицательных векторов для всех выполняется условие .

Доказательство. Если вектор , то найдется , такое что коническая окрестность состоит только из положительных векторов. Следовательно, по лемме 2.4 для всех выполняется условие , вследствие чего .

Лемма 2.6. Если в задаче и выполняются условия леммы 2.5, то найдется число , такое что для всякой оптимальной траектории этой задачи при выполняется условие .

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

Для оптимальной траектории значение целевой функции не может быть меньшим, чем для траектории , поэтому получаем, что в оптимальной траектории .

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

Теорема 2.5. Если в задаче вектор Фробениуса матрицы положителен, матрица является примитивной и устойчивой, то вектор является магистралью для задачи .

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

.

Таким образом, при имеет место равенство .

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

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

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

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

Таким образом, при для любой оптимальной траектории задачи выполняется условие . Следовательно, вектор является магистралью.



<== предыдущая лекция | следующая лекция ==>
Магистральная теория. | Элемент памяти, микросхема памяти, модуль памяти, графическая память


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

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


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.