线性规划，单纯性法的学习
很早就想学习线性规划（皮毛，就是想搞学习单纯性法），但是每次都是看的晕晕乎乎，总结下来，以下阶梯非常薄弱：
对矩阵的知识和sigma的运用很生疏。高斯消元
很高兴找到了一个属于我菜鸟级别的入门级simplex介绍，里面真的是讲得非常详细，很适合最最基础的入门。
总结一下，至少我知道pivot operation做了些什么，还有ratio等概念。
其实只是了解了simplex的操作，并不知道为何simplex是这样设计的，以及其巧妙性。
不过懂一点总比看着WC2007论文干着急好。
应该能参照UVA 10498的程序掌握simplex standard form的编写。

a Simplex SIMPLEX METHOD OUTLINE FOR STANDARD MAXIMIZING PROBLEMS

http://math.uww.edu/~mcfarlat/simplex1.htm#345
又是一所Wisconsin的分校

花了一点时间写UVA10498的程序，终于知道怎么写了! 然后测试，保佑能AC.

{$APPTYPE CONSOLE}
const
max=maxlongint;
var
 n,m,s,l,e:integer;
 temp:double;
 happy:array [1..401,1..401] of double;
 total:array[1..401] of double;

function check:boolean;
  var i:integer;
  begin
    check:=true;
    for i:=1 to n+m do
       if happy[m+1,i]<0 then begin
      check:=false;
      exit;
      end;

   end;
Procedure pivot(row,col:integer);
 var i,j:integer;
 tmp,tmpcol:double;
  begin
    tmp:=happy[row,col];
    for i:=1 to n+m do
       begin
         happy[row,i]:=happy[row,i]*(1/tmp);
       end;
       total[row]:=total[row]*(1/tmp);
    for i:=1 to m+1 do
     if i<>row then begin
        tmpcol:=happy[i,col];
        for j:=1 to n+m do
           begin
             happy[i,j]:=happy[i,j]-tmpcol*happy[row,j];
           end;
         total[i]:=total[i]-total[row]*tmpcol;
        end;
    end;
procedure readata;
 var i,j:integer;
  begin
    readln(n,m);
    fillchar(happy,sizeof(happy),0);
    for i:=1 to n do
      begin
        read(temp);
        happy[m+1,i]:=-temp;
      end;
      readln;
      s:=n;
    for i:=1 to m do
       begin
         for j:=1 to n do
         read(happy[i,j]);
         inc(s);
         happy[i,s]:=1;
         readln(total[i]);
       end;
      end;
Procedure simplex;
 var i:integer;
  min1,min2:double;
   begin
    while true do
     begin
      if check then break;
      min1:=max;
      min2:=max;
     for i:=1 to n do
         if happy[m+1,i]<min1 then
           begin
             min1:=happy[m+1,i];
             e:=i;
           end;
        l:=1;
        for i:=1 to m do
         if happy[i,e]<>0 then
           if (total[i]/happy[i,e]<min2) then
              begin
                min2:=total[i]/happy[i,e];
                l:=i;
              end;
        pivot(l,e);
     end;
   end;
Procedure output;
   begin
     if trunc(total[m+1]*m)=total[m+1]*m then
     writeln('Nasa can spend ',trunc(total[m+1]*m),' taka.')
    else
writeln('Nasa can spend ',trunc(total[m+1]*m)+1,' taka.')
   end;
begin
  readata;
  simplex;
  output;
end.

学好规划，学好规划就是减少熵