SHPORA.net :: PDA

[ Back ]

Если для оптимального решения одной из пары двойственных задач какое-либо неравенство выполняется как строгое, то соответствующая ему переменная в оптимальном решении двойственной задачи равна 0. И наоборот, если какая-либо переменная в оптимальном решении двойственной задачи не равна 0, то соответствующее ограничение двойственной задачи при оптимальном решении обращается в равенство.

Док-во:

Пусть Х и У (векторы) - оптимальные решения пары двойственных задач. Тогда (система)

Yi* (Bi - Aik Xk*)=0

Xk*(AikYi*-Ck)=0

Где Yi*, Xk* - координаты соответствующих оптимальных решений.

Пусть X и У - оптимальные решения. Тогда

Х=Х*, Y=Y*

AikXk*  Bi (1) (i=1, .. m)

AikYi*  Ck(2) (k=1, .. n)

Т(vektorY*)=Z(vektorX*)

Вi Yi* =  CkXk* (i=1,.m, k=1, .n)

Возьмем первое ограничение и умножим его на Yi*, a второе на Xk*

Yi* AikXk*  Bi Yi*

Xk*AikYi*  Ck Xk*

Просуммируем первое ограничение по i:

Yi*AikXk*  BiYi* (I=1,.m)

(2) по k:

Xk*AikYi*  CkXk* (k=1,..n)

Правые части этих неравенств оказались равными (T=z), след-но

(I=1-m)  (k=1-n) Yi*AikXi*   (I=1-m) BiYi*

 (k=1-n)  (I=1-m) Xk*AikYi*   (k=1-n) CkXk*

Левые части неравенств, с одной стороны, меньше чем Т (вектор У), а с другой больше, чем z (вектор х), след-но это может выполняться в случае равенства

 Yi*  Aik Xk* -  Bi Yi* = 0

 Yi* ( AikXk* -  Bi ) = 0

След-но либо то 0, либо другое 0. Док-во достаточности состоит в том, что проводится рассуждение в обратную сторону.