<?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' : '').'><=</option><option value="0" '.((int)$_POST['e'.$i]==0 ? 'selected' : '').'>=</option><option value="1" '.((int)$_POST['e'.$i]==1 ? 'selected' : '').'>=></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>
Comments