第一章 线性规划及单纯形法1-图解法

第一章线性规划及单纯形法第一节线性规划问题及其数学模型例：某公司计划生产甲、乙两种产品，已知各生产一件时分别占用的设备A、B的台时、调试时间和调试工序每天可用于这两种产品的能力、各销售一件时的获利情况，如下表所示。问该公司应生产两种产品各多少件，使获取的利润为最大。甲乙每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21设和分别表示该公司生产甲乙两种产品的数量1x2x212maxxxz0,524261552121212xxxxxxx目标函数约束条件例：某公司拟在下一年度的1~4月的4个月内需租用仓库。已知各月份所需仓库的面积和租借费用如表所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小。月份1234所需仓库面积（100m2）15102012合同租借期限1个月2个月3个月4个月合同期内的租费（元/100m2）2800450060007300设为该公司在第i(i=1,2,3,4)个月初签定的租借期为j(j=1,2,3,4)个月的仓库面积合同（单位为100平方米）ijx142313322212413121117300)(6000)(4500)(2800minxxxxxxxxxxz)4,,1;4,,1(0122010154132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxij目标函数约束条件规划问题的数学模型由三个要素组成：（1）变量（决策变量）（2）目标函数（3）约束条件如果规划问题模型中，决策变量的取值是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则称该类规划问题的数学模型为线性规划的数学模型。假定线性规划问题中含有n个变量，分别用xj(j=1，…，n)表示，在目标函数中xj的系数为cj（cj通常称为价值系数），xj的取值受m项资源的限制，用bi（i=1，…，m）表示第i种资源的拥有量，用aij表示变量xj取值为1个单位时所消耗或含有的第i种资源的数量（技术系数或工艺系数），则线性规划模型为：nnxcxcxcz2211min)max(或0,,),(),(),(122112222212111212111nmnmnmmnnnnxxbxaxaxabxaxaxabxaxaxa目标函数约束条件简写为：njjjxcz1min)max(或),,1(0),,1(),(1njxmibxajnjijij向量表达形式：CXzmin)max(或0),(1XbxPnjjj),,,(21ncccCnxxxX21mjjjjaaaP21mbbbb21mnmmnnaaaaaaaaaA212222111211CXzmin)max(或0),(XbAX矩阵表达形式：标准形式：njjjxcz1max目标函数),,1(0),,1(1njxmibxajnjijij约束条件),,1(0mibi其中，如何将线性规划问题化为标准形式？（1）目标函数取极小值时（2）右端项小于0时（3）约束条件为不等式时（4）取值无约束的变量（5）对决策变量小于0时例：将下述线性规划化为标准形式32132minxxxz无约束321321321321,0,052327xxxxxxxxxxxx33311,,xxxxxzz54332100332maxxxxxxxz0,,,,,52232754332133215332143321xxxxxxxxxxxxxxxxxxxx解：令注：4x——松弛变量5x——松弛变量（剩余变量）第二节图解法基本概念：（1）可行解一个线性规划问题有解，是指能找出一组xi，满足约束条件，称这组xi为问题的可行解。（2）可行域称全部可行解的集合为可行域。（3）最优解可行域中使目标函数值达到最优的可行解称为最优解。图解法的步骤：（1）在平面上建立直角坐标系（2）图示约束条件，找出可行域（3）图示目标函数，寻求最优解线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2212maxxxz0,524261552121212xxxxxxx线性规划问题求解的可能结局：（1）无穷多最优解（2）无界解（3）无解，或无可行解（4）唯一最优解作业：43页：1.1(1),(4)1.2(2)