** 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 **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: *
*
*

Subject To:
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: *
*
*

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 **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.

** Next:** Use of Linear Programming
** Up:** Linear Programming
** Previous:** Introduction to Linear Programming
*Yishay Mansour*

*1999-12-18*