লিনিয়ার প্রোগ্রামিং

লিনিয়ার প্রোগ্রামিং বা রৈখিক কাম্যতমকরণ ফলিত গণিতের একটি ক্ষেত্র ও একটি শক্তিশালী ম্যাথম্যাটিকাল প্রোগ্রামিং কৌশল যেটি ব্যবহার করে কোনও জটিল সমস্যার সম্ভাব্য সেরা সমাধান নির্ণয় করা হয়, অর্থাৎ সমস্যাটির গাণিতিক মডেলে উপস্থিত বিভিন্ন চলরাশির কাম্যতম মান নির্ণয় করা হয়, যেখানে ঐ চলরাশিগুলির মধ্যে সরলরৈখিক সম্পর্ক বিদ্যমান।

এই কৌশলটিতে সমস্যাটির একটি গাণিতিক প্রতিমান (মডেল) নির্মাণ করা হয়, যেটিতে একটি লক্ষ্য অপেক্ষক (অবজেক্টিভ ফাংশন) ও বাধ্যতাগুলি সংজ্ঞায়িত করা থাকে। লক্ষ্য অপেক্ষকটি হল একটি রৈখিক সমীকরণ যেটি দ্বারা কাম্যতমকরণের জন্য প্রয়োজনীয় রাশিটিকে (অর্থাৎ যেটির সর্বোচ্চকরণ বা সর্বনিম্নকরণ করা দরকার), যেমন মুনাফা, আয় বা ব্যয়কে নির্দেশ করা হয়। বাধ্যতাগুলিকে কতগুলি রৈখিক সমীকরণ বা অসমতার একটি সংগ্রহ বা সেট দিয়ে নির্দেশ করা হয়, যেগুলি সমস্যার সীমাবদ্ধতা বা আবশ্যকীয়তাগুলিকে (যেমন সম্পদের লভ্যতা, উৎপাদনের ক্ষমতা, চাহিদা, ইত্যাদি) সংজ্ঞায়িত করে। যদি রৈখিক কাম্যতমকরণটি বাস্তবায়নযোগ্য হয়, তাহলে ঐ রৈখিক বাধ্যতাগুলি একটি বাস্তবায়নযোগ্য অঞ্চলকে সংজ্ঞায়িত করে, যে অঞ্চলটিতে অসীম সংখ্যক বাস্তবায়নযোগ্য সমাধান থাকতে পারে। জ্যামিতিকভাবে অঞ্চলটি একটি উত্তল বহুপার্শ্বিক জ্যামিতিক বস্তু (পলিটোপ) হয়ে থাকে। রৈখিক কাম্যতমকরণের লক্ষ্য হল এই গাণিতিক প্রতিমানটির উপরে কলনবিধি (অ্যালগোরিদম) ব্যবহার করে বিদ্যমান প্রাথমিক সমাধানটির পৌনঃপুনিক উন্নয়ন সাধন করে শেষ পর্যন্ত কাম্যতম সমাধানটি নির্ণয় করা, যেটির আর উন্নতিসাধন সম্ভব নয়। কাম্যতম সমাধানটি হল সিদ্ধান্ত চলরাশিগুলির সেইসব মানের সমাহার যেটি সমস্ত বাধ্যতা সন্তুষ্ট করে লক্ষ্য অপেক্ষকের মান কাম্যতম (সর্বোচ্চ বা সর্বনিম্ন) করতে পারে। জ্যামিতিকভাবে লক্ষ্য অপেক্ষকটি বাস্তবায়নযোগ্য অঞ্চলের একটি শীর্ষবিন্দুতে সর্বোচ্চ বা সর্বনিম্ন মান অর্জন করে। রৈখিক কাম্যতমকরণে সর্বাধিক ব্যবহৃত কলনবিধিটি হল সিমপ্লেক্স পদ্ধতি; এছাড়া অভ্যন্তরীণ বিন্দু পদ্ধতি ও উপবৃত্তক পদ্ধতিও ব্যবহার করা হতে পারে।

রৈখিক কাম্যতমকরণের ইংরেজি পরিভাষাটি হল "লিনিয়ার অপটিমাইজেশন" (Linear optimization), তবে চিরায়তভাবে এটিকে "লিনিয়ার প্রোগ্রামিং" (Linear programming) বলা হয়ে থাকে, যার সাথে কম্পিউটার প্রোগ্রামিংয়ের কোনও সম্পর্ক নেই। এখানে "প্রোগ্রামিং" বলতে কোনও সমস্যা সমাধানের উদ্দেশ্যে বাস্তবায়নযোগ্য (feasible) কর্মপরিকল্পনাগুলি (program of action) থেকে সেরা বা কাম্যতমটি বের করাকে বোঝানো হয়। রৈখিক কাম্যতমকরণ ব্যবহার করা হলে এই সেরা কর্মপরিকল্পনা নির্ণয়ের পদ্ধতিকে চিরায়তভাবে ইংরেজিতে "লিনিয়ার প্রোগ্রাম" (Linear program) বলে। রৈখিক কাম্যতমকরণকে অতিরিক্ত বাধ্যতা ও অরৈখিক লক্ষ্য অপেক্ষক অন্তর্ভুক্ত করার মাধ্যমে সম্প্রসারিত করা হতে পারে, এভাবে সেটি আরও উন্নত কাম্যতমকরণ কৌশল যেমন অরৈখিক কাম্যতমকরণ, পূর্ণসংখ্যা কাম্যতমকরণ, দ্বিঘাত কাম্যতমকরণ, ইত্যাদির ভিত্তি হিসেবে কাজ করতে পারে।

রৈখিক কাম্যতমকরণ সরকারি, বেসরকারি ও সামরিক খাতে সিদ্ধান্ত গ্রহণের জন্য একটি মূল্যবান হাতিয়ার। পরিক্রিয়াদি গবেষণাবিদ্যা, অর্থশাস্ত্র, প্রকৌশল ও ব্যবস্থাপনা বিজ্ঞানে এর ব্যাপক ও বহুবিধ প্রয়োগ আছে, যেখানে কৃষি, শিল্পকারখানায় উৎপাদন, পরিবহন, পণ্য স্থানান্তর বিদ্যা, অর্থসংস্থান, শক্তি, টেলিযোগাযোগ ও অন্যান্য অনেক ক্ষেত্রে সম্পদের বণ্টন, উৎপাদন পরিকল্পনা, পরিসংখ্যাপত্র ব্যবস্থাপনা, বিনিয়োগ তালিকার কাম্যতমকরণ, সরবরাহ শৃঙ্খল ব্যবস্থাপনা, প্রেরণপথ নির্ণয় (রাউটিং), সময়সূচি নির্ণয়, বরাদ্দকরণ ও অন্যান্য সিদ্ধান্ত-গ্রহণ সমস্যার কাম্যতম সমাধান বের করা হয়। এভাবে আধুনিক সমাজে সীমিত সম্পদ ও অর্থের অপচয় ব্যাপকভাবে হ্রাস করে সেগুলির সবচেয়ে দক্ষ ব্যবহার করে বিভিন্ন উদ্দীষ্ট লক্ষ্যপূরণ করে কোনও প্রতিষ্ঠান, অর্থনীতি, শিল্পকারখানা, যুদ্ধ, ইত্যাদি পরিচালনা করা যায়।

তথ্যসূত্র

রৈখিক কাম্যতমকরণ
উত্তল কাম্যতমকরণ
জ্যামিতিক কলনবিধি
পি-সম্পূর্ণ সমস্যা