python中整数编程到二进制的转换

Question

请参阅上图以了解我对问题的解释。在

from scipy.optimize import linprog

a = [-800,-1200,-800]

b = [[200,100,400],[200,200,400],[200,300,200]]

c = [600,600,600]

result = linprog(a,b,c)
print(result)

我写的代码在上面。我感兴趣的输出中的数字是fun : -2400.0<；--这是当前的结果。但这不是我想要的。在

这是问题和我要找的。在

图中有两张桌子。RHS上的表是整数部分，LHS表是二进制部分。我想要的答案是fun : -2800.0，它是LHS表中第4列的一部分。在

让我告诉你我是如何决定这个答案的。 首先，正如你所看到的，所有可能的0和1的组合都是为LHS表中的所有三个赋值编写的。我必须从第4列LHS中找到满足RHS表中所有条件的最佳最高数。例如：从顶部开始；数字取自LHS和RHS表格。1表示选择该赋值，0表示不选择。所以第一行是11，意思是选择所有的作业。现在，我们把第0天、第1天和第2天的所有数字加起来，我们可以看到它们都在600以上。加200*1+100*1+400*1=700，大于600。第一天和第二天也是一样。所以，2801不是我们想要的号码。接下来，我们选择2800，它确实满足每个加法数的总条件<；=600，因为assignment1是0，所以200*0+100*1+400*1=500，小于600，剩下的两天也是一样。在

我只是不明白如何将每一件事都放到python中并得到-2800而不是-2400的结果。在

linprog必须有一个简单的方法。在

我得到LHS表第4个数字的方法是使用RHS表中绿色突出显示的数字，这些数字也在LHS表的最后一行。 我做了=（（B5+$B$13）+（C5*$C$13）+（D5*$D$13））得到2801，以此类推。在

如果不使用linprog，我想不出比以下代码更好的了：

^{pr2}$

Answer 1

首先：您的问题措辞非常糟糕（而且您对linprog的使用并不常见；Variable A通常是2d格式的）。在

通常我对解决这类问题犹豫不决，但我想我现在有问题了。在

你的问题/公式有什么大问题？在

• 你没有告诉我们，左表第四列是从哪里来的！这些值是固定的（独立于剩余的表），还是以某种方式相互关联？在
• 在检查了这些值之后，我了解到，这些值本身（我们称之为z）是决策变量的线性函数，形式如下：
  • z = 1*x0 + 1200*x1 + 800*x2 + 800
  • 你的问题在这里不重要！

那么如何处理这个问题呢？在

正确方法：忽略800的恒定偏移量&稍后更正物镜

下面的代码（我以一种常见的方式使用变量名）忽略了偏移量（常量偏移量不会改变与决策变量相关的结果）。因此，您需要稍后将偏移量添加到您获得的解中/或忽略返回的目标，并根据上面的公式自行计算！在

from scipy.optimize import linprog
import numpy as np

a_ub = [[200, 100, 400], [200, 200, 300], [400, 400, 200]]
b_ub = [600, 600, 600]
c = [-1, -1200, -800]

result = linprog(c,a_ub,b_ub, bounds=(0,1))
print('*** result: (negated, offset of 800 missing) ***\n')
print(result)

结果：

^{pr2}$

在否定目标之后，只需加上偏移量，就可以得到2800的期望结果！在

愚蠢的方法：添加一些固定变量来描述偏移

""" Alternative formulation
    We introduce a 4th variable W, which is set to 1 and introduce the offset
    into the objective
"""
from scipy.optimize import linprog
import numpy as np

a_ub = [[200, 100, 400, 0], [200, 200, 300, 0], [400, 400, 200, 0]]  # no upper bound for W 
b_ub = [600, 600, 600]
c = [-1, -1200, -800, -800]  # W*800 added to objective
a_eq = [[0, 0, 0, 1]]  # W=1 fixed
b_eq = [1]             # ""  ""
result = linprog(c,a_ub,b_ub, a_eq, b_eq, bounds=(0,1))
print('*** alternative result (negated, including offset): ***\n')
print(result)

结果：

*** alternative result (negated, including offset): ***

     fun: -2800.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([ 100.,  100.,    0.,    1.,    0.,    0.,    0.])
  status: 0
 success: True
       x: array([ 0.,  1.,  1.,  1.])

但这种方法总体上能起作用吗？在

线性规划方法一般不起作用。正如ayhan在评论中提到的，一个幺模矩阵意味着，LP解算器保证了一个最优整数解。但是，如果没有关于数据的一些规则，这种单模块性的特性通常不会给出！在

请看下面的示例代码，该代码生成一个随机实例，并比较LP解算器和MIP解算器的结果。第一个随机实例失败，因为LP解是连续的！在

当然，您可以坚持使用MIP解算器，但是：

• MIP问题通常很难解决
• numpy/scipy中没有MIP解算器

代码：

from scipy.optimize import linprog
import numpy as np
from cylp.cy import CyCbcModel, CyClpSimplex
from cylp.py.modeling.CyLPModel import CyLPModel, CyLPArray

np.random.seed(1)

def solve_lp(a_ub, b_ub, c):
    result = linprog(c,a_ub,b_ub, bounds=(0,1))
    print(result)
    return result.fun

def solve_mip(a_ub, b_ub, c):
    a_ub, b_ub, c = np.matrix(a_ub), np.array(b_ub), np.array(c)
    n = b_ub.shape[0]

    model = CyLPModel()
    x = model.addVariable('x', n, isInt=True)

    model += a_ub*x <= b_ub
    for i in range(n):
        model += 0 <= x[i] <= 1

    c = CyLPArray(c)
    model.objective = c*x
    s = CyClpSimplex(model)
    cbcModel = s.getCbcModel()
    cbcModel.branchAndBound()
    print('sol: ', cbcModel.primalVariableSolution['x'])
    print('obj: ', cbcModel.objectiveValue)
    return cbcModel.objectiveValue

def solve_random_until_unequal():
    while True:
        a_ub = np.random.randint(0, 1000, size=(3,3))
        b_ub = np.random.randint(0, 1000, size=3)
        c = [-1, -1200, -800]

        lp_obj = solve_lp(a_ub, b_ub, c)
        mip_obj = solve_mip(a_ub, b_ub, c)
        print('A_ub: ', a_ub)
        print('b_ub: ', b_ub)
        assert np.isclose(lp_obj, mip_obj)

solve_random_until_unequal()

输出：

fun: -225.29335071707953
message: 'Optimization terminated successfully.'
nit: 1
slack: array([  9.15880052e+02,   0.00000000e+00,   7.90482399e+00,
    1.00000000e+00,   8.12255541e-01,   1.00000000e+00])
status: 0
success: True
  x: array([ 0.        ,  0.18774446,  0.        ])
Clp0000I Optimal - objective value 0
Clp0000I Optimal - objective value 0
Node 0 depth 0 unsatisfied 0 sum 0 obj 0 guess 0 branching on -1
Clp0000I Optimal - objective value 0
Cbc0004I Integer solution of -0 found after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective -0, took 0 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Clp0000I Optimal - objective value 0
Clp0000I Optimal - objective value 0
('sol: ', array([ 0.,  0.,  0.]))
('obj: ', -0.0)
('A_ub: ', array([[ 37, 235, 908],
  [ 72, 767, 905],
  [715, 645, 847]]))
('b_ub: ', array([960, 144, 129]))
Traceback (most recent call last):
File "so_linprog_v3.py", line 45, in <module>
solve_random_until_unequal()
File "so_linprog_v3.py", line 43, in solve_random_until_unequal
assert np.isclose(lp_obj, mip_obj)
AssertionError