شديد) چند ضلعي محدب رياضي در برنامه نويسي است كه با محدوديت هاي خطي در ابرفضا Rn گسترش يافته است. الگوريتم سپس در امتداد لبه هاي چند وجهي در جهت يافتن مقدار بهتر تابع هدف حركت مي كند. تضمين مي شود كه در نهايت اين روش در راه حل بهينه خاتمه مي يابد.
اگرچه الگوريتم سيمپلكس مي تواند رياضي در برنامه نويسي در اكثر كاربردهاي كاربردي به طور مثر مورد استفاده قرار گيرد ، اما بدترين پيچيدگي آن همچنان نمايي است. اينكه آيا الگوريتم زمان چند جمله اي براي مشكلات LP وجود دارد ، تا اواخر دهه 1970 ، زماني كه لئونيد خاچيان روش بيضي شكل را روي اين مشكل اعمال رياضي در برنامه نويسي كرد و ثابت كرد كه مي توان آن را در زمان O (n4w) حل كرد ، ناشناخته بود. در اينجا n و w به ترتيب تعداد و عرض متغيرها هستند.
روش خاچيان اهميت نظري داشت ، زيرا اولين الگوريتم زمان چند جمله اي بود كه مي تواند براي مشكلات LP به كار رود. با اين حال ، در اكثر موارد عملي بهتر از الگوريتم سيمپلكس عمل نكرد. بسياري از محققاني كه خاچيان را دنبال كردند بر بهبود عملكرد متوسط مورد و همچنين پيچيدگي بدترين حالت محاسباتي ايرانيان سايبر تمركز كردند. قابل توجه ترين پيشرفت ها شامل روش نقطه داخلي نارندرا كارماركار و بسياري ديگر از الگوريتم هاي رياضي در برنامه نويسي سيمپلكس تجديد نظر شده [كارماركار 1984] بود.
4.5.3 مشكل برنامه نويسي خطي صحيح (ILP)
بسياري از برنامه هاي كاربردي برنامه نويسي خطي فقط به متغيرهايي در حوزه انتگرال توجه دارند. به عنوان مثال ، مقادير سيگنال در يك مدار ديجيتال تحت يك سيستم شماره مدولار است. بنابراين ، به احتمال زياد مشكلات بهينه رياضي در برنامه نويسي سازي تعريف شده در رابطه با سيگنالها در يك مدار را مي توان به عنوان مشكلات ILP مدل كرد. از سوي ديگر ، مشكلاتي كه نياز به برشمردن موارد احتمالي دارند يا مربوط به زمان بندي برخي رويدادها هستند ، اغلب به عنوان ILP توصيف مي شوند.
مشكل ILP به طور كلي بسيار مشكل تر از LP است. مي توان نشان داد كه ILP در واقع يكي از مشكلات سخت NP است. اگرچه اثبات رسمي پيچيدگي محاسباتي مسئله ILP از حوصله اين كتاب خارج است ، ما از مثال زير براي نشان دادن روش و توضيح مشكل در حل مسئله ILP استفاده خواهيم كرد.
مشكل ILP در شكل 4.28 به حداكثر رياضي در برنامه نويسي رساندن يك تابع هدف f با توجه به چهار محدوديت خطي {g1 ، g2 ، g3 ، g4} است. از آنجا كه مسئله فقط شامل دو متغير x و y است ، مي توان آن را در صفحه دو بعدي نشان داد ، جايي كه هر محدوديت يك خط مستقيم است ، چهار محدوديت يك منطقه بسته C را تشكيل مي دهند و راه حل هاي ممكن شبكه يا انتگرال است. نقاط درون اين منطقه تابع هدف f كه به صورت يك خط راست در سمت راست ناحيه C نشان داده شده است ، با توجه به مقادير مختلف k به طور موازي حركت مي كند. به طور شهودي ، براي به دست آوردن حداكثر مقدار f ، مي توانيم خط f = k را از جايي كه در شكل قرار دارد منتقل كنيم تا منطقه C را بر روي يك نقطه شبكه قطع كند.
در شكل 4.30 ، برش هاي c1 و c2 نابرابري رياضي در برنامه نويسي هاي معتبري گفته مي شود ، زيرا همه نقاط امكان پذير (يعني نقاط انتگرالي درون خط تيره C) پس از افزودن محدوديت هاي جديد هنوز معتبر هستند. از طرف ديگر ، برش c3 يك نابرابري معتبر نيست زيرا يك نقطه امكان پذير p1 بعداً نامعتبر مي شود.