[Megoldva] teljesítmény elosztás erőművek között

Algoritmusok

Sziasztok,
az alábbi egyszerű teljesítmény-elosztásra szeretnék ötleteket kapni:

van n darab erőmű. Az n darab erőmű között kéne szétosztani p teljesítményt. Az erőműveknek van súlyozása, azaz szeretnénk, ha ez alapján a súlyozás alapján osztanák el a teljesítményt egymás között.
A nehézség, hogy van az erőműveknek max. teljesítménye, illetve hogy nem képződhet maradék (az összes teljesítményt fel kell használni, se többet, se kevesebbet, azaz az osztásból eredő kerekítési hibát a végén szét kell kenni az erőművek között).

Példák:
Igényelt: 3000
Erőmű 1. (max. telj. 2000) - súly 1/3 = 3000 * 1/3 = 1000
Erőmű 2. (max. telj. 3000) - súly 2/3 = 3000 * 2/3 = 2000 (ez ok)

Igényelt: 5001
Erőmű 1. (max. telj. 3000) - súly 1/3 = 6000 * 1/3 = 1667
Erőmű 2. (max. telj. 3000) - súly 2/3 = 6000 * 2/3 = 3334 (nem ok, mert átléptük a max. teljesítményt, pedig ki tudtuk volna elégíteni az igényt ha az Erőmű 1.-et tovább húzzuk)

Igényelt: 3950
Erőmű 1. (max. telj. 2000) - súly 1/3 = 3950 * 1/3 = 1316
Erőmű 2. (max. telj. 3000) - súly 2/3 = 3950 * 2/3 = 2633 (majdnem ok, de a kerekítésekből adódoan még hozzá kell adni 1-et valamelyik erőműhöz, amelyiknek maradt szabad kapacitása, jelen esetben mindegy melyikhez )

Szerkesztve (ez sikerült hétvégén):

http://pastebin.com/E4Wdp821

Még majd a setPlantsRatio()-s részt még átnézem, nem vagyok benne biztos, hogy a súlyozást újra kell e számolni a ciklusban.
Mindenkinek köszönöm a segítséget, és az ötleteket!

  • 2890 megtekintés

( WG | 2014. 12. 06., szo – 21:47 )

Én úgy csinálnám, hogy
E2 = Erőmű_2_max * 2/3 * Igény
Ha ( E2 ) > Erőmű_2_max, akkor E2 = Erőmű_2_max
E1 = Igény - E2

Azt nem vizsgáltuk, hogy Igény nem nagyobb-e, mint az össz. erőmű max teljesítményének az összege, de ez nem is volt feladat. :) 

openSUSE 13.1 x86_64.

Akárhány erőmű lehet. Az erőműveknek van egy maximális teljesítménye, ami erőművenként van definiálva és persze állandó, azért vettel lejjebb az erőmű teljesítményét a második példában, hogy ne lehessen könnyen elosztani az első módszerrel.

Minden esetre köszi az ötletet!

( STP | 2014. 12. 06., szo – 22:33 )

Specifikáció hiányos.
Mi az eljárás abban az esetben, ha a súllyal számított teljesítmény eredő magasabb az adott entitás maximális teljesítményénél?
A differencia hogyan oszlik meg a többi entitás között? Mert az ugye egyértelmű, hogy az eredeti felosztás már nem érvényes.
Persze, vélhetőleg újra kell súlyozni a korábbi súlyokat -a kiesőt kivonva, maximális teljesítménnyel számolva- a képletből, csak le is kéne írni.

Van szabadságod, hogyan súlyozod, minél életszerűbb, annál jobb. Ha nem tudod kielégíteni az adott teljesítményt akkor szerintem az a legjobb (gondolom én, nem vagyok energetikus), hogy kielégítesz annyit amennyit csak tudsz (felhúzod max-ra az erőműveket).
A feladatot lehet bonyolítani tovább, de inkább egyszerűsíteni szeretném (pl.: erőműnek van minimális teljesítménye is, kikapcsolható-e, szabályozható-e az adott erőmű).
Sőt, úgy tudom hogy az erőművek egy menetrendet kapnak az adott napra, negyedórás beosztásokkal, és nyilván olyan dolgokat is figyelembe kell venni hogy ne legyen nagy ugrálás a menetrendben az egymást követő negyedórák közötti teljesítményekben, szóval ez tényleg egy végtelenül leegyszerűsített példa.
Ezenkívül olyan is van, hogy ha nem tudod kielégíteni az adott igényt gazdaságosan, akkor licitálsz a szomszédos ország erőművének fölös kapacitására.

( mrceeka v | 2014. 12. 06., szo – 23:48 )

Valami ilyesmi, nem ellenőriztem teljesen. 


Vegyünk egy skalárt, benne az erőművek számával, n.
Vegyünk egy vektort, benne minden erőmű max teljesítménye, pmax[], n elemű.
Vegyünk egy vektort, benne minden erőmű súlya, súlyok[], n elemű.
Vegyünk egy vektort, benne a kiosztott kapacitás minden erőműre, kiosztott[], n elemű, kezdeti értékei 0-k.
Vegyünk egy skalárt, benne az igényelt kapacitással, igény.
Vegyünk egy skalárt, benne az összesített súly, összsúly, kezdeti értéke 1.
Vegyünk egy listát, benne az összes erőmű sorszáma, akinek van szabad kapacitása, szabadok(), kezdeti értékei az egész számok 1..n.
Vegyünk egy skalárt, benne az elosztatlan kapacitással, maradóigény.
Vegyünk egy skalárt, benne a még szabad erőművek összesített súlyával, maradóösszsúly.
Vegyünk egy logikai értéket, ami mutatja a kiosztás sikerét, sikeres, kezdeti értéke IGAZ.
végéntesztelő ciklus
  maradóigény:=0
  maradóösszsúly:= összsúly
  számlálós ciklus, menjünk végig egy ciklusban szabadok() elemein, i vegye fel az aktuális elem értékét.
	jutna egy helyi skalár változó.
	jutna:=igény*súlyok[i]/összsúly
	többlet egy helyi skalár változó.
	többlet:=kiosztott[i]+jutna-pmax[i]
	Ha többlet>0 akkor
		maradóigény+=többlet
		maradóösszsúly-=súlyok[i]
		kiosztott[i]:=pmax[i]
		i-t töröljük a szabadok() listáról.
	különben
		kiosztott[i]+=jutna
	elág vége
  számlálós ciklus vége
  összsúly:= maradóösszsúly
  igény:= maradóigény
  Ha szabadok() elemszáma 0, akkor
    sikeres:=HAMIS
  elág vége
végéntesztelős ciklus vége, kilépés a ciklusból, ha maradóigény=0 vagy sikeres=HAMIS		
Ha sikeres=HAMIS, akkor 
  üzenünk, hogy nem sikerült a dolog,
különben
  kiosztott[] tartalmazza az eredményt.
elág vége.

Megoldásom azt feltételezi, hogy az első kiosztási kör után a szabad kapacitással maradó erőművek közt a maradó kiosztandó igényt a a(z eredetileg meghatározott) súlyaik arányában osztjuk ki továbbra is.

Üdv,
Marci

perl deszkamodell, bedrótozott adatokkal: 


$n = 4;
@pmax = ( 750, 750, 2000, 1200 );
@sulyok = ( 0.25, 0.25, 0.25, 0.25 );
@kiosztott = ( 0, 0, 0, 0 );
$igeny = 4000;
$osszsuly = 1;
%szabadok = ( 0, 0, 1, 1, 2, 2, 3, 3 );
$sikeres = 1;
do {
  $maradoigeny = 0;
  $maradoosszsuly = $osszsuly;
  foreach $i (keys %szabadok) {
    $jutna = $igeny*$sulyok[$i]/$osszsuly;
    $tobblet = $kiosztott[$i]+$jutna-$pmax[$i];
    if ($tobblet > 0) {
      $maradoigeny += $tobblet;
      $maradoosszsuly -= $sulyok[$i];
      $kiosztott[$i] = $pmax[$i];
      delete $szabadok{$i};
    }
    else {
      $kiosztott[$i]+= $jutna;
    }
  }
  $osszsuly = $maradoosszsuly;
  $igeny = $maradoigeny;
  if (scalar(keys %szabadok) eq 0) {
    $sikeres = 0;
  }
} until (($maradoigeny eq 0) or !$sikeres);
if (!$sikeres) {
  print "Sikertelen kiosztas.\n";
}
else {
  print "Sikeres kiosztas, az egyes eromuvek kapacitasa rendre:\n";
  for ($j=0; $j<$n; $j++) {
    print $kiosztott[$j]."\n";
  }   
}

Üdv,
Marci

( Szenti v | 2014. 12. 06., szo – 23:43 )

Szerintem elrontottad a második példádat:

Igényelt: 6000
Erőmű 1. (max. telj. 2000) - súly 1/3 = 6000 * 1/3 = 2000
Erőmű 2. (max. telj. 3000) - súly 2/3 = 6000 * 2/3 = 4000(nem ok, mert átléptük a max. teljesítményt, pedig ki tudtuk volna elégíteni az igényt ha az Erőmű 1.-et maxra felhúzzuk)

Ebben az esetben 6000 Wattot nem szolgálhatnak ki az erőművek. Ellenben a példád magyarázó szövege megfelelő lenne, ha 5000 W lenne az igény: ekkor a súlyozás miatt az első erőmű 1/3 * 5000 Watt ~= 1666.6 Wattot kellene vigyen, a második pedig 2/3 * 5000 Watt = 3333 Wattot, amit nem lehetséges, mert 3000 Watt a max teljesítménye; tehát mindkét erőművet csúcsra járatva (2000 Watt + 3000 Watt = 5000 Watt) a feladatnak van megoldása.

Ellenben a specifikációd hiányos: pontosítsd kérlek, hogy mit értesz az alatt, hogy nem képződhet maradék! Azt jelenti, hogy nem lehet eltérni a súlyozott értéktől? Tehát az nem megoldás, ha a harmadik példánál először a súlyozott értékeket vesszük (1316 Watt és 2633 Watt), majd az elsőhöz hozzáadunk 1 Watt teljesítményt?

Köszi, igen elrontottam, javítom.
El lehet térni az adott aránytól, de mivel törtszámokkal számolunk, ezért maradt az a maradék, amivel igazából annyi valóban a teendő - amit írtál is- hogy hozzá kel adni valamelyik erőműhöz, amelyiknek még maradt kapacitása, implementációtól függően.

( joco01 v | 2014. 12. 06., szo – 23:53 )

Kerekítésről nem írtál, úgyhogy vegyük úgy, hogy tört számok is játszanak, ha esetleg kerekíteni kell, akkor a végén azt "szét kell kenni".

Nevezzük PLim-nek azt a teljesítményt, amit még ki lehet osztani úgy, hogy minden erőmű a súlyának megfelelő terhelést kap. PMax[] legyenek a max teljesítmények, W[] a súlyok. Ezt tudjuk felírni minden egyes erőműre:

PLim*W[i]/SUM(W[])<=PMax[i]

Átrendezve:

PLim<=PMax[i]/W[i]*SUM(W[])

Ha pl. PMax[]=2000,3000 és W[]=2,1, akkor:

i=0 esetén PLim<=3000, i=1 esetén PLim<=9000, tehát a legnagyobb PLim=3000. Ennél az igénynél P[0]=2000, P[1]=1000, tehát fennáll a 2:1 súlyozás. A 0. sorszámú erőmű maxon jár, ő "húzza le" a többit.

Tehát 0..3000 összteljesítmény esetén minden erőmű a saját súlya szerint van járatva, persze leosztva arányosan a limittől kisebb összigény esetén. Tehát pl. 1500 igény esetén P[0]=2000*1500/3000=1000, P[1]=1000*1500/3000=500, pont a fele, mint a limitnél. Sima arányosság, a 2:1 súlyozás megmaradt.

Mi van 3000 felett? Szerintem az lehet életszerű, ha lefutunk egy kört PLim-mel, és ha marad még kiosztatlan teljesítmény, akkor a telített erőműveket vegyük ki a listából, és fussunk neki megint, meg megint. Ha végül elfogytak az erőművek, de még kellene teljesítmény, akkor pedig túl nagy az összigény.

Tehát pl. 4000 igény esetén lefut az algoritmus, P[0]=2000, P[1]=1000, és még ki kell osztani 1000-et. Az első maxon jár, kivesszük, a maradék 1000-et csak a második erőműre tudjuk leosztani, és ő bírja is, tehát P[1]+=1000.

--

Ez nagyon szép leírás. Pont ilyesmire gondoltam én is. Köszönöm.
"Mi van 3000 felett? Szerintem az lehet életszerű, ha lefutunk egy kört PLim-mel, és ha marad még kiosztatlan teljesítmény, akkor a telített erőműveket vegyük ki a listából, és fussunk neki megint, meg megint. Ha végül elfogytak az erőművek, de még kellene teljesítmény, akkor pedig túl nagy az összigény."

Igen, ezt kéne valahogy allegorizálnom, remélem amit leírtál, meg a fentebbi hátultesztelős ciklussal már össze tudom hozni.

( persicsb | 2014. 12. 07., v – 00:04 )

Magyarán te a következő lineáris egyenlőtlenségrendszer feladatot akarod megoldani:
n erőműre ismeretlenek: w_i súlyok, i=1..n
Ismertek: P összteljesítmén, és m_i legnagyobb teljesítmények.
Az egyenlőtlenségek:
summa(w_i) = 1
P*w_i < m_i

Ez utóbbi egyenlőtlenségeket átalakíthatjuk egyenletekké, n db új ismeretlen bevezetésével, legyenek ezek az r_i maradékok, amelyek megmondják, mennyivel a maximális teljesítmény alatt működik egy erőmű.

Ekkor az egyenletrendszer a
summa(w_i) = 1
p*w_i + r_i = m_i
alakot veszi fel.

Összesen 2n ismeretlen (w_i és r_i), n+1 darab egyenlet.
Lineáris algebrából ismert, hogy ez egy alulhatározott feladat, végtelen sok megoldás létezik az általános esetben.

Nálad még bejön a w_i ≥ 0 feltétel is, azaz 2n + 1 egyenleted van 2n változóra.
Ez túlhatározott feladat, nem mindig létezik megoldása.

Ha a feltételrendszeredet kiegészíted még valamilyen célfüggvénnyel, például, hogy a summa(r_i)-t akarod minimalizálni, akkor ez egy klasszikus LP-feladat és létezik rá sokféle algoritmus, ami megmondja, hogy a feladatnak létezik-e optimális megoldása, és ha igen, mi az. Nyílt forráskódú eszközök közül ott az lp_solve vagy a COIN-LP.

Lehet, hogy félreértettem amit írtál, de a súlyok nem ismeretlenek. Amit írtam is a példában pl.: 1/3, 2/3 arány.
Ezek a súlyok úgy jöttek ki, hogy ismerjük az adott erőmű teljesítményeit egy hétre visszamenően az adott negyedórában és azokból képezünk egy átlagot, és ez az átlagteljesítmény határozza meg az erőmű súlyozását az adott negyedórában.

Ha ismertek a súlyok, akkor ez egy triviális feladat, hiszen ezek szerint van egy w_i terv súlyozás, ami szerint el akarod osztani a teljesítményt, de kijöhet, hogy egy v_i tény súlyozással oldható ez csak meg.

A példáidban a "maradékok" elosztása miatt nem egyezik meg a tényleges súlyozás a terv súlyozással, nem 1:2 az erőművek súlya a tényleges termelésben.

( zeller | 2014. 12. 07., v – 12:54 )

Melyik suli...? Csak hogy a megfelelő helyről érkezett oktató is rá tudjon nézni... :-P