Lexicographic optimization
লেক্সিকোগ্রাফিক অপ্টিমাইজেশন হল এক ধরনের মাল্টি-অবজেক্টিভ অপ্টিমাইজেশন। সাধারণভাবে, মাল্টি-অবজেক্টিভ অপ্টিমাইজেশান দুটি বা ততোধিক উদ্দেশ্যমূলক ফাংশন সহ অপ্টিমাইজেশান সমস্যা নিয়ে কাজ করে যা একই সাথে অপ্টিমাইজ করা যায়। প্রায়শই, বিভিন্ন উদ্দেশ্যগুলি সিদ্ধান্ত গ্রহণকারীর কাছে গুরুত্বের ক্রমানুসারে স্থান দেওয়া যেতে পারে, যাতে সেই উদ্দেশ্যটি সবচেয়ে গুরুত্বপূর্ণ, উদ্দেশ্যটি পরবর্তী সবচেয়ে গুরুত্বপূর্ণ এবং আরও অনেক কিছু। লেক্সিকোগ্রাফিক অপ্টিমাইজেশান অনুমান করে যে সিদ্ধান্ত গ্রহণকারী এমনকি খুব ছোট বৃদ্ধি, এমনকি খুব বড় বৃদ্ধি ইত্যাদি পছন্দ করে। একইভাবে, সিদ্ধান্ত গ্রহণকারী এমনকি খুব সামান্য বৃদ্ধি, এমনকি খুব বড় বৃদ্ধি ইত্যাদি পছন্দ করেন। অন্য কথায়, সিদ্ধান্ত গ্রহণকারীর অভিধানগত পছন্দ রয়েছে, তাদের উদ্দেশ্যমূলক ক্রিয়াকলাপের মানগুলির একটি অভিধানগত ক্রম অনুসারে সম্ভাব্য সমাধানগুলিকে র্যাঙ্কিং করে। লেক্সিকোগ্রাফিক অপ্টিমাইজেশানকে কখনও কখনও প্রিএম্পটিভ অপ্টিমাইজেশন বলা হয়, কারণ একটি উদ্দেশ্যমূলক মানের সামান্য বৃদ্ধি কম গুরুত্বপূর্ণ উদ্দেশ্যমূলক মানের অনেক বড় বৃদ্ধিকে বাধা দেয়। উদাহরণস্বরূপ, এমন একটি সংস্থার কথা বিবেচনা করুন যা নিরাপত্তাকে সর্বোপরি রাখে। এটি তার কর্মী এবং গ্রাহকদের নিরাপত্তা সর্বাধিক করতে চায়। সর্বাধিক সম্ভাব্য নিরাপত্তা অর্জনের সাপেক্ষে, এটি সর্বাধিক মুনাফা অর্জন করতে চায়। এই সংস্থাটি অভিধানগত অপ্টিমাইজেশন সম্পাদন করে, যেখানে নিরাপত্তা নির্দেশ করে এবং মুনাফা নির্দেশ করে। আরেকটি উদাহরণ হিসাবে, প্রকল্প ব্যবস্থাপনায়, পিইআরটি নেটওয়ার্কগুলি বিশ্লেষণ করার সময়, একজন প্রায়শই গড় সমাপ্তির সময়কে হ্রাস করতে চায় এবং এই সাপেক্ষে, সমাপ্তির সময়ের বৈচিত্র্যকে হ্রাস করতে চায়। একটি অভিধানগত সর্বাধিককরণ সমস্যা প্রায়শই এইভাবে লেখা হয়ঃ সর্বাধিক করার জন্য ফাংশনগুলি কোথায়, সর্বাধিক থেকে সর্বনিম্ন গুরুত্বপূর্ণ পর্যন্ত ক্রমযুক্ত; সিদ্ধান্তের চলকগুলির ভেক্টর; এবং সম্ভাব্য সেট-এর সম্ভাব্য মানগুলির সেট। একটি অভিধানগত ন্যূনতমকরণ সমস্যা অনুরূপভাবে সংজ্ঞায়িত করা যেতে পারে। অ্যালগরিদম লেক্সিকোগ্রাফিক অপ্টিমাইজেশান সমস্যা সমাধানের জন্য বেশ কয়েকটি অ্যালগরিদম রয়েছে। সাধারণ উদ্দেশ্যগুলির জন্য ক্রমিক অ্যালগরিদম n উদ্দেশ্যগুলির সাথে একটি লেক্সিমিন অপ্টিমাইজেশান সমস্যা n একক-উদ্দেশ্যমূলক অপ্টিমাইজেশান সমস্যার একটি ক্রম ব্যবহার করে সমাধান করা যেতে পারে, নিম্নরূপঃ t = 1,., n এর জন্য নিম্নলিখিত একক-উদ্দেশ্যমূলক সমস্যার সমাধান করুনঃ যদি সমস্যাটি অসম্ভব বা সীমাহীন হয়, তবে থামুন এবং ঘোষণা করুন যে কোনও সমাধান নেই। অন্যথায়, সর্বোত্তম সমাধানের মান রাখুন এবং চালিয়ে যান। সুতরাং, প্রথম পুনরাবৃত্তিতে, আমরা সবচেয়ে গুরুত্বপূর্ণ উদ্দেশ্যটির সর্বাধিক সম্ভাব্য মান খুঁজে পাই এবং এই সর্বাধিক মানটি রাখি। দ্বিতীয় পুনরাবৃত্তিতে, আমরা দ্বিতীয়-সবচেয়ে গুরুত্বপূর্ণ উদ্দেশ্যটির সর্বাধিক সম্ভাব্য মান খুঁজে পাই, অতিরিক্ত সীমাবদ্ধতা সহ যে সবচেয়ে গুরুত্বপূর্ণ উদ্দেশ্যটিকে অবশ্যই তার সর্বোচ্চ মান রাখতে হবে; ইত্যাদি। ক্রমিক অ্যালগরিদমটি সাধারণ-এটি প্রয়োগ করা যেতে পারে যখনই আমাদের একক-উদ্দেশ্যমূলক ফাংশনের জন্য একটি সমাধানকারী থাকে। লিনিয়ার উদ্দেশ্যগুলির জন্য লেক্সিকোগ্রাফিক সিম্প্লেক্স অ্যালগরিদম লিনিয়ার লেক্সিকোগ্রাফিক অপ্টিমাইজেশন হল লেক্সিকোগ্রাফিক অপ্টিমাইজেশনের একটি বিশেষ ক্ষেত্রে যেখানে উদ্দেশ্যগুলি লিনিয়ার হয় এবং সম্ভাব্য সেটটি লিনিয়ার অসমতা দ্বারা বর্ণনা করা হয়। এটি এইভাবে লেখা যেতে পারেঃ যেখানে ভেক্টরগুলি সর্বাধিক করার জন্য রৈখিক উদ্দেশ্যগুলির প্রতিনিধিত্ব করে, সর্বাধিক থেকে সর্বনিম্ন গুরুত্বপূর্ণ পর্যন্ত ক্রমযুক্ত; সিদ্ধান্তের চলকগুলির ভেক্টর; এবং সম্ভাব্য সেটটি ম্যাট্রিক্স এবং ভেক্টর দ্বারা নির্ধারিত হয়। ইসারম্যান লিনিয়ার প্রোগ্রামিং দ্বৈততার তত্ত্বকে লেক্সিকোগ্রাফিক লিনিয়ার প্রোগ্রামগুলিতে প্রসারিত করেছিলেন এবং একটি লেক্সিকোগ্রাফিক সিম্প্লেক্স অ্যালগরিদম তৈরি করেছিলেন। ক্রমিক অ্যালগরিদমের বিপরীতে, এই সিম্প্লেক্স অ্যালগরিদম একই সাথে সমস্ত উদ্দেশ্যমূলক ফাংশন বিবেচনা করে। রৈখিক উদ্দেশ্যগুলির জন্য ওজনযুক্ত গড় শেরালি এবং সয়স্টার প্রমাণ করে যে, যে কোনও রৈখিক অভিধানগত অপ্টিমাইজেশান সমস্যার জন্য, ওজনের একটি সেট রয়েছে যাতে অভিধানগতভাবে-সর্বোত্তম সমাধানগুলির সেট নিম্নলিখিত একক-উদ্দেশ্যমূলক সমস্যার সমাধানগুলির সেটের সাথে অভিন্নঃ ওজন গণনা করার একটি উপায় ইয়াগার দ্বারা দেওয়া হয়েছে। তিনি ধরে নেন যে সমস্ত বস্তুনিষ্ঠ মানগুলি 0 এবং 1 এর মধ্যে বাস্তব সংখ্যা, এবং যে কোনও দুটি সম্ভাব্য মানের মধ্যে ক্ষুদ্রতম পার্থক্য হল কিছু ধ্রুবক d <1 (যাতে d এর চেয়ে ছোট পার্থক্যের মানগুলি সমান হিসাবে বিবেচিত হয়)। তারপর, এর ওজন প্রায় নির্ধারণ করা হয়। এটি নিশ্চিত করে যে ওজনযুক্ত যোগফল সর্বাধিক করা লেক্সিকোগ্রাফিক সর্বাধিককরণের সমতুল্য। কোকোচিওনি, পাপ্পালার্ডো এবং সের্গেইয়েভ দেখান যে, এমন একটি কম্পিউটার দেওয়া হয়েছে যা অসীমের সাথে সংখ্যাসূচক গণনা করতে পারে, এমন ওজন নির্বাচন করা সম্ভব যা অসীম (বিশেষতঃ; অসীম; অসীম-বর্গ; ইত্যাদি)। ), এবং এইভাবে অসীম সহ একক-উদ্দেশ্যমূলক রৈখিক প্রোগ্রামিং-এ রৈখিক অভিধানগত অপ্টিমাইজেশানকে হ্রাস করে। তারা অসীমের সাথে সিম্প্লেক্স অ্যালগরিদমের একটি অভিযোজন উপস্থাপন করে এবং কিছু চলমান উদাহরণ উপস্থাপন করে। বৈশিষ্ট্য (1) অনন্যতা। সাধারণভাবে, একটি অভিধানগত অপ্টিমাইজেশান সমস্যার একাধিক সর্বোত্তম সমাধান থাকতে পারে। যাইহোক, যদি এবং দুটি সর্বোত্তম সমাধান হয়, তবে তাদের মান অবশ্যই একই হতে হবে, অর্থাৎ সকলের জন্য। উপরন্তু, যদি সম্ভাব্য ক্ষেত্রটি একটি উত্তল সেট হয়, এবং উদ্দেশ্যমূলক ফাংশনগুলি কঠোরভাবে অবতল হয়, তবে সমস্যার সর্বাধিক একটি সর্বোত্তম সমাধান রয়েছে, কারণ যদি দুটি ভিন্ন সর্বোত্তম সমাধান থাকে, তবে তাদের গড় আরেকটি সম্ভাব্য সমাধান হবে যেখানে উদ্দেশ্যমূলক ফাংশনগুলি উচ্চতর মান অর্জন করে-মূল সমাধানগুলির সর্বোত্তমতার বিরোধিতা করে। (2) আংশিক যোগফল। অনুকূল করার জন্য ফাংশনের একটি ভেক্টর দেওয়া হলে, 1,., n-এর সমস্ত t-এর জন্য, সংজ্ঞায়িত করুন = সবচেয়ে গুরুত্বপূর্ণ থেকে t-তম সবচেয়ে গুরুত্বপূর্ণ পর্যন্ত সমস্ত ফাংশনের যোগফল। তারপর, মূল অভিধানগত অপ্টিমাইজেশান সমস্যাটি নিম্নলিখিতগুলির সমতুল্যঃ কিছু ক্ষেত্রে, দ্বিতীয় সমস্যাটি সমাধান করা সহজ হতে পারে। আরও দেখুন লেক্সিকোগ্রাফিক ম্যাক্স-মিন অপ্টিমাইজেশন হল লেক্সিকোগ্রাফিক অপ্টিমাইজেশনের একটি রূপ যেখানে সমস্ত উদ্দেশ্য সমানভাবে গুরুত্বপূর্ণ, এবং লক্ষ্য হল ক্ষুদ্রতম উদ্দেশ্যকে সর্বাধিক করা, তারপর দ্বিতীয়-ক্ষুদ্রতম উদ্দেশ্য ইত্যাদি। গেম তত্ত্বে, নিউক্লিওলাসকে একটি অভিধানগত-ন্যূনতম সমাধান সেট হিসাবে সংজ্ঞায়িত করা হয়। একাধিক মানদণ্ডের সিদ্ধান্ত বিশ্লেষণ অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি