Бутун сонли дастурлаш

ОАВС кўп бурчакнинг нуқталари ичида берилган бутун сонли дастурлаш масаласининг ечими бўла оладиган нуқтани топиш учун бу кўпбурчакни OKEMNF кўпбурчак билан алмаштирамиз. OKEMNF кўпбурчак координаталари бутун сонлардан иборат бўлган нуқталарни ўз ичига олади ва унинг бурчак нуқталарининг координаталари бутун сонлардан иборат бўлади. Энди (17) функцияга максимум қиймат берувчи нуқтани OKEMNF кўпбурчакнинг бурчак нуқталари ичидан қидирамиз. Бу кўпбурчакнинг нуқталари ичида (17) функцияга максимум қиймат берувчи нуқта берилган масаланинг оптимал ечимини аниқлайди. Бундай нуқтани топиш учун У га ихтиёрий, масалан,

қиймат берамиз ва тўғри чизиқни ясаймиз.

Бу чизиқни С(2;4) вектор йўналишида OKEMNF кўпбурчакнинг шу йўналиш идаги четки нуқтаси билан кесишгунча силжитиб борамиз. Ана шу бурчак нуқтанинг координаталари берилган масаланинг ечимини аниқлайди, мақсад функциянинг шу нуқтадаги қиймати эса максимал бўлади. Шаклдан кўринадики, бундай нуқта Е(1;3) дан иборат. Демак, берилган масаланинг ечими қуйидагича бўлади:

Бу чизиқни С(2;4) вектор йўналишида OKEMNF кўпбурчакнинг шу йўналиш идаги четки нуқтаси билан кесишгунча силжитиб борамиз. Ана шу бурчак нуқтанинг координаталари берилган масаланинг ечимини аниқлайди, мақсад функциянинг шу нуқтадаги қиймати эса максимал бўлади. Шаклдан кўринадики, бундай нуқта Е(1;3) дан иборат. Демак, берилган масаланинг ечими қуйидагича бўлади:

2-мисол. Берилган бутун сонли дастурлаш масаласини график усулда ечинг.

2-мисол. Берилган бутун сонли дастурлаш масаласини график усулда ечинг.

Ечиш. Масаладаги (24) тенгсизликлар системасининг (25) шартни қаноатлантирувчи номанфий ечимларини ўз ичига олувчи ОАВС кўпбурчак ясаймиз (2-шакл).

Ечиш. Масаладаги (24) тенгсизликлар системасининг (25) шартни қаноатлантирувчи номанфий ечимларини ўз ичига олувчи ОАВС кўпбурчак ясаймиз (2-шакл).

2-шакл

ОАВС кўпбурчакни OKLMNF кўпбурчак билан алмаштирамиз. Бу кўпбурчак координа-талари бутун сонлардан иборат бўлган 16 та нуқтани ўз ичига олади. Шу нуқталар ичида (2) функцияга максимум қиймат берувчи нуқтани топиш керак. Бунинг учун Y га ихтиёрий, масалан, 2 қиймат берамиз ва

ОАВС кўпбурчакни OKLMNF кўпбурчак билан алмаштирамиз. Бу кўпбурчак координа-талари бутун сонлардан иборат бўлган 16 та нуқтани ўз ичига олади. Шу нуқталар ичида (2) функцияга максимум қиймат берувчи нуқтани топиш керак. Бунинг учун Y га ихтиёрий, масалан, 2 қиймат берамиз ва

тўғри чизиқни ясаймиз. Бу чизиқни С(1;2) вектор йўналишида суриб бориб N (5 ;l) нуқта шу йўналишдаги энг четки нуқта эканлигини аниқлаймиз. Демак, бу нуқтанинг координаталари берилган масаланинг ечимини аниқлайди: