Простейший способ решить задачу похожую на линейное программирование?

#python #алгоритм

Есть много массивов, каждый элемент которых - набор из 7ми floats.

На i-м месте каждого массива лежит набор, который должен всплыть максимально вверх
(i для каждого массива разное).

Нужно найти такие float-параметры, чтобы при домножении на них

sum(p*x for p,x in zip(params, pack)) --->> max  for each array

сумма заданного набора была максимальной, т.е. набор всплыл вверх при
сортировке.

Расскажите, пожалуйста, Ваши идеи.

Заранее спасибо.

Edit:

# Для простоты рассмотрим для 2х floats
# Дано:
array1 = [(1,4),(2,7),(3,1)] (i=2)
array2 = [(1,4),(2,5),(3,6)] (i=1)
...

# Найти:
p1 и p2
# чтобы p1 * array1[i][0] + p2 * array1[i][1] --->> max

# очевидно, что надо увеличивать те координаты набора,
# которые уже больше, чем у остальных,
# и уменьшать те координаты, которые у набора меньше

# Мой вариант решения:
p1, p2 = 1, 1 
for array in [array1, array2, ...]:
    array = np.array(array)

    stats, means = [], []
    for column in array.T:
        # 5-я порядковая статистика от максимума
        stats.append(np.partition(column, -5)[-5])
        means.append(np.mean(column))

    for j,coord in enumerate(array[i,:]):
        # Если координата искомого вектора достаточно велика
        # относительно других наборов в массиве -
        # делаем её ещё больше
        if stats[j] <= coord:
            p[i] += means[i] # p1 | p2
        else:
            # иначе делаем её по меньше
            p[i] += 1. / means[i] # p1 | p2

# В конце делим на количество массивов
p1 /= len(arrays)
p2 /= len(arrays)

    

Ответы

Ответ 1

Задача сложна, но интересна.

Сразу оговоримся, что вектор решения x в исходной постановке определён с точностью
до произвольного положительного множителя.

 1. Постановка задачи

Условия вида sum(ajxj) > sum(bjxj) легко приводятся к виду sum(сjxj) > 0.  

Если принять в качестве цели минимизацию суммы мест, занимаемых заданными наборами
в своих списках, то теперь целевая функция - это количество неравенств, которые удовлетворяются
вектором решения.

Целевая функция нелинейна, поэтому оптимизация вычислений по аналогии с симплекс-методом
невозможна.

 2. Геометрическая интерпретация

Каждому неравенству от n переменных соответствует n-мерное полупространство, граница
которого проходит через начало координат.
При этом каждой невырожденной системе из n неравенств соответствует n--гранный угол
в n-мерном пространстве с вершиной в начале координат.
Решение задачи представляет собой многогранный угол, который является частью остальных.
Поэтому достаточно построить все допустимые многогранные углы, брать внутри каждого
из них тестовую точку и подставлять её в неравенства задачи.

 3. Метод исключений Йордана

Пусть у нас есть система m неравенств от n переменных (n

y0 = с00x0 + с01x1 + ... +с0,n-1xn-1 > 0
y1 = с10x0 + с11x1 + ... + с1,n-1xn-1 > 0
y2 = с20x0 + с21x12 +  ... + с2,n-1xn-1> 0  



ym-1 = сm-1,0x0 + сm-1,1x1 + сm-1,n-1xn-1> 0

Метод исключений Йордана состоит в переходе от прямоугольного базиса {x0, x1, ...,
xn-1} к аффинному базису многогранного угла {y0, y1, ..., yn-1}. При этом каждая переменная
xi выражается через переменную yi с тем же индексом. Для выбора другого базиса достаточно
поменять неравенства местами.  

Метод Йордана понятен и хорошо работает на прямоугольных матрицах.
Сначала из уравнения для  yi выражается xi, и полученные коэффициенты записываются
на место использованного уравнения. 
Затем полученное выражение для xi подставляется в остальные уравнения системы, и
это приводит к корректировке их коэффициентов. 

Исключение переменных по Йордану можно проводить в произвольном порядке. Но для достижения
устойчивого результата следует выбирать наибольший диагональный элемент.
По окончании процедуры в первых n строках матрицы оказываются выражения для компонент
вектора x, а на остальных - оставшиеся неравенства в новом базисе.

 4. Проверка выполнения неравенств

Проверка выполнения неравенств производится в выбранном базисе.
Для проверки выбирается тестовый вектор y = [1,1,...,1], и это сразу обеспечивает
выполнение базисных неравенств. Остальные неравенства проверяются подстановкой тестового
вектора в последние (m-n) уравнений и проверкой знака результата.

Предполагается, что ранг системы (количество независимых неравенств) не меньше количества
независимых переменных задачи.

Заметим, что вместо пп.3-4 можно решать систему уравнений y1=1, y2=1,... для каждого
выбранного базиса, а получаемый решение x подставлять в неиспользованные уравнения системы.

 5. Описание программы

Программа содержит следующие функции:
print_1d(), print_2d(), print_3d() - вывод 1-2-3-мерных массивов;
array_sub() - разность векторов;
array_scale() - умножение вектора на число;
task_to_unequals() - преобразование исходной задачи в систему неравенств;
gen_combi() - генератор сочетаний;
rows_to_order() - перестановка строк матрицы в заданном порядке;
jordan() - метод исключений Йордана для диагональных элементов (с выбором разрешающего
элемента);
rank() - подсчёт количества выполненных неравенств;
test_subs() - тестирование подстановок;
coeff_to_x - расчёт значений независимых переменных x для тестового вектора с единичными
координатами.

Программа выполняет следующие действия:


Преобразует исходную задачу в систему неравенств
Генерирует все возможные базисы (перестановки неравенств системы).
Вычисляет целевую функцию для полученных перестановок, прекращая вычисления при достижении
максимально возможного результата.
Выводит результаты, в том числе количество выполненных неравенств и вектор решения.


 6. Текст программы (на языке PHP)

$task = [
    [2,[1,4],[2,7],[3,1]],
    [1,[1,4],[2,5],[3,6]]
];

// Вывод одномерного массива
function print_1d($text, $v){
    $eps = 1e-7;
    print "$text"."[";
    $flag = false;
    foreach($v as $key=>$item){
        if($flag) print ", ";
        $flag = true;
        if(abs((int)$item - $item) > $eps){
            printf("%.3f", $item);
        }else{
            print $item;
        }
    } 
    print "], ";
}

// Вывод двумерного массива
function print_2d($text, $v){
    print "$text"."[";
    foreach($v as $key => $item){
        //print " $key => ";
        print_1d("", $item);
    } 
    print "], ";
}

// Вывод трёхмерного массива
function print_3d($text, $data){
    print "
$text"."[";
    foreach($data as $key=>$item){
        print "
 $key => [";
        foreach($item as $v){
            if(is_numeric($v)){
                print "$v, ";
            }else{
                print_1d("",$v);
            }
        }
        print "],";
    }
    print "
],";
}

// Разность векторов
function array_sub($v1, $v2){
    $sub = array_map(function($a, $b){
        return $a - $b;
    }, $v1, $v2);
    return $sub;
}

// Умножение вектора на число
function array_scale($v, $factor){ 
    return array_map(function($item) use($factor){
        return $item * $factor;
    }, $v);
}

// Преобразование задачи в систему неравенств   
function task_to_unequals($task){ 
    $u = [];
    foreach($task as $arr){
        foreach($arr as $key => $item){
            if(is_numeric($item)){
                $key_g = $item;
                $goal = $arr[$item];
            }elseif($key != $key_g){
                $u[] = array_sub($goal, $item);
            }
        }
    }
    return $u;
}

// генератор сочетаний
function gen_combi($n, $m, $all_subs = null){
    $new_subs = [];
    if($m == 1){
        for($i = 0; $i < $n; $i++){
            $new_subs[] = [$i];
        }
    }else{
        $all_subs = gen_combi($n, $m-1, $all_subs);
        foreach($all_subs as $subs){                
            for($k = end($subs)+1; $k < $n; $k++){
                $s = $subs;
                $s[] = $k;
                $new_subs[] = $s;
            }
        }
    }   
    return $new_subs;
}

// Перестановка строк матрицы в заданном порядке
function rows_to_order($matrix, $subs){
    $columns = count($matrix[0]);
    foreach($subs as $l => $k){
        $c[$l] = $matrix[$k];
    }
    $rows = count($matrix);
    for($k = 0; $k < $rows; $k++){
        if(!(in_array($k, $subs))){
            $c[] = $matrix[$k];
        }
    }
    return $c;
}

// Йордановы исключения x[i] -> y[i] 
function jordan(&$c){
    $eps = 1e-7;
    $rows = count($c);
    $cols = count($c[0]);
    $queue = range(0, $cols-1);
    while(!empty($queue)){
        print_1d("
не обработано: ", $queue);
        // Выбор наибольшего по модулю диагонального элемента из очереди
        $max_abs = 0;
        foreach($queue as $key){
            $cur = abs($c[$key][$key]);
            if($cur > $max_abs){
                $i = $key;
                $max_abs = $cur;
            }   
        }
        unset($queue[$i]);      // удаление выбранного элемента из очереди
        if($max_abs < $eps){    // если выбранный элемент нуль, результат - ошибка
            $c = false;
            return;
        }else{
            $beta = 1/$c[$i][$i];   
            $c[$i] = array_scale($c[$i], -$beta);
            $c[$i][$i] = $beta;
            for($k = 0; $k < $rows; $k++){
                if($k != $i){
                    $gamma = $c[$k][$i];
                    $c[$k] = array_sub($c[$k], array_scale($c[$i], -$gamma));
                    $c[$k][$i] = $gamma*$beta;
                }
            }
        }
        print_2d(" выбрано: $i  результат: ", $c);
    }
}

// подсчёт количества выполненных неравенств
function rank($c){
    //print_2d("
rank: c = ", $c);
    $cols = count($c[0]);
    $r = $cols;
    foreach($c as $key => $v){
        if (($key >= $cols) && (array_sum($v) > 0)){
            $r++;   
        }
    }
    return $r;
}

// тестирование подстановок
function test_subs($unequals, $all_subs){
    $rows = count($unequals);
    $cols = count($unequals[0]);
    $rank = 0;
    foreach($all_subs as $subs){
        $r = 0;
        print_1d("

Базис: ", $subs);
        $c = rows_to_order($unequals, $subs);
        print_2d("
перестановка строк:
", $c);
        print("
исключение переменных по Йордану");
        jordan($c);
        if($c !== false){
            print_1d("
Тестовый вектор: y = ", array_fill(0,$cols,1));
            $r = rank($c);
            $x = coeff_to_x($c);
            print "
Выполнено неравенств: $r";
        }else{
            print"
Выполнено неравенств: 0";
        }
        if($r > $rank){
            $rank = $r;
            $coeff = $c;
        }
        if($r == $rows){
            break;
        }
    }
    return $coeff;
}

// вычисление независимых переменных по коэффициентам матрицы
function coeff_to_x($coeff){
    $cols = count($coeff[0]);
    $x = [];
    for($i= 0; $i < $cols; $i++){
        $x[] = array_sum($coeff[$i]);
    }
    return $x;
}

print_3d("Исходная задача:
", $task);
$unequals = task_to_unequals($task);
$rows = count($unequals);
$cols = count($unequals[0]);
print_2d("

Массив неравенств:
", $unequals);  
print("

Генератор базисов:
");
$all_subs = gen_combi($rows, $cols);
print_2d("all_subs = ", $all_subs);
$coeff = test_subs($unequals, $all_subs);   
print_2d("

РЕЗУЛЬТАТЫ
Система в оптимальном базисе: ", $coeff);
print_1d("
Bектор в оптимальном базисе: y = ", array_fill(0,$cols,1));
$r = rank($coeff);
$x = coeff_to_x($coeff);
print_1d("
Выполнено неравенств: $r

РЕШЕНИЕ: x = ", $x);


 7. Результаты



Исходная задача:
[
 0 => [2, [1, 4], [2, 7], [3, 1], ],
 1 => [1, [1, 4], [2, 5], [3, 6], ],
],

Массив неравенств:
[[1, 3], [-1, 6], [-1, -1], [-2, -2], ], 

Генератор базисов:
all_subs = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], ], 

Базис: [0, 1], 
перестановка строк:
[[1, 3], [-1, 6], [-1, -1], [-2, -2], ], 
исключение переменных по Йордану
не обработано: [0, 1],  выбрано: 1  результат: [[1.500, 0.500], [0.167, 0.167], [-1.167,
-0.167], [-2.333, -0.333], ], 
не обработано: [0],  выбрано: 0  результат: [[0.667, -0.333], [0.111, 0.111], [-0.778,
0.222], [-1.556, 0.444], ], 
Тестовый вектор: y = [1, 1], 
Выполнено неравенств: 2

Базис: [0, 2], 
перестановка строк:
[[1, 3], [-1, -1], [-1, 6], [-2, -2], ], 
исключение переменных по Йордану
не обработано: [0, 1],  выбрано: 0  результат: [[1, -3], [-1, 2], [-1, 9], [-2, 4], ], 
не обработано: [1],  выбрано: 1  результат: [[-0.500, -1.500], [0.500, 0.500], [3.500,
4.500], [0, 2], ], 
Тестовый вектор: y = [1, 1], 
Выполнено неравенств: 4

РЕЗУЛЬТАТЫ
Система в оптимальном базисе: [[-0.500, -1.500], [0.500, 0.500], [3.500, 4.500],
[0, 2], ], 
Bектор в оптимальном базисе: y = [1, 1], 
Выполнено неравенств: 4

РЕШЕНИЕ: x = [-2, 1],