Re: how to do linear programming in mpitb\octave

[Przemek Klosowski]

   I need to do linear programming in mpitb\octave.

Here are two examples I adapted from an IBM DeveloperWorks article on
GNU Linear Programming library to use Octave's glpk() function:

http://www-128.ibm.com/developerworks/linux/library/l-glpk1
http://www-128.ibm.com/developerworks/linux/library/l-glpk2

The first problem from 'Operations Research': Giapetto's Woodcarving Inc

  Giapetto's Woodcarving Inc. manufactures two types of wooden toys:
  soldiers and trains. A soldier sells for $27 and uses $10 worth of
  raw materials. Each soldier that is manufactured increases
  Giapetto's variable labor and overhead costs by $14. A train sells
  for $21 and uses $9 worth of raw materials. Each train built
  increases Giapetto's variable labor and overhead costs by $10. The
  manufacture of wooden soldiers and trains requires two types of
  skilled labor: carpentry and finishing. A soldier requires 2 hours
  of finishing labor and 1 hour of carpentry labor. A train requires 1
  hour of finishing and 1 hour of carpentry labor. Each week, Giapetto
  can obtain all the needed raw material but only 100 finishing hours
  and 80 carpentry hours. Demand for trains is unlimited, but at most
  40 soldier are bought each week. Giapetto wants to maximize weekly
  profits (revenues - costs).

The problem seeks a two-vector x=[x1 x2] whose elements are equal to produced 
number of soldiers and trains.
The objective function is the total production cost,  c' * x   where
c = [27-10-14, 21-9-10]'

The constraints result from the limited number of carpentry and finishing 
hours: a * x <= b , where
a=[2 1;1 1]
b=[100 80]
with additional constraints that x>=0 and x1<=40, i.e.
lb=[0 0]
ub=[40,Inf]

the solution (UU means Upper constraints, CC for continuous variables, and s=-1 
for Maximization problem
[xmin, fmin, status, extra] =  glpk (c, a, b, lb, ub, 'UU','CC',-1)

giving xmin = [ 20 60 ], with 'profit' equal to fmin = 180 and status
= 180(good minimum), which agrees with the book solution.



Another problem from Operations Research: Applications and Algorithms,
4th Edition, by Wayne L. Winston (Thomson, 2004)

    My diet requires that all the food I eat come from one of the four
    "basic food groups": chocolate cake, ice cream, soda, and
    cheesecake. At present, the following four foods are available for
    consumption: brownies, chocolate ice cream, cola, and pineapple
    cheesecake. Each brownie costs $0.50, each scoop of chocolate ice
    cream costs $0.20, each bottle of cola costs $0.30, and each piece
    of pineapple cheesecake $0.80. Each day, I must ingest at least
    500 calories, 6 oz of chocolate, 10 oz of sugar, and 8 oz of
    fat. The nutrition content per unit of each food is shown in the
    table below. Satisfy my daily nutritional requirements at minimum
    cost.

The problem seeks a four-vector x=[x1 x2 x3 x4] whose elements are
equal to purchased amounts of brownies, ice cream, soda and pineaple
cheesecake.

The objective function is the cost,  c' * x  , where
c=[0.50 0.20 0.30 0.80]';


The constraints are the minimal number of calories, chocolate, 
sugar and fat: a * x >= b , where

 a=[400 200 150 500; 3 2 0 0; 2 2 4 4; 2 4 1 5]
 b=[500,6,10 8]'


the Minimum solution (LLLL means Lower constraints):

[xmin, fmin, status, extra] =  glpk (c, a, b, lb, ub, 'LLLL')

giving xmin = [0 3 1 0] to within tolerance, with 'cost' equal to 0.9
and status = 180(good minimum), which agrees with the book solution.