线性规划导论和物理模型表示 线性规划导论 一个典型的线性规划问题 线性规划模型 三元素线性规划模型 物理表示 图解法和单纯形法 图解法 单纯形法求解简单线性规划模型的编程思想 求解案例示例 1：使用 scipy 求解示例 2：使用非线性项求解从整数规划到 0-1 规划整数规划模型 p>
线性规划介绍和线性规划的物理模型表示
在人们的生产实践中，经常会遇到如何利用现有资源安排生产以获得最大经济效益的问题。这类问题构成了运筹学的一个重要分支——数学编程，而线性规划（简称LP）是语言编程的一个重要分支，也是一种非常常用的优化模型。
随着计算机的发展，线性规划已被广泛应用于各个领域，成为物理建模中最经典、最常用的模型之一。线性规划模型可用于求解最大收益、最小成本、最短路径等优化问题。
一个典型的线性规划问题
某磨床厂生产A、B两种车床，每次销售后收入分别为4000元和3000元。生产A车床需要A、B机加工，每台加工时间分别为2小时和1小时；生产B车床需要A、B、C三台机床加工，每台加工时间为1小时。如果每晚可加工的机时数是机器10小时，机器8小时，C机7小时，那么工厂应该生产多少台车床A和B才能使总利润最大化？
问题分析
这个问题是一个非常典型的线性规划问题。首先，从问题中提取关键信息：
决定：生产多台A、B车床
优化目标：最大总收入
约束：生产车床的使用时间有限
将原告的三个元素写成物理表达式是典型的线性规划模型：
规划问题的分类
应用实例：旅行商问题、车辆路径问题、运输问题、最多泄漏问题、最大流量问题、中国邮差问题
线性规划模型的三个元素
线性规划模型主要包括三部分：决策变量、目标函数和约束
决策变量
决策变量是在一个问题中可以改变的量，例如生产多少商品，选择哪条路径等。线性规划的目标是找到最优决策变量。
线性规划中的决策变量包括实变量、整数变量、0-1变量等
目标函数
目标函数是对问题中的决策目标进行量化，通常分为最大化目标函数和最小化目标函数
在线性规划中，目标函数是一个包含决策变量的线性函数，比如
约束是指问题中的各种时间、空间、人、物等约束。
线性规划中的约束通常表示为一组包含决策变量的非方程，例如
据报道，决策变量的取值范围称为符号约束，如
线性规划模型的物理表示
线性规划模型可以写成：
to的缩写在哪里。
原告模型也可以写成矩阵如下：
对于具有决策变量和约束的线性规划模型，它是一个维列向量、一个维列向量和一个维矩阵。
线性规划模型的标准方法
线性规划的目标函数可以是最大化也可以是最小化，约束的符号可以大于等于，也可以小于等于。
因此，为了编程方便，通常统一最小化大于等于约束的目标函数
可以通过添加减号来更改最大化目标函数以最小化约束：
小于等于约束可以被两边除成大于等于约束：
等式约束可以改成小于等于约束和大于等于约束，但在编程中通常支持直接写方程约束，不能转换：
图解法和单纯形法图解法
图形方法可用于只有两个决策变量的更简单的线性规划问题。
考虑以下线性规划模型：
图像名称
从图中可以看出，当红线（即目标函数）经过五边形的顶点P（即代表两个约束的直线的交点）时，轴截距达到最大值。
即：此时目标函数的最大值为
单纯形法
对于决策变量较多的线性规划模型，图法不再适用。
单纯形法是G.B.提出的一种非常有效的求解方法。 1947 年，极大地促进了线性规划的应用，直到明天，一些线性规划求解器才会用到它。
从图解法的例子可以看出，约束所包围的区域是一个凸五边形。当决策变量少于两个时，约束所包围的区域为凸六面体，称为凸六面体。是可行域。这些面中的每一个（称为超平面）都代表一个约束。
图像名称
可以证明，线性规划的最优解一定在可行域的边界上
单纯形法的思想是在可行域的一个顶点处寻找一个初始可行解，并判断该解是否最优。如果不是，则迭代到下一个顶点进行重复确定。由于最优解的搜索范围从整个可行域缩小到可行域的有限个顶点，大大提高了算法的效率。
图像名称
求初始可行解的具体方法，判断解是否最优的条件，如何迭代这里不详述，有兴趣可以参考相关资料
据悉，求解线性规划有椭球法、算法、内点法等。
内点法求解效率更高，在决策变量和约束条件较多的情况下能取得较好的疗效。目前主流的线性规划求解器均采用内点法。
求解简单线性规划模型的编程思路
1.选择合适的决策变量
在解决实际问题时，将问题归纳为线性规划物理模型是非常重要的一步，但往往也很困难。模型是否正确构建直接影响解决方案。选择合适的决策变量是构建有效模型的关键之一。
2.将求解目标简化为找到目标函数的最大值/最小值
能够将要解决的问题简化为最大值问题是能够使用线性规划模型的关键。如果做不到这一点，未来的工作将毫无意义。
3.根据实际需求编写约束（正负、资源约束等）
线性规划的约束对于不同的问题有不同的方法。综上所述，约束分为三种：方程约束、非方程约束、符号约束
考虑以下线性规划问题
Step1：导出相关库
import numpy as np
from scipy import optimize as op
第二步：定义决策变量
# 给出变量取值范围
x1=(0,None)
x2=(0,None)
x3=(0,None)
Step3：将原问题转化为标准方式
注意：编程时，默认是最小化目标函数，所以这里改一下；第二个约束小于等于约束，这里是大于等于约束；
Step4：定义目标函数系数和约束系数
c=np.array([-2,-3,5]) # 目标函数系数,3x1列向量
A_ub=np.array([[-2,5,-1],[1,3,1]]) # 不等式约束系数A，2x3维矩阵
B_ub=np.array([-10,12]) # 等式约束系数b, 2x1维列向量
A_eq=np.array([[1,1,1]]) # 等式约束系数Aeq，3x1维列向量
B_eq=np.array([7]) # 等式约束系数beq，1x1数值
第五步：解决
res=op.linprog(c,A_ub,B_ub,A_eq,B_eq,bounds=(x1,x2,x3)) #调用函数进行求解
res
con: array([0.])
fun: -14.571428571428571
message: 'Optimization terminated successfully.'
nit: 3
slack: array([0. , 3.85714286])
status: 0
success: True
x: array([6.42857143, 0.57142857, 0. ])
此时目标函数达到最大值
求解案例示例 1：使用 scipy 求解
#导入相关库
import numpy as np
from scipy import optimize as op
#定义决策变量范围
x1=(0,None)
x2=(0,None)
x3=(0,None)
#定义目标函数系数
c=np.array([2,3,1])
#定义约束条件系数
A_ub=np.array([[-1,-4,-2],[-3,-2,0]])
B_ub=np.array([-8,-6])
#求解
res=op.linprog(c,A_ub,B_ub,bounds=(x1,x2,x3))
res
con: array([], dtype=float64)
fun: 7.0
message: 'Optimization terminated successfully.'
nit: 2
slack: array([0., 0.])
status: 0
success: True
x: array([0.8, 1.8, 0. ])
此时目标函数达到最小值
示例 2：非线性项的解决方案
由于非线性项的存在，例2中的函数解不能被继承。这里，目标函数和约束是按照自定义函数的方式编译的，函数在scipy中编译。用来解决的。
Step1：导出相关库
import numpy as np
from scipy.optimize import minimize
Step2：使用函数来表达目标和约束
# 定义目标函数
def objective(x):
return x[0] ** 2 + x[1]**2 + x[2]**2 +8
# 定义约束条件
def constraint1(x):
return x[0] ** 2 - x[1] + x[2]**2 # 不等约束
def constraint2(x):
return -(x[0] + x[1]**2 + x[2]**2-20) # 不等约束
def constraint3(x):
return -x[0] - x[1]**2 + 2 # 等式约束
def constraint4(x):
return x[1] + 2*x[2]**2 -3 # 等式约束
注意：每个函数的输入是一个维度列向量，表示列向量的第一个元素，即。
第三步：定义约束
con1 = {'type': 'ineq', 'fun': constraint1}
con2 = {'type': 'ineq', 'fun': constraint2}
con3 = {'type': 'eq', 'fun': constraint3}
con4 = {'type': 'eq', 'fun': constraint4}
# 4个约束条件
cons = ([con1, con2, con3,con4])
# 决策变量的符号约束
b = (0.0, None) #即决策变量的取值范围为大于等于0
bnds = (b, b ,b)
注意：每个约束都是一个字典，其中type代表约束类型：ineq小于等于，eq等于； fun表示约束函数表达式，即step2中的自定义函数。
第四步：解决
x0=np.array([0, 0, 0]) #定义初始值
solution = minimize(objective, x0, method='SLSQP',
bounds=bnds, constraints=cons)
注意：要最小化目标函数，默认小于等于约束中的约束。
Step5：复制求解结果
x = solution.x
print('目标值: ' + str(objective(x)))
print('最优解为')
print('x1 = ' + str(round(x[0],2)))
print('x2 = ' + str(round(x[1],2)))
print('x3 = ' + str(round(x[2],2)))
solution
目标值: 10.651091840572583
最优解为
x1 = 0.55
x2 = 1.2
x3 = 0.95
fun: 10.651091840572583
jac: array([1.10433471, 2.40651834, 1.89564812])
message: 'Optimization terminated successfully.'
nfev: 86
nit: 15
njev: 15
status: 0
success: True
x: array([0.55216734, 1.20325918, 0.94782404])
此时目标函数达到最小值z=10.65
从整数规划到0-1规划整数规划模型
当计划的变量（部分或全部）被限制为整数时，称为整数规划。如果在线性规划模型中，变量被限制为整数，则称为整数线性规划。
当决策变量都是整数时，称为纯整数规划；
当决策变量有的为整数，有的为实数时，称为混合整数规划；
通常用整数表示
在第1节线性规划图解法的例子中加入整数约束，可行域变成五边形内的一个整数点，如右图所示：
图像名称
可见将可行域做成离散点，这也使得整数规划问题比线性规划问题更难求解，但现实中很多决策变量只能取整数，所以混合整数规划问题也成为了研究最多的线性规划问题。
注意：整数规划的最优解不能通过简单地对实数的最优解进行四舍五入得到
整数规划的两种常见解法：分支定界算法和切割平面法
分支绑定法
Step1求解最优解，不考虑整数约束（通常不是整数）；
step2用解的整数上下界完善新的约束，将原来的整数规划问题变成两个问题（分支）；
step3分别求解两个子问题（不考虑整数约束），如果解正好是整数解，则结束；如果不是整数解，则继续分支；
Step4以初始目标函数值作为下界，子问题解中得到的任意整数解为上界（定界），子问题置顶以减小问题规模；
Step5 重复以上步骤线性规划软件，直到得到最优解
切面法
Step1求解最优解，不考虑整数约束（通常不是整数）；
step2通过解做一个切割平面（二维情况下的一条直线）以减少可行域；
step3在缩小的可行域中找到最优解（不考虑整数约束）
step4 重复步骤 2 和 3，直到最优解满足整数约束
0-1规划模型
当整数规划问题中的整数决策变量仅限于0或1时，称为0-1整数规划，简称0-1规划。
由于0-1规划问题的解空间比通常的整数规划问题要小，更容易求解，而且所有整数规划问题都可以转化为0-1规划问题，所以在构建一个混合整数规划模型求解在实际问题中，尽可能使用0-1决策变量进行建模。
例如：当有十个鞋厂进行决策时，可以使用十个0-1变量。值为0时表示不使用鞋厂，值为1时表示使用鞋厂。
0-1规划常用解法：分支定界算法、切割平面法、隐式枚举法
案例：投资收益及风险描述与分析
图像名称
图像名称
图像名称
图像名称
符号规则
图像名称
模型假设
细化和模型的简化
根据模型的假设和符号，我们可以写出模型的第一个优化目标是最小化总体风险，并且总体风险是所有投资中风险最高的
第二个优化目标是最大化净利润。根据题名的意思，交易费是分段函数（非线性函数），所以需要简化：因为题名给出的固定值相对于总投资额来说很小，可以忽略，所以交易费用简化为，所以目标函数为
对于多目标优化模型，一个常见的考虑是先确定一个目标，然后再优化另一个目标。
在这道题中，可以给出一个投资者可以承受的风险限额，使得最大投资风险下的损失率大于那个，即作为一个新的约束，多目标优化可以转化为转化为单目标优化，即：
使用scipy库解决
反映投资者对风险的偏好。从一开始，步长为 0.001 以执行循环搜索。使用的代码如下
#导入相关库
import numpy as np
import matplotlib.pyplot as plt
import scipy.optimize as op
#定义a的取值
a = 0
profit_list = [] #记录最大收益
a_list = [] #记录a的取值
while a<0.05:
#定义决策变量取值范围
x1=(0,None)
#定义目标函数系数
c=np.array([-0.05,-0.27,-0.19,-0.185,-0.185])
#定义不等式约束条件左边系数
A = np.hstack((np.zeros((4,1)),np.diag([0.025,0.015,0.055,0.026])))
#定义不等式约束条件右边系数
b=a*np.ones((4,1));
#定义等式约束条件左边系数
Aeq=np.array([[1,1.01,1.02,1.045,1.065]])
#定义等式约束条件右边系数
beq=np.array([1]);
#求解
res=op.linprog(c,A,b,Aeq,beq,bounds=(x1,x1,x1,x1,x1))
profit = -res.fun
profit_list.append(profit)
a_list.append(a)
a = a+0.001
#绘制风险偏好a与最大收益的曲线图
plt.figure(figsize=(10,7))
plt.plot(a_list,profit_list)
plt.xlabel('a');plt.ylabel('Profit')
Text(0, 0.5, 'Profit')
如上图所示
1.风险越大，收益越大；
2、投资越多元化，投资者承担的风险就越小线性规划软件，与题意一致。那就是：
冒险型投资者倾向于集中投资，而保守型投资者则尽可能分散投资。
3，附近有拐点，风险降低的一侧，收益下降较快。在这一点上，当风险大大降低时，收益会下降得很平缓，所以对于风险和利润没有特别偏好的投资者，应该选择曲线的拐点作为最优的投资组合，大致，整体利润为，对应的投资方案为：
风险，利润，
模型解决方案的其他想法
在前面的示例中，我们使用固定的风险水平来最大化利润，将多个目标转换为单个目标，但也可以考虑其他想法：
当总利润高于该水平时，寻找风险最低的投资方案，即：
2.为风险和利润分配一个权重和，成为投资偏好系数，即
