Есть такая математическая головоломка: дан прямоугольник, который надо заполнить числами так, чтобы суммы по строкам и столбцам были равны указанным значениям. Например, дан прямоугольник (3 на 2) и ограничения:

* * |4
* * |1
* * |2
----
3 4

Задача допускает несколько решений:

0 4 |4 3 1 |4
1 0 |1 0 1 |1
2 0 |2 0 2 |2
---- ----
3 4 3 4

Накладывается ограничение оптимизации: количество ненулевых чисел в ячейках должно быть минимальным. То есть решением задачи является первый вариант.
Хотелось бы разработать алгоритм решения. Сам думаю в сторону симплекс-метода. Только остается вопрос насчет целевой функции - она ведь не будет линейной. Если у кого-то есть мысли буду очень рад услышать.

Ошибся с форматированием:
Есть такая математическая головоломка: дан прямоугольник, который надо заполнить числами так, чтобы суммы по строкам и столбцам были равны указанным значениям. Например, дан прямоугольник (3 на 2) и ограничения:

* * |4
* * |1
* * |2
----
3 4

Задача допускает несколько решений:

0 4 |4
1 0 |1
2 0 |2
----
3 4

3 1 |4
0 1 |1
0 2 |2
----
3 4
Накладывается ограничение оптимизации: количество ненулевых чисел в ячейках должно быть минимальным. То есть решением задачи является первый вариант.
Хотелось бы разработать алгоритм решения. Сам думаю в сторону симплекс-метода. Только остается вопрос насчет целевой функции - она ведь не будет линейной. Если у кого-то есть мысли буду очень рад услышать.

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