数学建模模型之线性规划

()若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域的顶点上述论断可以推广到一般的线性规划问题,区别只在于空问的维数。在一般的维空间中,满足一线性等式∑的点集被称为一个超平面,而满足一线性不等式∑或∑≥)的点集被称为一个半空间(其中为一维行向量,为一实数)。若干个半空间的交集被称为多胞形,有界的多胞形又被称为多面体。易见,线性规划的可行域必为多胞形(为统一起见,空集Φ也被视为多胞形)。在一般维空间中,要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点,但这一几何概念的推广在一般维空间中的几何意义并不十分直观。为此,我们将采用另一途径来定义它。定义称维空间中的区域为一凸集,若V∈及∨A∈有+-∈。定义设为维空间中的一个凸集,中的点被称为的一个极点,若不存在∈及∈,使得=元+-A。定义说明凸集中任意两点的连线必在此凸集中;而定义说明,若是凸集的个极点,则不能位于中任意两点的连线上。不难证明,多胞形必为集。同样也不难证明,二维空间中可行域的顶点均为的极点(也没有其它的极点)求解线性规划的解法单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法,有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的解法。中线性规划的标准型为基木函数形式为它的返回值是向量的值。还有其它的些函数调用形式(在指令窗运行可以看到所有的函数调用形式),如:这里返回目标函薮的值,和分别是变量的下界和上界,是的初始值,是控制参数。例求解下列线性规划问题解()编写文件)将文件存盘,并命名为()在指令窗运行即可得所求结果。例求解线性规划问题解编写程序如下:C=12;3;1|;a=[1,4,2;3,2,0b=[8;6];x, y l=linprog(c, -a,-b,, II, zeros (3, 1))叫以转化为线性规划的问题很多看起米不是线性规划的问题也可以通过变换变戊线性规划的问题来解决。如:例规划问题为十其中和为相应维数的矩阵和向量要把上面的问题变换成线性规划问题,只要注意到事实:对任意的,存在>满足事实上,我们只要取就可以满足上面的条件。这样,记,从而我们可以把上面的问题变成例其中E对于这个问题,如果我们取E,这样,上面的问题就变换成此目我们通常的线性规划问题。运输问题产销平衡例某商品有个产地、个销地,各产地的产量分别为…,各销地的需求量分别为∴。若该商品由产地运到销地的单位运价为,问应该如何调运才能使总运费最省?解:引入变量,其取值为由产地运往销地的该商帛数量,数学模型为显然是一个线性规划问题,当然可以用单纯形法求解对产销平衡的运输问题,由于有以下关系式存在∑=∑∑|∑其约束条件的系数矩阵相当特殊,可用比较简单的计算方法,习惯上称为表上作业法(山康托洛维奇和希奇柯克两人独立地提出,简称康一希表上作业法)。§指派问题指派问题的数学模型例拟分配人去干项工作,每人干且仅干一项工作,若分配第人去干第项工作,需花费单位时间,问应如何分配工作才能使工人花费的总时间最少?容易看出,要给出个指派问题的实例,只需给出矩阵被称为指派问题的系数矩阵。引入变量,若分酉十工作,则取=,否则取。上述指派问题的数学模型为或上述指派问题的可行解可以用个矩阵表示,其每行每列均有且只有一个元素为,其余元素均为;可以用中的一个置换表示。问题中的变量只能取或,从而是个规划问题。般的规划问题求解极为困难。但指派问题并不难解,其约束方程组的系数矩阵十分特殊(被称为全单位模矩阵,其各阶非零子式均为±),其非负可行解的分量只能取或,故约束或可改写为≥而不改变其解。此时,指派问题被转化为一个特殊的运输问题,其中求鲜指派问题的匈牙利算法由于指派问题的特殊性,又存在着由匈牙利数学家提出的更为简便的解法匈牙利算法。算法主要依据以下事实:如果系数矩阵行(或·列)中每元素都加上或减去同一个数,得到一个新矩阵=,则以或为系数矩阵的指派问题具有相同的最优指派例求解指派问题,其系数矩阵为解将第一行元素减去此行中的最小元素,同样,第二行元素减去,第三行元素减去,最后一行的元素减去,得再将第饥元素各减去,得以为系数矩阵的指派问题有最优指派由等价性,它也是例的最优指派。有时问题会稍复杂一些。例求铎系数矩阵的指派问题解:先作等价变换如下容易看出,从变换后的矩阵中只能选出四个位于不同行不同列的零元素,但最优指派还无法看岀。此时等价变换还可进行下去。步骤如下对未选出元素的行打∨;对行中元素所在列打:对∨列中选中的元素所在行打;重复()、()直到无法再打ⅴ为止可以证明,若用直线划没有打ⅴ的行与打ⅴ的列,就得到了能够覆盖住矩阵中所有零元索的最少条数的直线集合,找出未覆盖的元素中的最小者,令√行元素减去此数,∨列元素加上此数,则原先选中的元素不变,而未覆盖元素中至少有一个已转变为,且新矩阵的指派问题与原问题也等价。上述过稈可反复采用,直到能选取出足够的元素为止。例如,对例变换后的矩阵再变换,第三行、第五行元素减去,第列元素加上,得现在已可看出,最优指派为§对偶理论与灵敏度分析原始问题和对偶问题考虑下列一对线性规划模型和称()为原始问题,()为它的对偶问题不太严谨地说,对偶问题可被看作是原始问题的“行列转置”()原始问题中的第列系数与其对偶问题中的第行的系数相同;()原始目标函数的各个系数行与其对偶问题右侧的各常数列相同;)原始问题右侧的各常数列与其对偶目标函数的各个系数行相同()在这·对问题中,不等式方向和优化方向相反考虑线性规划:把其中的等式约束变成不等式约束,可得它的对偶问题是其中和分别表示对应于约束和-≥-的对偶变量组。令则上式又可写成原问题和对偶的对偶约束之间的关系变量行约束≤>无限伺行约束变量无限訇对偶问题的基本性质对称性:对偶问题的对偶是原问题。弱对偶性:若ˉ是原问题的可行解,一是对偶问题的可行解。则存在无界性:若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解,可行解是最优解时的性质:设是原问题的可行解,是对偶问题的可行解,是最优解。对偶定理:若原问题有最优解,那么对偶问题也有最优解;且目标函数值相同。互补松弛性:若分别是原问题和对偶问题的最优解,则例已知线性规划问题已知其对偶问题的最优解为。试用对偶理论找出原问题的最优解解先写出它的对偶问题+≤①②③④⑤将的值代入约束条件,得②,③,④为严格不等式;由互补松弛性得>;原问题的两个约東条件应取等式,故有求解后得到==:故原问题的最优解为灵敏度分析在以前讨论线性规划问题时,假定都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变,值就会变化;往往是因工艺条什的改变而改变;是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题:当这些系数有一个或几个发生变化时,已求得的线性规划问题的最优解会有什么变化;或者这些系数在什么蒞围内变化时,线性规划问题的最优解或最优基不变。这里我们就不讨论了参数线性规划参数线性规划是研究这些参数中某一参数连续变化时,使最优解发生变化的各临界点的值。即把某一参数作为参变量,而日标函数在某区间内是这参变量的线性凶数,含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题§投资的收益和风险问题提出市场上有种资产(=)可以选择,现用数额为的相当大的资金作一个时期的投资。这种资产在这一时期内购买的平均收益率为,风险损失率为,投资越分散,总的风险越少,总体风险可用投资的中最大的一个风险米度量。购买时要付交易费,(费率),当购买额不超过给定值时,交易费按购头计算。另外,假定同期银行存款利率是,既无交易费又无风险。(已知=时相关数据如表试给该公司设计一种投资组合方案,即用给定资金,有选择地购头若十种资产或存银行生息,使净收益尽可能大,使总体风险尽可能小。符号规定和基本假设符号规定:第种投资项目,如股票,债券分别为的平均收益率,交易费率,风险损失率的父易定额同期银行利率投资项日的资金投资风险度总体收益基本假设:投资数额相当大,为了使于计算,假设投资越分散,总的风险越小总体人险用投资项目中最大的一个风险来度量;种资产之间是相互独立的;.在投资的这一时期内,为定值,不受意外因素影响净收益和总体风险只受影响,不受其它因素干扰。模型的分析与建立总体风险用所投资的中最大的一个风险来衡量,即购买所付交易贵是一个分段函数,即交易费=而题日所给定的定佰(单位:元)相对总投资很少,更小,可以忽略不计,这样购买的净收益为要使净收益尽可能大,总体风险尽可能小,这是一个多日标规划模犁10