Auswahlproblem aus nicht-disjunkten Mengen

Neue Frage »

rosinante Auf diesen Beitrag antworten »
Auswahlproblem aus nicht-disjunkten Mengen
Hallo!

Ich möchte eine Funktion schreiben, welche mir eine Lizenzprüfung durchführt. Mathematisch geht es darum, dass man verschiedene Mengen von ganzen Zahlen hat, wobei ich von jeder Menge Elemente nehmen darf. Die Frage ist, ob man daraus eine Lösungsmenge L bilden kann.

Z.B.





Kann man bilden?

Die Funktion müsste mir true zurückgeben - da man z.B. von nehmen kann, von und von .

Irgendwie erscheint mir das Problem recht "klassisch", d.h. es könnte sein dass ich hier von jemandem nur eine Anregung oder ein Stichwort benötige, welches mich in die richtige theoretische Richtung weist...
Meine bisherigen Überlegungen sind eher auf Optimierungsbasis (z.B. kann man wenn gleich gross ist wie die Anzahl der Elemente von alle Elemente von in der Lösung haben). Einzige Wirkliche Lösung die ich aktuell sehe ist es das ganze rekursiv komplett abzuarbeiten, doch dies wäre performancemässig sicher nicht so toll.

Hat hier jemand eine Hilfe für mich, wie ich dieses Problem lösen könnte, bzw. einen hint nach einem mathematischen Teilbereich, bzw. einem Algorithmus, welcher mir diesbezüglich weiterhelfen könnte?

Freundliche Grüsse

Rosie
Elvis Auf diesen Beitrag antworten »

Ich bin ziemlich sicher, dass ich daraus ein binäres Optimierproblem machen kann, obwohl ich es noch nicht fertig formuliert habe.
IfindU Auf diesen Beitrag antworten »

Gibt es denn einen Grund warum du das ausgerechnet so machen willst? Üblicher ist wohl einfache Regeln an einen Schlüssel zu stellen.

Wie z.B. Produkt der der Ziffern an ungerader Stelle muss 84 ergeben, die Quersumme des ganzen Schlüssels 112 usw.
Dann kann einmal alle/viele Schlüssel generieren lassen und verteilen. Das dauert dann je nach Anzahl und Komplexitität der Regeln zwar, aber es ist einmaliger Aufwand. Das prüfen hingegen geht flott.
rosinante Auf diesen Beitrag antworten »

@Elvis, danke schonmal. Schaue mir auch mal an was binäre Optimierungsprobleme sind, wenn du aber eine Ausformulierung schaffst, wäre es natürlich toll.

@IfindU: Es ist halt schon ein gegebenes System. Ein Kollege hat eine Lösung bei welcher die Kunden Lizenzen kaufen können. Z.B. Kauft jemand für 10 Computer 5 Lizenzen, d.h. es dürfen von den 10 Computern nur 5 gleichzeitig das Programm benutzen. Er kann nun für 12 weitere Computer 4 Lizenzen kaufen (z.T. sind es wieder dieselben wie vorher und zum Teil andere...). Ich weiss, dass ist recht vertrackt, warum kauft der Dödel nicht einfach zusätzliche Lizenzen für die vorherigen 10 Computer und dann neue für die anderen, aber es ist halt aktuell so. Wenn nun die Computer benutzt werden muss man entscheiden können, ob sie berechtigt sind, d.h. wenn z.B. 13 Computer laufen muss man testen, ob die vergebenen Lizenzen an diese 13 Computer verteilt werden können.
Elvis Auf diesen Beitrag antworten »

Definitionen




Entscheidungsvariable



Nebenbedingungen




Zielfunktion (pro forma):

Ergebnis der Optimierung kann wie folgt interpretiert werden
a) infeasible: nicht lösbar
b) optimal: Element
rosinante Auf diesen Beitrag antworten »

Hey danke Elivis!

Erste Nebenbedingung muss in meinem Fall jeweils <= sein statt =

Habe es verstanden und es macht total Sinn. Habe nicht an so was gedacht, weil es ja nix zu optimieren gibt. Danke für die Hilfe Freude
 
 
Elvis Auf diesen Beitrag antworten »

a) Ich verstehe, dass du mit "... nehmen darf" < oder = gemeint hast. Das hatte ich falsch interpretiert.
b) Für einen Ex-Profi-Optimierer sieht nahezu jedes Problem wie ein Optimierproblem aus. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »