第四讲线性规划-图解法(liu).pptVIP

第四讲 线性规划 本讲的主要内容： 一、情况介绍 二、线性规划模型及标准化 线性规划模型的一般形式 线性规划模型的标准形 三、二维线性规划的图解法 图解法含义 图解法举例 几个概念 解的状态 图解法延伸 一、情况介绍 作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。 线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。 一、情况介绍 线性规划研究的问题可以归结为两大类别： 1、在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求约束极大化问题）。 2、在给定目标下，如何以最少的资源消耗，实现这个目标（求约束极小化问题）。 一、情况介绍 线性规划问题就是在一定约束条件下，寻找目标函数的极值问题。 所谓线性规划，是指约束条件为线性等式或线性不等式，且目标函数也为线性函数。 二、线性规划模型及标准化 1、线性规划模型的一般形式 根据实际问题的要求，可建立线性规划问题数学模型。线性规划问题的数学模型，由目标函数和约束条件两部分组成。下面我们举例说明线性规划问题的数学模型。 例一：生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 二、线性规划模型及标准化 二、线性规划模型及标准化 解：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型： Max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x4≤2000 1.0x1+5.0x2+1.0x3+3.5x4≤8000 ? 1.0x1+3.0x2+3.5x3+1.0x4≤5000 ? x1，x2，x3，x4≥ 0 二、线性规划模型及标准化 1、线性规划模型的一般形式 例二：配料问题 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示： 二、线性规划模型及标准化 二、线性规划模型及标准化 假设熔炼时重量没有损耗，要熔炼成100千克不锈钢G，应选用各种原料各多少才能使成本达到最小。 解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4千克，根据条件，可建立相应的线性规划模型如下： 二、线性规划模型及标准化 1、线性规划模型的一般形式 Min Z=115x1+97x2+82x3+76x4? s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x4≥3.20 0.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.10? 0.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30? x1 + x2 + x3 + x4=100 x1 , x2 , x3 , x4≥0 二、线性规划模型及标准化 1、线性规划模型的一般形式 Max(Min) z=c1x1+c2x2+…+cnxn s.t. a11x1+a12x2+…+a1nxn≥(=、≤)b1