01-线性规划 运筹学 教学课件.pptVIP

线形规划目录 例1.1生产计划问题表格描述 各种食物的营养成分表（转置） 线形规划的一般模型:特点 线形规划的一般模型:数学模型 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量 线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划解的概念：最优基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 下料问题 下料问题:分析1 下料问题:分析2 下料问题:使用圆钢数量最少模型 下料问题:余料最少模型 设备配购问题 设备配购问题:分析 设备配购问题:模型 参考约束函数标准化 参考约束函数标准化 子矩阵可逆 重新选择 基变量 生产计划问题 食谱问题 产品配套问题 下料问题 配料问题 某企业使用m种资源生产n种产品，已知第i种资源的数量是bi，其单价为pi，每生产一个单位第j种产品所提供的产值是vj，所消耗第i种资源的数量是aij。第j种产品的合同与指令性计划的产量指标是ej，最高需求量为dj。问该企业该如何指定生产计划？ xn … x2 x1 生产量 ∑vjxj 总产值 vn … v2 v1 单位产值 dn … d2 d1 最高产量 en … e2 e1 最低产量 pm∑amjxj ∑amjxj bm pm amn … am2 am1 资源m … … … … … … p2∑a2jxj ∑a2jxj b2 p2 a2n … a22 a21 资源2 p1∑a1jxj ∑a1jxj b1 p1 a1n … a12 a11 资源1 资源 成本 资源 消耗量 资源数量 资源单价 产品n … 产品2 产品1 某厂生产一种产品，由2个B1零件和3个B2零件配套组装而成。该厂有A1、A2、A3三种机床可以加工这两种零件，每种机床的数量和每个工作日全部用于加工一种零件的最大产量见下表，试求该产品产量的最大生产方案。 18 10 4 A3 45 35 2 A2 30 20 3 A1 零件B2 零件B1 每台机床生产率（件/日） 机床数量 机床种类 72 40 A3 90 70 A2 90 60 A1 零件B2 零件B1 每类机床总生产率（件/日） 机床种类 1 1 1 合计 X32 x31 A3 X22 X21 A2 X12 X11 A1 零件B2 零件B1 每类机床每日计划加工时间 机床种类 每类机床每日加工零件数量 每类机床每日计划生产时间 工时约束： x11+x12=1、x21+x22=1、x31+x32=1 零件配套要求： Z=min{(60x11+70x21+40x31)/2, (90x12+90x22+72x32)/3} 配套要求线形表示： z ≤ (60x11+70x21+40x31 )/2 且 z ≤ (90x12+90x22+72x32 )/3 即：z - 30x11-35x21-20x31 ≤0 z – 30x12-30x22-24x32 ≤0 72 40 A3 90 70 A2 90 60 A1 零件B2 零件B1 机床 1 1 1 合计 X32 x31 A3 X22 X21 A2 X12 X11 A1 零件B2 零件B1 机床 每类机床每日加工零件数量 每类机床每日计划生产时间 max z s.t. z - 30x11 - 35x21 - 20x31 ≤0 z – 30x12 - 30x22 - 24x32 ≤0 x11 + x12 = 1 x21 + x22 = 1 x31 + x32 = 1 x11, x12, x13, x21, x22, x23 ≥ 0 4 1.2 C 2 2.1 B 1 3.1 A 每台机床需要轴件数量 长度 轴类 制造某机床需要A、B、C三种轴件，规格数量要求如下表，各轴件使用长度为5.5米的相同圆钢下料。计划生产100台机床，最少需要多少根圆钢? 1、问题要求每根使用圆钢下料后余料要少 余料小于1.2米 2、每根圆钢有多种下料方法 0.7 4 0 0 5 0.1 1 2 0 3 4 2 1 1 0 0.3 余料 2 2 0 C(1.2) 1 0 1 B(2.1) 0 1 1 A(3.1) 一根圆钢的下料方法 轴类