线性规划-标准型和图解法

《线性规划-标准型和图解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性规划宁波大学商学院1线性规划应用的典型情况制造者希望建立一个生产时间表和库存计划以满足未来一段时间的市场需求，最理想的情况是：既满足市场上产品的需求、同时又使生产和库存的成本最低；金融分析员必须选择一种股票或证券进行投资，金融分析员希望使自己的投资有最大的回报率；营销经理希望能够从广播、电视、报纸、杂志这几种媒体中选择一种合适的组合，确定广告预算使自己的广告效益最好；公司的仓库分布于全美各地，现在有一些顾客订单，公司希望确定每个仓库的发货量使成本最低……2问题的提出例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲

2、、乙两种产品，已知生产单位产品的资源消耗、单位产品利润等数据如表所示，问如何安排生产计划使企业利润最大？甲乙资源限制（公斤）A11300B21400C01250单位产品利润（元/件）50100产品资源单耗3解：设x、y分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。则有maxz=50x+100ys.t.x+y≤3002x+y≤400y≤250x，y≥0规划问题的数学模型4线性规划应用的典型情况这类例子的共同特点：要求目标函数最大化或最小化；一定存在约束条件，而且这些约束条件会影响目标的实现。5基本概念1、给定有限资源，充分利用资源

3、最大限度地实现目标2、给定目标，要求完成任务使用的资源最少目标函数：表示最大目标或是最小资源约束条件：表示资源的约束或是目标约束非负条件：往往实际问题中变量不允许为负，而问题不一定明确指出，需要自己判断。一般定义为≥06线性规划问题的数学模型规划问题的数学模型三要素决策变量：问题中要确定的未知量，用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制；目标函数：它是决策变量的函数，按优化目标分别在这个函数前加上max或min；约束条件：指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。7线性规划:是指约束条

4、件和目标函数都是线性时的规划模型。实际问题中线性的含义：一是严格的比例性；二是可叠加性。非线性规划的例子:K－T条件、0.618法、梯度法、随机搜索法等。规划问题的数学模型8LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*9线性规划数学模型目标函数约束条件决策变量10线性规划数学模型简写形式11线性规划数学模型

5、向量形式12线性规划数学模型用矩阵和向量形式13决策变量的取值变量xj的取值一般为非负，即xj≥0从数学意义上来说，可以有xj≤0xj的取值也可以是(－∞,+∞)，即xj取值不受约束或称xj无约束14maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………………………am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0线性规划问题的标准形式目标函数极大化约束条件为等号变量非负右端常数项大于或等于零15简写形式矩阵形式线性规划问题的标准形式16线

6、性规划问题的标准形式若minf=CX，可令z=－f，则maxz=min–f；目标函数为minf=c1x1+c2x2++cnxn令z=－f，变为maxz=–c1x1–c2x2-–cnxn17线性规划问题的标准形式约束条件为“≤”时，则约束条件左式加上非负的松弛变量xn+i，将约束条件变为等式约束；约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有a11x1+a12x2++a1nxn+xn+1=b118线性规划问题的标准形式约束条件为“≥”时，则约束条件左式减去非负的剩余变量xn+i，将约束条件变

7、为等式约束；约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有a11x1+a12x2++a1nxn－xn+1=b119线性规划问题的标准形式若xk无限制时，则令xk＝xk1－xk2，其中xk1、xk2≥0；若bi<0时，则－bi>0。20例化下列线性规划为标准形式maxz=2x1+2x2－4x3s.t.x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0,x3无限制21解：该线性规划问题的标准形式为maxz=2x1+2x2－4x31+4x32x1+3x2－3x31+3x32－x4=3

8、0x1+2x2－4x31+4x32+x5=80x1、x2、x31、x32、x4、x5≥022例23解：令则加入松驰变量s,w，得到标准型如下：24回顾：学校准备为学生添加营养餐，