线性规划问题的数学模型和标准形式

线性规划问题的数学模型和标准形式当下我们接触的不论是教科书还是各种学习资料，其实很多时候都会存在一个普遍性的问题，就是很多作者为了在追求严谨的基础上往往会将内容写得晦涩难懂。对于学习者来说，很多时候还是很头疼的。在将来，我也许会不定时分享一些有意思的学术文，我会用我自己的理解来表达出来，可能会有不太严谨的地方，也可能会存在一些错误，欢迎各位读者指正。在这个系列当中，我会分享一些关于数学建模的内容。但是我自己本身也是一个在学习阶段的数模小白，所以我就单纯分享一些较为基础的学习笔记。今天这篇分享的是数学建模里的第一个模型——线性规划。在这篇文章里的例子均是在网上摘录的，如果碰到相似的部分就是我借鉴的。什么是线性规划问题？首先我们先理解一下什么是线性线性这个词在我们的学习过程中还是挺经常会碰见的。从定义上来说，只要两个变量之间表现为一次函数关系，则这两个变量就呈现出线性关系。在几何意义上表示为直线。因此仅有一次函数参与的问题就可称之为线性问题。由线性可以引出两条代数性质若f(x)为线性函数1）可加性2）比例性两则性质相结合可知请在初高中的学习阶段我们可能会遇到这样的问题：根据高中线性规划问题的做法，具体解题过程如下：这就是简单的线性规划问题，线性规划其实就是研究线性约束条件下线性目标函数的极值问题。数学建模中的线性规划问题数学建模中的线性规划问题则会更贴近我们的生活以及生产实践日常，在已知条件下去找到最优方案等。在接下来笔者会通过一道具体例子来进行展开解释。例.某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

根据现有的数学知识很容易可以做出如下分析：在这里为了为后续代码部分做铺垫，笔者将约束条件分成以下三类1.不等式约束条件（上述式子中的1、2、3式）2.等式约束条件（上述式子中未出现，其实就是一次方程或一次方程组）3.决策变量的最小取值和最大取值（上述式子中的4式）线性规划问题在Matlab中的具体代码实现在数学建模当中python也同样可以实现相同的功能，笔者在这里采用matlab进行具体问题解决。有关matlab的基础语法在这里就不进行过多的解释。对于有一定编程基础的来说，matlab一定不算太难的。在matlab标准型中，所求目标函数为最小值（若要求最大值，则在此基础上对目标函数两边乘一个负号即可），同时要求约束条件必须为小于等于号或者等于号（若约束条件中出现大于等于号，则需在不等式两边乘上负号使其变号）。Linprog函数是解决线性规划问题的代码核心linprog函数标准形式为[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)其中x为返回最优解的变量取值，fval为返回目标函数的最优值。右边的参数会在后面进行相应的解释。接下来的部分会涉及一些有关线性代数的知识，当然涉及的部分也不算太难。我们将其标准形式中的多个参数分别对应到刚才阐释过的目标函数及三类约束条件来理解。1、参数ff表示的含义为目标函数中的系数列向量。由于我们所求的是最大值，不满足matlab所求的应为最小值的要求，所以我们要先将目标函数等式左右两边乘上负号。即目标函数变为：因此在代码中f=[-4000;-3000]注意：由于是列向量，在代码中相邻之间是“;”而不是“,”。2、不等式约束条件中的参数A:不等式约束条件中的变量系数矩阵b:不等式约束条件中的常数项矩阵在该例中1、2、3不等式可以整合成如下矩阵形式在具体的代码中呈现为：A=[2,1;1,1;0,1]b=[10;8;7]注意：若出现大于等于号，要在不等式两边同乘上一个负号，将其转换为小于等于号。3、等式约束条件中的参数Aeq:等式约束条件的系数矩阵beq:等式约束条件的常数项矩阵在该例中未出现等式约束条件，在这里笔者举一个例子假设存在这样一组等式约束条件：由此我们可以转换成矩阵形式：具体代码写作：Aeq=[1,1,1;0,2,3;2,0,0]beq=[7;0;14]4、决策变量的约束lb:决策变量的最小取值ub:决策变量的最大取值在这里我们也要将4式转换为矩阵形式：即lb=[0;0]在这一例子当中没有决策变量的上界约束。关于linprog函数的调用细节细心的读者读到这里已经会发现，在我们的例子当中缺少了等式约束条件，同时也没有决策变量的最大取值，但是在Matlab的linprog函数的标准形式中却有这些参数，我们在调用的时候该如何处理呢？总体遵循以下规则：1、若从某一参数开始，后续的参数均不存在，则后续的均可省略不写2、若在中间有出现参数缺失的情况，用“[]”在函数中进行占位详情见以下代码及结果：由结果可知最优方案为生产2台甲机床和生产6台乙机床，此时可以收获最大利润26000元。总结线性规划的研究成果还推动着其他数学问题包括整数规划、随机规划和非线性规划的算法研究。在本篇文章中的具体例子为较为浅显的情况，希望读者能从中有所收获。

数学建模常见最值求法——简单的线性规划问题

在建模赛题我们常常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题，实际上此类问题在生产实践中也很常见。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(LinearProgramming简记LP)则是数学规划的一个重要分支。1、线性规划的实例与定义例1

某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000

元与3000

元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床

需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10

小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产x₁台甲机床和x₂乙机床时总利润最大，则x₁和x₂应满足：这里变量x₁和x₂称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subjectto)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。2、线性规划的Matlab

标准形式

线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab

中规定线性规划的标准形式为其中c

和x

为n

维列向量，A

、Aeq

为适当维数的矩阵，b、beq为适当维数的列向量。例如线性规划的Matlab标准型为3、线性规划问题的解的概念

一般线性规划问题的（数学）标准型为可行解：满足约束条件（4）的解x

=

(

x₁，x₂,...,xn

)

，称为线性规划问题的可行解，而使目标函数（3）达到最大值的可行解叫最优解。

可行域：所有可行解构成的集合称为问题的可行域，记为R。4、

线性规划的图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线。对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*

=

(2,6)T，最优目标值z*

=26。从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空

时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R

非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。5、求解线性规划的Matlab解法

单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不再介绍单纯形法。下面我们介绍线性规划的Matlab解法。Matlab

中线性规划的标准型为基本函数形式为linprog(c,A,b)，它的返回值是向量x的值。还有其它的一些函数调用形式（在Matlab指令窗运行helplinprog可以看到所有的函数调用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，LB和UB

分别是变量x

的下界和上界，X

0是X

的初始值OPTIONS是控制参数。例2

求解下列线性规划问题解

（i）编写M

文件

c=[2;3;-5];a=[-2,5,-1;1,3,1];b=[-10;12];aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*