Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2017-11-28 | 144 |
5.00
из
|
Заказать работу |
|
|
Двойственная задача.
Двойственность в математическом программировании (МП), как и вообще в математике, играет фундаментальную роль. Она выступает в качестве краеугольного камня соответствующих теорий, порождает арсенал конструктивных средств анализа математических моделей, построения эффективных алгоритмов решения задач и формальной оценки этой эффективности.
Если - некоторый исходный математический объект (модель), то двойственный объект , вообще говоря, выступает как некий внешний по отношению к объект ''наблюдения'' за . Двойственность в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, выпуклый анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность в математике в здание хотя в определенном смысле и единой, но гармонически организованной и насыщенной архитектуры.
Содержание двойственности в линейном программировании состоит в сопоставлении исходной задаче C другой задачи , формируемой поопределенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности; оценить скорость сходимости итерационных процессов для задачи C и т.д.
Если задача МП (или ЛП) - результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ моделируемой ситуации (моделируемого объекта), выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме. Затакого рода анализом закрепился термин - экономико-математический анализ. Профессионально сделанные пакеты прикладных программ (ППП), решающие задачи МП или ЛП, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа. Это дает экономистам хорошие возможности для оценки состояния экономических (или производственных) систем и идентификации параметров управления.
|
Прямая задача ЛП в стандартной форме записывается следующим образом:
при ограничениях:
Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.
Двойственная задача - это вспомогательная задача ЛП, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи. В литературе по ЛП в большинстве случаев рассматриваются формулировки двойственной задачи, соответствующие различным формам прямой задачи, которые в свою очередь определяются типом ограничений, знаками переменных и направлением оптимизации (максимизация или минимизация). Однако, практическое использование теории двойственности на самом деле не требует знания деталей различных формулировок двойственной задачи.
Приведем обобщенную формулировку двойственной задачи ЛП, которая применима к любой форме представления прямой задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой задачи ЛП к стандартной форме. Следует, однако, помнить, что приводимая ниже формулировка двойственной задачи является обобщенной в том смысле, что она применима ко всем формам прямой задачи.
Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:
|
1. число переменных в дв. зад. = числу нетривиальных ограничений пр. зад., при этом 1я двойственная переменная y1 соответствует 1му ограничению пр. зад, у2 соответствует 2-му ограничению пр.зад. и т.д. Если в 1ом ограничении пр. зад. знак ≤, то у1≥0, если знак ≥, то у1≤0, если знак =, то у1 (знак у противоположен знаку соответствующего ограничения).
2. целевая функция дв. зад. всегда min. При этом g (y)=byàmin, где у - вектор переменных дв. зад, b - вектор правых частей ограничений пр. зад.
3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором с коэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х1, 2e-х2 и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х1≥0, то в 1ом ограничении дв. зад. знак ≥, если х1≤0, то знак ≤, если х1 , то знак =.
Прямая задача Двойственная задача
f(x)=c1x1+c2x2+…+cnxn → max g(y)=b1y1+b2y2+…+bnyn → min
xi≤0 (i=1,2….m)
Из указанных правил построения двойственной задачи следует, что она имеет m переменных (y1, y2, …, ym) и n ограничений (соответствующих n переменным прямой задачи x1, x2, …, xn).
Рассмотрим теперь, как формируются остальные условия двойственной задачи: направление оптимизации, ограничения и знаки двойственных переменных.
Если решать прямую задачу очень сложно, то проще решить двойственную задачу. И имея оптимальную симплекс-таблицу двойственной задачи можно получить оптимальную симплекс-таблицу прямой задачи, не решая её.
Пример 1.(у Ани)
ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ
Двойственная задача.
Двойственность в математическом программировании (МП), как и вообще в математике, играет фундаментальную роль. Она выступает в качестве краеугольного камня соответствующих теорий, порождает арсенал конструктивных средств анализа математических моделей, построения эффективных алгоритмов решения задач и формальной оценки этой эффективности.
Если - некоторый исходный математический объект (модель), то двойственный объект , вообще говоря, выступает как некий внешний по отношению к объект ''наблюдения'' за . Двойственность в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, выпуклый анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность в математике в здание хотя в определенном смысле и единой, но гармонически организованной и насыщенной архитектуры.
|
Содержание двойственности в линейном программировании состоит в сопоставлении исходной задаче C другой задачи , формируемой поопределенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности; оценить скорость сходимости итерационных процессов для задачи C и т.д.
Если задача МП (или ЛП) - результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ моделируемой ситуации (моделируемого объекта), выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме. Затакого рода анализом закрепился термин - экономико-математический анализ. Профессионально сделанные пакеты прикладных программ (ППП), решающие задачи МП или ЛП, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа. Это дает экономистам хорошие возможности для оценки состояния экономических (или производственных) систем и идентификации параметров управления.
Прямая задача ЛП в стандартной форме записывается следующим образом:
при ограничениях:
Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.
Двойственная задача - это вспомогательная задача ЛП, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи. В литературе по ЛП в большинстве случаев рассматриваются формулировки двойственной задачи, соответствующие различным формам прямой задачи, которые в свою очередь определяются типом ограничений, знаками переменных и направлением оптимизации (максимизация или минимизация). Однако, практическое использование теории двойственности на самом деле не требует знания деталей различных формулировок двойственной задачи.
|
Приведем обобщенную формулировку двойственной задачи ЛП, которая применима к любой форме представления прямой задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой задачи ЛП к стандартной форме. Следует, однако, помнить, что приводимая ниже формулировка двойственной задачи является обобщенной в том смысле, что она применима ко всем формам прямой задачи.
Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:
1. число переменных в дв. зад. = числу нетривиальных ограничений пр. зад., при этом 1я двойственная переменная y1 соответствует 1му ограничению пр. зад, у2 соответствует 2-му ограничению пр.зад. и т.д. Если в 1ом ограничении пр. зад. знак ≤, то у1≥0, если знак ≥, то у1≤0, если знак =, то у1 (знак у противоположен знаку соответствующего ограничения).
2. целевая функция дв. зад. всегда min. При этом g (y)=byàmin, где у - вектор переменных дв. зад, b - вектор правых частей ограничений пр. зад.
3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором с коэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х1, 2e-х2 и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х1≥0, то в 1ом ограничении дв. зад. знак ≥, если х1≤0, то знак ≤, если х1 , то знак =.
Прямая задача Двойственная задача
f(x)=c1x1+c2x2+…+cnxn → max g(y)=b1y1+b2y2+…+bnyn → min
xi≤0 (i=1,2….m)
Из указанных правил построения двойственной задачи следует, что она имеет m переменных (y1, y2, …, ym) и n ограничений (соответствующих n переменным прямой задачи x1, x2, …, xn).
Рассмотрим теперь, как формируются остальные условия двойственной задачи: направление оптимизации, ограничения и знаки двойственных переменных.
Если решать прямую задачу очень сложно, то проще решить двойственную задачу. И имея оптимальную симплекс-таблицу двойственной задачи можно получить оптимальную симплекс-таблицу прямой задачи, не решая её.
|
Пример 1.(у Ани)
ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ
Т.4.4.1 (о допустимых решениях прямой и двойственной задач)
Если х – любое допустимое решение пр. зад., а у – любое допустимое решение дв. зад., то f (x)≤g (y).
Док-во:
х – допустимое решение пр. зад., значит х удовлетворяет ограничениям пр. зад.
Ах≤b
x≥0
y – допустимое решение дв. зад., значит y удовлетворяет ограничениям дв.зад.
АTy≥c
y≥0
f(x)=cx≤(ATy)x=(Ax)y≤by=g(y)(Непосредственной проверкой, т.е. вычислением левой и правой частей устанавливаем равенство (Ах)у= х (АTу))
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!