ich habe folgendes Problem:
Mithilfe eines ungerichteten Graphen G = (V, E) soll bestimmt werden, ob es eine mögliche Finanzierung für die Reparatur der Straßen gibt wenn 1. die Kosten zwischen den Städten aufgeteilt werden oder 2. eine Stadt die gesamte Reparatur bezahlt. In dem Graphen repräsentieren die Knotven v ∈ V die Städte und die Kanten e = {u,v} die Straßen zwischen diesen Städten. Natürlich hat jede Stadt ein begrenztes Budget, welches nicht überschritten werden darf und es gibt keine negativen Zahlungen.
Für 1. wurde vorgeschlagen, ein lineares Programm zu entwickeln. Leider fällt mir hier nicht auf, was die Variablen sein sollen und was die Bedingungen sein sollen. Ich habe es so versucht, dass ich jeder Stadt ein Budget zugewiesen habe und die Reparaturkosten als Summe der beiden Städte zusammenrechne. Allerdings habe ich hier das Problem, dass das Budget überschritten bzw. nicht beachtet wird. Hier meine Idee, wobei x,y,z,a die Variablen der jeweiligen Stadt sein sollen:
maximize x + y + z + a;
subject to {
x <= 60000;
y <= 60000;
z <= 60000;
a <= 80000;
x + y == 70000;
x + z == 60000;
x + a == 100000;
};
Zu 2. wurde uns geraten, das Problem mit ganzzahliger linearer Programmierung zu lösen.
