Lexicographic optimization
લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન એ એક પ્રકારનું મલ્ટી-ઓબ્જેક્ટિવ ઓપ્ટિમાઇઝેશન છે. સામાન્ય રીતે, બહુ-ઉદ્દેશ્ય ઓપ્ટિમાઇઝેશન એક સાથે ઓપ્ટિમાઇઝ કરવા માટે બે અથવા વધુ ઉદ્દેશ્ય કાર્યો સાથે ઓપ્ટિમાઇઝેશન સમસ્યાઓ સાથે વ્યવહાર કરે છે. ઘણીવાર, વિવિધ ઉદ્દેશોને નિર્ણય લેનારા માટે મહત્વના ક્રમમાં ક્રમાંકિત કરી શકાય છે, જેથી તે ઉદ્દેશ સૌથી મહત્વપૂર્ણ હોય, ઉદ્દેશ્ય આગામી સૌથી મહત્વપૂર્ણ હોય, અને તેથી વધુ. લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન ધારે છે કે નિર્ણય લેનાર તેમાં ખૂબ જ નાનો વધારો, વગેરેમાં ખૂબ મોટો વધારો પણ પસંદ કરે છે. તેવી જ રીતે, નિર્ણય લેનાર ખૂબ જ નાનો વધારો, ખૂબ મોટો વધારો વગેરે પસંદ કરે છે. બીજા શબ્દોમાં કહીએ તો, નિર્ણય લેનાર પાસે લેક્સિકોગ્રાફિક પસંદગીઓ હોય છે, જે સંભવિત ઉકેલોને તેમના ઉદ્દેશ્ય કાર્ય મૂલ્યોના લેક્સિકોગ્રાફિક ક્રમ અનુસાર ક્રમ આપે છે. લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશનને કેટલીકવાર પ્રિએમ્પ્ટિવ ઓપ્ટિમાઇઝેશન કહેવામાં આવે છે, કારણ કે એક ઉદ્દેશ્ય મૂલ્યમાં થોડો વધારો ઓછા મહત્વપૂર્ણ ઉદ્દેશ્ય મૂલ્યોમાં ઘણો મોટો વધારો કરે છે. ઉદાહરણ તરીકે, એવી પેઢીનો વિચાર કરો જે સલામતીને સૌથી ઉપર રાખે છે. તે તેના કામદારો અને ગ્રાહકોની સલામતી વધારવા માંગે છે. મહત્તમ શક્ય સલામતી પ્રાપ્ત કરવાને આધીન, તે મહત્તમ નફો મેળવવા માંગે છે. આ પેઢી લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન કરે છે, જ્યાં સલામતી સૂચવે છે અને નફો સૂચવે છે. અન્ય એક ઉદાહરણ તરીકે, પ્રોજેક્ટ મેનેજમેન્ટમાં, PERT નેટવર્ક્સનું વિશ્લેષણ કરતી વખતે, ઘણીવાર સરેરાશ સમાપ્તિ સમયને ઓછો કરવા માંગે છે, અને આને આધિન, સમાપ્તિ સમયના તફાવતને ઓછો કરે છે. એક લેક્સિકોગ્રાફિક મહત્તમકરણ સમસ્યાને ઘણીવાર આ રીતે લખવામાં આવે છેઃ મહત્તમ કરવાના કાર્યો ક્યાં છે, સૌથી વધુથી ઓછામાં ઓછા મહત્વપૂર્ણ સુધી ક્રમબદ્ધ; નિર્ણય ચલોનો વેક્ટર છે; અને તે શક્ય સમૂહ છે-શક્ય મૂલ્યોનો સમૂહ. લેક્સિકોગ્રાફિક લઘુતમ સમસ્યાને સમાન રીતે વ્યાખ્યાયિત કરી શકાય છે. અલ્ગોરિધમ્સ લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે ઘણા અલ્ગોરિધમ્સ છે. સામાન્ય ઉદ્દેશ્યો માટે ક્રમિક અલ્ગોરિધમ n ઉદ્દેશ્યો સાથેની લેક્સિમિન ઓપ્ટિમાઇઝેશન સમસ્યાને n સિંગલ-ઓબ્જેક્ટિવ ઓપ્ટિમાઇઝેશન સમસ્યાઓના ક્રમનો ઉપયોગ કરીને ઉકેલી શકાય છે, જે નીચે મુજબ છેઃ t = 1 માટે, n નીચેની સિંગલ-ઓબ્જેક્ટિવ સમસ્યાનું સમાધાન કરે છેઃ જો સમસ્યા અવ્યવહારુ અથવા અમર્યાદિત હોય, તો બંધ કરો અને જાહેર કરો કે તેનો કોઈ ઉકેલ નથી. નહિંતર, શ્રેષ્ઠ ઉકેલનું મૂલ્ય મૂકો અને ચાલુ રાખો. તેથી, પ્રથમ પુનરાવર્તનમાં, આપણે સૌથી મહત્વપૂર્ણ ઉદ્દેશ્યનું મહત્તમ શક્ય મૂલ્ય શોધીએ છીએ, અને આ મહત્તમ મૂલ્યને તેમાં મૂકીએ છીએ. બીજા પુનરાવર્તનમાં, આપણે બીજા સૌથી મહત્વપૂર્ણ ઉદ્દેશ્યનું મહત્તમ શક્ય મૂલ્ય શોધીએ છીએ, જેમાં વધારાના અવરોધ સાથે કે જે સૌથી મહત્વપૂર્ણ ઉદ્દેશ તેના મહત્તમ મૂલ્યને જાળવી રાખવો જોઈએ; વગેરે. ક્રમિક અલ્ગોરિધમ સામાન્ય છે-જ્યારે પણ આપણી પાસે સિંગલ-ઓબ્જેક્ટિવ ફંક્શન્સ માટે સોલ્વર હોય ત્યારે તેને લાગુ કરી શકાય છે. રેખીય હેતુઓ માટે લેક્સિકોગ્રાફિક સિમ્પ્લેક્સ અલ્ગોરિધમ રેખીય લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન એ લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશનનો એક વિશેષ કેસ છે જેમાં ઉદ્દેશો રેખીય હોય છે, અને શક્ય સમૂહને રેખીય અસમાનતાઓ દ્વારા વર્ણવવામાં આવે છે. તેને આ રીતે લખી શકાય છેઃ મહત્તમ કરવા માટેના રેખીય ઉદ્દેશોનું પ્રતિનિધિત્વ કરતા વેક્ટર ક્યાં છે, સૌથી ઓછા મહત્વપૂર્ણથી ક્રમબદ્ધ; નિર્ણય ચલોનું વેક્ટર છે; અને શક્ય સમૂહ મેટ્રિક્સ અને વેક્ટર દ્વારા નક્કી કરવામાં આવે છે. ઇસર્મેને રેખીય પ્રોગ્રામિંગ દ્વૈતતાના સિદ્ધાંતને લેક્સિકોગ્રાફિક રેખીય કાર્યક્રમો સુધી વિસ્તાર્યો અને લેક્સિકોગ્રાફિક સિમ્પ્લેક્સ અલ્ગોરિધમનો વિકાસ કર્યો. ક્રમિક અલ્ગોરિધમથી વિપરીત, આ સિમ્પ્લેક્સ અલ્ગોરિધમ એક સાથે તમામ ઉદ્દેશ્ય કાર્યોને ધ્યાનમાં લે છે. રેખીય ઉદ્દેશ્યો માટે ભારિત સરેરાશ શેરાલી અને સોયસ્ટર સાબિત કરે છે કે, કોઈપણ રેખીય લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન સમસ્યા માટે, વજનનો એક સમૂહ અસ્તિત્વમાં છે જેમ કે લેક્સિકોગ્રાફિકલી-શ્રેષ્ઠ ઉકેલોનો સમૂહ નીચેની એક-ઉદ્દેશ્ય સમસ્યાના ઉકેલોના સમૂહ સાથે સમાન છેઃ વજનની ગણતરી કરવાની એક રીત યાગર દ્વારા આપવામાં આવી છે. તેઓ ધારે છે કે તમામ ઉદ્દેશ્ય મૂલ્યો 0 અને 1 વચ્ચેની વાસ્તવિક સંખ્યાઓ છે, અને કોઈપણ બે સંભવિત મૂલ્યો વચ્ચેનો સૌથી નાનો તફાવત અમુક અચળાંક d <1 છે (જેથી d કરતા નાના તફાવતવાળા મૂલ્યોને સમાન ગણવામાં આવે). પછી, તેનું વજન આશરે નક્કી કરવામાં આવે છે. આ ખાતરી આપે છે કે ભારિત રકમને મહત્તમ કરવી એ લેક્સિકોગ્રાફિક મહત્તમકરણની સમકક્ષ છે. કોકોસિઓની, પાપ્પાલાર્ડો અને સેર્ગેયેવ દર્શાવે છે કે, કોમ્પ્યુટરને જોતાં જે અનંત સાથે આંકડાકીય ગણતરીઓ કરી શકે છે, તે વજન પસંદ કરવાનું શક્ય છે જે અનંત છે (ખાસ કરીનેઃ; અનંત છે; અનંત-ચોરસ છે; વગેરે. ), અને આમ રેખીય લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશનને અનંત સાથે સિંગલ-ઉદ્દેશ્ય રેખીય પ્રોગ્રામિંગમાં ઘટાડે છે. તેઓ અનંત માટે સિમ્પ્લેક્સ અલ્ગોરિધમનો અનુકૂલન રજૂ કરે છે, અને કેટલાક ચાલી રહેલા ઉદાહરણો રજૂ કરે છે. ગુણધર્મો (1) વિશિષ્ટતા. સામાન્ય રીતે, લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન સમસ્યામાં એક કરતાં વધુ શ્રેષ્ઠ ઉકેલ હોઈ શકે છે. જો કે, જો અને બે શ્રેષ્ઠ ઉકેલો છે, તો તેમનું મૂલ્ય બધા માટે સમાન હોવું જોઈએ. વધુમાં, જો શક્ય ક્ષેત્ર બહિર્મુખ સમૂહ હોય, અને ઉદ્દેશ્ય કાર્યો સખત રીતે અંતર્મુખ હોય, તો સમસ્યાનો મહત્તમ એક શ્રેષ્ઠ ઉકેલ હોય છે, કારણ કે જો બે અલગ-અલગ શ્રેષ્ઠ ઉકેલો હોય, તો તેમનો સરેરાશ અન્ય શક્ય ઉકેલ હશે જેમાં ઉદ્દેશ્ય કાર્યો ઉચ્ચ મૂલ્ય પ્રાપ્ત કરે છે-જે મૂળ ઉકેલોની શ્રેષ્ઠતાને વિરોધાભાસી બનાવે છે. (2) આંશિક રકમ. ઓપ્ટિમાઇઝ કરવા માટે ફંક્શન્સના વેક્ટરને જોતાં, 1,., n માં તમામ t માટે, વ્યાખ્યાયિત કરો = સૌથી મહત્વપૂર્ણ થી t-th સૌથી મહત્વપૂર્ણ સુધીના તમામ ફંક્શન્સનો સરવાળો. પછી, મૂળ લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશન સમસ્યા નીચેની સમકક્ષ છેઃ કેટલાક કિસ્સાઓમાં, બીજી સમસ્યાનું સમાધાન કરવું સરળ હોઈ શકે છે. આ પણ જુઓ લેક્સિકોગ્રાફિક મહત્તમ-લઘુતમ ઓપ્ટિમાઇઝેશન એ લેક્સિકોગ્રાફિક ઓપ્ટિમાઇઝેશનનો એક પ્રકાર છે જેમાં તમામ ઉદ્દેશો સમાન રીતે મહત્વપૂર્ણ છે, અને ધ્યેય સૌથી નાના ઉદ્દેશ્યને મહત્તમ કરવાનો છે, પછી બીજા સૌથી નાના ઉદ્દેશ્ય, અને તેથી વધુ. રમત સિદ્ધાંતમાં, ન્યુક્લિયોલસને લેક્સિકોગ્રાફિકલી-મિનિમલ સોલ્યુશન સેટ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. સંદર્ભો બહુવિધ-માપદંડ નિર્ણય વિશ્લેષણ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ