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

12.1 పరిచయం

మునుపటి తరగతుల్లో, మనం సరళ సమీకరణ వ్యవస్థలను మరియు రోజువారీ సమస్యల్లో వాటి అనువర్తనాలను చర్చించాము. 11వ తరగతిలో, మనం సరళ అసమీకరణలు మరియు రెండు చరరాశుల్లో సరళ అసమీకరణ వ్యవస్థలను మరియు గ్రాఫికల్ పద్ధతి ద్వారా వాటి సాధనలను అధ్యయనం చేసాము. గణితంలోని అనేక అనువర్తనాలు అసమీకరణ/సమీకరణ వ్యవస్థలను కలిగి ఉంటాయి. ఈ అధ్యాయంలో, మనం క్రింద ఇవ్వబడిన రకం యొక్క కొన్ని వాస్తవ జీవిత సమస్యలను పరిష్కరించడానికి సరళ అసమీకరణ/సమీకరణ వ్యవస్థలను వర్తింపజేస్తాము:

ఒక ఫర్నిచర్ డీలర్ కేవలం రెండు వస్తువులను - టేబుల్లు మరియు కుర్చీలను మాత్రమే వ్యవహరిస్తాడు. అతని వద్ద పెట్టుబడి పెట్టడానికి రూ. 50,000 మరియు గరిష్ఠంగా 60 ముక్కల నిల్వ స్థలం ఉంది. ఒక టేబుల్ ధర రూ. 2500 మరియు ఒక కుర్చీ రూ. 500. ఒక టేబుల్ అమ్మకం నుండి, అతను రూ. 250 లాభం సంపాదించగలడని మరియు ఒక కుర్చీ అమ్మకం నుండి

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

ఆప్టిమైజేషన్ సమస్యల యొక్క ఒక ప్రత్యేకమైన కానీ చాలా ముఖ్యమైన వర్గం సరళ ప్రోగ్రామింగ్ సమస్య. పైన పేర్కొన్న ఆప్టిమైజేషన్ సమస్య సరళ ప్రోగ్రామింగ్ సమస్యకు ఒక ఉదాహరణ. సరళ ప్రోగ్రామింగ్ సమస్యలు పరిశ్రమ, వాణిజ్యం, నిర్వహణ శాస్త్రం మొదలైన వాటిలో వాటి విస్తృత అనువర్తనం కారణంగా చాలా ఆసక్తిని కలిగి ఉంటాయి.

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

12.2 సరళ ప్రోగ్రామింగ్ సమస్య మరియు దాని గణిత సూత్రీకరణ

మేము ఫర్నిచర్ డీలర్ యొక్క పై ఉదాహరణతో మా చర్చను ప్రారంభిస్తాము, ఇది రెండు చరరాశులలో సమస్య యొక్క గణిత సూత్రీకరణకు దారి తీస్తుంది. ఈ ఉదాహరణలో, మనం గమనించాము

(i) డీలర్ తన డబ్బును టేబుల్లు లేదా కుర్చీలు లేదా వాటి కలయికను కొనడంలో పెట్టుబడి పెట్టగలడు. మరింతగా, విభిన్న పెట్టుబడి వ్యూహాలను అనుసరించడం ద్వారా అతను విభిన్న లాభాలను సంపాదిస్తాడు.

(ii) కొన్ని అతిముఖ్యమైన షరతులు లేదా నిరోధకాలు ఉన్నాయి, అవి, అతని పెట్టుబడి గరిష్ఠంగా రూ. 50,000 మరియు అతని నిల్వ స్థలం కూడా గరిష్ఠంగా 60 ముక్కలకు మాత్రమే పరిమితం చేయబడింది.

అతను టేబుల్లు మాత్రమే కొనాలని మరియు కుర్చీలు ఏమీ కొనకూడదని నిర్ణయించుకుంటే, అతను $50000 \div 2500$, అంటే 20 టేబుల్లు కొనగలడు. ఈ సందర్భంలో అతని లాభం రూ. $(250 \times 20)$, అంటే రూ. $\mathbf{5 0 0 0}$.

అతను కుర్చీలు మాత్రమే కొనాలని మరియు టేబుల్లు ఏమీ కొనకూడదని ఎంచుకుంటాడని అనుకుందాం. రూ. 50,000 మూలధనంతో, అతను $50000 \div 500$, అంటే 100 కుర్చీలు కొనగలడు. కానీ అతను కేవలం 60 ముక్కలను మాత్రమే నిల్వ చేయగలడు. అందువలన, అతను కేవలం 60 కుర్చీలను మాత్రమే కొనడానికి బలవంతం చేయబడతాడు, ఇది అతనికి మొత్తం లాభం రూ. $(60 \times 75)$, అంటే రూ. 4500 ను ఇస్తుంది.

ఇంకా అనేక ఇతర అవకాశాలు ఉన్నాయి, ఉదాహరణకు, అతను 10 టేబుల్లు మరియు 50 కుర్చీలను కొనడాన్ని ఎంచుకోవచ్చు, ఎందుకంటే అతను కేవలం 60 ముక్కలను మాత్రమే నిల్వ చేయగలడు. ఈ సందర్భంలో మొత్తం లాభం రూ. $(10 \times 250+50 \times 75)$, అంటే రూ. $\mathbf{6 2 5 0}$ మరియు మొదలగునవి.

అందువలన, డీలర్ తన డబ్బును వివిధ మార్గాల్లో పెట్టుబడి పెట్టగలడని మరియు విభిన్న పెట్టుబడి వ్యూహాలను అనుసరించడం ద్వారా అతను విభిన్న లాభాలను సంపాదిస్తాడని మనం కనుగొంటాము.

ఇప్పుడు సమస్య: గరిష్ఠ లాభం పొందడానికి అతను తన డబ్బును ఎలా పెట్టుబడి పెట్టాలి? ఈ ప్రశ్నకు సమాధానం ఇవ్వడానికి, సమస్యను గణితశాస్త్రపరంగా రూపొందించడానికి ప్రయత్నిద్దాం.

12.2.1 సమస్య యొక్క గణిత సూత్రీకరణ

డీలర్ కొనే టేబుల్ల సంఖ్య $x$ మరియు కుర్చీల సంఖ్య $y$ గా ఉండనివ్వండి. స్పష్టంగా, $x$ మరియు $y$ రుణాత్మకం కానివి అయి ఉండాలి, అంటే,

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (Non-negative constraints) } $$

డీలర్ అతను పెట్టుబడి పెట్టగల గరిష్ఠ మొత్తం (ఇక్కడ ఇది రూ. 50,000) మరియు అతను నిల్వ చేయగల గరిష్ఠ వస్తువుల సంఖ్య (ఇక్కడ ఇది 60) ద్వారా పరిమితం చేయబడ్డాడు.

గణితశాస్త్రపరంగా పేర్కొన్నట్లయితే,

లేదా $$ \begin{array}{rlrl} 2500 x+500 y & \leq 50,000 & \text { (investment constraint ) } \\ 5 x+y & \leq 100 & & \\ x+y & \leq 60 & & \text { (storage constraint) } \tag{4} \end{array} $$

డీలర్ తన లాభాన్ని, ఉదాహరణకు, $Z$ ను గరిష్ఠీకరించే విధంగా పెట్టుబడి పెట్టాలనుకుంటాడు, ఇది $x$ మరియు $y$ యొక్క ఫలితం వలె పేర్కొనబడింది

$Z=250 x+75 y$ (లక్ష్య ఫలితం అని పిలువబడుతుంది)

గణితశాస్త్రపరంగా, ఇవ్వబడిన సమస్యలు ఇప్పుడు తగ్గించబడ్డాయి:

గరిష్ఠీకరించు $Z=250 x+75 y$

నిరోధకాలకు లోబడి:

$$ \begin{aligned} 5 x+y & \leq 100 \\ x+y & \leq 60 \\ x \geq 0, y & \geq 0 \end{aligned} $$

కాబట్టి, మనం సరళ ఫలితం $Z$ ను రుణాత్మకం కాని చరరాశులతో సరళ అసమీకరణల సమితి ద్వారా నిర్ణయించబడిన కొన్ని షరతులకు లోబడి గరిష్ఠీకరించాలి. రుణాత్మకం కాని చరరాశులతో సరళ అసమీకరణల సమితి ద్వారా నిర్ణయించబడిన కొన్ని షరతులకు లోబడి మనం ఒక సరళ ఫలితాన్ని కనిష్ఠీకరించవలసిన కొన్ని ఇతర సమస్యలు కూడా ఉన్నాయి. అటువంటి సమస్యలను సరళ ప్రోగ్రామింగ్ సమస్యలు అంటారు.

అందువలన, ఒక సరళ ప్రోగ్రామింగ్ సమస్య అనేది అనేక చరరాశుల ($x$ మరియు $y$ అని చెప్పండి) యొక్క ఒక సరళ ఫలితం (లక్ష్య ఫలితం అని పిలువబడేది) యొక్క సరైన విలువ (గరిష్ఠ లేదా కనిష్ఠ విలువ) కనుగొనడంతో సంబంధం కలిగి ఉంటుంది, చరరాశులు రుణాత్మకం కానివి మరియు సరళ అసమీకరణల సమితిని (సరళ నిరోధకాలు అని పిలువబడేవి) సంతృప్తిపరిచే షరతులకు లోబడి ఉంటాయి. సరళ అనే పదం సమస్యలో ఉపయోగించబడిన అన్ని గణిత సంబంధాలు సరళ సంబంధాలు అని సూచిస్తుంది, అయితే ప్రోగ్రామింగ్ అనే పదం ఒక నిర్దిష్ట ప్రోగ్రామ్ లేదా చర్య యొక్క ప్రణాళికను నిర్ణయించే పద్ధతిని సూచిస్తుంది.

మేము మరింత ముందుకు వెళ్లే ముందు, మేము ఇప్పుడు కొన్ని పదాలను (పైన ఉపయోగించబడినవి) శాస్త్రీయంగా నిర్వచిస్తాము, వీటిని మేము సరళ ప్రోగ్రామింగ్ సమస్యలలో ఉపయోగిస్తాము:

లక్ష్య ఫలితం సరళ ఫలితం $Z=a x+b y$, ఇక్కడ $a, b$ స్థిరాంకాలు, దీనిని గరిష్ఠీకరించడం లేదా కనిష్ఠీకరించడం అవసరం, దీనిని సరళ లక్ష్య ఫలితం అంటారు.

పై ఉదాహరణలో, $Z=250 x+75 y$ ఒక సరళ లక్ష్య ఫలితం. చరరాశులు $x$ మరియు $y$ నిర్ణయ చరరాశులు అంటారు.

నిరోధకాలు సరళ ప్రోగ్రామింగ్ సమస్య యొక్క చరరాశులపై సరళ అసమీకరణాలు లేదా సమీకరణాలు లేదా పరిమితులను నిరోధకాలు అంటారు. షరతులు $x \geq 0, y \geq 0$ రుణాత్మకం కాని పరిమితులు అంటారు. పై ఉదాహరణలో, అసమీకరణల సమితి (1) నుండి (4) వరకు నిరోధకాలు.

ఆప్టిమైజేషన్ సమస్య ఒక సమస్య, ఇది ఒక సరళ ఫలితాన్ని (రెండు చరరాశులు $x$ మరియు $y$ అని చెప్పండి) సరళ అసమీకరణల సమితి ద్వారా నిర్ణయించబడిన కొన్ని నిరోధకాలకు లోబడి గరిష్ఠీకరించడం లేదా కనిష్ఠీకరించడం కోరుతుంది, దీనిని ఆప్టిమైజేషన్ సమస్య అంటారు. సరళ ప్రోగ్రామింగ్ సమస్యలు ఆప్టిమైజేషన్ సమస్యల యొక్క ప్రత్యేక రకం. కుర్చీలు మరియు టేబుల్లను కొనడంలో డీలర్ ద్వారా ఇచ్చిన మొత్తాన్ని పెట్టుబడి పెట్టడం యొక్క పై సమస్య ఆప్టిమైజేషన్ సమస్యకు ఒక ఉదాహరణ మరియు సరళ ప్రోగ్రామింగ్ సమస్యకు కూడా ఒక ఉదాహరణ.

సరళ ప్రోగ్రామింగ్ సమస్యకు పరిష్కారాలను ఎలా కనుగొనాలో మనం ఇప్పుడు చర్చిస్తాము. ఈ అధ్యాయంలో, మనం గ్రాఫికల్ పద్ధతితో మాత్రమే సంబంధం కలిగి ఉంటాము.

12.2.2 సరళ ప్రోగ్రామింగ్ సమస్యలను గ్రాఫికల్గా పరిష్కరించడం

11వ తరగతిలో, రెండు చరరాశులు $x$ మరియు $y$ ను కలిగి ఉన్న సరళ అసమీకరణల వ్యవస్థను గ్రాఫ్ చేయడం మరియు దాని సాధనలను గ్రాఫికల్గా కనుగొనడం మనం నేర్చుకున్నాము. సెక్షన్ 12.2 లో చర్చించబడిన టేబుల్లు మరియు కుర్చీలలో పెట్టుబడి సమస్యను మనం ఇప్పుడు గ్రాఫికల్గా పరిష్కరిద్దాం. సరళ అసమీకరణాలుగా పేర్కొనబడిన నిరోధకాలను గ్రాఫ్ చేద్దాం:

$$ \begin{align*} 5 x+y & \leq 100 \tag{1} \\ x+y & \leq 60 \tag{2} \\ x & \geq 0 \tag{3} \\ y & \geq 0 \tag{4} \end{align*} $$

ఈ వ్యవస్థ యొక్క గ్రాఫ్ (నీడపడిన ప్రాంతం) అసమీకరణాలు (1) నుండి (4) వరకు (Fig 12.1) ద్వారా నిర్ణయించబడిన అన్ని అర్ధ-తలాలకు సాధారణమైన బిందువులను కలిగి ఉంటుంది. ఈ ప్రాంతంలోని ప్రతి బిందువు టేబుల్లు మరియు కుర్చీలలో పెట్టుబడి పెట్టడానికి డీలర్కు ఉన్న సాధ్యమైన ఎంపికను సూచిస్తుంది. అందువలన, ఈ ప్రాంతాన్ని సమస్యకు సాధ్యమైన ప్రాంతం అంటారు. ఈ ప్రాంతంలోని ప్రతి బిందువును సమస్యకు సాధ్యమైన పరిష్కారం అంటారు. అందువలన, మనకు ఉంది,

Fig 12.1

సాధ్యమైన ప్రాంతం ఒక సరళ ప్రోగ్రామింగ్ సమస్య యొక్క అన్ని నిరోధకాలు సహా రుణాత్మకం కాని నిరోధకాలు $x, y \geq 0$ ద్వారా నిర్ణయించబడిన సాధారణ ప్రాంతాన్ని సమస్యకు సాధ్యమైన ప్రాంతం (లేదా పరిష్కార ప్రాంతం) అంటారు. Fig 12.1 లో, ప్రాంతం OABC (నీడపడినది) సమస్యకు సాధ్యమైన ప్రాంతం. సాధ్యమైన ప్రాంతం కాకుండా ఉన్న ప్రాంతాన్ని సాధ్యం కాని ప్రాంతం అంటారు.

సాధ్యమైన పరిష్కారాలు సాధ్యమైన ప్రాంతం లోపల మరియు దాని సరిహద్దుపై ఉన్న బిందువులు నిరోధకాల యొక్క సాధ్యమైన పరిష్కారాలను సూచిస్తాయి. Fig 12.1 లో, సాధ్యమైన ప్రాంతం $OABC$ లోపల మరియు దాని సరిహద్దుపై ఉన్న ప్రతి బిందువు సమస్యకు సాధ్యమైన పరిష్కారాన్ని సూచిస్తుంది. ఉదాహరణకు, బిందువు $(10,50)$ సమస్య యొక్క సాధ్యమైన పరిష్కారం మరియు బిందువులు $(0,60),(20,0)$ మొదలైనవి కూడా అలానే ఉంటాయి.

సాధ్యమైన ప్రాంతం వెలుపల ఉన్న ఏదైనా బిందువును సాధ్యం కాని పరిష్కారం అంటారు. ఉదాహరణకు, బిందువు $(25,40)$ సమస్య యొక్క సాధ్యం కాని పరిష్కారం.

సరైన (సాధ్యమైన) పరిష్కారం: లక్ష్య ఫలితం యొక్క సరైన విలువ (గరిష్ఠ లేదా కనిష్ఠ) ను ఇచ్చే సాధ్యమైన ప్రాంతంలోని ఏదైనా బిందువును సరైన పరిష్కారం అంటారు.

ఇప్పుడు, సాధ్యమైన ప్రాంతం $OABC$ లోని ప్రతి బిందువు (1) నుండి (4) వరకు ఇవ్వబడిన అన్ని నిరోధకాలను సంతృప్తిపరుస్తుందని మనం చూస్తాము, మరియు అనంతమైన బిందువులు ఉన్నందున, లక్ష్య ఫలితం $Z=250 x+75 y$ యొక్క గరిష్ఠ విలువను ఇచ్చే బిందువును ఎలా కనుగొనాలో స్పష్టంగా లేదు. ఈ పరిస్థితిని నిర్వహించడానికి, మేము సరళ ప్రోగ్రామింగ్ సమస్యలను పరిష్కరించడంలో ప్రాథమికమైన క్రింది సిద్ధాంతాలను ఉపయోగిస్తాము. ఈ సిద్ధాంతాల రుజువులు పుస్తకం యొక్క పరిధికి మించినవి.

సిద్ధాంతం 1 $R$ సరళ ప్రోగ్రామింగ్ సమస్యకు సాధ్యమైన ప్రాంతం (కుంభాకార బహుభుజి) గా ఉండనివ్వండి మరియు $Z=a x+b y$ లక్ష్య ఫలితం గా ఉండనివ్వండి. $Z$ కు సరైన విలువ (గరిష్ఠ లేదా కనిష్ఠ) ఉన్నప్పుడు, ఇక్కడ చరరాశులు $x$ మరియు $y$ సరళ అసమీకరణల ద్వారా వివరించబడిన నిరోధకాలకు లోబడి ఉంటాయి, ఈ సరైన విలువ సాధ్యమైన ప్రాంతం యొక్క ఒక మూల బిందువు* (శీర్షం) వద్ద సంభవించాలి.

సిద్ధాంతం 2 $R$ సరళ ప్రోగ్రామింగ్ సమస్యకు సాధ్యమైన ప్రాంతం గా ఉండనివ్వండి, మరియు $Z=a x+b y$ లక్ష్య ఫలితం గా ఉండనివ్వండి. $R$ పరిమితమైతే**, అప్పుడు లక్ష్య ఫలితం $Z$ కు $R$ పై గరిష్ఠ మరియు కనిష్ఠ విలువ రెండూ ఉంటాయి మరియు వాటిలో ప్రతి ఒక్కటి R యొక్క ఒక మూల బిందువు (శీర్షం) వద్ద సంభవిస్తాయి.

వ్యాఖ్య $R$ అపరిమితమైతే, అప్పుడు లక్ష్య ఫలితం యొక్క గరిష్ఠ లేదా కనిష్ఠ విలువ ఉండకపోవచ్చు. అయినప్పటికీ, అది ఉన్నట్లయితే, అది R యొక్క ఒక మూల బిందువు వద్ద సంభవించాలి. (సిద్ధాంతం 1 ద్వారా).

పై ఉదాహరణలో, పరిమిత (సాధ్యమైన) ప్రాంతం యొక్క మూల బిందువులు (శీర్షాలు): $O, A, B$ మరియు $C$ మరియు వాటి నిరూపకాలను వరుసగా $(0,0),(20,0),(10,50)$ మరియు $(0,60)$ గా కనుగొనడం సులభం. ఇప్పుడు ఈ బిందువుల వద్ద $Z$ విలువలను గణిద్దాం.

మనకు ఉంది

• సాధ్యమైన ప్రాంతం యొక్క ఒక మూల బిందువు అనేది ప్రాంతంలో ఉన్న ఒక బిందువు, ఇది రెండు సరిహద్దు రేఖల ఖండన బిందువు.

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

డీలర్కు గరిష్ఠ లాభం పెట్టుబడి వ్యూహం $(10,50)$ నుండి వస్తుందని మనం గమనించాము, అంటే 10 టేబుల్లు మరియు 50 కుర్చీలు కొనడం.

సరళ ప్రోగ్రామింగ్ సమస్యను పరిష్కరించే ఈ పద్ధతిని మూల బిందువు పద్ధతి అని సూచిస్తారు. ఈ పద్ధతి క్రింది దశలను కలిగి ఉంటుంది:

1. సరళ ప్రోగ్రామింగ్ సమస్య యొక్క సాధ్యమైన ప్రాంతాన్ని కనుగొనండి మరియు దాని మూల బిందువులను (శీర్షాలు) పరిశీలన ద్వారా లేదా ఆ బిందువు వద్ద ఖండించే రెండు రేఖల సమీకరణాలను పరిష్కరించడం ద్వారా నిర్ణయించండి.

2. ప్రతి మూల బిందువు వద్ద లక్ష్య ఫలితం $Z=a x+b y$ ను మూల్యాంకనం చేయండి. ఈ బిందువుల యొక్క అతిపెద్ద మరియు చిన్న విలువలను వరుసగా $\mathbf{M}$ మరియు $m$ ద్వారా సూచించండి.

3. (i) సాధ్యమైన ప్రాంతం పరిమితమైతే, $M$ మరియు $m$ $Z$ యొక్క గరిష్ఠ మరియు కన