11.4. ડ્યુઅલ સિમ્પલેક્સ પદ્ધતિ
તે અગાઉના વિભાગોના પરિણામો પરથી અનુસરે છે કે મૂળ સમસ્યાનો ઉકેલ મેળવવા માટે, અમે દ્વિ એક તરફ જઈ શકીએ છીએ અને, તેની શ્રેષ્ઠ ડિઝાઇનના અંદાજનો ઉપયોગ કરીને, મૂળ સમસ્યાનો શ્રેષ્ઠ ઉકેલ નક્કી કરી શકીએ છીએ.
દ્વિ સમસ્યામાં સંક્રમણ જરૂરી નથી, કારણ કે જો આપણે પ્રથમ સિમ્પ્લેક્સ ટેબ્લોને એકમ વધારાના આધાર સાથે ધ્યાનમાં લઈએ, તો તે જોવાનું સરળ છે કે કૉલમમાં મૂળ સમસ્યા છે, અને દ્વિ સમસ્યા પંક્તિઓમાં લખેલી છે.
બતાવ્યા પ્રમાણે, કોઈપણ પુનરાવર્તન પર સીધી સમસ્યા હલ કરતી વખતે, તફાવત, એટલે કે તીવ્રતા - ચલ સાથે ગુણાંક, દ્વિ સમસ્યાના અનુરૂપ અવરોધની જમણી અને ડાબી બાજુઓ વચ્ચેના તફાવતની બરાબર છે. જો, મહત્તમ ઉદ્દેશ્ય કાર્ય સાથે સીધી સમસ્યાનું નિરાકરણ કરતી વખતે, પુનરાવર્તન શ્રેષ્ઠ ઉકેલ તરફ દોરી જતું નથી, તો ઓછામાં ઓછા એક ચલ માટે અને ફક્ત બધા માટે શ્રેષ્ઠમાંતફાવત
આ સ્થિતિને ધ્યાનમાં લેતા દ્વૈતતાને ધ્યાનમાં રાખીને, અમે લખી શકીએ છીએ
.
આમ, જો, પછી . આનો અર્થ એ છે કે જ્યારે પ્રાથમિક સમસ્યાનો ઉકેલ શ્રેષ્ઠ નથી, ત્યારે દ્વિ સમસ્યાનો ઉકેલ અમાન્ય છે. બીજી બાજુ 
ખાતે આ સૂચવે છે કે પ્રાથમિક સમસ્યાનો શ્રેષ્ઠ ઉકેલ દ્વિ સમસ્યાના સ્વીકાર્ય ઉકેલને અનુરૂપ છે.
આનાથી રેખીય પ્રોગ્રામિંગ સમસ્યાઓ ઉકેલવા માટે નવી પદ્ધતિ વિકસાવવાનું શક્ય બન્યું, જે પ્રથમ અસ્વીકાર્ય, પરંતુ "શ્રેષ્ઠ કરતાં વધુ સારા" ઉકેલમાં પરિણમે છે (સામાન્ય સિમ્પ્લેક્સ પદ્ધતિમાં, આપણે પ્રથમ શોધીએ છીએ. સ્વીકાર્ય, પરંતુ સબઓપ્ટિમલઉકેલ). નવી પદ્ધતિ કહેવાય છે ડ્યુઅલ સિમ્પ્લેક્સ પદ્ધતિ, સોલ્યુશનની શ્રેષ્ઠતાની સ્થિતિની પરિપૂર્ણતા અને શક્ય ઉકેલોના ક્ષેત્ર માટે તેના વ્યવસ્થિત "અંદાજે"ની ખાતરી કરે છે. જ્યારે મેળવેલ ઉકેલ સ્વીકાર્ય હોવાનું બહાર આવે છે, ત્યારે ગણતરીઓની પુનરાવર્તિત પ્રક્રિયા સમાપ્ત થાય છે, કારણ કે આ ઉકેલ પણ શ્રેષ્ઠ છે.
ડ્યુઅલ સિમ્પ્લેક્સ પદ્ધતિ રેખીય પ્રોગ્રામિંગ સમસ્યાઓ હલ કરવાની મંજૂરી આપે છે જેની અવરોધ સિસ્ટમો, હકારાત્મક આધાર સાથે, કોઈપણ સંકેતની મુક્ત શરતો ધરાવે છે. આ પદ્ધતિ અવરોધ સિસ્ટમ પરિવર્તનની સંખ્યા તેમજ સિમ્પ્લેક્સ ટેબલના કદને ઘટાડવાનું શક્ય બનાવે છે. ઉદાહરણનો ઉપયોગ કરીને ડ્યુઅલ સિમ્પ્લેક્સ પદ્ધતિના ઉપયોગને ધ્યાનમાં લો.
ઉદાહરણ. ફંક્શનનું ન્યૂનતમ શોધો 
પ્રતિબંધો હેઠળ
.
ચાલો પ્રમાણભૂત સ્વરૂપ પર જઈએ:
પ્રતિબંધો હેઠળ
પ્રારંભિક સિમ્પ્લેક્સ ટેબ્લોનું સ્વરૂપ છે
|
પાયાની ચલો |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
ઉકેલ |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
પ્રારંભિક મૂળભૂત ઉકેલશ્રેષ્ઠ, પરંતુ સ્વીકાર્ય નથી.
સામાન્ય સિમ્પ્લેક્સ પદ્ધતિની જેમ, વિચારણા હેઠળની ઉકેલ પદ્ધતિ સ્વીકાર્યતા અને શ્રેષ્ઠતાની શરતોના ઉપયોગ પર આધારિત છે.
સ્વીકાર્યતાની સ્થિતિ. નિરપેક્ષ મૂલ્યમાં સૌથી મોટું નકારાત્મક મૂળભૂત ચલ બાકાત ચલ તરીકે પસંદ કરવામાં આવે છે (જો ત્યાં વિકલ્પો હોય, તો પસંદગી મનસ્વી રીતે કરવામાં આવે છે). જો તમામ મૂળભૂત ચલો બિન-નકારાત્મક હોય, તો ગણતરી પ્રક્રિયા સમાપ્ત થાય છે, કારણ કે પરિણામી ઉકેલ શક્ય અને શ્રેષ્ઠ છે.
શરત શ્રેષ્ઠતા. આધારમાં સમાવિષ્ટ ચલ નીચે પ્રમાણે બિન-મૂળભૂત ચલોમાંથી પસંદ કરવામાં આવે છે. ડાબી બાજુના સહગુણાંકોના ગુણોત્તરની ગણતરી કરવામાં આવે છે-બાકાત ચલ સાથે સંકળાયેલ સમીકરણના અનુરૂપ ગુણાંકના સમીકરણો. હકારાત્મક અથવા શૂન્ય છેદ સાથેના સંબંધોને ધ્યાનમાં લેવામાં આવતા નથી. ઇનપુટ વેરીએબલના ન્યૂનતમીકરણની સમસ્યામાં, દર્શાવેલ ગુણોત્તરમાંથી સૌથી નાનો અનુરૂપ હોવો જોઈએ, અને મહત્તમકરણની સમસ્યામાં, સૌથી નાના સંપૂર્ણ મૂલ્ય સાથેનો ગુણોત્તર (જો ત્યાં વિકલ્પો હોય, તો પસંદગી મનસ્વી રીતે કરવામાં આવે છે). જો તમામ ગુણોત્તરના છેદ શૂન્ય અથવા હકારાત્મક હોય, તો સમસ્યાનો કોઈ શક્ય ઉકેલ નથી.
આધારમાં સમાવિષ્ટ કરવા અને બાકાત રાખવાના ચલોને પસંદ કર્યા પછી, આગળનું સોલ્યુશન મેળવવા માટે સિમ્પ્લેક્સ કોષ્ટકની પંક્તિઓને બદલવાની સામાન્ય કામગીરી હાથ ધરવામાં આવે છે.
આ ઉદાહરણમાં, બાકાત ચલ છે. નવા આધાર ચલને નિર્ધારિત કરવા માટે ગણતરી કરેલ ગુણોત્તર નીચેના કોષ્ટકમાં દર્શાવેલ છે:
|
ચલો |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
સમીકરણ x 4 - સમીકરણ |
–2 –4 |
–1 –3 |
|||
|
વલણ |
સમાવવાનું ચલ છે x 2. અનુગામી સ્ટ્રિંગ રૂપાંતરણ નવા સિમ્પ્લેક્સ કોષ્ટકમાં પરિણમે છે:
|
પાયાની ચલો |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
ઉકેલ |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
નવો ઉકેલ પણ શ્રેષ્ઠ, પરંતુ હજુ પણ અમાન્ય. નવા બાકાત ચલ તરીકે, અમે પસંદ કરીએ છીએ (મનસ્વી રીતે) x 3 ચાલો એક સમાવિષ્ટ ચલ વ્યાખ્યાયિત કરીએ.
|
ચલો |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
સમીકરણ x 4 - સમીકરણ |
|||||
|
વલણ |
સિમ્પ્લેક્સ પદ્ધતિ - જ્યાં સુધી ધ્યેય કાર્ય શ્રેષ્ઠ મૂલ્ય (મહત્તમ અથવા લઘુત્તમ) ન લે ત્યાં સુધી રેખીય પ્રોગ્રામિંગ સમસ્યાના અવરોધોની સિસ્ટમના એક મૂળભૂત સોલ્યુશન (સોલ્યુશન પોલિહેડ્રોનનું શિરોબિંદુ) થી બીજા મૂળભૂત ઉકેલમાં ક્રમિક સંક્રમણની આ પદ્ધતિ છે.
સિમ્પ્લેક્સ પદ્ધતિ એ એક સાર્વત્રિક પદ્ધતિ છે જે કોઈપણને ઉકેલી શકે છે રેખીય પ્રોગ્રામિંગ સમસ્યા, જ્યારે ગ્રાફિકલ પદ્ધતિ માત્ર બે-ચલ અવરોધ સિસ્ટમ માટે યોગ્ય છે.
સિમ્પ્લેક્સ પદ્ધતિ અમેરિકન ગણિતશાસ્ત્રી આર. ડેન્ટ્ઝિગ દ્વારા 1947 માં પ્રસ્તાવિત કરવામાં આવી હતી, ત્યારથી, ઉદ્યોગની જરૂરિયાતો માટે, આ પદ્ધતિ ઘણીવાર હજારો ચલો અને અવરોધો સાથે રેખીય પ્રોગ્રામિંગ સમસ્યાઓનું નિરાકરણ કરે છે.
સિમ્પ્લેક્સ પદ્ધતિના અલ્ગોરિધમ પર આગળ વધતા પહેલા, થોડી વ્યાખ્યાઓ.
અવરોધોની સિસ્ટમના કોઈપણ બિન-નકારાત્મક ઉકેલને કહેવામાં આવે છે સ્વીકાર્ય ઉકેલ .
એક સિસ્ટમ બનવા દો mથી પ્રતિબંધો nચલ ( m n).
સ્વીકાર્ય મૂળભૂત ઉકેલ સમાવતી ઉકેલ છે mબિન-નકારાત્મક મુખ્ય (પાયાની ) ચલ અને n - m બિન-કોર . (બિન-મૂળભૂત, અથવા મફત ) ચલો. મૂળભૂત ઉકેલમાં બિન-મૂળભૂત ચલો શૂન્યની બરાબર છે, જ્યારે મુખ્ય ચલો, નિયમ તરીકે, બિન-શૂન્ય છે, એટલે કે, તે હકારાત્મક સંખ્યાઓ છે.
કોઈપણ mસિસ્ટમ ચલો mસાથે રેખીય સમીકરણો nચલો કહેવામાં આવે છે મુખ્ય , જો તેમના પરના ગુણાંકનો નિર્ધારક શૂન્યથી અલગ હોય. પછી બાકીના n - mચલો કહેવામાં આવે છે બિન-કોર (અથવા મફત ).
સિમ્પ્લેક્સ પદ્ધતિ અલ્ગોરિધમ
- પગલું 1. રેખીય પ્રોગ્રામિંગ સમસ્યાને કેનોનિકલ સ્વરૂપમાં લાવો. આ કરવા માટે, મફત શરતોને જમણી બાજુએ ખસેડો (જો આ મફત શરતોમાંથી નકારાત્મક હોય, તો અનુરૂપ સમીકરણ અથવા અસમાનતાને - 1 વડે ગુણાકાર કરો) અને દરેક અવરોધમાં વધારાના ચલો દાખલ કરો (વત્તા ચિહ્ન સાથે, જો મૂળ અસમાનતાનું ચિહ્ન "થી ઓછું અથવા તેની બરાબર છે, અને બાદબાકી ચિહ્ન સાથે જો "તેના કરતા વધારે અથવા બરાબર").
- પગલું 2. જો પરિણામી સિસ્ટમમાં mસમીકરણો, પછી mચલોને મુખ્ય તરીકે લો, મુખ્ય ચલોને બિન-મૂળભૂતની દ્રષ્ટિએ વ્યક્ત કરો અને અનુરૂપ મૂળભૂત ઉકેલ શોધો. જો મળેલ મૂળભૂત ઉકેલ સ્વીકાર્ય હોવાનું બહાર આવ્યું, તો સ્વીકાર્ય મૂળભૂત ઉકેલ પર જાઓ.
- પગલું 3. શક્ય મૂળભૂત ઉકેલના નાના ચલોના સંદર્ભમાં ધ્યેય કાર્યને વ્યક્ત કરો. જો રેખીય સ્વરૂપનું મહત્તમ (લઘુત્તમ) જોવા મળે છે અને તેની અભિવ્યક્તિમાં નકારાત્મક (હકારાત્મક) ગુણાંક સાથે કોઈ બિન-મૂળભૂત ચલો નથી, તો પછી શ્રેષ્ઠતા માપદંડ પૂર્ણ થાય છે અને પરિણામી મૂળભૂત ઉકેલ શ્રેષ્ઠ છે - ઉકેલ સમાપ્ત થઈ ગયો છે. જો, રેખીય સ્વરૂપની મહત્તમ (ન્યૂનતમ) શોધતી વખતે, તેની અભિવ્યક્તિમાં નકારાત્મક (હકારાત્મક) ગુણાંક સાથે એક અથવા વધુ બિન-મૂળભૂત ચલો હોય, તો નવા મૂળભૂત ઉકેલ પર જાઓ.
- પગલું 4. નકારાત્મક (હકારાત્મક) ગુણાંક સાથે રેખીય સ્વરૂપમાં સમાવિષ્ટ બિન-મૂળભૂત ચલોમાંથી, સૌથી મોટા (મોડ્યુલો) ગુણાંકને અનુરૂપ એક પસંદ કરો અને તેને મુખ્યમાં સ્થાનાંતરિત કરો. પગલું 2 પર જાઓ.
મહત્વપૂર્ણ શરતો
કેટલાક ખાસ કિસ્સાઓની ચર્ચા અલગ લેખોમાં કરવામાં આવી છે: ક્યારે મહત્તમ ઉદ્દેશ્ય કાર્ય - અનંત, ક્યારે તંત્ર પાસે કોઈ ઉકેલ નથી, અને ક્યારે શ્રેષ્ઠ ઉકેલ માત્ર એક જ નથી .
આગળ, અમે એક લાક્ષણિક ઉદાહરણનું વિશ્લેષણ કરીશું, જ્યારે મર્યાદાઓની સિસ્ટમ સુસંગત હોય છે અને મર્યાદિત શ્રેષ્ઠ હોય છે, અને માત્ર એક જ હોય છે. સિમ્પ્લેક્સ પદ્ધતિની વિવિધતા છે પરિવહન સમસ્યા હલ કરવા માટે વિતરણ પદ્ધતિ .
સિમ્પ્લેક્સ કોષ્ટકો સાથે સિમ્પ્લેક્સ પદ્ધતિ
સિમ્પ્લેક્સ કોષ્ટકો બાંધવાથી, બીજગણિત પરિવર્તન કરતાં રેખીય પ્રોગ્રામિંગ સમસ્યાને હલ કરવી ખૂબ સરળ છે, જે આગળના ફકરામાં બતાવેલ છે. સિમ્પ્લેક્સ કોષ્ટકો ખૂબ જ દ્રશ્ય છે. સિમ્પ્લેક્સ કોષ્ટકો સાથે કામ કરવા માટે ઘણા પ્રકારના નિયમો છે. અમે નિયમનું વિશ્લેષણ કરીશું, જેને મોટાભાગે અગ્રણી કૉલમ અને અગ્રણી પંક્તિ નિયમ કહેવામાં આવે છે.
નવી વિન્ડોમાં અપૂર્ણાંકો સાથે મેન્યુઅલ ક્રિયાઓ ખોલવી ઉપયોગી થશે: તેમાં પૂરતા પ્રમાણમાં છે, સિમ્પ્લેક્સ પદ્ધતિમાં સમસ્યાઓમાં અપૂર્ણાંક, તેને હળવાશથી મૂકવા માટે.
ઉદાહરણ.
અમે વધારાના બિન-નકારાત્મક ચલો રજૂ કરીએ છીએ અને અસમાનતાઓની આ સિસ્ટમને સમીકરણોની સમકક્ષ સિસ્ટમમાં ઘટાડીએ છીએ.
.
આ નીચેના નિયમના પાલનમાં કરવામાં આવ્યું હતું: જો મૂળ મર્યાદામાંનું ચિહ્ન "ઓછું અથવા તેના જેટલું" હોય, તો વધારાનું ચલ ઉમેરવું આવશ્યક છે, અને જો "તેના કરતા વધારે અથવા સમાન" હોય, તો વધારાનું ચલ ઉમેરવું આવશ્યક છે. બાદબાકી
રજૂ કરાયેલ વધારાના ચલો મુખ્ય (મૂળભૂત) તરીકે લેવામાં આવે છે. પછી અને નોનબેઝિક (ફ્રી) ચલ છે.
મુખ્ય (મૂળભૂત) ચલોને બિન-મૂળભૂત (ફ્રી) ના સંદર્ભમાં વ્યક્ત કરવાથી, અમે મેળવીએ છીએ
અમે ધ્યેય કાર્યને બિન-મૂળભૂત (ફ્રી) ચલોના સંદર્ભમાં પણ વ્યક્ત કરીએ છીએ:
ચલોના ગુણાંક (અજ્ઞાત) પરથી આપણે પ્રથમ સિમ્પ્લેક્સ ટેબ્લો બનાવીએ છીએ.
| કોષ્ટક 1 | ||||
| મૂળભૂત અજ્ઞાત | મફત સભ્યો | છૂટક અજાણ્યા | સહાયક ગુણાંક | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| એફ | 0 | -1 | -2 | |
કોષ્ટકની છેલ્લી પંક્તિ, જેમાં ઉદ્દેશ્ય કાર્ય અને તેમાં મુક્ત ચલોના ગુણાંક છે, તેને અનુક્રમણિકા પંક્તિ કહેવામાં આવશે.
પરિણામી ઉકેલ શ્રેષ્ઠ નથી, કારણ કે અનુક્રમણિકા પંક્તિમાં મુક્ત ચલોના ગુણાંક નકારાત્મક છે. એટલે કે, શ્રેષ્ઠ ઉકેલ એ હશે કે જેમાં અનુક્રમણિકા પંક્તિમાં મુક્ત ચલોના ગુણાંક શૂન્ય કરતા વધારે અથવા તેના સમાન હશે.
આગલા કોષ્ટક પર જવા માટે, સંખ્યાઓનો સૌથી મોટો (મોડ્યુલો) શોધો અને . આ સંખ્યા 2 છે. તેથી, અગ્રણી કૉલમ એ કૉલમ છે જેમાં તે લખાયેલ છે
અગ્રણી પંક્તિ નક્કી કરવા માટે, અમે અગ્રણી સ્તંભના ઘટકો માટે મુક્ત સભ્યોના લઘુત્તમ ગુણોત્તર શોધીએ છીએ, અને જો અંશમાં સકારાત્મક સંખ્યા હોય અને છેદ નકારાત્મક હોય, તો ગુણોત્તરને અનંત સમાન ગણવામાં આવે છે.
.
તેથી, અગ્રણી લાઇન તે છે જેમાં તે લખાયેલ છે
અગ્રણી તત્વ આમ -2 છે.
અમે બીજું સિમ્પ્લેક્સ ટેબલ કંપોઝ કરીએ છીએ.
અમે પ્રથમ લાઇનમાં નવું મૂળભૂત તત્વ દાખલ કરીએ છીએ, અને અમે તે કૉલમ દાખલ કરીએ છીએ જેમાં તે ઊભું હતું, અમે એક નવું મફત ચલ દાખલ કરીએ છીએ.
પ્રથમ લાઇન ભરો. આ કરવા માટે, અમે કોષ્ટક 1 ની અગ્રણી હરોળમાં તમામ સંખ્યાઓને અગ્રણી તત્વ દ્વારા વિભાજીત કરીએ છીએ અને તેને કોષ્ટક 2 ની પ્રથમ પંક્તિના અનુરૂપ કૉલમમાં લખીએ છીએ, સિવાય કે અગ્રણી કૉલમમાંની સંખ્યાને બાદ કરતાં, જ્યાં અગ્રણીની પરસ્પર તત્વ લખાયેલ છે (એટલે કે, અગ્રણી તત્વ દ્વારા વિભાજિત).
સહાયક ગુણાંકના કૉલમ ભરો. કોષ્ટક 1 ની અગ્રણી કૉલમની આ સંખ્યા માટે, અગ્રણી તત્વ ઉપરાંત, અમે કોષ્ટક 2 ના સહાયક ગુણાંકના કૉલમમાં વિરુદ્ધ સંકેતો સાથે લખીએ છીએ.
| કોષ્ટક 2 | ||||
| મૂળભૂત અજ્ઞાત | મફત સભ્યો | છૂટક અજાણ્યા | સહાયક ગુણાંક | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| એફ | 2 | -2 | -1 | 2 |
જેમણે હજી સુધી નવી વિંડોમાં અપૂર્ણાંક સાથેની મેન્યુઅલ ક્રિયાઓ ખોલી નથી, તે હવે કરી શકે છે, કારણ કે તે સમય છે.
કોષ્ટક 2 ની બાકીની પંક્તિઓ મેળવવા માટે, આ કોષ્ટકની પ્રથમ પંક્તિમાં પહેલેથી જ સંખ્યાઓ ભરવામાં આવી રહેલી પંક્તિમાં સહાયક ગુણાંક દ્વારા ગુણાકાર કરવામાં આવે છે, અને પરિણામમાં આપણે કોષ્ટક 1 માંથી સંખ્યા ઉમેરીએ છીએ, જે સમાન પંક્તિમાં છે અનુરૂપ ચલ.
ઉદાહરણ તરીકે, બીજી હરોળના મફત સભ્ય મેળવવા માટે, અમે સંખ્યા 1 ને 1 વડે ગુણાકાર કરીએ છીએ અને કોષ્ટક 1 માંથી નંબર -4 ઉમેરીએ છીએ. આપણને -3 મળે છે. આપણે બીજી લીટીમાં તે જ રીતે ગુણાંક શોધીએ છીએ: 
. અગાઉના કોષ્ટકમાં નવા ફ્રી વેરીએબલ સાથે કોઈ કૉલમ ન હોવાથી, નવા ફ્રી ચલની કૉલમમાં બીજી પંક્તિનો ગુણાંક હશે 
(એટલે કે, કોષ્ટક 1 માંથી આપણે 0 ઉમેરીએ છીએ, કારણ કે કોષ્ટક 1 માં કોઈ કૉલમ c નથી).
ઇન્ડેક્સ લાઇન એ જ રીતે ભરવામાં આવે છે:
આ રીતે મેળવેલ ઉકેલ ફરીથી શ્રેષ્ઠ નથી, કારણ કે અનુક્રમણિકા પંક્તિમાં મુક્ત ચલોના ગુણાંક ફરીથી નકારાત્મક છે.
આગલા સિમ્પ્લેક્સ ટેબલ પર જવા માટે, ચાલો સંખ્યાઓનો સૌથી મોટો (મોડ્યુલો) શોધીએ અને , એટલે કે ઇન્ડેક્સ લાઇનમાં સહગુણાંકોના મોડ્યુલો. આ સંખ્યા 2 છે. તેથી, અગ્રણી કૉલમ એ કૉલમ છે જેમાં .
અગ્રણી પંક્તિ શોધવા માટે, ચાલો અગ્રણી પંક્તિના ઘટકો માટે મફત સભ્યોનો લઘુત્તમ ગુણોત્તર શોધીએ. અમને મળે છે:
.
તેથી, અગ્રણી લાઇન એ એક છે જેમાં લખાયેલ છે, અને અગ્રણી તત્વ -3/2 છે.
ત્રીજા સિમ્પ્લેક્સ કોષ્ટકનું સંકલન
આપણે પ્રથમ લીટીમાં નવું મૂળભૂત ચલ લખીએ છીએ. જે કૉલમમાં તે હતું, અમે એક નવું ફ્રી ચલ દાખલ કરીએ છીએ.
પહેલી કતાર:
સહાયક ગુણાંક:
| કોષ્ટક 3 | ||||
| મૂળભૂત અજ્ઞાત | મફત સભ્યો | છૂટક અજાણ્યા | સહાયક ગુણાંક | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| એફ | 6 | -4/3 | -1/3 | 2 |
પરિણામી ઉકેલ ફરીથી શ્રેષ્ઠ નથી, કારણ કે અનુક્રમણિકા પંક્તિમાં મુક્ત અજ્ઞાતના ગુણાંક ફરીથી નકારાત્મક છે.
ચોથા સિમ્પ્લેક્સ ટેબલ પર જવા માટે, ચાલો સૌથી મોટી સંખ્યાઓ શોધીએ અને . આ એક નંબર છે.
તેથી, અગ્રણી કૉલમ સાથેની એક છે.
અગ્રણી સ્તંભના ઘટકો સાથે મુક્ત સભ્યોના સંબંધોનું ન્યૂનતમ મોડ્યુલસ:
.
તેથી, અગ્રણી લાઇન એ એક છે જેમાં લખાયેલ છે, અને અગ્રણી તત્વ 1/3 છે.
ચોથા સિમ્પ્લેક્સ કોષ્ટકમાં, આપણે પ્રથમ લીટીમાં નવું મૂળભૂત ચલ લખીએ છીએ. કૉલમમાં જ્યાં તે હતું, અમે એક નવું ફ્રી ચલ લખીએ છીએ.
પહેલી કતાર:
સહાયક ગુણાંક:
| કોષ્ટક 4 | ||||
| મૂળભૂત અજ્ઞાત | મફત સભ્યો | છૂટક અજાણ્યા | સહાયક ગુણાંક | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| એફ | 14 | 4 | -3 | 4/3 |
બીજી પંક્તિના ઉદાહરણનો ઉપયોગ કરીને બાકીની પંક્તિઓની ગણતરી:
પરિણામી સોલ્યુશન પણ શ્રેષ્ઠ નથી, પરંતુ તે પહેલાનાં કરતાં વધુ સારું છે, કારણ કે અનુક્રમણિકા પંક્તિમાં મુક્ત ચલો માટેનો એક ગુણાંક બિન-નકારાત્મક છે.
યોજનાને સુધારવા માટે, ચાલો આગલા સિમ્પ્લેક્સ ટેબ્લો પર આગળ વધીએ.
4 અને નંબરોમાંથી સૌથી મોટી શોધો. આ સંખ્યા 4 છે. તેથી, અગ્રણી કૉલમ છે.
અગ્રણી પંક્તિ શોધવા માટે, શોધો
.
તેથી, અગ્રણી લાઇન એ છે જેમાં શામેલ છે. પરંતુ તેઓ પહેલાથી જ મુક્ત ચલો વચ્ચે સાથે હતા. તેથી, આગલા ચલને મફતમાંથી મૂળભૂતમાં સ્થાનાંતરિત કરવા માટે, અમે બીજી અગ્રણી કૉલમ પસંદ કરીએ છીએ - જેમાં લખાયેલ છે.
અગ્રણી પંક્તિ શોધવા માટે, શોધો
.
તેથી, કી લાઇન એ એક છે જેમાં લખાયેલ છે, અને અગ્રણી તત્વ 1 છે.
પાંચમા સિમ્પ્લેક્સ કોષ્ટકમાં, નવું મૂળભૂત ચલ પ્રથમ લીટીમાં લખેલું છે. કૉલમમાં જ્યાં તે હતું, અમે એક નવું ફ્રી ચલ લખીએ છીએ.
પહેલી કતાર:
સહાયક ગુણાંક:
| કોષ્ટક 5 | ||||
| મૂળભૂત અજ્ઞાત | મફત સભ્યો | છૂટક અજાણ્યા | સહાયક ગુણાંક | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| એફ | 20 | 1 | 3 | 3 |
ચાલો તરત જ શોધવાનો પ્રયાસ કરીએ કે શું ઉકેલ શ્રેષ્ઠ નથી. તેથી, બાકીની પંક્તિઓ માટે, અમે ફક્ત મફત શરતોની ગણતરી કરીએ છીએ (મૂળ ચલોના મૂલ્યો શોધવા માટે જ્યારે મફત ચલો શૂન્યની બરાબર હોય છે) અને અનુક્રમણિકા પંક્તિમાં મુક્ત ચલો માટે ગુણાંક.
મફત સભ્યો:
બીજી લાઇનમાં;
ત્રીજી પંક્તિમાં;
ચોથી લાઇન પર.
અનુક્રમણિકા રેખા:
અમે સિમ્પ્લેક્સ કોષ્ટક 5 જોઈએ છીએ. અમે જોઈએ છીએ કે શ્રેષ્ઠ ઉકેલ પ્રાપ્ત થયો છે, કારણ કે અનુક્રમણિકા પંક્તિમાં મફત અજાણ્યાઓ માટેના ગુણાંક બિન-નકારાત્મક છે.
બીજગણિત પરિવર્તન સાથે સિમ્પ્લેક્સ પદ્ધતિ
ચાલો બીજગણિત પરિવર્તનો દ્વારા અગાઉના ફકરાના સમાન ઉદાહરણને ઉકેલીએ. એ નોંધવું જોઈએ કે આ પ્રકારની સિમ્પ્લેક્સ પદ્ધતિને ઉકેલતી વખતે, ફોર્મમાં લક્ષ્ય કાર્ય ન લખવું વધુ સારું છે. , કારણ કે ચિહ્નોમાં મૂંઝવણમાં આવવું સરળ છે. પરંતુ આ કિસ્સામાં, અલ્ગોરિધમનો બિંદુ જે શ્રેષ્ઠતાના માપદંડને નિર્ધારિત કરે છે તે નીચે પ્રમાણે સંશોધિત કરવામાં આવશે.
જો રેખીય સ્વરૂપનું મહત્તમ (લઘુત્તમ) જોવા મળે છે અને તેની અભિવ્યક્તિમાં હકારાત્મક (નકારાત્મક) ગુણાંક સાથે કોઈ બિન-મૂળભૂત ચલો નથી, તો પછી શ્રેષ્ઠતા માપદંડ પૂર્ણ થાય છે અને પરિણામી મૂળભૂત ઉકેલ શ્રેષ્ઠ છે - ઉકેલ સમાપ્ત થઈ ગયો છે. જો, રેખીય સ્વરૂપની મહત્તમ (ન્યૂનતમ) શોધતી વખતે, તેની અભિવ્યક્તિમાં હકારાત્મક (નકારાત્મક) ગુણાંક સાથે એક અથવા વધુ બિન-મૂળભૂત ચલો હોય, તો નવા મૂળભૂત ઉકેલ પર જાઓ.
ઉદાહરણ.મર્યાદાઓ હેઠળ મહત્તમ કાર્ય શોધો
પગલું I. અમે વધારાના બિન-નકારાત્મક ચલો રજૂ કરીએ છીએ અને અસમાનતાઓની આ સિસ્ટમને સમીકરણોની સમકક્ષ સિસ્ટમમાં ઘટાડીએ છીએ.
.
પ્રસ્તુત વધારાના ચલો મુખ્ય તરીકે લેવામાં આવે છે, કારણ કે આ કિસ્સામાં સિસ્ટમનો મૂળભૂત ઉકેલ સરળતાથી મળી જાય છે. પછી અને નાના ચલો છે.
મુખ્ય ચલોને બિન-મૂળભૂતની દ્રષ્ટિએ વ્યક્ત કરવાથી, આપણે મેળવીએ છીએ
પરિણામે, મૂળભૂત અને બિન-મૂળભૂતમાં ચલોનું આ વિભાજન મૂળભૂત ઉકેલને અનુરૂપ છે 
, જે અમાન્ય છે (બે ચલો નકારાત્મક છે), અને તેથી શ્રેષ્ઠ નથી. ચાલો આ મૂળભૂત ઉકેલમાંથી સુધારેલા ઉકેલ તરફ આગળ વધીએ.
કયા ચલને નૉન-પ્રિન્સિપલમાંથી પ્રિન્સિપલમાં રૂપાંતરિત કરવું જોઈએ તે નક્કી કરવા માટે, છેલ્લી સિસ્ટમના બે ઉપલબ્ધ સમીકરણોમાંથી કોઈ એકને નકારાત્મક મુક્ત શરતો સાથે ધ્યાનમાં લો, ઉદાહરણ તરીકે, બીજું. તે બતાવે છે કે અને મુખ્ય ચલોમાં ભાષાંતર કરી શકાય છે, કારણ કે આ સમીકરણમાં તેઓ હકારાત્મક ગુણાંક ધરાવે છે (તેથી, જ્યારે તેઓ વધે છે, અને જો આપણે તેમાંના કોઈપણને મુખ્ય ચલોમાં અનુવાદિત કરીએ, તો ચલ વધશે).
ચાલો મુખ્ય ચલમાં અનુવાદ કરવાનો પ્રયાસ કરીએ. કયા ચલને મુખ્યમાંથી બિન-મૂળભૂતમાં સ્થાનાંતરિત કરવું જોઈએ તે નિર્ધારિત કરવા માટે, અમે સિસ્ટમના મુક્ત સભ્યોના ગુણોત્તર અને ગુણાંકમાં સૌથી નાના ગુણોત્તરનું સંપૂર્ણ મૂલ્ય શોધીએ છીએ. અમારી પાસે . તે ત્રીજા સમીકરણમાંથી મેળવવામાં આવે છે, જે દર્શાવે છે કે ચલને બિન-મૂળભૂતમાં રૂપાંતરિત કરવું આવશ્યક છે, જે મૂળ મૂળભૂત ઉકેલમાં હકારાત્મક છે. પરિણામે, મૂળ ઉકેલની જેમ મેળવેલ મૂળભૂત ઉકેલમાં બે નકારાત્મક ઘટકો છે, એટલે કે, આવા મૂળભૂત ઉકેલમાં સંક્રમણમાં કોઈ સુધારો થશે નહીં.
સિમ્પ્લેક્સ પદ્ધતિ- તે સંદર્ભ યોજનાઓની ક્રમબદ્ધ ગણતરીની એક પદ્ધતિ છે (આગામી યોજનામાં સંક્રમણ દરમિયાન ઉદ્દેશ્ય કાર્યના મૂલ્યમાં એકવિધ ફેરફાર દ્વારા ઓર્ડરની ખાતરી કરવામાં આવે છે). આ કિસ્સામાં, સિદ્ધાંતનું અવલોકન કરવું જરૂરી છે: દરેક આગલા પગલામાં સુધારો થવો જોઈએ અથવા, આત્યંતિક કેસોમાં, ઉદ્દેશ્ય કાર્યનું મૂલ્ય બગડવું જોઈએ નહીં.
LLP ઉકેલવા માટે સિમ્પ્લેક્સ પદ્ધતિતે પ્રમાણભૂત સ્વરૂપમાં ઘટાડો થયો છે, એટલે કે. પ્રતિબંધો - અસમાનતાઓમાંથી પ્રતિબંધો - સમાનતાઓ કરવી જરૂરી છે. આ કરવા માટે, દરેક અવરોધ વધારાના બિન-નકારાત્મક સાથે પૂરક છે બેલેન્સ શીટ ચલ“+” ચિહ્ન સાથે જો અસમાનતાનું ચિહ્ન “£” હોય, અને “–” ચિહ્ન સાથે જો અસમાનતાનું ચિહ્ન “³” હોય.
ઉદ્દેશ્ય કાર્યમાં, આ વધારાના ચલો શૂન્ય ગુણાંક સાથે દાખલ થાય છે, એટલે કે. લક્ષ્ય કાર્ય પ્રવેશ બદલાશે નહીં. પ્રત્યેક ચલ કે જે બિન-નકારાત્મક સ્થિતિને આધીન નથી તે બે બિન-નકારાત્મક ચલોના તફાવત તરીકે રજૂ કરી શકાય છે: .
જો કાર્યની મર્યાદાઓ સંસાધનોની હાજરી અને વપરાશને પ્રતિબિંબિત કરે છે, તો કાર્ય યોજનામાં વધારાના ચલનું સંખ્યાત્મક મૂલ્ય, પ્રમાણભૂત સ્વરૂપમાં લખાયેલ છે, તે ન વપરાયેલ સંસાધનની રકમની બરાબર છે.
સિમ્પ્લેક્સ પદ્ધતિ દ્વારા સમસ્યા હલ કરવા માટે, અમે ઉપયોગ કરીશું રેખીય સમીકરણોની સિસ્ટમ અને સંશોધિત જોર્ડન નાબૂદી પદ્ધતિના ટૂંકા સિમ્પ્લેક્સ કોષ્ટકો.
1. અમે પ્રથમ મૂળભૂત યોજના બનાવીએ છીએ
કાર્ય એ જ રહે છે. ચાલો વધારાના સંતુલન ચલો રજૂ કરીને સમીકરણોની સિસ્ટમના પ્રમાણભૂત સ્વરૂપમાં અસમાનતાઓની સિસ્ટમના પ્રમાણભૂત સ્વરૂપને (1) લાવીએ. x 3 , x 4 , x 5 ,x 6 .
આર્થિક અર્થમાં, વધારાના ચલોના મૂલ્યો x 3 , x 4 , x 5 ઉત્પાદનોના વેચાણ પછી કાચા માલનું સંતુલન નક્કી કરો.
પરિણામી સમીકરણોની સિસ્ટમના મેટ્રિક્સનું સ્વરૂપ છે:
તે જોઈ શકાય છે કે મેટ્રિક્સમાં એ 4થા ક્રમનો આધાર ગૌણ એ નિર્ણાયક છે, જે વધારાના ચલો માટે એકમ ગુણાંકથી બનેલો છે x 3 , x 4 , x 5 ,x 6 , કારણ કે તે બિન-શૂન્ય છે અને 1 ની બરાબર છે. આનો અર્થ એ છે કે આ ચલો માટે કૉલમ વેક્ટર રેખીય રીતે સ્વતંત્ર છે, એટલે કે. ફોર્મ આધાર, અને અનુરૂપ ચલો x 3 , x 4 , x 5 ,x 6 છે પાયાની(પાયાની). ચલો x 1 , x 2 બોલાવવામાં આવશે મફત(નાની).
જો મફત ચલો x 1 અને x 2 વિવિધ મૂલ્યો સેટ કરવા માટે, પછી, મૂળભૂત ચલોના સંદર્ભમાં સિસ્ટમને હલ કરીને, અમે ચોક્કસ ઉકેલોનો અનંત સમૂહ મેળવીએ છીએ. જો મફત ચલો માટે માત્ર શૂન્ય મૂલ્યો સેટ કરવામાં આવ્યા હોય, તો ચોક્કસ ઉકેલોના અનંત સમૂહમાંથી, મૂળભૂત ઉકેલો- મૂળભૂત યોજનાઓ.
ચલ મૂળભૂત હોઈ શકે છે કે કેમ તે શોધવા માટે, આ ચલોના ગુણાંક ધરાવતા નિર્ણાયકની ગણતરી કરવી જરૂરી છે. જો આ નિર્ણાયક શૂન્યની બરાબર ન હોય, તો આ ચલો મૂળભૂત હોઈ શકે છે.
મૂળભૂત ઉકેલોની સંખ્યા અને મૂળભૂત ચલોના જૂથોની અનુરૂપ સંખ્યા , જ્યાં nચલોની કુલ સંખ્યા છે, આરમૂળભૂત ચલોની સંખ્યા છે, આર≤ m≤ n.
અમારા કાર્ય માટે આર = 4; n= 6. પછી, એટલે કે 4 મૂળભૂત ચલોના 15 જૂથો શક્ય છે (અથવા 15 મૂળભૂત ઉકેલો).
ચાલો મૂળભૂત ચલોના સંદર્ભમાં સમીકરણોની સિસ્ટમ હલ કરીએ x 3 , x 4 , x 5 ,x 6:
એમ ધારી રહ્યા છીએ કે મુક્ત ચલો x 1 = 0, x 2 = 0, આપણે મૂળભૂત ચલોની કિંમતો મેળવીએ છીએ: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, એટલે કે. મૂળભૂત ઉકેલ = (0; 0; 312; 15; 24; -10) હશે.
આ મૂળભૂત ઉકેલ છે અસ્વીકાર્ય, કારણ કે x 6 = –10 ≤ 0, અને અવરોધ સ્થિતિ દ્વારા x 6 ≥ 0. તેથી, ચલને બદલે x 6 આધાર તરીકે, તમારે ફ્રીમાંથી બીજું ચલ લેવાની જરૂર છે x 1 અથવા x 2 .
અમે ટૂંકા સિમ્પ્લેક્સ કોષ્ટકોનો ઉપયોગ કરીને આગળનું સોલ્યુશન હાથ ધરીશું, નીચે પ્રમાણે સિસ્ટમના ગુણાંક સાથે પ્રથમ કોષ્ટકની પંક્તિઓ ભરીને (કોષ્ટક 1):
કોષ્ટક 1
એફ- શબ્દમાળા કહેવામાં આવે છે અનુક્રમણિકા. તે વિરુદ્ધ ચિહ્નો સાથે લેવામાં આવેલા ઉદ્દેશ્ય કાર્ય ગુણાંકથી ભરેલું છે, કારણ કે કાર્યના સમીકરણને આ રીતે રજૂ કરી શકાય છે એફ = 0 – (– 4x 1 – 3x 2).
મફત સભ્યોની કૉલમમાં b iનકારાત્મક તત્વ છે b 4 = -10, એટલે કે. સિસ્ટમનો ઉકેલ અમાન્ય છે. માન્ય સોલ્યુશન (બેઝ પ્લાન) મેળવવા માટે, તત્વ b 4 બિન-નકારાત્મક બનાવવું આવશ્યક છે.
પસંદ કરો x 6 - નકારાત્મક મુક્ત સભ્ય સાથેની રેખા. આ રેખા નકારાત્મક તત્વો ધરાવે છે. તેમાંથી કોઈપણ પસંદ કરો, ઉદાહરણ તરીકે, "-1" માં x 1 -કૉલમ, અને x 1 - કૉલમ તરીકે સ્વીકારો પરવાનગી કૉલમ(તે નક્કી કરશે કે ચલ x 1 મફતમાંથી મૂળભૂતમાં જશે).
અમે મફત સભ્યો શેર કરીએ છીએ b iસંબંધિત તત્વો પર a છેસ્તંભ ઉકેલવા, અમને મળે છે મૂલ્યાંકન સંબંધોΘ i==(24, 15, 12, 10). આમાંથી, અમે સૌથી નાનું હકારાત્મક (minΘ i=10), જે અનુરૂપ હશે પરવાનગી રેખા. પરવાનગી શબ્દમાળા ચલ વ્યાખ્યાયિત કરે છે xj, જે આગલા પગલા પર આધારમાંથી બહાર નીકળે છે અને મુક્ત બને છે. એટલા માટે x 6 -લાઇન એ અનુમતિશીલ રેખા છે, અને તત્વ "-1" છે સક્રિય તત્વ. અમે તેને વર્તુળ કરીએ છીએ. ચલો x 1 અને x 6 અદલાબદલી છે.
અંદાજિત ગુણોત્તર Θ iદરેક લાઇનમાં નિયમો દ્વારા નક્કી કરવામાં આવે છે:
1) Θ i= જો b iઅને a છેવિવિધ ચિહ્નો છે;
2) Θ i= ∞ જો b i= 0 અને a છે < 0;
3) Θ i= ∞ જો a છે = 0;
4) Θ i= 0 જો b i= 0 અને a છે > 0;
5) Θ i= જો b iઅને a છેસમાન ચિહ્નો છે.
અમે અનુમતિશીલ તત્વ સાથે સંશોધિત જોર્ડન એલિમિનેશન (MJJI)નું પગલું લઈએ છીએ અને નીચેના નિયમ અનુસાર એક નવું કોષ્ટક (કોષ્ટક 2) કમ્પાઈલ કરીએ છીએ:
1) રિઝોલ્વિંગ એલિમેન્ટ (RE) ની જગ્યાએ, મૂલ્ય સેટ કરવામાં આવે છે, તેનું વ્યસ્ત, એટલે કે. ;
2) અનુમતિશીલ રેખાના તત્વો RE માં વિભાજિત કરવામાં આવે છે;
3) રિઝોલ્વિંગ કૉલમના તત્વો RE માં વિભાજિત થાય છે અને ચિહ્ન બદલાય છે;
4) બાકીના તત્વો લંબચોરસ નિયમ અનુસાર જોવા મળે છે:
ટેબલમાંથી. 2 બતાવે છે કે માં મફત સભ્યો b i-કૉલમ બિન-નકારાત્મક છે, તેથી, પ્રારંભિક સ્વીકાર્ય ઉકેલ પ્રાપ્ત થાય છે - પ્રથમ આધાર યોજના= (10; 0; 182; 5; 4; 0). આ કિસ્સામાં, કાર્યનું મૂલ્ય એફ() = 40. ભૌમિતિક રીતે, આ ટોચને અનુરૂપ છે એફ(10; 0) ઉકેલ બહુકોણ (ફિગ. 1).
કોષ્ટક 2
2. અમે શ્રેષ્ઠતા માટે યોજના તપાસીએ છીએ.આધાર યોજના શ્રેષ્ઠ નથી, કારણ કે માં એફ-લાઇનમાં નકારાત્મક ગુણાંક "-4" છે. અમે યોજનામાં સુધારો કરીએ છીએ.
3. નવી આધારરેખા શોધવી
અમે નિયમ અનુસાર મંજૂરી આપતા તત્વને પસંદ કરીએ છીએ:
અમે માં સૌથી નાનો નકારાત્મક ગુણાંક પસંદ કરીએ છીએ એફ-લાઇન "-4", જે સક્ષમ કોલમ નક્કી કરે છે - x 6; ચલ x 6 મૂળભૂત માં અનુવાદ;
અમે ગુણોત્તર Θ શોધીએ છીએ i, તેમાંથી આપણે સૌથી નાનું હકારાત્મક પસંદ કરીએ છીએ, જે અનુમતિશીલ શબ્દમાળાને અનુરૂપ છે:
મિનિટ Θ i = મિનિટ(14, 5, 2, ∞) = 2, તેથી x 5 - રેખા - અનુમતિશીલ, ચલ x 5 અમે મફતમાં ભાષાંતર કરીએ છીએ (ચલ x 5 અને x 6 અદલાબદલી છે).
અનુમતિશીલ પંક્તિ અને કૉલમના આંતરછેદ પર અનુમતિશીલ તત્વ "2" છે;
અમે પગલું SHMZhI કરીએ છીએ, અમે ટેબલ બનાવીએ છીએ. ઉપરના નિયમ મુજબ 3 અને નવો સંદર્ભ પ્લાન મેળવો = (12; 0; 156; 3; 0; 2).
કોષ્ટક 3
4. શ્રેષ્ઠતા માટે નવી મૂળભૂત યોજના તપાસી રહ્યું છે
બેઝ પ્લાન પણ શ્રેષ્ઠ નથી, કારણ કે માં એફ-લાઇનમાં નકારાત્મક ગુણાંક "-1" છે. કાર્ય મૂલ્ય એફ() = 48, જે ભૌમિતિક રીતે ટોચને અનુરૂપ છે ઇ(12; 0) ઉકેલ બહુકોણ (ફિગ. 1). અમે યોજનામાં સુધારો કરીએ છીએ.
5. નવી આધારરેખા શોધવી
x 2-કૉલમ અનુમતિપાત્ર છે, ત્યારથી માં એફ-લાઇનમાં સૌથી નાનો નકારાત્મક ગુણાંક "-1" છે x 2-કૉલમ (Δ 2 = -1). સૌથી નાનું Θ શોધવું i: મિનિટ Θ i = મિનિટ(≈ 9, 6, ∞, 24) = 6, તેથી x 4 થી લાઇન - અનુમતિશીલ. અનુમતિશીલ તત્વ "1/2". ચલોની અદલાબદલી x 2 અને xચાર અમે પગલું SHMZhI કરીએ છીએ, અમે ટેબલ બનાવીએ છીએ. 4, અમને એક નવી સંદર્ભ યોજના = (9; 6; 51; 0; 0; 5) મળે છે.
6. શ્રેષ્ઠતા માટે મૂળભૂત યોજના તપાસી રહ્યું છે
એટી એફ-લાઇન, બધા ગુણાંક બિન-નકારાત્મક છે, તેથી, સંદર્ભ યોજના શ્રેષ્ઠ છે. ભૌમિતિક રીતે બિંદુને અનુરૂપ છે ડી(9;6) (ફિગ. 1 જુઓ). શ્રેષ્ઠ યોજના ઉદ્દેશ્ય કાર્ય c.u નું મહત્તમ મૂલ્ય આપે છે.
મુખ્ય LLP ઉકેલવા માટે સિમ્પ્લેક્સ પદ્ધતિનો વિચાર LLP સપોર્ટ સોલ્યુશન્સના સતત સુધારણામાં સમાવે છે.
સિમ્પ્લેક્સ પદ્ધતિ લખવાની ઘણી રીતો છે.
- સિમ્પ્લેક્સ પદ્ધતિનું મૂળ સ્વરૂપ;
- સિમ્પ્લેક્સ ટેબલના સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ;
- સંશોધિત સિમ્પ્લેક્સ પદ્ધતિ;
- સ્તંભાકાર સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ;
- પંક્તિ સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ.
ચાલો નીચેની અવરોધ શરતો હેઠળ ઉદ્દેશ્ય કાર્ય F(X) = 3x 1 +5x 2 +4x 3 ની મહત્તમ કિંમત વ્યાખ્યાયિત કરીએ.
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0.05x 1 +0.02x 2 +0.02x 3 ≤120
3x1 +x2 +2x3 ≤8000
પ્રથમ સંદર્ભ યોજના બનાવવા માટે, અમે વધારાના ચલો (પ્રમાણિક સ્વરૂપમાં સંક્રમણ) રજૂ કરીને સમીકરણોની સિસ્ટમમાં અસમાનતાની સિસ્ટમ ઘટાડીએ છીએ.
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
સિમ્પ્લેક્સ પદ્ધતિની મૂળભૂત સૂચના
| બિન-મૂળભૂત ચલો દ્વારા મૂળભૂત ચલોને વ્યક્ત કરીને ઉકેલ હાથ ધરવામાં આવે છે: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
સિમ્પ્લેક્સ ટેબલના સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ
સોલ્યુશન સિમ્પ્લેક્સ ટેબલના સ્વરૂપમાં હાથ ધરવામાં આવે છે. ફોર્મ કમ્પ્યુટર પર કમ્પ્યુટિંગ માટે રચાયેલ છે. કૃત્રિમ આધારનો ઉપયોગ કરતી વખતે, ખાસ નંબર M નો ઉપયોગ થાય છે (સામાન્ય રીતે 10000).| યોજના | આધાર | એટી | x 1 | x2 | x 3 | x4 | x5 | x6 | મિનિટ |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| અનુક્રમણિકા રેખા | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| અનુક્રમણિકા રેખા | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| અનુક્રમણિકા રેખા | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
સંશોધિત સિમ્પ્લેક્સ પદ્ધતિ
| ગુણાંક મેટ્રિક્સ A = a ij મેટ્રિક્સ b. |
સ્તંભાકાર સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ
| અમે સિમ્પ્લેક્સ પદ્ધતિના સ્તંભાકાર સ્વરૂપમાં પસાર કરીએ છીએ. અમે દરેક ચલને બિન-મૂળભૂતની દ્રષ્ટિએ વ્યક્ત કરીએ છીએ. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) આ સિસ્ટમ કોષ્ટક T 0 ને અનુરૂપ છે.
|
શબ્દમાળા સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ
પ્રારંભિક સ્વીકાર્ય આધાર તરીકે, આપણે B 0 = લઈ શકીએ છીએ<4, 5, 6>. તે નીચેના કોષ્ટકને અનુરૂપ હશે.
|
સિસ્ટમના ગુણાંકથી બનેલા મેટ્રિક્સ Q કહેવામાં આવે છે સિમ્પ્લેક્સ ટેબલઆધાર B ને અનુરૂપ. સિમ્પ્લેક્સ ટેબ્લો કહેવાય છે સ્વીકાર્ય, અથવા સીધા સ્વીકાર્ય, જો q i0 ≥ 0. સિમ્પ્લેક્સ કોષ્ટક Qની છેલ્લી પંક્તિના તત્વો q i0 કહેવામાં આવે છે સંબંધિત અંદાજો.
કૃત્રિમ આધારની પદ્ધતિ દ્વારા ઉકેલના સ્વરૂપો
ઉદ્દેશ્ય કાર્યમાં રજૂ કરાયેલા કૃત્રિમ ચલોના ઉપયોગ માટે, M નો કહેવાતો દંડ લાદવામાં આવે છે, જે ખૂબ મોટી સકારાત્મક સંખ્યા છે, જે સામાન્ય રીતે ઉલ્લેખિત નથી.પરિણામી આધારને કૃત્રિમ કહેવામાં આવે છે, અને ઉકેલ પદ્ધતિને કૃત્રિમ આધાર પદ્ધતિ કહેવામાં આવે છે.
તદુપરાંત, કૃત્રિમ ચલો કાર્યની સામગ્રી સાથે સંબંધિત નથી, પરંતુ તેઓ તમને પ્રારંભિક બિંદુ બનાવવાની મંજૂરી આપે છે, અને ઑપ્ટિમાઇઝેશન પ્રક્રિયા આ ચલોને શૂન્ય મૂલ્યો લેવા અને શ્રેષ્ઠ ઉકેલની સ્વીકાર્યતાને સુનિશ્ચિત કરવા દબાણ કરે છે.
કૃત્રિમ આધારની પદ્ધતિ દ્વારા ઉકેલના સ્વરૂપો:
- એમ-પદ્ધતિ (સરળ કોષ્ટક);
- બે-તબક્કા અથવા બે-તબક્કાની સિમ્પ્લેક્સ પદ્ધતિ (મૂળભૂત સંકેત, સંશોધિત સિમ્પ્લેક્સ પદ્ધતિ, કૉલમ સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ, રેખા સ્વરૂપમાં સિમ્પ્લેક્સ પદ્ધતિ).
જો સમસ્યાની સ્થિતિમાં ≥ ચિહ્ન સાથે પ્રતિબંધો હોય, તો અસમાનતાના બંને ભાગોને -1 વડે ગુણાકાર કરીને તેને ∑a ji b j સ્વરૂપમાં ઘટાડી શકાય છે. અમે m વધારાના ચલો x n+j ≥0(j =1,m ) રજૂ કરીએ છીએ અને અવરોધોને સમાનતાના સ્વરૂપમાં પરિવર્તિત કરીએ છીએ.
(2)
ચાલો ધારીએ કે સમસ્યાના તમામ પ્રારંભિક ચલો x 1 , x 2 ,..., x n નોનબેઝિક છે. પછી વધારાના ચલો મૂળભૂત હશે, અને અવરોધોની સિસ્ટમ માટે ચોક્કસ ઉકેલ સ્વરૂપ ધરાવે છે
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
આ કિસ્સામાં ધ્યેય કાર્ય F 0 = 0 નું મૂલ્ય હોવાથી, અમે F(x) ને નીચે પ્રમાણે રજૂ કરી શકીએ છીએ:
F(x)=∑c i x i + F 0 =0 (4)
પ્રારંભિક સિમ્પ્લેક્સ કોષ્ટક (સિમ્પ્લેક્સ કોષ્ટક 1) સમીકરણો (2) અને (4) ના આધારે સંકલિત કરવામાં આવે છે. જો વધારાના ચલ x n+j ની આગળ “+” ચિન્હ હોય, જેમ કે (2), તો x i અને મુક્ત શબ્દ b j ની પહેલાના તમામ ગુણાંકો સિમ્પ્લેક્સ કોષ્ટકમાં ફેરફાર કર્યા વિના દાખલ કરવામાં આવે છે. તેના મહત્તમકરણ દરમિયાન ધ્યેય કાર્યના ગુણાંકો વિરુદ્ધ ચિહ્નો સાથે સિમ્પ્લેક્સ કોષ્ટકની નીચેની લાઇનમાં દાખલ કરવામાં આવે છે. સિમ્પ્લેક્સ કોષ્ટકમાં મુક્ત સભ્યો સમસ્યાનું સમાધાન નક્કી કરે છે.
સમસ્યા હલ કરવા માટેનું અલ્ગોરિધમ નીચે મુજબ છે:
1 લી પગલું. મફત સભ્યો કૉલમના તત્વો જોવામાં આવે છે. જો તે બધા હકારાત્મક છે, તો સ્વીકાર્ય મૂળભૂત ઉકેલ મળી ગયો છે અને વ્યક્તિએ અલ્ગોરિધમના પગલા 5 પર આગળ વધવું જોઈએ, જે શ્રેષ્ઠ ઉકેલ શોધવાને અનુરૂપ છે. જો પ્રારંભિક સિમ્પ્લેક્સ ટેબ્લોમાં નકારાત્મક મુક્ત શબ્દો હોય, તો ઉકેલ માન્ય નથી અને તમારે પગલું 2 પર જવું જોઈએ.
2જું પગલું. શક્ય ઉકેલ શોધવા માટે, હાથ ધરવામાં આવે છે, જ્યારે તે નક્કી કરવું જરૂરી છે કે કયા બિન-મૂળભૂત ચલોનો આધારમાં સમાવેશ કરવો અને કયા ચલને આધારમાંથી પાછું ખેંચવું.
કોષ્ટક 1.
| આધાર ચલો | પ્રતિબંધોમાં મુક્ત સભ્યો | બિન-મૂળભૂત ચલો | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| xn+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | એક આરએલ | ... | એક આર.એન |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | a m1 | a m2 | ... | એક મિલી | ... | amn |
| F(x) મહત્તમ | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
આ કરવા માટે, મફત સભ્યોની કૉલમના કોઈપણ નકારાત્મક ઘટકોને પસંદ કરો (તેને b 2 અગ્રણી, અથવા મંજૂરી આપવી. સમસ્યાનો કોઈ ઉકેલ નથી.
તે જ સમયે, પસંદ કરેલ NP x l માં વધારો સાથે ચિહ્ન બદલનાર પ્રથમ ચલને BP માંથી બાકાત રાખવામાં આવે છે. આ x n+r હશે, જેની અનુક્રમણિકા r સ્થિતિ પરથી નક્કી થાય છે
તે ચલ કે જે પસંદ કરેલ અગ્રણી કૉલમના ઘટક સાથે મુક્ત શબ્દના સૌથી નાના ગુણોત્તરને અનુરૂપ છે. આ સંબંધ કહેવાય છે સિમ્પ્લેક્સ સંબંધ. માત્ર હકારાત્મક સિમ્પ્લેક્સ સંબંધો ધ્યાનમાં લેવા જોઈએ.
x n+r ચલને અનુરૂપ સ્ટ્રિંગ કહેવામાં આવે છે અગ્રણી, અથવા પરવાનગી આપે છે. સિમ્પ્લેક્સ કોષ્ટક a rl નું તત્વ, જે અગ્રણી પંક્તિ અને અગ્રણી કૉલમના આંતરછેદ પર છે, તેને અગ્રણી અથવા નિરાકરણ કરનાર તત્વ કહેવામાં આવે છે.અગ્રણી તત્વ શોધવાથી દરેક આગામી સિમ્પ્લેક્સ ટેબ્લો સાથે કાર્ય સમાપ્ત થાય છે.
3જું પગલું. નવા સિમ્પ્લેક્સ કોષ્ટકની ગણતરી કરવામાં આવે છે, જેનાં ઘટકોની ગણતરી પાછલા પગલાના સિમ્પ્લેક્સ કોષ્ટકના ઘટકોમાંથી કરવામાં આવે છે અને તેને પ્રાઇમ સાથે ચિહ્નિત કરવામાં આવે છે, એટલે કે. b" j , a" ji , c" i , F" 0 . તત્વોની ગણતરી નીચેના સૂત્રો અનુસાર કરવામાં આવે છે:
પ્રથમ, પાછલા સિમ્પ્લેક્સ કોષ્ટકમાં જે પંક્તિ અને કૉલમ આગળ હતા તે નવા સિમ્પ્લેક્સ કોષ્ટકમાં ભરવામાં આવશે. અભિવ્યક્તિ (5) નો અર્થ એ છે કે અગ્રણી તત્વના સ્થાને તત્વ a "rl એ અગાઉના સિમ્પ્લેક્સ કોષ્ટકના તત્વના પરસ્પર સમાન છે. પંક્તિ a ri ના ઘટકોને અગ્રણી તત્વ દ્વારા વિભાજિત કરવામાં આવે છે, અને તત્વના ઘટકો કૉલમ a jl ને પણ અગ્રણી તત્વ દ્વારા વિભાજિત કરવામાં આવે છે, પરંતુ વિપરીત ચિહ્ન સાથે લેવામાં આવે છે. તત્વો b" r અને c" l ની ગણતરી સમાન સિદ્ધાંત અનુસાર કરવામાં આવે છે.
બાકીના સૂત્રોનો ઉપયોગ કરીને સરળતાથી લખી શકાય છે.
લંબચોરસ જૂના સિમ્પ્લેક્સ કોષ્ટક અનુસાર એવી રીતે બાંધવામાં આવે છે કે તેના કર્ણમાંથી એક પુનઃગણિત (a ji) અને અગ્રણી (a rl) તત્વો (ફિગ. 1) દ્વારા રચાય છે. બીજો કર્ણ અનન્ય રીતે નિર્ધારિત છે. નવું તત્વ a "ji શોધવા માટે, અગ્રણી તત્વ દ્વારા વિભાજિત વિપરીત કર્ણના ઘટકોનું ઉત્પાદન એ તત્વ a ji માંથી બાદ કરવામાં આવે છે (આ કોષ પર" - "ચિહ્ન દ્વારા સૂચવવામાં આવે છે). તેવી જ રીતે, તત્વો b" j, (j≠r) અને c" i પુનઃગણતરી કરવામાં આવે છે, (i≠l).
4થું પગલું. નવા સિમ્પ્લેક્સ કોષ્ટકનું વિશ્લેષણ એલ્ગોરિધમના 1લા પગલાથી શરૂ થાય છે. જ્યાં સુધી શક્ય મૂળભૂત ઉકેલ ન મળે ત્યાં સુધી ક્રિયા ચાલુ રહે છે, એટલે કે. મફત સભ્યોની કૉલમના તમામ ઘટકો હકારાત્મક હોવા જોઈએ.
5મું પગલું. અમે માનીએ છીએ કે સ્વીકાર્ય મૂળભૂત ઉકેલ મળી ગયો છે. અમે ધ્યેય કાર્ય F(x) ની રેખાના ગુણાંકને જોઈએ છીએ. સિમ્પ્લેક્સ કોષ્ટકની શ્રેષ્ઠતાની નિશાની એ F-પંક્તિમાં બિન-મૂળભૂત ચલો માટે ગુણાંકની બિન-નકારાત્મકતા છે.
ચોખા. 1. લંબચોરસ નિયમ
જો એફ-પંક્તિના ગુણાંકમાં નકારાત્મક હોય છે (મુક્ત શબ્દના અપવાદ સાથે), તો તમારે બીજા મૂળભૂત ઉકેલ પર જવાની જરૂર છે. ધ્યેય કાર્યને મહત્તમ કરતી વખતે, આધારમાં બિન-મૂળભૂત ચલોનો સમાવેશ થાય છે (ઉદાહરણ તરીકે, x l), જેની કૉલમ સિમ્પ્લેક્સ કોષ્ટકની નીચેની પંક્તિમાં ઋણ ગુણાંક c l ના મહત્તમ સંપૂર્ણ મૂલ્યને અનુરૂપ છે. આ તમને ચલ પસંદ કરવા દે છે જેનો વધારો લક્ષ્ય કાર્યમાં સુધારો તરફ દોરી જાય છે. ચલ x l ને અનુરૂપ કૉલમને અગ્રણી કૉલમ કહેવામાં આવે છે. તે જ સમયે, તે ચલ x n+r ને આધારમાંથી બાકાત રાખવામાં આવે છે, જેનો અનુક્રમણિકા r લઘુત્તમ સિમ્પ્લેક્સ ગુણોત્તર દ્વારા નક્કી કરવામાં આવે છે:
x n+r ને અનુરૂપ પંક્તિને અગ્રણી પંક્તિ કહેવામાં આવે છે, અને સિમ્પ્લેક્સ કોષ્ટકના તત્વ a rl, જે અગ્રણી પંક્તિ અને અગ્રણી કૉલમના આંતરછેદ પર હોય છે, તેને કહેવામાં આવે છે. અગ્રણી તત્વ.
6ઠ્ઠું પગલું. 3 જી પગલામાં નિર્ધારિત નિયમો અનુસાર. પ્રક્રિયા ત્યાં સુધી ચાલુ રહે છે જ્યાં સુધી કોઈ શ્રેષ્ઠ ઉકેલ ન મળે અથવા તે નિષ્કર્ષ પર ન આવે કે તે અસ્તિત્વમાં નથી.
જો અગ્રણી સ્તંભમાં સોલ્યુશનને ઑપ્ટિમાઇઝ કરવાની પ્રક્રિયામાં તમામ ઘટકો બિન-પોઝિટિવ હોય, તો પછી અગ્રણી પંક્તિ પસંદ કરી શકાતી નથી. આ કિસ્સામાં, સમસ્યાના સ્વીકાર્ય ઉકેલોના ક્ષેત્રમાં કાર્ય ઉપરથી અને F મહત્તમ ->&∞થી બંધાયેલ નથી.
જો એક્સ્ટ્રીમમ માટે શોધના આગલા પગલા પર મૂળભૂત ચલોમાંનું એક શૂન્ય બરાબર થઈ જાય, તો અનુરૂપ મૂળભૂત ઉકેલને ડિજનરેટ કહેવામાં આવે છે. આ કિસ્સામાં, કહેવાતા લૂપિંગ થાય છે, જે એ હકીકત દ્વારા વર્ગીકૃત થયેલ છે કે BP નું સમાન સંયોજન ચોક્કસ આવર્તન સાથે પુનરાવર્તિત થવાનું શરૂ કરે છે (આ કિસ્સામાં ફંક્શન Fનું મૂલ્ય સાચવેલ છે) અને તેના પર સ્વિચ કરવું અશક્ય છે. એક નવો સ્વીકાર્ય મૂળભૂત ઉકેલ. લૂપિંગ એ સિમ્પ્લેક્સ પદ્ધતિની મુખ્ય ખામીઓમાંની એક છે, પરંતુ તે પ્રમાણમાં દુર્લભ છે. વ્યવહારમાં, આવા કિસ્સાઓમાં, વ્યક્તિ સામાન્ય રીતે ચલના આધારે દાખલ થવાનો ઇનકાર કરે છે જેની કૉલમ ધ્યેય કાર્યમાં નકારાત્મક ગુણાંકના મહત્તમ સંપૂર્ણ મૂલ્યને અનુરૂપ હોય છે, અને નવા મૂળભૂત ઉકેલની રેન્ડમ પસંદગી કરવામાં આવે છે.
ઉદાહરણ 1. સમસ્યા હલ કરો
મહત્તમ(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)
સિમ્પ્લેક્સ પદ્ધતિ અને ઉકેલ પ્રક્રિયાનું ભૌમિતિક અર્થઘટન આપો.
સમસ્યાના ઉકેલનું ગ્રાફિકલ અર્થઘટન અંજીરમાં બતાવવામાં આવ્યું છે. 2. ધ્યેય કાર્યનું મહત્તમ મૂલ્ય કોઓર્ડિનેટ્સ સાથે ODZP ની ટોચ પર પહોંચી ગયું છે. ચાલો સિમ્પ્લેક્સ કોષ્ટકોનો ઉપયોગ કરીને સમસ્યા હલ કરીએ. અમે બીજા અવરોધને (-1) વડે ગુણાકાર કરીએ છીએ અને અસમાનતાને સમાનતાના સ્વરૂપમાં લાવવા માટે વધારાના ચલો રજૂ કરીએ છીએ, પછી
પ્રારંભિક ચલો x 1 અને x 2 બિન-મૂળભૂત તરીકે લેવામાં આવે છે, અને વધારાના x 3 , x 4 અને x 5ને મૂળભૂત ગણવામાં આવે છે અને અમે એક સિમ્પ્લેક્સ કોષ્ટક (સિમ્પ્લેક્સ કોષ્ટક 2) કમ્પાઇલ કરીએ છીએ. સિમ્પ્લેક્સ કોષ્ટકને અનુરૂપ ઉકેલ. 2, માન્ય નથી; અગ્રણી તત્વ ઉપરના અલ્ગોરિધમના સ્ટેપ 2 અનુસાર દર્શાવેલ અને પસંદ કરેલ છે. આગામી સિમ્પ્લેક્સ ટેબ. 3 સ્વીકાર્ય મૂળભૂત ઉકેલ વ્યાખ્યાયિત કરે છે; 2 અગ્રણી તત્વની રૂપરેખા આપવામાં આવે છે અને સમસ્યાને ઉકેલવા માટેના અલ્ગોરિધમના 5મા પગલા અનુસાર પસંદ કરવામાં આવે છે. ટૅબ. 4 સમસ્યાના શ્રેષ્ઠ ઉકેલને અનુરૂપ છે, તેથી: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F મહત્તમ = 20.
ચોખા. 2. સમસ્યાનું ગ્રાફિકલ સોલ્યુશન
