570
2-хосса.
Талаб доирасидаги биринчи йиғилмаларни мумкин бўлган бирлашмалари учун
ij
i
j
I
i
J
j
Q
X
j
йиғиндининг қийматлари ичида
(
)
бош
син
ij
j
I
i
J
j
Q
X
j
йиғинди энг катта қийматга
(
)
ох
син
ij
i
I
i
J
j
Q
X
j
- эса энг кичик бўлади. Бу хоссани тўғрилигини “бошидан” тартибида
шакллантирилган бирлашма учун исботлаймиз. Маълумки “бошидан” тартибида
шакллантирилган бирлашма
бош
mg
i
j
j
X
H
1
)
(
йиғилмаларидан ташкил топади. Бу йиғилмани
элементлари
i
j
j
X
маршрутдаги тўла қатнов вақтини
1
t
ошиб бориш тартибида жойлашган.
Бу эса
j
i
Q
параметри қийматини камайиб бориш тартибига мос келади. Энди “бошидан”
тартибида шакллантирилган биринчи талабга доир йиғилмада, унинг бошида келувчи
i
j
j
X
элементлар, ўзининг энг катта қийматини қабул қилади ва
уларга
ij
Q
параметрларнинг энг
катта қиймати мос келади. Чунки,
j
i
Q
қиймати йиғилманинг бошидан охирига йўналишида
камаювчи
i
j
j
X
элементларга мос келувчи
j
i
Q
қийматлари
энг каттадан бошланиб, кейин
камая боради. “Бошидан” тартибида шакллантирилган бирлашма фақат
бош
mg
i
j
j
X
H
1
)
(
йиғилмалардан иборат бўлганлиги учун ва бу йиғилмалар учун
ij
i
j
I
i
J
j
Q
X
j
йиғинди мумкин
бўлган катта қийматлар ичида энг катта қийматга эга бўлганлиги туфайли мазкур бирлашма
учун ҳам бу йиғинди энг катта қийматга эга бўлади.
2- хоссадан қуйидаги натижавий хосса келиб чиқади:
1-натижавий хосса.
Агар синовчи бирлашма қуйидаги
шартга жавоб бера олса, яъни
(
)
бош
син
ij
j
I
i
J
j
Q
X
j
min
Q
ёки
(
)
max
Q
Q
X
ох
син
ij
j
I
i
J
j
j
, унда масала берилган дастлабки
параметрлар қийматлари доирасида ечимга эга бўлмайди.
Юқоридаги 2-хоссани ҳисобга олсак, 1-натижавий хоссани тўғрилигини ўз-ўзидан
маълум бўлади. Ҳақиқатан ҳам “бошидан” шакллантирилган синовчи бирлашма учун йиғинди
(
)
бош
син
ij
j
I
i
J
j
Q
X
j
мумкин бўлган йиғиндилар ичида энг каттаси ҳисобланади.
Агар бу
йиғинди
min
Q
қийматидан кичик бўлса, унда бошқа ҳар қандай бирлашма учун юқоридаги
шарт ўринлидир. Демак, масала ечимга эга эмас.
Шундай қилиб, масалани ечиш учун биринчи навбатда талаб доирасидаги барча 1- йиғилмалар
“бошидан” ёки “охиридан” тартибида шакллантирилади ва уларни тегишли синовчи
бирлашмаси учун йиғинди
(
)
бош
син
ij
i
j
I
i
J
j
Q
X
j
ёки
(
)
ох
син
ij
i
j
I
i
J
j
Q
X
j
қийматлари аниқланади.
Бу йиғинди қиймати
min
Q
ва
max
Q
қийматлари билан солиштирилади.
Агар солиштириш
натижасида 1- натижавий хоссада кўзда тутилган ҳоллар юз берса,
унда масала ечимга эга
бўлмайди. Агар бундай ҳоллар юз бермаса, унда дастлабки бирлашма йиғилмаларида “ўнг”
ёки “чап” йўналишида кўчиришлар ўтказиш лозимлиги ҳақида хулоса қилинади.
Шундай қилиб, туташма манзилни маршрутларига автотранспорт воситаларини самарали
тақсимлаш масаласини дискрет ечимларини аниқлашга
имкон берувчи комбинаторик
усулнинг назарий хоссалари асосланди. Келтирилган хоссаларга асосан масаланинг умумий
ечимини шакллантириш механизми, босқичлардаги процедураларнинг
алгоритмлари
шакллантириш мумкин.
