border=0


Typen fan dûbele lineêre programmearring taken




Elke ZPP kin, op in bepaalde wize, in oare taak ferienigje, dûrde de dûbel (of konjugat ) neffens it orizjinele probleem.

Bysûnder in foarbyld sjen litte hoe't ferskate problemen yn 'e echte ekonomyske situaasje ferskine oan beide lineêre programmearproblemen. By in bepaalde ûndernimmer nei de ferfolling fan it jierplan, ûntstie de fraach - wat te dwaan mei de oerbleaunen fan grûnstoffen? It bestjoer en ekonomen fan it bedriuw hie twa oplossings: it ferkeapjen fan de resten fan 'e grûnstoffen fan guon organisaasje yn need (de maklikste opsje), of om de produksje fan guon produkten op eigen apparaat te fêstigjen fan' e oerbleaune grûnstoffen.

Foar ienfâldigens ferwyt wy dat der twa soarten fan raw materials S 1 en S 2 binne , de oerbleaunen binne dêrby respektivelik en ienheden. Ut dit raw materiaal is it mooglik om de produksje fan trije soarten soarten foarsjenningen te meitsjen: T 1 , T 2 , T 3. Fan it ferkeap fan ien ienheid fan elke soarte fan produkt T 1 , T 2 , T 3, sil it bedriuw in respekt krije , , cu De konsumpsje-tariven fan grûnstoffen foar de produksje fan wagen T 1 , T 2 , T 3 tegearre mei gegevens oer profiten en fermogen binne presintearre yn de neikommende tabel wêr't betsjut hoefolle ienheden fan grûnstoffen ferbrutsen op 'e produksje fan soarten .

Typen fan soarten S 1 S 2 Profit
T 1
T 2
T 3
Stocks

Wy sille de trein fan gedachten folgje fan 'e ekonomy fan it bedriuw. As al neamde, moasten se twa mooglikheden analysearje.

Yn it ûndersyk fan 'e twadde mooglikheid (om de frijwilligers fan' e saak T 1 , T 2 , T 3 ) te passen, komt de fraach oer it plan foar graduaten. It frijlizzingsplan is definiearre troch trije nûmers. wêr - it oantal items te meitsjen ( ). Unbekend moat it resource constraint system befredigje

(8.1)

en it winst dat it bedriuw sil ûntfange fan 'e útfiering fan it optimale plan foar de frijlitting fan guod moat maksimearre wurde:

. (8.2)

Dêrom, om it beste brûken fan 'e twadde mooglikheid te meitsjen, is it nedich om it linear programmearprobleem (8.1), (8.2) op te lossen.

Wy sjogge no de earste kâns op - te ferkeapjen fan grûnstoffen nei in oare organisaasje. Hjir ûntstiet de fraach: op hokker prizen de rohstoffen te ferkeapjen? Besykje dizze prizen wêr - de priis foar in ienheid fan raw material S i ( ).

De juste priisfeardigens fan 'e ferkeapjende bedriuw is sa folget. As wy de grûnstoffen nimme foar de produksje fan in commodity unit T i ( ), dan sil de ynkomsten fan har ferkeap net minder wêze as de winst fan 'e ferkeap fan' e fertroude produkt (oars is it gjin sin foar ferkeap fan grûnstoffen - it is better om in produkt út te meitsjen en it profitearjen fan dat te meitsjen). Dizze fereaske liedt ta in systeem fan ûngelikens


border=0


(8.3)

De earste skriftlike ûngemakheid yn it systeem (8.3) betsjut dat it opbringt fan 'e ferkeap ienheden fan soarchynstruminten S 1 en ienheden fan soarchynstruminten S 2 (krekt dizze bedrach fan grûnstoffen wurdt brûkt foar de produksje fan in ienheid fan wittenskip T 1 ) net minder as de winst dat in bedriuw ûntfange koe fan it ferkeapjen fan ienheid fan 'e saak T 1 as it it idee ferkeapjen fan rohstoffen en te hawwen oan it fabrikjen fan soarten fan it T 1 , T 2 , T 3 . De oerbliuwende twa ûngelikens hawwe in ferlykbere betsjutting.

Hoe foar de keaper is de iennichste winsk foar him om de kosten te krijen foar it kopjen fan grûnstoffen nei in minimum:

. (8.4)

Dus, foar it optimaal brûken fan 'e earste kâns is it nedich om it linear programmearprobleem (8.3) op te lossen (8.4).

Foar dúdlikens fergelykje wy it wurding fan 'e twa taken:

Problem (8.1), (8.2) Task (8.3), (8.4)
( ) ( ),

Problem (8.1), (8.2) en probleem (8.3), (8.4) yn lineêre programmearring wurde dualen freonen nei in freon neamd. It probleem (8.1), (8.2) wurdt it direkte probleem neamd.

Besykje de basistypen fan twa lineêre programmearproblemen. Lit it direkte lineêre programmearprobleem it formulier hawwe

,

.

Wy skriuwe dit probleem yn matrixfoarm

, , , (8.5)

wêr - kolomfektor fan 'e objektive funksje-koeffizienten, - kolomfektor fan fariabele fariabelen - koeffizientmatrix foar it behearen fan fariabelen, - kolomfektor fan fergese leden.

Dan is it oerienkommende dûbel lineêre programmearprobleem oan it direkte probleem (8.5) it formulier

, , , (8.6)

wêr - kolomfektor fan fariabele fariabelen fan it dûbel probleem.



Definition 8.1. In pear rjochtline (8.5) en twa (8,6) LPP wurdt symmetrisch neamd .

Symmetrike dûbele LPPs wurde kompilearre as allinich alle tekens binne yn it direkte ferbiningsysteemsysteem of alle tekens allinich .

Wy prate in algoritme foar it bouwen fan symmetrysk Dual LPP .

1) Foar elke ymmigraasje fan it ferbânsysteem fan 'e direkte LPP (8.5), ferienigje in nonnegative fariabele (it oantal kontrolearringen fan it dûbel probleem is lyk oan it oantal funksjonele konflikten fan it direkte probleem.

2) As de koeffizienten fan 'e objektive funksje Dual zlup nimme fergees leden Constraintsystemen fan it direkte probleem.

3) Optimisaasje rjochting (type ekstreme) fan 'e objektive funksje Dûbele opsjes tsjinoer de rjochting fan optimisaasje fan 'e objektive funksje fan it direkte probleem (as it direkte probleem op it maksimum wie, dan it duale probleem op it minimum, en oarsom).

4) Lit - Matrix fan koeffizienten fan it konfiguraasjesysteem fan direkte LPP . Krij de koeffizientmatrix fan it systeem fan beheiningen fan 'e dual LPP fan' e matrix transposysje: . It oantal konflikten yn it beheiningsysteem fan 'e dual LPP is lyk oan it getal variable direkte zlp .

5) As de frije leden fan it beheiningsysteem fan it duale probleem, nim de koeffisynten fan 'e objektive funksje fan it direkte probleem.

6) Yn 'e twalich taak fan maksimaal set de tekens yn foar alle ûngelikens-kontrasten, yn it probleem fan minimum - .

Foarbyld 8.1. Bouwe in dûbel LPP foar de taak

.

It beslút. De matrix yngongfoarm fan dizze LPP hat de foarm (sjoch (8.5))

,

wêr - kolomfektor fan 'e objektive funksjonele koeffizienten ,

- kolomfektor fan fariabele fariabelen - koeffizientmatrix foar it behearen fan fariabelen, - kolomfektor fan fergese leden.

Dan sil de oerienkommende DZLP skreaun wurde as (sjoch (8.6))

wêr - kolomfektor fan fariabele fariabelen fan it dûbel probleem.

Tink de LPP fan 'e kanonike foarm yn' e matrixfoarm

, , . (8.7)

Dan hat de oerienkommende Dual LPP nei (8.7) it formulier

, , (8.8)

wêr - de kolomfektor fan kontrolearringen fan it dûbel probleem, mei de komponinten yn it algemiene gefal fan in willekeurige teken (ynklusyf in negative teken).

Definition 8.2. In pear rjochtline (8,7) en dual (8.8) LPP wurdt asymmetrisch neamd .

Definition 8.3. In pear direkte en duale LPP wurdt mingd neamd as it ferbânsysteem fan it streekprobleem hat sawol strikte lykwols tekeningen (= teken) en , .

By it kompilearjen fan in mingde pear dualtaken, wurde se begelaat troch in algoritme foar it komponearjen fan in symmetryske pear. As de funksjonele beheining fan it streekprobleem hat in ungelikens teken dan moat de fariabele fan 'e twalige probleem, dy' t oerienkomme mei dizze beheining, net as negative beskôge wurde. As de funksjonele beheining fan it direkte probleem lykweardich is, dan kin de oerienkommende fariant fan it dûbel probleem as positive en negative wearden nimme.

Foarbyld 8.2. Bouwe in dûbel LPP foar de taak

,

It beslút. De oerienkommende DZLP hat it formulier

.





; Datum tafoege: 2018-01-21 ; ; Views: 283 ; Is it publisearre materiaal it urheberrecht? | | Persoanlike data beskerming | ORDER WORK


Hast net fûn wat jo sochten? Brûk it sykjen:

De bêste wurden: Allinne in dream komt oan in studint oan 'e ein fan in lêzing. En in oar snapt him fuort. 8492 - | 7328 - of alles lêze ...

2019 @ edudocs.fun

Sidegegevens oer: 0.006 sek.