Дополнительные отличия

Дополнительные спреды

Дополнительные отклонения можно использовать, если первичное реализуемо и его решение ограничено, двойственное реализуемо и его решение также ограничено. Если значения прямого и двойственного решений равны, то они оптимальны для своей линейной программы, говорят о сильная двойственность. Иногда решение найти невозможно или бесполезно его вычислять. Поскольку основная и двойственная программы связаны, можно вывести решение обратной программы, используя дополнительные отклонения.

Процесс

Одна из основных теорем теории двойственности в линейное программирование есть теорема дополнительных отклонений. Эта теорема позволяет нам найти оптимальное решение двойственной задачи, когда мы знаем оптимальное решение прямой задачи (и наоборот) путем решения системы уравнений, образованной решающими переменными (основной и двойственной) и ограничениями (основной и двойная модель).

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

  1. Найдите допустимое решение на простом.
  2. Если это так, обратите внимание на ненулевые переменные (подразумевающие, что двойное ограничение насыщено) и слабые ограничения (подразумевающие, что двойная переменная равна нулю).
  3. Решите систему уравнений
  4. Проверьте сильную двойственность, т.е. решение простого уравнения идентично решению двойственного. В этом случае допустимое решение является оптимальным.

Версия I. Пусть x* и y* будут решениями простого и двойственного. Эти два решения оптимальны тогда и только тогда, когда:

  • для всех j от 1 до n
    • либо ограничение j двойственного
    • пусть х*я=0
    • или оба
  • для всех i от 1 до m
    • либо ограничение i основного числа насыщено
    • либо у*я=0
    • или оба

Второй вариант комплементарных пробелов позволяет лучше понять, как найти решение во взаимной программе. Для этого необходимо предположить, что оба условия версии I всегда верны.

Версия II. Решение x простого числа оптимально тогда и только тогда, когда существует вектор y* такой, что:

  • у* допустимо
  • шестья>0, то j-е ограничение двойственного
  • если i-е ограничение первичного числа не насыщено, то y*я=0.
  • и, наоборот, между двойственным и первичным.

Таким образом, после того как решение во взаимной программе найдено, остается только проверить сильную двойственность системы.

Пример 1

Рассмотрим следующую модель линейного программирования с двумя переменными, оптимальным решением которой является X = 14/5 и Y = 8/5 с оптимальным значением V = 20,8.

симплексный метод

Двойная модель, связанная с первичной моделью:

симплексный метод

Тогда теорема о дополнительной нежесткости показывает следующие отношения:

симплексный метод

Как мы знаем, X = 14/5 и Y = 8/5 (первое оптимальное решение). Если мы подставим эти значения X и Y в третье и четвертое уравнения (поскольку два ограничения первичного уравнения насыщаются и мы не можем ничего заключить об уравнениях 1 и 2), мы создадим систему уравнений в терминах A и B, решение которого соответствует A = 6/5 и B = 2/5. Если затем оценить целевую функцию в двойственной задаче этого решения, то получим: V = 12 (6/5) +16 (2/5) = 20,8, что аналогично оптимальному значению прямой задачи (сильная двойственность ).

Пример 2

Рассмотрим следующую проблему:

симплексный метод

Решение этой задачи: {42, 0, 10,4, 0, 0,4}. Двойственная проблема заключается в следующем:

симплексный метод

Тест на осуществимость. Первое ограничение насыщено, нет вывод для у1. Второе ограничение не насыщено, поэтому y2 = 0. Третье ограничение насыщено, ничего на y3.

Положительные переменные. x1 = 0, делать выводы нечего. x2 > 0, то второе ограничение дуала насыщается. x3 = 0, делать выводы нечего. x4 > 0, четвертое ограничение дуала насыщено.

Таким образом, решение двойственности должно удовлетворять: y2 = 0; у1 + у3 = 4; 4y1 + y3 = 1 с {1, 0, 3} в качестве решения. Значения первичного и двойственного эквивалентны, поэтому у нас есть оптимум.

Делиться
ru_RURU
%d такие блоггеры, как: