运筹学全套配套课件朱道立 ch04.ppt

《运筹学全套配套课件朱道立 ch04.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求：第四章线性规划进一步讨论进一步了解线性规划的基本原理了解线性规划在计算中的一些问题了解线性规划方法的某些推广目录退化问题及反退化方法改进单纯形法线性参数规划及其应用运输问题运用Excel求解运输问题目录退化问题及反退化方法改进单纯形法线性参数规划及其应用运输问题运用Excel求解运输问题退化问题x2x1退化问题死循环！x2x1定义4.1：如果线性规划问题存在一基本可行解，其中至少有一分量为零时，则称该问题为退化的。反退化问题——字典排序规则000-3/420-1/26bi/yiBx1x

2、2x3x4x5x6x70X101001/4-8-1900X200101/2-12-1/2300X310010010000-3/420-1/26最小值不唯一！用第一列代替常数项列得到主元素，第二行出基。X4进基基变换！目录退化问题及反退化方法改进单纯形法线性参数规划及其应用运输问题运用Excel求解运输问题改进单纯形法的计算步骤1．确定，计算。2．计算单纯形乘子。3．若是非基变量，计算判别数。若所有，则已达到最优解，结束。若存在，则取作为进基变量并转4。4．计算，。若，则问题无界。计算下式：则退出以取代

3、转1。若矩阵A中零元素的密度较大或A的行数比列数小的多时，它比单纯形的运算量要少的多。目录退化问题及反退化方法改进单纯形法线性参数规划及其应用运输问题运用Excel求解运输问题线性参数规划当目标函数的系数沿某一方向连续变化时，其参数规划形式是：其中为原线性规划问题的价值向量，为变动向量,2.当约束条件的右端项连续变化时，其参数线性规划的形式是：其中为原线性规划问题的资源向量，为变动向量，为参数。为参数。某文教用品厂利用白坯纸生产稿纸、日记本和练习本。该厂现有工人100人，每天白坯纸供应量为30000千

4、克。如单独生产各种产品，每个工人每天可生产稿纸30捆/日记本30打/练习本30箱。已知原材料消耗为：每捆稿纸用白坯纸千克，每打日记本用白坯纸千克，每箱练习本用白坯纸千克。已知生产各种产品的盈利为每捆原稿纸1元，每打日记本2元，每箱练习本3元。试求：（1）现有生产条件下使盈利最大的方案；（2）如白坯纸供应量不变，而工人不足时可以从市场上招收临时工，临时工费用为每人每天15元。问该厂是否应招收临时工？招多少最好？应用举例该厂每天生产原稿纸x1捆，日记本x2打，练习本x3箱。又用表示该厂招收的临时工数。目录

5、退化问题及反退化方法改进单纯形法线性参数规划及其应用运输问题运用Excel求解运输问题运输问题的提出某公司现将产品从三个工厂A1、A2、A3运往四个分销中心B1、B2、B3、B4。三个工厂的生产能力、四个分销中心的预测需求以及从三个工厂运往四个分销中心单位运输成本见下表。现在的问题是，决定使用哪些路线，并且每条路线分别运送多少货物可以使总运输成本达到最小。B1B2B3B4工厂生产能力A132765000A275236000A325452500分销中心需求600040002000150013500单位运

6、输成本供给=需求一般运输问题的基本原则最小化所有运输费用之和供给=需求产品是离散计量的要求运输量是整数个单位产品线性约束运输问题的一般模式目标函数供给约束需求约束非负约束运输问题的求解方法计算过程：1．寻找初始可行解；2．检查是否已达到最优。若已是最优或无可行解，则结束；3．进一步改善目前的解；寻找初始可行解的方法（1）西北角方法；（2）最小元素法。某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足

7、各销售点的需求量的前提下，使总运费为最小。产销平衡和单位运价表销地单位运费产地B1B2B3产量A151612A224014A33674销量91011运输问题例子求平衡运输问题初始解方法—西北角方法B1B2B3产量A112A214A34需求量9101130西北角方法求初始解615024367B1B2B3产量A112A214A34需求量91011306150243677477307090304000初始解求平衡运输问题初始解方法—西北角方法B1B2B3产量A112A214A34需求量9101130西北角方

8、法61502436773794其余为0。总运费=9*5+3*1+7*4+7*0+4*7=104（元）求平衡运输问题初始解方法—最小元素法B1B2B3产量A112A214A34需求量9101130最小元素法求初始解615024367B1B2B3产量A112A214A34需求量910113061502436711031003064022020初始解求平衡运输问题初始解方法—最小元素法B1B2B3产量A121012A231114A344需求量9101130最小