Переменная принимает отрицательное значение, хотя она должна быть неотрицательной - PullRequest
Новая
       9

Переменная принимает отрицательное значение, хотя она должна быть неотрицательной

0 голосов
/ 25 марта 2019

Я программирую проблему маршрутизации транспортных средств в Python с помощью PuLP. В нем есть весь мой код, но по какой-то причине я получаю отрицательное значение для одной из моих переменных решения, хотя я ограничил их все неотрицательными.

Мой код выглядит следующим образом (Traveltimes - это двумерный массив np, с временами перемещения между каждой парой клиентов (i, j), где c (i, j) = c (j, i) и c (i, я) = 0.):

Мой код: 

numVehicles = 2
numCustomers = 2


prob = LpProblem("DSP", LpMinimize)
var = [[[0 for k in range(numVehicles)] for j in range(numCustomers+1)] for i in range(numCustomers+1)]
for i in range(numCustomers+1):
    for j in range(numCustomers+1):
        for k in range(numVehicles):
            var[i][j][k] = LpVariable("x"+str(i)+","+str(j)+","+str(k), 0,1, cat='Binary')

# ADD OBJECTIVE
obj = ""
for i in range(numCustomers+1):
    for j in range(numCustomers+1):
        for k in range(numVehicles):
            obj += traveltimes[i][j]*var[i][j][k]
prob += obj

# ADD CONSTRAINTS

# All customers visited
for j in range(numCustomers+1):
    for k in range(numVehicles):
        nr = ""
        for i in range(numCustomers+1):
            nr += var[i][j][k] 
        prob += nr == 1

# Enter each customer exactly once
for i in range(numCustomers+1):
    nr = ""
    for k in range(numVehicles):
        for j in range(1, numCustomers+1):
            nr += var[i][j][k]
    prob += nr == 1

# Leave each customer exactly once
for j in range(numCustomers+1):
    nr = ""
    for k in range(numVehicles):
        for i in range(1, numCustomers+1):
            nr += var[i][j][k]
    prob += nr == 1

# Per vehicle only one customer can be visited as first
nrFirst = ""
for k in range(numVehicles):
    for j in range(numCustomers+1):
        nrFirst += var[0][j][k]
    prob += nrFirst <= 1

# Max num vehicles
nrOut = ""
for k in range(numVehicles):
    for j in range(numCustomers+1):
        nrOut += var[0][j][k]
prob += nrOut <= numVehicles

# Restrict x(0,j,k) to be nonpositive
for j in range(numCustomers+1):
    for k in range(numVehicles):
        prob += var[0][j][k] >= 0



print(prob)

# Solve LP
prob.solve()
for v in prob.variables(): 
    print(v.name, "=", v.varValue)
print("objective=", value(prob.objective))

Первый вывод - это напечатанная формулировка 

MINIMIZE
1.731*x0,1,0 + 1.731*x0,1,1 + 2.983*x0,2,0 + 2.983*x0,2,1 + 1.731*x1,0,0 + 1.731*x1,0,1 + 9.375*x1,2,0 + 9.375*x1,2,1 + 2.983*x2,0,0 + 2.983*x2,0,1 + 9.375*x2,1,0 + 9.375*x2,1,1 + 0.0
SUBJECT TO
_C1: x0,0,0 + x1,0,0 + x2,0,0 = 1

_C2: x0,0,1 + x1,0,1 + x2,0,1 = 1

_C3: x0,1,0 + x1,1,0 + x2,1,0 = 1

_C4: x0,1,1 + x1,1,1 + x2,1,1 = 1

_C5: x0,2,0 + x1,2,0 + x2,2,0 = 1

_C6: x0,2,1 + x1,2,1 + x2,2,1 = 1

_C7: x0,1,0 + x0,1,1 + x0,2,0 + x0,2,1 <= 1

_C8: x1,1,0 + x1,1,1 + x1,2,0 + x1,2,1 <= 1

_C9: x2,1,0 + x2,1,1 + x2,2,0 + x2,2,1 <= 1

_C10: x0,0,0 + x0,1,0 + x0,2,0 <= 1

_C11: x0,0,0 + x0,0,1 + x0,1,0 + x0,1,1 + x0,2,0 + x0,2,1 <= 1

VARIABLES
0 <= x0,0,0 <= 1 Integer
0 <= x0,0,1 <= 1 Integer
0 <= x0,1,0 <= 1 Integer
0 <= x0,1,1 <= 1 Integer
0 <= x0,2,0 <= 1 Integer
0 <= x0,2,1 <= 1 Integer
0 <= x1,0,0 <= 1 Integer
0 <= x1,0,1 <= 1 Integer
0 <= x1,1,0 <= 1 Integer
0 <= x1,1,1 <= 1 Integer
0 <= x1,2,0 <= 1 Integer
0 <= x1,2,1 <= 1 Integer
0 <= x2,0,0 <= 1 Integer
0 <= x2,0,1 <= 1 Integer
0 <= x2,1,0 <= 1 Integer
0 <= x2,1,1 <= 1 Integer
0 <= x2,2,0 <= 1 Integer
0 <= x2,2,1 <= 1 Integer

Хорошо видно, что все переменные ограничены целым числом от 0 до 1 (таким образом, двоичное). Однако по какой-то причине я получаю отрицательные значения для некоторых переменных, как показано ниже 

x0,0,0 = 0.0
x0,0,1 = -1.0
x0,1,0 = 0.0
x0,1,1 = 1.0
x0,2,0 = 0.0
x0,2,1 = 1.0
x1,0,0 = 1.0
x1,0,1 = 1.0
x1,1,0 = 1.0
x1,1,1 = 0.0
x1,2,0 = 0.0
x1,2,1 = 0.0
x2,0,0 = 0.0
x2,0,1 = 1.0
x2,1,0 = 0.0
x2,1,1 = 0.0
x2,2,0 = 1.0
x2,2,1 = 0.0
objective= 11.159

Очень жду любых предложений о том, как решить эту проблему, поскольку я явно не хочу отрицательных значений!

Ответы [ 2 ]

1 голос
/ 26 марта 2019

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

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

Чтобы проверить это, добавьте:

print (("Status:"), LpStatus[prob.status])

Сразу после того, как вы сделаете prob.solve().Я полагаю, вы найдете, что это невозможно.

0 голосов
/ 25 марта 2019 
prob += nr == 1

"+ =" предназначен для присваивания

"==" проверяет эквивалентность и входит в оператор "if" или "while".

Например: 

if prob + nr == 1: #execute what follows if prob + nr is equal to 1
...