《管理运筹学》02-1线性规划的数学模型及相关概念.ppt

* 第1节 线性规划的数学模型及相关概念 四、线性规划的基、基本可行解 B6= 1 0 0 1 ，则 | B6 |=1≠0, x3 x4 ——基变量 ——基本可行解 对应O点 令 x1=x2 =0，则 x3 =3, x4=4，X6=(0,0,3,4)T 同理可以求得B1、B2、B3、B4、B5对应的基本解： X1=(x1，x2，x3，x4)T=(2，1，0，0)T 对应B点 X2=(x1，x2，x3，x4)T=(4，0，-1，0)T对应E点 X3=(x1，x2，x3，x4)T=(3，0，0，1)T对应C点 X4=(x1，x2，x3，x4)T=(0，2，1，0)T对应A点 X5=(x1，x2，x3，x4)T=(0，3，0，-2)T对应D点 其中X1， X3 ， X4 是基本可行解。 O(0,0) x1 x2 B(2,1) E(4,0) C(3,0) A(0,2) D(0,3) * 第1章 线性规划的基本性质 第1章 线性规划的数学模型及相关概念  第 1 节 Linear Programming L P 线性规划 的数学模型 第1节 线性规划的数学模型及相关概念 * 一、现实中的线性规划问题及数学模型 二、线性规划的标准形式 三、线性规划的几何解释 四、线性规划的基及基本可行解 第1节 线性规划的数学模型及相关概念 插入链接 * 一 现实中的线性规划问题及模型 例2-1 生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。 第1节 线性规划的数学模型及相关概念 产品甲 产品乙 产品丙 产品丁 1.5 1.0 1.5 2000 8000 5000 设备A 设备B 设备C 单位产品消耗的机时数 产品 设备能力 （小时） 利润 （元/件） 5.24 7.30 8.34 4.18 1.0 5.0 3.0 2.4 1.0 3.5 1.0 3.5 1.0 * 一 现实中的线性规划问题及模型 z x1 x2 x3 x4 决策变量 z = 5.24x1 +7.30x2 +8.34x3 +4.18x4 max 0 目标函数 1.5x1 + 1.0x2 + 2.4x3 + 1.0x4 ≤ 2000 ① 函数约束 非负性约束 s.t. 第1节 线性规划的数学模型及相关概念 1.0x1 + 5.0x2 + 1.0x3 + 3.5x4 ≤ 8000 ② 1.5x1 + 3.0x2 + 3.5x3 + 1.0x4 ≤ 8000 ③ x1 ， x2 ， x3 ， x4 ≥ 0 ④ 产品甲 产品乙 产品丙 产品丁 1.5 1.0 1.5 2000 8000 5000 设备A 设备B 设备C 单位产品消耗的机时数 产品 设备能力 （小时） 利润 （元/件） 5.24 7.30 8.34 4.18 1.0 5.0 3.0 2.4 1.0 3.5 1.0 3.5 1.0 * 一 现实中的线性规划问题及模型 第1节 线性规划的数学模型及相关概念 求解这个线性规划，可以得到最优解为： x1=294.12（件） x2=1500 （件） x3=0 （件） x4=58.82 （件） 最大利润为 z=12737.06（元） 请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。 * 一 现实中的线性规划问题及模型 例2-2 配料问题 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示： 设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。 第1节 线性规划的数学模型及相关概念 T1 T2 T3 T4 3.21 2.04 5.82 3.20 2.10 4.30 Cr Mn Ni G