<<
>>

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

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

id="Рисунок 10082" class="lazyload" data-src="/files/uch_group46/uch_pgroup327/uch_uch1271/image/4468.gif">

где 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 — область допустимых решений. При λ = 0 строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Итак, (D) — оптимальное решение, при котором имеем L( (D))max. При различных значениях λ линия M'N', параллельная линии уровня MN, будет определенным образом поворачиваться вокруг точки D. Пусть при λ = λ1 прямая M'N' проходит через сторону CD многоугольника допустимых решений, а при λ = λ2 — через сторону DE. Тогда значения (D)опт и L((D))max не изменятся до тех пор, пока λ1 ≤ λ ≤ λ2. Такая картина будет повторяться до получения нового оптимального решения, соответствующего новой целевой функции, для которой существует свой диапазон изменения λ.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

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

  1. 4.3 Метод диагностического определения потребительной стоимости.
  2. 2.2 ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ ПРОЦЕССА НАХОЖДЕНИЯ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ
  3. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  4. БИБЛИОГРАФИЯ
  5. 7.3. Графическое решение задачи линейного программирования
  6. 7.8. Двойственные задачи линейного программирования
  7. 12.1. Постановка задачи и геометрический метод ее решения
  8. 12.2. Аналитический метод решения задач параметрического программирования
  9. 17.3. КОМПЬЮТЕРИЗАЦИЯ ЭКОНОМИЧЕСКИХ РАСЧЕТОВ
  10. 4.1. СУЩЕСТВУЮЩИЕ МЕТОДЫ ОПТИМИЗАЦИИ ПАРАМЕТРИЧЕСКИХ РЯДОВ МАШИН И ИХ ЭЛЕМЕНТОВ