Simplex method

<?php
 function draw_matrix($x, $hbase, $r, $max_i, $max_j){
  echo '<table><tr><td></td><td>B</td>';
  for ($j=1;$j<=$max_j;$j++){echo '<td><span style="'.($hbase[$j] ? 'color: green;' : '').($r[$j] ? 'text-decoration: underline;' : '').'">x'.$j.'</span></td>';}
  echo '<td>|</td></tr>';
  $a=array();for ($i=1;$i<=$max_i;$i++){$a[]=array($i,'|');}
  $a[]=array(0,'L');
  $u2=false;for ($j=0;$j<=$max_j;$j++){if ((int)$x[-1][$j]!==0){$u2=true;$a[]=array(-1,'W');break;} }

  foreach ($a as $ar){
   echo '<tr><td>'.$ar[1].'</td><td>'.(round($x[$ar[0]][0]*100)/100).'</td>';
   for ($j=1;$j<=$max_j;$j++){
    echo '<td style="'.(($hbase[$j]>0 and (int)$x[$ar[0]][$j]!==0) ? 'color: red; ' : '').'"><!-- $x['.$i.', '.$j.']= -->'.(round($x[$ar[0]][$j]*100)/100).'</td>';
   }
   echo '<td>|</td></tr>';
  }
  echo '</table>';
 }

 function math_simplex($x, $e, $max_i, $max_j){
  global $debug;
  $hbase=array(null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);// Базовая ли переменная
  $r    =array(null, false, false, false, false, false, false, false, false, false);// Искуственная переменная
  //Заполняем матрицу и список базовых элементов
  $x[-1]=array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
  for ($i=1;$i<=$max_i;$i++){
   if ($e[$i]!==(int)0){
    $max_j++;$x[$i][$max_j]=-$e[$i];
    if ($x[$i][$max_j]==1){$hbase[$max_j]=$i;continue;}
   }

   //Ищем базовые переменные
   $u=false;
   for ($j=$max_j;$j>=1;$j--){
    if ((int)$x[$i][$j]!==1){continue;}
    $u1=false;for ($i1=1;$i1<=$max_i;$i1++){if ((int)$x[$i1][$j]!==0 and $i1!==$i){$u1=true;break;}}
    if (!$u1){$u=true;break;}
   }
   if (!$u){
    //$max_j++;$x[$i][$max_j]=1;$hbase[$max_j]=$i;$r[$max_j]=true;
//    echo "Для строки <b>{$i}</b> не найдена базовая переменная {$max_j} _ {$hbase[$max_j]}<br />";
    for ($j2=0;$j2<=$max_j;$j2++){$x[-1][$j2]-=$x[$i][$j2];}
   }else{
    $hbase[$j]=$i;
//    echo "Для строки <b>{$i}</b> НАЙДЕНА базовая переменная {$j} _ {$hbase[$j]}<br />";
   }
  }
  if ($e[0]==0){for ($j=1;$j<=$max_j;$j++){$x[0][$j]=-$x[0][$j];}}

//  echo $max_i.'; '.$max_j.'<pre>';print_r($hbase);echo '</pre>';

  $u=false;
  for ($j=1;$j<=$max_j;$j++){
   if ($hbase[$j]>0 and (int)$x[0][$j]!==0){
    if ($debug){
     echo "Базовая переменная в уравнении x{$j}; ".(!$u ? 'Оригинальный вариант: ' : '');
     if (!$u){$u=true;draw_matrix($x, $hbase, $r, $max_i, $max_j);}
    }

    for ($j1=0;$j1<=$max_j;$j1++){
     if ($j1==$j){continue;}
     $x[0][$j1]-=$x[$hbase[$j]][$j1]*$x[0][$j];
    }
    $x[0][$j]=0;
   }
  }


  //$u1=true;
  //ИТЕРАЦИИ
  while (true){
   if ($debug){echo '<hr/>Итерация';draw_matrix($x, $hbase, $r, $max_i, $max_j);}

   //Выбираем уравнение между W и L
   $wneed=false;
   for ($j=0;$j<=$max_j;$j++){if ((int)$x[-1][$j]!==0){$wneed=true;break;}}
   if ($wneed and $debug){Echo 'Нам до сих пор нужна W<br />';};
   if ($wneed){
    //Решаем W
    $u=false;for ($j=1;$j<=$max_j;$j++){if ($x[-1][$j]<0){$u=true;break;}}
//  echo '_'.$u.' and '.($x[-1][0]<0).'; ';
    if (!$u and (int)$x[-1][0]==0){$x[-1]=array(0,0,0,0,0,0,0,0,0,0,0);continue;}
    if (!$u and $x[-1][0]<0){return null;}
    $w=-1;
   }else{
    //Решаем L
    $u=false;for ($i=1;$i<=$max_j;$i++){if ($x[0][$i]<0){$u=true;break;}}
    if (!$u){return $x[0][0]*($e[0]==1 ? -1 : 1);}
    $w=0;
   }

   if (true){
    //Находим ведущий столбец
    $nv=0;for ($j=1;$j<=$max_j;$j++){
     if ($x[$w][$j]<$x[$w][$nv] or $nv==0){$nv=$j;}
    }
    if ($debug){echo 'nv='.$nv.' ['.abs($x[$w][$nv]).']; <br>';}
    //Находим ведущую строку
    $nh=0; for ($i=1;$i<=$max_i;$i++){
     if ($x[$i][$nv]<=0){continue;}
//   echo $x[$i][0].'/'.$x[$i][$nv].' = '.($x[$i][0]/$x[$i][$nv]).'; ';
     if ($nh==0){$d=$x[$i][0]/$x[$i][$nv];$nh=$i;continue;}
     $d1=$x[$i][0]/$x[$i][$nv];
     if ($d1<$d){$nh=$i;$d=$d1;}
    }
    if ($nh==0){return 'inf';}
    if ($debug){echo 'nh='.$nh.' ['.$d.'];<br>РЭ = '.$x[$nh][$nv].'; ';}


    //пересчитываем матрицу
    $x1=$x;$x1[$nh][0]/=$x[$nh][$nv];
    for ($j=1;$j<=$max_j;$j++){$x1[$nh][$j]/=$x[$nh][$nv];}
    for ($i=$w;$i<=$max_i;$i++){
     if ($i==$nh){continue;}

     $x1[$i][0]-=$x[$nh][0]*$x[$i][$nv]/$x[$nh][$nv];
     for ($j=1;$j<=$max_j;$j++){
      $x1[$i][$j]-=$x[$nh][$j]*$x[$i][$nv]/$x[$nh][$nv];
     }
    }
    $x=$x1;unset($x1);
    continue;
   }
   exit;

   //if ($u1){$u1=false;continue;}
   //echo '<strong>ДЕБАЖНЫЙ ВЫХОД!</strong>'; break;
  }
 }


?><!doctype html><html><head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
 <title>Симплекс</title>
 <link rel="stylesheet" href="/ascet.css" type="text/css" media="screen">
</head><body><?php

 echo '<form method="post"><table class="sad">';
 echo '<tr >';for ($j=1;$j<9;$j++){
  echo '<td><input name="x0_'.$j.'" value="'.(strlen($_POST['x0_'.$j])>0 ? $_POST['x0_'.$j] : '0').'">*x'.$j.'+</td>';
 }
 echo '<td >→<select name="e0"><option value="1" '.((int)$_POST['e0']==1 ? 'selected' : '').'>min</option><option value="0" '.((int)$_POST['e0']==0 ? 'selected' : '').'>max</option></select></td></tr>';

 for ($i=1;$i<10;$i++){
  echo '<tr>';
  for ($j=1;$j<9;$j++){
   echo '<td><input name="x'.$i.'_'.$j.'" value="'.(strlen($_POST['x'.$i.'_'.$j])>0 ? $_POST['x'.$i.'_'.$j] : '0').'">*x'.($j).'+</td>';
  }
  echo '<td><select name="e'.$i.'"><option value="-1" '.((int)$_POST['e'.$i]==-1 ? 'selected' : '').'>&lt;=</option><option value="0" '.((int)$_POST['e'.$i]==0 ? 'selected' : '').'>=</option><option value="1" '.((int)$_POST['e'.$i]==1 ? 'selected' : '').'>=&gt;</option></select> <input name="y'.$i.'" value="'.(strlen($_POST['y'.$i])>0 ? $_POST['y'.$i] : '0').'"></td>';
  echo '</tr>';
 }
 echo '</TABLE><input class="nice mrgn" type="submit"><input type="hidden" name="action" value="math"></form>';

 if ($_POST['action']!=='math'){echo '</body></html>';return;}

 $x=array();$e=array();$max_i=0;$max_j=0;
 for ($i=0;$i<10;$i++){
  $x[$i]=array(0);
  for ($j=1;$j<9;$j++){
   preg_match('|(\\-?[0-9.]+)|',$_POST['x'.$i.'_'.$j], $a);
   $x[$i][$j]=(float)$a[1];

   if ($x[$i][$j]!==(float)0){$max_i=$i;$max_j=max($j, $max_j);}
  }

  $e[$i]   =(int)$_POST['e'.$i];
  $x[$i][0]=(float)$_POST['y'.$i];
 }

 //echo $max_i.'; '.$max_j.'<pre>';echo '</pre>';
 require('./simplex.php');


 //Вычисляем
 $debug=true;
 echo '<h2>!'.math_simplex($x, $e, $max_i, $max_j).'</h2>';

 return;
 $dx=array(
  array(20,0,-1,-1,0,0,0),
  array(20,1,0,1,0,0,0),
  array( 5,0,1,0,-1,1,0),
  array(50,0,1,0,0,0,1),
 );
 echo '<h2>'.math_simplex($dx, array(0,0,0,0,0,0,0,0,0,0,0), 3, 6).'</h2>';

?></body></html>