Configuration linear program
રૂપરેખાંકન રેખીય પ્રોગ્રામ (રૂપરેખાંકન-એલ. પી.) એ એક રેખીય પ્રોગ્રામિંગ તકનીક છે જેનો ઉપયોગ સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે થાય છે. તે કટીંગ સ્ટોક સમસ્યાના સંદર્ભમાં રજૂ કરવામાં આવી હતી. પાછળથી, તે બિન પેકિંગ અને જોબ શેડ્યુલિંગ સમસ્યાઓ પર લાગુ કરવામાં આવ્યું છે. રૂપરેખાંકન-એલ. પી. માં, દરેક સંભવિત રૂપરેખાંકન માટે એક ચલ છે-વસ્તુઓનો દરેક સંભવિત બહુવિધ સમૂહ જે એક જ ડબ્બામાં ફિટ થઈ શકે છે (આ રૂપરેખાંકનોને પેટર્ન તરીકે પણ ઓળખવામાં આવે છે). સામાન્ય રીતે, સમસ્યાના કદમાં રૂપરેખાંકનોની સંખ્યા ઘાતાંકીય હોય છે, પરંતુ કેટલાક કિસ્સાઓમાં રૂપરેખાંકનોની માત્ર બહુપદી સંખ્યાનો ઉપયોગ કરીને અંદાજિત ઉકેલો મેળવવાનું શક્ય છે. બિન પેકિંગમાં અભિન્ન એલ. પી. બિન પેકિંગની સમસ્યામાં, વિવિધ કદની n વસ્તુઓ હોય છે. ધ્યેય વસ્તુઓને ઓછામાં ઓછી સંખ્યામાં ડબ્બામાં પેક કરવાનો છે, જ્યાં દરેક ડબ્બામાં મહત્તમ બી હોઈ શકે છે. શક્ય રૂપરેખાંકન એ કદનો સમૂહ છે જેનો સરવાળો મહત્તમ B છે. ઉદાહરણોઃ ધારો કે વસ્તુનું કદ 3,3,3,3,3,4,4,4,4,4, અને B = 12 છે. પછી સંભવિત રૂપરેખાંકનો છેઃ 3333; 333; 33,334,344; 4,44,444. જો આપણી પાસે કદ 3 ની માત્ર ત્રણ વસ્તુઓ હોત, તો આપણે 3333 રૂપરેખાંકનનો ઉપયોગ કરી શક્યા ન હોત. S દ્વારા વિવિધ કદના સમૂહને (અને તેમની સંખ્યા) દર્શાવો. C દ્વારા વિવિધ રૂપરેખાંકનો (અને તેમની સંખ્યા) નો સમૂહ દર્શાવો. S માં દરેક કદ s અને C માં રૂપરેખાંકન c માટે, સૂચવોઃ ns-કદ s ની વસ્તુઓની સંખ્યા. તરીકે, c-રૂપરેખાંકનમાં કદ s ની ઘટનાઓની સંખ્યા c. xc-રૂપરેખાંકન c સાથે ડબ્બાની સંખ્યાને સૂચવતો ચલ. પછી, બિન-પેકિંગનું રૂપરેખાંકન LP છેઃ S માં તમામ s માટે (-કદ s ની તમામ ns વસ્તુઓ પેક કરવામાં આવે છે). સી માં તમામ સી માટે (-એકંદરે વધુમાં વધુ એન ડબ્બા હોય છે, તેથી દરેક વ્યક્તિગત રૂપરેખાંકનમાં વધુમાં વધુ એન). રૂપરેખાંકન એલ. પી. એક પૂર્ણાંક રેખીય પ્રોગ્રામ છે, તેથી સામાન્ય રીતે તે એન. પી.-હાર્ડ છે. વધુમાં, સમસ્યા પોતે પણ સામાન્ય રીતે ખૂબ મોટી હોય છેઃ તેમાં C ચલ અને S અવરોધો હોય છે. જો સૌથી નાની વસ્તુનું કદ eB હોય (કેટલાક અપૂર્ણાંક e માટે (0,1)), તો પછી દરેક બિનમાં 1/e વસ્તુઓ હોઈ શકે છે, તેથી રૂપરેખાંકનોની સંખ્યા C ~ S1/e, જે ખૂબ મોટી હોઈ શકે જો e નાની હોય (જો e ને અચળાંક ગણવામાં આવે, તો પૂર્ણાંક LP ને સંપૂર્ણ શોધ દ્વારા ઉકેલી શકાય છેઃ ત્યાં મહત્તમ S1/e રૂપરેખાંકનો છે, અને દરેક રૂપરેખાંકન માટે મહત્તમ n સંભવિત મૂલ્યો છે, તેથી તપાસવા માટે મોટાભાગના સંયોજનો છે. દરેક સંયોજન માટે, આપણે S અવરોધો તપાસવા પડશે, તેથી રન-ટાઇમ છે, જે n માં બહુપદી છે જ્યારે S, e અચળ હોય છે). જો કે, આ આઇએલપી કેટલાક અંદાજિત અલ્ગોરિધમ્સ માટે આધાર તરીકે કામ કરે છે. આ અલ્ગોરિધમ્સનો મુખ્ય વિચાર મૂળ ઉદાહરણને નવા ઉદાહરણમાં ઘટાડવાનો છે જેમાં S નાનો છે અને e મોટો છે, તેથી C પ્રમાણમાં નાનો છે. પછી, આઇએલપીને કાં તો સંપૂર્ણ શોધ દ્વારા ઉકેલી શકાય છે (જો એસ, સી પૂરતા પ્રમાણમાં નાના હોય તો), અથવા તેને અપૂર્ણાંક એલપીમાં ઢીલ આપીને. અપૂર્ણાંક એલ. પી. બિન-પેકિંગનું અપૂર્ણાંક રૂપરેખાંકન એલ. પી. તે ઉપરોક્ત આઇ. એલ. પી. ની રેખીય પ્રોગ્રામિંગ છૂટછાટ છે. તે છેલ્લા અવરોધને અવરોધ સાથે બદલે છે. બીજા શબ્દોમાં કહીએ તો, દરેક રૂપરેખાંકનનો અપૂર્ણાંક સંખ્યામાં ઉપયોગ કરી શકાય છે. છૂટછાટ સૌપ્રથમ ગિલમોર અને ગોમોરી દ્વારા રજૂ કરવામાં આવી હતી, અને તેને ઘણીવાર ગિલમોર-ગોમોરી રેખીય કાર્યક્રમ કહેવામાં આવે છે. ઉદાહરણ તરીકેઃ ધારો કે ત્યાં કદ 3 ની 31 વસ્તુઓ અને કદ 4 ની 7 વસ્તુઓ છે, અને બિન-કદ 10 છે. રૂપરેખાંકનો છેઃ 4,44,34,334,33,333. અવરોધો છે [0,0,1,2,1,2,3] * x = 31 અને [1,2,1,1,0,0,0] * x = 7. અપૂર્ણાંક એલ. પી. નો શ્રેષ્ઠ ઉકેલ છે [0,0,0,7,0,0,17/3] એટલે કેઃ રૂપરેખાંકન 334 ના 7 ડબ્બા અને રૂપરેખાંકન 333 ના 17/3 ડબ્બા છે. નોંધ લો કે માત્ર બે અલગ અલગ રૂપરેખાંકનોની જરૂર છે. ટૂંકમાં, અપૂર્ણાંક LP ને નીચે પ્રમાણે લખી શકાય છેઃ જ્યાં 1 એ કદ C નો વેક્ટર (1,., 1) છે, A એ S-by-C મેટ્રિક્સ છે જેમાં દરેક સ્તંભ એક જ રૂપરેખાંકનને રજૂ કરે છે, અને n એ વેક્ટર (n1,., nS) છે. અપૂર્ણાંક એલ. પી. ને ઉકેલવું કોઈ અભિન્નતાના અવરોધો વગરનો એક રેખીય પ્રોગ્રામ ચલ અને અવરોધોની સંખ્યામાં સમય બહુપદીમાં ઉકેલી શકાય છે. સમસ્યા એ છે કે અપૂર્ણાંક રૂપરેખાંકન એલ. પી. માં ચલની સંખ્યા સંભવિત રૂપરેખાંકનોની સંખ્યા જેટલી છે, જે વિશાળ હોઈ શકે છે. કરમરકર અને કાર્પ એક એલ્ગોરિધમ રજૂ કરે છે જે આ સમસ્યાને દૂર કરે છે. પ્રથમ, તેઓ અપૂર્ણાંક એલ. પી. ના દ્વિ રેખીય કાર્યક્રમનું નિર્માણ કરે છેઃ તેમાં એસ ચલ y1,., yS, અને C અવરોધો છેઃ દરેક રૂપરેખાંકન c માટે, એક અવરોધ છે, જ્યાં એ ની કોલમ રૂપરેખાંકન c નું પ્રતિનિધિત્વ કરે છે. દરેક કદ s માટે, આપણે બિન-નકારાત્મક કિંમત ys નક્કી કરવી જોઈએ. અમારો નફો એ તમામ વસ્તુઓની કુલ કિંમત છે. અમે દરેક રૂપરેખાંકનમાં વસ્તુઓની કુલ કિંમત મહત્તમ 1 છે તે મર્યાદાઓને આધિન નફાને મહત્તમ કરવા માંગીએ છીએ. બીજું, તેઓ લંબગોળ પદ્ધતિનો એક પ્રકાર લાગુ કરે છે, જેમાં તમામ અવરોધોની યાદી આપવાની જરૂર નથી-તેને માત્ર એક અલગ ઓરેકલની જરૂર છે. સેપરેશન ઓરેકલ એ એક અલ્ગોરિધમ છે, જે વેક્ટર y આપવામાં આવે છે, તે ક્યાં તો ભારપૂર્વક જણાવે છે કે તે શક્ય છે, અથવા તે ઉલ્લંઘન કરે છે તે અવરોધ શોધે છે. ડ્યુઅલ એલ. પી. માટે સેપરેશન ઓરેકલને માપ s અને મૂલ્યો y સાથે નૅપસેક સમસ્યાને હલ કરીને અમલમાં મૂકી શકાય છેઃ જો નૅપસેક સમસ્યાના શ્રેષ્ઠ ઉકેલનું કુલ મૂલ્ય વધુમાં વધુ 1 હોય, તો y શક્ય છે; જો તે 1 કરતા મોટું હોય, તો y શક્ય નથી, અને નૅપસેક સમસ્યાનો શ્રેષ્ઠ ઉકેલ તે રૂપરેખાંકનને ઓળખે છે જેના માટે બંધનું ઉલ્લંઘન કરવામાં આવ્યું છે. ત્રીજું, તેઓ દર્શાવે છે કે, નૅપસેક સમસ્યાના અંદાજિત ઉકેલ સાથે, કોઈ પણ વ્યક્તિ ડ્યુઅલ એલ. પી. નો અંદાજિત ઉકેલ મેળવી શકે છે, અને આમાંથી, પ્રાથમિક એલ. પી. નો અંદાજિત ઉકેલ; કરમરકર-કાર્પ બિન પેકિંગ અલ્ગોરિધમ્સ જુઓ. એકંદરે, કોઈપણ સહિષ્ણુતા પરિબળ એચ માટે, મહત્તમ એલઓપીટી (આઈ) + એચ પર ખર્ચનો મૂળભૂત શક્ય ઉકેલ શોધે છે, અને સમયસર ચાલે છેઃ, જ્યાં એસ એ વિવિધ કદની સંખ્યા છે, એન એ વિવિધ વસ્તુઓની સંખ્યા છે, અને સૌથી નાની વસ્તુનું કદ ઇબી છે. ખાસ કરીને, જો e ≤1/n અને h = 1 હોય, તો અલ્ગોરિધમ સમયે મહત્તમ LOPT + 1 ડબ્બો સાથે ઉકેલ શોધે છેઃ આ અલ્ગોરિધમનો રેન્ડમાઇઝ્ડ પ્રકાર અપેક્ષિત સમયમાં ચાલે છેઃ અપૂર્ણાંક એલ. પી. ને ગોળાકાર કરીને કરમરકર અને કાર્પે અપૂર્ણાંક એલ. પી. ને અભિન્ન એલ. પી. ના અંદાજિત ઉકેલમાં ગોળાકાર કરવાની રીત વિકસાવી; કરમરકર-કાર્પ બિન પેકિંગ અલ્ગોરિધમ્સ જુઓ. તેમનો પુરાવો દર્શાવે છે કે આ એલ. પી. નું એડિટિવ ઇન્ટિગ્રેલિટી ગેપ ઓ (લોગ 2 (એન)) માં છે. પાછળથી, હોબર્ગ અને રોથવોસે તેમના પરિણામમાં સુધારો કર્યો અને સાબિત કર્યું કે અખંડિતતાનું અંતર ઓ (લોગ (એન)) માં છે. ઇન્ટિગ્રાલિટી ગેપ પર સૌથી વધુ જાણીતી લોઅર બાઉન્ડ એ કોન્સ્ટન્ટ ω (1) છે. ચોક્કસ અખંડિતતાનું અંતર શોધવું એ એક ખુલ્લી સમસ્યા છે. બિન આવરણમાં બિન આવરણ સમસ્યામાં, વિવિધ કદની n વસ્તુઓ હોય છે. ધ્યેય વસ્તુઓને મહત્તમ સંખ્યામાં ડબ્બામાં પેક કરવાનો છે, જ્યાં દરેક ડબ્બામાં ઓછામાં ઓછો બી હોવો જોઈએ. આ સમસ્યા માટે કુદરતી રૂપરેખાંકન એલ. પી. હોઈ શકે છેઃ જ્યાં એ ઓછામાં ઓછા બી ના સરવાળા સાથે વસ્તુઓની તમામ રૂપરેખાંકનોને રજૂ કરે છે (એક માત્ર સમાવેશ-ન્યૂનતમ રૂપરેખાંકનો લઈ શકે છે). આ એલ. પી. સાથે સમસ્યા એ છે કે, બિન-આવરણની સમસ્યામાં, નાની વસ્તુઓનું સંચાલન કરવું સમસ્યારૂપ છે, કારણ કે શ્રેષ્ઠ ઉકેલ માટે નાની વસ્તુઓ જરૂરી હોઈ શકે છે. નાની વસ્તુઓની મંજૂરી સાથે, કરમરકર અને કાર્પની તકનીક માટે પણ ગોઠવણીની સંખ્યા ખૂબ મોટી હોઈ શકે છે. સિરિક, જ્હોનસન અને કેન્યોન વૈકલ્પિક એલ. પી. રજૂ કરે છે. પ્રથમ, તેઓ વસ્તુઓના સમૂહને વ્યાખ્યાયિત કરે છે જેને નાની કહેવામાં આવે છે. ધારો કે T એ તમામ નાની વસ્તુઓનું કુલ કદ છે. પછી, તેઓ એક મેટ્રિક્સ A બનાવે છે જે સરવાળો <2 સાથે તમામ રૂપરેખાંકનો રજૂ કરે છે. પછી, તેઓ ઉપરોક્ત એલ. પી. ને એક વધારાના અવરોધ સાથે ધ્યાનમાં લે છેઃ વધારાની અવરોધ બાંયધરી આપે છે કે ડબ્બામાં "ખાલી જગ્યા" નાની વસ્તુઓ દ્વારા ભરી શકાય છે. આ એલ. પી. નું દ્વૈત વધુ જટિલ છે અને તેને સરળ નૅપસેક-પ્રોબ્લેમ સેપરેશન ઓરેકલ દ્વારા ઉકેલી શકાતું નથી. સિરિક, જ્હોનસન અને કેન્યોન તેને લગભગ 1/એપ્સિલોનમાં સમય ઘાતાંકીયમાં ઉકેલવા માટે એક અલગ પદ્ધતિ રજૂ કરે છે. જેનસેન અને સોલિસ-ઓબા તેને લગભગ 1/એપ્સિલોનમાં સમય ઘાતાંકીયમાં ઉકેલવા માટે એક સુધારેલી પદ્ધતિ રજૂ કરે છે. મશીન શેડ્યુલિંગમાં અસંબંધિત-મશીનોના શેડ્યુલિંગની સમસ્યામાં, કેટલાક અલગ-અલગ મશીનો છે જે કેટલીક અલગ-અલગ નોકરીઓ પર પ્રક્રિયા કરે છે. જ્યારે મશીન i જોબ જે પર પ્રક્રિયા કરે છે, ત્યારે તે પાઈ, જે સમય લે છે. ધ્યેય એ છે કે કામોને મશીનો વચ્ચે એવી રીતે વહેંચવામાં આવે કે મશીનનો મહત્તમ પૂર્ણતાનો સમય શક્ય તેટલો ઓછો હોય. આ સમસ્યાનું નિર્ણય સંસ્કરણ છેઃ આપેલ સમય T, શું એવું કોઈ પાર્ટીશન છે જેમાં તમામ મશીનો પૂર્ણ થવાનો સમય મહત્તમ T હોય? દરેક મશીન i માટે, નોકરીઓના ઘણા બધા ઉપગણ હોય છે જેની પ્રક્રિયા મશીન i દ્વારા મહત્તમ T સમયે કરી શકાય છે. આવા દરેક ઉપગણને મશીન i માટે રૂપરેખાંકન કહેવામાં આવે છે. Ci (T) દ્વારા મશીન i માટે તમામ રૂપરેખાંકનોના સમૂહને દર્શાવો, સમય T આપવામાં આવે છે. Ci (T) માં દરેક મશીન i અને રૂપરેખાંકન c માટે, ચલ વ્યાખ્યાયિત કરો જે મશીન i માં વપરાયેલ વાસ્તવિક રૂપરેખાંકન c છે, અને અન્યથા 0 છે. પછી, એલ. પી. ની મર્યાદાઓ છેઃ 1,., m માં દરેક મશીન માટે; 1,., n માં દરેક જોબ માટે; દરેક i, j માટે. ગુણધર્મો બિનસંબંધિત-મશીનોના સમયપત્રક માટે રૂપરેખાંકન-LPનું અભિન્ન અંતર 2 છે. હાઇ-મલ્ટિપ્લિસિટી બિન પેકિંગ સંદર્ભો બિન પેકિંગ નંબર પાર્ટીશનિંગ જોબ શેડ્યૂલિંગ લીનિયર પ્રોગ્રામિંગ પણ જુઓ.