资源描述：
《《线性规划基本性质》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章LinearProgrammingLP线性规划基本性质1第1章线性规划的基本性质1.1线性规划的一般模型1.2线性规划的图解法1.3线性规划的标准形式1.4线性规划的解及其性质1.5线性规划的应用模型第1章线性规划的基本性质2第1章线性规划的基本性质1.1线性规划的一般模型1.1.1引例例1产品配比问题（范例）某厂拟生产甲、乙两种产品，每件利润分别为3、5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1、2工时。两件产品的部件最后都要在C车间装配，装配每
2、件甲、乙产品分别需要3、4工时，三车间每天可用于生产这两种产品的工时分别为8、12、36，问应如何安排生产这两种产品才能获利最多？3第1章线性规划的基本性质1.1线性规划的一般模型zx1x2决策变量z=3x1+5x2max0目标函数x1≤8①2x2≤12②3x1+4x2≤36③函数约束x1，x2≥0④非负性约束s.t.甲乙10302481236ABC车间产品单耗（工时/件）最大生产能力（工时/天）单位利润（百元/件）354第1章线性规划的基本性质1.1线性规划的一般模型例2配料问题某化工厂根据一项合同要为用户生产
3、一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？5第1章线性规划的基本性质1.1线性规划的一般模型成分含量(%)原料化学成分甲乙产品成分最低含量(%)ABC12323315425成本（元/千克）32x1x2minz=3x1+2x212x1+3x2≥42x1+3x2≥2s.t.3x1+15
4、x2≥5x1+x2=1x1,x2≥0配料平衡条件z6第1章线性规划的基本性质1.1线性规划的一般模型1.1.2线性规划的一般模型一般LP模型的三类参数：价值系数cj，消耗系数aij，右端常数bi.LP模型的三要素：决策变量，目标函数，约束条件.s.t.optz=c1x1+c2x2+c3x3+…+cnxna11x1+a12x2+…+a1nxnb1a21x1+a22x2+…+a2nxnb2…am1x1+am2x2+…+amnxnbmxj≥(或≤)0,或自由,j=1,2,…,n><><><7第1章线性规划的基本性质1.
5、2线性规划的图解法1.2.1图解法的基本步骤X*=(4,6)Tz*=421°画出可行域图形2°画出目标函数的等值线及其法线3°确定最优点maxz=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42边界方程8第1章线性规划的基本性质1.2线性规划的图解法1.2.2几点说明实际运用时还须注意以下几点:(1)若
6、函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,只须赋给z两个适当的值。(3)在找出最优点后,关于其坐标值有两种确定方法:①在图上观测最优点坐标值②通过解方程组得出最优点坐标值9第1章线性规划的基本性质1.2线性规划的图解法1.2.3几种可能结果一、唯一解如例1、例2都只有一个最优点，属于唯一解的情形。s.t.maxz=3x1+4x2x1≤82x2≤123x1+4x2≤36x1，x2≥0二、多重解z
7、=12z*=36线段BC上无穷多个点均为最优解。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)10第1章线性规划的基本性质1.2线性规划的图解法x1x2z*三、无界解3694812x1x2R2R1∩R2=Ø四、无可行解+∞R111第1章线性规划的基本性质1.3线性规划的标准形式1.3.1线性规划问题的标准形式maxz=c1x1+c2x2+c3x3+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(≥0)a21x1+a22x2+…+a2nxn=b2(≥0)………am1x1+a
8、m2x2+…+amnxn=bm(≥0)x1,x2,…,xn≥0简记为：maxz=∑cjxjj=1ns.t.∑aijxj=bi,i=1,2,…,mj=1nxj≥0,j=1,2,…,nmaxz=CTXs.t.AX=bX≥0(M1):(M2):(M3):(M)12第1章线性规划的基本性质1.3线性规划的标准形式1.3.2非标准形LP问题的标准化一、目标函数minz=CTX令z′
