经贸院基础知识回顾.ppt

《经贸院基础知识回顾.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、线性规划基础知识回顾1第1章、线性规划与单纯形法—回顾1、线性规划的特点目标函数和约束条件均是线性关系。2、解决的主要问题在给定的条件下，按照某一衡量指标来寻找最优方案。3、解决方法图解法和单纯形法。22.1线性规划的标准形式目标函数：约束条件：目标系数决策变量技术系数右端项3线性规划的矩阵表示方式41、minZ=CX—>maxZ=-CX2、约束条件为“≤”—>转换为“=”方法：在s.t.中左端加上一个“松弛变量”，使“≤”变为“=”。同时，在目标函数中，令松弛变量的目标系数为0。3、约束条件为“≥”—>转换为“

2、=”方法：在s.t.中左端减去一个“剩余变量”，使“≥”变为“=”。同时，在目标函数中，令剩余变量的目标系数为0。2.2非标准形式的标准化方法54、决策变量xi≤0—>xj=-xi5、决策变量的符号不受限制—>xj=xj’-xj’’，xj’，xj’’≥0.6、决策变量有上下界，即a≤xi≤b。（1）令xj=xi-a，则0≤xj≤b-a。（2）用xj替换目标函数和s.t.中所有的xi；（3）将xj≤b-a作为新的约束条件，列入原有s.t.中；（4）采用添加“松弛变量”的方法来标准化xj≤b-a约束。6例子x3’=x

3、3-271、线性规划解法的问题（1）标准数学模型中，有n个未知数（决策变量），m个约束方程，一般m≠n，且常有m

4、向量可能有很多，则每组基变量不同，那么目标函数值也不同，如何寻求最优解？2.3单纯形法82、单纯形法的解题步骤例：（P17）9步骤一：将非标准型的线性规划变化为标准型线性规划。标准型线性规划10步骤二：建立初始单纯形表。cj—>c1c2c3c4c5c6θiCBXBbx1x2x3x4x5x6对应的目标系数基变量符号变化后的右端项约束方程中的技术系数Zδj目标函数值目标系数值检验数2检验数单纯形表11cj—>230000θiCBXBbx1x2x3x4x5x6221000120100400010040001Zδj初始单

5、纯形表的建立（1）将技术系数矩阵和目标系数矩阵的数据填入，完善单纯形表。在后续的变化中，两者将保持恒定。12cj—>230000θiCBXBbx1x2x3x4x5x6221000120100400010040001Zδj初始单纯形表的建立（2）确定初始基变量XB。原则：一般选择技术系数矩阵中的单位列向量作为初始基，与之对应的几个决策变量为初始基变量，其余为非基变量。并将基变量的符号写入XB列中；（3）确定CB。与XB对应的目标系数值，填入CB列；（4）b的确定。将初始右端项填入b列；（5）计算Z值。基变量的解=b

6、列对应的值。x3x4x5x600001281612013步骤三：校验基变量是否最优？规则：判断δｊ＝cｊ－∑CBi×aij≤0，如是，则表示最优，否则需要进行基变量的更换。δｊ＝cｊ－∑CBi×aijcj—>230000θiCBXBbx1x2x3x4x5x6221000120100400010040001Zδjx3x4x5x6000012816120检验数计算技巧：（1）每个变量对应一个检验数；（2）xj检验数=xj目标系数-xj对应的列向量与CB列值依次相乘后的和。23000014步骤四：基变量的更换规则：（1

7、）基变量的换入（选择一个基变量来取代初始的基变量）：max{δj

8、δj>0}=δk，即选择δj>0数值中的最大值，其所在的列为换入基向量。此时，此列被称为主元列Pk。δｊ＝cｊ－∑CBi×aijcj—>230000θiCBXBbx1x2x3x4x5x6221000120100400010040001Zδjx3x4x5x6000012816120230000δk2204换入基向量15步骤四：基变量的更换规则：（2）基变量的换出（从原始基变量中选择一个，取出）：min{θi=bi/aik

9、aik>0}=θl，即选择θ

10、i数值中的最小值，其所在的行对应的变量为换出基变量。此时，此行被称为主元行Pl。Pk和Pl交汇元素为主元素。cj—>230000θiCBXBbx1x2x3x4x5x6221000120100400010040001Zδjx3x4x5x600001281612023000064-3θi计算技巧：初始基变量对应的θi=右端项b除以换入基变量所在的列的对应值。min{θi=bi