1
$\begingroup$

Trying to solve the following question:

A final list of foods is given, and a final list of nutrients (such as protein, carbohydrates, etc.). Also non-negative numbers $r_{k,l}$ are given that indicate the amount of nutrients $k$ in a unit of food $l$, positive numbers $t_{k}$ that indicate the daily amount required for a person of nutrient $k$, and positive numbers that indicate the amount of calories $s_{l}$ of a unit of food $l$.

In the primal problem we must define for each nutrient number $k$ a non-negative value $x_{k}$, then the expression $x_{k}\cdot r_{k,l}$ is called the "weighted-cost" of nutrient number $k$ for food number $l$, And the expression $x_{k}\cdot t_{k}$ is called the "weighted-contribution" of nutrient number $k$. Our goal is to maximize the weighted contribution of all nutrients, while for any food, the weighted cost of all nutrients must not exceed the amount of calories of that food.

Find the dual program.

Let's denote the list of foods to be $L$, whose size is $n_{L}$ and the list of nutrients to be $K$, whose size is $n_{K}$. For each $1\leq k\leq n_{K}$, we define the variable $x_{k}$ to represent the non-negative values of the amount of each nutrient $k$. As I understand, the primary program is: $$ \begin{align*} \max&\sum_{k=1}^{n_{K}}x_{k}\cdot t_{k}\\\text{s.t.}&\forall l\in\left[1,n_{L}\right],\,\sum_{k=1}^{n_{K}}x_{k}\cdot r_{k,l}\leq s_{l}\\&\forall k\in\left[1,n_{K}\right],\,x_{k}\geq0 \end{align*} $$

Therefore the dual program is: $$ \begin{align*} \min&\sum_{l=1}^{n_{L}}y_{l}s_{l}\\\text{s.t.}&\forall k\in\left[1,n_{K}\right],\,\sum_{l=1}^{n_{L}}y_{l}r_{k,l}\leq t_{k}\\&\forall l\in\left[1,n_{L}\right],\,y_{l}\leq0 \end{align*} $$ But for some reason, the final answer in the answers: $$ \begin{align*} \min&\sum_{l=1}^{n_{L}}y_{l}\cdot s_{l}\\\text{s.t.}&\forall k\in\left[1,n_{K}\right],\,\sum_{l=1}^{n_{L}}y_{l}r_{k,l}\geq t_{k}\\&\forall l\in\left[1,n_{L}\right],\,y_{l}\geq0 \end{align*} $$

The difference is in the direction of the inequalities. In the picture below I see a summary of the transitions from a primal to a dual plan. So because $x_k\geq0$ for every $k\in\left[1,n_{K}\right]$, I need to get $n_K$ inequalities of $\leq$ (and not $\geq$), no? Am I wrong or is their final answer incorrect?

enter image description here

$\endgroup$
1
  • $\begingroup$ This nutritional plan should be optimized by an hyper-plan. $\endgroup$
    – Jean Marie
    Commented Feb 4, 2023 at 18:16

1 Answer 1

1
$\begingroup$

The provided final answer is correct, and your inequalities are flipped. Here's why.

LP duality is a symmetric relationship, so it does not know which program you've decided to call "primal" and which program you've decided to call "dual". The "summary of transitions" you've given actually describes the relationship between a primal-dual pair where the key distinction is that the left LP is a minimization problem and the right LP is a maximization problem. In your case, the primal is a maximization problem, so the primal is on the right and the dual is on the left.

The relevant rows of the table are:

  1. The first row: a nonnegative variable in a maximization problem corresponds to a $\ge$ constraint in its maximization dual. Therefore we get the constraint $$\sum_{l=1}^{n_{L}}y_{l}r_{k,l}\geq t_{k}.$$
  2. The fourth row: a $\le$ constraint in a maximization problem corresponds to a nonegative variable in its minimization dual. Therefore our dual variables are $y_l \ge 0$.

As a mnemonic device, I suggest thinking about the table in the following way. These rules are symmetric relationships: they describe the correspondence between constraints in one half of a primal-dual pair, and variables in the other half.

Rule 1. Equations always correspond to unrestricted variables.

For the second rule, we classify constraints and variables as either ordinary or weird:

  • Nonnegative variables are always ordinary and nonpositive variables are always weird. (This makes sense; you don't usually see nonpositive variables in the wild!)
  • In a maximization problem, upper bounds ($\le$ constraints) are ordinary and lower bounds ($\ge$ constraints) are weird. (If you're maximizing, you'd expect a constraint to generally be limiting you from above!)
  • In a minimization problem, the reverse is true: lower bounds are ordinary and upper bounds are weird.

Rule 2. Ordinary inequalities correspond to ordinary variables, and weird inequalities correspond to weird variables.

This summarizes the correspondence better than trying to memorize a $6 \times 2$ table of rules.

(Applying it to this example: in the primal LP for the nutrition plan, all constraints and variables are ordinary, so the same thing should be true in the dual LP. Since the dual LP is a minimization problem, it should have upper bounds and nonnegative variables.)

$\endgroup$
2
  • 1
    $\begingroup$ Arthur Benjamin has a similar S-O-B method, where the three cases are called Sensible, Odd, and Bizarre. $\endgroup$
    – RobPratt
    Commented Feb 4, 2023 at 20:52
  • 1
    $\begingroup$ @RobPratt That's excellent and I am absolutely using it the next time I teach linear programming. $\endgroup$ Commented Feb 4, 2023 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .