- হাঙ্গেরিয়ান পদ্ধতি কী?
- পদক্ষেপ 1: প্রতিটি সারির মিনিমা বিয়োগ করুন
- পদক্ষেপ 2: প্রতিটি কলাম থেকে সর্বনিম্ন বিয়োগ করুন
- পদক্ষেপ 3: সর্বনিম্ন সংখ্যক লাইনের সাথে সমস্ত শূন্যকে কভার করুন
- পদক্ষেপ 4: অতিরিক্ত শূন্য তৈরি করুন
- অনুকূল বরাদ্দ
- উদাহরণ
- পদক্ষেপ 1: প্রতিটি সারির মিনিমা বিয়োগ করুন
- পদক্ষেপ 2: প্রতিটি কলাম থেকে সর্বনিম্ন বিয়োগ করুন
- পদক্ষেপ 3: সর্বনিম্ন সংখ্যক লাইনের সাথে সমস্ত শূন্যকে কভার করুন
- পদক্ষেপ 4: অতিরিক্ত শূন্য তৈরি করুন
- পদক্ষেপ 3 (পুনরাবৃত্তি)
- অনুকূল বরাদ্দ
- তথ্যসূত্র
হাঙ্গেরীয় পদ্ধতি একটি অ্যালগরিদম যে বরাদ্দ সমস্যার ব্যবহার করা হয় যখন আপনি খরচ কমানোর জন্য চাই। অর্থাত্, এটি ন্যূনতম ব্যয়ের ভিত্তিতে বিভিন্ন ক্রিয়াকলাপে একাধিক লোককে নিয়োগ দিয়ে সর্বনিম্ন ব্যয় সন্ধান করতে ব্যবহৃত হয়। প্রতিটি ক্রিয়াকলাপ অবশ্যই আলাদা ব্যক্তির কাছে বরাদ্দ করা উচিত।
একটি বরাদ্দ সমস্যা হ'ল এক বিশেষ ধরণের লিনিয়ার প্রোগ্রামিং সমস্যা, যেখানে একাধিক লোকের দ্বারা বেশ কয়েকটি কাজ শেষ করার জন্য ব্যয় বা সময়কে হ্রাস করা লক্ষ্য।
সূত্র: pixabay.com
বরাদ্দের সমস্যার একটি গুরুত্বপূর্ণ বৈশিষ্ট্য হ'ল মেশিনে (বা প্রকল্প) কেবলমাত্র একটি কাজ (বা কর্মী) নির্ধারিত হয়।
এই পদ্ধতিটি হাঙ্গেরীয় গণিতবিদ ডি কোনিগ দ্বারা বিকাশ করা হয়েছিল। এই কারণে, এটি নিয়োগের সমস্যার জন্য হাঙ্গেরীয় পদ্ধতি হিসাবে পরিচিত। এটি কুহান-মুনক্রেস বরাদ্দ অ্যালগরিদম হিসাবেও পরিচিত।
যে কোনও বরাদ্দের সমস্যাটি সহজেই এই পদ্ধতিটি প্রয়োগ করে সমাধান করা যেতে পারে যা দুটি পর্যায় নিয়ে গঠিত:
- প্রথম পর্যায়ে সারি হ্রাস এবং কলাম হ্রাস সম্পন্ন করা হয়।
- দ্বিতীয় পর্যায়ে সমাধানটি পুনরাবৃত্তির ভিত্তিতে অনুকূলিত করা হয়।
হাঙ্গেরিয়ান পদ্ধতি কী?
হাঙ্গেরীয় পদ্ধতিতে চারটি ধাপ রয়েছে। প্রথম দুটি পদক্ষেপ কেবল একবার কার্যকর করা হয়, যখন 3 এবং 4 ধাপগুলি সর্বোত্তম বরাদ্দ না পাওয়া পর্যন্ত পুনরাবৃত্তি করা হয়।
অর্ডার এন বাই এন এর বর্গক্ষেত্রের ম্যাট্রিক্সকে ইনপুট ডেটা হিসাবে বিবেচনা করা হয়, এতে কেবল অ-নেতিবাচক উপাদান থাকতে হবে।
প্রদত্ত সমস্যার জন্য, যদি ম্যাট্রিক্সের সারিগুলির সংখ্যা কলামগুলির সংখ্যার সমান না হয় তবে কেসটির উপর নির্ভর করে একটি ডামি সারি বা একটি ডামি কলাম যুক্ত করতে হবে। এই ডামি সেলগুলির জন্য বরাদ্দ ব্যয় সর্বদা শূন্য হিসাবে বরাদ্দ করা হয়।
পদক্ষেপ 1: প্রতিটি সারির মিনিমা বিয়োগ করুন
অ্যারের প্রতিটি সারির জন্য, সর্বনিম্ন মান সহ উপাদানটি সেই সারির প্রতিটি উপাদান থেকে নির্বাচিত এবং বিয়োগ করা হয়।
পদক্ষেপ 2: প্রতিটি কলাম থেকে সর্বনিম্ন বিয়োগ করুন
একইভাবে, সর্বনিম্ন মানযুক্ত আইটেমটি প্রতিটি কলামের জন্য নির্বাচিত হয় এবং সেই কলামের প্রতিটি আইটেম থেকে বিয়োগ করা হয়।
পদক্ষেপ 3: সর্বনিম্ন সংখ্যক লাইনের সাথে সমস্ত শূন্যকে কভার করুন
পদক্ষেপ 2 এর ফলে ম্যাট্রিক্সের সমস্ত জিরো সারি বা কলাম দ্বারা ন্যূনতম অনুভূমিক এবং উল্লম্ব লাইন ব্যবহার করে আবরণ করা আবশ্যক।
যদি সমস্ত শূন্যগুলি কভার করার জন্য মোট এন লাইনগুলির প্রয়োজন হয়, যেখানে n ম্যাট্রিক্সের n n এর n এর আকারের সমান হয় তবে জিরোগুলির মধ্যে একটি অনুকূল বরাদ্দ পাওয়া যাবে এবং তাই অ্যালগরিদম বন্ধ হয়ে যায়।
অন্যথায়, অ্যারের সমস্ত জিরোগুলি কভার করার জন্য যদি কম কম লাইনের প্রয়োজন হয়, তবে পদক্ষেপ 4 এ এগিয়ে যান।
পদক্ষেপ 4: অতিরিক্ত শূন্য তৈরি করুন
ম্যাট্রিক্সের ক্ষুদ্রতম উপাদান (কে কে বলা হয়) যা তৃতীয় ধাপে তৈরি লাইনগুলির একটিতে আচ্ছাদিত নয় নির্বাচিত হয়।
কে এর মান লাইন দ্বারা আচ্ছাদিত নয় এমন সমস্ত উপাদান থেকে বিয়োগ করা হয়। পরবর্তীকালে, কা এর মান দুটি উপাদানের ছেদ দ্বারা আচ্ছাদিত সমস্ত উপাদানগুলিতে যুক্ত করা হয়।
একক লাইন দ্বারা আচ্ছাদিত আইটেমগুলি যেমন রয়েছে তেমনই রেখে দেওয়া হয়েছে। এই পদক্ষেপটি সম্পাদন করার পরে, আপনি পদক্ষেপ 3 এ ফিরে যান।
অনুকূল বরাদ্দ
পদক্ষেপ 3 এ অ্যালগরিদম বন্ধ হওয়ার পরে, শূন্যগুলির একটি সেট এমনভাবে চয়ন করা হয় যাতে প্রতিটি সারি এবং প্রতিটি কলামে কেবল একটি শূন্য নির্বাচিত থাকে।
যদি এই নির্বাচন প্রক্রিয়াটিতে একটি সারি বা কলামে একক শূন্য না থাকে, তবে সেই শূন্যগুলির মধ্যে একটি বেছে নেওয়া হবে। সেই কলাম বা সারিতে থাকা শূন্যগুলি অপসারণ করা হবে, অন্যান্য অ্যাসাইনমেন্টগুলির জন্য একই পুনরাবৃত্তি করে।
যদি কোনও একক শূন্য অ্যাসাইনমেন্ট না থাকে তবে একাধিক সমাধান রয়েছে। তবে বিভিন্ন অ্যাসাইনমেন্টের জন্য ব্যয় একই থাকবে।
যে কোনও ডামি সারি বা কলাম যুক্ত করা হয়েছে তা সরানো হবে। এই চূড়ান্ত ম্যাট্রিক্সে নির্বাচিত শূন্যগুলি মূল ম্যাট্রিক্সে প্রয়োজনীয় আদর্শ অ্যাসাইনমেন্টের সাথে মিলে যায়।
উদাহরণ
আসুন এমন একটি সংস্থা বিবেচনা করুন যেখানে চারটি ক্রিয়াকলাপ রয়েছে (এ 1, এ 2, এ 3, এ 4) যা অবশ্যই চার কর্মী দ্বারা পরিচালিত হবে (টি 1, টি 2, টি 3, টি 4)। প্রতিটি কর্মীকে একটি ক্রিয়াকলাপ বরাদ্দ করতে হবে।
নিম্নলিখিত ম্যাট্রিক্স একটি নির্দিষ্ট ক্রিয়াকলাপে নির্দিষ্ট কর্মী নির্ধারণের ব্যয় দেখায়। উদ্দেশ্য এই চারটি ক্রিয়াকলাপ নিয়ে গঠিত কাজের মোট ব্যয় হ্রাস করা।
পদক্ষেপ 1: প্রতিটি সারির মিনিমা বিয়োগ করুন
আপনি সেই সারির অন্যান্য উপাদান থেকে প্রতিটি সারিতে ন্যূনতম মান দিয়ে উপাদানটি বিয়োগ করে শুরু করবেন। উদাহরণস্বরূপ, প্রথম সারিতে ক্ষুদ্রতম উপাদান 69 Therefore সুতরাং, 69 প্রথম সারির প্রতিটি উপাদান থেকে বিয়োগ করা হয়। ফলাফল ম্যাট্রিক্স হয়:
পদক্ষেপ 2: প্রতিটি কলাম থেকে সর্বনিম্ন বিয়োগ করুন
একইভাবে, প্রতিটি কলামের সর্বনিম্ন মান সহ উপাদানটি নিম্নলিখিত ম্যাট্রিক্সটি প্রাপ্ত করে column কলামের অন্যান্য উপাদানগুলি থেকে বিয়োগ করা হয়:
পদক্ষেপ 3: সর্বনিম্ন সংখ্যক লাইনের সাথে সমস্ত শূন্যকে কভার করুন
এখন আমরা ম্যাট্রিক্সের সমস্ত শূন্যগুলি আবরণ করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যা (অনুভূমিক বা উল্লম্ব) নির্ধারণ করব। সমস্ত শূন্যগুলি 3 টি লাইন ব্যবহার করে আচ্ছাদন করা যেতে পারে:
যেহেতু প্রয়োজনীয় রেখাগুলির সংখ্যা তিনটি এবং এটি ম্যাট্রিক্সের আকার (এন = 4) এর চেয়ে কম, সুতরাং আমরা 4 ধাপে চালিয়ে যাচ্ছি।
পদক্ষেপ 4: অতিরিক্ত শূন্য তৈরি করুন
রেখাগুলি দ্বারা আচ্ছন্ন না হওয়া সবচেয়ে ছোট উপাদানটি নির্বাচিত হয়, যার মান 6.. এই মানটি আচ্ছাদিত নয় এমন সমস্ত উপাদান থেকে বিয়োগ করা হয় এবং এই একই মানটি দুটি রেখার ছেদ দ্বারা আচ্ছাদিত সমস্ত উপাদানগুলিতে যুক্ত হয়। এটি নিম্নলিখিত ম্যাট্রিক্সের ফলাফল:
হাঙ্গেরীয় পদ্ধতিতে ইঙ্গিত হিসাবে, তৃতীয় পদক্ষেপটি আবার সম্পাদন করা উচিত।
পদক্ষেপ 3 (পুনরাবৃত্তি)
আবার ম্যাট্রিক্সের সমস্ত শূন্যগুলি আবরণ করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যার সংখ্যা নির্ধারিত হয়। এবার চারটি লাইন প্রয়োজন:
যেহেতু প্রয়োজনীয় লাইনের সংখ্যা 4, ম্যাট্রিক্সের আকার (n = 4) এর সমান, আমাদের ম্যাট্রিক্সের শূন্যগুলির মধ্যে একটি অনুকূল বরাদ্দ রয়েছে। অতএব, অ্যালগরিদম বন্ধ হয়ে যায়।
অনুকূল বরাদ্দ
পদ্ধতিটি ইঙ্গিত হিসাবে, নিম্নলিখিত শূন্যগুলি থেকে তৈরি নির্বাচনটি একটি অনুকূল কার্যভারের সাথে মিলে যায়:
শূন্যগুলির এই নির্বাচনটি মূল ব্যয় ম্যাট্রিক্সের নিম্নলিখিত অনুকূল বরাদ্দের সাথে মিলে যায়:
অতএব, কর্মী 1 অবশ্যই কার্যকলাপ 3, কর্মী 2, ক্রিয়াকলাপ 2, কর্মী 3, ক্রিয়াকলাপ 1, এবং কর্মী 4 অবশ্যই ক্রিয়াকলাপ সম্পাদন করতে হবে 4. এই অনুকূল নিয়োগের মোট ব্যয় 69 + 37 + 11 + 23 = 140।
তথ্যসূত্র
- হাঙ্গেরিয়ান অ্যালগরিদম (2019)। হাঙ্গেরিয়ান অ্যালগরিদম। থেকে নেওয়া: hungarianalgorithm.com।
- অধ্যয়ন (2019)। অ্যাসাইনমেন্ট সমস্যার সমাধান করার জন্য হাঙ্গেরীয় অ্যালগরিদম ব্যবহার করে। থেকে নেওয়া: অধ্যয়ন.কম।
- উইজডম জবস (2018)। নিয়োগের সমস্যা সমাধানের হাঙ্গেরীয় পদ্ধতি - পরিচালনার জন্য পরিমাণগত কৌশল। থেকে নেওয়া: জ্ঞানিজবস.কম।
- গিক্সের জন্য গিগস (2019)। নিয়োগের সমস্যার জন্য হাঙ্গেরীয় অ্যালগরিদম। থেকে নেওয়া: geeksforgeeks.org।
- কার্লেইগ মুর, নাথান ল্যান্ডম্যান (2019)। হাঙ্গেরিয়ান সর্বাধিক ম্যাচিং অ্যালগরিদম। উজ্জ্বল। থেকে নেওয়া: brilliant.org।