এই পেপারটি অসম্পূর্ণ জোড়া তুলনা ম্যাট্রিক্স অধ্যয়ন করে এবং সঠিকভাবে নির্ধারণ করে যে কখন সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ বিদ্যমান থাকে, এবং যদি না থাকে তবে কখন আনুমানিক সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ বিদ্যমান থাকে। লেখকরা সর্বোচ্চ ৩-চক্র গুণফল ব্যবহার করেন অসামঞ্জস্য পরিমাপ হিসাবে এবং প্রমাণ করেন যে যখন নির্দিষ্ট প্রবেশাধিকারের গ্রাফ একটি কর্ডাল গ্রাফ হয়, তখন সর্বদা এই পরিমাপ বৃদ্ধি না করে সম্পূর্ণকরণ খুঁজে পাওয়া সম্ভব। পেপারটি এই ধরনের সম্পূর্ণকরণ উৎপাদনের পদ্ধতিবিদ্যা বিকাশ করে, যা অল্প সংখ্যক তুলনা পরিবর্তনের মাধ্যমে অসামঞ্জস্য হ্রাস করতেও ব্যবহার করা যায়।
১. জোড়া তুলনা ম্যাট্রিক্সের গুরুত্ব: সিদ্ধান্ত বিশ্লেষণে, জোড়া তুলনা ম্যাট্রিক্স A = aij n টি বিকল্পের মধ্যে আপেক্ষিক গুরুত্ব প্রকাশ করতে ব্যবহৃত হয়, যেখানে aij বিকল্প i এর সাপেক্ষে বিকল্প j এর গুরুত্বের অনুপাত প্রতিনিধিত্ব করে। এই ধরনের ম্যাট্রিক্স শ্রেণিবদ্ধ বিশ্লেষণ পদ্ধতি (AHP) এর মতো সিদ্ধান্ত পদ্ধতিতে ব্যাপকভাবে প্রয়োগ করা হয়।
२. সামঞ্জস্যতার সমস্যা: আদর্শভাবে, তুলনাগুলি সামঞ্জস্যপূর্ণ হওয়া উচিত, অর্থাৎ সংক্রমণশীলতা সন্তুষ্ট করা উচিত: aijajk = aik সমস্ত i,j,k এর জন্য। তবে বাস্তবে মানুষের বিচারের সীমাবদ্ধতার কারণে, সম্পূর্ণ সামঞ্জস্যপূর্ণ তুলনা ম্যাট্রিক্স খুব কমই দেখা যায়।
३. অসম্পূর্ণ ডেটার চ্যালেঞ্জ: বাস্তব প্রয়োগে, বিভিন্ন কারণে (সময়ের সীমাবদ্ধতা, বিশেষজ্ঞ জ্ঞানের অভাব, তুলনার কঠিনতা ইত্যাদি), কিছু জোড়া তুলনা অনুপস্থিত থাকতে পারে, যা আংশিক পারস্পরিক ম্যাট্রিক্স (PRM) গঠন করে।
१. সম্পূর্ণতার প্রয়োজনীয়তা: সিদ্ধান্ত পদ্ধতিগুলি সাধারণত ওজন ভেক্টর গণনা করতে সম্পূর্ণ তুলনা ম্যাট্রিক্স প্রয়োজন, তাই অসম্পূর্ণ ম্যাট্রিক্সের যুক্তিসঙ্গত সম্পূর্ণকরণ প্রয়োজন।
२. সামঞ্জস্যতা অপ্টিমাইজেশন: যখন সম্পূর্ণ সামঞ্জস্য অর্জন করা যায় না, তখন "আনুমানিক সামঞ্জস্যপূর্ণ" সম্পূর্ণকরণ সমাধান খুঁজে বের করতে হয়, অসামঞ্জস্য পরিমাপ ন্যূনতম করতে হয়।
३. তাত্ত্বিক ফাঁক: বিদ্যমান গবেষণায় কখন সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ বিদ্যমান থাকে তার সঠিক বৈশিষ্ট্যকরণ এবং কর্ডাল গ্রাফ শর্তে অসামঞ্জস্য পরিমাপ বৃদ্ধি না করার পদ্ধতিগত পদ্ধতির অভাব রয়েছে।
१. সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ অস্তিত্বের সঠিক বৈশিষ্ট্যকরণ: দুটি দৃষ্টিকোণ থেকে সম্পূর্ণ তত্ত্ব প্রদান করে:
२. কর্ডাল গ্রাফ ক্ষেত্রে আনুমানিক সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ: প্রমাণ করে যে যখন নির্দিষ্ট প্রবেশাধিকার গ্রাফ একটি কর্ডাল গ্রাফ হয়, তখন সর্বদা ত্রিমুখ অসামঞ্জস্য পরিমাপ MT বৃদ্ধি না করে সম্পূর্ণকরণ খুঁজে পাওয়া যায়।
३. সম্পূর্ণকরণ পদ্ধতিবিদ্যা: কর্ডাল ক্রম ব্যবহার করে ম্যাট্রিক্স ক্রমান্বয়ে সম্পূর্ণ করার জন্য নির্দিষ্ট অ্যালগরিদম কাঠামো বিকাশ করে, অসামঞ্জস্য বৃদ্ধি না করা নিশ্চিত করে।
४. অসামঞ্জস্য হ্রাস কৌশল: বিদ্যমান সম্পূর্ণ ম্যাট্রিক্সের অসামঞ্জস্য হ্রাস করতে অল্প সংখ্যক প্রবেশাধিকার সংশোধনের মাধ্যমে পদ্ধতি প্রস্তাব করে।
ইনপুট: আংশিক পারস্পরিক ম্যাট্রিক্স (PRM) A, যেখানে কিছু প্রবেশাধিকার aij নির্দিষ্ট এবং পারস্পরিক সম্পত্তি aji = 1/aij সন্তুষ্ট করে আউটপুট: সম্পূর্ণ পারস্পরিক ম্যাট্রিক্স Ã, যেমন: १. Ã নির্দিষ্ট অবস্থানে A এর সাথে সামঞ্জস্যপূর্ণ २. যদি সম্ভব হয়, Ã সামঞ্জস্যপূর্ণ (rank-1) ३. যদি সম্ভব না হয়, MT(Ã) = MT(A) (অসামঞ্জস্য পরিমাপ বৃদ্ধি না করে)
সম্পূর্ণ পারস্পরিক ম্যাট্রিক্স A ∈ PCn এর জন্য, নিম্নলিখিত শর্তগুলি সমতুল্য:
MT(A) কে A তে সমস্ত ३-চক্র গুণফলের সর্বোচ্চ মান হিসাবে সংজ্ঞায়িত করুন: যেখানে c(i,j,k) = aijajkaki হল ३-চক্র গুণফল।
উপপাদ্য १: যদি G একটি কর্ডাল গ্রাফ হয়, অনুপস্থিত প্রান্তগুলির একটি ক্রম বিদ্যমান থাকে, যেমন এই প্রান্তগুলি ক্রমান্বয়ে যোগ করার সময় প্রতিটি বার কর্ডাল গ্রাফ বৈশিষ্ট্য বজায় থাকে।
এই বৈশিষ্ট্য বহুচলক সম্পূর্ণকরণ সমস্যাকে একক চলক সমস্যার একটি সিরিজে বিভক্ত করে।
উপপাদ্য २: প্রতিটি আংশিক সামঞ্জস্যপূর্ণ ম্যাট্রিক্স (PCM) যখন এবং শুধুমাত্র যখন এর গ্রাফ G এর প্রতিটি সংযুক্ত উপাদান একটি কর্ডাল গ্রাফ হয়, তখন সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ বিদ্যমান থাকে। যদি G সংযুক্ত হয়, তবে সম্পূর্ণকরণ অনন্য।
প্রমাণের চিন্তাধারা: १. একক চলক ক্ষেত্র: A(x) ফর্মের ম্যাট্রিক্সের জন্য, x = (a1,n-1 × a2n)/a2,n-1 নির্বাচন করুন যাতে A(x) rank-1 হয় २. বহুচলক ক্ষেত্র: কর্ডাল ক্রম ব্যবহার করে ক্রমান্বয়ে অনির্দিষ্ট প্রবেশাধিকার নির্ধারণ করুন ३. অসংযুক্ত ক্ষেত্র: প্রতিটি সংযুক্ত উপাদান আলাদাভাবে সম্পূর্ণ করুন, তারপর সামঞ্জস্যপূর্ণ ব্লক ম্যাট্রিক্স দিয়ে সংযুক্ত করুন
উপপাদ্য ६: ধরুন A হল n×n এর PRM এবং PC+ (প্রতিটি সম্পূর্ণ নির্দিষ্ট চক্র গুণফল ১ এর সমান), তাহলে A এর একটি সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ রয়েছে। যদি গ্রাফ G(A) সংযুক্ত হয়, এই সম্পূর্ণকরণ অনন্য।
প্রমাণ পদ্ধতি: १. G এর একটি বিস্তৃত গাছ T নির্বাচন করুন २. T এর সাথে সংশ্লিষ্ট আংশিক ম্যাট্রিক্সের একটি অনন্য সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ Ã রয়েছে ३. চক্র গুণফল শর্তের কারণে, Ã সমস্ত নির্দিষ্ট অবস্থানে A এর সাথে সামঞ্জস্যপূর্ণ
একক চলক সম্পূর্ণকরণ সমস্যা A(x) এর জন্য, সংজ্ঞায়িত করুন:
উপপাদ্য ९: একটি x0 > 0 বিদ্যমান থাকে যেমন MT(A(x0)) = MT(A) যখন এবং শুধুমাত্র যখন:
যেখানে MS(A) = max S(A), mS(A) = min S(A)।
উপপাদ্য११: ধরুন B হল নির্দিষ্ট প্রবেশাধিকার গ্রাফ কর্ডাল গ্রাফ হওয়া PRM, তাহলে B এর একটি পারস্পরিক সম্পূর্ণকরণ B̃ রয়েছে যেমন MT(B̃) = MT(B)।
অ্যালগরিদমের ধাপ: १. যদি গ্রাফ শুধুমাত্র একটি গাছ হয়, সরাসরি সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ করুন २. যদি গ্রাফ সংযুক্ত হয় এবং ३-চক্র থাকে, কর্ডাল ক্রম অনুযায়ী উপপাদ্য ९ ক্রমান্বয়ে প্রয়োগ করুন ३. যদি গ্রাফ অসংযুক্ত হয়, প্রথমে প্রতিটি সংযুক্ত উপাদান সম্পূর্ণ করুন, তারপর লেম্মা १२ ব্যবহার করে সংযুক্ত করুন
A = [१ २ x ४ ]
[१/२ १ १/३ y ]
[१/x ३ १ ५ ]
[१/४ १/y १/५ १ ]
গ্রাফ হল ४-চক্র १२३४१, যেহেতু ४ = a14 ≠ a12a23a34 = १०/३, কোন সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ নেই।
५×५ ম্যাট্রিক্স N(x,y) বিবেচনা করুন, যার নির্দিষ্ট প্রবেশাধিকার গ্রাফ একটি কর্ডাল গ্রাফ। দুটি ধাপে সম্পূর্ণকরণের মাধ্যমে: १. প্রথমে y নির্ধারণ করুন যাতে MT বৃদ্ধি না পায়: y ∈ १/३, १/२ २. তারপর x নির্ধারণ করুন যাতে MT বৃদ্ধি না পায়: x ∈ √६/४, २
१. কর্ডাল গ্রাফ শর্ত: সমস্ত পরীক্ষিত কর্ডাল গ্রাফ PCM সফলভাবে সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ খুঁজে পেয়েছে २. অ-কর্ডাল গ্রাফ পাল্টা উদাহরণ: নির্মিত ४-চক্র ইত্যাদি অ-কর্ডাল গ্রাফ PCM সত্যিই কোন সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ নেই ३. ডেটা শর্ত: PC+ শর্তের যাচাইকরণ নির্দেশ করে যে এটি সামঞ্জস্যপূর্ণ সম্পূর্ণকরণের প্রয়োজনীয় এবং পর্যাপ্ত শর্ত
१. MT পরিমাপ সংরক্ষণ: সমস্ত কর্ডাল গ্রাফ পরীক্ষা ক্ষেত্রে, MT(Ã) = MT(A) এর সম্পূর্ণকরণ সফলভাবে খুঁজে পেয়েছে २. সম্ভাব্য অঞ্চল: একক চলক সমস্যার সম্ভাব্য অঞ্চল সর্বদা অ-খালি (লেম্মা ८ দ্বারা গ্যারান্টিযুক্ত) ३. সর্বোত্তম নির্বাচন: সম্ভাব্য অঞ্চলের মধ্যে আরও অপ্টিমাইজেশন নতুন প্রবর্তিত ३-চক্র গুণফল ন্যূনতম করতে পারে
একক প্রবেশাধিকার সংশোধনের মাধ্যমে, পরীক্ষা ম্যাট্রিক্সের MT মান সফলভাবে মূল সর্বোচ্চ মান থেকে ছোট মানে হ্রাস করেছে, পদ্ধতির ব্যবহারিকতা যাচাই করেছে।
१. প্রাথমিক কাজ: সায়েটির শ্রেণিবদ্ধ বিশ্লেষণ পদ্ধতি জোড়া তুলনার ভিত্তি স্থাপন করেছে २. সম্পূর্ণকরণ পদ্ধতি: বেনিটেজ এবং অন্যরা সামঞ্জস্যপূর্ণ সম্পূর্ণকরণের বৈশিষ্ট্যকরণ অধ্যয়ন করেছেন ३. অসম্পূর্ণ ম্যাট্রিক্স: বোজোকি এবং অন্যরা সর্বোত্তম সম্পূর্ণকরণ সমস্যা অধ্যয়ন করেছেন
१. কোকজোডাই সূচক: K(A) = १/(१-MT(A)) এই পেপারের MT পরিমাপের সাথে সমতুল্য २. অন্যান্য পরিমাপ: একাধিক অসামঞ্জস্য পরিমাপ বিদ্যমান, কিন্তু MT স্থানীয়তা এবং সহজ গণনার সুবিধা রয়েছে ३. স্বতঃসিদ্ধ গবেষণা: সিসাটো ত্রিমুখ অসামঞ্জস্য সূচকের স্বতঃসিদ্ধ বিশ্লেষণ করেছেন
१. কর্ডাল গ্রাফ তত্ত্ব: গোলুম্বিকের ক্লাসিক কাজ কর্ডাল গ্রাফের ভিত্তি তত্ত্ব প্রতিষ্ঠা করেছে २. ম্যাট্রিক্স সম্পূর্ণকরণ: গ্রোন এবং অন্যরা ধনাত্মক নির্দিষ্ট ম্যাট্রিক্স সম্পূর্ণকরণে কর্ডাল গ্রাফ প্রয়োগ করেছেন ३. এই পেপারের অবদান: পারস্পরিক ম্যাট্রিক্স সম্পূর্ণকরণে কর্ডাল গ্রাফ তত্ত্ব প্রথমবারের মতো সিস্টেমেটিকভাবে প্রয়োগ করা
१. সম্পূর্ণ তাত্ত্বিক কাঠামো: পারস্পরিক ম্যাট্রিক্স সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ অস্তিত্বের সম্পূর্ণ তত্ত্ব প্রতিষ্ঠা করেছে, গ্রাফ কাঠামো এবং ডেটা-ভিত্তিক দুটি দৃষ্টিকোণ অন্তর্ভুক্ত করে २. ব্যবহারিক অ্যালগরিদম: কর্ডাল গ্রাফ ক্ষেত্রে অসামঞ্জস্য পরিমাপ বৃদ্ধি না করার নির্দিষ্ট সম্পূর্ণকরণ অ্যালগরিদম প্রদান করেছে ३. প্রয়োগ সম্প্রসারণ: পদ্ধতি বিদ্যমান ম্যাট্রিক্সের অসামঞ্জস্য হ্রাস করতে ব্যবহার করা যায়
१. কর্ডাল গ্রাফ সীমাবদ্ধতা: আনুমানিক সম্পূর্ণকরণের গ্যারান্টি শুধুমাত্র কর্ডাল গ্রাফ ক্ষেত্রে প্রযোজ্য, সাধারণ গ্রাফ ক্ষেত্র এখনও আরও গবেষণা প্রয়োজন २. পরিমাপ নির্বাচন: যদিও MT পরিমাপের তাত্ত্বিক সুবিধা রয়েছে, বাস্তব প্রয়োগে অন্যান্য পরিমাপ বিবেচনা করতে হতে পারে ३. গণনামূলক দক্ষতা: বড় আকারের সমস্যার জন্য, অ্যালগরিদমের ব্যবহারিক দক্ষতা আরও অপ্টিমাইজেশন প্রয়োজন হতে পারে
१. সাধারণ গ্রাফ সম্প্রসারণ: অ-কর্ডাল গ্রাফ ক্ষেত্রে আনুমানিক সম্পূর্ণকরণ পদ্ধতি গবেষণা করুন २. অন্যান্য পরিমাপ: পদ্ধতি অন্যান্য অসামঞ্জস্য পরিমাপে সম্প্রসারিত করুন ३. ব্যবহারিক প্রয়োগ: নির্দিষ্ট সিদ্ধান্ত সমস্যায় পদ্ধতির কার্যকারিতা যাচাই করুন
१. তাত্ত্বিক সম্পূর্ণতা: সামঞ্জস্যপূর্ণ সম্পূর্ণকরণ সমস্যার সম্পূর্ণ তাত্ত্বিক বৈশিষ্ট্যকরণ প্রদান করে, গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করে २. পদ্ধতি উদ্ভাবন: কর্ডাল গ্রাফ তত্ত্ব পারস্পরিক ম্যাট্রিক্স সম্পূর্ণকরণে চতুরভাবে প্রয়োগ করে, প্রযুক্তিগত পথ উদ্ভাবনী ३. ব্যবহারিক মূল্য: অ্যালগরিদম বহুপদী সময় জটিলতা রয়েছে, ব্যবহারিক প্রয়োগের জন্য উপযুক্ত ४. লেখার স্পষ্টতা: পেপার কাঠামো স্পষ্ট, উপপাদ্য প্রমাণ কঠোর, উদাহরণ সমৃদ্ধ
१. প্রয়োগের পরিধি: প্রধান ফলাফল কর্ডাল গ্রাফ ক্ষেত্রে সীমাবদ্ধ, সাধারণ গ্রাফের চিকিৎসা অপর্যাপ্ত २. পরীক্ষামূলক যাচাইকরণ: বড় আকারের সংখ্যাগত পরীক্ষা এবং বাস্তব ডেটা যাচাইকরণের অভাব ३. তুলনামূলক বিশ্লেষণ: অন্যান্য সম্পূর্ণকরণ পদ্ধতির সাথে সিস্টেমেটিক তুলনা অপর্যাপ্ত ४. গণনামূলক বিবরণ: কিছু অ্যালগরিদম ধাপের নির্দিষ্ট বাস্তবায়ন বিবরণ অপর্যাপ্ত
१. তাত্ত্বিক অবদান: সিদ্ধান্ত বিশ্লেষণে অসম্পূর্ণ ডেটা প্রক্রিয়াকরণের জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে २. পদ্ধতিগত মূল্য: কর্ডাল ক্রম বিয়োজন চিন্তাভাবনা অন্যান্য ম্যাট্রিক্স সম্পূর্ণকরণ সমস্যার গবেষণা অনুপ্রাণিত করতে পারে ३. ব্যবহারিক সম্ভাবনা: পদ্ধতি AHP ইত্যাদি সিদ্ধান্ত পদ্ধতিতে ডেটা প্রাক-প্রক্রিয়াকরণে সরাসরি প্রয়োগ করা যায় ४. শৃঙ্খলা অতিক্রম: গ্রাফ তত্ত্ব, ম্যাট্রিক্স তত্ত্ব এবং সিদ্ধান্ত বিশ্লেষণের জৈব সমন্বয় প্রদর্শন করে
१. সিদ্ধান্ত বিশ্লেষণ: AHP, ANP ইত্যাদি জোড়া তুলনা প্রয়োজনীয় বহু-মানদণ্ড সিদ্ধান্ত পদ্ধতি २. ডেটা খনন: অসম্পূর্ণ সম্পর্ক ডেটার প্রাক-প্রক্রিয়াকরণ এবং সম্পূর্ণকরণ ३. সামাজিক নেটওয়ার্ক: সম্পর্ক শক্তি ম্যাট্রিক্সের সম্পূর্ণকরণ এবং সামঞ্জস্যতা বিশ্লেষণ ४. অর্থনীতি: পছন্দ সম্পর্ক এবং উপযোগিতা ফাংশনের অনুমান
পেপারটি ২६টি সম্পর্কিত তথ্যসূত্র উদ্ধৃত করে, যা জোড়া তুলনা ম্যাট্রিক্স, অসামঞ্জস্য পরিমাপ, গ্রাফ তত্ত্ব এবং ম্যাট্রিক্স সম্পূর্ণকরণ সহ একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।
সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক পেপার যা পারস্পরিক ম্যাট্রিক্স সম্পূর্ণকরণের এই গুরুত্বপূর্ণ সমস্যায় উল্লেখযোগ্য তাত্ত্বিক অগ্রগতি অর্জন করেছে। যদিও পরীক্ষামূলক যাচাইকরণ এবং প্রয়োগের পরিধিতে কিছু অপূর্ণতা রয়েছে, তবে এর তাত্ত্বিক অবদান এবং পদ্ধতি উদ্ভাবন গুরুত্বপূর্ণ মূল্য রাখে এবং সিদ্ধান্ত বিশ্লেষণ এবং সম্পর্কিত ক্ষেত্রের গবেষণায় ইতিবাচক প্রভাব ফেলে।