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

11-МАВЗУ. БУТУН СОНЛИ ДАСТУРЛАШ

РЕЖА:

1. Иқтисодий масалалар.

2. Бутун сонли дастурлаш масаласининг қўйилиши, турлари ва геометрик талқини.

Ўзгарувчиларига бутун сонли бўлишлик шарти қўйилган чизиқли дастурлаш масалалари катта аҳамиятга эгадир. Бундай масалалар бутун сонли дастурлаш масалалари деб аталади. Бутун сонли дастурлаш масалаларига сайёҳ ҳақидаги масала, оптимал жадвал тузиш, рационал бичиш, транспорт воситаларини маршрутларга оптимал тақсимлаш, бўлинмайдиган махсулотлар ишлаб чиқарувчи корхонанинг ишини оптимал режалаштириш масалалари мисол бўла олади. Бу масалаларнинг баъзилари билан бугунги маърузамизда танишамиз.

Ўзгарувчиларига бутун сонли бўлишлик шарти қўйилган чизиқли дастурлаш масалалари катта аҳамиятга эгадир. Бундай масалалар бутун сонли дастурлаш масалалари деб аталади. Бутун сонли дастурлаш масалаларига сайёҳ ҳақидаги масала, оптимал жадвал тузиш, рационал бичиш, транспорт воситаларини маршрутларга оптимал тақсимлаш, бўлинмайдиган махсулотлар ишлаб чиқарувчи корхонанинг ишини оптимал режалаштириш масалалари мисол бўла олади. Бу масалаларнинг баъзилари билан бугунги маърузамизда танишамиз.

1. Иқтисодий масалалар.

1. Иқтисодий масалалар.

a. Сайёҳ ҳақидаги масала.

Фараз қилайлик, P0 шаҳарда яшовчи сайёҳ n та P1,P2,…,Pn шаҳарларда бир мартадан бўлиб, минимал вақт ичида P0 шаҳарга қайтиб келиши керак бўлсин. Бу масаланинг математик моделини тузиш учун савдогарнинг Pi шаҳардан Pj шаҳарга бориши учун сарф қилган вақтини tij ( i=1,2,…,n ; j=1,…,n) билан ҳамда унинг ҳар бир Pi шаҳардан Pj шаҳарга бориш вариантининг характеристикасини xij билан белгилаймиз. Агар савдогар Pi шаҳардан Pj га борса, xij=1, бормаса xij=0 бўлади (Соддалик учун Pi ва Pj шаҳарлар фақат бир маршрут ёрдами билан боғланган деб фараз қиламиз).

Юқоридаги масаланинг математик модели қуйидаги кўринишда бўлади:

Юқоридаги масаланинг математик модели қуйидаги кўринишда бўлади: