运筹学 1线性规划(20090907).ppt

1、1-0线性规划(简介)线性规划的创始人：美国g.b .丹增于1947年，线性规划(简介)线性规划的创始人：美国G.B .但泽于1947年提出了Simpler，线性规划(简介)线性规划的创始人：美国G.B .但泽于1947年提出Simpler，丹增于1963年写了线性规划与扩展。线性规划(简介)线性规划的创始人：美国人丹增于1947年提出了更简单的方法，1963年提出了线性规划和扩展，1979年提出了椭球方法。线性规划(简介)线性规划创始人：1947年，美国G.B .但泽于1951年提出了更简单的方法，丹增于1963年提出了“线性规划与扩展”，苏联的卡奇安于1979年提出了“椭球法”，印度的卡尔

2、马卡尔于1984年提出了“投影梯度法”，线性规划(简介)线性规划创始人：1947年，美国G.B .但泽于1951年提出了更简单的方法，丹增于1963年提出了“线性规划与扩展” 印度的卡尔马卡尔在1984年提出“投影梯度”，线性规划是研究线性不等式或凸多面体(在高维空间)的理论，是线性代数的应用和发展。 线性规划(简介)线性规划的创始人：1947年，美国人G.B .但泽提出了Simpler，1951年，丹增写了“线性规划与扩展”，1963年，苏联的卡奇安提出了“椭球方法”，1979年，印度的卡尔马卡尔提出了“投影梯度”，1984年，线性规划是研究线性不等式或凸多面体(在高维空间)的理论，是线性代

3、数的应用和发展。1-1线性规划生产计划的基本概念如何合理使用有限的人力、物力和资金，以获得最佳的经济效益。如何合理利用有限的人力、物力和资金，以最经济的方式满足生产计划的要求。生产计划问题胜利家具厂生产两种家具：桌子和椅子。桌子每张卖50元，椅子每张卖30元。桌椅的生产需要木工和油漆工。木匠制作一张桌子需要4个小时，油漆工需要2个小时。木匠需要3个小时，油漆工需要1个小时来制作椅子。这家工厂每个月可以做120个小时的木工活和50个小时的油漆工。询问工厂如何组织生产以最大化每月销售收入。将实际问题转化为线性规划模型有几个步骤。将实际问题转化为线性规划模型有几个步骤。解决方案：将实际问题转化为线性

4、规划模型有以下步骤：1 .确定决策变量：x1=生产的桌子数量x2=生产的椅子数量2。确定目标函数：家具厂的目标是最大化销售收入max z=50 x1 30 x2。解决方案：将实际问题转化为线性规划模型有以下步骤：1 .确定决策变量：x1=生产的桌子数量x2=生产的椅子数量2。确定目标函数：家具厂的目标是最大化销售收入max z=50 x1 30 x2 3。确定约束条件：4x1 3x2 120(木工时限)2x1 x2 50(油漆工时限)。解决方案：将实际问题转化为线性规划模型有以下步骤：1 .确定决策变量：x1=生产的桌子数量x2=生产的椅子数量2。确定目标函数：家具厂的目标是最大化销售收入ma

5、x z=50 x1 30 x2 3。确定约束条件：4x1 3x2 120(木工时间限制)2x1 x2 50(油漆工时间限制)4个变量限制：一般来说，决策变量只取正值(非负值)X10和X20。解决方案：将实际问题转化为线性规划模型有以下步骤：1 .确定决策变量：x1=生产的桌子数量x2=生产的椅子数量2。确定目标函数：家具厂的目标是最大化销售收入max z=50 x1 30 x2 3。确定约束条件：4x1 3x2120(木工时间限制)2x1 x2 50(油漆工时间限制)4个变量值限制系统：一般来说，决策变量只取正值(非负值)x1 0，x2 0，而数学模型Max S=50x 130 x2s . t

6、 . 4x 13x 21202 x 1 x250x 1，X20线性规划数学模型有三个元素：决策变量，约束条件，目标函数，1-2线性规划问题的数学模型示例12营养配餐问题假设成人每天都需要食物。如果市场上只有四种食物可供选择，它们每公斤的卡路里和营养含量以及市场价格如下表所示。如何在满足营养的前提下选择最小化购买食品的成本？各种食物的营养成分表，解决方案：让xj为j食物的日购买量，餐饮问题的线性规划模型为：最小s=141 62 3324s . t . 100018002 9003 2004 3000 501602 203 104 55 40012002 3003 5004 8001，x2，x3，

7、x4 0，其他典型问题：理性切割，运输，生产组织与计划，投资组合，其他典型问题运输、生产的组织和计划、投资组合的分配、生产过程的优化、成功决策的例子：美国航空公司关于哪架飞机用于哪一次飞行和哪一名机组人员安排在哪架飞机上的决策，成功决策的例子：美国航空公司关于哪架飞机用于哪一次飞行和哪一名机组人员安排在哪架飞机上的决策， 美国国防部关于如何从一些现有基地运送海湾战争所需的人员和物资的决定，成功决策的例子：美国航空公司关于哪架飞机用于哪次飞行和哪些机组人员安排在哪架飞机上的决定，美国国防部关于如何从一些现有基地运送海湾战争所需的人员和物资的决定， 切斯路系统公司购买和维修价值40亿美元的货车的决

8、策，成功决策的例子：魁北克水利部门决定使用哪些水库来满足日常电力需求，魁北克水利部门决定使用哪些水库来满足日常电力需求。 农业信贷系统联邦土地银行决定如何支付到期债券以及发行多少新债券以获得维持发展所需的资金(每年总计60亿美元)。成功决策的例子：魁北克水利部门决定使用哪些水库来满足日常电力需求，农业信贷系统，联邦土地银行决定如何支付到期债券和出售多少新债券以获得资金(每年总计60亿美元)来维持发展决策，北美长途运输公司决定如何每周调度数千辆卡车。成功决策的例子：魁北克水利部门决定使用哪些水库来满足日常电力需求；农业信贷系统；联邦土地银行决定如何支付到期债券以及应该出售多少新债券以获得维持发展

9、的资金(每年总计60亿美元)；北美长途运输公司决定如何每周调度数千辆卡车；埃克森炼油厂决定调整冶炼能力，以适应无铅燃料生产的法律变化。成功决策的例子：魁北克水利部门决定使用哪些水库来满足日常电力需求；农业信贷系统；联邦土地银行决定如何支付到期债券以及应该出售多少新债券以获得维持发展的资金(每年总计60亿美元)；北美长途运输公司决定如何每周调度数千辆卡车；埃克森炼油厂决定调整冶炼能力以适应无铅燃料生产的法律变化线性规划问题的一般形式是最大(最小)s=c1x1c2x2.a11x1a12x2.a1nxn (=，)b1a21x1a22x2.a2nxn (=，)B2 . am1x 1 a2 x2 . a

10、mxn(=，)bmx1，x2.xn0，线性规划问题的隐含假设：比例假设：决策变量的变化引起的目标函数的变化与决策变量的变化成正比。类似地，由每个决策变量的变化引起的约束方程左端值的变化与该变量的变化成正比。线性规划问题的隐含假设：比例假设：决策变量的变化引起的目标函数的变化与决策变量的变化成正比。类似地，由每个决策变量的变化引起的约束方程左端值的变化与该变量的变化成正比。可加性假设：每个决策变量对目标函数和约束方程的影响独立于其他变量，目标函数值是每个决策变量对目标函数的总贡献。线性规划问题的隐含假设：连续性假设：线性规划问题中的决策变量应该取连续值。线性规划问题的隐含假设：连续性假设：线性规

11、划问题中的决策变量应该取连续值。确定性假设：线性规划问题中的所有参数都是确定的参数。线性规划不包含随机因素。线性规划问题的隐含假设：比例假设、可加性假设、连续性假设、确定性假设、线性规划问题的1-3解的概念、(二维)线性规划问题的图解法：(1)满足约束的变量值称为可行解。(二维)线性规划问题的图解法：(1)满足约束的变量值称为可行解。(2)使目标函数获得最优值的可行解称为最优解。(二维)线性规划问题的图解法：(1)满足约束的变量值称为可行解。(2)使目标函数获得最优值的可行解称为最优解。示例1.1的数学模型是max s=50x 130 x2s . t . 4x 13 x 21202 x 1 x

12、250 x 1，x20、x2、50、40、30、20、10、20、30、40、x1、4x1 3x2 12 0 x1 0 x2 0，最大s=50x 130 x2s . t . 4x 13 x 21202 x1 250 x1，x2 0，x2，50，40，30，20，1 0，10，20，30，30由2x1 x2 50 x1 0，x2 0，最大s=50x 130 x2st . 4x 13 x 21202 x1 250 x1，x20，x2，50包围的区域该问题的可行域是一个凸多边形，其顶点为0、Q1、Q2和Q3、x2、50、40、30、20、10、10、20、30、40、x1、可行域、目标函数是一个以S

13、为参数的集合30、20、10、10、20、30、40、X1、可行域，当S的值连续增加时，直线x2=S/30-(5/3)x1沿其法线向右上方移动，x2，50，40，30，20，10，10，20，30，40，x1，可行域，当直线移动到Q2时，s(目标函数)的值达到最大值：Max s=50 * Max z=x1 3 x2 s . t . x1 x26-x1 2x 28 x1 0，x20，可行域，目标函数的等值线，最优解，6，4，-8，6，0，x1，x2，两个重要结论：满足约束条件的可行域这个事实可以扩展到更多的可变情况。两个重要结论：满足约束条件的可行域通常构成凸多边形。这个事实可以扩展到更多的可变情况。在凸多边形的某个顶点上可以得到最优解的事实也可以推广到更多的