next up previous
Next: Use of Linear Programming Up: Linear Programming Previous: Introduction to Linear Programming

   
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 bi from each vitamin type. There exist M fruits. Each fruit j contains vj,1...vj,N vitamins of each type. Each fruit j costs pj. 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:
Where xj 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:
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 yi. It is known that every person is taking a quantity of bi 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 vj,1...vj,N vitamins of each type. Each fruit j costs pj. 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 yi 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.
next up previous
Next: Use of Linear Programming Up: Linear Programming Previous: Introduction to Linear Programming
Yishay Mansour
1999-12-18