Metodo Simplex

import java.util.*;
import java.awt.*;
import java.applet.*;

class RN {
int n;
int d;

RN() {n=0; d=1;}
RN(int n) {this.n=n; this.d=1;}
RN(int n, int d) {this.n=n; this.d=d; reduce();}
RN(String s) {
int k = s.indexOf('/');
if (k>0) {
d = Integer.valueOf(s.substring(k+1)).intValue();
s = s.substring(0,k);
} else
d = 1;
n = Integer.valueOf(s).intValue();
reduce();
}

inteuclid(int a, int b) {
int q,r;

if (a < 0) a = -a;
if (b < 0) b = -b;
if (b == 0)
if (a==0)
return -1;
else
return a;
for {
q = a / b;
r = a % b;
if (r==0)
break;
a = b;
b = r;
}
return b;
}

boolean reduce() {
int c;

if ((c = euclid(n,d))<0)
return false;
if (d<0)
c *= -1;
n /= c;
d /= c;
return true;
}

void set(int n) {this.n=n; this.d=1;}
voidset(int n, int d) {this.n=n; this.d=d;}
void set(RN a) {n=a.n; d=a.d;}

void mul(RN a) {
a.reduce();
RN aa = new RN(n,a.d);
RN bb = new RN(a.n,d);
aa.reduce();
bb.reduce();
n = aa.n * bb.n;
d = aa.d * bb.d;
}

void div(RN a) {
a.reduce();
RN aa = new RN(n, a.n);
RN bb = new RN(a.d, d);
aa.reduce();
bb.reduce();
n = aa.n * bb.n;
d = aa.d * bb.d;
}

void inv() {int x; x = n; n= d; d = x; reduce();}

boolean plus(RN a) {
int c,x,y;

c = euclid(d, a.d);
if (c < 0)
return false;
if ((x = a.d/c*n + d/c*a.n)==0) {
x = 0;
y = 1;
} else
y = d/c*a.d;
n = x;
d = y;
this.reduce();
return true;
}

boolean minus(RN a) {
int c,x,y;

c = euclid(d, a.d);
if (c < 0)
return false;
if ((x = a.d/c*n - d/c*a.n)==0) {
x = 0;
y = 1;
} else
y = d/c*a.d;
n= x;
d = y;
this.reduce();
return true;
}

boolean gt(RN a) {RN c=new RN(n,d); c.minus(a); return c.n>0;}
boolean ge(RN a) {RN c=new RN(n,d); c.minus(a); return c.n>=0;}
boolean eq(RN a) {RN c=new RN(n,d); c.minus(a); return c.n==0;}
boolean le(RN a) {RN c=new RN(n,d); c.minus(a); return c.n<=0;}
boolean lt(RN a) {RN c=new RN(n,d); c.minus(a); return c.n<0;}
}

publicclass Simplex extends Applet {
int m,n,r,s;
int step,cycle;
RN[][] a = new RN[10][20];
int[] base = new int[10];
String message = "";

void Print(Graphics g, FontMetrics fm, int x, int y, String s) {
int w = fm.stringWidth(s);
int h = fm.getHeight();
g.drawString(s,x-w/2,y-h/2+fm.getAscent());
}

void Print(Graphics g, FontMetrics fm, int x, int y, int n) {
Print(g,fm,x,y,""+n);
}void Print(Graphics g, FontMetrics fm, int x, int y, RN rn) {
int wn, wd, h = fm.getHeight();
int sign;

if (rn.n<0)
sign = -1;
else
sign = 1;
if (rn.d == 1) {
Print(g,fm,x,y,sign*rn.n);
wd = fm.stringWidth(""+(sign*rn.n));
} else {
Print(g,fm,x,y-h/2-2,sign*rn.n);
Print(g,fm,x,y+h/2+2,rn.d);
wn = fm.stringWidth(""+sign*rn.n);
wd = fm.stringWidth(""+rn.d);
if (wn>wd)
wd = wn;g.drawLine(x-wd/2,y-1,x+wd/2,y-1);
}
if (sign<0) {
wn = wd/2+fm.stringWidth("-")+2;
wd = fm.getHeight();
g.drawString("-",x-wn,y-wd/2+fm.getAscent());
}
}

void input_data() {
m = Integer.parseInt(getParameter("m"));
n = Integer.parseInt(getParameter("n"));
String sdat = getParameter("data");
StringTokenizer st = new StringTokenizer(sdat,",");
for (int i = 0; i<=m; i++) {
for(int j=0; j<n; j++)
a[i][j] = new RN(st.nextToken());
base[i] = n+i;
for (int j=n; j<n+m; j++) {
RN rn = new RN(0);
if (j == i+n)
rn.set(1);
a[i][j] = rn;
}
a[i][n+m] = new RN(st.nextToken());
}
n += m;
}

boolean step1() { /* búsqueda de pivote s (r, s)*/
RN c = new RN();

s = 0; r = -1;
c.set(a[m][s]);
for (int j=1; j<n; j++)
if (c.gt(a[m][j])) {
s = j;c.set(a[m][s]);
}
if (c.n>=0) {
s = -1;
return true;
} else
return false;
}

boolean step2() { /* búsqueda de pivote r (r, s)*/
RN t = new RN();
RN c = new RN();

for (int i=0; i<m; i++) {
if (a[i][s].n<=0)
continue;
t.set(a[i][n]);
t.div(a[i][s]);
if (r<0 || t.lt(c)) {
r = i;
c.set(t);
}
}
if (r<0)
return true;
else
return false;
}

void step3() { /* pivote...