管理运筹学Chapter-2.1-线性规划问题的数学模型及相关概念

线性规划,ChapterTwo：LP,第一节线性规划的数学模型及相关概念,现实中的线性规划问题及数学模型线性规划的标准形式线性规划的几何解释线性规划的基及基本可行解,一现实中的线性规划问题及模型,例2-1生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。,一现实中的线性规划问题及模型,一现实中的线性规划问题及模型,5,求解这个线性规划，可以得到最优解为：x1=294.12（件）x2=1500（件）x3=0（件）x4=58.82（件）最大利润为z=12737.06（元）请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。,一现实中的线性规划问题及模型,6,例2-2配料问题某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。,一现实中的线性规划问题及模型,一现实中的线性规划问题及模型,8,例2-3背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：要在背包中装入这三种物品各多少件，使背包中的物品价值最高。,一现实中的线性规划问题及模型,9,一现实中的线性规划问题及模型,10,例2-4最小费用流问题某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和F2是两个工厂，W1和W2是两个仓库。D是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，F1F2与DW2路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。,一现实中的线性规划问题及模型,11,一现实中的线性规划问题及模型,12,一现实中的线性规划问题及模型,可用一些变量表示这类问题的待定方案，这些变量的一组定值就代表一个具体方案这些变量称为决策变量，并往往要求它们非负有一个期望达到的目标，这个目标能以某种确定的数量指标刻画出来，而这种指标可表示为关于决策变量的线性函数，按所考虑的问题不同，要求该函数值最大化或最小化存在一定的约束条件，这些约束条件都能用关于决策变量的线性不等式或等式来表示,一现实中的线性规划问题及模型,线性规划模型的三要素：决策变量：指模型中要求解的未知量，简称变量。目标函数：指模型中要达到的目标的数学表达式。约束条件：指模型中的变量取值所需要满足的一切限制条件。,一现实中的线性规划问题及模型,一现实中的线性规划问题及模型,16,二、线性规划的标准形式,二、线性规划的标准形式,二、线性规划的标准形式,非标准形LP问题的标准化一、极小化目标函数的问题minz=CX令z=zmaxz=CX例：minz=3x12x2maxz=3x12x2二、约束条件不是等式的问题bim），其秩为m，B是A矩阵中的一个非奇异的mm阶（满秩）子矩阵，则称B为线性规划的一个基。与其中的列向量所对应的变量叫做基变量，除基变量之外的变量称为非基变量。,四、线性规划的基、基本可行解,定义2-5基本解令所有的非基变量等于零，根据CramerRule，将得到唯一解，称为线性规划的基本解。基本可行解满足非负约束条件（XB=B-1b0）的基本解称为基本可行解。相应地，基本可行解对应的基称为可行基。,-33-,Maxz=2x1+3x2st.x1+x23x1+2x24x1,x20,Maxz=2x1+3x2+0 x3+0 x4st.x1+x2+x3=3x1+2x2+x4=4x1,x2,x3,x40,A=,x1x2x3x4,11101201,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。,设,B=,1001,，令,，则,|B|=10,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T,例：,x3x4,基变量,令,B=,1110,x1x3,，则,令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T,|B|=-10,非基本可行解,基本可行解,标准化,四、线性规划的基、基本可行解,四、线性规划的基、基本可行解,定理2-1线性规划的基本可行解就是可行域的极点。,34,Maxz=2x1+3x2s.t.x1+x23x1+2x24x1,x20,Maxz=2x1+3x2+0 x3+0 x4s.t.x1+x2+x3=3x1+2x2+x4=4x1,x2,x3,x40,例：,标准化,A矩阵包含以下六个22的子矩阵：B1=p1，p2B2=p1，p3B3=p1，p4B4=p2，p3B5=p2，p4B6=p3，p4其中所有的子矩阵行列式值均不等于0，均为非奇异方阵，因此该问题共有6个基。,四、线性规划的基、基本可行解,35,B6=,1001,，则,|B6|=10,x3x4,基变量,基本可行解对应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是基本可行解。,B(2,1)