Теория двойственности в линейном программировании и ее применение в анализе решения задач линейного программ-ия.
Понятие пары взаимодвойственных задач линейного программирования: Всякой ЗЛП, называемой в дальнейшем исходной задачей, соответ-ет некоторая двойственная задача, построенная на основе исходной задачи по определенным правилам. Пара этих задач (исх. и двойств.) наз-ся симметричной, если все функциональные ограничения в исходной ЗЛП заданы неравенствами. В случае, если есть хотябы 1 равенство, эта пара наз-ся несимметричной. Правила построения двойственной задачи на основе исходной для симметричной и несимметричной одни и те же. Но для несимметрич. задач на 2 пункта правил больше. Рассмотрим правила для несимметричной задачи: Исходная задача:
(1) при ограничениях:
;
. Двойственная задача:
(1’) при ограничениях:
;
, Yk+1, Ym – не ограничены. 1. Каждому функциональному ограничению исходной задачи поставим в соответствие двойственную переменную. 2.Если в исходной задаче ограничение в сис-ме (2) задано неравенством типа £, то соответст-щая этому ограничению двойственная переменная ограничена по знаку и яв-ся не отрицательной (Yi³ 0). 3.Если же огранич-е исход-й задачи задано равенством, то двойственная переменная по знаку не ограничена, т.е. м. принимать значение от -¥ до +¥. 4.Коэфф-тами при переменных в целевой функции двойственной задачи яв-ся свободные члены в сис-ме (2) ограничений исходной задачи. При этом если в исходной задаче целевая ф-я максимизируется, то в двойственной задаче минимизир-ся. 5.Каждой неизвестной (переменной) в исходной ЗЛП в двойственной задаче соответ-ет ограничение. В этом ограничении коэфф-ми при двойственных переменных яв-ся коэфф-ты при данном Х, а свободным членом в этом огранич-ии яв-ся коэфф-т целевой ф-ии при этой же переменной. 6.Если в исходной ЗЛП переменная Хj ³ 0, то в двоиственной задаче j-е ограничение задается нерав-вом ³. Если в исходной задаче переменные Хj не ограничены по знаку, то в двойственной задаче ставим знак =. Сформулиров-е правила справедливы для след-х условий: 1.В исх. зад. целевая ф-я максимизир-ся. Если это усл-е не выполн-ся, то надо сначала привести целевую ф-ю к максимизации:
, т.е. надо изменить знаки у всех переменных. 2.Все ограничения нерав-ва заданы знаком £. Если это усл-е не вып-ся, надо умножить обе части нерав-ва на (-1) и изменить знак. Пара двойственных задач яв-ся взаимодвойственной, т.е. если двойственную зад. принять за исходную, привести ее к нужному виду, постоить к ней по правилам двойств-ю зад., то получим исходную задачу.
Экономическая интерпретация двойственной задачи линейного программирования: Прямая задача (исходная): Предприятие располагает m видами рес-сов с номерами i=1, …, m, из к-х м. изготовить n изделий с номерами j=1, …, n. Запас i-го рас-са – bi, прибыль от реализ-ии j-го изделия – Cj и норма расхода i-го рес-са на учетную единицу j-го изделия задана. Треб-ся опред-ть объемы выпуска каждого изделия, к-е обеспечивают в ограниченных рес-сах максимум прибыли.
(1),
,
. Двойственная задача: Предположим, что некая фирма желает взять в аренду рес-сы предприятия, тогда перед фирмой возникает задача опред-ть такие цены за ед-цу каждого рес-са Yi, к-е обеспечивали бы фирме минимальные затраты за аренду рес-сов предприятий и при этом заинтересовывали бы предприятия в передаче рес-сов в аренду фирме. L(Y) – выражает затраты фирмы.
. Столбик коэфф-тов при Х1 – комплект рес-сов, обеспечивающих пр-во одной шт. из n изделий.
,
.
Основные теоремы о взаимосвязи решений прямой и двойственной задач линейного программирования: Т-ма 1: Если исходная задача имеет конечное оптимальное реш-е, то и двойственная зад. имеет конечное оптимальное реш-е. При этом знач-я целевых функций при оптимальных реш-х совпадают.
- оптим-е реш-е исход-й зад.
- максимальное знач-е, значит
- оптимальное реш-е двойственной зад.
- минимальное знач-е;
. Т-ма 2: Если исходная задача не имеет реш-я, то целевая ф-я двойственной зад. не ограничена и, наоборот. Т-ма 3: Если
- допустимое реш-е исходной задачи и
- знач-е целевой функции исх. зад., соответ-щее этому допустимому реш-ю;
- допустимое реш-е двойственной задачи и
- знач-е целевой ф-ии двойств-й зад., соответ-щее этому реш-ю, то справедливо соотнош-е:
;
,
- максимальное знач-е.
. Если известно допустимое реш-е прямой и двойств-й зад., то допустимое реш-е исх. зад. м. принять в качестве оптимального с точностью до e> 0, если
. Реш-е яв-ся оптимальным с точностью до d %, если
. Т-ма 4: Если Х1, …, Хn – основные переменные исх-й зад., а
- дополнительные перемен-е;
- основные переменные двойств-й зад., а
- дополнит-е перемен-е, то справедливы соотнош-я:
;
;
.
Устойчивость структуры оптимального базиса задачи линейного программирования и способы оценки пределов изменения коэффициентов целевой функции и свободных членов задачи линейного программирования, не изменяющих оптимального базиса: Реш-е конкретных ЗЛП осущ-ся на конкретном цифровом материале, т.е. заданы конкретные цифры целевой ф-ии Ci. Если реальная информ-я в пр-ссе реш-я измен-ся, возникает вопрос: ранее полученное оптим-е реш-е остается по-прежнему оптим-м или нет, и в каких пределах остается оптим-м. Влияние изменений в исх-х данных на оптим-е реш-е характ-ет чувствительность реш-я к измен-ям среды. Если небольшие изм-я в исх-х данных вызывают необх-ть получения нового оптим-го реш-я, т.е. старое реш-е уже не яв-ся оптим-м, то говорят, что данное оптим-е реш-е чувствит-но к изменнению исход-х данных, и оно по этой причине не яв-ся устойчивым. Если исх-я инфор-я меняется значит-но, а структура (набор базисных переменных) оптим-го плана остается прежней, то такое реш-е – устоичивое, мало чувствительное к измен-ю исход-х данных. Поэтому после нахождения оптим-го реш-я необх-мо выполнить анализ устойчивости реш-я при этом анализе задача ставится такая: опр-ть пределы изменения (увелич-я, уменьш-я) исход-х (цифровых) данных, в к-х колебание цифровой информации не меняет стр-ру оптим-го плана, т.е. набор базисных переменных остается прежним. Если обозначить ч/з Cj – цену ед-цы выпускаемой прод-ии; Xj – физический объем выпуска (кол-во ед-ц), bi – запас i-го рес-са;
- норма расхода i-го рес-са на ед-цу j-го продукта; L(x) – стоимостной объем выпуска прод-ии, то зад. опр-я оптим-го объема выпуска прод-ии, обеспечивающего при данных запасах рес-сов максимум стоимостного объема выпуска прод-ии запишется:
, (2)
; (3)
. Предположим, что зад. решена и в оптим-й базис вошли переменные
, а остальные - яв-ся свободными. Тогда вектор переменных:
. Коэфф-ты при базисных перемен-х образуют матрицу:
; при небазис-х:
. Вектор С=(СБ, СНБ),
. Тогда (1)
, (2) АБХБ+АНБХНБ=В, (3) ХБ³ 0, ХНБ³ 0. Т.к. в оптим-м плане ХНБ=0, то АБХБ=В. Т.е. имеем сис-му m урав-й с m неизвестными, т.е. сущ-ет обратная матрица
. Тогда
. Если усл-е (2) умнож-ть на
, то:
. Если вместо вектора В задать вектор с приращением:
, тогда реш-е
, т.е.
. Реш-е остается оптимальным, если все базис-е перемен-е ост-ся ³ 0. Решая сис-му нерав-в (**) надо опр-ть предел измен-я DВ. Обозначив элементы обратной матрицы
как
, получаем:
, тогда
. Полагаем, что
, а
, тогда
, …,
. Решаем правую часть ур-я. Получаем, что если
,
. Если
, тогда обе части нерав-ва умнож-ем на (-1), т.е.
. Пределы изменения Db1:
. Тогда пределы изменения b1:
. Измен-е коэфф-в целевой ф-ии при реш-ии ЗЛП симпл.-методом оказывает влияние на величину Dj, характер-щую критерий оптимальности.
. В сучае max-ции ф-ии Dj³ 0, min-ции Dj£ 0. Если D не измен-ся, то и реш-е не изм-ся. Если коэфф-та при переменной – Сj, то, задав приращение DСj, новое знач-е
. Знач-е оценки:
,
,
,
;
. Чуть сложнее с базисными переменными:
;
;
: 1)
,
,
; 2)
,
;
.
Основные направления использования теории двойственности в экономическом анализе: Двойств-е оценки ресурсов опред-ют степень дефицитности рес-сов: по оптим-му плану произв-ва дефицитные (т.е. полностью используемые) рес-сы получают ненулевые оценки, а недефицитные – нулевые оценки. В оптим-й план пр-ва могут попасть только рентабельные, неубыточные виды продукции. Двойств-е оценки рес-сов показ-ют, на сколько денеж-х ед-ц изм-ся максимальная прибыль (выручка) от реализации прод-ии при измен-ии запаса соответ-щего рес-са на 1 ед-цу. Двойств-е оценки рес-сов могут служить инструментом анализа и принятия правильных реш-й в условиях постоянно меняющегося пр-ва. С помощью них возможно сопоставление оптим-х условных затрат и рез-тов пр-ва (в случае небольшого изменения рес-сов). При резких изменениях сами оценки могут стать другими, что приведет к невозможности их использ-я для анализа эффект-ти пр-ва. По соотношению двойств-х оценок м.б. определены рассчетные нормы заменяемости рес-сов, при соблюдении к-х проводимые замены в пределах устойчивости двойственных оценок не влияют на эффект-ть оптим-го плана.
Популярное: