Bestimmen Sie das duale Problem zu folgendem linearen Programm

Question

Aufgabe:

Bestimmen Sie das duale Problem zu folgendem linearen Programm

\( \left\{\begin{aligned} \min \; & c^{\top} x \\ \text { s.t. } & A x=0 \\ & 0 \leq x \leq a \end{aligned}\right. \)

mit \( A \in \mathbb{R}^{m \times n} \) und c, \( a \in \mathbb{R}^{n} \) mit \( a \geq 0 \) gegeben. Gilt starke Dualität?

Problem/Ansatz:

Ich weiß leider überhaupt nicht wie ich da jetzt vorgehen soll. Meine Idee wäre die Lagrange-Funktion aufzustellen. Allerdings weiß ich dann nicht was ich maximieren soll und unter welchen Bedingungen. Kann mir hier jemand weiterhelfen?

Answer 1

Solltest Du nachlesen können, etwa

Zu einem linearen Programm
(P) \( \quad \min \left\{c^{t} x \mid A x \geq b, x \geq 0\right\} \)
gehört stets ein sogenanntes duales Programm
(D) \( \quad \max \left\{b^{T} y \mid A^{T} y \leq c\right\} \).

Comments

Danke, das hab ich auch schon gefunden, allerdings verstehe ich nicht wie ich mit der Bedingung 0<x<a umgehen soll. Wie Sieht die im dualen Problem aus?