హోమోరీ విధానం. పూర్ణ ప్రోగ్రామింగ్ సమస్యలను పరిష్కరించడం

ఒక ఆర్థిక స్వభావం, సమస్యల ప్రణాళిక మరియు మానవ జీవిత కార్యకలాపాల యొక్క ఇతర రంగాలకు చెందిన సమస్యల పరిష్కారం కూడా మొత్తం సంఖ్యలను సూచించే వేరియబుల్స్తో సంబంధం కలిగి ఉంటుంది. వారి విశ్లేషణ మరియు పరిష్కారం యొక్క సరైన పద్ధతుల కోసం శోధన ఫలితంగా, ఒక extremal సమస్య భావన కనిపించింది. దీని లక్షణాలు పూర్ణాంక విలువను తీసుకోవటానికి పైన ఉన్న విశేషణం, మరియు ఈ సమస్యను గణితంలో పూర్ణ ప్రోగ్రామింగ్గా పరిగణిస్తారు.

పూర్ణాంక విలువలను తీసుకునే వేరియబుల్స్తో పనులు ఉపయోగించి ప్రధాన దిశలో ఆప్టిమైజేషన్ ఉంది. పూర్ణాంక సరళ ప్రోగ్రామింగ్ను ఉపయోగించే పద్ధతి కూడా క్లిప్పింగ్ పద్ధతిగా పిలువబడుతుంది.

1957-1958లో మొట్టమొదటిగా రూపొందించిన గణిత శాస్త్రవేత్త పేరు హోమోరీ పద్ధతికి పేరు వచ్చింది, ఇది అల్గోరిథం, ఇది పూర్ణాంక సరళ ప్రోగ్రామింగ్ సమస్యలను పరిష్కరించడానికి విస్తృతంగా ఉపయోగించబడుతుంది. పూర్ణాంక ప్రోగ్రామింగ్ సమస్య యొక్క నియమావళి రూపం ఈ పద్ధతి యొక్క ప్రయోజనాలను పూర్తిగా కనుగొనగలదు.

సరళ ప్రోగ్రామింగ్ కోసం గోమోరి పద్ధతి గణనీయంగా సరైన విలువలను కనుగొనే సమస్యను క్లిష్టతరం చేస్తుంది. అన్ని తరువాత, సమస్య యొక్క అన్ని పారామితులు పాటు, పూర్ణాంకం ప్రధాన పరిస్థితి. ఒక పనికిమాలిన (పూర్ణాంక) పథం ఉన్నప్పుడు, లక్ష్యపు పనితీరు ఒక అంగీకారయోగ్యమైన సమితిపై అడ్డంకులు ఉన్నట్లయితే, పరిష్కారం గరిష్ట స్థాయికి చేరుకోకపోయినా, సమస్యకు ఇది అసాధారణం కాదు. పూర్ణాంక పరిష్కారాలు లేనందున ఇది. ఇదే పరిస్థితి లేకుండా, నియమం వలె, సరైన వెక్టర్ ఒక పరిష్కారం రూపంలో ఉంటుంది.

సమస్యలను పరిష్కరించడంలో సంఖ్యా అల్గోరిథంలను నిరూపించడానికి, వివిధ అదనపు పరిస్థితులను సూపర్మిస్ చేయవలసిన అవసరం ఉంది.

గోమోరి పద్ధతిని ఉపయోగించి, సమస్యల ప్రణాళికల సెట్ సాధారణంగా పరిష్కారాల యొక్క పాలిటోప్ అని పిలవబడే పరిమితంగా పరిగణించబడుతుంది. దీని నుండి కొనసాగుతుంటే, సమస్యలో ఉన్న అన్ని సమగ్ర ప్రణాళికల సమితి పరిమిత విలువను కలిగి ఉంటుంది.

అలాగే, ఒక ఫంక్షన్ యొక్క సమగ్రతను నిర్ధారించడానికి, గుణకం విలువలు కూడా పూర్ణాంకాలుగా ఉంటుందని భావించబడుతుంది. ఇటువంటి పరిస్థితుల యొక్క తీవ్రత ఉన్నప్పటికీ, వారు ఒక బిట్ పంపవచ్చు.

వాస్తవానికి, హోమోరీ పద్ధతిలో, పూర్ణాంకం లేని నిర్ణయాలు తగ్గించే అడ్డంకులను నిర్మిస్తుంది. ఈ సందర్భంలో, పూర్ణ-విలువైన ప్రణాళికకు ఎలాంటి పరిష్కారం ఏమీ ఉండదు.

సమస్య పరిష్కారం కోసం అల్గోరిథం, సంక్లిష్ట పద్దతి ద్వారా సరిఅయిన వైవిధ్యాలను గుర్తించి, సంపూర్ణ పరిస్థితులను పరిగణనలోకి తీసుకోకుండా ఉంటుంది. సరైన పథకం యొక్క అన్ని భాగాలలో పూర్ణాంకాలకు సంబంధించిన పరిష్కారాలు ఉంటే, పూర్ణాంక ప్రోగ్రామింగ్ యొక్క లక్ష్యం సాధించబడిందని మేము అనుకోవచ్చు. సమస్య యొక్క undecidability వెల్లడించగల అవకాశం ఉంది, కాబట్టి మేము పూర్ణాంక ప్రోగ్రామింగ్ సమస్య పరిష్కారం లేదు అని రుజువు పొందండి.

సరైన పరిష్కారం యొక్క భాగాలలో పూర్ణసంఖ్య కాని సంఖ్యలు ఉన్నప్పుడు ఒక వైవిధ్యం సాధ్యపడుతుంది. ఈ సందర్భంలో, పని యొక్క అన్ని అడ్డంకులకు ఒక క్రొత్త పరిమితి జోడించబడుతుంది. ఒక క్రొత్త పరిమితి అనేక లక్షణాల ఉనికిని కలిగి ఉంటుంది. అన్ని మొదటి, ఇది సరళంగా ఉండాలి, అది కనిపించని సరైన సెట్ నుండి కాని పూర్ణాంక ప్రణాళికను కత్తిరించాలి. ఏ పూర్ణాంక పరిష్కారం కోల్పోకూడదు, కత్తిరించాలి.

పరిమితిని నిర్మిస్తున్నప్పుడు, మీరు సరైన పథకం యొక్క భాగాలను అతిపెద్ద భిన్నమైన భాగాన్ని ఎంచుకోవాలి. ఇది ప్రస్తుత నియంత్రణ పట్టికకు జోడించబడే ఈ పరిమితి.

సాధారణ సరళ పరివర్తనలు ఉపయోగించి పొందిన సమస్య పరిష్కారం దొరుకుతుంది. పరిస్థితి పూర్ణాంక ఆప్టిమల్ ప్లాన్ ఉండటం కోసం సమస్య పరిష్కారం తనిఖీ, పరిస్థితి సంతృప్తి ఉంటే, అప్పుడు సమస్య పరిష్కరించబడుతుంది. పూర్ణాంక పరిష్కారాల ఉనికితో ఫలితాన్ని పొందినట్లయితే, మేము అదనపు పరిమితిని పరిచయం చేస్తాము మరియు మేము లెక్కల ప్రక్రియను పునరావృతం చేస్తాము.

పునరావృతమయ్యే పరిమిత సంఖ్యలో పాల్గొన్న తర్వాత, పూర్ణాంక ప్రోగ్రామింగ్కు ముందు ఎదురయ్యే సమస్య కోసం మేము సరైన ప్రణాళికను పొందడం లేదా సమస్య యొక్క అన్యోల్బబిలిటీ నిరూపించాము.