2.1(一、二)线性规划与单纯形方法

1第二章线性规划与单纯形方法运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大2§2.1线性规划问题及其数学模型一、线性规划模型介绍例1：生产计划问题AB每周可用资源微量元素1230使用设备时间3260工时0224利润4050某制药厂生产A、B两种药品，生产这两种药品要消耗某种微量元素。生产每吨药品所需要的微量元素分别为1Kg，2Kg；所占设备时间分别为3小时，2小时；A产品全自动化生产不需要人工参与，生产每吨B产品需要的劳动工时为2工时。该厂每周所能得到的维生素量为30kg，每周设备最多能开60个台班，每周最多可投入24工时。已知该厂生产每吨A、B两种产品的利润分别为40万元及50万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？3全面的了解问题描述目标描述约束条件定义决策变量写出目标函数写出约束条件问题模型化（建模）4x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2建模：设产品A,B产量分别为变量x1，x2s.t.51.线性规划模型特点决策变量：向量(x1…xn)T，决策人要考虑和控制的因素，非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小62.一般式Max(Min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn(=,)b2………am1X1+am2X2+…+amnXn(=,)bmXj0(j=1,…,n)s.t.73.线性规划隐含的假设比例性目标函数改变量与决策变量改变量成比例；可加性：每个决策变量对目标和约束的影响独立于其它变量，目标函数值是每个决策变量对目标函数贡献的总和连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值，不包含随机因素二、线性规划的标准型1.一般形式a11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2…………am1X1+am2X2+…+amnXn=bmXj0(j=1,2,…,n)MaxZ=C1X1+C2X2+…+CnXn其中bi0(i=1,2,…,m)2.矩阵型maxZ=CXAX=bX0P1P2………Pna11a12………a1n其中A=a21a22………a2n…………………am1am2………amnX1X=X2Xn…b1b=b2bm…C=(C1C2…Cn)3.向量型X1AX=(P1P2…Pn)X2=bXn…CXZmax01XbxpnjjjP1X1+P2X2+…+PnXn=b114.化标准型(1)目标函数为求极小值(2)右端项小于0(3)约束条件为不等式（4）取值无约束的变量（5）X小于等于0的情况12x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2(1)约束条件例2.213X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1,…,X50松弛变量maxZ=40X1+50X2+0·X3+0·X4+0·X514maxZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)154X1+6X2+X3+2X4-X5=12X1+X2+7X3+5X4-X6=142X2+X3+3X4-X7=8X1,…,X70剩余变量maxZ=2X1+5X2+6X3+8X4(2)变量3X1'-3X1+2X28X1'-X1-4X214X1',X1,X203X1+2X28X1-4X214X20令X1=X1'-X1(3)目标函数njjjXCZ1minnjjjXCZ1'max令Z'=-Z18练习：将下列线性规划模型化为标准形式无约束321321321321321005232732minxxxxxxxxxxxxxxxzs.t.19提示：令Z’=-Z=-x1+2x2-3x3x3=x4-x5第一个约束条件左边加上松弛变量X6，第二个左边减去剩余变量x7，第三个两边同乘(-1)，则得到标准形式7105)232700)(32'max54217542165421765421ixxxxxxxxxxxxxxxxxxxxxzi（s.t.Z