آزادسازی در برنامه ریزی خطی. در ریاضی و دانش رایانه، واهِلِش به برنامه نویسی خطی برنامه ای دُرُست ( integer program ) را به برنامه ای خطی می ترادیساند. در این ترادیسی، هر متغیر x i ∈ { 0 , 1 } در برنامهٔ درست با متغیری خطی 0 ≤ x i ≤ 1 جایگزین می شود. این واهلش پرسمانی ان پی سخت را به پرسمانی خطی که در زمانی چند جمله ای حل می شود می ترادیساند. پاسخ به برنامهٔ خطی به دست آمده، اطلاع های سودمندی را دربارهٔ برنامهٔ درست اصلی فراهم می آورد.
برای نمونه، به پرسمان پوشش مجموعه می پردازیم. مجموعه ای مانند F و زیرمجموعه های S 0 , S 1 , . . . ⊆ U از این مجموعه داده شده اند. این پرسمان شماری از S i ها را می جوید که یکایش ( اجتماع ) این زیرمجموعه ها مجموعه F خواهد بود.
در برنامهٔ درست برای پوشش مجموعه، برای هر زیرمجموعهٔ S i متغیری بولی x i داریم.
یکایش زیرمجموعه های گزینش شده باید برابر با F باشد. به سخنی دیگر، هر e j ∈ F باید در این یکایش باشد: ∑ { i | e j ∈ S i } x j ≥ 1 . این پاوند را پاوند یکایش می نامیم.
هم چنین، پاوندِ x i ∈ { 0 , 1 } برای هر متغیر x i نشان می دهد که آیا زیرمجموعه S i در پاسخ خواهد بود یا نه. به سخنی دیگرِ، ارزش یک/صفر برای x i نشان می دهد که زیرمجموعهٔ S i در پوشش هست/نیست. این پاوند را پاوند بولی می نامیم.
پرسمان کم ترین شمار زیرمجموعه ها را می جوید: min ∑ i x i .
واهلش به برنامهٔ خطی هر پاوند بولی x i ∈ { 0 , 1 } را با پاوند 0 ≤ x i ≤ 1 جایگزین می کند. برنامهٔ خطی به دست آمده وزنی را برای هر زیرمجموعه فرضیده است؛ ولی، پاوند یکایش یکسان می ماند. در پاسخ به این برنامهٔ خطی، جمع وزن همهٔ زیرمجموعه هایی چون S i که دربردارندهٔ عضو e j ∈ F برابر با یک خواهند بود.
به این نمونه از پوشش مجموعه ای بنگرید: مجموعهٔ F = { a , b , c } و زیرمجموعه های S 1 = { a , b } , S 2 = { b , c } , S 3 = { a , c } را داریم. در برنامهٔ درست، سه متغیر x 1 , x 2 , x 3 خواهیم داشت. برای هر کدام از a , b , c ∈ F یک پاوند یکایش هست. برای نمونه، برای a پاوندِ x 1 + x 3 ≥ 1 را داریم. هم چنین، برای هر S i یک پاوند بولی 0 ≤ x i ≤ 1 داریم.
گزینش هر جفت از زیرمجموعه های S 1 , S 2 , S 3 پاسخی بهین است. به سخنی دیگر، هر یک از { S 1 , S 2 } ، { S 1 , S 3 } یا { S 2 , S 3 } یک پوشش مجموعه ای کمینه است؛ بنابراین پاسخ کمینه برای برنامهٔ درست برابر است با 2 .
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبرای نمونه، به پرسمان پوشش مجموعه می پردازیم. مجموعه ای مانند F و زیرمجموعه های S 0 , S 1 , . . . ⊆ U از این مجموعه داده شده اند. این پرسمان شماری از S i ها را می جوید که یکایش ( اجتماع ) این زیرمجموعه ها مجموعه F خواهد بود.
در برنامهٔ درست برای پوشش مجموعه، برای هر زیرمجموعهٔ S i متغیری بولی x i داریم.
یکایش زیرمجموعه های گزینش شده باید برابر با F باشد. به سخنی دیگر، هر e j ∈ F باید در این یکایش باشد: ∑ { i | e j ∈ S i } x j ≥ 1 . این پاوند را پاوند یکایش می نامیم.
هم چنین، پاوندِ x i ∈ { 0 , 1 } برای هر متغیر x i نشان می دهد که آیا زیرمجموعه S i در پاسخ خواهد بود یا نه. به سخنی دیگرِ، ارزش یک/صفر برای x i نشان می دهد که زیرمجموعهٔ S i در پوشش هست/نیست. این پاوند را پاوند بولی می نامیم.
پرسمان کم ترین شمار زیرمجموعه ها را می جوید: min ∑ i x i .
واهلش به برنامهٔ خطی هر پاوند بولی x i ∈ { 0 , 1 } را با پاوند 0 ≤ x i ≤ 1 جایگزین می کند. برنامهٔ خطی به دست آمده وزنی را برای هر زیرمجموعه فرضیده است؛ ولی، پاوند یکایش یکسان می ماند. در پاسخ به این برنامهٔ خطی، جمع وزن همهٔ زیرمجموعه هایی چون S i که دربردارندهٔ عضو e j ∈ F برابر با یک خواهند بود.
به این نمونه از پوشش مجموعه ای بنگرید: مجموعهٔ F = { a , b , c } و زیرمجموعه های S 1 = { a , b } , S 2 = { b , c } , S 3 = { a , c } را داریم. در برنامهٔ درست، سه متغیر x 1 , x 2 , x 3 خواهیم داشت. برای هر کدام از a , b , c ∈ F یک پاوند یکایش هست. برای نمونه، برای a پاوندِ x 1 + x 3 ≥ 1 را داریم. هم چنین، برای هر S i یک پاوند بولی 0 ≤ x i ≤ 1 داریم.
گزینش هر جفت از زیرمجموعه های S 1 , S 2 , S 3 پاسخی بهین است. به سخنی دیگر، هر یک از { S 1 , S 2 } ، { S 1 , S 3 } یا { S 2 , S 3 } یک پوشش مجموعه ای کمینه است؛ بنابراین پاسخ کمینه برای برنامهٔ درست برابر است با 2 .
