Modifikation eines Linearen Programms (LP)

19.10.2009, 21:55	Manuuela	Auf diesen Beitrag antworten »
Modifikation eines Linearen Programms (LP) Das Optimierungsproblem $\begin{eqnarray} \{\max cx, \text{ s.d } Ax\leq b, x\geq 0\} \end{eqnarray}$ mit $\begin{eqnarray} c,x\in \mathbb R^n, A\in \mathbb R^{m\times n}, b\in \mathbb R^m \end{eqnarray}$ sei gegeben. Betrachten Sie nun die folgenden Situationen: (a) Eine neue Nebenbedingung $\begin{eqnarray} A^{m+1}x\leq b_{m+1} \end{eqnarray}$ wird zum LP hinzugefügt. (b) Eine neue Variable, $\begin{eqnarray} x_{n+1} \end{eqnarray}$ mit Koeffizienten $\begin{eqnarray} c_{n+1} \end{eqnarray}$ und $\begin{eqnarray} A_{n+1} \end{eqnarray}$ wird zum LP hinzugefügt. (c) Die Bedingung $\begin{eqnarray} A^ix\leq b_i \end{eqnarray}$ für ein $\begin{eqnarray} i\in \{1,...,m\} \end{eqnarray}$ wird entfernt. (d) Die Variable $\begin{eqnarray} x_j \end{eqnarray}$ für ein $\begin{eqnarray} j\in \{1,...,n\} \end{eqnarray}$ wird entfernt. Beantworten Sie für jeden der obigen Fälle die beiden folgenden Fragen und begründen Sie ihre Antwort: 1) Wie verändert sich die zulässige Menge $\begin{eqnarray} P \end{eqnarray}$ ? 2) Wie änder sich der optimale Zielfunktionswert $\begin{eqnarray} z^ \end{eqnarray}$ ? Zu a) Wird die zulässige Menge von der Nebenbedingung geschnitten so wird die Menge P kleiner ansonsten bleibt sie gleich. Der optimale Funktionswert $\begin{eqnarray} z^* \end{eqnarray}$ bleibt gleich wenn die Nebenbedingung die Menge P nicht schneidet, ansonsten wird $\begin{eqnarray} z^* \end{eqnarray}$ kleiner wenn der vorherige Wert nicht mehr in der zulässigen Menge $\begin{eqnarray} P \end{eqnarray*}$ ist. Zu b) Durch eine weitere Nebenbedingung wird die Dimension um eins größer und somit die zulässige Menge P größer. Der optimale Zielfunktionswert bleibt gleich oder wird größer. Zu c) Die zulässige Menge bleibt gleich falls die Nebenbedingung nicht im zulässigen Bereich liegt. Sie wird größer oder gar unbeschränkt wenn sie im zulässigen Bereich liegt. Der optimale Zielfunktionswert bleibt gleich oder wird größer oder gar unendlich. Zu d) Die Dimension wird um eins kleiner und somit wird auch die zulässige Menge P kleiner oder bleibt gleich. Der optimale Zielfunktionswert bleibt gleich oder wird kleiner. Das sind so meine Gedanken und Ideen, ich hoffe ihr könnt mir die Bestätigen oder mich ggf. korrigieren. Danke
19.10.2009, 22:26	Ben Sisko	Auf diesen Beitrag antworten »
Sieht gut aus

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »