Блог

У меня есть матрица E. В каждой строке я должен выбрать ровно одну запись. То же самое относится и к колонкам. Записи должны быть выбраны таким образом, чтобы их накопленные значения были как можно ниже. Я написал фрагмент кода, используя библиотеку Python-MIP, которая должна позаботиться об этом.

Однако, похоже, что код находит только решение, которое удовлетворяет всем условиям (написано после m =), но не оптимизирует. Что я здесь делаю не так?

 from mip import Model, xsum, minimize, BINARY, INTEGER

E_ =    [
            [0, 4, 3, 1],
            [4, 0, 6, 3],
            [5, 8, 0, 10],
            [10, 7, 12, 0]
        ]

N = len(E_)

m = Model("model")

R = [[m.add_var(var_type=INTEGER) for j in range(N)] for i in range(N)]
E = [[m.add_var(var_type=INTEGER) for j in range(N)] for i in range(N)]

m.objective = minimize(xsum(((E[i][j] * R[i][j]) for i in range(N)) for j in range(N)))

for i in range(N):
    for j in range(N):
        m  = E[i][j] == int(E_[i][j])

for i in range(N):
    m  = xsum(R[i][j] for j in range(N)) == 1

for j in range(N):
    m  = xsum(R[i][j] for i in range(N)) == 1

for i in range(N):
    m  = R[i][i] == 0
    
m.optimize()
 

Полученная матрица R выглядит так, как показано ниже, в результате чего в общей сложности получается 30:

 0 1 0 0 
1 0 0 0 
0 0 0 1 
0 0 1 0
 

Однако следующая матрица (я понял это вручную) дает в общей сложности 18. Таким образом, очевидно, что программа не оптимизируется:

 0 0 1 0 
0 0 0 1 
1 0 0 1 
0 1 0 0