1、二、线性规划与目标规划二、线性规划与目标规划（概论）（概论） 线性规划（线性规划（ Linear Programming)创始人：创始人：1947年美国人丹捷克（年美国人丹捷克（ G.B. Dantzing）1951年提出单纯形算法（年提出单纯形算法（ Simpler）1963年年 Dantzing写成写成 “ Linear Programming and Extension”目标规划目标规划1961年查恩斯（年查恩斯（ A.Charnes）与库伯）与库伯 (W.W.Cooper)多目标规划多目标规划 (优先因子优先因子 )：艾吉利：艾吉利 (Y.Ijiri)计算机处理目标规划：斯计算机处理目
2、标规划：斯 .姆姆 .李李 (S.M.Lee)与杰斯开莱尼（与杰斯开莱尼（V.Jaaskelainen）线性规划是研究线性不等式组的理论，或者说是研究（高线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。维空间中）凸多面体的理论，是线性代数的应用和发展。第第 1章：线性规划与单纯形法章：线性规划与单纯形法第第 1节：线性规划问题及其数学模型节：线性规划问题及其数学模型1.1 问题的提出问题的提出生产计划问题生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划
3、的要求。例例 1.1 生产计划问题（资源利用问题）生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家胜利家具厂生产桌子和椅子两种家具。桌子售价具。桌子售价 50元元 /个，椅子销售价格个，椅子销售价格30元元 /个，生产桌子和椅子要求需要木工个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要和油漆工两种工种。生产一个桌子需要木工木工 4小时，油漆工小时，油漆工 2小时。生产一个椅小时。生产一个椅子需要木工子需要木工 3小时，油漆工小时，油漆工 1小时。该厂小时。该厂每个月可用木工工时为每个月可用木工工时为 120小时，油漆工小时，油漆工工时为工时为 50小时。问该厂如何组
4、织生产才小时。问该厂如何组织生产才能使每月的销售收入最大？能使每月的销售收入最大？解：解： 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤：几个步骤：1确定决策变量：确定决策变量： x1=生产桌子的数量生产桌子的数量x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数： 家具厂的目标是销售收入最大家具厂的目标是销售收入最大max z=50x1+30x23确定约束条件：确定约束条件：4x1+3x2120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）4变量取值限制：变量取值限制：一般情况，决策变量只取正值（非
5、负值）一般情况，决策变量只取正值（非负值）x1 0, x2 0 数学模型数学模型maxZ=50x1+30x2 s.t. 4x1+3x2 1202x1+ x2 50x1,x2 0线性规划数学模型三要素：线性规划数学模型三要素：决策变量、约束条件、目标函数决策变量、约束条件、目标函数例例 1 .2 营养配餐问题营养配餐问题假定一个成年人每天需要从食物中假定一个成年人每天需要从食物中获得获得 3000千卡的热量、千卡的热量、 55克蛋白质和克蛋白质和800毫克的钙。如果市场上只有四种食毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量品可供选择，它们每千克所含的热量和营养成分和市场价格见
6、下表。问如和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购何选择才能在满足营养的前提下使购买食品的费用最小？买食品的费用最小？各种食物的营养成分表各种食物的营养成分表解：解： 设设 xj为第为第 j种食品每天的购入量，则配种食品每天的购入量，则配餐问题的线性规划模型为：餐问题的线性规划模型为：min Z=14x1+6x2 +3x3+2x4 s.t. 1000x1+800x2 +900x3+200x4 300050x1+ 60x2 + 20x3+ 10x4 55400x1+200x2 +300x3+500x4 800x1， x2 ， x3 ， x4 0其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题分派问题分派问题生产工艺优化问题生产工艺优化问题
