Vikipedio:Projekto matematiko/Lineara programado

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Lineara programado
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematiko, lineara programado (Longeluda disko) (problemoj, problemas) estas optimumigo (problemoj, problemas) en kiu la (empiria, objektiva) funkcio kaj la (limigoj, limigas) estas ĉiuj lineara.

Lineara programado estas grava kampo de optimumigo por kelkaj kaŭzoj. Multaj praktika (problemoj, problemas) en operaciesploro povas esti esprimita kiel lineara programado (problemoj, problemas). Certaj specialaj okazoj de lineara programado, kiel reta fluo (problemoj, problemas) kaj _multicommodity_ (flui, fluo) (problemoj, problemas) estas (konsiderita, konsideris) grava sufiĉa al havi generita multa esplori sur specialigita (algoritmoj, algoritmas) por ilia solvaĵo. Nombro de (algoritmoj, algoritmas) por alia (klavas, tipoj) de optimumigo (problemoj, problemas) laboro per solvanta Longeluda disko (problemoj, problemas) kiel sub-(problemoj, problemas). Historie, (ideoj, ideas) de lineara programado havi kuraĝigita multaj de la centra (konceptoj, konceptas) de optimumiga teorio, kiel duvarianteco, malkomponaĵo, kaj la graveco de _convexity_ kaj ĝia (ĝeneraligoj, ĝeneraligas).

Enhavo

1 Normo (formo, formi)
- 1.1 Ekzemplo
2 Pligrandigita (formo, formi) (malvigla (formo, formi))
- 2.1 Ekzemplo
3 Duvarianteco
4 Teorio
5 (Algoritmoj, Algoritmas)
- 5.1 (Malfermi, Malfermita) (problemoj, problemas)
6 Entjero (nekonatoj, nekonatas)
7 Vidu ankaŭ jenon:
8 Referencoj
9 Ekstera (ligoj, ligas)

[redaktu] Normo (formo, formi)

Normo (formo, formi) estas la kutima kaj plej intuicia (formo, formi) de priskribanta lineara programada problemo. Ĝi konsistas de jeno tri (partoj, partas):

A lineara funkcio al esti maksimumigita

e.g. maksimumigi

c 1 x 1 + c 2 x 2

Problemo (limigoj, limigas) de jeno (formo, formi)

e.g. $a_{11} x_1 + a_{12} x_2 \le b_1$

$a_{21} x_1 + a_{22} x_2 \le b_2$

$a_{31} x_1 + a_{32} x_2 \le b_3$

Nenegativa (variabloj, variablas)

e.g. $x_1 \ge 0$

$x_2 \ge 0$

La problemo estas kutime esprimita en matrico (formo, formi), kaj tiam iĝas:

maksimumigi $\mathbf{c}^T \mathbf{x}$

kun rezervo pri $\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0$

Alia (formoj, formas), kiel minimumigo (problemoj, problemas), (problemoj, problemas) kun (limigoj, limigas) sur alternativo (formoj, formas), kaj ankaŭ (problemoj, problemas) engaĝante negativa (variabloj, variablas) povas ĉiam esti reskribita enen ekvivalenta problemo en normo (formo, formi).

[redaktu] Ekzemplo

Supozi (tiu, ke, kiu) (pli agrara, bienisto) havas peco de biena lando, diri A kvadrataj kilometroj granda, al esti plantita kun ĉu tritiko aŭ hordeo aŭ iu kombinaĵo de la du. La (pli agrara, bienisto) havas (limigita, limigis) _permissible_ kvanto F de sterko kaj P de _insecticide_ kiu povas esti uzita, ĉiu kies estas postulita en malsamaj kvantoj por unua areo por tritiko (F₁, P₁) kaj hordeo (F₂, P₂). Estu S₁ esti la vendanta prezo de tritiko, kaj S₂ la prezo de hordeo. Se ni signifi la areo plantis kun tritiko kaj hordeo kun x₁ kaj x₂ respektive, tiam la optimala nombro de kvadrataj kilometroj al (plantoj, planto, planti) kun tritiko _vs_ hordeo povas esti esprimita kiel lineara programada problemo:

maksimumigi $S 1 x 1 + S 2 x 2$		(maksimumigi la enenspezo - enenspezo estas la "(empiria, objektiva) funkcio")
kun rezervo pri	$x_1 + x_2 \le A$	(limigo sur tuteca areo)
	$F_1 x_1 + F_2 x_2 \le F$	(limigo sur sterko)
	$P_1 x_1 + P_2 x_2 \le P$	(limigo sur _insecticide_)
	$x_1 \ge 0,\, x_2 \ge 0$	(ne povas (plantoj, planto, planti) negativa areo)

Kiu en matrico (formo, formi) iĝas:

maksimumigi $\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$

kun rezervo pri $\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge 0$

[redaktu] Pligrandigita (formo, formi) (malvigla (formo, formi))

Lineara programado (problemoj, problemas) devas esti konvertita enen pligrandigita (formo, formi) antaŭ estante solvis per la simpleca algoritmo. Ĉi tiu (formo, formi) prezentas nenegativa malvigla (variabloj, variablas) al anstataŭigi ne-egalecoj kun egalecoj en la (limigoj, limigas). La problemo povas tiam esti skribita sur jeno (formo, formi):

Maksimumigi Z en:

$\begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} Z \\ \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}$

$\mathbf{x}, \, \mathbf{x}_s \ge 0$

kie x_s estas la nove prezentis malvigla (variabloj, variablas), kaj Z estas la (variablo, varianta) al esti maksimumigita.

[redaktu] Ekzemplo

La ekzemplo pli supre iĝas kiel sekvas kiam konvertis enen pligrandigita (formo, formi):

maksimumigi $S 1 x 1 + S 2 x 2$		((empiria, objektiva) funkcio)
kun rezervo pri	$x 1 + x 2 + x 3 = A$	(pligrandigita limigo)
	$F 1 x 1 + F 2 x 2 + x 4 = F$	(pligrandigita limigo)
	$P 1 x 1 + P 2 x 2 + x 5 = P$	(pligrandigita limigo)
	$x_1,x_2,x_3,x_4,x_5 \ge 0$

kie $x 3, x 4, x 5$ estas (nenegativa) malvigla (variabloj, variablas).

Kiu en matrico (formo, formi) iĝas:

Maksimumigi Z en:

$\begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0$

[redaktu] Duvarianteco

Ĉiu lineara programada problemo, referis al kiel _primal_ problemo, povas esti konvertita enen ekvivalenta duala problemo. En matrico (formo, formi), ni povas (ekspreso, esprimi) la _primal_ problemo kiel:

maksimumigi $\mathbf{c}^T \mathbf{x}$

kun rezervo pri $\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0$

La ekvivalento duala problemo estas:

minimumigi $\mathbf{y}^T \mathbf{b}$

kun rezervo pri $\mathbf{A}^T \mathbf{y} \ge \mathbf{c}, \, \mathbf{y} \ge 0$

kie y estas uzita anstataŭ x kiel (variablo, varianta) vektoro.

[redaktu] Teorio

Geometrie, la lineara (limigoj, limigas) difini konveksa pluredro, kiu estas (nomita, vokis) la farebla regiono. Ekde la (empiria, objektiva) funkcio estas ankaŭ lineara, ĉiuj loka _optima_ estas aŭtomate malloka _optima_. La lineara (empiria, objektiva) funkcio ankaŭ (implicas, enhavas) (tiu, ke, kiu) optimala solvaĵo povas nur okazi je randa punkto de la farebla regiono.

Estas du (situacioj, situacias) en kiu ne optimala solvaĵo povas troviĝi. Unua, se la (limigoj, limigas) kontraŭdiri unu la alian (ekzemple, x ≥ 2 kaj x ≤ 1) tiam la farebla regiono estas malplena kaj tie povas esti ne optimala solvaĵo, ekde estas ne solvaĵoj ajn. En ĉi tiu (kesto, okazo), la Longeluda disko estas dirita al esti _infeasible_.

Alternative, la pluredro povas esti nebarita direkte al la (empiria, objektiva) funkcio (ekzemple: maksimumigi x₁ + 3 x₂ kun rezervo pri x₁ ≥ 0, x₂ ≥ 0, x₁ + x₂ ≥ 10), en kiu (kesto, okazo) estas ne optimala solvaĵo ekde solvaĵoj kun arbitre alta (valoroj, valoras) de la (empiria, objektiva) funkcio povas esti konstruita.

(Mezuranta, Drinkejanta, Baranta) ĉi tiuj du malnormalaj kondiĉoj (kiu estas ofte (regulita, kriteriita, rektara) ekster per rimedo (limigoj, limigas) integralo al la problemo estante (prezentita, prezentis), kiel pli supre), la optimumo estas ĉiam atingis je vertico de la pluredro. Tamen, la optimumo estas ne bezone unika: ĝi estas ebla al havi aro de optimalaj solvaĵoj (kovranta, kovro) rando aŭ (vizaĝo, edro) de la pluredro, aŭ (ebena, para, eĉ) la tuta pluredro (Ĉi tiu lasta situacio devus okazi se la (empiria, objektiva) funkcio estis konstanto).

[redaktu] (Algoritmoj, Algoritmas)

Serio de lineara (limigoj, limigas) sur du (variabloj, variablas) produktas regiono de ebla (valoroj, valoras) por tiuj (variabloj, variablas). Solvebla (problemoj, problemas) estos havi farebla regiono en la formo de simpla poligono.

La simpleca algoritmo, ellaborita per Georgo _Dantzig_, solvas Longeluda disko (problemoj, problemas) per konstruanta konsentebla solvaĵo je vertico de la pluredro, kaj tiam marŝanta laŭ randoj de la pluredro al verticoj kun sukcese pli alta (valoroj, valoras) de la (empiria, objektiva) funkcio ĝis la optimumo estas atingita. Kvankam ĉi tiu algoritmo estas sufiĉe kompetenta en praktiko, kaj povas esti garantiita al trovi la malloka optimumo se certaj antaŭzorgoj kontraŭ (biciklado, ciklanta) estas prenita, ĝi havas malriĉa plej malbona-(kesto, okazo) konduto: ĝi estas ebla al konstrui lineara programada problemo por kiu la simpleca maniero prenas nombro de (ŝtupoj, ŝtupas, paŝas) eksponenta funkcio en la problema amplekso. Fakte por iu tempa ĝi estis ne sciata ĉu la lineara programada problemo estis NP-pleneco aŭ solvebla en polinoma tempo.

La unua plej malbona-(kesto, okazo) polinomo-tempa algoritmo por la lineara programada problemo estis proponita per _Leonid_ _Khachiyan_ en 1979. Ĝi estis bazita sur la elipsoida maniero en nelineara optimumigo per _Naum_ _Shor_, kiu estas la ĝeneraligo de la elipsoida maniero en konveksa optimumigo per _Arkadi_ _Nemirovski_, 2003 John von Neumann Teoria Premio _winner_, kaj Don/Doña _Yudin_.

Tamen, la praktika (seanco, rendimento) de _Khachiyan_'s algoritmo estas elreviganta: ĝenerale, la simpleca maniero estas pli kompetenta. Ĝia ĉefa graveco estas (tiu, ke, kiu) ĝi kuraĝigis la esplori de enaj punktaj manieroj. En kontrasto al la simpleca algoritmo, kiu nur pliboniĝoj laŭ punktoj sur la rando de la farebla regiono, enaj punktaj manieroj povas movi tra la eno de la farebla regiono.

En 1984, N. _Karmarkar_ proponis la projekcia maniero. Ĉi tiu estas la unua algoritmo plenumante bone ambaŭ en teorio kaj en praktiko: Ĝia plej malbona-(kesto, okazo) komplekseco estas polinomo kaj (eksperimentoj, eksperimentas) sur praktika (problemoj, problemas) montri (tiu, ke, kiu) ĝi estas laŭkaŭze kompetenta (komparita, komparis) al la simpleca algoritmo. Ekde tiam, multaj enaj punktaj manieroj havi estas proponita kaj analizis. Populara ena punkta maniero estas la _Mehrotra_ antaŭdirilo-_corrector_ maniero, kiu plenumas bonege en praktiko (ebena, para, eĉ) kvankam malgranda estas sciata pri ĝi teorie.

La aktuala opinio estas (tiu, ke, kiu) la rendimento de bona (realigoj, realigas) de simpleca-bazitaj manieroj kaj enaj punktaj manieroj estas simila por rutinaj aplikoj de lineara programado.

Longeluda disko (solviloj, solvas) estas en vasta uzi por optimumigo de diversaj (problemoj, problemas) en industrio, kiel optimumigo de (flui, fluo) en transporto (retoj, retas), multaj kies povas esti konvertita enen lineara programado (problemoj, problemas) nur kun iu malfacilaĵo.

[redaktu] (Malfermi, Malfermita) (problemoj, problemas)

Polinomo pivoti maniero por Longeluda disko (ne-simpleca, e.g., _criss_-kruci)
Forte polinoma maniero por Longeluda disko
Polinoma algoritmo por Longeluda disko en la reela nombra modelo de kalkulado
Polinoma diametra konjekto sur multedra (grafikaĵoj, grafeoj)
- _Hirsch_ (lineara diametro) konjekto sur multedra (grafikaĵoj, grafeoj)
- Polinoma simpleca maniero por Longeluda disko

[redaktu] Entjero (nekonatoj, nekonatas)

Se la nekonato (variabloj, variablas) estas ĉiuj postulis al esti (entjeroj, entjeras), tiam la problemo estas (nomita, vokis) entjera programado (_IP_) aŭ entjera lineara programado (_ILP_) problemo. En kontrasto al lineara programado, kiu povas esti solvita kompetente en la plej malbona (kesto, okazo), entjera programado (problemoj, problemas) estas en la plej malbona (kesto, okazo) nedecidebla, kaj en multaj praktika (situacioj, situacias) (tiuj kun barita (variabloj, variablas)) NP-peza. 0-1 entjera programado estas la speciala okazo de entjera programado kie (variabloj, variablas) estas postulita al esti 0 aŭ 1 (iom ol ajna (entjeroj, entjeras)). Ĉi tiu maniero estas ankaŭ (klasifikis, klasigita) kiel NP-peza, kaj fakte la decida versio estis unu de _Karp_'s 21 NP-pleneco (problemoj, problemas).

Se nur iu de la nekonato (variabloj, variablas) estas postulita al esti (entjeroj, entjeras), tiam la problemo estas (nomita, vokis) (miksita, miksis) entjera programado (_MIP_) problemo. Ĉi tiuj estas ĝenerale ankaŭ NP-peza.

Estas tamen iuj gravaj subklasoj de _IP_ kaj _MIP_ (problemoj, problemas) (tiu, ke, kiu) estas kompetente solvebla, plej rimarkinde (problemoj, problemas) kie la limiga matrico estas tutece _unimodular_ kaj la dekstraj flankoj de la (limigoj, limigas) estas entjero.

Plibonigita (algoritmoj, algoritmas) por solvantaj entjeraj linearaj programoj inkluzivi:

branĉo kaj baro
branĉo kaj tranĉo
branĉo kaj prezo
se la problemo havas iu superflua strukturo, ĝi (majo, povas) ebli al apliki malfruigita kolumna generacio.

[redaktu] Vidu ankaŭ jenon:

Simpleca algoritmo, kutima solvi Longeluda disko (problemoj, problemas)
(Ŝirmi, Ombro) prezo
_MPS_ (fajli, kolono, dosiero, paperujo, fajlilo) aranĝo
Longeluda diska ekzemplo, Laboro (Butikumi, Butiko) problemo

Solvilo enpakas

_AIMMS_
_SYMPHONY_
_MINTO_
_XPRESS_
_CPLEX_
GNU Lineara Programada Garnituro
_Qoca_
Vidu ankaŭ jenon: la "Ekstera (ligoj, ligas)" sekcio pli sube

[redaktu] Referencoj

Aleksander _Schrijver_: "Teorio de Lineara kaj Entjera Programado". Johano _Wiley_ kaj (Filoj, Fas). 1998.
Tomaso H. Cormen-a, Karlo E. _Leiserson_, _Ronald_ L. _Rivest_, kaj _Clifford_ Stein-a. Enkonduko al (Algoritmoj, Algoritmas), (Sekundo, Dua) Redakcio. _MIT_ Premi kaj _McGraw_-Monteto, 2001. ISBN 0262032937. Ĉapitro 29: Lineara Programado, _pp_.770–821.
_A6_: _MP1_: _INTEGER_ _PROGRAMMING_, _pg_.245.

[redaktu] Ekstera (ligoj, ligas)

Programaro

_AIMMS_ Optimumigo Modelanta _AIMMS_ — inkluzivi lineara programado en industriaj solvaĵoj (libera prova permesilo havebla);
_COIN_-_OR_ — _COmputational_ _INfrastructure_ por (Operacioj, Operacias) Esplori, (malfermi, malfermita)-fonta biblioteko
_Cplex_ — Komerca biblioteko por lineara programado
[http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html _HOPDM_
_LINGO_ — Longeluda disko, _IP_, Malloka solvilo/modelanta lingvo
Lineara Programada Ilo
_lp__solvi
_MOSEK_ — Optimumiga programaro por Longeluda disko, _QP_, _MIP_, _SOCP_ kaj pli
Aĝia Solvilo — _Spreadsheet_ adicii-en
(Tia, Kia) Plej bona! — _Spreadsheet_ adicii-en
_Xpress_-_MP_ — Optimumiga programaro libera al studentoj
_GIPALS_ — Lineara programada ĉirkaŭaĵo kaj dinamike bindebla biblioteko (Dinamike bindebla biblioteko)
_DecisionPro_ Lineara Programada Optimumiga Programaro
_QSopt_ Optimumiga programaro por Longeluda disko (libera por esplori (celoj, celas)).

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Lineara_programado_59ab.html"

Kategorioj: Artikoloj por polurado kaj movo | Optimumigo | Matematiko

We provide Linux to the World

Vikipedio:Projekto matematiko/Lineara programado

El Vikipedio

Enhavo

[redaktu] Normo (formo, formi)

[redaktu] Ekzemplo

[redaktu] Pligrandigita (formo, formi) (malvigla (formo, formi))

[redaktu] Ekzemplo

[redaktu] Duvarianteco

[redaktu] Teorio

[redaktu] (Algoritmoj, Algoritmas)

[redaktu] (Malfermi, Malfermita) (problemoj, problemas)

[redaktu] Entjero (nekonatoj, nekonatas)

[redaktu] Vidu ankaŭ jenon:

[redaktu] Referencoj

[redaktu] Ekstera (ligoj, ligas)

Views

Navigado

Serĉu

Aliaj lingvoj