运筹学线性规划问题与图解法.ppt

《运筹学线性规划问题与图解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学（OR:operationalresearch(英)operationsresearch(美)）主讲：卢安文2线性规划（LP:LinearProgramming）问题与图解法2.1问题的提出生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360设备约束4

2、X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥0配料问题:每单位原料i含vitamin如下：原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量求：最低成本的原料混合方案解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)线性规划问题的基本特征决策变量：向量(x1…xn)T代表一个具体的方案，一般有xi非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1

3、…xn)线性式，求Z极大（Max）或极小(Min)线性规划问题的一般形式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn(=,)b2………am1X1+am2X2+…+amnXn(=,)bmXj0(j=1,…,n)简写式向量式其中：C=(c1,c2,…,cn)价值向量X=(x1,x2,…,xn)T决策向量Pj=(a1j.a2j,…,amj)T系数向量B=(b1,b2,…,bn)T资源向量矩阵式其中系数矩阵2.2线性规划问题的图解法1图解法用于求解两个决策变量的线性规划问题，图解法简单直观，

4、有助于了解线性规划问题求解的基本原理。如：maxZ=70X1+120X2人力约束9X1+4X2≤360设备约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥0.9080604020020406080100x1x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300ABCDEFGHIZ=70x1+120x2图中阴影部分为可行域（满足约束条件的点的集合）可行解：满足约束条件的解可行域是可行解的集合当等值线Z=70x1+120x2平行移动到H点时Z取得最大值此时，x1=20,x2=24Z=70*20+120*24设备和原材料恰好使用完，而人力节余8

5、4个单位即：设备约束和原材料约束条件取等号，而人力约束条件仍然取不等号2线性规划问题的解可行解：满足约束条件的解X=(x1,x2,…,xn)F可行域:可行解的集合(线性规划问题的可行域一般为凸集)最优解：使目标函数达到最优的可行解若线性规划问题有唯一最优解，则最优解一定在可行域的顶点处取得线性规划问题可能存在无穷多个最优解（若线性规划问题有两个最优解，则一定有无穷多个最优解）线性规划问题可能存在无界解（即无最优解）线性规划问题可能存在无可行解（此时无最优解，可行域为空集）3线性规划问题的标准型目标函数极大化（或极小化）约束条件为等式，且右端常数全为非负决策变量非负化标准型maxZ=70X1+

6、120X2maxZ=70X1+120X2+0S1+0s2+0s39X1+4X2≤3609X1+4X2+S1=3604X1+5X2≤2004X1+5X2+s2=2003X1+10X2≤3003X1+10X2+s3=300X1≥0X2≥0Xj≥0j=1,2其中S1，s2，s3≥0为松弛变量化标准型minZ=x1+2x2-3x3maxZ’=x’1－2x2+3(x’3－x”3)x1+x2+x3≤9－x’1+x2+x’3－x”3+s1=9-x1-2x2+x3≥2x’1－2x2+x’3－x”3–s2=23x1+x2-3x3=5－3x’1+x2－3(x’3－x”3)=5x1≤0x2≥0x3无约束x’1≥0

7、x2≥0x’3≥0x”3≥0s1≥0s2≥0其中s1为松弛变量，s2为剩余变量x3＝x’3－x”3+0s1+0s2线性规划的标准型下列情况具体处理若要求目标函数求最大化若约束方程为不等式：非负松弛变量，非负剩余变量若变量不是非负：非正，自由变量，右边为非正任何形式的线性规划模型都可以化为标准型。