1.3. Алгоритм линейного программирования

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

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

При любом справедливы очевидные соотношения

где — вероятность того, что в момент система находится в состоянии (см. (1.2)).

Лемма 1.2. Любая неотрицательная функция удовлетворяющая соотношениям (1.9), является вероятностным распределением, и соответствующий суммарный средний доход с учетом переоценки ограничен.

Доказательство. Поскольку , то суммируя (1.9) по всем получаем

Из предположения, что — вероятностное распределение, находим, что при

Это равенство и тот факт, что по предположению неотрицательны, доказывают первую часть леммы. Вторая часть была доказана неравенством (1.6).

Утверждение леммы 1.2 позволяет рассмотреть следующую задачу линейного программирования:

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

Они могут рассматриваться как -преобразования последовательностей в точке Используя переменные получаем следующую стандартную задачу линейного программирования (назовем ее задачей

при условии

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

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

Теорема 1.4. Если в системе уравнений (1.15) оставить лишь переменные отвечающие некоторой стационарной стратегии (полагая остальные переменные равными нулю), то а) соответствующая подсистема имеет единственное решение; б) если

Доказательство. Указанную подсистему можно записать в виде

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

а) Рассмотрим однородную систему, получаемую из (1.17), если положить . У этой системы заведомо существует нулевое решение. Предположим, что у нее существует еще ненулевое решение, которое обозначим Пусть

Суммируя уравнения указанной однородной системы по всем получим

Так как все слагаемые левой части равенства (1.18) неположительны, то они должны, равняться нулю. Однако, поскольку 1, то откуда следует, что первая сумма в (1.18) должна быть строго отрицательна. Это ведет к противоречию, если

Используя аналогичные рассуждения и определяя получим, что Таким образом, нулевое решение является единственным у однородной системы. Следовательно, ранг системы (1.17) равен и при любых значениях существует единственное решение этой системы.

б) Пусть Просуммируем уравнение (1.17) по всем

Правая часть (1.19) снова неотрицательна, откуда следует, что т. е.

в) Пусть, наконец, 0. В этом случае положим Тогда правая часть (1.19) строго положительна, а левая часть неположительна. Отсюда или

Используем теперь теорему 1.4 для доказательства важного соотношения между стационарными стратегиями и допустимыми базисными решениями уравнений (1.15), когда

Теорема 1.5. Если то существует взаимно однозначное соответствие между стационарными стратегиями и допустимыми базисными решениями уравнений (1.15). Более того, любое допустимое базисное решение невырождено.

Доказательство. Действительно, теорема 1.4 устанавливает, что в случае, когда стационарная стратегия соответствует единственному решению (1.17), которое имеет положительных переменных. Оно является по определению невырожденным допустимым базисным решением (1.15). Обратно, если — допустимое решение (1.15), то

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

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

Теорема 1.6. Если правая часть уравнений (1.15) строго положительна, то задача имеет оптимальное базисное решение, а двойственная задача имеет единственное оптимальное решение. Любая оптимальная стационарная стратегия, соответствующая этому решению, остается оптимальной для любой неотрицательной правой части

Доказательство. Из теоремы 1.4 следует, что допустимые решения существуют, а из леммы 1.2 известно, что целевая функция ограничена. Это гарантирует существование оптимальных решений как для исходной,

так и для двойственной задач. В силу теоремы 1.5 любое базисное решение невырождено, а в силу условий дополнительной нежесткости любое оптимальное решение двойственной задачи должно удовлетворять соответствующей невырожденной системе из двойственных равенств; следовательно, решение двойственной задачи единственно.

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

Следующее следствие будет использовано в разделе 1.4.

Следствие. Если все в правой части (1.15) положительны, то существует базисное решение, обладающее тем свойством, кто для каждого найдется в точности один элемент для которого при остальных же

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