به طور شهودي ، دسته هاي رياضي در برنامه نويسي مختلف مسائل برنامه نويسي رياضي بايد شامل تكنيك هاي حل مختلف باشند ، بنابراين ممكن است پيچيدگي هاي محاسباتي متفاوتي داشته باشند. در حقيقت ، اكثر مسائل بهينه سازي رياضي عموماً غيرقابل حل هستند-الگوريتم هايي براي حل مسائل بهينه سازي قبلي مانند روش نيوتن ، شيب شديد ، شاخه و محدوده و غيره ، اغلب به زمان اجراي نمايي يا مقدار بيش از حد حافظه نياز دارند. راه حل هاي بهينه جهاني را بيابيد. به عنوان يك جايگزين ، مردم به تكنيك هاي ابتكاري مانند صعود از تپه ، بازپخت شبيه سازي شده ، الگوريتم هاي ژنتيك و جستجوي محرمانه براي يك راه حل مناسب و منطقي مناسب روي مي آورند.
با اين وجود ، برخي از مسائل بهينه رياضي در برنامه نويسي سازي رياضي ، مانند برنامه نويسي خطي و بهينه سازي محدب ، مي توانند به طور مlyثر و قابل اعتماد حل شوند. بنابراين ، اين امكان وجود دارد كه بررسي كنيم كه آيا مشكل بهينه سازي اصلي را مي توان به عنوان يكي از اين مشكلات مدل يا تقريب زد. پس از اتمام مدل سازي ، بقيه بايد آسان باشند - ابزارهاي تجاري يا ابزارهاي تجاري متعددي براي حل اين مشكلات استاندارد موجود است.
در ادامه ، ما به طور مختصر تعاريف مشكل و تكنيك هاي حل برنامه نويسي خطي و مسائل بهينه سازي محدب را شرح خواهيم داد. رياضي در برنامه نويسي براي جزئيات بيشتر نظري ، لطفاً به ساير كتابهاي درسي يا يادداشت ايرانيان سايبر هاي سخنراني در اين زمينه مراجعه كنيد.
4.5.2 مساله برنامه نويسي خطي (LP)
بسياري از مشكلات بهينه سازي را مي توان با اشكال خطي مدل سازي يا تقريب زد. به طور مستقيم ، حل مسائل LP بايد ساده تر از حل مسائل بهينه سازي رياضي عمومي باشد ، زيرا آنها فقط با محدوديت هاي خطي و توابع عيني سروكار دارند. با اين حال ، چندين دهه طول كشيد تا الگوريتم زمان چند جمله اي براي مشكلات رياضي در برنامه نويسي LP ايجاد شود و چندين مشكل نظري مرتبط هنوز باز است [Smale 2000].
الگوريتم سيمپلكس ، كه توسط George Dantzig در سال 1947 توسعه يافت ، اولين روش عملي است كه براي حل مشكل LP استفاده مي شود. با در نظر گرفتن مجموعه اي از محدوديت هاي خطي n متغير ، الگوريتم سيمپلكس ابتدا يك راه حل اساسي ممكن را پيدا مي كند كه تمام محدوديت ها را برآورده مي كند. اين راه حل اساسي از نظر مفهومي يك راس (يعني يك نقطه شديد) چند ضلعي محدب است كه با محدوديت هاي خطي در ابرفضا Rn گسترش يافته است. الگوريتم سپس در امتداد لبه هاي چند وجهي در جهت يافتن مقدار بهتر تابع هدف حركت مي كند. تضمين مي شود كه در نهايت اين رياضي در برنامه نويسي روش در راه حل بهينه خاتمه مي يابد.
اگرچه الگوريتم سيمپلكس مي تواند در اكثر كاربردهاي كاربردي به طور مثر مورد استفاده قرار گيرد ، اما بدترين پيچيدگي آن همچنان نمايي است. اينكه آيا الگوريتم زمان چند جمله اي براي مشكلات LP وجود دارد ، تا اواخر دهه 1970 ، زماني كه لئونيد خاچيان روش بيضي شكل را روي اين مشكل اعمال كرد و ثابت كرد كه مي توان آن را رياضي در برنامه نويسي در زمان O (n4w) حل كرد ، ناشناخته بود. در اينجا n و w به ترتيب تعداد و عرض متغيرها هستند.
مفید ترین مسابقات اسکرچ