A Linear Programming Example

Consider the translation of the following problem to a linear programming problem:
A person undergoing a diet should take N types of vitamins. One should take a quantity of b_i from each vitamin type. There exist M fruits. Each fruit j contains v_j,1...v_j,N vitamins of each type. Each fruit j costs p_j. Assuming that it is possible to buy a fraction of a fruit, what is the cheapest combination of fruits that should be bought while keeping the diet constraints?
The following linear program describes this problem:
Minimize: $\sum_{j=1}^{M}x_{j}p_{j}$
Subject To:

• $\forall i: \sum_{j=1}^{M}x_{j}v_{j,i} \geq b_{i}$
• $\forall j: x_{j} \geq 0$

Where x_j would denote the quantity bought of fruit j.
The solution of this linear program gives the lowest price needed to achieve the diet constraints. Yet, this problem can be also translated to a dual maximization linear program:
Maximize: $\sum_{i=1}^{N}y_{i}b_{i}$
Subject To:

• $\forall j: \sum_{i=1}^{N}y_{i}v_{j,i} \leq p_{j}$
• $\forall i: y_{i} \geq 0$

The intuition behind this translation can be viewed by changing the point of view about the problem. In this case we can assume the following problem:
A vitamins company sells N types of vitamins. Each vitamin price is y_i. It is known that every person is taking a quantity of b_i from each vitamin type. The person can either buy the vitamin directly from the company or get it by eating fruits. There exist M fruits. Each fruit j contains v_j,1...v_j,N vitamins of each type. Each fruit j costs p_j. The company does not want a combination of vitamins to cost more than the fruit which contains them, since then people will buy the fruit rather than the vitamins. The aim is to maximize the return of the diet..
The variable y_i in the above program denotes the price of each vitamin type i. The solution of this program will give the maximal income of the company. According to Theorem the company's maximal income will be equal exactly to buyer's minimal expense.