فصل 12 وزیرانی: دوگان LP

این قبلا قسمت اولش را توضیح داده ام!

قضیه 12.2: قضیه ضعیف دوگان

اگر x=(x1,...,xn) و y=(y1,...,ym) به ترتیب دو جواب مجاز برای مساله های اصلی و دوگان باشند، داریم:

sum_j_1_n(cj*xj) >= sum_i_1_m(bi*yi)

اثبات: چون y دوگان پذیر است و xjها نامنفی هستند، داریم:

sum_j_1_n(cj*xj) >= sum_j_1_n( sum_i_1_m(aij*yi) * xj )

مشابه همین را برای x می نویسیم و حکم نتیجه می شود.

قضیه 12.3: (شرایط سستی مکمل): اگر x و y به ترتیب جوابهای مجاز مساله و دوگان آن باشند. آنگاه x و y هر دو بهینه اند اگر و تنها اگر شرایط زیر صادق باشند:

اولیه: به ازای هر j بین 1 تا n یا xj=0 باشد یا sum(aij yi) = cj

و

دوگان: به ازای هر i بین 1 تا m یا yi = 0 باشد یا sum(aij xj) = bi باشد.

(تا سر 12.2)