Теория двойственности в линейном программировании и ее применение в анализе решения задач линейного программ-ия.

⇐ ПредыдущаяСтр 24 из 51Следующая ⇒

Понятие пары взаимодвойственных задач линейного программирования: Всякой ЗЛП, называемой в дальнейшем исходной задачей, соответ-ет некоторая двойственная задача, построенная на основе исходной задачи по определенным правилам. Пара этих задач (исх. и двойств.) наз-ся симметричной, если все функциональные ограничения в исходной ЗЛП заданы неравенствами. В случае, если есть хотябы 1 равенство, эта пара наз-ся несимметричной. Правила построения двойственной задачи на основе исходной для симметричной и несимметричной одни и те же. Но для несимметрич. задач на 2 пункта правил больше. Рассмотрим правила для несимметричной задачи: Исходная задача: (1) при ограничениях: ; . Двойственная задача: (1’) при ограничениях: ; , Y_k₊₁, Y_m – не ограничены. 1. Каждому функциональному ограничению исходной задачи поставим в соответствие двойственную переменную. 2.Если в исходной задаче ограничение в сис-ме (2) задано неравенством типа £, то соответст-щая этому ограничению двойственная переменная ограничена по знаку и яв-ся не отрицательной (Y_i³ 0). 3.Если же огранич-е исход-й задачи задано равенством, то двойственная переменная по знаку не ограничена, т.е. м. принимать значение от -¥ до +¥. 4.Коэфф-тами при переменных в целевой функции двойственной задачи яв-ся свободные члены в сис-ме (2) ограничений исходной задачи. При этом если в исходной задаче целевая ф-я максимизируется, то в двойственной задаче минимизир-ся. 5.Каждой неизвестной (переменной) в исходной ЗЛП в двойственной задаче соответ-ет ограничение. В этом ограничении коэфф-ми при двойственных переменных яв-ся коэфф-ты при данном Х, а свободным членом в этом огранич-ии яв-ся коэфф-т целевой ф-ии при этой же переменной. 6.Если в исходной ЗЛП переменная Х_j ³ 0, то в двоиственной задаче j-е ограничение задается нерав-вом ³. Если в исходной задаче переменные Х_j не ограничены по знаку, то в двойственной задаче ставим знак =. Сформулиров-е правила справедливы для след-х условий: 1.В исх. зад. целевая ф-я максимизир-ся. Если это усл-е не выполн-ся, то надо сначала привести целевую ф-ю к максимизации: , т.е. надо изменить знаки у всех переменных. 2.Все ограничения нерав-ва заданы знаком £. Если это усл-е не вып-ся, надо умножить обе части нерав-ва на (-1) и изменить знак. Пара двойственных задач яв-ся взаимодвойственной, т.е. если двойственную зад. принять за исходную, привести ее к нужному виду, постоить к ней по правилам двойств-ю зад., то получим исходную задачу.

Экономическая интерпретация двойственной задачи линейного программирования: Прямая задача (исходная): Предприятие располагает m видами рес-сов с номерами i=1, …, m, из к-х м. изготовить n изделий с номерами j=1, …, n. Запас i-го рас-са – b_i, прибыль от реализ-ии j-го изделия – Cj и норма расхода i-го рес-са на учетную единицу j-го изделия задана. Треб-ся опред-ть объемы выпуска каждого изделия, к-е обеспечивают в ограниченных рес-сах максимум прибыли. (1), , . Двойственная задача: Предположим, что некая фирма желает взять в аренду рес-сы предприятия, тогда перед фирмой возникает задача опред-ть такие цены за ед-цу каждого рес-са Y_i, к-е обеспечивали бы фирме минимальные затраты за аренду рес-сов предприятий и при этом заинтересовывали бы предприятия в передаче рес-сов в аренду фирме. L(Y) – выражает затраты фирмы. . Столбик коэфф-тов при Х₁ – комплект рес-сов, обеспечивающих пр-во одной шт. из n изделий. , .

Основные теоремы о взаимосвязи решений прямой и двойственной задач линейного программирования: Т-ма 1: Если исходная задача имеет конечное оптимальное реш-е, то и двойственная зад. имеет конечное оптимальное реш-е. При этом знач-я целевых функций при оптимальных реш-х совпадают. - оптим-е реш-е исход-й зад. - максимальное знач-е, значит - оптимальное реш-е двойственной зад. - минимальное знач-е; . Т-ма 2: Если исходная задача не имеет реш-я, то целевая ф-я двойственной зад. не ограничена и, наоборот. Т-ма 3: Если - допустимое реш-е исходной задачи и - знач-е целевой функции исх. зад., соответ-щее этому допустимому реш-ю; - допустимое реш-е двойственной задачи и - знач-е целевой ф-ии двойств-й зад., соответ-щее этому реш-ю, то справедливо соотнош-е: ; , - максимальное знач-е. . Если известно допустимое реш-е прямой и двойств-й зад., то допустимое реш-е исх. зад. м. принять в качестве оптимального с точностью до e> 0, если . Реш-е яв-ся оптимальным с точностью до d %, если . Т-ма 4: Если Х₁, …, Х_n – основные переменные исх-й зад., а - дополнительные перемен-е; - основные переменные двойств-й зад., а - дополнит-е перемен-е, то справедливы соотнош-я: ; ; .

Устойчивость структуры оптимального базиса задачи линейного программирования и способы оценки пределов изменения коэффициентов целевой функции и свободных членов задачи линейного программирования, не изменяющих оптимального базиса: Реш-е конкретных ЗЛП осущ-ся на конкретном цифровом материале, т.е. заданы конкретные цифры целевой ф-ии C_i. Если реальная информ-я в пр-ссе реш-я измен-ся, возникает вопрос: ранее полученное оптим-е реш-е остается по-прежнему оптим-м или нет, и в каких пределах остается оптим-м. Влияние изменений в исх-х данных на оптим-е реш-е характ-ет чувствительность реш-я к измен-ям среды. Если небольшие изм-я в исх-х данных вызывают необх-ть получения нового оптим-го реш-я, т.е. старое реш-е уже не яв-ся оптим-м, то говорят, что данное оптим-е реш-е чувствит-но к изменнению исход-х данных, и оно по этой причине не яв-ся устойчивым. Если исх-я инфор-я меняется значит-но, а структура (набор базисных переменных) оптим-го плана остается прежней, то такое реш-е – устоичивое, мало чувствительное к измен-ю исход-х данных. Поэтому после нахождения оптим-го реш-я необх-мо выполнить анализ устойчивости реш-я при этом анализе задача ставится такая: опр-ть пределы изменения (увелич-я, уменьш-я) исход-х (цифровых) данных, в к-х колебание цифровой информации не меняет стр-ру оптим-го плана, т.е. набор базисных переменных остается прежним. Если обозначить ч/з C_j – цену ед-цы выпускаемой прод-ии; X_j – физический объем выпуска (кол-во ед-ц), b_i – запас i-го рес-са; - норма расхода i-го рес-са на ед-цу j-го продукта; L(x) – стоимостной объем выпуска прод-ии, то зад. опр-я оптим-го объема выпуска прод-ии, обеспечивающего при данных запасах рес-сов максимум стоимостного объема выпуска прод-ии запишется: , (2) ; (3) . Предположим, что зад. решена и в оптим-й базис вошли переменные , а остальные - яв-ся свободными. Тогда вектор переменных: . Коэфф-ты при базисных перемен-х образуют матрицу: ; при небазис-х: . Вектор С=(С_Б, С_НБ), . Тогда (1) , (2) А_БХ_Б+А_НБХ_НБ=В, (3) Х_Б³ 0, Х_НБ³ 0. Т.к. в оптим-м плане Х_НБ=0, то А_БХ_Б=В. Т.е. имеем сис-му m урав-й с m неизвестными, т.е. сущ-ет обратная матрица . Тогда . Если усл-е (2) умнож-ть на , то: . Если вместо вектора В задать вектор с приращением: , тогда реш-е , т.е. . Реш-е остается оптимальным, если все базис-е перемен-е ост-ся ³ 0. Решая сис-му нерав-в (**) надо опр-ть предел измен-я DВ. Обозначив элементы обратной матрицы как , получаем: , тогда . Полагаем, что , а , тогда , …, . Решаем правую часть ур-я. Получаем, что если , . Если , тогда обе части нерав-ва умнож-ем на (-1), т.е. . Пределы изменения Db₁: . Тогда пределы изменения b₁: . Измен-е коэфф-в целевой ф-ии при реш-ии ЗЛП симпл.-методом оказывает влияние на величину Dj, характер-щую критерий оптимальности. . В сучае max-ции ф-ии Dj³ 0, min-ции Dj£ 0. Если D не измен-ся, то и реш-е не изм-ся. Если коэфф-та при переменной – С_j, то, задав приращение DС_j, новое знач-е . Знач-е оценки: , , , ; . Чуть сложнее с базисными переменными: ; ; : 1) , , ; 2) , ; .

Основные направления использования теории двойственности в экономическом анализе: Двойств-е оценки ресурсов опред-ют степень дефицитности рес-сов: по оптим-му плану произв-ва дефицитные (т.е. полностью используемые) рес-сы получают ненулевые оценки, а недефицитные – нулевые оценки. В оптим-й план пр-ва могут попасть только рентабельные, неубыточные виды продукции. Двойств-е оценки рес-сов показ-ют, на сколько денеж-х ед-ц изм-ся максимальная прибыль (выручка) от реализации прод-ии при измен-ии запаса соответ-щего рес-са на 1 ед-цу. Двойств-е оценки рес-сов могут служить инструментом анализа и принятия правильных реш-й в условиях постоянно меняющегося пр-ва. С помощью них возможно сопоставление оптим-х условных затрат и рез-тов пр-ва (в случае небольшого изменения рес-сов). При резких изменениях сами оценки могут стать другими, что приведет к невозможности их использ-я для анализа эффект-ти пр-ва. По соотношению двойств-х оценок м.б. определены рассчетные нормы заменяемости рес-сов, при соблюдении к-х проводимые замены в пределах устойчивости двойственных оценок не влияют на эффект-ть оптим-го плана.

⇐ Предыдущая 19 20 21 22 232425 26 27 28 Следующая ⇒