Бутун сонли программалаштириш

12-мавзу. Бутун сонли дастурлаш масаласи

• Мавзу режаси:
• 1. Бутун сонли дастур-
• лаш масалаларини ечиш
• методлари
• 2. Гомори усули
• 3. Кесувчи тенглама

МАСАЛАНИНГ ҚЎЙИЛИШИ

• Ўзгарувчиларга бутун сон
• бўлиш шарти қўйилган
• чизиқли дастурлаш
• масалалари катта амалий
• аҳамиятга эга.

• Чизиқли дастурлаш маса-
• ласининг математик моде-
• лидаги ўзгарувчиларнинг
• ҳаммасига ёки маълум
• қисмига бутун сон бўлиш
• шарти қўйилса, бутун
• сонли чизиқли дастурлаш
• масаласи ҳосил бўлади.

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

БСДМга оптимал жадвал

• БСДМга оптимал жадвал
• тузиш, рационал бичиш,
• транспорт воситаларини
• маршрутларга оптимал
• тақсимлаш, бўлинмайдиган
• маҳсулот ишлаб чиқарувчи
• корхонанинг ишини опти-
• мал режалаштириш масала-
• лари киради.

• ТЎЛИҚ ВА
• ҚИСМАН БУТУН
• СОНЛИ
• ДАСТУРЛАШ
• МАСАЛАСИ

• Бутун сонли дастурлаш
• масалаларидаги номаълум-
• ларнинг ҳаммаси учун бу-
• тун бўлиш шарти қўйилса,
• тўлиқ бутун сонли дастур
• лаш масаласи дейилади.

• Агар уларнинг маълум
• бир қисми учунгина
• бутун бўлиш шарти
• қўйилса, қисман бутун
• сонли дастурлаш
• масалалари деб аталади.

БУТУН СОНЛИ ЧИЗИҚЛИ

• БУТУН СОНЛИ ЧИЗИҚЛИ
• ДАСТУРЛАШ
• МАСАЛАСИНИНГ УМУМИЙ
• КЎРИНИШИ

• Таъриф. а сонининг бутун
• қисми деб, шу сондан
• катта бўлмаган энг катта
• бутун сонга айтилади ва
• [а] деб белгиланади.

Таъриф. а сонининг

• Таъриф. а сонининг
• каср қисми деб, а- [а]
• сонга айтилади ва
• {а} деб белгиланади.
• Таърифга кўра ҳар қан-
• дай соннинг каср қисми
• номанфий бўлади.

• Хулоса. Ҳарқандай
• сон шу соннинг бутун
• ва каср қисмлари
• йиғиндиси кўриниши
• да ёзилиши мумкин.

ЧДМларининг бутун ечим ларини топишда аввал ЧДМ ўзгарувчилари ажратилган ЧДМ га келтирилади

Бутун сон бўлиши керак бўлган номаълум учун кесувчи тенглама ёзамиз. Агар бундай номаълумлар кўп бўлса, уларнинг бирортаси учун кесувчи тенглама ёзилади.

КЕСУВЧИ ТЕНГЛАМА ТУЗИШ

• КЕСУВЧИ ТЕНГЛАМА ТУЗИШ
• 1. Кесувчи тенгламанинг озод
• хади танланган тенгламанинг
• озод хадидан унинг бутун
• қисмидан катта бўлмаган
• бутун сонни айириш билан
• ҳосил қилинади;

• 2. Кесувчи тенгламанинг
• ўзгарувчиларининг коэффи-
• циентлари танланган тенгла –
• мадаги мос коэффициент-
• лардан унга яқин бўлган ва
• ўзидан кичик бўлмаган бутун
• сонни айрилиб тузилади;

• 3. Кесувчи ўзгарувчи
• қўшилади (у систе-
• мадаги ўзгарувчилар
• дан фарқли).

Кесувчи тенглама ёрдами

• Кесувчи тенглама ёрдами
• да берилган масала ечим-
• ларидан ташкил топган
• К қавариқ тўпламнинг
• каср сонли ечимларини
• ўз ичига олган қисми кесиб борилади.

Кесиш жараёни

• Кесиш жараёни
• К тўпламнинг фақат бутун
• сонли ечимларини ўз ичига
• олган қисми топилгунча ёки бундай қисм мавжуд эмаслиги аниқлангунча такрорланади.

ЧИЗИҚЛИ

• ЧИЗИҚЛИ
• ДАСТУРЛАШ
• МАСАЛАСИ-
• ДАН ФАРҚИ

Ўзгарувчиларга қўйилган

• Ўзгарувчиларга қўйилган
• бутун сон бўлиш шарти билан
• фарқ қилади. Бу шартлар
• БСДМни ечиш жараёнини
• қийинлаштиради. Натижада
• ЧДМларини ечишга қўллани-
• ладиган усулларни БСДМ
• ларига қўллаш мумкин бўл-
• май қолади.

• БУТУН СОНЛИ ДАСТУРЛАШ
• МАСАЛАЛАРИНИ
• ЕЧИШ МЕТОДЛАРИ

• Кесувчи
• текисликлар
• методи

• Тармоқлар
• ва чегаралар
• методи

• КЕСУВЧИ ТЕКИСЛИКЛАР МЕТОДИГА
• ТЕГИШЛИ БЎЛГАН МЕТОДЛАР

• ЦИКЛИК
• МЕТОД

• ТЎЛА
• БУТУН
• СОНЛИ
• МЕТОД

• ТЎҒРИ
• МЕТОД

• ГОМОРИ
• УСУЛИ

• БСДМ ларини ечиш учун
• кўплаб усуллар яратилган,
• улардан Америка олими
• Р.Гомори яратган усул
• оптимал ечимни берувчи
• усул ҳисобланади.

• ГОМОРИ
• УСУЛИНИНГ
• ҒОЯСИ

Усулнинг ғояси берилган

• Усулнинг ғояси берилган
• БСДМ сида номаълумлар-
• нинг бутун бўлиш шартига
• эътибор бермасдан, оддиий
• чизиқли дастурлаш масала
• си сифатида симплекс усул
• дан фойдаланиб ечишдан
• иборат.

• Бутун сонли ечим мавжуд эмас

Агар чегаравий шартлар системаси

• Агар чегаравий шартлар системаси
• даги тенгламалардан ҳеч бўлмаса
• бирининг озод хади каср сон бўлиб,
• ўзгарувчиларнинг барча коэффици-
• ентлари бутун сон бўлса масала бу-
• тун сонли ечимга эга бўлмайди.
• Масаланинг чегаравий шартлар сис-
• темаси биргалашмаган ҳолда ҳам
• берилган бутун сонли дастурлаш
• масаласи ечимга эга бўлмайди.

ЭЪТИБОРИНГИЗ УЧУН РАХМАТ!!!

• ЭЪТИБОРИНГИЗ УЧУН РАХМАТ!!!