Prugrammazzioni liniàri

Dâ Wikipedia, la nciclupidìa lìbbira.

A prugrammazzioni liniàri (PL o LP 'nta lingua angrisi) eni dda branca di la ricerca upiratìva ca si occupa di sturiari algurittima ppi prubblema d'uttimizzaziona liniàri Nu prubblema eni dittu liniàri si sia a funzioni ubbiettivu sia li vincola sunu funziona liniàri. 'Nta matimatica, a prugrammazzioni liniàri (LP) eni na ticnuloggìa ppi ottimizzazioni di na funzioni uggittiva liniàri.
Informalmenti a prugrammazziuni liniàri ditermina a manèra p'addicidiri a miegghiu manèra ppi raggiungiri lu miegghiu risultatu (comu, ppa isempiu lu massimu prufittu o lu costu cchiu vaschiu) 'nta nu mudellu matimaticu e data na lista di primessi arrapprisintati di iquazzioni liniàri. A prugrammazzioni liniàri ppo ssiri appricata a diversa campi di studiu.
Cchiu ssai eni iusatu 'nta l'affari e 'nta li situazziona icunomica, ma ppo siri macari usatu ppi prubblema 'ngigniristichi: ppa isempiu trasporta, inirgia, tilicumunicazziona e pruduzziona di beni.

Storia dâ prugrammazzioni liniari[cancia | cancia la surgenti]

Lu prubblema d'arrisovviri nu sistema di iniguaglianzi liniàri accumenza cu Fourier ca strummintau l'iliminazzioni Fourier-Motzkin.
A prugrammazzioni liniàri comu nu mudellu matimaticu s'asviluppau duranti a Sicunna Verra Munniali ppi pianificari li spisi e l'intrati ppi arridurri li costa ppi l'isercitu e 'incrimintari li perditi ppi li nimici.
A statu tinutu ammucciatu finu a lu 1947.
Duoppu a verra nu munzieddu d'industri truvarru sta prugrammazioni utili ppi urganizzarisi uogni gghiornu.

Li funnatura di stu suggettu sunu Leonid Kantorovich, nu matimaticu russu ca asviluppau li prubblema di prugrammazioni liniari 'nta lu 1939, George Dantzig, ca pubbricau lu metudu semprici 'nta lu 1947, John von Neumann, ca asviluppau a tiurìa da dualitati lu stessu annu.
Lu prubblema di prugrammazioni liniàri a statu mustratu ssiri arrisulvibbili 'nta lu tiempu pulinomiali di parti di Leonid Khachiyan 'nta lu 1979, ma na rivuluzzioni pratica e tiorica cumparìu nta lu 1984 quannu Narendra Karmarkar antruducìu lu metudu di lu puntu 'ntiriuri pp'arrisovviri li prubblema di prugrammazziona liniàri.

L'isempiu urigginali di Dantzig 'nta lu truvari a miegghiu accuppiata di 70 pirsuni ppi 70 travagghi simplifica l'utilitati da prugrammazzioni liniàri.
Lu putìri ilabburativu ppi cullaudari tutti li pirmutazziona e sciegghiri a miegghiu situazzioni eni ranni.
Lu nummiru di li cunfigurazziona pussibili eni cchiu ranni di lu nummiru di li particeddi 'nta l'universu.
'Nta ogni casu, siervunu picca sicunna ppi truvari a suluzzioni uttimali 'mpostandu lu prubblema comu nu prubblema liniàri e appricannu lu algurittimu Simplex.
A tiurìa i rarrieri a prugrammazzioni liniàri arriduci drasticamenti lu nummiru di suluzziona uttimali pussibbili ca ana ssiri cuntrullati.

Utilizza[cancia | cancia la surgenti]

A prugrammazzioni liniàri eni un campu di ottimizzazzioni cunsidirevuli ppi diffirenti ragghiuna.
Nu munzieddu di prubblema pratici 'nta a ricerca upirativa ponu ssiri spressi comu prubblmea di prugrammaziona liniàri.
Certi casi spiciàli di prugrammaziona liniàri comu lu prubblema di flussu di riti e li prubblema di flussu di multicumuditati sunu cunzidirati abbastanza 'mpurtanti.

Chissu sintissi a ddiri ca a funzioni ubbiettivu po ssiri macari scritta comu:

F.O.=\sum_{i=1}^{NV}c_i\cdot x_i=\underline{c}^T\underline{x} aviennu 'nnicatu ccu

  • NV lu nummiru di li variabbila ca addiscrivunu lu prubblema;
  • \underline{c} lu vitturi di li cuifficienta dâ funzioni ubbiettivu;
  • \underline{x} lu vitturi di li variabbili.