运筹学第二章.ppt

运筹学第二章.ppt运筹学
成都信息工程学院
应用数学学院
梅志红
******@cuit.
2017/12/10
1
Chapter2 单纯形法
单纯形法的基本思想
单纯形法的计算过程
人工变量法
单纯形法补遗
本章主要内容:
2017/12/10
2
单纯形法(Simplex Method)是美国人丹捷格()1947年创建的
这种方法简捷、规范,是举世公认的解决线性规划问题行之有效的方法。
单纯形法的表现形式:
代数法
表格法
矩阵法
单纯形法的求解线性规划问题, 解决了三个技术问题:⑴给出第一个基可行解; ⑵检验一个基可行解是否是最优解; ⑶转换到另一个基可行解。
2017/12/10
3
Mathematical experiment
:
一般线性规划问题具有线性方程组的变量数大于方程个数,这时有不定的解。但可以从线性方程组中找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小,决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。
2017/12/10
4
Mathematical experiment
2017/12/10
5
Mathematical experiment
例1 试以例1来讨论如何用单纯形法求解。例1的标准型为:
2017/12/10
6
Mathematical experiment
约束方程(1-12)式的系数矩阵
从(1-12)式中可以看到x3,x4,x5的系数列向量
2017/12/10
7
Mathematical experiment
P3 ,P4,P5是线性独立的,这些向量构成一个基  对应于B的变量x3,x4,x5为基变量.
从(1-12)式中可以得到(1-13)
2017/12/10
8
Mathematical experiment
将(1-13)式代入目标函数(1-11)
得到
当令非基变量x1=x2=0,便得到z=0。这时得到一个基可行解X(0)
X(0)=(0,0,8,16,12)T
这个基可行解表示:工厂没有安排生产产品Ⅰ、Ⅱ;资源都没有被利用,所以工厂的利润指标z=0。
2017/12/10
9
Mathematical experiment
从分析目标函数的表达式(1-14)可以看到
非基变量x1,x2(即没有安排生产产品Ⅰ,Ⅱ)的系数都是正数,因此将非基变量变换为基变量,目标函数的值就可能增大。从经济意义上讲,安排生产产品Ⅰ或Ⅱ,就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量,这表示目标函数值还有增加的可能,就需要将非基变量与基变量进行对换。
2017/12/10
10
Mathematical experiment