武汉工程大学 运筹学02-线性规划的图解法知识讲解.ppt

《武汉工程大学 运筹学02-线性规划的图解法知识讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、武汉工程大学运筹学02-线性规划的图解法例2合理配料问题求：最低成本的原料混合方案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量2例3、运输问题工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。3(2)线性规划问题的特征：决策变量：每个问题都用一组决策变量(X1…Xn)表示，这组决策变量的值都代表一个具体方案。目标函数：衡量决策方案优劣的函数，它是决策变量的线性函数，根据问题不同，目标函数

2、实现最大化或最小化。约束条件：分为两类1）函数约束，一组决策变量的线性函数>=/<=/=一个给定的数（右端项）。2）决策变量约束。具备以上三个要素的问题就称为线性规划问题。4目标函数约束条件(3)线性规划模型一般形式5隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值62.2线性规划问题的图解法定义1：满足约束(2)的X=(X1…Xn)称为线性规划问

3、题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。7x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=275008直观结论若线性规划问题有解，则

4、可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。92.3线性规划问题的标准形式目标函数约束条件(1)线性规划模型一般形式10价值系数决策变量技术系数右端常数(2)线性规划模型标准形式11简记形式(3)线性规划模型其它形式12矩阵形式价值向量决策向量系数矩阵右端向量13价值向量决策向量右端向量向量形式列向量14对

5、于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于零和小于零决策变量可能存在小于零的情况15(4)一般型向标准型的转化SLP的特点（1）目标函数取极大（2）所有约束条件均由等式表示（3）所有决策变量取非负值（4）每一约束的右端常数(资源向量的分量)均为非负值线性规划问题标准形式的特点161.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与

6、下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝-Maxz172、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s，使它等于约束右边与左边之差s=bi–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi变量s称为松弛变量18Ma

7、xZ=40X1+50X2X1+2X2≤30s.t3X1+2X2≤60引入松弛变量X3、X4、X52X2≤24X1,X20MaxZ=40X1+50X2+0X3+0X4+0X5X1+2X2+X3＝30s.t3X1+2X2+X4＝602X2+X5＝24X1,…,X5019当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi变量s称

8、为剩余变量20MaxZ=2X1+5X2+6X3+8X44X1+6X2+X3+2X4≥12s.tX1+X2+7X3+5X4≥142X2+X3+3X4≥8X1,…,X40引入剩余变量：X5、X6、X7MaxZ=2X1+5X2+6X3+8X44X1+6X2+X3+2X4-X5＝12s.tX1+X2+7X3+5X4-X6＝142X2+X3+3X4-X7＝8X1,…,X70213.决策变量如果某个变量的约束条件为或者可令或者代入原问题如果某个变量为自由变量（无非负限制），则可令且22X1+X25s.