Рассмотрим экономику из отраслей, задающуюся матрицей межотраслевого баланса . Для осуществления валового выпуска необходимо произвести производственные затраты . Предлагается, что валовый выпуск предыдущего периода может быть использован как запас сырья в периоде . Получаем задачу:
,
– известный начальный запас.
Обозначим
, , , .
где , , – матрицы . Тогда задача сводится к задаче линейного программирования
.
Размерность задачи (матрицы ): .
Задачу, двойственную к , можно записать в виде:
Определение 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 получаем, что для каждого найдется , такое, что для при выполняется условие .
Таким образом, при для любой оптимальной траектории задачи выполняется условие . Следовательно, вектор является магистралью.