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

F(x,λ)=(c1’+ λc1”)x1+(c2’+ λc2”)x2+…+(cj’+ λcj”)xj+…+(cn’+ λcn”)xnàmax

cj’+ λcj” – цены

λ – скалярный параметр (показывает темп изменения цен реализации)

λ ≤ λ ≤ λ (м.б. время)

Возможные результаты:

считается, что задача разрешима при λ = 0

0 ≤ λ ≤ λ (исследуется вправо до заданной величины)

С ростом параметра λ значение может меняться

х2

 

Р

Q

 

 

R

 

х1

Существует область устойчивости при изменении параметра λ – область в которой сохраняются признаки текущей вершины

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

Каждая локальная область м.б. точкой или отрезком или лучом.

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

Теорема: Алгоритм симплекс-типа со специальными правилами перехода от текущего базиса к следующему позволяет полностью исследовать модель за конечное число шагов при условии, что предпринимаются меры против зацикливания процессов.

PàQàR

F(λ) ~ F(λ) ~ F(λ)

Если цепочка состоит из более, чем 5 вершин, то возникает цикл.

Практическое применение модели: 1) цены; 2) выпуск железа; 3) глубина обогащения сырья.

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

Области устойчивости при этом не определяются, график функции при этом F(λ) будет получен.

При изменении параметра λ, меняется оценка оптимальности Δj

Δj = Δj’+ λΔj” ≥ 0 j=1,n

Оценки ресурсов: yi*, i=1,m y* = yi*

В каждой области устойчивости свой фикс. вектор оценок на ресурсы.

Типы моделей, для которых используются строгие эффективные методы:

1) Функция цели зависит от λ – PARAOBJ, F(x, λ)

2) Функция цели зависит от параметра b’+μb” – PARARHS

3) зависимость от t

4) два различных параметра – λ и μ

5) Любая строка матрицы условий зависит от параметра PARAROW (параметры вводятся только в строки)

(ai1*+µai1**) -1й элемент

(аi2*+µаi2**) – 2й элемент

0≤µ≤µ - количественный параметр

аi2* - коэф-т расхода сырья

аi2** - темпы изменения по линейному закону

6) Любой столбец зависит от параметра PARACOL (столбцы условий) Когда вводятся параметры в столбцы. Третий случай – когда добавляются ещё цены реализации 0≤t≤t’

Функция второго порядка F(t)=F*+tF**+t²F***

Цены меняются вне зависимости от запасов на складе – двухпараметрическая модель