Параметрическое линейное программирование

 

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

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

Рассмотрим частный случай, когда от параметра t зависят только коэффициенты целевой функции:

,

а вся задача выглядит следующим образом:

      т.е.  

                                                                 (1)

Рассмотрим геометрическую интерпретацию такой модели.

 

Для  линии уровня целевой функции параллельны MN. При  линии уровня параллельны M₂N₂, а при   –  M₁N₁.  Изменению  от  до  соответствует поворот  MN по часовой стрелке. При  оптимальное решение соответствует т. А. При , решение в т. В, при  – в т. С.

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

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

 

Для исследования параметрической модели воспользуемся алгоритмом метода последовательного улучшения плана.

 

Алгоритм

Задаемся каким-либо . Если в модели область изменения параметра t ограничена, т.е. , то в качестве  можно взять одну из границ.

После конечного числа шагов алгоритма либо придем к оптимальному плану задачи при  (случай 1⁰), либо убедимся, что целевая функция при данном  не ограничена на допустимой области (задача неразрешима) (случай 2⁰).

Рассмотрим сначала случай 1⁰.

 

Случай 1⁰

Если мы ищем max линейной формы, то признаком оптимальности опорного плана является неотрицательность коэффициентов  строки критерия.

Эти коэффициенты можно представить в виде следующей суммы

,     i = 1,…, n.

Так как план оптимален для  , то

,   i = 1,…, n,

и, следовательно, совместна система неравенств (из неотрицательности коэффициентов)

,    i = 1,…, n .                                (2)

Для всех   неравенства этой системы можно переписать в виде

,

а для всех 

.

Введем следующие обозначения

                                     (3)

 

Таким образом, можно утверждать, что если

,                                                           (4)

то найденный оптимальный план для  будет оставаться оптимальным для всех t, удовлетворяющих неравенству (4).

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

  и   .

Это в том случае, если хотя бы   или  .

Исследуем задачу на области . Пусть

Тогда в опорный план (в базис) необходимо ввести переменную, соответствующую столбцу k  ( x _k ).

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

Для нового плана получаем, что , т.е. наше  становится левой границей нового интервала.

Находится правая граница

.

Если  или правая граница исходного интервала , , то исследование в этом направлении прекращается.

Аналогично проводится исследование параметрической модели для . В этом случае в базис вводят переменную, соответствующую .

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

Случай 2⁰

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

Это соответствует тому, что коэффициент в строке целевой функции

                                         (5)

и все коэффициенты в k-м столбце неположительны.

При  условие (5) соблюдается для любого значения параметра, а значит задача неразрешима на всей оси t.

Если , то (5) выполняется для всех значений

.

  

Если , то (5) выполняется при

.

Таким образом,  в первом случае наша задача неразрешима слева от  ,  а в другом – справа от .

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

Если и сейчас процесс окончился выявлением неразрешимости задачи:

и в столбце коэффициентов , , то дальнейший анализ зависит от знака . Если , то задача неразрешима всюду.

Если , то задача неразрешима при

.

И если , то задача неразрешима на всей оси (при  задача неразрешима и при  неразрешима).

Если , то задача неразрешима при

.

И если  исследования продолжаются при .

неразрешима, то она вообще неразрешима на всей оси.

Аналогично исследования проводятся на луче .

 

Алгоритм метода последовательного улучшения плана для параметрической модели обладает некоторыми особенностями. Вместо одной строки критерия вводятся три дополнительные строки  и  для случая 1⁰ и две строки   и  в случае 2⁰.

Процесс решения начинается с анализа для некоторого . После выявления случая 1⁰, вводят строки  и . t₀  стараются выбрать таким образом, чтобы при анализе движение по оси t происходило в одном фиксированном направлении.

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

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

Если в модели , то этот процесс может закончиться раньше, как только область анализа охватит этот интервал.

 

 

 

 

 

Пример. Для всех значений параметра t найти максимум линейной формы

при

 

Решение начинаем при t=0:

 

 

 

 

 

План оптимален при  ,  где

.

Для того, чтобы исследовать задачу при , надо ввести в базис y₁, а при   –  ввести в базис x₁.

 

 

Этой таблице соответствует оптимальный план . Т.к. все  неположительны, и мы двигались влево по оси t, то последнюю строку не заполняем, т.к. полученный план будет оптимален для всех   и : . Исследуем модель при  . Из базиса выводим переменную x₄.

 

 

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