chap1线性规划基本性质

运筹学

第一章 线性规划的基本性质

运筹学

线性规划(概论) 线性规划(概论)线性规划(Linear Programming)创始人： 线性规划( Programming)创始人： 创始人 1947年美国人G.B.丹齐克(Dantzing) 1947年美国人G.B.丹齐克(Dantzing) 年美国人G.B.丹齐克 1951年提出单纯形算法(Simpler) 1951年提出单纯形算法(Simpler) 年提出单纯形算法 1963年Dantzing写成“ 1963年Dantzing写成“Linear Programming and 写成 Extension” Extension” 1979年苏联的Khachian提出“椭球法” 1979年苏联的Khachian提出“椭球法” 年苏联的Khachian提出 1984年印度的Karmarkar提出“投影梯度法” 1984年印度的Karmarkar提出“投影梯度法” 年印度的Karmarkar提出 线性规划是研究线性不等式组的理论，或者 线性规划是研究线性不等式组的理论， 说是研究(高维空间中)凸多面体的理论， 说是研究(高维空间中)凸多面体的理论，是线 性代数的应用和发展。 性代数的应用和发展。 2

运筹学

1.1 线性规划的数学模型 生产计划问题如何合理使用有限的人力， 如何合理使用有限的人力，物力 和资金，使得收到最好的经济效益。 和资金，使得收到最好的经济效益。 如何合理使用有限的人力， 如何合理使用有限的人力，物力 和资金，以达到最经济的方式， 和资金，以达到最经济的方式，完 成生产计划的要求。 成生产计划的要求。3

运筹学

例1.1 生产计划问题(资源利用问题) 生产计划问题(资源利用问题) 胜利家具厂生产桌子和椅子两种家 桌子售价50元 椅子销售价格30 具。桌子售价50元/个，椅子销售价格30 元/个，生产桌子和椅子要求需要木工和 油漆工两种工种。 油漆工两种工种 。 生产一个桌子需要木 小时，油漆工2小时。 工 4 小时 ， 油漆工 2小时 。 生产一个椅子 需要木工3 小时，油漆工1小时。 需要木工 3 小时 ， 油漆工 1小时 。 该厂每 个月可用木工工时为120小时 小时， 个月可用木工工时为120小时，油漆工工 时为50 小时 小时。 时为 50小时。 问该厂如何组织生产才能 使每月的销售收入最大？ 使每月的销售收入最大？4

运筹学

解：将一个实际问题转化为线性规划模型有以下几个步骤： 几个步骤：

1.确定决策变量：x1=生产桌子的数量 确定决策变量： x2=生产椅子的数量 2.确定目标函数：家具厂的目标是销售收入最大 确定目标函数： max z=50x1+30x2 z=50x 30x 3.确定约束条件： 确定约束条件： 4x1+3x2≤120(木工工时限制) 木工工时限制) 2x1+x2 ≤ 50 (油漆工工时限制) 油漆工工时限制) 4.变量取值限制： 变量取值限制：一般情况，决策变量只取正值(非负值) 一般情况，决策变量只取正值(非负值)

x1 ≥ 0, x2 ≥ 05

运筹学

数学模型

max z=50x1+30x2 z=50x 30x s.t. 4x1+3x2 ≤ 120 2x1+ x2 ≤ 50 x1,x2 ≥ 0 线性规划数学模型三要素： 线性规划数学模型三要素： 决策变量、约束条件、 决策变量、约束条件、目标函数 线性规划问题： 线性规划问题： 以未知量的线性函数为特征的一类最 优化问题6

运筹学

例1 .2 营养配餐问题 假定一个成年人每天需要从食物中 获得3000千卡的热量 55克蛋白质和 千卡的热量、 获得3000千卡的热量、55克蛋白质和 800毫克的钙 800毫克的钙。如果市场上只有四种食 毫克的钙。 品可供选择， 品可供选择，它们每千克所含的热量 和营养成分和市场价格见下表。 和营养成分和市场价格见下表。问如 何选择才能在满足营养的前提下使购 买食品的费用最小？ 买食品的费用最小？7

运筹学

各种食物的营养成分表热量 蛋白质 千卡) 序号 食品名称 (千卡) (克) 1 2 3 4 猪肉 鸡蛋 大米 白菜 1000 800 900 200 50 60 20 10 钙 价格 毫克) (毫克) (元) 400 200 300 500 14 6 3 2

运筹学

则配餐问题的线性规划模型为： 则配餐问题的线性规划模型为：

解 ： 设 xj 为第 j种食品每天的购入量 ， 为第j 种食品每天的购入量，min S=14x1+6x2 +3x3+2x4 S=14x s.t. 1000x1+800x2 +900x3+200x4 ≥ 3000 1000x 800x 900x 200x 50x 60x 50x1+ 60x2 + 20x3+ 10x4 ≥ 55 20x 10x 400x 200x 300x 500x 400x1+200x2 +300x3+500x4 ≥ 800 x1,x2 , x3 , x4 ≥ 09

运筹学

其他典型问题： 其他典型问题： 合理下料问题 合理下料问题 运输问题 运输问题 生产的组织与计划问题 生产的组织与计划问题 投资证券组合问题 投资证券组合问题 分派问题 分派问题 生产工艺优化问题10

运筹学

线性规划问题的一般形式： 线性规划问题的一般形式： Min (Max)S=c1x1+c2x2+…..+cnxn s.t. a11x1+a12x2+….+a1nxn ≥(=, ≤ )b1 a21x1+a22x2+….+a2nxn ≥(=, ≤ )b2 …………………. am1x1+am2x2+….+amnxn ≥(=, ≤ )bm x1,x2….xn ≥ 011

运筹学

线性规划问题隐含的假定： 线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标 比例性假定： 函数的改变量和决策变量的改变量成比 同样， 例，同样，每个决策变量的变化引起约 束方程右端值的改变量和该变量的改变 量成比例。 量成比例。

运筹学

线性规划问题隐含的假定： 线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标 比例性假定： 函数的改变量和决策变量的改变量成比 同样， 例，同样，每个决策变量的变化引起约 束方程左端值的改变量和该变量的改变 量成比例。 量成比例。 …… 此处隐藏：988字，全部文档内容请下载后查看。喜欢就下载吧 ……