Linear programming — রৈখিক প্রোগ্রামিং

রৈখিক প্রোগ্রামিং — এটি গাণিতিক প্রোগ্রামিংয়ের একটি শাখা এবং অপারেশন রিসার্চের একটি বহুল ব্যবহৃত পদ্ধতি, যা রৈখিক সীমাবদ্ধতার উপস্থিতিতে একটি রৈখিক ফাংশনের চরম মান (সর্বোচ্চ বা সর্বনিম্ন) অনুসন্ধানের তত্ত্ব ও পদ্ধতি উন্নয়নে নিবেদিত।

রৈখিক প্রোগ্রামিং অর্থনীতি, ব্যবস্থাপনা, পরিকল্পনা, লজিস্টিক্স এবং অন্যান্য ক্ষেত্রে অপ্টিমাইজেশন সমস্যা সমাধানের জন্য সবচেয়ে শক্তিশালী ও বহুল প্রয়োগকৃত হাতিয়ারগুলির মধ্যে একটি।

বিষয় ও উদ্দেশ্য

রৈখিক প্রোগ্রামিংয়ের মূল সমস্যা — কোনো লক্ষ্য অর্জনের জন্য সীমিত সম্পদের সর্বোত্তম বণ্টনের উপায় খুঁজে বের করা, যখন লক্ষ্যটি এবং সম্পদ ব্যবহারের উপর আরোপিত সীমাবদ্ধতাগুলি উভয়ই রৈখিক নির্ভরতা দ্বারা প্রকাশ করা যায়।

• রৈখিক প্রোগ্রামিং নিম্নলিখিত ব্যবহারিক সমস্যাগুলি সমাধান করতে সক্ষম করে:
• উৎপাদনের সর্বোত্তম পরিকল্পনা।
• পরিবহন প্রবাহের অপ্টিমাইজেশন (পরিবহন সমস্যা)।
• বিনিয়োগের সর্বোত্তম বণ্টন।
• উপকরণের সর্বোত্তম কর্তন। নিয়োগ সমস্যা।

রৈখিক প্রোগ্রামিং সমস্যার গাণিতিক প্রণয়ন

রৈখিক প্রোগ্রামিংয়ের আদর্শ সমস্যাটি নিম্নরূপে সংজ্ঞায়িত করা হয়:

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

গাণিতিকভাবে এর অর্থ হলো রৈখিক ফাংশন এবং রৈখিক সমীকরণ/অসমতার তন্ত্রের সাথে কাজ করা।

রৈখিক প্রোগ্রামিংয়ের মূল ধারণাসমূহ

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

রৈখিক প্রোগ্রামিং সমস্যা সমাধানের পদ্ধতিসমূহ

রৈখিক প্রোগ্রামিং সমস্যা সমাধানের জন্য বেশ কিছু মূল পদ্ধতি রয়েছে:

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

রৈখিক প্রোগ্রামিংয়ে দ্বৈততা

রৈখিক প্রোগ্রামিংয়ের প্রতিটি সমস্যার (যাকে প্রাথমিক বলা হয়) সাথে আরেকটি রৈখিক প্রোগ্রামিং সমস্যা সংযুক্ত করা যায়, যাকে দ্বৈত সমস্যা বলা হয়। প্রাথমিক ও দ্বৈত সমস্যা একে অপরের সাথে ঘনিষ্ঠভাবে সম্পর্কিত:

একটি সমস্যার সমাধান অপর সমস্যার সমাধান সম্পর্কে তথ্য প্রদান করে। উভয় সমস্যায় লক্ষ্য ফাংশনের সর্বোত্তম মান একই হয় (যদি সেগুলি বিদ্যমান থাকে)। দ্বৈত সমস্যার চলকগুলির একটি গুরুত্বপূর্ণ অর্থনৈতিক ব্যাখ্যা রয়েছে — এগুলি সম্পদের ছায়া মূল্য (বা দ্বৈত মূল্যায়ন) এর সাথে সম্পর্কিত, যা দেখায় যে সংশ্লিষ্ট সম্পদের সীমাবদ্ধতায় সামান্য পরিবর্তন হলে প্রাথমিক সমস্যার লক্ষ্য ফাংশনের সর্বোত্তম মান কতটা পরিবর্তিত হবে।

রৈখিক প্রোগ্রামিংয়ের প্রয়োগ

রৈখিক প্রোগ্রামিং নিম্নলিখিত ক্ষেত্রে ব্যাপকভাবে ব্যবহৃত হয়:

• অর্থনীতি ও ব্যবসায় (উৎপাদন পরিকল্পনা, লজিস্টিক্স, অর্থায়ন, বিপণন)।
• শিল্পে (প্রযুক্তিগত প্রক্রিয়ার অপ্টিমাইজেশন, মজুত ব্যবস্থাপনা, উপকরণ কর্তন)।
• পরিবহনে (রুট ও সময়সূচির অপ্টিমাইজেশন)। কৃষিতে (চাষের জমি ও পশু খাদ্যের অনুপাতের অপ্টিমাইজেশন)।
• জ্বালানি খাতে (উৎপাদন সক্ষমতার ব্যবহারের অপ্টিমাইজেশন)।

সাহিত্য

• ড্যান্টজিগ জি. রৈখিক প্রোগ্রামিং, এর প্রয়োগ ও সাধারণীকরণ। — মস্কো: প্রগ্রেস, ১৯৬৬।
• ইউদিন ডি. বি., গোলশতেইন ই. জি. রৈখিক প্রোগ্রামিং (তত্ত্ব, পদ্ধতি ও প্রয়োগ)। — মস্কো: নাউকা, ১৯৬৯।
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

আরও দেখুন

• অপারেশন রিসার্চ
• অপ্টিমাইজেশন
• লক্ষ্য ফাংশন
• সীমাবদ্ধতা
• সম্ভাব্য সমাধানের এলাকা
• সর্বোত্তম সমাধান