Возможное, ограниченное первичное, но недопустимое двойственное в линейном программировании - PullRequest
Новая
       53

Возможное, ограниченное первичное, но недопустимое двойственное в линейном программировании

0 голосов
/ 08 декабря 2018

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

Первичное: 

min -4x + y
subject to 
5x - 2y <= 3
3x + y <= 2
x,y >= 0

Это дает оптимальное решение x = 7/11, y = 1 / 11.

Двойственная проблема:

max 3x' + 2y'
subject to
5x' + 3y' <= -4
-2x' + y' <= -1
x',y' <= 0

Это не имеет решения.Я рассчитал двойное неправильно или это возможно?

1 Ответ

0 голосов
/ 08 декабря 2018

Нет, это невозможно.Если простое число выполнимо и ограничено, то двойственное также должно быть выполнимым и ограниченным, и они должны иметь одинаковое оптимальное объективное значение (это следует из сильной двойственности для линейного программирования).Таким образом, в вашем случае вывод заключается в том, что двойственное должно быть неправильно сформировано.

Одна стандартная первичная / двойственная установка состоит в том, что первичное min c'x s.t. Ax >= b, x >= 0 имеет двойное max b'y s.t. A'y <= c, y >= 0.Мы можем легко получить ваше начальное в этой форме с помощью: 

min  -4x + y
s.t. -5x + 2y >= -3
     -3x - y >= -2
      x,y >= 0

Соответствующий двойник: 

max  -3a - 2b
s.t. -5a - 3b <= -4
     2a - b <= 1
     a, b >= 0

Двойник имеет оптимальное решение a = 7/11, b = 3/11и оптимальное объективное значение -27/11, которое в точности является оптимальным первичным объективным значением.

...