Հոմորի մեթոդը: Ամբողջական ծրագրավորման խնդիրները լուծելու համար

Տնտեսական բնույթի խնդիրների խնդիրները, պլանավորման խնդիրները եւ նույնիսկ մարդկային կյանքի գործունեության այլ ոլորտներից հարցերի լուծումը կապված է ամբողջ թվերին վերաբերող փոփոխականների հետ: Վերլուծության եւ լուծման օպտիմալ մեթոդների որոնման արդյունքում հայտնվեց ծայրահեղ խնդիրների հայեցակարգը: Դրա առանձնահատկությունները վերը նշված առանձնահատկությունն են, որ վերցնեն ամբողջական արժեք, եւ խնդիրն ինքնին վերաբերվում է մաթեմատիկայում որպես ամբողջական ծրագրավորում:

Առանձնահատուկ արժեքներ ունեցող փոփոխականների հետ խնդիրների օգտագործման հիմնական ուղղությունը օպտիմալացում է: Մի մեթոդ, որն օգտագործում է ամբողջական գծային ծրագրավորում, կոչվում է նաեւ կրկնօրինակման մեթոդ:

Homori- ի մեթոդը ստացել է իր անունը մաթեմատիկոսի անունով, որը 1957-1958թթ. Մշակվել է ալգորիթմ, որը դեռեւս լայնորեն օգտագործվում է ամբողջական գծային ծրագրավորման խնդիրները լուծելու համար: Լրիվ ծրագրավորման պրոբլեմի կրոնական ձեւը հնարավորություն է տալիս ամբողջովին բացահայտել այս մեթոդի առավելությունները:

Գոմորի մեթոդը գծային ծրագրավորման համար զգալիորեն բարդացնում է օպտիմալ արժեքներ գտնելու խնդիրը: Ի վերջո, ամբողջը հիմնական պայմանն է, բացի խնդրի բոլոր պարամետրերից: Խնդիրը հազվադեպ չէ, երբ ունենալով հնարավոր (լիարժեք) պլան, եթե օբյեկտիվ գործառույթը թույլատրելի սահմանների վրա խոչընդոտներ ունի , լուծումը չի հասնում առավելագույնի: Դա պայմանավորված է ամբողջական լուծումների բացակայությամբ: Առանց այդ նույն վիճակի, որպես կանոն, համապատասխան վեկտորը լուծման տեսքով է:

Սխալների լուծման թվային ալգորիթմները հիմնավորելու համար անհրաժեշտ է լրացնել լրացուցիչ լրացուցիչ պայմաններ:

Գոմորի մեթոդի կիրառմամբ, պրոբլեմային պլանների փաթեթը սովորաբար համարվում է սահմանափակված այսպես կոչված լուծումների բազմազանություն: Դրանից ելնելով `հետեւում է, որ տվյալ խնդրի բոլոր ինտեգրալային պլանների շարքը ունի վերջնական արժեք:

Բացի այդ, գործառույթի ամբողջականությունը ապահովելու համար ենթադրվում է, որ գործակիցների արժեքները նույնպես ամբողջական են: Չնայած նման պայմանների ծանրությանը, նրանք կարող են մի քիչ ուղարկվել:

Homori- ի մեթոդը, ըստ էության, ներառում է խոչընդոտների կառուցումը, որոնք կտրամադրեն ոչ ամբողջական թվացող որոշումներ: Այս պարագայում, ամբողջական արժեքի պլանի որեւէ լուծման բացակայում չկա:

Խնդրի լուծման ալգորիթմը ներառում է պարզ տարբերակով հարմար տարբերակները `առանց հաշվի նստելու ամբողջական պայմանները: Եթե օպտիմալ պլանի բոլոր բաղադրիչներում կան ամբողջական լուծումներ, ապա կարող ենք ենթադրել, որ ամբողջական ծրագրավորման նպատակն է հասնել: Հնարավոր է, որ խնդրի անճանաչելիությունը կհաստատվի, ուստի մենք ապացուցում ենք, որ ամբողջական ծրագրավորման խնդիրը լուծում չունի:

Տարբերակ հնարավոր է, երբ օպտիմալ լուծման բաղադրիչներում առկա են ոչ թվային համարներ: Այս դեպքում նոր սահմանափակում է ավելացվում խնդիրի բոլոր խոչընդոտները: Նոր սահմանափակումն առանձնանում է մի շարք հատկությունների առկայությամբ: Նախեւառաջ, պետք է լինի գծային, այն պետք է կտրված լինի ոչ լիարժեք պլանը, գտնված օպտիմալ հավաքածուից: Ոչ մի ամբողջական լուծում չպետք է կորչվի, կտրված լինի:

Սահմանափակումը կառուցելիս պետք է ընտրեք օպտիմալ պլանի բաղադրիչը `ամենամեծ մասնաբաժինը: Սա այս սահմանափակումն է, որը կավելացվի առկա simplex սեղանին:

Մենք գտնում ենք, որ ստացված խնդրի լուծումը սովորական սիմպլեքս վերափոխումների միջոցով է: Մենք ստուգում ենք խնդրի լուծումը ամբողջական օպտիմալ պլանի առկայության դեպքում, եթե պայմանը բավարարված է, ապա խնդիրը լուծվում է: Եթե կրկին արդյունքը ստացվի ոչ ամբողջական լուծումների առկայությամբ, ապա մենք լրացուցիչ սահմանափակում ենք ներկայացնում, եւ մենք կրկնում ենք հաշվարկների գործընթացը:

Ելնելով վերջնական քանակի կրկնողություններից, մենք ստանում ենք օպտիմալ պլան, խնդրի առաջ ամբողջ ծրագրի առաջ, կամ ապացուցում խնդրի լուծելիությունը: