Усложненная задача о назначениях

[ArgMax]

Здравствуйте!
Есть оптимизационная задача следующего вида.
Входные данные:
1. Матрица вероятностей: $P = \{p_i_j\}_{i=1,..,n; j=1,..,m},\, p_i_j \in \mathbb{R},\, p_i_j \in [0, 1];$
2. $k_j \in \mathbb{R},\, k_j \in (0, \infty),\, j=1,..,m.$
Функционал качества:
$Q = \sum_{j=1}^m{ k_j \cdot (1 - \prod_{i=1}^n{(1 - p_i_j x_i_j)} )} \to \max_{\text{для всех}\, x_i_j},$ $ \text{где}\, x_i_j \, \text{принимает значения}\, 0, \text{либо}\, 1 \quad (i=1,..,n; j=1,..,m).$
Ограничения:
$\sum_{j=1}^m{x_i_j} = 1, \, i=1,..,n$ (т.е. в каждой строке выбираем один столбец). В столбце может быть выбрано несколько строк. Если в столбце выбрана только одна строка, то соответствующее слагаемое в функционале превращается в $k_j p_i_j x_i_j$.
Это задача целочисленного нелинейного программирования(с квазивыпуклым функционалом). Не зная можно ли расширить точные методы решения задачи о назначениях, решил применить методы глобальной оптимизации.
1. Поиск максимума из выборки случайных назначений.
2. Добавил эвристику, которая после применения первого метода искала наилучшее значение функционала при построчном переназначении элементов (для каждой строки).

Теперь встал вопрос о точности найденного решения, а для больших матриц(при n=m=50) не очевидно как его найти.
Существует ли точный метод решения и ли хотя бы сходящийся с известной величиной ошибки?
Заранее благодарю!

[mserg]

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

Что касается "метода" - то сейчас это сложная система техник, объединенных в единый "алгоритм". Если найдется оптимум - то вкратце напишу.

[ArgMax]

К сожалению, пока тестирую на случайной матрице, приведенной ниже. $k_j = 1,\, j=1,..,m.$

0.97;0.08;0.43;0.64;0.69;0.02;0.54;0.08;0.23;0.4;0.34;0.64;0.96;0.89;0.75;0.73;0.61;0.37;0.52;0.39;0.96;0.27;0.37;0.82;0.04;0.54;0;0.91;0.92;0.37;0.96;0.27;0.72;0.68;0.09;0.99;0;0.26;0.06;0.84;0.88;0.32;0.07;0.81;0.84;0.46;0.15;0.91;0.65;0.36
0.45;0.53;0.81;0.48;0.77;0.8;0.4;0.22;0.17;0.8;0.03;0.24;0.72;0.24;0.16;0.6;0.59;0.3;0.93;0.94;0.39;0.86;0.93;0.26;0.46;0.45;0.88;0.38;0.93;0.61;0.35;0.08;0.21;0.55;0.65;0.02;0.49;0.52;0.88;0.69;0.24;0.8;0.58;0.95;0.23;0.28;0.37;0.48;0.33;0.62
0.01;0.84;0.56;0.7;0.25;0.51;0.27;0.91;0.01;0.53;0.42;0.5;0.62;0.67;0.18;0.02;0.38;0.81;0.38;0.29;0.34;0.94;0.04;0.26;0.38;0.01;0.8;0.68;0.76;0.09;0.26;0.02;0.51;0.03;0.59;0.51;0;0.5;0.09;0.59;0.22;0.07;0.62;0.15;0.31;0.18;0.54;0.26;0.35;0.41
0.68;0.4;0.6;0.48;0.63;0.31;0.98;0.61;0.81;0.32;0.64;0.65;0.51;0.03;0.15;0.54;0.22;0.66;0.63;0.46;0.1;0.99;0.99;0.88;0.89;0.39;0.56;0.78;0.7;0.3;0.33;0.71;0.94;0.69;0.06;0.01;0.23;0.79;0.42;0.61;0.28;0.27;0.97;0.3;0.08;0.88;0.14;0.11;0.22;0.1
0.53;0.85;0.6;0.64;0.24;0.13;0.94;0.59;0.79;0.45;0.26;0.9;0.9;0.25;0.14;0.87;0.74;0;0.98;0.97;0.5;0.16;0.98;0.89;0.64;0.22;0.85;0.9;0.06;0.45;0.71;0.04;0.02;0.22;0.84;0.52;0.66;0.96;0.91;0.06;0.04;0.69;0.02;0.95;0.41;0.24;0.9;0.26;0.3;0.45
0.82;0.17;0.15;0.42;0.35;0.11;0.8;0.19;0.54;0.48;0.02;0.92;0.53;0.23;0.07;0.29;0.86;0.67;0.72;0.54;0.9;0.65;0.93;0.12;0.98;0.37;0.3;0.21;0.59;0.43;0.65;0.79;0.59;0.48;0.72;0.55;0.18;0.05;0.61;0.39;0.06;0.43;0.87;0.52;0.19;0.68;0.23;0.94;0.94;0.53
0.7;0.68;0.4;0.16;0.76;0.88;0.97;0.15;0.86;0.98;0.89;0.5;0.36;0.68;0.35;0.7;0.38;0.67;0.01;0.14;0.44;0.56;0.91;0.27;0.23;0.29;0.27;0.3;0.7;0.21;0.87;0.93;0.61;0.16;0.61;0.58;0.04;0.6;0.08;0.06;0.4;0.09;0.24;0.82;0.9;0.91;0.32;0.7;0.04;0.58
0.02;0.31;0.99;0.21;0.71;0.95;0.53;0.87;0.67;0.58;0.6;0.98;0.67;0.47;0.64;0.8;0.08;0.84;0.62;0.04;0.23;0.54;0.44;0.01;0.04;0.68;0.71;0.41;0.6;0.13;0.42;0.4;0.78;0.8;0.89;0.7;0.67;0.48;0.3;0.26;0.36;0.92;0.02;0.57;0.52;0.48;0.35;0.35;0.07;0.09
0.93;0.48;0.54;0.18;0.87;0.89;0.12;0.91;0.83;0.6;0.81;0.02;0;0.89;0.25;0.36;0.39;0.87;0.5;0.97;0.84;0.11;0.3;0.59;0.63;0.18;0.15;0.04;0.83;0.25;0.52;0.74;0.69;0.32;0.33;0.9;0.08;0.87;0.29;0.28;0.95;0.73;0.11;0.78;0.75;0.82;0.7;0.35;0.67;0.72
0.46;0.23;0.25;0.36;0.52;0.16;0.76;0.13;0.16;0.58;0.55;0.25;0.08;0.42;0.22;0.16;0.43;0.11;0.87;0.42;0.43;0.75;0.66;0.56;0.88;0.61;0.7;0.93;0.15;0.38;0.56;0.41;0.33;0.17;0.77;0.66;0.76;0.7;0.63;0.59;0.34;0.03;0.79;0.77;0.11;0.02;0.17;0.72;0.58;0.89
0.52;0.98;0.78;0.91;0.2;0.98;0.99;0.42;0.37;0.31;0.94;0.93;0.15;0.58;0.09;0.76;0.34;0.62;0.72;0.94;0.82;0.5;0.67;0.3;0.63;0.88;0.97;0.97;0.41;0.56;0;0.75;0.4;0.67;0.58;0.2;0.42;0.37;0.19;0.53;0.37;0.69;0.48;0.07;0.78;0.03;0.24;0.39;0.1;0.5
0.53;0.75;0.45;0.35;0.33;0.44;0.24;0.3;0.73;0.64;0.47;0.72;0.5;0.62;0.02;0.57;0.46;0.35;0.43;0.94;0.77;0.99;0.09;0.77;0.53;0.77;0.48;0.4;0.5;0.19;0.93;0.56;0.99;0.34;0.3;0.11;0.73;0.21;0.89;0.75;0.53;0.63;0.14;0.08;0.35;0.49;0.99;0.12;0.07;0.32
0.31;0.42;0.89;0.96;0.05;0.29;0.21;0.94;0.14;0.13;0.45;0;0.81;0.38;0.61;0.75;0.07;0.52;0.43;0.44;0.35;0.27;0.15;0.77;0.14;0.01;0.77;0.09;0.02;0.72;0.46;0.94;0.75;0.96;0.55;0.95;0.22;0.92;0.99;0.35;0.34;0.15;0.51;0.77;0.88;0.54;0.61;0.29;0.44;0.88
0.54;0.05;0.44;0.87;0.08;0.15;0.51;0.33;0.42;0.22;0.63;0.77;0.64;0.98;0.38;0.59;0.3;0.93;0.67;0.01;0.41;0.36;0.91;0.88;0.02;0.83;0.7;0.27;0.53;0.84;0.99;0.94;0.72;0.01;0.15;0.25;0.87;0.72;0.9;0.73;0.23;0.75;0.42;0.99;0.72;0.44;0.44;0.81;0.56;0.26
0.92;0.94;0.33;0.92;0.61;0.26;0.44;0.93;0.93;0.76;0.98;0.53;0.3;0.26;0.47;0.4;0.21;0.74;0.1;0.73;0.54;0.38;0.96;0.64;0.48;0.43;0.81;0.23;0.14;0.29;0.59;0.01;0.62;0.02;0.36;0.52;0.17;0.35;0.82;0.88;0.71;0.59;0.6;0.72;0.52;0.27;0.16;0.65;0.84;0.67
0.35;0.29;0.63;0.91;0.57;0.9;0.32;0.11;0.38;0.47;0.95;0.82;0.2;0.34;0.52;0.57;0.41;0.91;0.62;0.37;0.71;0.6;0.95;0.59;0.71;0.33;0.14;0.51;0.71;0.33;0.99;0.7;0.23;0.45;0.34;0.79;0.9;0.65;0.22;0.09;0.96;0.25;0.31;0.06;0.07;0.18;0.14;0.59;0.82;0.09
0.88;0.38;0.57;0.36;0.66;0.96;0.66;0.86;0.19;0.05;0.56;0.35;0.42;0.12;0.1;0.49;0.42;0.68;0.62;0.04;0.63;0.67;0.07;0.85;0.58;0.12;0.71;0.17;0.8;0.36;0.25;0.28;0.88;0.6;0.34;0.2;0.99;0.54;0.51;0.42;0.03;0.41;0.98;0.08;0.7;0.26;0.64;0.56;0.23;0.01
0.98;0.64;0.7;0.23;0.63;0.46;0.41;0.64;0.9;0.02;0.27;0.52;0.76;0.62;0.44;0.38;0.83;0.25;0.5;0.17;0.36;0.31;0.62;0.63;0.82;0.6;0.78;0.71;0.89;0.42;0.45;0.37;0.06;0.45;0.43;0.07;0.91;0.53;0.43;0.7;0.18;0.86;0.1;0.35;0.05;0.79;0.07;0.24;0.76;0.35
0.91;0.66;0.66;0.73;0.21;0.55;0.45;0.74;0.46;0.42;0.6;0.77;0.01;0.9;0.82;0.18;0.59;0.17;0.53;0.05;0.17;0.59;0.72;0.2;0.62;0.45;0.25;0.44;0.14;0.86;0.33;0.41;0.03;0.15;0.89;0.86;0.99;0.17;0.09;0.39;0.26;0.01;0.59;0.78;0.46;0.83;0.74;0.27;0.01;0.2
0.51;0.95;0.14;0.37;0.84;0.33;0.57;0.11;0.47;0.73;0.71;0.4;0.62;0.12;0.45;0.45;0.56;0.03;0.45;0.7;0.82;0.86;0.87;0.71;0.96;0.64;0.33;0.92;0.17;0.61;0.37;0.08;0.54;0.07;0.78;0.29;0.37;0.61;0.21;0.19;0.57;0.09;0.41;0.18;0.26;0.19;0.53;0.68;0.57;0.86
0.97;0.4;0.62;0.88;0.73;0.44;0.59;0.69;0.37;0.73;0.33;0.48;0.75;0.13;0.02;0.44;0.81;0.75;0.41;0.75;0.54;0.98;0.05;0.52;0.17;0.04;0.38;0.11;0.8;0.97;0.14;0.87;0.3;0.44;0.63;0.2;0.06;0.12;0.34;0.57;0.66;0.3;0.96;0.87;0.72;0.27;0.02;0.38;0.6;0.32
0.18;0.92;0.98;0.69;0.16;0.92;0.17;0.58;0.02;0.44;0.17;0.38;0.56;0.82;0.05;0.47;0.55;0.39;0.88;0.27;0.8;0.13;0.2;0.2;0.67;0.87;0.27;0.1;0.04;0.1;0.42;0.02;0.81;0.03;0.79;0.54;0.14;0.1;0.59;0.28;0.02;0.77;0.68;0.05;0.47;0.7;0.84;0.91;0.92;0
0.62;0.81;0.24;0.81;0.96;0.13;0.93;0.31;0.17;0.22;0.86;0.04;0.83;0.39;0.62;0.68;0.65;0.75;0.63;0.13;0.87;0.75;0.82;0.15;0.54;0.37;0.87;0.39;0.22;0.74;0.82;0.4;0.89;0.26;0.95;0.6;0.85;0.26;0.76;0.76;0.65;0.51;0.69;0.23;0.72;0.45;0.13;0.29;0.34;0.51
0.26;0.27;0.36;0.41;0.01;0.01;0.66;0.73;0.79;0.74;0.99;0.02;0.87;0.67;0.67;0.14;0.61;0.75;0.71;0.64;0.02;0.18;0.03;0.57;0.09;0.92;0.2;0.06;0.7;0.6;0.44;0.01;0.72;0.72;0.42;0.55;0.72;0.51;0.44;0.55;0.32;0.43;0.95;0.05;0.53;0.6;0.78;0.65;0.26;0.73
0.71;0.41;0.12;0.28;0.79;0.28;0.3;0.63;0.35;0.21;0.24;0.49;0.67;0.75;0.42;0.93;0.97;0.9;0.63;0.59;0.09;0.22;0.54;0.77;0.83;0.22;0.18;0.44;0.82;0.96;0.29;0.27;0.24;0.59;0.34;0.5;0.82;0.17;0.59;0.75;0.22;0.06;0.88;0.53;0.45;0.92;0.42;0.9;0.58;0.36
0.94;0.55;0.2;0.42;0.25;0.93;0.95;0.77;0.32;0.14;0.77;0.21;0.8;0;0.34;0.96;0.12;0.05;0.79;0.46;0.62;0.92;0.75;0.92;0.9;0.08;0.4;0;0.48;0.54;0.44;0.35;0.05;0.11;0.85;0.19;0.29;0.02;0.93;0.1;0.72;0.39;0.49;0.57;0.57;0.45;0.66;0.54;0.46;0.53
0.86;0.32;0.73;0.03;0.25;0.61;0.5;0.85;0.87;0.47;0.78;0.02;0.31;0.74;0.19;0.08;0.24;0.89;0.18;0.05;0.67;0.41;0.29;0.66;0.22;0.53;0.45;0.06;0.79;0.44;0.23;0.25;0.92;0.96;0.97;0.56;0.57;0.08;0.35;0;0.71;0.13;0.14;0.37;0.27;0.56;0.54;0.34;0.66;0.52
0.47;0.93;0.36;0.42;0.85;0.44;0.98;0.2;0.28;0.18;0.29;0.25;0.48;0.62;0.68;0.52;0.05;0.18;0.85;0.45;0.71;0.75;0.14;0.1;0.1;0.92;0.69;0.35;0.04;0.48;0.54;0.08;0.41;0.47;0.13;0.65;0.38;0.33;0.95;0.37;0.61;0.73;0.97;0.47;0.13;0.48;0.26;0.18;0.11;0.18
0.56;0.32;0;0.71;0.23;0.18;0.24;0.54;0.85;0.14;0.9;0.86;0.09;0.89;0.96;0.07;0.72;0.78;0.09;0.32;0.73;0.82;0.06;0.2;0.26;0.65;0.66;0.02;0.59;0.41;0.93;0.39;0.39;0.46;0.51;0.59;0.47;0.45;0.48;0.32;0.65;0.77;0.51;0.58;0.25;0.27;0.12;0.36;0.16;0.33
0.38;0.13;0.02;0.98;0.53;0.99;0.24;0.91;0.03;0.88;0.38;0.37;0.37;0.58;0.68;0.45;0.4;0.49;0.8;0.04;0.8;0.3;0.31;0.24;0.45;0.46;0.8;0.5;0.88;0.87;0.74;0.3;0.49;0.26;0;0.6;0.71;0.42;0.55;0.81;0.75;0.43;0.79;0.49;0.25;0.39;0.05;0.7;0.71;0.25
0.61;0.33;0.19;0.39;0.3;0.35;0.5;0.06;0.3;0.23;0.98;0.71;0.4;0.49;0.9;0.24;0.94;0.1;0.92;0.99;0.84;0.75;0.24;0.11;0.06;0.91;0.17;0.37;0.74;0.77;0.31;0.12;0.38;0.09;0;0.44;0.71;0.78;0;0.03;0.06;0.72;0.8;0.57;0.33;0.91;0.24;0.02;0.25;0.23
0.87;0.53;0.98;0.29;0.04;0.75;0.92;0.06;0.71;0.68;0.89;0.07;0.97;0.1;0.44;0.37;0.32;0.16;0.56;0.97;0.09;0.76;0.52;0.59;0.15;0.36;0.01;0.98;0.72;0.3;0.08;0.03;0.34;0.38;0.5;0.15;0.28;0.28;0.2;0.38;0.49;0.7;0.32;0.1;0.3;0.22;0.82;0.55;0.55;0.56
0.19;0.56;0.81;0.7;0.88;0.74;0.47;0.93;0.89;0.36;0.38;0.84;0.07;0.54;0.39;0.47;0.5;0.86;0.59;0.69;0.51;0.95;0.17;0.68;0.11;0.28;0.11;0.65;0.04;0.69;0.48;0.15;0.88;0;0.78;0.37;0.83;0.11;0.96;0;0.68;0.47;0.46;0.81;0.62;0.16;0.51;0.63;0.09;0.44
0.83;0.39;0.24;0.86;0.45;0.17;0.24;0.43;0.43;0.58;0.07;0.14;0.61;0.42;0.14;0.55;0.06;0.72;0.47;0.93;0.81;0.2;0.02;0.93;0.76;0.13;0.58;0.9;0.22;0.94;0.6;0.42;0.34;0.5;0.23;0.17;0.7;0.58;0.05;0.57;0.13;0.62;0.98;0.25;0.12;0.05;0.17;0.31;0.31;0.4
0.39;0.07;0.91;0.09;0.88;0.49;0.23;0.43;0.58;0.1;0.36;0.06;0.01;0.13;0.05;0.89;0.76;0.25;0.67;0.26;0.78;0.21;0.28;0.8;0.29;0.72;0.23;0.31;0.05;0.86;0.03;0.84;0.24;0.79;0.23;0.13;0.13;0.06;0.4;0.11;0.39;0.77;0.17;0.2;0.91;0.39;0.72;0.52;0.24;0.82
0.82;0.43;0.61;0.66;0.17;0.21;0.64;0.22;0.83;0.04;0.87;0.94;0.91;0.53;0.16;0.6;0.34;0.33;0.61;0.38;0.64;0.31;0.51;0.92;0.92;0.83;0.82;0.86;0.31;0.08;0.5;0.93;0.61;0.25;0.04;0.42;0.92;0.01;0.8;0.71;0.23;0.33;0.94;0.77;0.18;0.35;0.38;0.7;0.63;0.32
0.44;0.68;0.52;0.2;0.6;0.85;0.9;0.29;0.91;0.68;0.66;0.33;0.54;0.6;0.57;0.77;0.82;0.12;0.89;0.11;0.28;0.19;0.06;0.82;0.9;0.09;0.62;0.61;0.27;0.29;0.09;0.56;0.35;0;0.47;0.77;0.42;0.9;0.43;0.22;0.24;0.15;0.44;0.78;0.41;0.17;0.9;0.95;0.32;0.56
0.6;0.16;0.09;0.62;0.31;0.42;0.99;0.09;0.17;0.99;0.62;0.53;0.79;0.49;0.37;0.22;0.48;0;0.83;0.65;0.87;0.79;0.56;0.38;0.22;0.32;0.98;0.3;0.84;0.66;0.21;0.34;0.12;0.87;0.3;0.64;0.39;0.58;0.38;0.8;0.32;0.62;0.67;0.58;0.14;0.76;0.47;0.02;0.02;0.65
0.49;0.44;0.62;0.08;0.84;0.65;0.44;0.95;0.89;0.01;0.67;0.31;0.41;0.9;0.38;0.69;0.79;0.85;0.34;0.7;0.55;0.76;0.11;0.7;0.14;0.96;0.94;0.25;0.2;0.28;0.46;0.21;0.52;0.17;0.07;0.76;0.02;0.72;0.7;0.38;0.23;0.61;0.66;0.61;0.48;0.52;0.5;0.17;0.24;0.21
0.28;0.69;0.24;0.96;0.74;0.78;0.84;0.11;0.99;0.43;0.08;0.64;0.04;0.6;0.1;0.14;0.03;0.72;0.65;0.19;0.84;0.73;0.87;0.37;0.18;0.13;0.59;0.29;0.16;0.56;0.74;0.29;0.33;0.07;0.47;0.56;0.65;0.23;0.68;0.52;0.17;0.34;0.95;0.63;0.52;0.45;0.93;0.26;0.98;0.75
0.58;0.46;0.85;0.89;0.45;0.63;0.91;0.03;0.17;0.43;0.88;0.21;0.52;0.35;0.32;0.29;0.23;0.24;0.43;0.08;0.06;0.97;0.99;0.6;0.54;0.55;0.17;0.45;0.44;0.77;0.76;0.26;0.92;0.77;0.63;0.1;0.09;0.66;0.25;0.7;0.3;0.67;0.37;0.21;0.58;0.64;0.79;0.35;0.77;0.8
0.25;0.18;0.79;0.23;0.38;0.03;0.24;0.53;0.17;0.75;0.52;0.91;0.25;0.85;0.39;0.84;0.92;0.39;0;0.06;0.96;0.11;0.31;0.26;0.89;0.04;0.05;0.05;0.96;0.8;0.95;0.88;0.43;0.05;0.14;0.11;0.62;0.75;0.33;0.58;0.18;0.52;0.52;0.24;0;0.39;0.35;0.55;0.01;0.85
0.5;0.43;0.83;0.81;0.51;0.22;0.9;0.93;0.8;0.12;0.08;0.45;0.27;0.93;0.21;0.32;0.83;0.32;0.35;0.73;0.46;0.44;0.77;0.72;0.56;0.64;0.67;0.28;0.09;0.94;0.01;0.63;0.69;0.69;0.35;0.56;0.79;0.09;0.69;0.85;0.87;0.75;0.78;0.7;0.17;0.89;0.31;0.36;0.03;0.29
0.57;0.2;0.46;0.41;0.34;0.98;0.88;0.31;0.52;0.22;0.52;0.54;0.62;0.3;0.83;0.76;0.04;0.42;0.33;0.21;0.13;0.83;0.71;0.13;0.72;0.81;0.36;0.89;0.68;0.92;0.69;0.12;0.31;0.01;0.85;0.59;0.53;0.74;0.49;0.45;0.24;0.1;0.48;0.01;0.38;0.82;0.55;0.53;0.78;0.29
0.95;0.12;0.28;0.68;0.91;0.09;0.24;0.69;0.16;0.5;0.77;0.84;0.21;0.16;0.99;0.16;0.08;0.92;0.45;0.13;0.54;0.9;0.18;0.75;0.46;0.88;0.34;0.9;0.33;0.22;0.85;0.33;0.72;0.81;0.68;0.87;0.47;0.85;0.39;0.4;0.53;0.14;0.94;0.38;0.76;0.48;0.35;0.64;0.18;0.79
0.47;0.07;0.59;0.19;0.76;0.54;0.21;0.8;0.78;0.66;0.74;0.72;0.49;0.63;0.69;0.43;0.47;0.37;0.88;0.88;0.93;0.63;0.68;0.07;0.71;0.2;0.29;0.46;0.88;0.94;0.83;0.44;0.11;0.15;0.69;0.78;0.72;0.78;0.41;0.6;0.82;0.63;0.45;0.88;0.37;0.82;0.81;0.32;0.27;0.5
0.05;0.02;0.3;0.29;0.79;0.31;0.8;0.66;0.56;0.13;0.37;0.85;0;0.94;0.13;0.1;0.63;0.85;0.88;0.01;0.07;0.55;0.82;0.73;0.26;0.24;0.82;0.48;0.68;0.59;0.92;0.33;0.02;0.75;0.98;0.87;0.33;0.8;0.16;0.25;0.41;0.17;0.4;0.38;0.91;0.83;0.45;0.36;0.01;0.86
0.38;0.31;0.1;0.83;0.93;0.63;0.42;0.97;0.56;0.7;0.19;0.88;0.12;0.67;0.27;0.19;0.12;0.76;0.67;0.53;0.57;0.17;0.49;0.58;0.47;0.77;0.07;0.82;0.54;0.44;0.56;0.63;0.74;0.05;0.38;0.35;0.56;0.74;0.96;0.92;0.99;0.54;0.8;0.31;0.45;0.39;0.73;0.14;0.61;0.93
0.87;0.06;0.69;0.69;0.87;0.36;0.55;0.49;0.29;0.43;0.74;0.58;0.39;0.58;0.54;0.15;0.08;0.9;0.99;0.22;0;0.24;0.54;0.6;0.65;0.8;0.33;0.14;0.79;0.4;0.69;0.93;0.52;0.74;0.05;0.17;0.76;0.19;0.56;0.94;0.63;0.03;0.23;0.79;0.14;0.17;0;0.08;0.95;0.1
0.3;0.25;0.83;0.4;0.71;0.04;0.78;0.47;0.06;0.27;0.26;0.05;0.64;0.85;0.23;0.07;0.69;0.71;0.47;0.36;0.18;0.41;0.8;0.44;0.42;0.47;0.18;0.51;0.1;0.61;0.39;0.34;0.85;0.5;0.12;0.9;0.96;0.96;0.5;0.57;0.13;0.55;0.08;0.54;0.74;0.73;0.51;0.72;0.52;0.45

[mserg]

Что-то получилось...

Решение 47.91 при доказанной верхней границе 48.2707:

  1, 36
  2, 44
  3, 8
  4, 22
  5, 19
  6, 25
  7, 10
  8, 12
  9, 1
  10, 50
  11, 28
  12, 47
  13, 39
  14, 14
  15, 40
  16, 31
  17, 43
  18, 42
  19, 37
  20, 2
  21, 30
  22, 3
  23, 5
  24, 11
  25, 17
  26, 16
  27, 34
  28, 7
  29, 15
  30, 4
  31, 20
  32, 13
  33, 33
  34, 24
  35, 45
  36, 32
  37, 48
  38, 27
  39, 26
  40, 9
  41, 23
  42, 29
  43, 46
  44, 6
  45, 18
  46, 21
  47, 35
  48, 41
  49, 49
  50, 38

Первый столбец в таблице выше - это номер строки, второй - назначенная колонка.

Мог что-нибудь напутать при формулировании задачи - тогда постановка решения в формулу критерия не даст 47.91 ...

[ArgMax]

Интересный результат. Действительно даёт 47.91. У меня лучшее решение было 47.15, которое находилось за несколько часов. Хотя решение со значением 46.5 нашлось за минуту. А каким образом, была вычислена верхняя граница? Она достижима?

[mserg]

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

Предварительно задача немного была переформулирована: выражение под знаком произведения была преобразовано в экспоненту (благо, переменные принимают всего по два значения). Далее произведение было заменено экспонентой с суммой в показателе.

Потом – метод ветвей и отсечений, который нашел допустимое значение и улучшил верхнюю границу. Приведенный в предыдущем сообщении результат был получен за несколько минут. После нескольких часов решения рекорд был улучшен до 47.93, а оценка верхней границы снижена до 48.25 с копейками. Достижимость верхней границы, видимо, останется риторическим вопросом...

[ArgMax]

Цитата:

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

Подразумевается метод нелинейного программирования? Что-то вроде этого: http://www.ccas.ru/personal/evtush/p/E2_R.pdf ?
Наверное были добавлены ограничения на $x_i_j$, например, $x_i_j \in [0,1]$.
Метод ветвей и отсечений использовал тот же релаксационный метод?

[mserg]

Для решения релаксационной задачи применялся метод внутренней точки; а на диапазоны переменных, ограничение, конечно, не снимались.

Многократное решение нелинейной задачи – довольно трудоемко и применение его в методе ветвей и отсечений проблематично.

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

Примерно так.

[ArgMax]

Цитата:

Многократное решение нелинейной задачи – довольно трудоемко и применение его в методе ветвей и отсечений проблематично.

Действительно трудоёмко. Матлаб пару часов вычислял, хотя я не заменял переменные, но перешел к экспонентам.

Цитата:

Можно пойти дальше – ввести дополнительные переменные для сумм – критерием будет сумма экспонент с показателями в виде дополнительных переменных.

В этом сомневаюсь, т.к. непонятно как потом распознавать результат вычислений.

$$y_j = \sum_{i=1}^n{\ln(1-p_i_j x_i_j)}$$

$$Q = \sum_{j=1}^m{k_j(1-e^{y_j})}$$

$y_j$ - это сумма по столбцу, а в столбце можно назначить несколько строк. Можно лишь узнать, что ни одной строки не назначено в столбце, если $y_j = 0$.

Цитата:

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

Это отличная идея! Благодарю!

[mserg]

Можно сделать замену:
$1-p x$ на $e^{q x}$
Могут быть некоторые заморочки при $p=1$, но это можно обойти.