君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
实验1__线性规划
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口约束函数和目标函数带绝对值号的特殊非线性规划问题的求解方法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
约束函数和目标函数带绝对值号的特殊非线性规划问题的求解方法
&&运筹学 非线性规划
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩4页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢查看: 12414|回复: 12|关注: 0
单纯形法简介
<h1 style="color:#4 麦片财富积分
不知何许人也~
入门, 积分 344, 距离下一级还需 156 积分
关注者： 415
simplex method
　　求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
　　用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。
　　改进单纯形法 原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。
　　对偶单纯形法 　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
& & 数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。
这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。
==============================
我的另一篇帖子有关单纯形法实现和GUI界面
[ 本帖最后由 faruto 于
13:54 编辑 ]
[url=.cn/faruto][color=red]孤单是一个人的狂欢狂欢是一群人的孤单[/color][/url] [url=/thread-.html]神经网络30个案例分析[/url]
<h1 style="color:# 麦片财富积分
关注者： 1
遭遇无钱下载，:'(
<h1 style="color:#7 麦片财富积分
关注者： 22
运筹学的内容，好啊
<h1 style="color:#4 麦片财富积分
不知何许人也~
关注者： 415
回复 3# 的帖子
感觉坛子里 运筹学方面的 资料不是很多，这好我这段有这门课就发了一些上来~！:) :)
[url=.cn/faruto][color=red]孤单是一个人的狂欢狂欢是一群人的孤单[/color][/url] [url=/thread-.html]神经网络30个案例分析[/url]
<h1 style="color:#4 麦片财富积分
不知何许人也~
关注者： 415
回复 2# 的帖子
遭遇无钱下载，:'(
你想要那个ＧＵＩ的源代码吗？把邮箱告诉我，我传给你好了～！:)
[url=.cn/faruto][color=red]孤单是一个人的狂欢狂欢是一群人的孤单[/color][/url] [url=/thread-.html]神经网络30个案例分析[/url]
<h1 style="color:#7 麦片财富积分
关注者： 22
原帖由 faruto 于
00:37 发表
感觉坛子里 运筹学方面的 资料不是很多，这好我这段有这门课就发了一些上来~！:) :)
线性规划,非线性规划都是啊,论坛里不少问题啊
<h1 style="color:# 麦片财富积分
我也是没钱下载:'(
<h1 style="color:# 麦片财富积分
，谢谢了，不过不知道你知不知道二次规划的算法。
<h1 style="color:# 麦片财富积分
哎，没钱。
想用来算一下水环境容量的东西。
，不知道能不能给我发一下！
<h1 style="color:# 麦片财富积分
KARMARKA算法
单纯形法虽然有效,但不是多项式算法,在求解大规模问题时有可能出现死循环的情况,为此,KARKARKA曾在1984年提出改进的内点算法,称为KARMARKA算法,该算法是多项式时间算法,如果有兴趣大家可以看相应的资料
站长推荐 /2
机器视觉和人工智能在医疗设备中的应用及实现
MATLAB中文论坛是全球最大的 MATLAB & Simulink 中文社区。用户免费注册会员后，即可下载代码，讨论问题，请教资深用户及结识书籍作者。立即注册加入我们吧！
MATLAB官方社交平台
MATLAB中文论坛微社区当前位置： >>
第二章 单纯形法单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法1单纯形法的一般原理考虑到如下线性规划问题maxZ=CX ?AX=b ? ?X ≥ 0其中Ａ一个m 矩阵，且秩为m 总可以被调整为一个m 其中 Ａ 一个m×n 矩阵 ， 且秩为 m ， ｂ总可以被调整为一个 m 维非负列 向量， 向量，Ｃ为n维行向量，Ｘ为n维列向量。 维行向量， 维列向量。 根据线性规划基本定理： 根据线性规划基本定理： 如果可行域Ｄ ＡＸ= 非空有界， 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 上的最优目标函数值Ｚ ＣＸ一定可以在 的一个顶点上达到。 一定可以在Ｄ 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。 这个重要的定理启发了Dantzig的单纯形法， 这个重要的定理启发了Dantzig的单纯形法， Dantzig的单纯形法 即将寻优的目标集中在D的各个顶点上。 即将寻优的目标集中在D的各个顶点上。2Dantzig的单纯形法把寻优的目标集中在所有基本可行解 Dantzig的单纯形法把寻优的目标集中在所有基本可行解 即可行域顶点） （即可行域顶点）中。 其基本思路是从一个初始的基本可行解出发， 其基本思路是从一个初始的基本可行解出发，寻找一条达到 最优基本可行解的最佳途径。 单纯形法的一般步骤如下： 最优基本可行解的最佳途径。 单纯形法的一般步骤如下： 寻找一个初始的基本可行解。 （1）寻找一个初始的基本可行解。 检查现行的基本可行解是否最优，如果为最优， （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 则停止迭代，已找到最优解，否则转一步。 移至目标函数值有所改善的另一个基本可行解， （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（ 然后转会到步骤（2）。3确定初始的基本可行解确定初始的基本可行解等价于确定初始的可行基， 确定初始的基本可行解等价于确定初始的可行基，一旦初始 的可行基确定了， 的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ 中前m个系数列向量恰好构成一个可行基， 中前m个系数列向量恰好构成一个可行基，即 Ａ=（ＢＮ），其中 （ＢＮ），其中 Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量 Ｐ 为基变量x x 构成的可行基， 构成的可行基， 为非基变量xm+1， m+2， x =(Ｐm+1， m+2， Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn的 系数列向量构成的矩阵。 系数列向量构成的矩阵。4所以约束方程AX=b 就可以表示为?XB ? A X = (B N ) ? ? =BX B +NX N =b ?XN ?用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 用可行基Ｂ的逆阵Ｂ 左乘等式两端，再通过移项可推得：X B =B b-B NX N若令所有非基变量 X N =0 , 由此可得初始的基本可行解 则基变量-1-1X B =B -1b? B?1b ? X= ? ? ? 0 ?5AX=b → BX B +NX N =b → X B =B-1b-B-1 NX N → X N =0,X B =B-1b问题： 问题： 要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。 要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。 基由系数矩阵Ａ 个线性无关的系数列向量构成。 基由系数矩阵Ａ中m个线性无关的系数列向量构成。 但是要判断m个系数列向量是否线性无关并非易事。 但是要判断m个系数列向量是否线性无关并非易事。 即使系数矩阵Ａ中找到了一个基B 也不能保证该基恰好是可行基。 即使系数矩阵Ａ中找到了一个基B，也不能保证该基恰好是可行基。 因为不能保证基变量Ｘ b≥0 因为不能保证基变量ＸB=Ｂ-1b≥0。? B?1b? 为了求得基本可行解 X=? ，必须求基Ｂ的逆阵Ｂ-1。 ? 必须求基Ｂ的逆阵Ｂ ? 0 ?但是求逆阵Ｂ 也是一件麻烦的事。 但是求逆阵Ｂ-1也是一件麻烦的事。 结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I 结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始 可行基Ｂ 可行基Ｂ，6为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规 为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规 Ｂ， 划标准化过程中作如下处理： 划标准化过程中作如下处理： 若在化标准形式前， 个约束方程都是“ 若在化标准形式前，m个约束方程都是“≤”的形式， 的形式， 那么在化标准形时只需在一个约束不等式左端都加上一个松弛变 (i=12…m) m)。 量xn+i (i=12 m)。 若在化标准形式前，约束方程中有“ 若在化标准形式前，约束方程中有“≥”不等式， 不等式， 那么在化标准形时除了在方程式左端减去剩余变量使不等式变 成等式以外，还必须在左端再加上一个非负新变量， 成等式以外，还必须在左端再加上一个非负新变量，称为 人工变量． 人工变量． 若在化标准形式前，约束方程中有等式方程， 若在化标准形式前，约束方程中有等式方程，那么可以直接在 等式左端添加人工变量。 等式左端添加人工变量。7判断现行的基本可行解是否最优? B?1b ? 假如已求得一个基本可行解 X= ? ? 0 ? ?将这一基本可行解代入目标函数， 将这一基本可行解代入目标函数，可求得相应的目标函数值? B?1b ? Z=CX=(CBC N ) ? =CB B-1b ? ? 0 ?其中 C =(c ,c ,? c ), C =(c ,c ,? c ) 分别表示基变量和 B 1 2 m N m+1 m+2 n 非基变量所对应的价值系数子向量。 非基变量所对应的价值系数子向量。8是否已经达到最大值， 要判定 Z=C B B -1 b 是否已经达到最大值，只需将 代入目标函数，使目标函数用非基变量 X B = B -1 b -B -1 N X N 代入目标函数，使目标函数用非基变量 表示， 表示，即：? XB ? Z=CX=(C B C N ) ? ? XN ? ? =C B X B +C N X N =C B (B -1b-B -1 NX N )+C N X N-1 -1? x m+1 ? =C B B b+(C N -C B B N)X N ? ? x m+2 ? ? C B B -1 b+ σ N X N = C B B -1 b+(σ m+1, σ m+1, ? σ n ) ? ? ? ? ? ? x ? ? ? n ? 称为非基变量Ｘ 其中 σ N =C N -CB B-1 N=(σ m+1 , σ m+1 ,?σ n ) 称为非基变量ＸN的检验向量，它的各个分量称为检验数。 的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小 ≤0，那么现在的基本可行解就是最优解。 于等于0 于等于0，即σN≤0，那么现在的基本可行解就是最优解。9定理1 定理1：最优解判别定理 对于线性规划问题若某个基本可行解所对应的检验向量 σ N =C N -C B B -1 N ≤ 0 ， 则这个基本可行解就是最优解。 则这个基本可行解就是最优解。maxZ=CX, D= {X ∈ R n /AX=b,X ≥ 0}? x m+1 ? ? ? x m+2 ? -1 Z = C B B b+(σ m+1, σ m+1, ? σ n ) ? ? ? ? ? ? x ? ? ? n ?定理2：无穷多最优解判别定理 定理2? B?1b ? 是一个基本可行解，所对应的检验向量 是一个基本可行解， 若 X= ? ? ? 0 ?其中存在一个检验数σ =0， σ N =C N -CB B-1 N ≤ 0 ，其中存在一个检验数σm+k=0， 则线性规划问题有无穷多最优解。 则线性规划问题有无穷多最优解。10基本可行解的改进如果现行的基本可行解Ｘ不是最优解， 如果现行的基本可行解Ｘ不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解Ｘ σ N =C N -CB B-1N 中存在正的检验数，则需在原基本可行解Ｘ的基 础上寻找一个新的基本可行解，并使目标函数值有所改善。 础上寻找一个新的基本可行解 ，并使目标函数值有所改善。 具体 做法是： 做法是： 先从检验数为正的非基变量中确定一个换入变量， 先从检验数为正的非基变量中确定一个换入变量 ， 使它从非基 变量变成基变量（将它的值从零增至正值） 变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量， 再从原来的基变量中确定一个换出变量 ，使它从基变量变成非 基变量（将它的值从正值减至零） 基变量（将它的值从正值减至零）。? x m+1 ? ? ? x m+2 ? -1 由此可得一个新的基本可行解， 由此可得一个新的基本可行解，由 Z = C B B b+(σ m+1, σ m+1, ? σ n ) ? ? ? ? ? 可知，这样的变换一定能使目标函数值有所增加。 可知，这样的变换一定能使目标函数值有所增加。 ? x ? ? ? n ?11换入变量和换出变量的确定： 换入变量和换出变量的确定： 换入变量的确定― 换入变量的确定 最大增加原则 假设检验向量 σ N =C N -C B B N=(σ m+1 , σ m+2 ,?σ n ) ， 若其中有两个以上的检验数为正， 若其中有两个以上的检验数为正，那么为了使目标函数值增加得快 通常要用“最大增加原则” 些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基 变量为换入变量，即若 变量为换入变量，-1max {σ j /σ j &0,m+1 ≤ j ≤ n} =σ m+k 为换入变量， 则选取对应的 xm+k 为换入变量，且为最大， 由于σ m+k & 0 且为最大， 由零增至正值， 因此当 x m+k 由零增至正值，? xm+1 ? ? ? xm+2 ? Z = CBB-1b+(σm+1,σm+1, ?σn ) ? 可使目标函数值 ? ? ? 最大限度的增加。 最大限度的增加。 ? ? x ? ? ? n ?12换出变量的确定― 换出变量的确定 最小比值原则 为换入变量， 如果确定 x m+k为换入变量，方程X B = B -1 b -B -1 N X N ? X B = B -1 b -B -1 Pm + k x m + k其中 Pm+k为Ａ中与x m+k对应的系数列向量。 对应的系数列向量。中确定一个基变量为换出变量。 现在需在 X B =(x1 , x 2 ,? x m )T 中确定一个基变量为换出变量。 由零慢慢增加到某个值时， 的非负性可能被打破。 当 x m+k 由零慢慢增加到某个值时， B 的非负性可能被打破。 X 为保持解的可行性，可以按最小比值原则确定换出变量： 为保持解的可行性，可以按最小比值原则确定换出变量： 若? (B-1b)i ? (B-1b)l ? min ? -1 /(B-1Pm+k )i &0,1 ≤ i ≤ m ? = -1 ? (B Pm+k )i ? (B Pm+k )l ?则选取对应的基变量 x l 为换出变量。 为换出变量。13定理3 定理3：无最优解判别定理? B?1b ? 是一个基本可行解， 若 X= ? ? 是一个基本可行解，有一个检验数 σ m+k ? 0 ? -1 则该线性规划问题无最优解。 但是 B Pm+k ≤ 0 ，则该线性规划问题无最优解。证：令 x m+k = λ,(λ & 0)，则得新的可行解 将上式代入 X B =B b-B Pm+k x m+k = B b-B Pm+k λ-1 -1 -1 -1&0，? x m+1 ? ? ? ? ? ? -1 Z=C B B b+(σ m+1 , ? σ m+k , ? σ n ) ? λ ? = C B B -1 b+σ m+k λ ? ? ? ? ? ? x ? ? n ?因为σ m+k & 0,故当λ→+∞时 Z→+∞。 故当λ→+∞时，Z→+∞。 λ→+∞14用初等变换求改进了的基本可行解假设Ｂ 假设Ｂ是线性规划maxZ=CX,AX=b,X ≥ 0 的可行基，则 的可行基，?XB ? ?XB ? -1 ( I,B N ) ? = B -1 b A X =b ? (B N ) ? ? ? = b ? XN ? ? ?XN ?令非基变量 X N =0 ，则基变量 X B =B?1b 。? B?1b ? 可得基本可行解 X= ? ?。 ? 0 ?左乘约束方程组的两端， 用逆阵 B?1 左乘约束方程组的两端，等价于对方程组施以一系列 的初等“行变换”。变换的结果是将系数矩阵Ａ中的可行基Ｂ变换 的初等“行变换” 变换的结果是将系数矩阵Ａ中的可行基Ｂ 成单位矩阵I 把非基变量系数列向量构成的矩阵Ｎ B?1 N 成单位矩阵I，把非基变量系数列向量构成的矩阵Ｎ变换成 把资源向量b 把资源向量b变换成 b B?1 。15，由于行初等变换后的方程组 (I,B -1 N) ? ??XB ? 与原约束方程组 AX=b 或 ( B ,N ) ? ? = b 同解 ?XN ?XB ? -1 ? =B b ?XN ?只是在Ｘ 且改进了的基本可行解X &#39;只是在Ｘ的基变量的基础上用一个换 入变量替代其中一个换出变量，其它的基变量仍然保持不变。 入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些 基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基 基变量的系数列向量是单位矩阵I中的单位向量。 本可行解 X &#39; ，只需对增广矩阵( I,B N ,B b )施行初等行变换， 施行初等行变换，将换入变量的系数列向量变换成换出变量所对 应的单位向量即可。 应的单位向量即可。-1-116例1 maxZ=5x1 + 2x 2 + 3x 3 ? x 4 + x 5=8 ? x1 + 2x 2 + 2x 3 + x 4 ? + x5 = 7 ?3x1 + 4x 2 + x 3 ? x ,x ,x ,x ,x ≥ 0 ? 1 2 3 4 5解： 确定初始的基本可行解。 (１)确定初始的基本可行解。C = ( 5 ,2 ,3 , ? 1 , 1 )?1 A= ? ?32 42 11 00? ?8? ? b = ?7? 1? ? ??1 B=(P4 P5 )= ? ?00? ? ，基变量 1?x 4 ,x 5，非基变量 x1 ,x 2 , x 3 。? x1 ? ?x ? ?1 0? ? 1 2 2 ? CB =(-1,1) ?8? ? ? X B = ? 4 ? ,X N = ? x 2 ? ,B= ? ,N= ? , ,b= ? ? ? ? x5 ? 0 1? 3 4 1 ? C N =(5,2,3) ? ? ?7? ? ?x ? ? 3??8? X N = 0 → X B = B ? 1 b= ? ? ? X = ( 0 , 0 , 0 , 8 , 7 ) T ?7??1?8? Z=C B B b=(-1,1) ? ? = ? 1 ?7?17? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?(2) 检验 X = ( 0 ,0 ,0 , 8 , 7 ) T 是否最优。 是否最优。 检验向量 σ N = C N -C B B -1 N = (5 ,2,3)-(-1,1 ) ??1 ?32 42? ? 1?= (5,2 ,3 )-(2 ,2 ,-1)= (3 , 0 , 4 ) ↑ ↑ ↑ σ1 σ 2 σ 3因为σ =3， 均大于零， 因为σ1=3，σ3=4 均大于零， 不是最优解。 所以 X = ( 0 ,0 ,0 , 8 , 7 ) T 不是最优解。18? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?σN= (σ 1 ,σ 2 ,σ 3 ) = (3, 0 , 4 )（3）基本可行解 X = ( 0 ,0 ,0 , 8 , 7 ) T 的改进 ） ① 选取换入变量 因为max{3，4}=4， 为换入变量。 因为max{3，4}=4，取x3为换入变量。 max{3 ②?1选取换出变量? 8 ? ?1 ?2? ?8 7? 8 且 min ? , ? = ， B b= ? ? , B P3 = ? ? ≤ 0 ?2 1? 2 ?7? ?1?选取x 为换出变量. 选取x4为换出变量.? x4 ? ? x5? ?8? ?2? -1 -1 ? = B b -B P3 x 3 = ? ? - ? ? x 3 ?7? ?1? ?19? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?（4）求改进了的基本可行解 X&#39; ） 对约束方程组的增广矩阵施以初等行变换，使换入变量x 对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的1 2 系数列向量 P = ? ? 变换成换出变量x4所对应的单位向量 P = ? ? , 变换成换出变量x 4 ? ? 3 ? ??0? 注意保持基变量x 为单位向量不变。 注意保持基变量x5的系数列向量 P5 = ? ?为单位向量不变。 ?1??1?? 0?? 1 1 1 1 0 4? ? 1 2 2 1 0 8 ? 第一行除以２ 第一行除以２ ? 2 → ? ? ???????? ? 2 ? ? ?3 4 1 0 1 7 ? 3 4 1 0 1 7? ? ?1 1 1 1 0 4? ?2 ? 2 ????????→ ? ? 5 3 0 -1 1 3 ? ? ? ?2 2 ?第二行减去第一行20C = ( 5 ,2 ,3 , ? 1, 1 )?1 2 2 1 0 8? ? ? 3 4 1 0 1 7? ?可得改进的基本可行解。 可得改进的基本可行解。――――――――――――――――――――――――――?1 0? B=(P3 P5 )= ? x ? ，基变量 x 3 ， 5 非基变量x1 ,x 2 , x 4 。 ?0 1? 1? ?1 ? x1 ? 1 ?2 ? x3 ? ?1 0? ? 4? ? ? 2 ? CB =(3,1) X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2??1C = ( 5 ,2 ,3 , ?1 1 1 ?2 ? ? ?5 3 0 ?2? 1,1)1 0 4? ? 2 ? -1 1 3 ? 2 ??4? X N =0 → X B =B b= ? ? ? 基本可行解 X = ( 0 ,0 ,4 , 0 , 3 ) T ?3??4? Z=C B B b=(3,1) ? ? = 15 ?3??1目标函数值易见目标函数值比原来的Z=- 增加了， 再转向步骤(2) 易见目标函数值比原来的Z=-1增加了， 再转向步骤(2) Z=211? ?1 ? x1 ? 1 ?2 ? x3 ? ?1 0? ? 4? ? ? 2 ? CB =(3,1) X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? 2? ?2是否最优。 （2）检验 X = ( 0 ,0 ,4 , 0 , 3 ) T 是否最优。 ）? ? 检验向量 -1 σ N = C N -C B B N = (5 ,2 ,-1 )-(3 ,1 ) ? ? ? ? = (5 ,2 ,-1 )-(4 ,6 ,1 )= (1 , -4 , -2 )因为1 2 5 21 31 ? 2 ? ? -1 ? ? 2 ?σ1 = 1 & 0↑ ↑ ↑，Tσ1 σ 2 σ 4仍不是最优解。 所以 X = ( 0 ,0 ,4 , 0 , 3 ) 仍不是最优解。221? ?1 ? x1 ? 1 ?2 ? x3 ? ?1 0? ? 4? ? ? 2 ? CB =(3,1) X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? 2? ?2（3）基本可行解 X = ( 0 ,0 ,4 , 0 , 3 ) T 的改进 ） ① ② 选取换入变量1因为 σ为换入变量。 = 1 & 0 ，取 x1 为换入变量。选取换出变量?1 ?2 ?4? ?1 ?1 B b = ? ? , B P1 = ? ?3? ?5 ? ?2 为换出变量. 选取x 5 为换出变量. ? x ?3? ? ?≤0 ? ? ?-13 ? 3 ? 4 , 且 min ? ， ?= ?1/ 2 5 / 2 ? 5 / 2-1? 4 ? ? 1 /2 ? ? ? = B b -B P1 x 1 = ? ? - ? ? x1 ? 3 ? ? 5 /2 ? ? x5 ?231? ?1 ? x1 ? ? 2 1 2 ? CB =(3,1) ? x3 ? ?1 0? ? 4? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2? （4）求改进了的基本可行解 X &#39;&#39; ）对约束方程组的增广矩阵施以初等行变换， 对约束方程组的增广矩阵施以初等行变换，使换入变量? ? 的系数列向量 P1 = ? ? , ? ? 1 2 5 2 ? ? ? 变换成换出变量 ? ? ?x1 所对应?0? x 5 所对应的单位向量 P5 = ? ? ?1?1 1 1 2 6 0 -1 5 5 2 1 3 5 5 6 0 -1 5 5 0 2 5 -1 5 2 5 4 ? ? 6? ? 5? 17 ? 5 ? 6? ? 5??1 ?2 ?5 ? ?21 0 4? ?1 第二行乘以２ ５ 第二行乘以２/５ ?2 ? 2 ?? ? ? ? ? ? ?→ ? ? -1 1 3 ? 3 0 ? ?1 2 ? ? 1 1 ? ?? ? ? ? ? ? ? ? ? ? → ?1 ?第一行减以第二行的１ ２ 第一行减以第二行的１/２倍 ? 024C = ( 5 , 2 ,3 , ? 1 , 1 )?1 ?2 ?5 ? ?2 1 1C = ( 5 , 2 ,3 , ? 1 , 1 )2 1 3 -1 17 ? 5 5 5 5 ? 6 0 -1 2 6 ? ? 5 5 5 5?――――――――――――――――――――――――――可得改进的基本可行解。 可得改进的基本可行解。1 0 4? ?0 ? ? 2 ? ? ? 3 0 -1 1 3 ? ?1 2 ? ??1 0? B=(P3 P1 )= ? ? ，基变量 x 3 ,x 1 ，非基变量 x 2 ,x 4 , x 5 ?0 1? ? 2 3 -1 ? ? 17 ? ? x2 ? ? 5 5 5 ? CB =(3,5) ? 5? ? x3 ? ?1 0? ? ? X B = ? ? ,X N = ? x 4 ? ,B= ? ,b= ? ? ?, ? ,N= ? ? 6 -1 2 ? C N =(2,-1,1) ? 6? ?0 1? ? x1 ? ?x ? ? ? ? ? ? 5? ?5 5 5 ? ? 5? ? 17 ? ? 5 ? 6 17 ?1 X=( ,0, , 0, 0)T X N =0 → X B =B b= ? ? ? 基本可行解 5 5 ? 6 ?目标函数值 骤(2)? ? ? 17 ? ? 5 ? ? 5 ? 81 ?1 Z=C B B b=(3,5) ? ?= Z=15增加了 增加了， 比Z=15增加了，再转向步 6 ? 5 ? 25 ? ? ? 5 ??2 ? x2 ? ?5 ? x3 ? ?1 0? ? ? X B = ? ? ,X N = ? x 4 ? ,B= ? ? ,N= ? ?6 ?0 1? ? x1 ? ?x ? ? ? 5? ?53 -1 ? ? 17 ? ? 5? 5 5 ? CB =(3,5) ,b= ? ? ?, -1 2 ? C N =(2,-1,1) ? 6? ? ? ? 5 5? ? 5?-1 ? 5 ? ? 2 ? ? 5 ?（2）检验 X &#39;&#39; =( 6 ,0, 17 , 0, 0)T ）5 5检验向量是否最优。 是否最优。3 5 -1 5?2 ?5 -1 σ N = C N -C B B N = (2 ,-1 ,1 )-(3 ,5 ) ? ?6 ? ?5 36 4 7 -2 6 -9 -2 = (2 ,-1 ,1 )-( , , )= ( , , ) 5 5 5 5 5 5 ↑ ↑ ↑ σ2 σ4 σ5因为所有检验数均小于零， 因为所有检验数均小于零， 所以 X * =X &#39;&#39; =(6 17 81 T 是最优解， 是最优解， Z * = ,0, , 0, 0) 5 5 526表格单纯形法通过例１我们发现，在单纯形法的求解过程中，有下列重要指标： 通过例１我们发现，在单纯形法的求解过程中，有下列重要指标： 每一个基本可行解的检验向量 根据检验向量可以确定所求得的基本可行解是否为最优解。 根据检验向量可以确定所求得的基本可行解是否为最优解。 如果不 σ N = C N -C B B -1 N 是最优又可以通过检验向量确定合适的换入变量。 是最优又可以通过检验向量确定合适的换入变量。 每一个基本可行解所对应的目标函数值 通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值 Z=C B B ? 1 b 有效地增加，直至求得最优目标函数为止。 有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行 在单纯形法求解过程中， 每一个基本可行解 Ｘ都以 某个经过初等行 变换的约束方程组中的单位矩阵Ι为可行基。 变换的约束方程组中的单位矩阵Ι为可行基。 约束方程组中的单位矩阵 易知： 当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：σ N = C N -C B NZ=C B b27可将这些重要结论的计算设计成如下一个简单的表格， 可将这些重要结论的计算设计成如下一个简单的表格， 即单纯形表来完成： 即单纯形表来完成：C CB C1 C2 . . Cm Z XB X1 X2 . Xm b b1 b2 . . bm CBbCB X1 X2 ??? XmCN X m+1 Xm+2 ??? Xn θ θ1 θ2 . . θmI0NCN- CBN28试利用单纯形表求例1中的最优解解： 例2、试利用单纯形表求例1中的最优解解： maxZ=5x1 + 2x 2 + 3x 3 ? x 4 + x 5 C = ( 5 ,2 ,3 , ? 1, 1 ) =8 ? x1 + 2x 2 + 2x 3 + x 4 ?1 2 2 1 0 8? ? (Ab)= ? ? + x5 = 7 ?3x1 + 4x 2 + x 3 3 4 1 0 1 7? ? ? x ,x ,x ,x ,x ≥ 0 ? 1 2 3 4 5 得初始的单纯形表： 得初始的单纯形表： C CB -1 1 ZZ=C B b5 b 8 7 -1 x1 1 3 32 x2 2 4 03 x3 2 1 4-1 x4 1 0 01 Θ x5 0 1 0XB x4 x5σ N = C N -C B N29初始基本可行解 X = ( 0 ,0 ,0 , 8 , 7 ) T ，Z= -1，C CB -1 1 Z XB x4 x5 b 8 7 -15 x1 1 3 32 x2 2 4 03 x3 2 1 4-1 x4 1 0 01 Θ x5 0 1 0 8/2 7/1x 3 换入变量，x 4 换出变量，２为主元进行旋转变换 换入变量， 换出变量，C CB 3 1 Z XB x3 x5 b 4 3 15 5 x1 1/2 5/2 1 2 x2 1 3 -4T3 x3 1 0 0-1 x4 1/2 -1/2 -21 x5 0 1 0Θ15， 基本可行解 X = ( 0 ,0 ,4 , 0 , 3 )，Z= 15，30C CB 3 1 Z XB x3 x5 b 4 3 155 x1 1/2 5/2 12 x2 1 3 -43 x3 1 0 0-1 x4 1/2 -1/2 -21 x5 0 1 0Θ 4/1/2 3/5/2x1 换入变量，x 5 换出变量，５/２为主元进行旋转变换 换入变量， 换出变量，C CB 3 5 Z XB x3 x1 b 17/5 6/5 81/5 5 x1 0 1 0 2 x2 2/5 6/5 -26/5 3 x3 1 0 0 -1 x4 3/5 -1/5 -9/5 1 x5 -1/5 2/5 -2/5 ΘT 81 17 ? ?6 ? σ N = C N -C B N ≤ 0 最优解 X ? = ? , 0 , , 0 , 0 ?最优值 Z = 5 5 ?5 ?31例3、用单纯形方法求解线性规划问题m inZ=-x 1 -2x 2 + x3 =4 ? x1 ? x2 + x4 =3 ? ? + x5 = 8 ? x 1 + 2x 2 ? x j ≥ 0 ， j = 1,2,3,4,5 ?本题的目标函数是求极小化的线性函数， 解：本题的目标函数是求极小化的线性函数， 可以令 则Z&#39; = -Z = x1 +2x 2m inZ=-x 1 -2x 2 ? m ax Z &#39; = x 1 +2x 2这两个线性规划问题具有相同的可行域和最优解， 这两个线性规划问题具有相同的可行域和最优解， 只是目标函数相差一个符号而已。 只是目标函数相差一个符号而已。32C CB 0 0 0 Z’ 0 2 0 Z’ 0 2 1 Z’ x3 x2 x1 x3 x2 x5 XB x3 x4 x5 b 4 3 8 0 4 3 2 6 2 3 2 8T1 x1 1 0 1 1 1 0 1 1 0 0 1 02 x2 0 1 2 2 0 1 0 0 0 1 0 00 x3 1 0 0 0 1 0 0 0 1 0 0 00 x4 0 1 0 0 0 1 -2 -2 2 1 -2 00 x5 0 0 1 0 0 0 1 0 -1 0 1 -1Θ _ 3/1 8/2 4/1 2/1 2/2 3/1 -? 最优解 X = ( 2,3, 2,0,0 ) 最优值maxZ&#39; =8 or minZ=-833因为非基变量x4的检验数σ4=0，由无穷多最优解判别定理，本例 因为非基变量x 的检验数σ 由无穷多最优解判别定理， 的线性规划问题存在无穷多最优解。事实上若以x 为换入变量， 的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为 换出变量，再进行一次迭代，可得一下单纯形表： 换出变量，再进行一次迭代，可得一下单纯形表： C CB 0 2 1 Z’ XB x4 x2 x1 b 1 2 4 8 1 x1 0 0 1 0 2 x2 0 1 0 0 0 x3 1/2 -1/2 1 0 0 x4 1 0 0 0 0 x5 -1/2 1/2 0 -1 Θ最优解 X? = ( 4, 2,0,1,0 )T 最优值 最优解的一般表示式? TmaxZ&#39; =8 or minZ=-8TX = α (2,3, 2,0,0) + (1 ? α ) ( 4, 2,0,1,0) ,0 ≤ α ≤ 1.34对于极小化的线性规划问题的处理： 对于极小化的线性规划问题的处理： 先化为标准型，即将极小化问题变换为极大化问题， 先化为标准型，即将极小化问题变换为极大化问题，然后利用单 纯形方法求解． 纯形方法求解． 直接利用单纯形方法求解，但是检验是否最优的准则有所不同， 直接利用单纯形方法求解，但是检验是否最优的准则有所不同， 即： 若某个基本可行解的所有非基变量对应的检验数σ N =CN而不是≤ -C B N ≥ 0 （而不是≤０），则基本可行解为最优解． 则基本可行解为最优解． 否则采用最大减少原则（而非最大增加原则）来确定换入变量， 否则采用最大减少原则（而非最大增加原则）来确定换入变量， 即： 若min {σ j /σ j &0,m+1 ≤ j ≤ n} =σ m+k则选取对应的非基变量x 为换入变量． 则选取对应的非基变量xm+k为换入变量． 确定了换入变量以后，换出变量仍采用最小比值原则来确定。 确定了换入变量以后，换出变量仍采用最小比值原则来确定。35借助人工变量求初始的基本可行解若约束方程组含有“ 若约束方程组含有“≥”不等式，那么在化标准形时除了在方程 不等式， 式左端减去剩余变量，还必须在左端加上一个非负的人工变量。 式左端减去剩余变量，还必须在左端加上一个非负的人工变量。 因为人工变量是在约束方程已为等式的基础上， 因为人工变量是在约束方程已为等式的基础上 ， 人为的加上去 的一个新变量，因此加入人工变量后的约束方程组与原约束方程组 的一个新变量 ， 因此 加入人工变量后的约束方程组与原约束方程组 是不等价的。 是不等价的。 加上人工变量以后， 加上人工变量以后 ， 线性规划的基本可行解不一定是原线性规 划的问题的基本可行解。 划的问题的基本可行解 。 只有当基本可行解中所有人工变量都为取 零值的非基变量时，该基本可行解对原线性规划才有意义。 零值的非基变量时 ， 该基本可行解对原线性规划才有意义 。 因为此 时只需去掉基本可行解中的人工变量部分， 时只需去掉基本可行解中的人工变量部分 ， 剩余部分即为原线性规 划的一个基本可行解．而这正是我们引入人工变量的主要目的。 划的一个基本可行解．而这正是我们引入人工变量的主要目的。36考虑线性规划问题： maxZ= 考虑线性规划问题：∑c xj j=1nj? n ? ∑ a i j x j =b i ,i=1,2,...,m ? j=1 ? x ≥ 0,j=1,2,....,n ? j为了在约束方程组的系数矩阵中得到一个m 为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为 初始可行基，在每个约束方程组的左端加上一个人工变量 初始可行基，x n+i (i=1,2, ? m)可得到： 可得到：maxZ= ∑ c j x jj=1n? n ? ∑ a i j x j +x n+i =b i ,i=1,2,...,m ? j=1 ? x ≥ 0,j=1,2,....,n+m ? j37? ? n ? a i jx j +x n+i =bi ,i=1,2,...,m ? ∑ a i j x j =b i ,i=1,2,...,m ? ? j=1 ? j=1 ? x ≥ 0,j=1,2,....,n ? x ≥ 0,j=1,2,....,n+m ? j ? j ――――――――――――――――――――――――∑n添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵， 添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵， 为基变量， 以该单位矩阵对应的人工变量 x n+i (i=1,2, ? m) 为基变量， 即可得到一个初始的基本可行解X(0 )= ( 0 ,0 ,? ,0 ,b 1 ,b 2 ,? b m ) T这样的基本可行解对原线性规划没有意义的。 这样的基本可行解对原线性规划没有意义的。 但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变 但是我们可以从X 出发进行迭代， 量迭代出来，变成只能取零值的非基变量， 量迭代出来， 变成只能取零值的非基变量 ， 那么我们实际上已经求得 了原线性规划问题的一个初始的基本可行解。 了原线性规划问题的一个初始的基本可行解。 此时可以把所有人工变量剔除， 此时可以把所有人工变量剔除 ，开始正式进入求原线性规划最优 解的过程。 解的过程。38大M法 法法首先将线性规划问题化为标准型。 大M法首先将线性规划问题化为标准型。如果约束方程组中包含 有一个单位矩阵I 那么已经得到了一个初始可行基。 有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方 程组的左边加上若干个非负的人工变量， 程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向 量与其它变量的系数列向量共同构成一个单位矩阵。 量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初 始基，即可求得一个初始的基本可行解。 始基，即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解， 为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人 工变量从基变量中替换出来成为非基变量。 工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋 予人工变量一个绝对值很大的负系数予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在 人工变量，目标函数就不可能实现极大化。 人工变量，目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同， 以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数 即可。假如在单纯形最优表的基变量中还包含人工变量， 即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问 题无可行解。 题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初 始基本可行解。 始基本可行解。39用大M法求解下面的线性规划问题: 例4、用大M法求解下面的线性规划问题: 解： 首先将原问题化为标准型maxZ=-x1 +2x 2 ? x1 + x 2 ≥ 2 ? -x + x ≥ 1 ? 1 2 ? x2 ≤ 3 ? ? x1 ,x 2 &= 0 ?=2 ? x1 + x 2 -x 3 ?-x + x -x 4 =1 ? 1 2 ? x2 + x5 = 3 ? ? x j &= 0,j = 1,2,3,4,5 ?并在目标函数中分别赋予添加人工变量 x 6 ,x 7 ，并在目标函数中分别赋予-ＭmaxZ= -x1 +2x 2 -Mx 6 -Mx 7 + x6 =2 ? x1 + x 2 -x 3 ? -x + x -x 4 + x7 = 1 ? 1 2 ? x2 + x5 =3 ? ? x j &= 0,j = 1,2,3,4,5,6,7 ?40C CB -M -M 0 Z -M 2 0 Z -1 2 0 Z X1 X2 X5 X6 X2 X5 XB X6 X7 X5 b 2 1 3 -3M 1 1 2 2-M 1/2 3/2 3/2 5/2-1 X1 1 -1 0 -1 2 -1 1 1+2M 1 0 0 02 x2 1 1 1 2+2M 0 1 0 0 0 1 0 00 x3 -1 0 0 -M -1 0 0 -M -1/2 -1/2 1/2 1/20 x4 0 -1 0 -M 1 -1 1 2+M 1/2 -1/2 1/2 3/20 x5 0 0 1 0 0 0 1 0 0 0 1-M x6 1 0 0 0 1 0 0 1/2 1/2 -1/2-M x7 0 1 0 0 -1 1 -1 -1/2 1/2 -1/2θ 2/1 1/1 3/1 1/2 2/10 -2-2M -0 -1/2-M -3/2-M41C CB -1 2 0 Z 0 2 0 Z 0 2 0 Z?-1 b 1/2 3/2 3/2 5/2 1 2 1 4 2 3 1 6 X1 1 0 0 0 2 1 -1 -3 1 0 -1 -1T2 x2 0 1 0 0 0 1 0 0 0 1 0 00 x3 -1/2 1/2 1/2 -1 -1 1 2 0 0 1 00 x4 1/2 1/2 3/2 1 0 0 0 1 0 0 00 x5 0 0 1 0 0 1 0 1 1 1 -2-M x6 1/2 -1/2 1 1 -1 -2-M 0 0 -1 -M-M x7θ1/2/1/2 3/2 /1/2XB X1 X2 X5 X4 X2 X5 X4 X2 X31/2 -1/2 1/2 -1/2 -1 0 0 -M -1 0 0 -M-1/2 -1/20 -1/2-M -3/2-M最优解 X = ( 0,3,1,2,0)最优值Z? = 642两阶段法两阶段法引入人工变量的目的和原则与大M法相同， 两阶段法引入人工变量的目的和原则与大M法相同，所不同的是 处理人工变量的方法。 处理人工变量的方法。 两阶段法的步骤： 两阶段法的步骤： 求解一个辅助线性规划。目标函数取所有人工变量之和， 求解一个辅助线性规划 。 目标函数取所有人工变量之和， 并取极 小化； 小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准 型的约束条件。 型的约束条件。 如果辅助线性规划存在一个基本可行解， 如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于 则所有人工变量都已经“离基” 零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始 的基本可行解，可转入第二阶段继续计算； 的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行 可停止计算。 解，可停止计算。 求原问题的最优解。 求原问题的最优解 。在第一阶段已求得原问题的一个初始基本可 行解的基础上， 行解的基础上，继续用单纯形法求原问题的最优解43用两阶段法求解例4中的线性规划问题。 例5、用两阶段法求解例4中的线性规划问题。maxZ=-x +2x 1 2 解：首先将问题化为标准型=2 ? x1 + x 2 -x 3 ?-x + x -x 4 =1 ? 1 2 ? x2 + x5 = 3 ? ? x j ≥ 0, j = 1,2,3,4,5 ?? x1 + x 2 ≥ 2 ? -x + x ≥ 1 ? 1 2 ? x2 ≤ 3 ? ? x1 ,x 2 &= 0 ?添加人工变量x 并建立辅助线性规划如下： 添加人工变量x6,x7,并建立辅助线性规划如下：minZ=x 6 +x 7 + x6 =2 ? x1 + x 2 -x 3 ? -x + x -x 4 + x7 = 1 ? 1 2 ? x2 + x5 =3 ? ? x j ≥ 0, j = 1,2,3,4,5,6,7 ?由于辅助线性规划的目标函数 是极小化， 是极小化，因此最优解的判别 准则应为： 准则应为：σ N = C N -C B N ≥ 044C CB 1 1 0 W 1 0 0 W 0 0 0 W X1 X2 X5 X6 X2 X5 XB X6 X7 X5 b 2 1 3 3 1 1 2 1 1/2 3/2 3/2 00 x1 1 -1 0 0 2 -1 1 -2 1 0 0 00 x2 1 1 1 -2 0 1 0 0 0 1 0 00 x3 -1 0 0 1 -1 0 0 1 -1/2 1/2 00 x4 0 -1 0 1 1 -1 1 -1 1/2 1/2 00 x5 0 0 1 0 0 0 1 0 0 0 1 01 x6 1 0 0 0 1 0 0 01 θ x7 0 1 0 0 -1 1 -1 2 1/2 2/1 2/1 1/1 3/11/2 -1/2 1/2 1/2 -1/2 -1/2 1 1-1/2 -1/2辅助规划所有检验数： 辅助规划所有检验数：原问题已得一个初始基本可行解， 原问题已得一个初始基本可行解， 1 3 3 σ N = C N -C B N ≥ 0 m in W = 0 X = ( , ,0 ,0, ) 45 2 2 2由上表可知，通过若干次旋转变换， 由上表可知 ， 通过若干次旋转变换 ， 原问题的约束方程组已 变换成包含一个单位矩阵的约束方程组=2 ? x1 + x 2 -x 3 ?-x + x =1 -x 4 ? 1 2 ? x2 + x5 = 3 ? ? x j ≥ 0, j = 1,2,3,4,5 ?1 1 1 ? - x3 + x4 = ?x1 2 2 2 ? 1 1 3 ? ? x2 - x3 - x4 = ? 2 2 2 ? ? 1 1 3 x3 + x4 + x5 = ? 2 2 2 ? ? x j ≥ 0 , j = 1 ,2 ,3 ,4 ,5 ?该约束方程组可作为第二阶段初始约束方程组， 该约束方程组可作为第二阶段初始约束方程组 ， 将目标函数 则还原成原问题的目标函数，可继续利用单纯形表求解。 则还原成原问题的目标函数，可继续利用单纯形表求解。46C CB -1 2 0 Z 0 2 0 Z 0 2 0 Z?-1 b 1/2 3/2 3/2 5/2 1 2 1 4 2 3 1 6 x1 1 0 0 0 2 1 -1 -3 1 0 -1 -1T2 x2 0 1 0 0 0 1 0 0 0 1 0 00 x30 x40 x5 0 0 1 0 0 0 1 0 1 1 1 -2θ1/2/ 1/2XB X1 X2 X5 X4 X2 X5 X4 X2 X3-1/2 1/2 -1/2 -1/2 1/2 1/2 1/2 3/2 -1 -1 1 2 0 0 1 0 1 0 0 0 1 0 0 03/2/ 1/2可得最优解X = ( 0, 3,1, 2, 0 ) ，目标函数值maxZ=6， 目标函数值maxZ=6， maxZ=6 与用大M法的结果完全相同。 与用大M法的结果完全相同。47单纯形表与线性规划问题的讨论无可行解通过大Ｍ法或两阶段法求初始的基本可行解。 通过大 Ｍ 法或两阶段法求初始的基本可行解 。 但是如果在大 法的最优单纯形表的基变量中仍含有人工变量， Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的 辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存 辅助线性规划的目标函数的极小值大于零， 在可行解。 在可行解。 人工变量的值不能取零， 人工变量的值不能取零，说明了原线性规划的数学模型的约束 条件出现了相互矛盾的约束方程。 条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空 集。48例6、求解下列线性规划问题 解： 首先将问题化为标准型 令minZ=3x1 +2x 2 +x 3 ? x1 + x 2 + x 3 ≤ 6 ?x -x 3 ≥ 4 ? 1 ? x 2 -x 3 ≥ 3 ? ? x1 ,x 2 ,x 3 ≥ 0 ?Z&#39; = -Z ，则maxZ&#39; = -3x1 -2x 2 -x 3 =6 ? x1 +x 2 +x 3 +x 4 ?x -x 3 -x 5 =4 ? 1 ? -x 6 =3 ? x 2 -x 3 ? xj ≥ 0, j=1,2,? 6. ?故引入人工变量maxZ&#39; = -3x1 -2x 2 -x 3 -Mx 7 -Mx 8 =6 ? x1 +x 2 +x 3 +x 4 ?x -x 3 -x 5 +x 7 =4 ? 1 ? -x 6 +x 8 =3 ? x 2 -x 3 ? xj ≥ 0, j=1,2,?8. ?49x7 ,x8，并利用大M法求解 并利用大MC CB 0 -M -M Z’ 0 -M -2 Z’ -3 -M -2 Z’ x1 x7 x2 x4 x7 x2 XB x4 x7 x8 b 6 4 3 -7M 3 4 3 -6-4M 3 1 3 -15-M-3 x1 1 1 0-2 x2 1 0 1-1 x3 1 -1 -10 x4 1 0 0 0 1 0 0 0 1 -1 00 x5 0 -1 0 -M 0 -1 0 -M 0 -1 0 -M0 -M -M x6 x7 x8 0 0 -1 -M 1 0 -1 -2 1 -1 -1 0 1 0 0 0 0 1 0θ 6/1 3/1-3+M -2+M -1-2M 1 1 0 -3+M 1 0 0 0 0 0 1 0 0 0 1 0 2 -1 -1 -3-M 2 -3 -10 -1 1 0 0 1 0 2-M 0 -1 1 1 0 1 -13/1 4/1 -3-3M 3-M1-M 0在以上最优单纯形表中，所有非基变量检验数都小于零， 在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人 工变量x 为基变量， 工变量 7=1为基变量，所以原线性规划不存在可行解。 为基变量 所以原线性规划不存在可行解。50无最优解无最优解与无可行解时两个不同的概念。 无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解， 无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解， 无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值， 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大 或者无穷小） 无最优解也称为有限最优解，或无界解。 （或者无穷小）。无最优解也称为有限最优解，或无界解。 判别方法： 判别方法：无最优解判别定理 在求解极大化的线性规划问题过程中， 在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数， 行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零， 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解， 无最优解，σ m+k & 0B-1Pm+k ≤ 0X B =B -1 b-B -1 Pm+k x m+kZ=C B B -1 b+σ m+k x m+kx m+k 可以 → +∞Z可以→ +∞51试用单纯形法求解下列线性规划问题： 例7、试用单纯形法求解下列线性规划问题： maxZ=2x +2x 1 2 引入松弛变量x 解：引入松弛变量x3,x4化为标准型maxZ=2x1 +2x 2 ? -x1 + x 2 + x 3 = 1 ? 1 ? +x 4 = 2 ?- x1 + x 2 ? 2 ? x j ≥ 0,j = 1,2,3,4 ?C C 0 0 Z XB X3 X4 B 1 2 0 2 x1 -1 -1/2 2 2 x2 1 1 2 0 x3 1 0 0 0 x4 0 1 0? x1 - x 2 ≥ -1 ? 1 ? ?- x1 + x 2 ≤ 2 ? 2 ? x1 ≥ 0,x 2 ≥ 0 ?因 σ1 = 2&0 θ? -1 ? ? ? 1 但 P =? 1 ? ≤ 0 ?- ? ? 2?所以原问题 无最优解52退化解当线性规划问题的基本可行解中有一个或多个基变量取零值时， 当线性规划问题的基本可行解中有一个或多个基变量取零值时， 称此基本可行解为退化解。 称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时， 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时， 有时存在两个或两个以上相同的最小比值θ， 有时存在两个或两个以上相同的最小比值 ，那么在下次迭代中就会 出现一个甚至多个基变量等于零。 出现一个甚至多个基变量等于零。 遇到的问题：当某个基变量为零， 遇到的问题 ： 当某个基变量为零 ， 且下次迭代以该基变量作为换 出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可 出变量时， 目标函数并不能因此得到任何改变（ 任何一个换入变量只能仍取零值， 知 ， 任何一个换入变量只能仍取零值 ， 其它基变量的取值保持不 变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完 全相同。从几何角度来解释， 全相同。从几何角度来解释，这两个退化的基本可行解对应线性规 划可行域的同一个顶点， 划可行域的同一个顶点， 解决的办法：最小比值原则计算时存在两个及其以上相同的最小 解决的办法： 比值时，选取下标最大的基变量为换出变量， 比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一 定能避免循环现象的产生（摄动法原理） 定能避免循环现象的产生（摄动法原理）。53求解下述线性规划问题： 例8、求解下述线性规划问题：maxZ=3x1 -80x 2 +2x 3 -24x 4 ? x1 -32x 2 -4x 3 + 36x 4 ≤ 0 ? x -24x - x + 6x ≤ 0 ? 1 2 3 4 ? x3 ≤1 ? ? x j ≥ 0,j = 1,2,3,4 ?解：引入松弛变量maxZ=3x1 -80x 2 +2x 3 -24x 4 =0 ? x1 -32x 2 -4x 3 + 36x 4 + x 5 ? x -24x - x + 6x + x6 =0 ? 1 2 3 4 ? x3 + x7 = 1 ? ? x j ≥ 0,j = 1,2,3,4,5,6,7 ?54x5 ,x6 ,x7 化标准型C CB XB 第一次迭代 中使用了摄动 法原理， 法原理，选择 下标为6的基 变量x 离基。 变量 6离基。 0 0 0 Z 0 3 0 Z 0 3 2 Z?3 b 0 0 1 0 0 0 1 0 3 1 1 5 x1 1 1 0 3 0 1 0 0 0 1 0 0-80 x2 -32 -24 0 -80 -8 -24 0 -8 -8 -24 0 -8T2 x3 -4 -1 1 2 -3 -1 1 5 0 0 1 0-24 x4 36 6 0 -24 30 6 0 -42 30 6 0 -420 x5 1 0 0 0 1 0 0 0 1 0 0 00 x6 0 1 1 0 -1 1 1 -3 2 2 0 -60 x7 0 0 1 0 0 0 1 0 3 1 1 -5θ 0 0 -x5 x6 x7 x5 x1 x7 x5 x1 x3目标函数值maxZ=５， 可得最优解 X = (1,0,1,0,3) ，目标函数值 ５55无穷多最优解无穷多最优解判别原理： 无穷多最优解判别原理： 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零， 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零， 但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。 但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。 例３：最优表： 最优表： 非基变量检验 数 ， 所以有无穷多 σ4 = 0 最优解。 最优解。 C CB 0 2 1 XB x3 x2 x1 b 2 3 2 1 x1 0 0 1 2 x2 0 1 0 0 0 x3 1 0 0 0 0 x4 2 1 -2 0 0 x5 -1 0 1 -1 2/2 3/1 -θZ’ 8 0 最优解集为可行域两个顶点的凸组合： 最优解集为可行域两个顶点的凸组合：X? = α (2,3, 2,0,0)T + (1 ? α ) ( 4, 2,0,1,0) ,0 ≤ α ≤ 1.T56改进单纯形法改进单纯形法的特点利用单纯形表求解线性规划时， 利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计 算一遍，事实上我们关心的只是以下一些数据： 算一遍，事实上我们关心的只是以下一些数据： 基本可行解 X B =B -1 b ，其相应的目标函数值 非基变量检验数 σ N =C N -CB B-1 N 设 设max {σ j / σ j &0, j 为非基变量下标Z=C B B -1b ，及其换入变量 x k ，，} =σk主元列元素 B -1 Pk ，及其换出变量 x l ，? (B -1b) i ? (B ?1b) l ? -1 min ? -1 /(B Pk ) i &0, i为基变量下标 ? = ?1 ? (B Pk ) i ? (B Pk ) l ? 利用它们可得到一组新的基变量以及新的可行基Ｂ1。 利用它们可得到一组新的基变量以及新的可行基Ｂ57X B =B -1 bZ=C B B -1bσ N =C N -CB B-1 NB -1 Pk对任一基本可行解Ｘ，只要知道 任一基本可行解ＸB -1 ，上述关键数据都可以从线性规划问题的初始数据直接计算出来。 线性规划问题的初始数据直接计算出来。因此如何计算基本可行解 对应的可行基Ｂ Ｘ对应的可行基Ｂ的逆阵 成为改进单纯形法的关键． B -1 成为改进单纯形法的关键．-1 B1改进单纯形法推导出从可行基Ｂ变换到Ｂ 改进单纯形法推导出从可行基Ｂ变换到Ｂ1时， -1 到 B的变换公式。当初始可行基为单位矩阵Ι 的变换公式。当初始可行基为单位矩阵Ι时，变换公式将更具有优 越性， 越性，因为这样可以避免矩阵求逆的麻烦-1 B1 的变换公式： 的变换公式： 以下推导从 B 到 -158假设当前基 B = (P1 , P2 ,? , Pl ?1 , Pl , Pl +1 ,? Pm ) ， 基变换中用非基变量 x k 取代基变量 x l 可得新基B1 = (P1 , P2 ,? , Pl ?1 , Pk , Pl +1 ,? Pm )0? ? . ? ? 1 ?m×m?1 . B-1B = (B-1P1 , B-1P2 ,? , B-1Pl ?1 , B-1Pl , B-1Pl +1 ,? B-1Pm ) = ? . ? ? ?0 . ? 比较以上二式， 比较以上二式，可得前后二个基相比仅相差一列， 前后二个基相比仅相差一列，且B-1B1 = (B-1P1 , B-1P2 ,? , B-1Pl ?1 , B-1Pk , B-1Pl +1 ,? B-1Pm )= ( e1 ,e 2 , ? , el ?1 , B -1 Pk , el +1 , ? e m )个元素为1 其它元素均为零的单位列向量， 其中 ei表示第 i 个元素为1，其它元素均为零的单位列向量，B -1 Pk 为主元列元素。 为主元列元素。59B -1 B 1 = ( e1 ,e 2 , ? , el ?1 , B -1 Pk , el +1 , ? e m )第 l 列（换出变量x l 对应列 ）? a&#39;1k ? ? ? a&#39;2k ? ? ? ? ? -1 假设 B PK = ? ? ， ? a&#39;lk ? ? ? ? 主元素 ? ? a&#39; ? ? ? mk ?则Elk=? ?1 ? ? ? ? ? ( B - 1B 1 ) - 1 = ? ? ? ? ? ? ? ?0 ? ?? ? -a &#39;1 k a &#39; lk a &#39;2 k a &#39; lk ? 1 a &#39;l k ? ? ? ?-a &#39;m k a &#39; lk? 0? ? ? ? ? ? ? ? ? ? ? ? ? 1? ? ?第l 行所以由E lk = (B -1 B1 ) -1 = B1-1 B ? B1-1 = E lk B -160改进单纯形法的步骤根据给出的线性规划问题的标准型， （1） 根据给出的线性规划问题的标准型，确定初始基变量和初 始可行基Ｂ。求初始可行基B的逆阵Ｂ 始可行基Ｂ。求初始可行基B的逆阵Ｂ-1，得初始基本可行解 Ｂ。求初始可行基X B =B -1 b,X N = 0。-1 -1 （2）计算单纯形乘子 π=C B B ，得目标函数当前值 Z=C B B b=πb（3） 计算非基变量检验数 σ N =C N -CB B-1 N=C N -πN，≤0，则当前解已是最优解，停止计算；否则转下一步。 若σN≤0，则当前解已是最优解，停止计算；否则转下一步。 为换入变量， （4） 根据 max σ j /σ j &0 =σ k ，确定非基变量 x k 为换入变量，-1 则问题没有有限最优解，停止计算， 计算 B Pk ,若 B -1 Pk ≤0，则问题没有有限最优解，停止计算，{}否则转下一步。 否则转下一步。61? (B -1b) i ? (B -1b) l ? （5） 根据 min ? -1 /(B -1Pk ) i &0 ? = -1 ? (B Pk ) i ? (B Pk ) l ?为换出变量。 为换出变量。，确定基变量 x l-1 -1 得新基Ｂ （6） 用 P k 替代 P l 得新基Ｂ1，由变换公式 B1 = E lk B计算新基的逆阵Ｂ 计算新基的逆阵Ｂ1-1，求出新的基本可行解 为变换矩阵，构造方法是： 其中 E lk 为变换矩阵，构造方法是： 从一个单位矩阵出发， 在基B 从一个单位矩阵出发，把换出变量 x l 在基B中的对应列的单位 向量， 并做如下变形， 向量，替换成换入变量 xk对应的系数列向量 B -1 Pk ，并做如下变形， 应在主对角线上）取倒数， 主元素 a l&#39; k （应在主对角线上）取倒数，其它元素除以主元素a l&#39; k 并取相反数。 并取相反数。重复（ ）～（6 直至求得最优解。 重复（2）～（6）直至求得最优解。62①初始基 B=ImaxZ=CX ? AX=b ? ?X ≥ 0X B =B -1 b,X N = 0② π=C B B -1Z=πb③ ≤０ 最优解 σ N =C N -πN ④换入 x kmax {σ j /σ j &0} =σ kB1-1 = E lk B -1⑥新基B1换出 x l⑤≤０B-1Pk无界解? (B -1b) i ? (B -1b) l ? -1 min ? -1 /(B Pk ) i &0 ? = -1 ? (B Pk ) i ? (B Pk ) l ?63例9、试用改进单纯形法求解 解：maxZ=3x1 +2x 2 ? x1 +x 2 +x 3 =40 ? ?2x1 +x 2 +x 4 =60 ? x ,x ,x ,x ≥ 0 ? 1 2 3 4C = (3 ,2 ,0 ,0 )?1 1 1 0 ? A= ? ? 2 1 0 1? ?? 40 ? b= ? ? 60 ? ?（１）观察法确定?1 0? B0 =(P3 P4 )= ? ? 0 1? ?-1 0， x 3 ,x 4 为基变量 x1 ,x 2 为非基变量?1 0? ? 1 0 ? ? 40 ? ? 40 ? -1 B =? , X B =B0 b= ? = ? ? , X 0 = (0, 0, 40, 60)T ? ?? ? 0 1? 0 1 ? ? 60 ? ? 60 ? ? ?64C = (3 ,2 ,0 ,0 )?1 1 1 0 ? A= ? ? 2 1 0 1? ?-1 0 -1 0? 40 ? b= ? ? 60 ? ?0? ? = (0, 0) 1??1 （2）计算单纯行乘子 π 0 =C B B = (c 3 ,c 4 )B = (0, 0) ? ?0 目标函数当前值 ? 40 ? Z 0 = π 0 b = (0,0) ? ? = 0 ? 60 ?（3）非基变量检验数? 1 1? σ N =C N -π 0 N=(c1 ,c 2 )-π 0 (P1 P2 )=(3,2)-(0,0) ? ? = (3, 2) ? 2 1?m a x {σ j /σ j & 0 } = {3 ,2 } = 30??1? ?1? ?? ? = ? ? ≤ 0 1?? 2? ? 2?65(4） (4） 选择换入变量σ1 σ 2?1 为换入变量。 故 x1 为换入变量。计算 B -1P1 = ? 0 ?0C = (3 ,2 ,0 ,0 )?1 1 1 0 ? A= ? ? 2 1 0 1? ?? 40 ? b= ? ? 60 ? ?? 40 ? X B =B b= ? ? ? 60 ?-1 0?1? B -1P1 = ? ? 0 ?2?(５)确定换出变量 ? ( B 0 ?1b ) ( B 0 ?1 b ) ? ? ? 40 60 ? 60 3 4 ? =? , ?= min ? , ? B 0 ?1 P1 ) ( B 0 ?1 P1 ) ? ? 1 2 ? 2 ?( 3 4 ? ? 确定 x 4 为换出变量，主元素＝２ 为换出变量，主元素＝-1 ? -1 ? ? ? 1 1 ? 2 ??1 0? =? 2? -1 -1 B1 = E 41B0 = ? ?? ? ? ? ? 0 1 ?? 0 1 ? ? 0 1 ? ? ? ? ? ? 2? ? 2?重复以上步骤， 重复以上步骤，进入第二循环?1 (6) 用 P1 代替 P 4 得新可行基 B1 =(P3 ,P1 )= ? ?01? 为基变量， ? x 3 ,x1 为基变量， 2?x 2 ,x 4 为非基变量， 为非基变量，?1 ? ?00? ?→ 1??1 ? ?01? ?→ 2?? ?1 ? ? ?0 ?66-1 ? ? 2? 1? ? 2?C = (3 ,2 ,0 ,0 )?1 1 1 0 ? ? 40 ? A= ? ? b= ? ? 2 1 0 1? 60 ? ? ??1 B1 =(P3 ,P1 )= ? ?0 1? ? 2?-1 ? ? 1 ? 2? -1 B1 = ? ? ?0 1 ? ? ? ? 2??1 (1) -1 X B =B1 b= ? ?0 ? ?? 10 ? = ? ? , X 1 = (30, 0,10, 0) T ? 30 ? ?1 ? ? ?1 2 ? (2) 3 -1 -1 π1 =C B B1 = (c 3 ,c1 )B1 = (0, 3) ? ? = (0, ) 2 ?0 1 ? ? ? ? 2 ? 3 ? 40 ? Z1 = π1b = (0, ) ? ? = 90 2 ? 60 ?(3)?1 ? 2 ? ? 40 ? 1 ? ? 60 ? ?? ? 2 ?3 ?1 0 ? 1 3 σ N =C N -π1 N=(c2 ,c4 )-π1 (P2 P4 )=(2,0)-(0, ) ? ? =( , - ) 2 ?1 1 ? 2 2σ2 σ467C = (3 ,2 ,0 ,0 )?1 1 1 0 ? ? 40 ? A= ? ? b= ? ? 2 1 0 1? 60 ? ? ??1 B1 =(P3 ,P1 )= ? ?0? 10 ? 1? -1 ? X B =B1 b= ? 30 ? 2? ? ??1 ? ?0 ↓ ?1 ?2 ? ?1 ? ?2 ? 0? ? 1? ? ? 0? ? 1??1 ? ? ?1? ? 1 2 ? ?1? ? 2 ? (4) 选择 x 2 换入变量 -1 B1 P2 = ? ?? ? = ? ? ≤ 0 ? 0 1 ? ?1? ? 1 ? ? ? ? ? ? 2 ? ?2? ? ( B1 ? 1 b ) ( B1 ? 1 b ) ? ? ? 10 30 ? 10 3 1 ? min ? , =? , ? ?= (5) ?1 ?1 ? ( B1 P2 )3 ( B1 P2 )1 ? ? 1 / 2 1 / 2 ? 1 / 2 ? ?-1 换出变量,主元素＝ 选择 x 3 换出变量,主元素＝ (B1 P2 ) 3 =?1 1 ? ↓ x 2 ,x1 (6) 用 P2 代替 P3 得新可行基 B 2 =(P2 ,P1 )= ? 1 2 ? ? ? 为基变量， 为基变量， ? 2 0 ? -1 ? ? 1 x 3 ,x 4 为非基变量，? 为非基变量， -1 1 ? ? 2 0?? 2 ? ? 2 -1 ? -1 -1 ? ? B 2 = E 32 B1 = ? ?=? ?? ? ? ?1 1 ? ? 0 1 ? ? -1 1 ? 进入第三循环. 进入第三循环. ? ? 68 ? 2?1 2C = (3 ,2 ,0 ,0 )?1 1 1 0 ? ? 40 ? A= ? ? b= ? ? 2 1 0 1? 60 ? ? ?(1) X =B -1 b= B 2 ??1 1 ? B 2 =(P2 ,P1 )= ? ? 1 2? ?? 2 -1? B =? ? -1 1 ? ?-1 2? 1 ? ? 40 ? ? 20 ? = ? ? , X 2 = (20, 20, 0, 0) T ?? ? 1 ? ? 60 ? ? 20 ? ? 2 ?1 ? (2) -1 -1 π 2 =C B B 2 = (c 2 ,c1 )B 2 = (2, 3) ? ? = (1, 1) ? ?1 1 ? ? 40 ? Z 2 = π 2 b = (1,1) ? ? = 100 ? 60 ? ?1 0? (3) σ N =C N -π 2 N=(c3 ,c 4 )-π 2 (P3 P4 )=(0,0)-(1,1) ? ? =(-1, -1) ?0 1? ? 2 ? ?1非基变量对应的检验数全部非正， 非基变量对应的检验数全部非正， 即为最优解， 故当前解 X 2 =X * =(20, 20, 0, 0) T 即为最优解， 相应的目标函数最优值σ3 σ4maxZ = 100。69
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。