система линейного уравнения с дополнительным ограничением минимальных переменных sum

Question

У меня есть система линейных уравнений, которую я уже приводил к матрице эшелонов строк с использованием исключения Гаусса-Джордана. Моя система с n переменными Xn (где Xn находится в N0 (= положительные целые числа)) имеет несколько решений, и я хочу найти решение для witch Сумма всех Xn минимальна.

Как я могу сделать это программно?

Для примера рассмотрим эту систему линейных уравнений:

x1 +    + x5 + x6 = 2 
    x2   + x5  = 1  
      x3   + x6 = 1 
       x4 + x5 + x6 = 1 

один из минимального решения я хочу получить это:

x3 = x4 = x5 = 0 
x1 = x2 = x6 = 1 

другой будет

x2 = x4 = x6 = 0 
    x1 = x3 = x5 = 1 

Но Я не хочу

x1 = 2 
x2 = x3 = x4 = 1 
x5 = x6 = 0 

, который также является решением этой системы, но не является минимальным по моим критериям: x1 + x2 + x3 + x4 + x5 + x6 = 5 (тогда как для 2 первых решений - только 3)

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

Answer 1

с переменные все неотрицательны, эта проблема по существу эквивалентна целочисленному программированию. Используйте встроенный программный решатель и сформулируйте как

minimize x1 + x2 + x3 + x4 + x5 + x6 
subject to 
x1    + x5 + x6 = 2 
    x2   + x5  = 1 
      x3   + x6 = 1 
       x4 + x5 + x6 = 1 
integers 
x1, x2, x3, x4, x5, x6 >= 0 

(точный синтаксис зависит от инструмента).