Двойственные задачи. Принцип двойственности. краткое описание

Двойственные задачи и принцип двойственности — краткое,но понятное объяснение с примером 1) Что такое двойственная задача - Для линейной задачи в общем виде большая часть оптимизаций имеет «породившую» ей пару: primal (первичная задача) и dual (двойственная задача). - Идея: к каждому ограничению primal ставится переменная (ценовой коэффициент в рамках задачи), и наоборот — к каждому коэффициенту в целевой функции primal ставится свой набор условий в dual. - Практически двойственная задача задаёт минимизацию (вместо максимизации) или наоборот, и связана с тем, как «стоят» ограничения и их влияние на достижение оптимума. 2) Как строится двойственная задача к линейной задаче - Примем стандартную форму primal: maximize c^T x при условиях Ax ≤ b и x ≥ 0. - Тогда двойственная задача: minimize b^T y при условиях A^T y ≥ c и y ≥ 0. - Где: - x — вектор переменных primal. - y — вектор переменных dual (их интерпретация зависит от задачи). - A — матрица коэффициентов ограничений primal. - b — правая часть ограничений primal. - c — коэффициенты в целевой функции primal. 3) Принцип двойственности - Слабая двойственность: для любого допустимого решения primal и любого допустимого решения dual выполняется неравенство: значение primal не превосходит значение dual (для maximize primal ≤ dual). - Сильная двойственность: при допустимости и ограниченности primal и dual оптимальные значения равны. То есть opt(primal) = opt(dual). - Условия: в линейном программировании слабая двойственность всегда выполняется, сильная двойственность выполняется, если primal (или dual) допустим и ограничен по значению (есть конечный оптимум). 4) Компоненты, полезные для понимания - Комплементарная слабость (complimentary slackness): на оптимуме выполняются условия: - для каждого ограничения i primal: y_i · (b_i − (A x)_i) = 0; - для каждой переменной j primal: x_j · ((A^T y)_j − c_j) = 0. Это означает: если ограничение не «притягивает» (слэк задан нулём), то соответствующаяdual‑переменная может быть положительной, и наоборот. - Экономическое толкование: двойственные переменные y часто интерпретируются как «теневые» или «shadow» цены на ресурсы. Они показывают, как меняется максимум primal, если увеличить правую часть ограничений на единицу. 5) Короткий пример (практическая иллюстрация) Primal: - Максимизируем z = 3x1 + 2x2 - при ограничениях: 2x1 + x2 ≤ 4 x1 + x2 ≤ 3 x1 ≥ 0, x2 ≥ 0 Двойственная задача: - Минимизируем w = 4y1 + 3y2 - при ограничениях: 2y1 + y2 ≥ 3 y1 + y2 ≥ 2 y1 ≥ 0, y2 ≥ 0 Проверим оптимум (быстрый обзор): - Найдём решение primal: вершины полигонa feasible: (0,0), (2,0), (1,2), (0,3). Значения z: 0, 6, 7, 6 соответственно. Оптимум z* = 7 достигается в x = (1, 2). - Решим dual: возьмём две активные ограничения в двойственной задаче и решим систему: 2y1 + y2 = 3 y1 + y2 = 2 Отсюда y1 = 1, y2 = 1. Стоимость: w = 4·1 + 3·1 = 7. - Видим, opt.primal = opt.dual = 7, что иллюстрирует сильную двойственность. - Комплементарная slackness: в оптимуме primal обе ограничения заданы равенствами, поэтому соответствующие dual‑переменные могут быть положительными; в случае dual и их умножение на slack равны нулю, что тоже выполняется. 6) Что это значит на практике - Двойственные задачи дают эффективный способ проверить оптимальность и получить ценовую информацию: величины y дают тени стоимости ресурса. - Если primal сложный для прямого решения, можно начать с dual или использовать оба параллельно, используя сильную двойственность и комплементарную slackness. - Принцип двойственности применим не только к классическим LP, но и к более общим формам оптимизаций, где аналогичные пары задач существуют (с соответствующими условиями существования и гладкости). Если нужна, могу привести другой пример или показать пошаговое решение конкретной задачи в формате primal-dual и проверить условия комплементарной слабости.