Python线性规划函数optimize.linprog求解为整数

Question

Python线性规划函数optimize.linprog求出来的解，为什么部分都是整数啊？谢谢！

def makeA(alpha,K,X,Y,v):
    M = np.zeros((len(X)+len(Y),len(X)+len(Y)+len(X)*n+1))
    B = np.zeros((len(X)+len(Y))*2+len(X)*n)
    for i in range(len(X)):
        M[i][i] = -1
        for k in range(n):
            u = 0
            for j in range(len(X)+len(Y)):
                if j < len(X):
                    for l in range(n):
                        u += alpha[j]*v[j][l]*K[i*n+k][j*n+l]
                else:u -= alpha[j]*K[i*n+k][j+(n-1)*len(X)]
            M[i][len(X)+len(Y)+i*n+k] = (-1)*u
            # print(len(X)+len(Y)+i*n+k)
        M[i][-1] = -1
        B[len(X)+len(Y)+len(X)*n+i] = -1
    for i in range(len(X),len(X)+len(Y)):
        M[i][i] = -1
        M[i][-1] = 1
        u = 0
        for j in range(len(X)+len(Y)):
            if j < len(X):
                for l in range(n):u+= alpha[j]*v[j][l]*K[i+len(X)*(n-1)][j*n+l]
            else:u -= alpha[j]*K[i+len(X)*(n-1)][j+(n-1)*len(X)]
        B[len(X)+len(Y)+len(X)*n+i] = -1+(-1)*u
    A = np.append(-np.eye(len(X)+len(Y)+len(X)*n+1)[:-1,:],M,axis=0)
    return A,B

def makeAeq(X,Y):
    Aeq = np.zeros((len(X),len(X)+len(Y)+len(X)*n+1))
    for i in range(len(X)):
        for k in range(n): Aeq[i][len(X)+len(Y)+i*n+k] = 1
    return Aeq

A_ub,B_ub = makeA(alpha,K,MX_POS,MX_NEG_all,v)
Aeq = makeAeq(MX_POS,MX_NEG_all)
Beq = np.ones(len(MX_POS))
 res=op.linprog(c,A_ub,B_ub,Aeq,Beq)

Answer 1

此答案是由GPT4和本人亲自作答，如有帮助，还请采纳！
在使用 Python 的 scipy.optimize.linprog 函数进行线性规划求解时，通常得到的解是实数，而不是整数。你遇到的问题可能是由于线性规划算法本身并不保证整数解。因此，如果你发现某些解是整数，这可能只是偶然的结果，但这并不是该算法的目标或保证。

scipy.optimize.linprog 是用于求解线性规划问题的工具，它使用的是线性规划的单纯形法或内点法，这些方法的本质是处理连续变量的优化问题，并不能直接处理整数约束。因此，如果需要找到整数解，通常需要使用整数规划方法。以下是一些关于你代码的说明、改进建议以及解决方案。

代码分析

你的代码使用了 scipy.optimize.linprog 函数来求解线性规划问题。具体来说，你通过 makeA 和 makeAeq 函数构造了不等式约束矩阵 A_ub 和 B_ub 以及等式约束矩阵 Aeq 和 Beq，然后调用了 linprog 函数来求解线性规划问题。

import numpy as np
from scipy.optimize import linprog

def makeA(alpha, K, X, Y, v):
    # 省略具体实现，参考你的代码
    pass

def makeAeq(X, Y):
    # 省略具体实现，参考你的代码
    pass

A_ub, B_ub = makeA(alpha, K, MX_POS, MX_NEG_all, v)
Aeq = makeAeq(MX_POS, MX_NEG_all)
Beq = np.ones(len(MX_POS))

res = linprog(c, A_ub, B_ub, Aeq, Beq)

为什么得到的解可能是整数？

1. 问题的特殊性：
   在某些情况下，线性规划问题的解可能自然是整数。尤其是当你的约束和目标函数特别设计得使得整数解满足时。例如，当所有变量的解均处于整数点附近或约束条件限制了变量在整数点处的解时。

2. 数据的特性：
   如果你的数据和约束条件具有特定的结构，可能会导致某些线性规划问题的解恰好是整数。例如，特定的系数和约束可能会限制解在整数值上。

3. 浮点数精度：
   数值计算中的浮点数精度问题可能导致某些实数解看起来像整数。如果计算过程中使用的是有限精度，可能会导致看似整数的结果。

解决方案

为了确保得到整数解，你应该使用整数线性规划（ILP）或混合整数线性规划（MILP）的方法。scipy.optimize.linprog 不支持直接处理整数约束，所以你需要使用专门的库如 PuLP、Google OR-Tools 或 Gurobi 来处理这些问题。以下是使用 PuLP 库的示例代码：

import pulp

# 构建线性规划问题
prob = pulp.LpProblem("Integer_Problem", pulp.LpMinimize)

# 定义变量
x = pulp.LpVariable("x", lowBound=0, cat='Integer')
y = pulp.LpVariable("y", lowBound=0, cat='Integer')

# 添加目标函数
prob += 2 * x + 3 * y  # 这是一个例子，使用你实际的目标函数

# 添加约束
prob += x + y >= 5  # 添加你的实际约束
prob += x - y <= 2  # 添加你的实际约束

# 求解
prob.solve()

# 打印结果
print(f"Status: {pulp.LpStatus[prob.status]}")
print(f"x = {pulp.value(x)}")
print(f"y = {pulp.value(y)}")

具体步骤

1. 定义问题：使用 pulp.LpProblem 定义一个线性规划问题。设置目标函数和约束。

2. 添加变量：使用 pulp.LpVariable 定义整数变量，并设置相应的约束。

3. 定义目标函数：使用 prob += 添加目标函数。

4. 添加约束：使用 prob += 添加约束条件。

5. 求解问题：使用 prob.solve() 求解问题。

6. 获取结果：打印或使用求解后的结果。

总结

你的线性规划模型可能会产生整数解，但这不是 scipy.optimize.linprog 的特性或保证。如果需要整数解，建议使用适合整数线性规划的库，如 PuLP、Google OR-Tools 或 Gurobi。这些工具提供了处理整数约束的能力，可以确保求解整数解。