优化模型yhmx

1、优化模型优化模型优化模型n优化模型的一般意义优化模型的一般意义n存贮模型存贮模型n生猪的出售时机生猪的出售时机n森林救火问题森林救火问题n线性规划模型举例线性规划模型举例（一）优化模型的数学描述（一）优化模型的数学描述下的最大值或最小值，其中下的最大值或最小值，其中.,.,)(mihi210 x.,.,),)()(piggii2100 xx设计变量（决策变量）设计变量（决策变量）目标函数目标函数),.,(nxxxx321x将一个优化问题用数学式子来描述，即求函数将一个优化问题用数学式子来描述，即求函数)(xfu 在约束条件在约束条件和和x)(xf x 可行域可行域一一 优化模型的一般意义优化模

2、型的一般意义.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(max)min(ortosubjectts .“受约束于”之意（二）优化模型的分类（二）优化模型的分类1.1.根据是否存在约束条件根据是否存在约束条件 有约束问题和无约束问题。有约束问题和无约束问题。2.2.根据设计变量的性质根据设计变量的性质 静态问题和动态问题。静态问题和动态问题。3.3.根据目标函数和约束条件表达式的性质根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标规划等。线性规划，非线性规划，二次规划，多目标规划等。（1）非线性规划）非线性规划目标函

3、数和约束条件中，至少有一个非线性函数。目标函数和约束条件中，至少有一个非线性函数。.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(min.,.,.,.,.minnixnibxatsxcuinkikikniii2102111（2）线性规划（）线性规划（LP） 目标函数和所有的约束条件都是设计目标函数和所有的约束条件都是设计变量的线性函数。变量的线性函数。（3）二次规划问题）二次规划问题目标函数为二次函数，约束条件为线性约束目标函数为二次函数，约束条件为线性约束.,.,.,.,.)(min,nixnibxatsxxbxcxfuinjijijnjij

4、iijniii21021211115. 根据变量具有确定值还是随机值根据变量具有确定值还是随机值 确定规划和随机规划。确定规划和随机规划。4. 4. 根据设计变量的允许值根据设计变量的允许值整数规划（整数规划（0-1规划）和实数规划。规划）和实数规划。（三）建立优化模型的一般步骤（三）建立优化模型的一般步骤1.确定设计变量和目标变量；确定设计变量和目标变量；2.确定目标函数的表达式；确定目标函数的表达式；3.寻找约束条件。寻找约束条件。工厂定期订购原料，存入仓库供生产之用；工厂定期订购原料，存入仓库供生产之用；车间一次加工出一批零件，供装配线每天生产之用；车间一次加工出一批零件，供装配线每天生

5、产之用；商店成批购进各种商品，放在货柜里以备零售；商店成批购进各种商品，放在货柜里以备零售；水库在雨季蓄水，用于旱季的灌溉和发电。水库在雨季蓄水，用于旱季的灌溉和发电。例例1 1 存贮模型存贮模型存贮量多少合适？存贮量多少合适？存贮量过大，存贮费用太高；存贮量太小，会导致一存贮量过大，存贮费用太高；存贮量太小，会导致一次性订购费用增加，或不能及时满足需求。次性订购费用增加，或不能及时满足需求。（四）简单优化模型举例（四）简单优化模型举例 配件厂为装配线生产若干种部件，轮换生产不同的部件时因更换设备要付生产准备费（与生产数量无关），同一部件的产量大于需求时因积压资金、占用仓库要付存贮费。今已知某

6、一部件的日需求量100件，生产准备费5000元，存贮费每日每件1元。如果生产能力远大于需求，并且不允许出现缺货，试安排该产品的生产计划，即多少天生产一次（称为生产周期），每次产量多少，可使总费用最小。问题问题1 不允许缺货的存贮模型不允许缺货的存贮模型问题分析问题分析若每天生产一次，每次100件，无存贮费，生产准备费5000元，每天费用5000元；若10天生产一次，每次1000件，存贮费900+800+100=4500元，生产准备费5000元，总计9500元，平均每天费用950元；若若5050天生产一次，每次天生产一次，每次50005000件，件，存贮费存贮费4900+4800+100=122

7、5004900+4800+100=122500元，元，生产准备费生产准备费50005000元，元，总计总计127500127500元，元，平均每天费用平均每天费用25502550元；元；寻找生产周期、产量、需求量、生产准备费和寻找生产周期、产量、需求量、生产准备费和存贮费之间的关系，使每天的费用最少。存贮费之间的关系，使每天的费用最少。模型假设模型假设1 连续化，即设生产周期 T 和产量 Q 均为连续量；2 产品每日的需求量为常数 r ；3 每次生产准备费 C1，每日每件产品存贮费 C2；4 生产能力为无限大（相对于需求量），当存贮量 降到零时，Q件产品立即生产出来供给需求，即 不允许缺货。模

8、型建立模型建立总费用与变量的关系总费用=生产准备费+存贮费存贮费=存贮单价*存贮量存贮量=？设 t 时刻的存贮量为 q(t) ，t = 0时生产 Q 件，存贮量 q(0) = Q , q(t) 以需求速率 r 线性递减，直至q(T) = 0，如图。q(t) = Q- r t， Q = r T 。otqQTrA不允许缺货模型的存贮量不允许缺货模型的存贮量q q( (t t) ) 存贮量和存贮费的计算存贮量和存贮费的计算一个周期内存贮量dttqT0)(一个周期内存贮费dttqcT02)(2QT(A的面积)一个周期的总费用dttqccCT021)(2222121rTccQTcc每天平均费用221rT

9、cTcTCTC)(2 21rTcTcTCT)(min满足求模型求解模型求解用微分法02221rcTcTC)(rccT212212crcrTQ每天平均最小费用rccC212著名的 经济订货批量公式（经济订货批量公式（EOQ公式）公式）。结果解释结果解释rccT212212crcrTQrccC212当准备费 c1 增加时，生产周期和产量都变大；当存贮费 c2 增加时，生产周期和产量都变小；当日需求费 r 增加时，生产周期变小而产量变大。这些定性结果符合常识，而定量关系（平方根，系数2 等）凭常识是无法得出，只能由数学建模得到。rccT212rccC212100010 10015000 21CTrc

10、c，得当,这里得到的费用C与前面计算得950元有微小差别，你能解释吗？在本例中敏感性分析敏感性分析讨论参数rcc,21 有微小变化时对生产周期T 影响。由相对变化量衡量对参数的敏感程度。T 对c1 的敏感程度记为),(1cTS111ccTTcTS ),(TcdcdT11Tcrccrc1212222121212),(cTS21),(rTS意义是当准备费增加1%时，生产周期增加0.5% ；而存贮费增加1%时，生产周期减少0.5% ；日需求量增加1%时，生产周期减少0.5% 。211),(cTS212),(cTS21),(rTS当rcc,21 有微小变化对生产周期影响不太大。思考思考 建模中未考虑生

11、产费用（这应是最大一笔费建模中未考虑生产费用（这应是最大一笔费 用），在什么情况下才可以不考虑它？用），在什么情况下才可以不考虑它？ 建模时作了建模时作了“生产能力无限大生产能力无限大”的简化假设，如的简化假设，如 果生产能力有限，是大于需求量的一个常数，果生产能力有限，是大于需求量的一个常数， 如何建模？如何建模？模型假设模型假设1 连续化，即设生产周期 T 和产量 Q 均为连续量；2 产品每日的需求量为常数 r ；3 每次生产准备费 C1，每日每件产品存贮费 C2；4 生产能力为无限大（相对于需求量），允许缺 货，每天每件产品缺货损失费C3 ，但缺货数量需 在下次生产（订货）时补足。问题问

12、题2 允许缺货的存贮模型允许缺货的存贮模型模型建立模型建立总费用总费用=生产准备费生产准备费+存贮费存贮费+缺货损失费缺货损失费存贮费存贮费=存贮单价存贮单价*存贮量存贮量缺货损失费缺货损失费=缺货单价缺货单价*缺货量缺货量存贮量存贮量=？，缺货量？，缺货量=？因存贮量不足造成缺货，因此 q(t) 可取负值， q(t) 以需求速率 r 线性递减，直至q(T1) = 0，如图。q(t) = Q-r t， Q = r T1 。otqQTrA允许缺货模型的存贮量允许缺货模型的存贮量q q( (t t) ) RT1BR：每个：每个周期的周期的供货量供货量一个周期内缺货损失费一个周期内存贮费dttqcT

13、102)(212QTcdttqcTT13)(213)(TTQrTcrQrTc223)(rQc222一个周期的总费用rQrTcrQccC2223221)(每天平均费用rTQrTcrTQcTcQTC2223221)(),(使求,QT模型求解模型求解用微分法 令332212cccrccT323212ccccrcQ每天平均最小费用),(QTCCrTQrTcrTQcTcQTC2223221)(),(min0 0QQTCTQTC),(,),(每个周期的供货量TrR332212cccrccrR332ccc 与不允许缺货模型相比较，有QRQQTT ,/,QRQQTT ,/,结果解释结果解释QRQQTT 1,即

14、允许缺货时，周期和供货量增加，周期初的存贮量减少。2）缺货损失费愈大， 愈小， 愈接近 ， 愈接近 。1）TTRQ , Q332ccc 3），时，当13cQRQQTT ,不允许缺货模型可视为允许缺货模型的特例。不允许缺货模型可视为允许缺货模型的特例。 一个饲养场每天投入一个饲养场每天投入4元资金用于饲料、元资金用于饲料、设备、人力，估计可使一头设备、人力，估计可使一头80 公斤重的生猪每公斤重的生猪每天增加天增加2公斤。目前生猪出售的市场价格为每公公斤。目前生猪出售的市场价格为每公斤斤8元，但是预测每天会降低元，但是预测每天会降低0.1元，问该厂什元，问该厂什么时候出售这样的生猪为佳。如果上面

15、的估计么时候出售这样的生猪为佳。如果上面的估计和预测有出入，对结果有多大影响。和预测有出入，对结果有多大影响。例例2 生猪的出售时机问题生猪的出售时机问题问题分析问题分析 投入资金可使生猪体重随时间增长，但售价（单价）随时间减少，应该存在一个最佳的出售时机，使获得利润最大。这是一个优化问题。模型假设模型假设决策变量为时间 t，目标函数为利润函数Q每天投入4元资金使生猪体重每天增加常数 r 公斤(r = 2)；生猪出售的市场价格每天降低常数 g 元(g = 0.1)。符号说明符号说明设第 t 天生猪体重为w(t)公斤， t 天投入的资金为C(t)元，纯利润Q(t)元，出售收入R(t)，单价p(t

16、)(元/公斤)。rttw80)(gttp8)(tCtwtpR4 ),()(纯利润函数808CRtQ )(8084880tgtrt)(其中10 2.,gr求t，使)(maxtQ模型建立模型建立模型求解模型求解这是二次函数求最大值问题。用代数法和微分法最大。时，可使得当Qrggrt2404，时，当1010 2tgr.,即10天后出售，可得最大纯利润为20 元。敏感性分析敏感性分析由于模型假设中的参数（生猪每天体重的增加量 r 和每天价格降低量 g ）均为估计和预测的，所以必须研究它们变化时对结果的影响。1）设每天价格降低量 g =0.1元不变，研究 r 变化时的影响作用。51 6040.,rrrt

17、t 是 r 的增函数。rrttrtS ),(trdrdt36040602rr即当每天生猪体重增加1%时，出售时间推迟3% 。2）设每天生猪体重的增加量 r =2 公斤不变，研究 g 变化时的影响作用。0.15g0 203,ggtt 是 g 的减函数。ggttgtS ),(tgdgdt3203310 .gg即当生猪价格每天降低量 g 增加1%时，出售时间提前3% 。当gr, 有微小变化对模型结果影响不太大。强健性分析强健性分析建模过程中假设了生猪体重的增加和价格的降低都是常数，由此得到的 w 和 p 都是线性函数，这是对现实情况的简化。更实际的模型应考虑非线性和不确定性，如)(tww )(tpp

18、 8084ttwtptQ)()()(由微分法，最优解应满足4)()()()(twtptwtp出售的最佳时机是保留生猪直到利润的增值等于每天投入的资金为止。本例中是估计的，只要它们变化不大，上述结论可用。，2 10wp,.另外，从敏感性分析，3),( rtS所以若，以内)%(.102281 w则结果应为).%(以内30137 t注：注：对优化模型，进行敏感性和强健性分析是很有对优化模型，进行敏感性和强健性分析是很有必要的。必要的。森林失火了！消防站接到报警后派多少队员前去救火？派的队员越多，森林的损失越小，但是救援的开支会越大，所以需要综合考虑森林损失费和救援费与消防队员人数之间的关系，以总费用

19、最小来决定派出队员的数目。例例3 森林救火问题森林救火问题问题分析问题分析特点：问题中没有任何数据与问题相关的因素：损失费：救援费：森林烧毁的面积，失火到救火，救火到灭火的时间消防队员的数目消防队员的人数，消防设备，消防用品消耗灭火时间的长短。模型假设模型假设1 时刻 t 森林烧毁的面积为。)(tB2 损失费与森林烧毁的面积成正比，比例系数 ,1c表示烧毁单位面积的损失费。3 从失火到开始救火这段时间 内，火 势蔓延程度与时间 t 成正比，比例系数 表示 火势蔓延速度。可解释如下：则dttdB )(表示火势蔓延的程度。)(10tt 火势以失火点为中心，以均匀速度向四周呈圆火势以失火点为中心，以

20、均匀速度向四周呈圆形蔓延，所以蔓延的半径形蔓延，所以蔓延的半径 r 与时间与时间 t 成正比。而成正比。而烧毁面积烧毁面积B与与 r2 成正比，故成正比，故 B与与 t2 成正比，从成正比，从而而dttdB )(与与 t 成正比。成正比。 派出消防队员 x 名，开始救火以后 火 势蔓延速度降为 其中 可视为每 个队员的平均灭火速度。显然， 。)(1tt ,xx 每个消防队员单位时间的费用 ，每个队员 的救火费用是 ；每个队员的一次性补 贴为 。2c)(122ttc3c模型构成模型构成损失费损失费 = 火势自由蔓延时的损失费火势自由蔓延时的损失费 + 有灭火时的损失费有灭火时的损失费根据假设，d

21、ttdB )(与 t 的关系，如图otdttdB )(t1t2bxdtdtdBtBt202)(221bt)(1212121ttbbtxbtt12)(xbbt2221森林损失费)(21tBc救援费 =救火费 + 消防队员个人补贴费救火费 =)(122ttxc消防队员个人补贴费 =xc3救火总费用xcxbxcxbcbtcxC32211122)()(归结为求x的值，使得)(minxC模型求解模型求解用微分法，得应派出的队员人数为2322122cbcbcx使得，总损失最小为)(xC结果解释结果解释应派出的队员数目由两部分组成，其中一部分为是为了把火扑灭的最低限度。结果解释结果解释另一部分是在最低限度之

22、上的人数，与问题的各个参数有关。当队员灭火速度和救援补贴费用系数减少时，队员数增加；当火势蔓延速度、开始救火时的火势b及损失费用系数c1增加时，队员数目增加。考虑：c2增加时，队员数目也增加，是否合理？2322122cbcbcx思考思考在森林救火模型中，如果考虑消防队员的灭火速度 与开始救火时的火势b有关，试假设一个合理的函数关系，重新求解模型。讨论题1）最优下料问题）最优下料问题用已知尺寸的矩形板材加工半径一定的圆盘。给出几种加工排列方法，比较出最优下料方案。讨论题思考：思考： 用已知尺寸的矩形板材（或某一形状的板材）加工半径一定（两种以上）的圆（不一定为圆）盘。 给出最优下料方案。最优捕食

23、策略最优捕食策略运输问题运输问题点菜问题点菜问题旅行商问题旅行商问题（五）线性规划模型举例（五）线性规划模型举例实例实例1 最优捕食者策略最优捕食者策略 假设存在一种捕食者，穴居假设存在一种捕食者，穴居A处，在处，在B和和C处有两个食物处有两个食物源源X、Y。捕食者从巢穴。捕食者从巢穴A到区域到区域B和和C带回一单位的食物所需带回一单位的食物所需的时间估计为的时间估计为2分钟和分钟和3分钟。捕食者在区域分钟。捕食者在区域B平均花平均花2分钟捕分钟捕获一单位食物获一单位食物X，而在区域，而在区域C只花只花1分钟就捕获一单位食物分钟就捕获一单位食物Y。一单位一单位X所产生的热量估计为所产生的热量估

24、计为25焦耳，一单位焦耳，一单位Y所产生的热量所产生的热量估计为估计为30焦耳。假设捕食者每天不可超过焦耳。假设捕食者每天不可超过120分钟用于从巢穴分钟用于从巢穴到食物区来回行走，同时每天不可能花到食物区来回行走，同时每天不可能花80分钟以上搜寻食物。分钟以上搜寻食物。估计捕食者每天能获得的最大热量值是多少？估计捕食者每天能获得的最大热量值是多少？一单位实物一单位实物行走时间行走时间( (分钟分钟) )捕获时间捕获时间( (分钟分钟) )热量热量( (焦耳焦耳) )X2225Y3130 假设捕食者每天能得到 x 单位的食物 X 和 y 单位的食物 Y ，则每天获得的热量值为.,.max008

25、02120323025yxyxyxtsyxuxyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳焦耳图解法图解法设有某物资从设有某物资从m个发点个发点A1,A2,Am输送到输送到n个收点个收点B1,B2,Bn，其中每个发点发出量分别为其中每个发点发出量分别为 每个收点输入量分别每个收点输入量分别为为 ，并且满足，并且满足从发点从发点A到收点到收点B的距离（或单位运费）是已知的，设的距离（或单位运费）是已知的，设为为 。一个调运方案主要由一组从发。一个调运方案主要由一组从发点点 到收点到收点 的输送量的输送量 来描述。来

26、描述。问题：问题：寻求一个调运方案，使总运输费用达到最小。寻求一个调运方案，使总运输费用达到最小。maaa,.,21nbbb,.,21minijjiba1),.,.,(njmicij2121iAjBijx实例实例2运输问题运输问题B1 B2 . BnA1A2Ama1a2am b1 b2 . bn.X11 X12 . X1nX21 X22 . X2nXm1 Xm2 . Xmn收点收点发点发点总的费用总的费用njjjnnjxCxCxCxCBA11111121211111.njjjnnjxCxCxCxCBA12222222221212.minjijijxCf11A1A1的总费用的总费用A2A2的总费

27、用的总费用s.t.njmixnjbxmiaxijmijijnjiij,.,.,.,.,.,.,21210212111minjijijxCf11min数学模型数学模型求解：单纯形方法。实例实例3 点菜问题点菜问题 我们在餐馆中点菜，我们在餐馆中点菜， 需要包含某些营养成需要包含某些营养成份，但同时又希望总价格最低。下表是这个餐份，但同时又希望总价格最低。下表是这个餐馆的部分菜单，请你提供合理的选菜方案。馆的部分菜单，请你提供合理的选菜方案。序号序号菜单菜单价格价格(元元 )蛋白质蛋白质淀粉淀粉维生素维生素矿物质矿物质1菜肉蛋卷菜肉蛋卷1810112炒猪肝炒猪肝21.501013色拉色拉12.50

28、0104红烧排骨红烧排骨2310005咖喱土豆咖喱土豆10.501006清汤全鸡清汤全鸡321001建模建模设设xi 表示点序号为表示点序号为i 的菜，则的菜，则目标函数：目标函数：约束条件：约束条件：1 0,1111. .6216213152641orxxxxxxxxxxxxxts654321325 .10235 .125 .2118minxxxxxxz求解求解注：注：0-10-1规划问题至今尚无好的算法，目前使规划问题至今尚无好的算法，目前使 用的算法在很大程度上依赖于穷举法。用的算法在很大程度上依赖于穷举法。下面用下面用Mathematica 软件，求得结果：软件，求得结果：18, 21

29、.5, 12.5, 23, 10.5, 321., 0, 0, 0, 1., 028.5Input c=18,21.5,12.5,23.10.5,32 A=1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,0,1 b= 1,1,1,1 result=LinearProgrammingc,A,b z=c.result进一步考虑进一步考虑如果至少点四个不同的菜，结果又如何？如果至少点四个不同的菜，结果又如何？1 0,41111. .6216543216213152641orxxxxxxxxxxxxxxxxxxxts654321325 .10235 .125 .

30、2118minxxxxxxz1., 0, 0, 0, 3., 0利用利用mathematica 软件，得软件，得这显然不是我们想要的结果。这显然不是我们想要的结果。Input c=18,21.5,12.5,23.10.5,32 A=1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,1 b= 1,1,1,1,4result=LinearProgrammingc,A,b z=c.result18, 21.5, 12.5, 23, 10.5, 3249.5点菜点菜价格（元）价格（元）点菜点菜价格（元）价格（元）1,2,3,6844,5

31、,3,267.54,2,1,694.54,5,3,6784,5,1,236,5,1,2824,5,1,683.56,5,3,1734,5,3,1646,5,3,276.5利用穷举法，得利用穷举法，得实例实例4 旅行商问题旅行商问题(Travelling Saleman Problem）TSP某商人由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。建模建模TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,n问题就转化为：,21niii21,n,nkkk,iid01)(

32、其中 为城市 到 的距离，最小。)(1kk,iidki1ki010nii求一个 的排序 使得TSP的数学规划形式：的数学规划形式：ijjiijxdmin 1or 0)1(111 ts00ijijjinjijniijxjn,ii,jnnxuuxx.表示进入且仅进入城表示进入且仅进入城 j 一次一次;表示离开且仅离开城表示离开且仅离开城 i 一次一次;保证连通性。保证连通性。其中其中 表示若该旅行商在访问城表示若该旅行商在访问城 i i 后接着访问城后接着访问城 j j ，则令则令 ，否则令，否则令),(0 ni,jxij1 ijx0 ijx模型求解模型求解1 穷举法穷举法21,n,的不同排序有

33、个，当n稍大!n时，很难找出最佳答案。这是个NP-完全问题。2 近似算法近似算法 贪婪算法贪婪算法西德曾对一个有西德曾对一个有318318个点的问题找到了最优方案。个点的问题找到了最优方案。3 利用数学软件利用数学软件 一个送报员从送报中心出发到五个小区一个送报员从送报中心出发到五个小区送报，最后要回到送报中心。送报中心到各送报，最后要回到送报中心。送报中心到各小区的距离及各小区间的距离均已知（见表小区的距离及各小区间的距离均已知（见表1），问送报员应按怎样的线路行驶较好？），问送报员应按怎样的线路行驶较好？（距离单位为千米）（距离单位为千米）送报线路安排送报线路安排表表1 1 送报中心及各小

34、区间的距离送报中心及各小区间的距离01234500745861703109142430591035105014948991407561410970起起终终01234500745861703109142430591035105014948991407561410970贪婪算法贪婪算法送报中心及五个小区分别用送报中心及五个小区分别用0 0，1 1，2 2，3 3，4 4，5 5来记。来记。算法的中心思想：算法的中心思想：每次寻找最小距离每次寻找最小距离 。起起终终01234500745861703109142430591035105014948991407561410970起起终终21301234

35、500745861703109142430591035105014948991407561410970起起终终021433050214330501234500745861703109142430591035105014948991407561410970起起终终4570214330501234500745861703109142430591035105014948991407561410970起起终终4570214330501234500745861703109142430591035105014948991407561410970起起终终457990123450074586170310914

36、2430591035105014948991407561410970起起终终0214530439795总距离：37千米。（六）线性规划问题的求解（六）线性规划问题的求解Tnxxxx),.,(321x0 xbxxxAtsCfLPT.)(min)()()(nmaAnmij TnccccC),.,(321),.,(nbbbb321b线性规划的标准提法bxxxAtsCfLPT .)(min)(线性规划的常见提法两种提法是等价的，可以通过引入“松弛变量”将不等式约束化为等式约束。可行域满足约束条件的 称为可行解，可行解的集合称为可行域。x1 主要性质主要性质性质1(LP)的可行域 是凸多面体。,0 xb

37、xx As可行域的顶点是重要的点。ox1x2ABox1x2Ax1x2x3ABC设矩阵 的秩为 m，A 的 m 个列构成的方阵AB称为(LP)的一个基， AB的列向量称为基列，相应于基列的变量称基变量。),()()()(naaaA21),()()()(mBaaaA21TmBxxx),(21x),()()()(nmmNaaaA21TnmmNxxx),(21x非基列非基变量)(nmAnm NBNBAAAxxx),(NNBBAAxx b)(NNBBAAxbx1NBxxxNNNBAAxxb)(101bxBAbx A的解称为(LP)的基本解称为基本可行解。 01xb,BA性质2是(LP)的可行域的顶点等价

38、于 x是(LP)的基本可行解。x引理。则的所有顶点，记为有界可行域设SRRASiPiiPiiin 0 10 0021,)()()()(xxxxb,xxxxx定理如果(LP)存在最优解，则最优解一定在可行域的顶点取得。证明当可行域有界时，设 是可行域S所有顶点中使目标函数 取最小的顶点，即 ，任取 ，则由引理得 ，故)(0ixxxTCf)()()(0iTiTCCxxSxRxPiii0,)(xxxxTCf)(PiiiTC0)(xPiiTiC0)(xPiiTiC00)(xPiiiTC00)(x)()(0if x)(min)()(xxxffSi0证毕2单纯形法单纯形法单纯形法是通过迭代来求最优解的一个

39、方法。在一个基本可行解非最优时，确定一个更优的一个基本可行解，形成一个使目标函数单调减的基本可行解序列 ，经有限步即可求得最优解。基本思想,)()(21xx的一个基，为，设AAAAABNB),( 构成可行域。的则使得 0 1xxxbxNNNBAA)(的基本可行解，为相应于基记BBAA0 1bx，记),(),(TNTBnCCCCCC21 01bxxBTNTBTACCCf),()(b1BTBACNNNBTNTBTAACCCfxxbxx)(),()(1NTNNNBTBCAACxxb)(1NNBTBTNBTBAACCACxb)(11)(xfb1BTBAC为最优解，则若 0 1xxNNBTBTNAACC

40、)(否则， 不是最优解。x，若0 1NNBTBTNAACCx)(),()()(nBmBNBNaAaAAAA1111 记),()()(nmaa1)(NBTBTNTNAACCC1),(nmcc1其中,)(nmNiaCcciTBii1令,miniNipcc，继续。为最优解，若停止，若0 0 ppccx（1）取相应的分量 、相应的列 为入基变 量、入基列。px)(pa（2）选出基向量。令TpNx),(0000 x则NNBBBAAAxbx11ppxa)( bppBTBpBpxcCfxa)()(xxx可行域无界，且增加而单调增加，随，则若 0 此时(LP)无解。 0 ，要保证有正分量若Bpqpaax)()

41、( 0个分量的第时，当qababxBpiiapqqppix)()(min)( 0 ，其余分量均为正。ppqqqxabx)( 为出基变量、出基列。、取)(qqax，得新基和的交换BqpAaa)()(ATqqpBBeaaAA)()()()(），个元素），（第，（其中010 qeTq)()(的基本解为相应于BA,)()(mBiaabbpipqqii21 ，x:xpiNixabxipqqp,)( 0,nmN1为可行解，故为基本可行解。且)()(xxff例54321 0 21543212524232221151413121151,.)(min)(ixbbxxxxxaaaaaaaaaatsxcCfLPiiiiTxx215432524231514132122211211bbxxxaaaaaaxxaaaa5432524231514131222112112112221121121xxxaaaaaaaaaabb