Shishani taqiqlash bo'yicha muammo - Linear bottleneck assignment problem - Wikipedia

Yilda kombinatorial optimallashtirish, matematikadagi maydon, the chiziqli to'siqni tayinlash muammosi (LBAP) ga o'xshash chiziqli tayinlash muammosi.^[1]

Oddiy so'zlar bilan muammo quyidagicha bayon etilgan:

Bir qator bor agentlar va bir qator vazifalar. Har qanday agentga biron bir vazifani bajarish uchun tayinlanishi mumkin, bunda ba'zilari bo'ladi xarajat agent-topshiriq topshirig'iga qarab farq qilishi mumkin. Har bir topshiriqqa shunday qilib bitta agentni tayinlash orqali barcha vazifalarni bajarish talab qilinadi maksimal narx individual topshiriqlar orasida minimallashtiriladi.

Atama "torlik "muammoning qo'llanilishining keng tarqalgan turi bilan izohlanadi, bu erda xarajatlar agent tomonidan bajariladigan topshiriqning davomiyligi hisoblanadi. Ushbu parametrda" maksimal xarajat "" maksimal davomiylik "bo'lib, bu jadvalning taqsimlanish nuqtasi hisoblanadi. minimallashtirilishi kerak bo'lgan umumiy ish.

Rasmiy ta'rif

Darboğazni tayinlash muammosining rasmiy ta'rifi

Ikki to'plam berilgan, A va Tbilan birga vazn funktsiyasi C : A × T → R. A ni toping bijection f : A → T shunday xarajat funktsiyasi:

${ displaystyle max _ {a in A} C (a, f (a))}$

minimallashtirilgan.

Odatda vazn funktsiyasi haqiqiy qiymatga ega kvadrat sifatida qaraladi matritsa C, shuning uchun xarajat funktsiyasi quyidagicha yoziladi:

${ displaystyle max _ {a in A} C_ {a, f (a)}}$

Matematik dasturlashni shakllantirish

${ displaystyle min , max _ {i, j} c_ {ij} x_ {ij}}$

uchun mavzu:

${ displaystyle sum _ {j = 1} ^ {n} x_ {ij} = 1 (i = 1,2, nuqta, n),}$

${ displaystyle sum _ {i = 1} ^ {n} x_ {ij} = 1 (j = 1,2, nuqta, n),}$

${ displaystyle x_ {ij} in {0,1 } (i, j = 1,2, nuqta, n)}$

Asimptotiklar

Ruxsat bering ${ displaystyle c_ {n} ^ {*}}$ muammo uchun maqbul ob'ektiv funktsiya qiymatini belgilang n agentlari va n vazifalar. Agar xarajatlar bo'lsa ${ displaystyle c_ {ij}}$ (0,1) bo'yicha yagona taqsimotdan namuna olinadi, keyin ^[2]

${ displaystyle E [c_ {n} ^ {*}] = { frac { log n + log 2+ gamma} {n}} + O chap ({ frac {( log n) ^ {2) }} {n ^ {7/5}}} o'ng)}$

va

${ displaystyle Var [c_ {n} ^ {*}] = { frac { zeta (2) -2 ( log 2) ^ {2}} {n ^ {2}}} + O chap ({ frac {( log n) ^ {2}} {n ^ {7/3}}} o'ng).}$

Adabiyotlar