爱与彼岸财经分析团队编制
目前已成功地应用于求解
分枝定界法求解整数规划（最大化）问题的步骤为：
第0步
第1步
第2步
$$ Max\ z=40x_1+90x_2 \\ $$
$$ s.t.\ \ \left\{ \begin{aligned} 9x_1+7x_2 \leq 56 \\ 7x_1+20x_2 \leq \ \ 70 \\ x_1,x_2 \geq \ \ 0 \\ \end{aligned} \right. $$
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
print("最优值",v.name,":",v.varValue,"单位")
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
print("最优值",v.name,":",v.varValue,"单位")
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4
prob += 0 * x1 + x2 <= 2
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
print("最优值",v.name,":",v.varValue,"单位")
$$ Max\ z=\sum_{i=1}^7 {c_i x_i} \\ $$
$$ s.t.\ \ \left\{ \begin{aligned} \sum_{i=1}^7 {c_i x_i} \leq B \\ x_1+x_2+x_3 \leq 2 \\ x_4+x_4 \geq 1 \\ x_6+x_7 \geq 1 \\ x_i = 0\ 或\ 1 \\ \end{aligned} \right. $$
$$ s.t.\ \ \left\{ \begin{aligned} 5x_1+4x_2 \leq 24 + yM \\ 7x_1+3x_2 \leq 45 + (1-y)M \\ y = 0\ 或\ 1 \\ 其中M是充分大的数 \end{aligned} \right. $$
$$ s.t.\ \ \left\{ \begin{aligned} 500y \leq x_1 \leq 800y \\ y = 0\ 或\ 1 \\ 其中M是充分大的数 \end{aligned} \right. $$
如果有 $m$ 个互相排斥的约束条件：
$a_{i1}x_1+...+a_{in}x_n \leq b_i \ \ \ i=1,2,...,m$
为了保证这 $m$ 个约束条件只有一个起作用，我们引入 $m$ 个$0-1$ 变量$\ \ y_i\ (i=1,2,...,m)$ 和一个充分大的常数 $M$
下面这一组 $m+1$ 个约束条件
$a_{i1}x_1+...+a_{in}x_n \leq b_i + y_i M\ \ \ i=1,2,...,m \ \ \ （1）$
$y_i+...+y_m = m-1 \ \ \ \ \ \ （2）$
就合于上述的要求。
这是因为，由于（2）， $m$ 个$y_i$ 中只有一个能取 0 值，设 $y_{i^*} = 0$ ，代入（1），就只有$i=i^*$ 的约束条件起作用
而别的式子都是多余的。
但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。
某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令:
为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为: $$ P_j = \ \ \left\{ \begin{aligned} k_j + c_jx_j,\ 当 x_j > 0 \\ 0\ 当x_j = 0 \\ \end{aligned} \ \ \ \ j = 1,2,3. \right. $$
引入 $0-1$ 变量
$$ y_j = \ \ \left\{ \begin{aligned} 1，\ \ \ \ \ \ j\ is\ in\ use(x_j > 0). \\ 0，j\ is\ not\ in\ use(x_j = 0). \\ \end{aligned} \right. $$
模型建立
设原油 $A$ 用于生产甲、乙两种汽油的数量分别为 $x_{11}$ 和 $x_{12}$，原油 $B$ 用于生产甲、乙两种汽油的数量分别为$x_{21}$ 和 $x_{22}$ ，则总的收入为 $4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})$（千元）。
于是目标函数（利润）为 $$ max\ z=4.8(x_{11}+x_{21}) + 5.6(x_{12}+x_{22})-c(x) $$
约束条件包括加工两种汽油用的原油 $A$ 、原油 $B$ 库存量的限制，原油 $A$ 购买量的限制，以及两种汽油含原油 $A$ 的比例限制，它们表示为
$$ s.t. = \ \ \left\{ \begin{aligned} x_{11} + x_{12} \leq 500 + x \\ x_{21} + x_{22} \leq 1000 \\ x \leq 1500 \\ \dfrac{x_{11}}{x_{11}+x_{21}} \geq 0.5 \\ \dfrac{x_{12}}{x_{12}+x_{22}} \geq 0.6 \\ x_{11},\ x_{12},\ x_{21},\ x_{22},\ x \geq 0 \\ \end{aligned} \right. $$
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4 # 通过分枝、定界、剪枝添加的约束条件
prob += 0 * x1 + x2 <= 2 # 通过分枝、定界、剪枝添加的约束条件
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
print("最优值",v.name,":",v.varValue,"单位")
# -*- coding: utf-8 -*-
import pulp as pulp
def solve_ilp(objective , constraints):
prob = pulp.LpProblem('LP1' , pulp.LpMaximize)
prob += objective
for cons in constraints:
prob += cons
print(prob)
status = prob.solve()
if status != 1:
return None
else:
return [v.varValue.real for v in prob.variables()]
V_NUM = 2
#变量，直接设置下限
variables = [pulp.LpVariable('X%d'%i , lowBound = 0 , cat = pulp.LpInteger) for i in range(0 , V_NUM)]
#目标函数
c = [40 , 90]
objective = sum([c[i]*variables[i] for i in range(0 , V_NUM)])
#约束条件
constraints = []
a1 = [9 , 7]
constraints.append(sum([a1[i]*variables[i] for i in range(0 , V_NUM)]) <= 56)
a2 = [7 , 20]
constraints.append(sum([a2[i]*variables[i] for i in range(0 , V_NUM)]) <= 70)
#print(constraints)
res = solve_ilp(objective , constraints)
print(res)
爱与彼岸财经分析团队编制