我正在尝试解决线性规划问题。以下是问题的具体情况：
我有一个网络流问题已转换为线性规划问题。因此，所有流量约束，例如容量、流量守恒等，都必须强制执行。我的目标是最小化成本。
决策变量 - 我通过定义字典并在这 128 个位置中的每个位置添加决策变量来构建两个 8x8 矩阵。
约束 - 总共有 24 个约束，即：
1) 流程从源头开始。两个 8x8 矩阵都有 2 个约束。
2) 水流在水槽处结束。两个 8x8 矩阵都有 2 个约束。
3) 流量守恒有 12 个约束，两个矩阵各有 8 个。
4) 有 2 个约束来遵守容量约束，每个矩阵 1 个。
5）有6个约束以避免重复
所有变量都必须是二进制的。
目标 - 8x8 矩阵中的某些变量的总和需要最小化。
同样，所有变量都必须是二进制的。
我已经能够在 Google ORTOOLS 中编写解决方案，并且解决方案收敛并显示最小值。但是，当我查看变量时，有些变量具有非二进制值。另外，该解决方案是错误的（我有一个在 Excel 中运行的现有解决方案，它是正确的且不同）。
如果有人能指出我正确的方向，我将不胜感激。以下是用 Python 36 编写的代码。
from ortools.linear_solver import pywraplp
import numpy as np
def configure_constraints(cfg, solver, variable_list):
print(cfg)
dest_convs = cfg['dest_convs']
msize = cfg['lookback_win'] + 1 + 1
rem_capacity = cfg['rem_caps']
# Constraint 1 - Flow starts at the source
for i in range(dest_convs):
# print([(i, 0, c) for c in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,0,c)] for c in range(1, msize)]) == 1)
# Constraint 2 - Flow ends at the sink
for i in range(dest_convs):
# print([(i, r, msize - 1) for r in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,r,msize - 1)] for r in range(1, msize)]) == 1)
# Constraint 3 - Flow Conservation
for i in range(dest_convs):
for r in range(msize - 1):
if r+1 == msize - 1:
continue
solver.Add(solver.Sum([variable_list[(i,rind, r+1)] for rind in range(r + 1)]) - solver.Sum([variable_list[(i,r+1, cind + 1)] for cind in range(r+1, msize - 1)]) == 0)
#
# # Constraint 4 - Capacity Constraint
for i in range(dest_convs):
solver.Add(solver.Sum([variable_list[(i, r, c)] for r in range(1, msize-1) for c in range(r+1, msize - 1)]) <= rem_capacity[i] - 1)
#
# # Constraint 5 - 1-vehicle, 1-conveyor
dest_conv_list = []
for i in range(dest_convs):
dest_conv_list.append([])
for r in range(1, msize - 1):
dest_conv_list[i].append(sum([variable_list[(i,r,c)] for c in range(r+1, msize)]))
for items in zip(*dest_conv_list):
solver.Add(solver.Sum(items) == 1)
def configure_objective(solver, variable_list, cost_vars):
# Objective
solver.Minimize(solver.Sum([variable_list[items] for items in zip(*np.where(cost_vars))]))
def solve(solver):
result_status = solver.Solve()
return result_status
def configure_variables(cfg, solver):
# identify variables for the objective function
# print(cfg)
nvehs = cfg['vehicles']
dest_convs = cfg['dest_convs']
color_vec = cfg['color_vec']
cur_cars = cfg['cur_cars']
msize = cfg['lookback_win'] + 1 + 1
# objective_mat = np.zeros((msize, msize), dtype="int32")
mat = [[[0] * msize for i in range(msize)] for j in range(dest_convs)]
# source to vehicles
for i in range(dest_convs):
for j in range(nvehs):
# print(color_vec[j], cur_cars[i])
if color_vec[j] != cur_cars[i]:
mat[i][0][j+1] = 1
for h in range(dest_convs):
for i in range(0, nvehs):
for j in range(i+1, nvehs):
# print(i+1,j+1)
# print(color_vec[i+1], color_vec[j])
if color_vec[i] != color_vec[j]:
mat[h][i+1][j + 1] = 1
cost_vars = np.array(mat).reshape(dest_convs, msize, msize)
print(np.array(mat).reshape(dest_convs,msize,msize))
dvars = {}
for i in range(dest_convs):
for j in range(msize):
for k in range(msize):
dvars[i, j, k] = solver.BoolVar('x[%i,%i, %i]' % (i, j, k))
return dvars, cost_vars
def main(cfg, what):
solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
dvars_list, cost_vars = configure_variables(cfg, solver)
configure_constraints(cfg, solver, dvars_list)
configure_objective(solver, dvars_list, cost_vars)
result_status = solve(solver)
print('Number of Variables:', solver.NumVariables())
print('Number of Constraints:', solver.NumConstraints())
# print('Constraints:', solver.)
if result_status == solver.OPTIMAL:
print('Solution Found.')
# The problem has an optimal solution.
print(('Problem solved in %f milliseconds' % solver.wall_time()))
# The objective value of the solution.
print(('Optimal objective value = %f' % solver.Objective().Value()))
var_sum = 0
for variable in dvars_list:
print(('%s = %f' % (dvars_list[variable].name(), dvars_list[variable].solution_value())))
var_sum += dvars_list[variable].solution_value()
print(('Variable sum = %f' % var_sum))
# The value of each variable in the solution.
elif result_status == solver.INFEASIBLE:
print('No solution found.')
elif result_status == solver.POSSIBLE_OVERFLOW:
print('Some inputs are too large and may cause an integer overflow.')
if __name__ == '__main__':
cfg = {'vehicles': 6,
'dest_convs': 2,
'cur_cars':['B', 'R'],
'rem_caps': [3,3],
'lookback_win':6,
'color_vec': ['W', 'W', 'B', 'B', 'R', 'B'],
}
main(cfg, 'cost')
