Двойственная задача позволяет проверить корректность решения исходной задачи линейного программирования и часто дает более удобную форму для вычислений. Она строится по строгим правилам, основанным на структуре исходной модели, и помогает анализировать чувствительность решения к изменениям параметров.
При составлении двойственной задачи важно определить, является ли исходная модель задачей на максимум или на минимум. От этого зависит направление неравенств и знаки переменных. Каждому ограничению прямой задачи соответствует переменная двойственной, а каждому показателю целевой функции – ограничение двойственной системы.
Коэффициенты целевой функции прямой задачи переходят в правые части ограничений двойственной, а коэффициенты при ограничениях – в целевую функцию двойственной задачи. Такой переход требует внимательного соблюдения порядка строк и столбцов, чтобы не нарушить взаимосвязь между переменными.
Построив двойственную модель, можно проверить равенство оптимальных значений обеих задач и определить, при каких условиях исходное решение сохраняет оптимальность. Этот подход используется в анализе экономических моделей, планировании производства и оценке ресурсов, где важно понимать предельные значения ограничений и влияние коэффициентов на итоговый результат.
Определение типа исходной задачи: минимизация или максимизация
Перед построением двойственной задачи необходимо точно определить, что делает исходная модель – минимизирует или максимизирует целевую функцию. От этого зависит направление неравенств в ограничениях и знаки переменных двойственной задачи.
Если исходная задача формулируется как максимизация функции прибыли, выручки или выхода продукции, то двойственная задача будет задачей на минимизацию. В случае, когда исходная модель описывает минимизацию затрат, времени или потребления ресурсов, соответствующая двойственная задача превращается в задачу на максимизацию.
Для корректного перехода необходимо привести исходную задачу к стандартной форме. При максимизации все ограничения записываются как «≤», а при минимизации – как «≥». Если встречаются равенства, их следует заменить двумя противоположными неравенствами или ввести вспомогательные переменные. Такое преобразование обеспечивает возможность прямого построения двойственной модели без дополнительных допущений.
Ошибки при определении направления оптимизации приводят к неверным знакам в системе двойственной задачи и искажению экономического смысла переменных. Поэтому тип исходной задачи фиксируют на первом этапе и не изменяют при дальнейшем преобразовании.
Преобразование ограничений прямой задачи к стандартной форме
Перед составлением двойственной задачи необходимо привести прямую задачу к стандартной форме. Это обеспечивает однозначное соответствие между переменными и ограничениями обеих задач.
Стандартная форма линейной задачи записывается так:
максимизировать: z = cTx
при условиях:
- Ax ≤ b
- x ≥ 0
Если ограничения не соответствуют этим условиям, выполняются следующие преобразования:
- Неравенства “≥”. Умножить обе части на –1, чтобы получить вид “≤”.
Пример: 2x₁ + x₂ ≥ 5 преобразуется в –2x₁ – x₂ ≤ –5. - Равенства. Разбиваются на два неравенства:
2x₁ + x₂ = 5 заменяется на
2x₁ + x₂ ≤ 5 и 2x₁ + x₂ ≥ 5 (далее преобразуется как в пункте 1).
- Переменные без ограничений знака. Каждая такая переменная представляется разностью двух неотрицательных:
xj = x’j – x»j, где x’j ≥ 0 и x»j ≥ 0. - Ограничения “≥” в задаче на минимум. При минимизации целевой функции направление неравенств меняется на противоположное:
Ax ≥ b преобразуется в –A x ≤ –b. - Свободный член с отрицательным значением. Если bi < 0, то ограничение умножается на –1, чтобы правая часть стала неотрицательной.
Пример: –x₁ + 3x₂ ≤ –6 → x₁ – 3x₂ ≥ 6 → –x₁ + 3x₂ ≤ –6 (в зависимости от нужного направления).
После всех преобразований система ограничений принимает вид, пригодный для дальнейшего составления двойственной задачи. Каждый элемент матрицы A и вектора b при этом должен быть четко определён и согласован по размерности.
Определение числа и знаков переменных двойственной задачи
Число переменных двойственной задачи определяется количеством ограничений прямой задачи в стандартной форме. Каждое ограничение прямой задачи соответствует одной переменной двойственной задачи.
Знаки переменных устанавливаются по виду ограничения:
- Ограничение Ax ≤ b: соответствующая двойственная переменная y ≥ 0.
- Ограничение Ax ≥ b: соответствующая двойственная переменная y ≤ 0.
- Ограничение Ax = b: соответствующая двойственная переменная свободна по знаку.
При этом необходимо учитывать, что порядок ограничений прямой задачи определяет порядок переменных в двойственной задаче. Нарушение соответствия приведёт к неверной матрице коэффициентов.
Пример для задачи с тремя ограничениями:
- 1-е ограничение ≤ → y₁ ≥ 0
- 2-е ограничение ≥ → y₂ ≤ 0
- 3-е ограничение = → y₃ свободна
После определения числа и знаков переменных двойственная задача может быть составлена с точным соответствием коэффициентов и направлений неравенств.
Построение целевой функции двойственной задачи
Целевая функция двойственной задачи формируется на основе свободных членов ограничений прямой задачи. Если прямая задача имеет вид:
максимизировать z = c₁x₁ + c₂x₂ + … + cₙxₙ
при ограничениях Ax ≤ b, x ≥ 0, то целевая функция двойственной задачи записывается как:
минимизировать w = b₁y₁ + b₂y₂ + … + bmym
Каждый коэффициент bi в целевой функции двойственной задачи берется из соответствующего ограничения прямой задачи. Переменные yi соответствуют каждому ограничению прямой задачи, а их знак определяется типом ограничения.
Если прямая задача минимизации:
минимизировать z = cTx
при ограничениях Ax ≥ b, x ≥ 0, то целевая функция двойственной задачи формируется как:
максимизировать w = b₁y₁ + b₂y₂ + … + bmym
Рекомендуется сохранять порядок ограничений при подстановке bi в целевую функцию, чтобы коэффициенты переменных двойственной задачи точно соответствовали строкам матрицы ограничений прямой задачи.
В случае смешанных типов ограничений (≤, ≥, =) целевая функция составляется одинаково, меняется только знак переменных yi в зависимости от типа ограничения.
Формирование системы ограничений двойственной задачи
Система ограничений двойственной задачи строится на основе коэффициентов целевой функции и ограничений прямой задачи. Каждое исходное неизвестное xj прямой задачи порождает одно ограничение в двойственной.
Общие правила:
- Если прямая задача максимизации z = cTx при ограничениях Ax ≤ b, x ≥ 0, то для каждой переменной xj формируется ограничение двойственной задачи:
a₁j·y₁ + a₂j·y₂ + … + amj·ym ≥ cj. - Если прямая задача минимизации z = cTx при ограничениях Ax ≥ b, x ≥ 0, то ограничения двойственной задачи имеют вид:
a₁j·y₁ + a₂j·y₂ + … + amj·ym ≤ cj. - Для переменных прямой задачи без ограничений знака соответствующее ограничение двойственной задачи является равенством:
a₁j·y₁ + a₂j·y₂ + … + amj·ym = cj. - Знак переменных yi в двойственной задаче определяется типом ограничения прямой задачи (≤, ≥, =).
- Соблюдать порядок переменных и коэффициентов: строка матрицы A соответствует конкретной переменной yi, столбец – соответствующей переменной xj.
После построения ограничений проверяется соответствие размерностей: число ограничений двойственной задачи равно числу переменных прямой задачи, а число переменных двойственной задачи равно числу ограничений прямой задачи.
Связь между коэффициентами прямой и двойственной задач
Коэффициенты матрицы ограничений прямой задачи становятся коэффициентами переменных в ограничениях двойственной задачи. Если прямая задача задаётся матрицей A = [aij], то ограничение двойственной задачи для переменной xj имеет вид:
a₁j·y₁ + a₂j·y₂ + … + amj·ym ≥ cj при максимизации прямой задачи,
a₁j·y₁ + a₂j·y₂ + … + amj·ym ≤ cj при минимизации прямой задачи.
Свободные члены bi прямой задачи формируют коэффициенты целевой функции двойственной задачи:
w = b₁y₁ + b₂y₂ + … + bmym
Порядок коэффициентов сохраняется: строка A соответствует конкретной переменной двойственной задачи, столбец – переменной прямой задачи. Нарушение порядка приводит к несоответствию между ограничениями и переменными.
Знаки переменных двойственной задачи определяются типом ограничения прямой задачи: ≤ → y ≥ 0, ≥ → y ≤ 0, = → свободная переменная.
Такое прямое соответствие коэффициентов обеспечивает корректное преобразование задачи и позволяет анализировать решения прямой и двойственной задач совместно.
Проверка взаимной допустимости и равенства оптимальных значений
Взаимная допустимость означает, что решение прямой задачи удовлетворяет ограничениям двойственной, и наоборот. Проверка проводится по следующей схеме:
- Определить решение прямой задачи x* и подставить его в ограничения двойственной задачи.
- Определить решение двойственной задачи y* и подставить его в ограничения прямой задачи.
- Если все неравенства выполняются, решения взаимно допустимы.
Равенство оптимальных значений проверяется по формуле двойственности:
z* = cTx* = bTy* = w*
Пример проверки:
| Прямая задача | Двойственная задача |
|---|---|
|
Максимизация: z = 3x₁ + 2x₂ Ограничения: x₁ + x₂ ≤ 4 2x₁ + x₂ ≤ 5 x₁, x₂ ≥ 0 |
Минимизация: w = 4y₁ + 5y₂ Ограничения: y₁ + 2y₂ ≥ 3 y₁ + y₂ ≥ 2 y₁, y₂ ≥ 0 |
Если найденные решения x* = (2,2) и y* = (1,1) удовлетворяют ограничениям и z* = 10 = w*, проверка взаимной допустимости и равенства оптимальных значений подтверждается.
Вопрос-ответ:
Как определить количество переменных в двойственной задаче?
Количество переменных в двойственной задаче совпадает с количеством ограничений прямой задачи, приведённой к стандартной форме. Каждое ограничение порождает одну переменную. При этом необходимо соблюдать порядок ограничений, чтобы коэффициенты двойственной задачи соответствовали строкам матрицы ограничений прямой задачи.
Как правильно выбрать знак переменных двойственной задачи?
Знак переменной двойственной задачи зависит от типа соответствующего ограничения прямой задачи. Для ограничений вида «≤» переменная двойственной задачи должна быть неотрицательной. Для ограничений вида «≥» переменная берётся с условием «≤ 0». Для равенств переменная двойственной задачи свободна по знаку. Это правило сохраняется независимо от того, максимизируется или минимизируется целевая функция прямой задачи.
Как формируется целевая функция двойственной задачи?
Целевая функция двойственной задачи строится из свободных членов ограничений прямой задачи. Если прямая задача максимизации имеет ограничения Ax ≤ b, то двойственная задача минимизации будет иметь целевую функцию вида w = b₁y₁ + b₂y₂ + … + bmym. Для задачи минимизации с ограничениями Ax ≥ b целевая функция двойственной задачи будет максимизацией с теми же коэффициентами bi. Порядок коэффициентов должен соответствовать порядку ограничений прямой задачи.
Как построить систему ограничений двойственной задачи по переменным прямой задачи?
Каждая переменная прямой задачи формирует одно ограничение в двойственной задаче. Коэффициенты ограничения берутся из соответствующего столбца матрицы A прямой задачи, а знак неравенства зависит от типа исходной задачи: для максимизации прямой задачи неравенство «≥», для минимизации — «≤». Если переменная прямой задачи не имеет ограничений по знаку, ограничение в двойственной задаче становится равенством.
Как проверить, что решения прямой и двойственной задач взаимно допустимы и оптимальны?
Для проверки взаимной допустимости нужно подставить решение прямой задачи в ограничения двойственной и проверить выполнение всех неравенств, а затем подставить решение двойственной задачи в ограничения прямой. Если все условия выполнены, решения взаимно допустимы. Равенство оптимальных значений проверяется через формулу: z* = cᵀx* = bᵀy* = w*. Если значения совпадают, оба решения являются оптимальными.
Как связаны коэффициенты прямой задачи с ограничениями двойственной?
Коэффициенты прямой задачи из матрицы A становятся коэффициентами переменных в ограничениях двойственной задачи. Для каждой переменной прямой задачи формируется одно ограничение двойственной задачи, где коэффициенты берутся из соответствующего столбца матрицы A. Свободные члены прямой задачи формируют целевую функцию двойственной задачи. При этом порядок строк и столбцов строго соблюдается, чтобы коэффициенты соответствовали переменным и ограничениям.
Что делать с переменными прямой задачи, которые не имеют ограничений по знаку?
Если переменная прямой задачи свободна по знаку, соответствующее ограничение в двойственной задаче оформляется как равенство. Это позволяет точно отразить влияние такой переменной на целевую функцию двойственной задачи. Остальные переменные, ограниченные неотрицательностью, формируют ограничения двойственной задачи с неравенством, соответствующим направлению задачи (максимизация или минимизация).
Загрузка...
