第三章规划论 1.什么是规划论 在生产生活以及军事领域经常会遇到资源 分配问题,不同的分配方案产生的效益是不 样的,所以,为了追求最佳效益,必须在不同 的分配方案中选择最佳的资源分配方案。规划 论就是研究针对不同需求对有限资源进行分配 的一个运筹学分支
1.什么是规划论 在生产生活以及军事领域经常会遇到资源 分配问题,不同的分配方案产生的效益是不一 样的,所以,为了追求最佳效益,必须在不同 的分配方案中选择最佳的资源分配方案。规划 论就是研究针对不同需求对有限资源进行分配 的一个运筹学分支。 第三章 规划论
2理论分支 理论分支 零一规 动态规 非线性 目 线性规划 整数规划 标规 划 划规划 划 其中,线性规划是形成最早也是最成熟的一个分支。到 目前为止,它的应用也最广泛,是数学规划及运筹学其他分 支的基础
其中,线性规划是形成最早也是最成熟的一个分支。到 目前为止,它的应用也最广泛,是数学规划及运筹学其他分 支的基础。 线 性 规 划 整 数 规 划 动 态 规 划 零 一 规 划 非 线 性 规 划 目 标 规 划 2 理论分支 理论分支
第一节线性规划 康脱络维奇—论文“生产组织与 计划中的数学方法”,1939年 1947年,丹捷格提出了单纯形法
康脱络维奇——论文 “生产组织与 计划中的数学方法” ,1939年。 1947年,丹捷格提出了 单纯形法 第一节 线性规划
1线性规划方法解决问题的过程 对于一个实际问题,如果采用线性规划去求 解,应做两方面的工作,一是把求解问题抽象成 能用线性规划来解的数学模型,这就是数学建模 。二是对这个线性规划进行求解。即 数学建模 求解
对于一个实际问题,如果采用线性规划去求 解,应做两方面的工作,一是把求解问题抽象成 能用线性规划来解的数学模型,这就是数学建模 。二是对这个线性规划进行求解。即 数 学 建 模 求 解 1 线性规划方法解决问题的过程
2线性规划问题的数学模型 (1)引例 某军工厂准备用三种原料来制造两种产品,有关数据 如下表所示。问如何安排生产,以使总利润达到最大化。 单位产品产品 消耗量 原料总量 原料(公斤 360 ABC 200 437 450 300 单位产品利润 12 (元
3.线性规划的数学模型 (1)引例 某军工厂准备用三种原料来制造两种产品,有关数据 如下表所示。问如何安排生产,以使总利润达到最大化。 单位产品 产品 消耗量 原料(公斤) I II 原料总量 A 9 4 360 B 4 5 200 C 3 10 300 单位产品利润 (元) 7 12 2 线性规划问题的数学模型
确定目标:求出生产两种产品的数量各为公斤,以使总利 润达到最大。 建立数学模型 设I产品生产x1公斤,Ⅱ产品生产x2公斤 目标是MAX总利润Z=7x1+12x2 9x1+4 2s360 4x1+5x2<200 3X1+10x2<300 0
确定目标:求出生产两种产品的数量各为公斤,以使总利 润达到最大。 建立数学模型: 设 I 产品生产 x1 公斤,II 产品生产 x2 公斤 MAX 总利润 Z = 7 x1 + 12 x 目标是 2 9 x1 + 4 x2 ≤ 360 4 x1 + 5 x2 ≤ 200 3 x1 + 10 x2 ≤ 300 x1,x2, ,x3 ≥ 0
建立数学模型: 设I产品生产x1公斤,Ⅲ产品生产x2公斤 目标是MAX总利润Z=7x1+12x2 9x1+4x2≤360 4x1+5x2<200 3x1+10x2<300 ,x3≥0
建立数学模型: 设 I 产品生产 x1 公斤,II 产品生产 x2 公斤 MAX 总利润 Z = 7 x1 + 12 x 目标是 2 9 x1 + 4 x2 ≤ 360 4 x1 + 5 x2 ≤ 200 3 x1 + 10 x2 ≤ 300 x1,x2, ,x3 ≥ 0
(2)线性规划问题的共同特征 以上问题属于线性规划问题,这类问题从数学上讲所 具有的共同特征是: 1)决策变量。 每一个问题都用一组未知数(x1 表示某一方案,这组 Q知速条他定值代表一个具体的规划方案。通常要求这些未知 数取值是非负。以后我们称这组未知数为决策变量 3)目标函数。 线性规划问题都有一个目标要求,并且这个目标可以表示为一组未知数的 线性函数,称之为目标函数,按研究问题的实际情况目标函数可以是求最小值 也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化,而对 于成本、费用、支出等指标则希望达到最小化
以上问题属于线性规划问题,这类问题从数学上讲所 具有的共同特征是: 1)决策变量。 每一个问题都用一组未知数(x1.x2……xn)表示某一方案,这组 未知数的一组定值代表一个具体的规划方案。通常要求这些未知 数取值是非负。以后我们称这组未知数为决策变量。 2)约束条件。 3)目标函数。 线性规划问题都有一个目标要求,并且这个目标可以表示为一组未知数的 线性函数,称之为目标函数,按研究问题的实际情况目标函数可以是求最小值 也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化,而对 于成本、费用 、支出等指标则希望达到最小化。 (2)线性规划问题的共同特征
综合上述这三点,这类问题都可以用如下数学语言 来描述 目标函数:max(min)Z=c1x1+c2x2+…+cnxn a1x1+a12x2+…a1nxn≥(=,≤)b1 a21x1+a2X2+….a2xn2(=,≤)b m1x1+am2x2+… aX≥(=,≤)b 0
综合上述这三点,这类问题都可以用如下数学语言 来描述。 目标函数: max ( min ) Z = c1 x1 + c2 x2 + … + cn xn a11x1 + a12x2 + … a1n xn ≥(= ,≤)b1 a21x1 + a22x2 + … a2n xn ≥(= ,≤)b2 …… am1 x1 + am2 x2 + … amnxn ≥(= ,≤)bm x1,x2,… xn ≥ 0
3线性规划问题的标准形式 (1)线性规划的标准形式是: 目标函数:maxZ=c1x1+c2x2+…+cnxn a1x1+a12x2+…a1nxn=b 214+ax+ a X 2 b nn m1X1+8m22 X+a x= b mn n m 0
3 线性规划问题的标准形式 (1)线性规划的标准形式是: 目标函数: max Z = c1 x1 + c2 x2 + … + cn xn a11x1 + a12x2 + … a1n xn = b1 a21x1 + a22x2 + … a2n xn = b2 …… am1 x1 + am2 x2 + … amnxn = bm x1,x2,… xn ≥ 0