ഒരു പ്രശ്നം സ്വയം കണ്ടുപിടിച്ച് പരിഹരിക്കാനുള്ള അവസരം ഒരു വിദ്യാർത്ഥിക്ക് ലഭിച്ചിട്ടില്ലെങ്കിൽ അയാളുടെ ഗണിത അനുഭവം അപൂർണ്ണമാണ്. - ജി. പോളിയ

12.1 ആമുഖം

മുമ്പത്തെ ക്ലാസുകളിൽ, നാം രേഖീയ സമവാക്യങ്ങളുടെ സംവിധാനങ്ങളും അവയുടെ ദൈനംദിന പ്രശ്നങ്ങളിലെ പ്രയോഗങ്ങളും ചർച്ച ചെയ്തിട്ടുണ്ട്. ക്ലാസ് XI-ൽ, നാം രേഖീയ അസമത്വങ്ങളും രണ്ട് ചരങ്ങളിലുള്ള രേഖീയ അസമത്വ സംവിധാനങ്ങളും അവയുടെ ഗ്രാഫിക് രീതിയിലുള്ള പരിഹാരങ്ങളും പഠിച്ചിട്ടുണ്ട്. ഗണിതശാസ്ത്രത്തിലെ പല പ്രയോഗങ്ങളിലും അസമത്വങ്ങളുടെ/സമവാക്യങ്ങളുടെ സംവിധാനങ്ങൾ ഉൾപ്പെടുന്നു. ഈ അദ്ധ്യായത്തിൽ, രേഖീയ അസമത്വങ്ങളുടെ/സമവാക്യങ്ങളുടെ സംവിധാനങ്ങൾ ചുവടെ നൽകിയിരിക്കുന്ന തരത്തിലുള്ള ചില യാഥാർത്ഥ ജീവിത പ്രശ്നങ്ങൾ പരിഹരിക്കാൻ ഉപയോഗിക്കും:

ഒരു ഫർണിച്ചർ ഡീലർ രണ്ട് ഇനങ്ങൾ മാത്രം വിൽക്കുന്നു - മേശകളും കസേരകളും. അദ്ദേഹത്തിന് നിക്ഷേപിക്കാൻ 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 രൂപ.

മറ്റ് പല സാധ്യതകളും ഉണ്ട്, ഉദാഹരണത്തിന്, അദ്ദേഹത്തിന് 60 കഷണങ്ങൾ മാത്രമേ സൂക്ഷിക്കാൻ കഴിയുകയുള്ളൂ എന്നതിനാൽ, 10 മേശകളും 50 കസേരകളും വാങ്ങാൻ അദ്ദേഹം തിരഞ്ഞെടുക്കാം. ഈ സാഹചര്യത്തിൽ മൊത്തം ലാഭം $(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 രേഖീയ പ്രോഗ്രാമിംഗ് പ്രശ്നങ്ങൾ പരിഹരിക്കുന്നതിനുള്ള ഗ്രാഫിക് രീതി

ക്ലാസ് XI-ൽ, രണ്ട് ചരങ്ങൾ $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) വരെ നിർണ്ണയിക്കുന്ന എല്ലാ അർദ്ധ തലങ്ങൾക്കും പൊതുവായ പോയിന്റുകൾ ഉൾക്കൊള്ളുന്നു (ചിത്രം 12.1). ഈ പ്രദേശത്തിലെ ഓരോ പോയിന്റും മേശകളിലും കസേരകളിലും നിക്ഷേപിക്കുന്നതിന് ഡീലറിന് ലഭ്യമായ ഒരു സാധ്യമായ തിരഞ്ഞെടുപ്പിനെ പ്രതിനിധീകരിക്കുന്നു. അതിനാൽ, ഈ പ്രദേശത്തെ പ്രശ്നത്തിനുള്ള സാധ്യമായ പ്രദേശം എന്ന് വിളിക്കുന്നു. ഈ പ്രദേശത്തിലെ ഓരോ പോയിന്റിനെയും പ്രശ്നത്തിനുള്ള ഒരു സാധ്യമായ പരിഹാരം എന്ന് വിളിക്കുന്നു. അങ്ങനെ, നമുക്കുണ്ട്,

ചിത്രം 12.1

സാധ്യമായ പ്രദേശം ഒരു രേഖീയ പ്രോഗ്രാമിംഗ് പ്രശ്നത്തിന്റെ എല്ലാ നിയന്ത്രണങ്ങളും ഉൾപ്പെടെ നോൺ-നെഗറ്റീവ് നിയന്ത്രണങ്ങൾ $x, y \geq 0$ നിർണ്ണയിക്കുന്ന പൊതു പ്രദേശത്തെ പ്രശ്നത്തിനുള്ള സാധ്യമായ പ്രദേശം (അല്ലെങ്കിൽ പരിഹാര പ്രദേശം) എന്ന് വിളിക്കുന്നു. ചിത്രം 12.1-ൽ, OABC പ്രദേശം (നിറം പൂശിയത്) പ്രശ്നത്തിനുള്ള സാധ്യമായ പ്രദേശമാണ്. സാധ്യമായ പ്രദേശം ഒഴികെയുള്ള പ്രദേശത്തെ സാധ്യമല്ലാത്ത പ്രദേശം എന്ന് വിളിക്കുന്നു.

സാധ്യമായ പരിഹാരങ്ങൾ സാധ്യമായ പ്രദേശത്തിനുള്ളിലും അതിന്റെ അതിർത്തിയിലുമുള്ള പോയിന്റുകൾ നിയന്ത്രണങ്ങളുടെ സാധ്യമായ പരിഹാരങ്ങളെ പ്രതിനിധീകരിക്കുന്നു. ചിത്രം 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$ ബൗണ്ടഡ്** ആണെങ്കിൽ, ഉദ്ദേശ്യ ഫംഗ്ഷൻ ⟦