线性规划 单纯形法，单纯形法，请问这个怎么算？要步骤和思路，谢谢

来源：蜘蛛抓取(WebSpider) 时间：2017-09-14 02:02 标签： 线性规划 单纯形法
线性规划与单纯形法-博泰典藏网
典藏文档　篇篇精品
线性规划与单纯形法
导读：单纯形法迭代原理，例求解下列线性规划问题的最优解，可以看出x3,x4,x5的系数列向量是线性独立的，单纯形法计算步骤，对已经标准化的线性规划模型，1．单纯形表，例用单纯形法解上例中的线性规划问题，当线性规划的约束条件为≤号时，单纯形法迭代原理一、基本思路枚举法：若LP问题有最优解，则必可在某个顶点上达到，即在某个基可行解上取得最优解。因此，对LP问题，把所有基可行解都找出来，然后逐个进行比较，单纯形法迭代原理 一、基本思路 枚举法：若LP问题有最优解，则必可在某个顶点上达到，即在某个基可行解上取得最优解。因此，对LP问题，把所有基可行解都找出来，然后逐个进行比较，求出最优解。基本可行解的个数≤Cnm个，若m,n取值都很小还可以列出来，但如果m,n很大时，例如m=20,n=40时，Cnm≈1.3×1011，显然行不通。
逐步改善法：对于LP问题，先找出一个基可行解，判断其是否为最优解，如为否，则寻求一个更好的基可行解，一直找到最优解为止，但这种逐步改善的求解方法需要解决以下三个问题：
（1）如何判别当前的基本可行解是否已达到了最优解
（2）若当前解不是最优解，如何去寻找一个比当前解更好的基可行解
（3）如何得到一个初始的基可行解
求解下列线性规划问题的最优解
maxz?5x1?2x2?30x1?20x2?5x?x2?1??x1??x1?0
解：化为标准形式 ?160?15?4x2?0maxz?5x1?2x2?0?x3?0?x4?0?x5?30x1?20x2?x3?5x?x2?x4?1??x5?x1?x1?5?0?
13 ?160?15?4 第一步：确定一个初始基可行解；基可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵。
?3020100???A??51010? ?10001??? 这里m=3，3阶可逆方阵，可以看出x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基
?100???B(0)??010??(p3,p4,p5)，对应的基变量为x3,x4,x5，x1,x2为非基变量。 ?001??? 将基变量用非基变量表示，由(2)得：
x3=160-30x1-20x2 x4=15-5x1-x2 x5=4-x1
将(3)代入目标函数得Z=5x1+2x2+0
令非基变量x1=x2=0,代入(3),得到一个基可行解X(0)
X(0)=(0,0,160,15,4)
第二步：从当前基可行解转换为更好的基可行解；
从数学角度看，x1,x2的增加将会增加目标函数值，从目标函数值中x1,x2前的系数看，x1前的系数大于x2前的系数，所以让x1从非基变量转为基变量，称为进基变量，怎样确定离基变量：
因为x2仍为非基变量，故x2=0
则(3)式变为 x3=160-30x1
160/30=16/3 x4=15-5x1
15/5=3 x5=4-x1
14 min=3，所以当x1=3时，x4第一个减少到0，所以x4出基
则X(1)=(3,0,70,0,1) B(1)?(p1,p3,p5) Z(1)=15
此时非基变量为x2,x4,用非基变量表示基变量，代入(3)
x3=70-14x2+6x4 x1=3-1/5x2-1/5x4 x5=1+1/5x2+1/5x4
将(4)代入目标函数得Z=15+x2-x4
第三步：继续迭代
x2进基，x4仍为非基变量，令x4=0，则(4)式表示为
x3=70-14x2
70/14＝5 x1=3-1/5x2
3/(1/5)＝15 x5=1+1/5x2
min=5，所以当x2=5时，x3首先减少到0，所以x3出基
则X(2)=(2,5, 0,0,2) B(2)?(p1,p2,p5) Z(2)=20
此时非基变量为x3,x4,用非基变量表示基变量，代入(4)
x2=5-1/14x3+3/7x4 x1=2+1/70x3-2/7x4 x5=2-1/70x3+2/7x4
将(5)代入目标函数得Z=20-1/14x3-4/7x4
此时若非基变量x3,x4的值增加，只能使Z值下降
所以X(2)为最优解，Z*=20,
X*=(2,5, 0,0,2)’
15 单纯形法计算步骤 第1步：将LP数学模型标准化，构造一个初始基可行解
对已经标准化的线性规划模型，设法在约束矩阵Am×n中构造出一个m阶单位阵作为初始可行基，相应就有一个初始基本可行解。
第2步：判断当前基本可行解是否为最优解
用非基变量表示基变量及目标函数的表示式。在目标函数的表示式中，若至少有一个非基变量前的系数（检验数）为正数，则当前解不是最优解，反之，则是（最大化问题）。即对于最大化问题，当所有的检验数都≤0时，当前解即为最优解。
第3步：若当前解不是最优解，则要进行基变换迭代到下一个基本可行解。
(1)进基变量：目标函数表示式中，最大正检验数所属的非基变量 (2)出基变量：最小比值原则 (3基变换：得到新的基可行解
1．单纯形表
用单纯形法解上例中的线性规划问题 maxz?5x1?2x2?30x1?20x2?5x?x2?1??x1??x1?0?160?15?4x2?0 解：第1步：将LP数学模型标准化，构造一个初始基可行解
当线性规划的约束条件为≤号时，在每个约束条件的左端加上一个松弛变量。
对约束条件为≥或＝的情况，为便于找到初始基可行解，可以构造人工基，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。
maxz?5x1?2x2?0?x3?0?x4?0?x5?30x1?20x2?x3?5x?x2?x4?1??x5?x1?x1?5?0? 反映到表上
Cj XB X3 X4 X5 -Z b 160 15 4
5 X1 30 5 1 5 2 X2 20 1 0 2 0 X3 1 0 0 0 0 X4 0 1 0 0 0 X5 0 0 1 0 ?160?15?4 第2步：判断当前基本可行解是否为最优解
根据上节课讲的，将基变量用非基变量表示，判断检验数。
为了书写上的便利及总结规律，我们将所得到的标准形式中的变量次序重新整理及编号：让基变量排在前m个变量的位置上。这对所讨论的结果没有影响。这样可得到以下的模型形式： maxz??cjxjj?1ns.t:
x1?a1,m?1xm?1?...?a1nxn?b1 x2?a2,m?1xm?1?...?a2nxn?b2
…………………………… xm'?am,m?1xm?1?...?amnxn?bm xj?0(j?1,2,...,n) 这里，基变量为x1,x2,…,xm, 令非基变量xm+1=xm+2=…=xn=0
X1=(b1,b2,…,bm,0,0,…,0)’
一般情况下，经过若干次迭代后的当前解，其基变量用非基变量表示的典式的一般形式为
17 包含总结汇报、农林牧渔、外语学习、资格考试、教学研究、经管营销、自然科学以及线性规划与单纯形法等内容。本文共7页
相关内容搜索HTTP Error 404. The requested resource is not found.君，已阅读到文档的结尾了呢~~
本文档主要内容包括：线性规划问题及模型、图解法、单纯形方法及大M法、线性规划应用举例分析。
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
线性规划及单纯形法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口

我要回帖

更多关于 线性规划 单纯形法 的文章

 

随机推荐