વિદ્યાર્થીનો ગાણિતિક અનુભવ અપૂર્ણ છે જો તેને ક્યારેય પોતાની દ્વારા શોધેલી સમસ્યા હલ કરવાની તક ન મળી હોય. - જી. પોલ્યા

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 નો નફો આપશે.

ઘણી બીજી શક્યતાઓ છે, ઉદાહરણ તરીકે, તે 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 રેખીય પ્રોગ્રામિંગ સમસ્યાઓ હલ કરવાની આલેખીય પદ્ધતિ

ધોરણ 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$ પરિબદ્ધ** હોય, તો ઉદ્દેશ્ય ફલન $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$ ના મહત્તમ અને ન્યૂનતમ મૂલ્યો છે.

(ii) જો કિસ્સામાં, શક્ય પ્રદેશ અપરિબદ્ધ હોય, તો આપણી પાસે:

4. (a) $M$ $Z$ નું મહત્તમ મૂલ્ય છે, જો $a x+b y>M$ દ્વારા નિર્ધારિત ખુલ્લા અર્ધ-સમતલનો શક્ય પ્રદેશ સાથે કોઈ સામાન્ય બિંદુ ન હોય. નહિંતર, $Z$ નું કોઈ મહત્તમ મૂલ્ય નથી.

(b) એ જ રીતે, $m$ $Z$ નું ન્યૂન