Methods of Assignment Problem
Posted by ADMIN in My Research And Development
Assignment ျပႆနာဆိုသည္မွာ ကြဲျပားျခားနားတဲ႔ အလုပ္မ်ားအတြက္ ကြဲျပားျခားနားတဲ႔ အစီအမံေတြ ခန္႔ခြဲေပးျခင္းျဖစ္သည္။ ေငြေၾကး (သို႔) အဓိကစြမ္းအင္ တစ္ခုခုကို အေကာင္းဆံုး စီမံခန္႔ခြဲ အသံုးျပဳျခင္း ဟူ၍လည္းနားလည္နုိင္သည္။ ဤျပႆနာသည္ေန႔စဥ္ႏွင္႔အမွ် လူသားတို႔ ရင္ဆုိင္ေနရတာေၾကာင္႔ ေျဖရွင္းနည္းလည္း ေျမာက္မ်ားစြာ ရွိေပသည္။ အထူးသျဖင္႔ စီးပြားေရး လုပ္ငန္းမ်ားတြင္သာမက လူမႈေရးလုပ္ငန္းမ်ား၊ ကယ္ဆယ္ေရးလုပ္ငန္းမ်ားအျပင္ သယ္ယူပို႔ေဆာင္ေရးလုပ္းမ်ားအတြက္ အေရးပါေသာ ျပႆနာျဖစ္လာသည္။
ယေန႔ ကမာၻတြင္ ရင္ဆုိင္ေနရေသာ Assignment ျပႆနာကို ေျဖရွင္းေနသည္႔ နည္းလမ္း (၄) ခုရွိသည္။ ၎တို႔မွာ
ယေန႔ ကမာၻတြင္ ရင္ဆုိင္ေနရေသာ Assignment ျပႆနာကို ေျဖရွင္းေနသည္႔ နည္းလမ္း (၄) ခုရွိသည္။ ၎တို႔မွာ
- Complete Enumeration Method:
Complete Enumeration Method ဆိုသည္မွာ assignment ျပႆနာ အေသးေလးမ်ားအတြက္ အသံုးျပဳေသာ နည္းလမ္းျဖစ္သည္။ အခ်က္အလက္မ်ားအားလံုးကို တိတိက်က် ျပည္႔ျပည္႔စံုစံု တစ္ခုခ်င္းစီၿပီး ခြဲေသာ စနစ္ျဖစ္သည္။ ဥပမာ အလုပ္လိုခ်င္သူမ်ားကို သူတို႔၏ ကၽြမ္းက်င္မႈအလိုက္ တစ္ခုခ်င္း ေလ႔လာၿပီး သင္႔ေလွ်ာ္အလုပ္မ်ားသို႔ ခိုင္းေစ ျခင္းျဖစ္သည္။ သို႔ေသာ္ ဤနည္းလမ္းသည္ တြက္ခ်က္ျခင္းမွ ထြက္လာေသာ ရလဒ္ႏွင္႔ ျပင္ပတြင္ရွိေသာ ရလဒ္တို႔၏ ကြာဟမႈမ်ား မၾကာခဏ ႀကံဳေတြ႔ရတတ္သည္။ - Simplex Method:
Simplex Method ဆိုသည္မွာ ကြန္ပ်ဴတာ သခ်ၤာ၏ အခက္ခဲဆံုး programming ထဲမွာ တစ္ခုအပါအဝင္ျဖစ္ေသာ linear programming ကို အေျခခံထားေသာ နည္းလမ္းျဖစ္သည္။ ဤနည္းလမ္းျဖင္႔ ေျဖရွင္းျခင္းသည္ ရလဒ္ေကာင္းကို ရရွိနုိင္ေသာ္လည္း ၿငီးေငြ႔ဖြယ္ ေကာင္းလွသည္။ - Transportation Method:
Transportation Method ဆိုသည္မွာ အမ်ားထဲမွ အသင္႔ေတာ္ဆံုးကို ေရြးခ်ယ္ေသာ စနစ္ျဖစ္သည္။ ရလဒ္ေကာင္းေတြ ရရွိနုိင္ၿပီး အေျခခံအက်ဆံုး နည္းလမ္းျဖစ္သည္။ သို႔ေသာ္ အလုပ္တစ္ခုကို လူတစ္ေယာက္က ကိုင္တြယ္နုိင္မွသာ အဆင္ေျပနုိင္သည္။ မ်ားျပားလာလွ်င္ မွားယြင္းေသာ ရလဒ္မ်ား ျဖစ္ေပၚလာနုိင္သည္။ - Hungarian Assignment Method (HAM):
Hungarian Assignment Method (HAM) ဤနည္းလမ္းသည္ ေငြေၾကးျပႆနာမ်ားႏွင္႔ အျခား ျပႆနာမ်ားကို ေျဖရွင္းရန္အတြက္ အေကာင္းဆံုး နည္းလမ္းျဖစ္သည္။
Hungarian Assignment Method
Hungarian Assignment Method သည္ Assignment ျပႆနာမ်ား ေျဖရွင္းရာတြင္ လက္တေလာအားျဖင္႔ ေကာင္းဆံုး နည္းျဖစ္သည္။ လြယ္ကူျခင္း၊ လွ်င္ျမန္ျခင္း၊ တိက်ျခင္း တို႔သည္ ဤနည္းလမ္း၏ အားသာခ်က္မ်ားျဖစ္သည္။ က်ေနာ္လုပ္ေနသည္႔ Research သည္ Navigation System ျဖစ္ေသာေၾကာင္႔ Navigation ႏွင္႔ ပတ္သက္ေသာ Assignment ျပႆနာ တစ္ခုကို Hungarian Assignment နည္းလမ္းျဖင္႔ ေျဖရွင္းျခင္း အေၾကာင္း ပုဒ္စာတစ္ပုဒ္ကို ေျဖရွင္းျပပါမည္။ Navigation System အေၾကာင္း သိလိုပါက http://www.meepyatite.info/2008/03/navigation-system.html သို႔ သြားေရာက္ဖတ္ရႈနုိင္သည္။
Assignment ျပႆနာအေၾကာင္း ေျပာခဲ႔စဥ္က သကဲ႔သို႔ပင္ ဤျပႆနာသည္ ေရာင္းသူႏွင္႔ ဝယ္သူၾကား (သို႔) ေပးခ်င္သူႏွင္႔ လိုခ်င္သူၾကား (သို႔) လြတ္ေနေသာေနရာႏွင္႔ အလုပ္လုပ္ခ်င္သူတို႔ အေၾကား (သို႔) သြားခ်င္သူမ်ားႏွင္႔ ေခၚခ်င္သူ မ်ားအၾကား စီမံခန္႔ခြဲေပးသည္႔ စနစ္ျဖစ္သည္။
ံပံု ကား (၅) စီးႏွင္႔ တည္ေနရာ (၅) ခု ကို ေဖာ္ျပထားသည္။ ကားမ်ားသည္ Taxi မ်ားလည္း ျဖစ္နုိင္သည္။ ရဲကားမ်ားလည္း ျဖစ္နုိင္သည္။ မီးသတ္ကားမ်ားလည္း ျဖစ္နုိင္သည္။ ေနရာ မ်ားသည္ Taxi ငွားလိုသူမ်ားလည္း ျဖစ္နုိင္သည္။ ရာဇဝတ္မႈ က်ဴးလြန္ရာေနရာ (သို႔) 199 ကို ေခၚၿပီး ရဲစခန္းသို႔ အကူညီေတာင္းေသာ ေနရာမ်ားလည္း ျဖစ္နုိင္သည္။ မီးေလာင္ေနေသာ ေနရာမ်ားလည္း ျဖစ္နုိင္သည္။ အတြင္းမွ ဂဏန္းမ်ားမွာ အကြာအေဝး မိုင္ (သို႔) ကီလိုမီတာ မ်ားျဖစ္သည္။ ထိုအကြာအေဝးမ်ားကို ႀကိဳတင္ မွတ္သားထားရမည္ျဖစ္ၿပီး ယဥ္မ်ား၏ ေရြ႕လွ်ားေနမႈအေပၚတြင္ အၿမဲ ေျပာင္းလဲ ေဖာ္ျပေပးရမည္။ ယင္းအတြက္ GPS ၿဂိဳလ္တုမ်ား (သို႔) GSM အန္တင္နာ မ်ားကို အသံုးျပဳ ရမည္ျဖစ္သည္။ GSM Antenna မ်ားျဖင္႔ တည္ေနရာ ေဖာ္ျပပံုကို http://www.meepyatite.info/2009/06/1.html တြင္ ျမန္မာ၊ အဂၤလိပ္၊ ရုရွား သံုးဘာသာျဖင္႔ ေရးသားထားသည္။ ၿဂိဳလ္တုမ်ား အေၾကာင္း သိလိုပါက http://www.meepyatite.info/2009/11/blog-post.html တြင္ ေလ႔လာနုိင္သည္။ စာအုပ္လိုက္ ဖတ္လိုပါက http://www.meepyatite.info/2010/05/satellite-system-navigation-system-gnss.html တြင္ ေဖာ္ျပထားသည္။
မတူညီေသာ ေနရာ ၅ ခု သို႔ ေရာက္ရွိေနေသာ Taxi ၅ စီးကို မတူညီေသာ ေနရာ ၅ ေနရာမွ ေခၚခ်ိန္တြင္ မည္သည္႔ Taxi ကို မည္သည္႔ ေနရာသို႔ သြားခိုင္းမည္နည္း?? မတူညီေသာ ေနရာမ်ားသို႔ ေရာက္ရွိေနေသာ ကင္းလွည္႔ေနသည္႔ ရဲ ကား ၅ စီးကို အခင္းျဖစ္ပြားေန ေသာ ေနရာ ၅ ခု အတြက္ မည္သည္႔ ကားကို မည္သည္႔ေနရာသို႔ သြားခိုင္းမည္နည္း?? မီးသတ္စခန္း ၅ ခု မွ မီးသတ္ကား မ်ားကို တစ္ခ်ိန္တည္း မီးေလာင္ေနေသာ ေနရာ ၅ ေနရာအတြက္ ဘယ္စခန္းက ကားမ်ားကို ဘယ္ေနရာသို႔ ေစလႊတ္မည္နည္း?? အေရးပါသည္႔ ေမးခြန္းမ်ားျဖစ္သည္။ လြယ္လြယ္ေျဖလွ်င္ေတာ႔ အနီးဆံုးႏွင္႔ အျမန္ဆံုးေရာက္နုိင္သည္႔ ယဥ္မ်ားကို အနီးဆံုးေနရာမ်ားသို႔ ပို႔မည္ျဖစ္သည္။ မွန္သည္။ အနီးဆံုးႏွင္႔ အျမန္ဆံုးကို မည္သို႔ သိနုိင္မည္နည္း?? ေအာက္တြင္ ဆက္လက္ၿပီး အေျဖထုတ္ၾကပါစို႔။
ရရွိလာေသာ အေျဖသည္ အလြန္အေရးႀကီးေပသည္။ ၁၀၀% ႏံႈးမွန္ကန္ဖို႔လိုအပ္သည္။ သို႔မွသာ အနီးဆံုးေနရာသို႔ အနီးဆံုးယဥ္မွ ေရာက္ရွိသြားၿပီး ပ်က္ဆီးဆံုးရႈံးမႈမ်ားႏွင္႔ အသက္ေပါင္းမ်ားစြာကို ကယ္တင္နုိင္မည္ျဖစ္သည္။
ပထမဆံုး အေနနွင္႔ ဇယားအတြင္းမွ အတန္း (row) အလိုက္ အငယ္ဆံုး ဂဏာန္းမ်ားကို ေရြးခ်ယ္ပါ။ ထို႔ေနာက္ ထို ဂဏန္းမ်ားျဖင္႔ အတန္း တစ္ခုလံုးကို ႏုတ္ပါ။
အတန္းတိုင္း အတြက္ သုည မ်ား ရရွိလာပါလိမ္႔မည္။ ထို႔ေနာက္ အတိုင္ (column) တိုင္းတြင္ သုညမ်ား ရွိမရွိ စစ္ေဆးပါ။ မရွိပါက မရွိသည္႔ အတိုင္ မွ အငယ္ဆံုး ဂဏန္းကို ရွာ၍ အတိုင္ တစ္ခုလံုးကို ႏႈတ္ပါ။
ယခုဆိုလွ်င္ အတန္းတုိင္း၊ အတုိင္တိုင္းအတြက္ သုညမ်ား ရရွိလာၿပီျဖစ္သည္။
သုည ရွိရာ ေနရာမ်ားအတိုင္း ခ်ိတ္ဆက္လိုက္ပါ။ ယခု အေနအထားတြင္ မည္သည္႔ယဥ္က မည္သည္႔ေနရာသို႔ သြားနုိင္ေၾကာင္း သိနုိင္ၿပီျဖစ္သည္။ ကားအမွတ္ ၁ အတြက္ အနီးဆံုး မွာ ေနရာ ၂ ျဖစ္သည္။ ကား အမွတ္ ၂ အတြက္ ေနရာ (၁)(၃)(၅) သံုးခုလံုး က အနီးဆံုးေတြျဖစ္၍ ႀကိဳက္တဲ႔ေနရာ သြားနုိင္သည္။
တစ္စီးစီက တစ္ေနရာစီ ေဖာ္ျပလွ်င္ ျပႆနာ ေျပလည္သြားမည္ျဖစ္ေသာ္လည္း အကြာအေဝး တူေနေသာၾကာင္႔ ပိုမိုရႈပ္ေထြးလာမည္။ အဆင္ေျပသည္႔ တစ္ေနရာ လႊတ္၍လည္း မျဖစ္ေပ၊ က်န္သည္႔ ယဥ္မ်ားအတြက္ က်န္သည္႔ေနရာမ်ားက အေဝးဆံုးေတြလည္း ျဖစ္နုိင္သည္။
ဤအေနအထားတြင္ ပထမဆံုး ယဥ္တစ္စီးမွ တည္ေနရာတည္းကိုသာ သြားနုိင္ေသာ ရလဒ္မ်ား ႏွင္႔ ေနရာတစ္ေနရာမွ ယဥ္ တစ္စီး ကိုသာ လက္ခံေသာ ရလဒ္မ်ားကို အရင္ ေရြးထုတ္ဖို႔လိုသည္။
ရလဒ္မ်ားအတုိင္း လမ္းေၾကာင္းမ်ားကို အနီေရာင္ျဖင္႔ ေဖာ္ျပထားသည္။ မူလတြင္ X2 သည္ Y1, Y3, Y5 ေနရာ သံုးခုလံုးသို႔ သြားနုိင္ေသာ္လည္း Y1 ႏွင္႔ Y3 သို႔ အျခား ယဥ္မ်ားလည္း သြားနုိင္သည္။ သို႔ေသာ္ Y5 သို႔ သြားရန္မွ X2 တစ္စီးသာရွိေသာေၾကာင္႔ X2 ကို Y5 သို႔ ေသခ်ာေပါက္ ေစလြတ္ရေပမည္။
ၠဤ အေျခအေနတြင္ ယဥ္အေရအတြက္ ႏွင္႔ တည္ေနရာ အေရအတြက္ မွာ ၅ ခုစီျဖစ္ၿပီး။ ရလဒ္ ၄ ခု ထြက္ေနေသာေၾကာင္႔ ေနာက္ဆံုး က်န္ခဲ႔သည္႔ ယဥ္ X4 ကို ေနာက္ဆံုးက်န္ခဲ႔သည္ Y1 သို႔ ေစလႊတ္နုိင္သည္။ သို႔ေသာ္ လမ္းေၾကာင္း ရလဒ္မ်ား နည္းလွ်င္ေသာလည္းေကာင္း၊ ယဥ္ႏွင္႔ ေနရာ အေရအတြက္တို႔ မ်ားလွ်င္ေသာ္လည္းေကာင္း ဆက္လက္ အေျဖရရန္ လိုအပ္ေပသည္။
ပံုတြင္ ရွင္းလင္းထားသည္႔အတိုင္း α (alpha) မရွိေသာ X (၃) လံုးႏွင္႔ α (alpha) ရွိေသာ Y တစ္လံုးကို ေရြးခ်ယ္ပါ။
ထို ေနရာမ်ားကို အေရာင္ျခယ္လိုက္ပါ။
ထို႔ေနာက္ အေရာင္ မျခယ္ထားေသာ ဂဏာန္း ၈ ခုထဲမွ အငယ္ဆံုး ဂဏာန္း ကို ေရြးခ်ယ္၍ ပံုတြင္ ျပထားသည္႔ အတုိင္း အေရာင္ျခယ္ထားသည္႔ အတန္းမ်ားအားလံုး ကို ေပါင္းထည္႔ၿပီး အေရာင္မခ်ယ္ထားေသာ အတုိင္မ်ားကို ႏႈတ္ပါ။
ထို႔ေနာက္ ဇယားတြင္ သုည အသစ္မ်ား ထပ္ရလာလိမ္႔မည္။ ထို သုည အသစ္မ်ားအတိုင္း ေနရာမ်ားႏွင္႔ ယဥ္မ်ားကို ခ်ိတ္ဆက္လွ်င္ အနီးဆံုးလမ္းႏွင္႔ အလွ်င္ျမန္ဆံုး ေရာက္ရွိမည္႔ ရလဒ္ကို ရရွိမည္ျဖစ္သည္။
မူလ ဇယားႏွင္႔ ရလဒ္ တို႔မွာ ပံုတြင္ ျပထားသည္႔အတုိင္းျဖစ္သည္။
Hungarian Assignment Method ကို ျမန္မာနုိင္ငံတြင္ အသံုးျပဳရန္ လုပ္ထားေသာ Modal ျဖစ္သည္။ ေဖာ္ျပပါ ပံုသည္ ျမန္မာနုိင္ငံ အလယ္ပိုင္းေဒသ တစ္ေနရာျဖစ္ၿပီး ကား ပံုမ်ားသည္ မီးသတ္စခန္းမ်ား (သို႔) ရဲကားမ်ား ျဖစ္သည္။ အနီေရာင္ အလံမ်ားမွာ အေရးေပၚ သြားရန္လိုအပ္ေသာ ေနရာမ်ားျဖစ္သည္။ ယင္းအေျခအေနမ်ိဳးတြင္ မည္သည္႔ စခန္း က မည္သည္႔ေနရာကို သြားေရာက္တာဝန္ယူရန္ ခ်က္ခ်င္းမသိနုိင္ေပ။
အထက္ပါ ပံုမွာ ရလဒ္ အေျဖျဖစ္ၿပီး ဤ Program ကို C# ထဲ တြင္ ေရးထားသည္။ ယဥ္မ်ားေနရာတြင္ လူေမာင္းယဥ္မ်ားအျပင္ ေမာင္းသူမဲ႔ ယဥ္မ်ားကိုလည္း အစားထိုး အသံုးျပဳနိုင္သည္။ ေမာင္သူမဲ႔ ယဥ္မ်ားအေၾကာင္းကို http://www.meepyatite.info/2010/09/navigation-system-darpa.html တြင္ ေရးသားခဲ႔ၿပီးျဖစ္သည္။
Simplex Method
Simplex Method ဆိုသည္မွာ အလြန္ရႈပ္ေထြးၿပီး ၿငီးေငြ႔ဖြယ္ေကာင္းေသာ နည္းလမ္းျဖစ္ေၾကာင္း အထက္တြင္ ေဖာ္ျပခဲ႔ၿပီးျဖစ္သည္။ ယခု Simplex Method ဥပမာ ပုဒ္စာတစ္ပုဒ္ကို ရွင္းလင္းျပပါမည္။
ေပးထားေသာ ပုဒ္စာတြင္ မသိကိန္း (၃) လံုးႏွင္႔ မညီမွ်ျခင္း (၃) ခု ေပးထားသည္။
ပထမဆံုး ေနာက္ထပ္ မသိကိန္း အသစ္ ၃ လံုးကို တစ္လံုးစီ ေပါင္းထည္႔ၿပီး မညီမွ်ျခင္းကို ညီမွ်ျခင္းအျဖစ္ေျပာင္းပါ။
ထို႔ေနာက္ ဇယားအတြင္းသို႔ ပံုတြင္ ျပထားသည္႔အတုိင္းထည္႔ပါ။
ထို႔ေနာက္ အသစ္ထည္႔လိုက္သည္႔ မသိကိန္း (၃) လံုး၏ တန္ဖိုးမ်ားကို ရရွိလာသည္။ စာျဖင္႔ နားလည္ေအာင္ ေရးသား၍ မျဖစ္နုိင္ေသာေၾကာင္႔ ဗြီဒီယိုဖိုင္ကို ဆက္ၾကည္႔ပါ။ မည္မွ် ရႈပ္ေထြး ၿငီးေငြ႔ဖြယ္ေကာင္းေၾကာင္း သိနိုင္သည္။
Simplex Method သည္ ရႈပ္ေထြးေသာ္လည္း Navigation System အတြက္ အသံုးဝင္သည္။ Simplex Method ကို အသံုးျပဳ၍ တည္ေနရာကို တိတိက်က် ရွာေဖြနုိင္ေပသည္။ တည္ေနရာ ရွာေဖြျခင္းအေၾကာင္းႏွင္႔ ပတ္သက္ၿပီး ကမာၻ႔ေနရာျပစနစ္ ေခၚ (GPS System) အေၾကာင္းကို http://www.meepyatite.info/2009/01/global-positioning-system.html တြင္ ေလ႔လာနုိင္သည္။ တည္ေနရာရွာေဖြျခင္းသည္ Navigation System ၏ အေရးပါဆံုး အခ်က္ျဖစ္ေၾကာင္း ကိုလည္း http://www.meepyatite.info/search/label/My%20Research%20And%20 Development% 20 Of% 20.... မွ post အေတာ္မ်ားမ်ားတြင္ ေဖာ္ျပခဲ႔ၿပီးျဖစ္သည္။ ယခုလည္း ၿဂိဳလ္တုမ်ား မလိုပဲ Simplex Method ျဖင္႔ တည္ေနရာကို ရွာေဖြနုိင္ေၾကာင္း ေဖာ္ျပပါအံုးမည္။
Simplex Method မသိကိန္း မ်ားပါဝင္ေသာ မညီမွ်ျခင္းမ်ားရွိေၾကာင္း အထက္တြက္ ေဖာ္ျပခဲ႔ၿပီးျဖစ္သည္။ ထို မညီမွ်ျခင္းမ်ားအတုိင္း ပံုတြင္ ေရးဆြဲလိုက္ပါ။ မညီမွ်ျခင္းမ်ားမွ less than (< ) ဆိုလွ်င္ အတြင္း၊ greater than ( > ) ဆိုလွ်င္ အျပင္ သို႔ ေရးျခယ္ပါ။ ထို႔ေနာက္ လိုခ်င္ေသာ တည္ေနရာ အကြက္ငယ္ တစ္ခုကို ရရွိမည္ျဖစ္သည္။ မညီမွ်ျခင္း အေၾကာင္းေရ မ်ားလွ်င္ မ်ားသေလာက္ တိက်မည္ျဖစ္သည္။
ဤ နည္းလမ္းက http://www.meepyatite.info/2010/07/idea.html တြင္ ေဖာ္ျပထားသည္႔ IDEA မ်ားမွ Idea №4 ကိုလည္း မ်ားစြာ အေထာက္ကူျဖစ္ေစသည္။
8
comments »
ဘယ္လ္ဂ်ီယန္ 
အဲလ္ ေစးလ္ဗားေဒါ 
.jpg)
