Lexicographic optimization
لیکسیگرافک آپٹیمائزیشن ایک قسم کی ملٹی آبجیکٹیو آپٹیمائزیشن ہے۔ عام طور پر، ملٹی آبجیکٹیو آپٹیمائزیشن دو یا زیادہ آبجیکٹیو فنکشنز کے ساتھ آپٹیمائزیشن کے مسائل سے متعلق ہے جنہیں بیک وقت بہتر بنایا جانا چاہیے۔ اکثر، مختلف مقاصد کی درجہ بندی فیصلہ ساز کے لیے اہمیت کے لحاظ سے کی جا سکتی ہے، تاکہ وہ مقصد سب سے اہم ہو، مقصد اگلا سب سے اہم ہو، اور اسی طرح۔ لیکسیگرافک آپٹیمائزیشن یہ فرض کرتی ہے کہ فیصلہ ساز بہت کم اضافے، یہاں تک کہ بہت بڑے اضافے وغیرہ کو بھی ترجیح دیتا ہے۔ اسی طرح فیصلہ ساز بھی بہت کم اضافے کو ترجیح دیتا ہے، یہاں تک کہ بہت زیادہ اضافے وغیرہ کو بھی۔ دوسرے لفظوں میں، فیصلہ ساز کی لغت کی ترجیحات ہوتی ہیں، جو ممکنہ حل کو ان کے معروضی فعل کی اقدار کی لغت کی ترتیب کے مطابق درجہ بندی کرتی ہیں۔ لیکسیگرافک آپٹیمائزیشن کو بعض اوقات پری ایمپٹو آپٹیمائزیشن کہا جاتا ہے، کیونکہ ایک معروضی قدر میں ایک چھوٹا سا اضافہ کم اہم معروضی اقدار میں بہت زیادہ اضافے کو روکتا ہے۔ مثال کے طور پر، ایک ایسی فرم پر غور کریں جو حفاظت کو سب سے اوپر رکھتی ہے۔ یہ اپنے کارکنوں اور صارفین کی حفاظت کو زیادہ سے زیادہ کرنا چاہتا ہے۔ زیادہ سے زیادہ ممکنہ تحفظ حاصل کرنے کے تابع، یہ زیادہ سے زیادہ منافع حاصل کرنا چاہتا ہے۔ یہ فرم لیکسیگرافک آپٹیمائزیشن انجام دیتی ہے، جہاں حفاظت کی نشاندہی ہوتی ہے اور منافع کی نشاندہی ہوتی ہے۔ ایک اور مثال کے طور پر، پروجیکٹ مینجمنٹ میں، پی ای آر ٹی نیٹ ورکس کا تجزیہ کرتے وقت، کوئی بھی اکثر اوسط تکمیل کے وقت کو کم کرنا چاہتا ہے، اور اس کے تابع، تکمیل کے وقت کے تغیر کو کم کرنا چاہتا ہے۔ نوٹیشن ایک لیکسیگرافک میکسمائزیشن کا مسئلہ اکثر اس طرح لکھا جاتا ہے: زیادہ سے زیادہ کرنے کے افعال کہاں ہیں، سب سے زیادہ سے کم سے کم اہم تک ترتیب دیا گیا ہے ؛ فیصلہ متغیرات کا ویکٹر ہے ؛ اور قابل عمل سیٹ ہے-کی ممکنہ اقدار کا مجموعہ۔ لیکسیکگرافک کم سے کم کرنے کے مسئلے کی تعریف اسی طرح کی جا سکتی ہے۔ الگورتھم لیکسیگرافک آپٹیمائزیشن کے مسائل کو حل کرنے کے لیے کئی الگورتھم ہیں۔ عام مقاصد کے لیے ترتیب وار الگورتھم n مقاصد کے ساتھ ایک لیکسیمین اصلاح کا مسئلہ n واحد مقصد اصلاح کے مسائل کی ترتیب کا استعمال کرتے ہوئے حل کیا جا سکتا ہے، جیسا کہ مندرجہ ذیل ہے: t = 1 کے لیے، n مندرجہ ذیل واحد مقصد کے مسئلے کو حل کرتا ہے: اگر مسئلہ ناقابل عمل یا غیر محدود ہے، تو رک جائیں اور اعلان کریں کہ کوئی حل نہیں ہے۔ بصورت دیگر، بہترین حل کی قدر ڈالیں اور جاری رکھیں۔ تو، پہلی تکرار میں، ہم سب سے اہم مقصد کی زیادہ سے زیادہ قابل عمل قیمت تلاش کرتے ہیں، اور اس زیادہ سے زیادہ قیمت کو اس میں ڈالتے ہیں۔ دوسری تکرار میں، ہمیں دوسرے سب سے اہم مقصد کی زیادہ سے زیادہ قابل عمل قیمت ملتی ہے، اس اضافی رکاوٹ کے ساتھ کہ سب سے اہم مقصد کو اپنی زیادہ سے زیادہ قیمت برقرار رکھنی چاہیے۔ ترتیب وار الگورتھم عام ہے-جب بھی ہمارے پاس واحد مقصد کے افعال کے لیے حل کنندہ ہو تو اس کا اطلاق کیا جا سکتا ہے۔ لکیری مقاصد کے لیے لیکسیگرافک سمپلیکس الگورتھم لکیری لیکسیگرافک آپٹیمائزیشن کا ایک خاص معاملہ ہے جس میں مقاصد لکیری ہوتے ہیں، اور قابل عمل سیٹ کو لکیری عدم مساوات کے ذریعے بیان کیا جاتا ہے۔ اسے اس طرح لکھا جا سکتا ہے: جہاں ویکٹر زیادہ سے زیادہ کرنے کے لیے لکیری مقاصد کی نمائندگی کرتے ہیں، سب سے زیادہ سے کم اہم تک ترتیب دیے گئے ہیں ؛ فیصلہ متغیرات کا ویکٹر ہے ؛ اور قابل عمل سیٹ کا تعین میٹرکس اور ویکٹر کے ذریعے کیا جاتا ہے۔ آئسرمین نے لکیری پروگرامنگ ڈوئلٹی کے نظریہ کو لیکسیگرافک لکیری پروگراموں تک بڑھایا، اور ایک لیکسیگرافک سمپلیکس الگورتھم تیار کیا۔ ترتیب وار الگورتھم کے برعکس، یہ سمپلیکس الگورتھم بیک وقت تمام معروضی افعال پر غور کرتا ہے۔ لکیری مقاصد کے لیے وزنی اوسط شیرالی اور سوئسٹر یہ ثابت کرتے ہیں کہ، کسی بھی لکیری لیکسیگرافک اصلاح کے مسئلے کے لیے، وزن کا ایک مجموعہ موجود ہے جس میں لیکسیگرافک طور پر بہترین حل کا مجموعہ مندرجہ ذیل واحد مقصد والے مسئلے کے حل کے سیٹ سے ملتا جلتا ہے: وزن کا حساب لگانے کا ایک طریقہ یاگر نے دیا ہے۔ وہ فرض کرتا ہے کہ تمام معروضی اقدار 0 اور 1 کے درمیان حقیقی اعداد ہیں، اور کسی بھی دو ممکنہ اقدار کے درمیان سب سے چھوٹا فرق کچھ مستقل d <1 ہے (تاکہ d سے چھوٹے فرق والی اقدار کو برابر سمجھا جائے)۔ پھر، کا وزن تقریبا مقرر کیا جاتا ہے۔ یہ اس بات کی ضمانت دیتا ہے کہ وزن کی رقم کو زیادہ سے زیادہ کرنا لیکسیگرافک کو زیادہ سے زیادہ کرنے کے برابر ہے۔ کوکوسیونی، پاپلارڈو اور سرگئیف ظاہر کرتے ہیں کہ، ایک ایسے کمپیوٹر کو دیکھتے ہوئے جو لامحدود کے ساتھ عددی حساب کتاب کر سکتا ہے، ایسے وزن کا انتخاب کرنا ممکن ہے جو لامحدود ہوں (خاص طور پر: ؛ لامحدود ہے ؛ لامحدود مربع ہے ؛ وغیرہ۔ )، اور اس طرح لامحدود کے ساتھ واحد مقصد لکیری پروگرامنگ کے لیے لکیری لیکسیگرافک آپٹیمائزیشن کو کم کرتا ہے۔ وہ لامحدود کے لیے سمپلیکس الگورتھم کی موافقت پیش کرتے ہیں، اور کچھ چلتی ہوئی مثالیں پیش کرتے ہیں۔ خصوصیات (1) انفرادیت۔ عام طور پر، ایک لغت کی اصلاح کے مسئلے کا ایک سے زیادہ بہترین حل ہو سکتا ہے۔ تاہم، اگر اور دو بہترین حل ہیں، تو ان کی قیمت یکساں ہونی چاہیے، یعنی سب کے لیے۔ مزید برآں، اگر قابل عمل ڈومین ایک کنویکس سیٹ ہے، اور معروضی افعال سختی سے کنکریٹ ہیں، تو اس مسئلے کا زیادہ سے زیادہ ایک بہترین حل ہوتا ہے، کیونکہ اگر دو مختلف بہترین حل ہوتے، تو ان کا اوسط ایک اور قابل عمل حل ہوتا جس میں معروضی افعال اعلی قدر حاصل کرتے ہیں-جو اصل حل کی اصلاح سے متصادم ہوتا ہے۔ (2) جزوی رقم۔ افعال کے ویکٹر کو بہتر بنانے کے لیے، 1،.، n میں تمام t کے لیے، سب سے اہم سے لے کر t-th سب سے اہم تک تمام افعال کا مجموعہ بیان کریں۔ پھر، اصل لیکسیگرافک آپٹیمائزیشن کا مسئلہ درج ذیل کے مساوی ہے: بعض صورتوں میں، دوسرا مسئلہ حل کرنا آسان ہو سکتا ہے۔ یہ بھی دیکھیں کہ لیکسیکگرافک میکس-من آپٹیمائزیشن لیکسیکگرافک آپٹیمائزیشن کی ایک قسم ہے جس میں تمام مقاصد یکساں طور پر اہم ہیں، اور مقصد سب سے چھوٹے مقصد کو زیادہ سے زیادہ کرنا ہے، پھر دوسرا سب سے چھوٹا مقصد، اور اسی طرح۔ گیم تھیوری میں، نیوکلیولس کو لغت کے لحاظ سے کم سے کم حل سیٹ کے طور پر بیان کیا گیا ہے۔ حوالہ جات متعدد معیار کے فیصلے کا تجزیہ آپٹیمائزیشن الگورتھم اور طریقے