Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Линейное программирование с параметром в целевой функции



 

Пусть коэффициент cj целевой функции изменяется в пре­делах (cjc'j,cj + с''j), тогда для удобства решения задачи его можно заменить выражением

 

 

где c'j, с''j постоянные; λ — параметр, который изменяется в некоторых пределах (в общем случае от - до ).

В общем виде задача линейного программирования с пара­метром в целевой функции записывается так:

 

 

при ограничениях:

 

 

Для каждого значения λ в промежутке δ ≤ λ ≤ φ, где δ и φ — произвольные действительные числа, найти вектор (x1, x2,..., xп), удовлетворяющий системе ограничений и об­ращающий в максимум (минимум) целевую функцию.

Решая задачу на максимум симплексным методом и иссле­дуя ее решение в зависимости от изменения параметра λ, полу­чим выражения для определения нижнего (λ1) и верхнего (λ2) его значений:

 

 

где Δ"j, — оценка симплексной таблицы, содержащая пара­метр λ; Δ'j — оценка симплексной таблицы, не содержащая параметр λ.

Если для целевой функции отыскивается min, то границы изменения λ (λ1 и λ2) определяются следующим образом:

 

 

 

Приведем алгоритм решения.

1) Задачу решаем симплекс-методом при конкретном зна­чении параметра λ до получения оптимального решения.

2) Вычисляем значения параметров λ1, λ2.

3) Определяем множество значений параметра λ, для кото­рых полученное решение является оптимальным.

4) В случае необходимости в базис вводим вектор, соответ­ствующий столбцу, из которого определялось значение параметра λ2.

5) Выбираем ключевую строку и ключевой элемент.

6) Определяем новое оптимальное решение.

7) Находим новое множество значений λ, для которых ре­шение останется оптимальным.

8) Процесс вычисления повторяем до тех пор, пока весь от­резок [δ, φ] не будет исследован.

Выясним геометрический смысл задачи.

 

 

Пусть L( ) = (c'j + λc''jxj) → max. ABCDEF — область допустимых решений (рис. 25.1). При λ = 0 строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Итак, (D) — оп­тимальное решение, при котором имеем L( (D))max. При различных значениях λ линия M'N', параллельная линии уров­ня MN, будет определенным образом поворачиваться вокруг точки D. Пусть при λ = λ1 прямая M'N' проходит через сторо­ну CD многоугольника допустимых решений, а при λ = λ2 через сторону DE. Тогда значения (D)опт и L( (D))max не изменятся до тех пор, пока λ1 ≤ λ ≤ λ2. Такая картина будет повторяться до получения нового оптимального решения, соот­ветствующего новой целевой функции, для которой существует свой диапазон изменения λ.




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.