Транспортная задача. Метод минимального элемента.

mattxs

Новичок
Добрый вечер, дорогие форумчане!
Программирую алгоритм транспортной задачи методом минимального элемента, чтобы получить первый опорный план и перейти к методу потенциалов.
Столкнулся с проблемой:
Никак не могу понять, почему не ищутся правильно индексы минимального элемента. Они (инлдексы0 вначале находят правильный элемент, а потом идут на (0;0), и всегда (0;0), хотя функция по их поиску работает правильно.
Вот код:
PHP:
// Матрица тарифов
$c = array(
        array(2,5,2),
        array(4,1,5),
        array(3,6,8)
        );

// Запасы груза
$m = array(90,400,110);

// Потребности в грузе
$n = array(140,300,160);


function MinTarif($c,$m, $n)
    {
       
        $X = array();
       
     
       
        for ($i=0; $i < count($m); $i++) { 
            for ($j=0; $j < count($n); $j++) { 
                $X[$i][$j]=-1;
            }
        }
       
        $k=0;
        $t=0; 
               
     
                    for ($i=0; $i < count($c); $i++)
                        {
                            for ($j=0; $j < count($c[0]); $j++)
                                {

                                    $k = getIndexi($c);
                                    $t = getIndexj($c);

                                        $minPost = min($m[$k],$n[$t]); // Минимальная поставка в строке или столбце
   
                                        $X[$k][$t] = $minPost; // Загружаем поставку
                                                           

                                        if($minPost == $m[$k]) { $n[$t] -= $m[$k]; $m[$k]=0; $c = ZamenaStroki($c,$k); }

                                        if($minPost == $n[$t]) { $m[$k] -= $n[$t]; $n[$t]=0; $c = ZamenaStolbca($c,$t); }
                              }
                 
                        }

        return $X;

    }
В функции я передаю матрицу тарифов $c, массив с запасами груза $n, и массив с потребностями $n.
Результат, соответственно, я записываю в Матрицу поставок $X.
Иду по матрице тарифов, ищу и запоминаю индексы минимального элемента с помощью функции getIndexi() и getIndexj() соответственно.
Вот эти функции:
PHP:
function getMin($arr)
     {
        static $res = array();

        foreach ($arr as $k => $v) {
            if(is_array($v))
                getMin($v);
            else{
                if($v != 0)
                    $res[] = $v;
            }
        }
        return !empty($res) ? min($res) : 0;
     }
       

    function getIndexi($ab)
    {
        $k=0;
        for ($i=0; $i < count($ab); $i++) { 
            for ($j=0; $j < count($ab[0]); $j++) { 
                if($ab[$i][$j] == getMin($ab))
                    $k = $i;
            }
        }
        return $k;
    }

    function getIndexj($ab)
    {
        $t=0;
        for ($i=0; $i < count($ab); $i++) { 
            for ($j=0; $j < count($ab[0]); $j++) { 
                if($ab[$i][$j] == getMin($ab))
                    $t = $j;
            }
        }
        return $t;
    }
Функция getMin() возвращает минимальный элемент двумерного массива. Причем пропуская нули. То есть если в матрице есть нули, то функция работает как continue в цикле for. (P. S. я писал функцию поиска мин элемента в двумерном массиве сам, она пропускала нули, но если первый элемент матрицы был бы 0, она брала его за минимум, так как я стартовал с первого элемента, но не суть).

Далее в самой MinTarif() я ищу минимальную поставку в массивах $m и $n, и записываю её в матрицу погрузок $X. После этого я проверяю, какая была поставка минимальна и, в соответствии с этим, зануляю элементы массива, а так же заменю нулями строку или столбец матрицы $c (в зависимости, чьи потребности были удовлетворены) функциями ZamenaStroki() и ZamenaStolbca() соответственно.
Вот они:
PHP:
function ZamenaStroki($c, $stroka)
    {
        for ($i=0; $i < count($c[0]); $i++) { 
                $c[$stroka][$i] = 0;
        }
       
        return $c;
    }


    function ZamenaStolbca($c,$stolbec)
    {
        for ($i=0; $i < count($c); $i++) 
        {
            $c[$i][$stolbec] = 0;
        }
        return $c;
    }
Проблема вот в чем: первый элемент ищется нормально. Всё зануляется, всё работает. А дальше, индексы минимального элемента принимается (0;0), т.е. первый элемент. И всегда последующий становится первым элементом...
Возможно проблема в цикле или ещё в чём-то. Если можете, подскажжите, пожалуйста. Заранее спасибо!
==============================================
Кратко о методе минимального элемента в транспортной задаче:
В матрице тарифов ищется минимальный элемент запоминаются его индексы $k, $t. Затем в матрицу погрузок вносится минимальный элемент из массивов запасов и потребностей min($m[$k],$n[$t]). В массиве $m[k] (или $n[$t]) этот минимальный элемент зануляется путём вычитания из него большего, а матрице тарифов вычёркивается строка (или столбец), считая, что потребности поставщика (или получателя) удовлетворены, т.е.$m[k]=0 (или $n[k]=0). И далее идёт до тех пор, пока не будут удовлетворены все потребности, т.е. массив $m и $n должны быть будут пустыми.
 
Сверху