如何使用Python和Scipy解决线性规划问题？

vyu0f0g1  于 5个月前  发布在  Python
关注(0)|答案(2)|浏览(93)

我有一个由化学元素制成的一些材料，每公斤克有一个价格：

A: { cu: 0.02, mg: 0.3, nc: 0.005, price: 1000 }

字符串
这意味着1千克的材料A是由0.02克“铜”，0.3克“毫克”，0.005克“数控”，并具有1000$的价格。我有一些其他类似的材料：

A: { cu: 0.02, mg: 0.3, nc: 0.005, price: 1000 }  
 B: { cu: 0.033, mg: 0.2, nc: 0.00, price: 1500 }  
 C: { cu: 0.05, mg: 0.35, nc: 0.00, price: 1700 }

型
我想建立一个产品，让我们称之为Pr_1，有10千克的重量，由材料A，B和/或C制成，所以Pr_1有最低价格。Pr_1也有一些限制：

Pr_1: {minCu: 0.00, maxCu: 1.2, minMg: 1.2, maxMg: 1.9, minNc: 0, maxNc: 0}

型
这意味着10千克的Pr_1应该至少有0.00克，最多1.2克“铜”，也应该至少有1.2克，最多1.9克“毫克”，它不应该有任何“nc”。正如我提到的，Pr_1必须在所有可能的材料A，B和C的组合中具有最低价格。
因此，让我们将由材料A、B和C制成的Pr_1的权重分别表示为x_A、x_B和x_C。目标是使总成本最小化：
最小化：

1000*x_A + 1500*x_B + 1700*x_C

型
我们有三个不等式：

0.00 <= 0.02*x_A + 0.033*x_B + 0.05*x_C <= 1.2 // cu constraint  
1.2 <= 0.03*x_A + 0.2*x_B + 0.35*x_C <= 1.9 // mg constraint  
0.005*x_A + 0.00*x_B + 0.00*x_C = 0 // nc constraint

型
我不知道如何使用Scipy和Python来解决这个问题。

from scipy.optimize import linprog

# Coefficients of the objective function (costs)
c = [1000, 1500, 1700]

# Coefficients of the inequality constraints matrix
A = [
    [-0.02, -0.033, -0.05],   # Cu constraint
    [-0.3, -0.2, -0.35],      # Mg constraint
    [-0.005, 0, 0]            # Nc constraint
]

# Right-hand side of the inequality constraints
b = ???? # I don't know what this should be

# Bounds for each variable (x_A, x_B, x_C)
x_bounds = (0, None)

# Solve the linear programming problem
result = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, x_bounds, x_bounds], method='highs')

# Print the results
print("Optimal weights for Pr_1 from A, B, and C:", result.x)
print("Minimum cost of Pr_1:", result.fun)

型

scipy

2条答案

按热度按时间
cigdeys3

cigdeys31#

正如我在评论中所说，在你目前的限制下，这个问题是不可行的。
在相同的约束条件下，您可以生产9 kg。此外，我认为您应该更加小心和明确地使用您的单位，因此我使用Pandas演示了尺寸管理。最后，这产生了一个更清晰的输出。
另外，猜测一下，你的Nc意味着镍实际上是Ni。

import numpy as np
import pandas as pd
from scipy.optimize import milp, Bounds, LinearConstraint

materials = pd.DataFrame(
    data={'dollars_per_kg': (1_000, 1_500, 1_700)},
    index=pd.Index(name='material_name', data=('A', 'B', 'C')),
)
materials['dollars_per_g'] = 1e-3*materials['dollars_per_kg']

components = pd.DataFrame(
    data={
        'min_g': (0.0, 1.2, 0),
        'max_g': (1.2, 1.9, 0),
    },
    index=pd.Index(name='component_name', data=('Cu', 'Mg', 'Ni')),
)

material_components = pd.DataFrame(
    data={
        'g_per_kg': (
            0.0200, 0.30, 0.005,
            0.0033, 0.20, 0.000,
            0.0500, 0.35, 0.000,
        ),
    },
    index=pd.MultiIndex.from_product(
        iterables=(materials.index, components.index),
    ),
)
material_components['concentration'] = 1e-3 * material_components['g_per_kg']

mass_kg = 9  # 10 not feasible
mass_g = 1e3*mass_kg

'''
Minimize cost = (A, B, C mass g).(A, B, C dollars per g)
s.t.
A, B, C mass g >= 0
sum(A, B, C mass g) = mass_g
component min <= sum by component(A, B, C mass g) < component max
'''

mass_sum_constraint = LinearConstraint(
    A=np.ones(len(materials)),
    lb=mass_g, ub=mass_g,
)

component_constraint = LinearConstraint(
    A=material_components['concentration'].unstack('material_name'),
    lb=components['min_g'],
    ub=components['max_g'],
)

result = milp(
    c=materials['dollars_per_g'],
    bounds=Bounds(lb=0),
    constraints=(
        mass_sum_constraint,
        component_constraint,
    ),
)
if not result.success:
    raise ValueError(result.message)
print(result.message, end='\n\n')

materials['mass_g'] = result.x
materials['dollars'] = result.x * materials['dollars_per_g']
material_components['mass_g'] = material_components['concentration'] * materials['mass_g']
components['mass_g'] = material_components['mass_g'].groupby('component_name').sum()

print('Materials:')
print(materials, end='\n\n')
print('Components:')
print(components, end='\n\n')

个字符
要找到最大总质量，请更改您的目标：

import numpy as np
import pandas as pd
from scipy.optimize import milp, Bounds, LinearConstraint

materials = pd.DataFrame(
    data={'dollars_per_kg': (1_000, 1_500, 1_700)},
    index=pd.Index(name='material_name', data=('A', 'B', 'C')),
)
materials['dollars_per_g'] = 1e-3*materials['dollars_per_kg']

components = pd.DataFrame(
    data={
        'min_g': (0.0, 1.2, 0),
        'max_g': (1.2, 1.9, 0),
    },
    index=pd.Index(name='component_name', data=('Cu', 'Mg', 'Ni')),
)

material_components = pd.DataFrame(
    data={
        'g_per_kg': (
            0.0200, 0.30, 0.005,
            0.0033, 0.20, 0.000,
            0.0500, 0.35, 0.000,
        ),
    },
    index=pd.MultiIndex.from_product(
        iterables=(materials.index, components.index),
    ),
)
material_components['concentration'] = 1e-3 * material_components['g_per_kg']

mass_kg = 9  # 10 not feasible
mass_g = 1e3*mass_kg

'''
Minimize cost = (A, B, C mass g).(A, B, C dollars per g)
Or: maximize total mass
s.t.
A, B, C mass g >= 0
sum(A, B, C mass g) = mass_g
component min <= sum by component(A, B, C mass g) < component max
'''

mass_sum_constraint = LinearConstraint(
    A=np.ones(len(materials)),
    lb=mass_g, ub=mass_g,
)

component_constraint = LinearConstraint(
    A=material_components['concentration'].unstack('material_name'),
    lb=components['min_g'],
    ub=components['max_g'],
)

result = milp(
    # c=materials['dollars_per_g'],  # to minimize price
    c=-np.ones_like(materials['dollars_per_g']),  # to maximize total mass
    bounds=Bounds(lb=0),
    constraints=(
        # mass_sum_constraint,  # to ask for a fixed total mass
        component_constraint,
    ),
)
if not result.success:
    raise ValueError(result.message)
print(result.message, end='\n\n')

materials['mass_g'] = result.x
materials['dollars'] = result.x * materials['dollars_per_g']
material_components['mass_g'] = material_components['concentration'] * materials['mass_g']
components['mass_g'] = material_components['mass_g'].groupby('component_name').sum()

print('Materials:')
print(materials, end='\n\n')
print('Components:')
print(components, end='\n\n')
print('Material components:')
print(material_components)
Optimization terminated successfully. (HiGHS Status 7: Optimal)

Materials:
               dollars_per_kg  dollars_per_g  mass_g  dollars
material_name                                                
A                        1000            1.0     0.0      0.0
B                        1500            1.5  9500.0  14250.0
C                        1700            1.7     0.0      0.0

Components:
                min_g  max_g   mass_g
component_name                       
Cu                0.0    1.2  0.03135
Mg                1.2    1.9  1.90000
Ni                0.0    0.0  0.00000

Material components:
                              g_per_kg  concentration   mass_g
material_name component_name                                  
A             Cu                0.0200       0.000020  0.00000
              Mg                0.3000       0.000300  0.00000
              Ni                0.0050       0.000005  0.00000
B             Cu                0.0033       0.000003  0.03135
              Mg                0.2000       0.000200  1.90000
              Ni                0.0000       0.000000  0.00000
C             Cu                0.0500       0.000050  0.00000
              Mg                0.3500       0.000350  0.00000
              Ni                0.0000       0.000000  0.00000

的字符串

赞(0）分享  回复(0）举报  5个月前
8dtrkrch

8dtrkrch2#

在你的帖子中定义的系统可以写如下：

from scipy import optimize

c = [1000, 1500, 1700]

字符串
我们需要复制这两个约束，并将其放在A_ub @ x <= b_ub的形式中（参见documentation）：

A_ub = [
    [0.02,  0.033,  0.05],    # Normal inequality, stands for 0.02*x_A + 0.033*x_B + 0.05*x_C <= 1.2
    [0.3,   0.2,    0.35],
    [-0.02,  -0.033, -0.05],  # Reversed inequality, stands for 0.00 <= 0.02*x_A + 0.033*x_B + 0.05*x_C
    [-0.3,   -0.2,   -0.35],
]

b_ub = [1.2, 1.9, 0.0, -1.2]

型
你还需要一个严格的等式：

A_eq = [
    [0.005, 0., 0.]
]
b_eq = [0.]

型
我们把一切联系在一起：

result = optimize.linprog(
    c,
    A_ub=A_ub, b_ub=b_ub,
    A_eq=A_eq, b_eq=b_eq,
    bounds=[(0., None)] * 3,
    method='highs'
)
# x: array([-0.        ,  0.        ,  3.42857143])

型
注意0.005*x_A + 0.00*x_B + 0.00*x_C = 0约束力x_A = 0。
optimize.linprog的替代方案是optimize.milp：

c = [1000, 1500, 1700]

A = [
    [0.02,  0.033,  0.05],
    [0.3,   0.2,    0.35],
    [0.005, 0.,     0.],
]

b_lb = [0.0, 1.2, 0.0]
b_ub = [1.2, 1.9, 0.0]

optimize.milp(c=c, constraints=[optimize.LinearConstraint(A, b_lb, b_ub)])
# x: array([-0.        ,  0.        ,  3.42857143])

型
它还允许积分解约束：

optimize.milp(c=c, constraints=[optimize.LinearConstraint(A, b_lb, b_ub)], integrality=[1, 1, 1])
# x: array([0., 1., 3.])

型

赞(0）分享  回复(0）举报  5个月前
我来回答

相关问题

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com