浅谈Python数学建模之线性规划

一、求解方法、算法和编程方案

线性规划 (Linear Programming,LP) 是很多数模培训讲的第一个算法,算法很简单,思想很深刻。

线性规划问题是中学数学的内容,鸡兔同笼就是一个线性规划问题。数学规划的题目在高考中也经常出现,有直接给出线性约束条件求线性目标函数极值,有间接给出约束条件求线性目标函数极值,还有已知约束条件求非线性目标函数极值问题。

因此,线性规划在数学建模各类问题和算法中确实是比较简单的问题。下面我们通过这个比较简单、也比较熟悉的问题,分析一下数学模型问题的方法、算法和学习方案。探讨这些容易混淆的概念,也便于大家理解本系列教程的初衷和特色。

1.1、线性规划问题的求解方法

解决线性规划问题有很多数学方法,例如:

  • 图解法, 用几何作图的方法并求出其最优解,中学就讲过这种方法,在经济学研究中十分常用;
  • 矩阵法, 引进松弛变量将线性规划问题转换成增广矩阵形式后逐次求解, 是单纯性法之前的典型方法;
  • 单纯性法, 利用多面体在可行域内逐步构造新的顶点来不断逼近最优解,是线性规划研究的里程碑,至今仍然是最重要的方法之一;
  • 内点法,通过选取可行域内部点沿下降方向不断迭代来达到最优解,是目前理论上最好的线性规划问题求解方法;
  • 启发式方法,依靠经验准则不断迭代改进来搜索最优解 ,如贪心法、模拟退火、遗传算法、神经网络。

虽然不同的求解方法都是面对线性规划问题,也就必然会殊途同归,但它们在思想上就存在着本质区别,在求解方法和步骤上也就完全不同。

不夸张地说,对于很多小白,学没学过单纯性法,对于学习启发式方法可能完全没有区别。

这意味着什么呢?这就是说,对于非数学专业的同学,对于学习数学建模的同学,针对每一类问题,完全没必要学习各种解决方法。即便是数学专业的同学,也不可能在数模学习期间把各种方法都学会。

对于小白,本文推荐选择较为通用、相对简单(思路简单、程序简单)的方法来进行学习,没必要贪多求新。

1.2、线性规划的最快算法

算法,跟方法有什么不同呢?

算法的定义是“解题方案的准确而完整的描述”,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。

我对“方法”的理解是思想方法,是求解问题总体框架,而“算法”是具体和明确的实现步骤,在计算机编程中相当于详细的流程图。

在每一种方法的基本思想和方案提出后,往往都会有很多变形、改进和发展的算法。极少的改进算法具有实质贡献而成为主流的经典算法,即便如此往往也只是性能、效率上的提升,对于求解数模竞赛中的问题基本没有影响。

而绝大多数改进算法只是针对某些特殊情况、特殊问题(自称)有效,常用于大量的灌水论文。对于数学建模来说,学习基本算法或者目前的经典算法就足够了,不需要听信改进算法中自称的优点,那都是莆田系的广告。

有一种例外情况,就是一些算法是有适用范围和限制条件的。举个例子,内点法的基本算法不能处理等式约束,最短路径问题中 Dijkstar算法不能处理负权边。这种情况下如果选错算法,问题是无法求解的。所以对我们来说,搞清楚算法的适用范围,比理解算法本身更重要。

回到本节的标题,对于线性规划问题,什么算法是最快的呢?答案是:猜。不是让你猜,而是说求解线性规划问题,猜起来比较快。不是开玩笑,我是认真的。

佐治亚理工学院彭泱教授在 2021年计算机理论顶会 SODA2021 获得最佳论文(Best paper award at ACM-SIAM symposium on discrete algorithms 2021),正是研究线性规划问题的求解——“Solving sparse linear systems faster than matrix multiplication”,所用的全新思路是:猜,反复猜,迭代猜。

当然,猜起来比较快只是在某些特殊条件下才有效的,至于在什么条件下猜,怎么猜,这不是我们所要关心,所能理解的问题了。只是以此说明,简单的问题也有复杂的情况,每个问题都有很多求解的思路、方法和算法。

1.3、选择适合自己的编程方案

编程方案是我杜撰的术语。我所要表达意思是,在选择了求解方法和算法以后,是自己按照算法步骤一步步编程实现,或者找到例程调试使用,还是调用第三方工具包/库函数来完成呢?

首先,对于学习数学建模、参加数模竞赛,不建议自己按照算法步骤去编程。我们在《01.新手必读》中讨论过这个问题,对于数学小白兼计算机小白,这样做既不可行也没必要;即使你愿意挑战自我去试试,那其实已经是走在学习另一门计算机或算法课程的路上了。

其次,要不要找到例程自己调试、使用?很多数模培训就是这么说,这么做的,而且把这些收集的例程当作核心机密吸引同学。我不反对这样做,这种学习方法对于理解算法、提高编程能力很有帮助;但是并不推荐这样做,原因是:

(1)我认为学习数学建模、参加数模竞赛,重点应该放在识别问题、分析问题、解决问题,能使用算法和编程就足够了;

(2)第三方库与例程没有本质区别,第三方库就是经典的、规范的、标准化的例程,既然选择例程为什么不选择优秀的例程——第三方库呢?

(3)大部分例程都存在很多问题,即使调试通过仍然有很多坑,而且新手难以识别。

所以我是明确推荐优选直接使用第三方库来解决问题,这也是 Python 语言“不要重复造轮子”的思想。

进一步地,很多工具包/库函数都能实现常用的算法,应该如何选择呢?

如果你对某个工具包已经很熟悉,又能实现所要的算法,这当然是理想的选择。如果你是小白,就跟着我走吧。

本系列选择第三方工具包的原则是:

(1)优选常用的工具包;

(2)优选通用功能的工具包和函数(例如,最好既能实现线性规划,又能实现整数规划、非线性规划);

(3)优选安装简单、使用简单、配置灵活的工具包;

(4)优选兼模型检验、图形绘制的工具包。

二、PuLP库求解线性规划问题

2.1、线性规划问题的描述

线性规划是研究线性等式或不等式约束条件下求解线性目标函数的极值问题,常用于解决资源分配、生产调度和混合问题。

一般线性规划问题的标准形式为:

满足所有约束条件的解,称为线性规划问题的可行解;所有可行解构成的集合,称为可行域。

使目标函数达到最小值的解,称为最优解。

线性规划问题的建模和求解,通常按照以下步骤进行:

  • 问题定义,确定决策变量、目标函数和约束条件;
  • 模型构建,由问题描述建立数学方程,并转化为标准形式的数学模型;
  • 模型求解,用标准模型的优化算法对模型求解,得到优化结果。

很多 Python 的第三方包,都提供求解线性规划问题的算法,有的工具包还提供整数规划、非线性规划的算法。例如:

  • Scipy 库提供了解简单线性或非线性规划问题,但是不能求解如背包问题的0-1规划问题,或整数规划问题,混合整数规划问题。
  • PuLP 可以求解线性规划、整数规划、0-1规划、混合整数规划问题,提供多种针对不同类型问题的求解器。
  • Cvxpy 是一种凸优化工具包,可以求解线性规划、整数规划、0-1规划、混合整数规划、二次规划和几何规划问题。

此外,SKlearn、DOcplex、Pymprog 等很多第三方工具包也都能求解线性规划问题。

2.2、PuLP 求解线性规划问题的步骤

例题 1:

下面以该题为例讲解 PuLP 求解线性规划问题的步骤:

(0)导入 PuLP库函数

import pulp

(1)定义一个规划问题

MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize)

pulp.LpProblem 是定义问题的构造函数。

"LPProbDemo1"是用户定义的问题名(用于输出信息)。

参数 sense 用来指定求最小值/最大值问题,可选参数值:LpMinimize、LpMaximize 。本例 “sense=pulp.LpMaximize” 表示求目标函数的最大值。

(2)定义决策变量

x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') 
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous')
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') 

pulp.LpVariable 是定义决策变量的函数。
'x1' 是用户定义的变量名。

参数 lowBound、upBound 用来设定决策变量的下界、上界;可以不定义下界/上界,默认的下界/上界是负无穷/正无穷。本例中 x1,x2,x3 的取值区间为 [0,7]。

参数 cat 用来设定变量类型,可选参数值:'Continuous' 表示连续变量(默认值)、' Integer ' 表示离散变量(用于整数规划问题)、' Binary ' 表示0/1变量(用于0/1规划问题)。

(3)添加目标函数

MyProbLP += 2*x1 + 3*x2 - 5*x3  	# 设置目标函数

添加目标函数使用 "问题名 += 目标函数式" 格式。

(4)添加约束条件

MyProbLP += (2*x1 - 5*x2 + x3 >= 10)  # 不等式约束
MyProbLP += (x1 + 3*x2 + x3 <= 12)  # 不等式约束
MyProbLP += (x1 + x2 + x3 == 7)  # 等式约束

添加约束条件使用 "问题名 += 约束条件表达式" 格式。

约束条件可以是等式约束或不等式约束,不等式约束可以是 小于等于 或 大于等于,分别使用关键字">="、"<="和"=="。

(5)求解

MyProbLP.solve()
print("Status:", pulp.LpStatus[MyProbLP.status]) # 输出求解状态
for v in MyProbLP.variables():
    print(v.name, "=", v.varValue)  # 输出每个变量的最优值
print("F(x) = ", pulp.value(MyProbLP.objective))  #输出最优解的目标函数值   

solve() 是求解函数。PuLP默认采用 CBC 求解器来求解优化问题,也可以调用其它的优化器来求解,如:GLPK,COIN CLP/CBC,CPLEX,和GUROBI,但需要另外安装。 

2.3、Python例程:线性规划问题

例程 1:求解线性规划问题

import pulp
MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize)  # 求最大值
x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') 
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous') 
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') 
MyProbLP += 2*x1 + 3*x2 - 5*x3  	# 设置目标函数
MyProbLP += (2*x1 - 5*x2 + x3 >= 10)  # 不等式约束
MyProbLP += (x1 + 3*x2 + x3 <= 12)  # 不等式约束
MyProbLP += (x1 + x2 + x3 == 7)  # 等式约束
MyProbLP.solve()  # youcans@xupt
print("Status:", pulp.LpStatus[MyProbLP.status]) # 输出求解状态
for v in MyProbLP.variables():  # youcans
    print(v.name, "=", v.varValue)  # 输出每个变量的最优值
print("Max F(x) = ", pulp.value(MyProbLP.objective))  #输出最优解的目标函数值

例程 1 运行结果:

Welcome to the CBC MILP Solver 

Version: 2.9.0 

Build Date: Feb 12 2015 

Status: Optimal

x1 = 6.4285714

x2 = 0.57142857

x3 = 0.0

Max F(x) =  14.57142851

例程01 程序说明:

  • 用 PuLP 库求解线性规划问题,可以选择求最大值或最小值,可以按照问题的数学描述,直接输入目标函数、等式约束和不等式约束,不等式约束可以选择 <= 或 >=,不需要进行转换。这中方式简单直观,非常适合初学者掌握。
  • 对于较大规模线性规划问题, PuLP 库支持用字典类型(dict)建立多个变量,设置目标函数和约束条件。

三、小结

求解线性规划问题的方法非常简单,本文实际上并未讲解具体的算法。

希望通过对求解方法、算法和编程方案的讲解,阐明作者对于数学建模学什么、怎么学的理解,也使读者能了解本系列教程的特点:本教程不打算详细讲解各种算法的具体方法,重点介绍如何使用第三方包实现算法、解决问题。

以上就是浅谈Python数学建模之线性规划的详细内容,更多关于Python 线性规划的资料请关注179885.Com其它相关文章!

猜你在找的浅谈Python数学建模之线性规划相关文章

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问
Jython 是 Python 的纯 Java 实现。她无缝地结合了 Java 类与 Python,使用户能以 Python 语言的语法编写在 Java 虚拟机上运行的 软件,本文重点给大家介绍通过Jytho
为大家详细介绍了Opencv Python实现两幅图像匹配,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的程序猿们可以参考一下
Python借助openpyxl可以对xlsx文件进行操作,帮助大家高效办公,处理excel文件,下面就介绍一下相关的方法,以及一个小例子。
MySQLdb是用于Python链接Mysql数据库的接口,它实现了Python数据库API规范V2.0,基于MySql C API上建立的,本文给大家介绍pycharm找不到MySQLdb模块解决方法,需要的朋友
一般查询都是单条件查询,F和Q是组合条件查询,本文主要介绍了django中F与Q查询的使用,感兴趣的可以了解一下
sqlite的官网 sqlite.org/index.html SQLite 作为一个SQL数据库引擎,是由C语言实现的,又小又快,具有高可靠性且功能齐全。 作为嵌入式数据库,在移动设备中使用非常广
作为Python开发者,你迟早都会用到图形用户界面来开发应用。本文将推荐Python GUI工具取色器的一些知识,感兴趣的朋友一起看看吧
为大家详细介绍了python学生信息管理系统的实现代码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的程序猿们可以参考一下
我们经常需要解析用不同语言编写的数据。Python提供了许多库来解析或拆分用其他语言编写的数据。在此Python XML解析器教程中,您将学习如何使用Python解析XML
为大家详细介绍了python使用tcp传输图片数据,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的程序猿们可以参考一下
本文给大家分享python持久化存储文件操作方法,给大家讲解存储文件的重要性,指针的基本概念及关闭文件的方法,介绍文件的创建和删除技巧,感兴趣的朋友一起看看吧