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

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 шаҳарлар фақат бир маршрут ёрдами билан боғланган деб фараз қиламиз).

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

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

б) Оптимал жойлаштириш масаласи.

б) Оптимал жойлаштириш масаласи.

Фараз қилайлик, m та A1, A2, … , Am пунктларда бир хил маҳсулотлар ишлаб чиқарувчи корхоналарни жойлаштириш керак бўлсин. Ҳар бир корхонанинг ишлаб чиқариш қувватини билдирувчи xi, (i = 1,2,...,m) бутун сонли қийматларни қабул қилади. Ҳар бир Ai пунктда маҳсулот ишлаб чиқариш учун сарф қилинган ҳаражат ишлаб чиқарилган маҳсулот миқдорига боғлиқ бўлиб, у fi(xi) функция орқали ифодаланади. Соддалик учун бу функцияни чизиқли деб қабул қиламиз, яъни

fi(xi)=cixi

Бундан ташқари n та пунктда бу маҳсулот истеъмол қилинади. Ҳар бир истеъмол қилувчи пунктнинг маҳсулотга бўлган талаби маълум ва улар b1, b2,…,bn бирликларни ташкил қилади деб фараз қиламиз. Ҳар бир Ai ишлаб чиқарувчи пункт ҳар бир Bj истеъмол қилувчи пункт билан боғланган бўлиб йўл харажатлари матрицаси C=(cij) дан иборат бўлсин. Ai пунктдан Bj пунктга юбориладиган маҳсулот миқдорини xij билан белгилаймиз.

Бундан ташқари n та пунктда бу маҳсулот истеъмол қилинади. Ҳар бир истеъмол қилувчи пунктнинг маҳсулотга бўлган талаби маълум ва улар b1, b2,…,bn бирликларни ташкил қилади деб фараз қиламиз. Ҳар бир Ai ишлаб чиқарувчи пункт ҳар бир Bj истеъмол қилувчи пункт билан боғланган бўлиб йўл харажатлари матрицаси C=(cij) дан иборат бўлсин. Ai пунктдан Bj пунктга юбориладиган маҳсулот миқдорини xij билан белгилаймиз.

У ҳолда масаланинг математик модели қуйидаги кўринишда ифодаланади:

У ҳолда масаланинг математик модели қуйидаги кўринишда ифодаланади: