管理运筹学复习.ppt

《管理运筹学复习.ppt》由会员分享，可在线阅读，更多相关《管理运筹学复习.ppt（39页珍藏版）》请在三一办公上搜索。

1、管理运筹学复习,马昌谱,2,线性规划问题,线性规划主要解决有限资源的最佳分配问题决策变量决策变量的取值要求非负。约束条件存在一组决策变量构成的线性等式或不等式的约束条件。目标函数存在唯一的线性目标函数（极大或极小）。求解方法：图解法单纯形解法,3,线性规划的一般模型,例1.生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。,线性规划模型的构建,4,线性规划的一般模型,(1)决策变量：设x1为甲产品产量，x2为乙产品产量。(2)约束条件：A车间能力约束 x1 8 B车间能力约束 2x2 12

2、C车间能力约束 3x1+4 x2 36(3)目标函数：maxZ=3x1+5 x2(4)非负约束：x1 0，x2 0线性规划数学模型为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0,建立模型,5,某厂生产甲、乙、丙三种产品，已知有关数据如下表所示,6,目标规划 建模,某工厂计划生产A、B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。厂长首先考虑要充分利用供电部门分配的电量限额66，然后考虑利润不低于100元；据市场调查结果，希望B产品的产量不低于A产品的产量，问应如何制定产品A、B的产量。,7,目标规划,解：设x1、

3、x2分别表示A、B两种产品的产量，则目标规划模型如下：minZ=P1(d1-+d1+)+P2d2-+P3d3-2x1+x2 8 10 x1+12x2+d1-d1+=66 10 x1+20 x2+d2-d2+=100-x1+x2+d3-d3+=0 x1,x2,d1-,d1+,d2-,d2+,d3-,d3+0,题例：,一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过68

4、0工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。试求如何安排生产？,8,9,10,线性规划标准型,标准型,目标函数极大化，约束条件为等式，右端常数项bi0，决策变量非负。,简记,11,线性规划标准型,目标函数极小化问题只需将目标等式两端乘以-1 即变为极大化问题。右端常数项非正将约束等式两端同乘以-1约束条件为不等式当约束方程为“”时，左端加入一个非负的松弛变量；当约束条件为“”时，不等式左端减去一个

5、非负的剩余变量(也可称松弛变量)即可。决策变量xk没有非负性要求 令xk=xk-x k，xk=xk，x k 0，用xk、x k 取代模型中xk,非标准型向标准型转化,12,线性规划解的概念,基m个线性无关的约束方程，称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。基变量与基向量Pj相对应的m个变量xj称为基变量其余的m-n个变量为非基变量。,线性规划解的概念,基解令所有非基变量等于零，求出基变量的值，基解是各约束方程及坐标轴之间交点的坐标。基可行解：满足非负性约束的基解。最优基：最优解对应的基矩阵，称为最优基。,13,表格单纯形法,maxZ=3x1+5 x2+0 x3

6、+0 x4+0 x5=0 x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36,单纯形法计算,14,表格单纯形法,最优解:X*=(4,6,4,0,0)T，Z*=42,15,表格单纯形法,最优基,最优基的逆,最优基和最优基的逆,扩展题,16,17,18,对偶理论,对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=42,例1的对偶问题的数学模型,19,对偶理论,这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。若原问题的价值系数Cj表示单

7、位产值，则yi 称为影子价格。若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。对资源i总存量的评估：购进 or 出让对资源i当前分配量的评估：增加 or 减少,对偶问题的经济解释,灵敏度分析,20,最优单纯形表为：,21,(1)求出a、b、c 的值；（2）写出此线性规划的最优解、最优基 B 和它的逆 B-1；(3)求此线性规划的对偶问题及其最优解；(4)试求 c2 在什么范围内，此线性规划的最优解不变；(5)若 b1=20 变为 45，最优解及最优值是什么？

8、,22,整数规划重点掌握匈牙利算法,指派问题,23,2023年9月28日星期四,【题例】某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如表5-35所示求最优生产配置方案,【解】问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有,指派问题assignment problem,2023年9月28日星期四,第二步：找出矩阵每列的最小元素，再分别从每列中减去，有,指派问题assignment problem,2023年9月28日星期四,第三步：用最少的直线覆盖所有“0”，得,第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算从矩阵

9、未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k5直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵,指派问题assignment problem,第四步等价于第2、3行减去5，同时第1列加上5得到的结果,2023年9月28日星期四,第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素容易看出4个“0”的位置,(),(),(),(),或,(),(),(),(),指派问题assignment problem,2023年9月28日星期四,得到两个最优解,有两个最优方案第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工

10、厂加工产品2；第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；单件产品总成本Z5815025055513,指派问题assignment problem,2023年9月28日星期四,【题例】求表56所示的运输问题的初始基可行解。,表56,运输单纯形法 Transportation Simplex Method,2023年9月28日星期四,表57,【解】,30,15,10,25,20,5.2 运输单纯形法 Transportation Simplex Method,2023年9月28日星期四,【例】求表5-10给出的运输问题的初始基本可行解,表5-

11、10,5.2 运输单纯形法 Transportation Simplex Method,2023年9月28日星期四,表5-11,【解】,5,10,0,15,10,10,5.2 运输单纯形法 Transportation Simplex Method,2023年9月28日星期四,初始基本可行解可用下列矩阵表示,表511中，基变量恰好是3+41=6个且不包含闭回路，是一组基变量，其余标有符号的变量是非基变量,5.2 运输单纯形法 Transportation Simplex Method,2023年9月28日星期四,【例】用左上角法求例5.3中表5-6的初始基本可行解,表5-17,30,30,15

12、,15,10,35,最短路与最小树,题例：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,题例2：某驾驶员要将一批货物从v1运输到v8，问该驾驶员应如何选择路线才能使得线路最短？下图给出了两地间的交通图。权数表示两地间公路的长度（单位：公里）,2023年9月28日星期四,存储论,题例：某工厂生产载波机需电容元件，正常生产每日需600个，每个存贮费 C1=0.01 元/周，订购费每次为 C3=50 元，问：经济订货量为多少？一年订购几次？(一年按 52 周计)，一年的存贮费和订购费各是多少？若订货提前期为2天，订货点是多少？,2023年9月28日星期四,解：以周为时间单位，每周按 5 天计，则 D=5600=3000个/周由公式得：,不考虑安全储备的情况下，订货点为：600*2=1200（个）即每当库存量下降到1200个时，就提出订货5477个。,