Двойная программа

Двойная программа

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

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

Построение двойной программы

Двойственная программа является симметрией первичной программы: существует ограничение для каждой переменной первичной программы; и двойная переменная для каждого ограничения основной программы; коэффициенты основной целевой функции являются элементами б дуального и наоборот. Обратите внимание, что двойственное двойственное является первичным.

симплексный метод Данцига, линейное программирование, двойственность, двойственность, двойная программа

Для следующих специальных правил преобразования первичное значение считается находящимся под каноническая форма :

  • Если переменная i первичного числа положительна или равна нулю, то ограничение i двойственного числа находится в канонической форме.
  • Если переменная i простого числа является действительным числом, то ограничение i двойственного числа является равенством (логично, если мы рассматриваем равенство как комбинацию «меньше или равно» и «больше или равно»)
  • Если ограничение j простого числа находится в канонической форме, то переменная j двойственного числа положительна или равна нулю.
  • Если ограничение j простого числа является равенством, то переменная j двойственного числа является действительным числом (логично, если мы рассматриваем равенство как комбинацию «меньше или равно» и «больше или равно»)

Учитывая преобразование линейная программа в канонической форме вторая точка и четвертая точка обычно не применяются при преобразовании в двойную для расчета симплекса!

Вот краткое изложение преобразования в Dual по канонической форме.

симплексный метод Данцига, линейное программирование, двойственность, двойственность, двойная программа

Слабая двойственность и сильная двойственность

Слабая двойственность : для любого решения двойственного и для любого решения простого целевое значение двойственного z=cx* больше или равно значению простого w=by*.

сильная двойственность : если у простого есть оптимальное решение x *, то у двойственного есть оптимальное решение y * и объективное значение основного равно значению двойственного.

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

Существует связь в решениях первичного и двойственного:

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

Интерпретация двойной программы

симплексный метод Данцига, линейное программирование, двойственность, двойственность, двойная программа
Делиться
ru_RURU
%d такие блоггеры, как: