"Prugrammazzioni liniàri" : Diffirenzi ntrê virsioni
Contenuto cancellato Contenuto aggiunto
n + Category:Uttimizzazziuni matimàtica (catigurìa) |
iditazzioni di l'articulu... |
||
Riga 2:
{{S|matematica}}
-->
A '''prugrammazzioni
<!-- troppu difficili -->
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 [[ottimizzazzioni (matimatica)|ottimizzazioni]] di na [[funzioni uggittiva]] [[liniàri]].<br>
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.
<!--
More formally, given a [[polytope]] (for example, a [[polygon]] or a [[polyhedron]]), and a [[real number|real]]-valued [[affine function]]
: <math>f(x_1, x_2, \dots, x_n)=c_1x_1+c_2x_2+\cdots +c_nx_n+d\,</math>
defined on this polytope, a linear programming method will find a point in the polytope where this function has the smallest (or largest) value. Such points may not exist, but if they do, searching through the polytope vertices is guaranteed to find at least one of them.
Linear programs are problems that can be expressed in [[canonical form]]:
: Maximize <math> \mathbf{c}^T \mathbf{x} </math>
: Subject to <math>A\mathbf{x} \leq \mathbf{b}.</math>
<math>\mathbf{x}</math> represents the vector of variables (to be determined), while <math>\mathbf{c}</math> and <math>\mathbf{b}</math> are vectors of (known) coefficients and <math>\mathbf{A}</math> is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function (<math>\mathbf{c}^T \mathbf{x} </math> in this case). The equations <math>A\mathbf{x} \leq \mathbf{b}</math> are the constraints which specify a [[Convex set|convex polyhedron]] over which the objective function is to be optimized.
-->
A prugrammazzioni liniàri ppo ssiri appricata a diversa campi di studiu.<br>
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.<br>
<!--
A statu pruvatu utili ppi diversti tipi di mudellazziona ppa pianificazzioniIt has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.
-->
==Storia dâ prugrammazzioni liniari==
Lu prubblema d'arrisovviri nu sistema di iniguaglianzi liniàri accumenza cu [[Joseph Fourier|Fourier]] ca strummintau l'iliminazzioni Fourier-Motzkin.<br>
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.<br>
A statu tinutu ammucciatu finu a lu [[1947]].<br>
Duoppu a verra nu munzieddu d'industri truvarru sta prugrammazioni utili ppi urganizzarisi uogni gghiornu.<br>
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 [[algurittimu simplex|metudu semprici]] 'nta lu 1947, [[John von Neumann]], ca asviluppau a tiurìa dwho developed the theory of the duality in the same year. The linear programming problem was first shown to be solvable in polynomial time by [[Leonid Khachiyan]] in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when [[Narendra Karmarkar]] introduced a new [[interior point method]] for solving linear programming problems.
Dantzig's original example of finding the best assignment of 70 people to 70 jobs exemplifies the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the Simplex algorithm. The theory behind linear programming drastically reduces the number of possible optimal solutions that must be checked.
==Uses==
Linear programming is a considerable field of optimization for several reasons. Many practical problems in [[operations research]] can be expressed as linear programming problems. Certain special cases of linear programming, such as ''network flow'' problems and ''multicommodity flow'' problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as ''duality,'' ''decomposition,'' and the importance of ''convexity'' and its generalizations. Likewise, linear programming is heavily used in [[microeconomics]] and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can boil down to linear programming problems.
Chissu sintissi a ddiri ca a funzioni ubbiettivu po ssiri macari scritta comu:<br>
Line 14 ⟶ 47:
*<math>\underline{x}</math> lu vitturi di li variabbili.
<!-- mucciai picchini mi pari troppu difficili
Aisistunu ttri granni classa di prubblema liniari:
Line 52 ⟶ 87:
-->
[[Category:Uttimizzazziuni matimàtica]]
| |||