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

Высшая математика в экономике

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

Постановка задачи

Общая задача линейного программирования имеет вид

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть 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. Такая картина будет повторяться до получения нового оптимального решения, соответствующего новой целевой функции, для которой существует свой диапазон изменения

Комплексные числа.

Понятие о комплексных числах.

 Определение. Комплексным числом z называется выражение , где a и b – действительные числа, i – мнимая единица, которая определяется соотношением:

  При этом число a называется действительной частью числа z (a = Re z), а b- мнимой частью (b = Im z).

 Если a =Re z =0, то число z будет чисто мнимым, если b = Im z = 0, то число z будет действительным.

 Определение. Числа  и называются комплексно – сопряженными.

 Определение. Два комплексных числа  и  называются равными, если соответственно равны их действительные и мнимые части:

  Определение. Комплексное число равно нулю, если соответственно равны нулю действительная и мнимая части.

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

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

 


 у

 A(a, b)

 r b

  j

 0 a x

 Таким образом, на оси ОХ располагаются действительные числа, а на оси ОY – чисто мнимые.

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

Определение диапазона оптимального решения выпуска продукции при изменении условий реализации

Транспортная параметрическая задача

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

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

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

Свойства бесконечно малых функций.

Сумма фиксированного числа бесконечно малых функций при х®а тоже бесконечно малая функция при х®а.

Произведение фиксированного числа бесконечно малых функций при х®а тоже бесконечно малая функция при х®а.

Произведение бесконечно малой функции на функцию, ограниченную вблизи точки х = а является бесконечно малой функцией при х®а.

Частное от деления бесконечно малой функции на функцию, предел которой не равен нулю есть величина бесконечно малая.

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

Доказательство теоремы 2. Представим f(x) = A + a(x), g(x) = B + b(x), где

, тогда

f(x) ± g(x) = (A + B) + a(x) + b(x)

A + B = const, a(х) + b(х) – бесконечно малая, значит

Теорема доказана.

Доказательство теоремы 3. Представим f(x) = A + a(x), g(x) = B + b(x), где

, тогда

A×B = const, a(х) и b(х) – бесконечно малые, значит

Теорема доказана.


Элементы системы массового обслуживания