Consider a linear program $$\{\max c^T x \mid Ax \leq b\}$$​. Which of the following statements is true?

Correct option is B

Given the primal linear program:
​$$\boxed{\max \; c^T x \quad \text{subject to } Ax\leq b}$$​​
The corresponding dual is obtained using the standard maximization – ≤ form.
Step 1: Primal Form
​$$\max c^Tx$$​​
subject to:
​$$Ax\leq b$$​​
The constraint matrix is A, so in the dual, it becomes: $$A^T$$​​
The primal right-hand-side vector b becomes the coefficient vector of the dual objective function.
Step 2: Dual Objective
Since the primal is a maximization problem, its dual is a minimization problem:
​$$\min b^Ty$$​​
Step 3: Dual Constraint
The dual constraint is: $$A^Ty\geq c$$​​
Thus, the complete dual is:
​$$\boxed{\min b^Ty\quad\text{subject to }A^Ty\geq c,\quad y\geq0}$$​​
Therefore:
​$$\boxed{\text{(b) the dual program is }\{\min b^Ty\mid A^Ty\geq c,\ y\geq0\}}$$​​
Information Booster
For the standard form:
​$$\boxed{\max c^Tx\quad\text{s.t. }Ax\leq b,\ x\geq0}$$​​
the dual is:
​$$\boxed{\min b^Ty\quad\text{s.t. }A^Ty\geq c,\ y\geq0}$$​​
The key transformations are:
​$$\boxed{\max\leftrightarrow\min}\\\boxed{A\leftrightarrow A^T}\\\boxed{\leq\leftrightarrow\geq}\\\boxed{c\leftrightarrow b}$$​​
Additional Knowledge
Why the Other Options Are Incorrect?
· (a) Uses $$A^Ty\leq c,$$​ but the inequality should be ≥.
· (c) Equality $$A^Ty=c$$​ is not appropriate for the given ≤ primal constraints.
· (d) The dual of a maximization problem here is a minimization problem, not maximization.
Primal: $$\max,\ Ax\leq b,\ x\geq0$$​​
Dual: $$\min,\ A^Ty\geq c,\ y\geq0$$​​