对偶理论和灵敏度分析.pptx

1第二章对偶理论和灵敏度分析一、单纯形法的矩阵描述CjC1C2……………Cj………….CnCBXBbx1x2…xj…xnxB1xB2…xBnb1b2...bna11a12…a1j…a1na21a22…a2j…a2n…an1an2…anj…ann检验数?j

2添加标题设线性规划问题:01添加标题约束条件AX≤b;03添加标题目标函数maxz=CX;02添加标题非负条件X≥004

3maxz=CX+0Xs;AX+IXs=b;X，Xs≥0这里I是m×m单位矩阵。给这线性规划问题的约约束条件加入松弛变量以后，得到标准型：

4初始单纯形表和最终单纯形矩阵表示如下:第二章对偶理论和灵敏度分析CjCNCB00XSbXNXBXSXSbNBI检验数?jCjCNCB0CBXBbXNXBXSXBB-1bB-1NBB-1B-1检验数?jCN-CBB-1N-CBB-1

5令非基变量=0；由上式得到：

65%55%30%10%改进单纯形法以下介绍一种比较简便的计算方法求解线性规划问题的关键是计算设m?m系数矩阵A，求其逆矩阵。

7A可以先从第1列开始单击此处添加小标题B以为主元素,进行变换单击此处添加小标题

*融资项目商业计划书单击此处添加副标题

9然后构造含有（1）列，而其他列都是单位列的矩阵

10可得到：

而后以第2列的为主元素，进行变换*融资项目商业计划书单击此处添加副标题

然后构造含有（2）列，而其他列都是单位列的矩阵*添加标题单击此处添加副标题

可得到*融资项目商业计划书单击此处添加副标题

重复以上的步骤，直到获得*融资项目商业计划书单击此处添加副标题

15A求单纯形表的基矩阵的逆矩阵也可以用这方法单击此处添加小标题B例：用改进单纯形法求解线性规划问题：单击此处添加小标题

16

第1步：确定初始基，初始基变量;确定换入，换出变量。

（1）确定初始基和初始基变量：

17（2）计算非基变量的检验数，确定换入变量。

(3)确定换出变量计算：表示选择0的元素*融资项目商业计划书单击此处添加副标题

（4）基变换计算将新的基单位矩阵。计算：*添加标题单击此处添加副标题

（5）计算非基变量的系数矩阵*融资项目商业计划书单击此处添加副标题

（6）计算RHS*添加标题单击此处添加副标题

第1步计算结束后的结果*融资项目商业计划书单击此处添加副标题

第2步重复第1步的计算步骤从新的基，基变量开始。*添加标题单击此处添加副标题

计算非基变量的检验数，确定换入变量。*融资项目商业计划书单击此处添加副标题

(3)确定换出变量计算：表示选择0的元素*融资项目商业计划书单击此处添加副标题

*融资项目商业计划书单击此处添加副标题

计算RHS*融资项目商业计划书单击此处添加副标题

第2步计算结束后的结果*融资项目商业计划书单击此处添加副标题

29第3步从新的基，基变量开始,

重复第1步的计算步骤.

30计算非基变量检验数，检查检验数，确定换入变量

(3)确定换出变量计算：表示选择0的进行计算*融资项目商业计划书单击此处添加副标题

新的基*融资项目商业计划书单击此处添加副标题

33计算B逆矩阵

*融资项目商业计划书单击此处添加副标题

计算非基变量的检验数*融资项目商业计划书单击此处添加副标题

最优解*融资项目商业计划书单击此处添加副标题

目标函数的值*融资项目商业计划书单击此处添加副标题

38第二章对偶理论和灵敏度分析若第一章中例