《第一章线性规划引言》由会员分享，可在线阅读，更多相关《第一章线性规划引言（30页珍藏版）》请在金锄头文库上搜索。
1、最优化方法一、引言最优化理论与方法是一门应用性很强的年轻学 科。它研究某些数学上定义的问题的最优解，即对于 给出的实际问题，从众多的方案中选出最优方案。虽然最优化可以追朔到十分古老的极值问题，然 而，他成为一门独立的学科诗在上世纪 40 年代末， 是在 1947 年 Dantzing 提出求解一般线性规划问题的 单纯型法之后。现在，解线性规划、非线性规划以及 随机规划、非光滑规划、多目标规划、几何规划、整 数规划等各种最优化问题的理论的研究发展迅速，新 方法不断出现，实际应用日益广泛。在电子计算机的 推动下，最优化理论与方法在经济计划、工程设计、 生产管理、交通运输等方面得到了广泛应用，成为一
2、 门十分活跃的学科。现在大多数有代表性的最优化算法已有可以方便使用的软件包，如lindolingo优化软件包。但有效利用这些成果是以有待解决的问题已被模型化成最优 化问题的形式为前提的。要做到这点，要有深刻的洞 察力和综合能力，这需要掌握最优化算法的结构和特 点，并与专业知识的结合和兼蓄。最优化有着丰富的内容和方法，本课我们主要介绍线性规和非线性规划的主要方法与理论他们是最 优化理论的重要分支，也是最基本的部分。第一部分：线性规划第一章：单纯型法 第一节问题的引出:例 1：某制造公司需要生产 n 种产品，生产这 n 种 产品需要m种不同的原材料，第i (i=1,2,m。种 原材料的拥有量为b.
3、。实际情况很复杂，我们将其简 i化或理想化，只关注某个时间点的特定情况，第 i 种 原材料在某时间点的市场价格为P .，生产单位数量的 第j种产品需消耗第i种原材料a.个单位。第j种产 ij品在同一时间点上的市场价格为a。j考虑问题一：如何安排1，2,n种产品的生产, 从而使收益最大设第 j 种的产量为 x 单位,第 j 种产品的收益与市 场销售价。有关，也与生产第j种产品所消耗的原材 i料费用 p有关，因此第j种单位产品的纯收入为i j ii=1c =c -Ya p，全部纯收入工cx，此时x 0。jjij ij jji=1而我们不可能超出原材料的拥有量生产产品。生产n种产品时，所消耗的第i
4、(i=1,2,m。种原材料的总量为ax +i 1 1a x + + a xi 2 2 in naxij jnx ax bi = 1 mij j ij =1综上所述，我们为达到收益最大，就建立了这样的数学规划问题：max 工 c x = c x + c x HF c xj j 1 12 2n nj=1st 工 a x = a x + a x HF a x 0 j = 1 n这是一个资源配制问题(资源分配问题)，也是一 个线性规划问题。从另一种角度考虑上述问题：假若由于某种原因，该制造单位打算放弃这些生产项目，而另一家企业希望收购这些资源。那么如何 确定这m种原材料的转让价格，同时照顾到买卖双方
5、的利益使买卖有可能成交？设这m种原材料的单位定价为33。1m全部损失机会成本为iii=1定价要不低于市场获利,即mwa c ,j = 1 ni i jj。i=1m是当前市场价格的提升价格，全部机会损失值变为另byii i=1约束 2 ya ci ijji=1y0从卖方角度看，希望以尽可能低的价格收购这些资源，即总费用最小，于是得到min 2byiiyai ijcj(2)y0这两个角度考虑问题得到了两个线性规划问题（LP问题）前例问题中，有些变量决定了问题的最优值，称为 决策变量，LP问题中总是要求极大化或极小化由决策变量构成的线性函数，此函数称为目标函数。第二节：线性规划问题的标准型 (sta
6、ndard form)A线性规划问题的标准型LP的标准型是指如下形式的优化问题min 艺 c xjjj=1(3)+ x =b n n +i is.t为 a x = bij j ij=1x 0,j = 1 nj例如(1)(2)都很容易化成标准型先看(1),引入变量X”+iSm，使a x + a x + a xi1 1 i 2 2in则有min 工(-c ) xjjj=1s.t工 a x + x = bij jn+iii=1xx x x x12 nn+1n+mx x此时 n+1n+m 称为松弛变量。对（2）l!GSFi Cj增加变量yy使y ym+1m+ nm工 ay y=cij im+ j j
7、，i=1y y此时m+1m+ n 称为剩余变量。由此看任一个 LP 问题都可以化为标准型（3）。 前面对不等式约束化成了等式约束再看决策l=Jl=lx = P x 0jjj若 x a = x a 0jjja x P a x , x 0, x 0jjj1j 2j1j 2一组取定的决策变量的值称为一个解。S = x = (x x )T1n在（3）中，记a x = b ,x 0, j = 1 nij j i jj=1为可行域。x & S称为（3）的一个可行解。则称 x若存在X* E S使Vx w S，都有ex* cx ,是（3）的最优解。当S =0时，问题（ 3）无可行解，称（ 3）是不可行的。mi
8、n5 x + 4 xs.t12x + x 2122x 2x 012另一种极端的情形是称为无界的情况，即对任意大的目标值都有解。min x + 4 x12s.t2x + x W112 x 2 x W 21 2 ，x ,x 0121解(x , x ) = (x ,0),xl 2可以任意大。1 2 1 1 2B线性规划问题的图解法当n 3时的线性规划问题可以用图解法求其最优解。例 2：求解下列 LP 问题min x 3 x12s.t x + x 6 12x + 2 x 012例 3：maxz = c x + x1 1 2s . tx+x612x+2x012试用图解法分析问题的最优解随C1(7 C1
9、+Q , 取值的不同的变化情况。C1值对应的Vf (x)最优值点c = 1y1f(x)= (1,1)AB线段1c = V1 2f ( x) = (1,1)BC线段11 c 1v 2 1f ( x) = (1,1)B(2, 4)1-8 c 1 2Vf(x)=(1,1)C(0,6)1 c +81Vf(x)=(1,1)A(0,6)C线性规划的图表法(单纯形图表法)例 4：min 5x 4x 3x123s.t 2x + 3 x + x 51234 x + x + 2 x 111233 x + 4x + 2 x 0123解：引入松弛变量将原问题化为标准形min f = 5x 4x 3x123st 2 x
10、 + 3 x + x + x =512344 x + x + 2 x +x =11(4)12353 x + 4 x + 2 x +x = 81236x,x , , x 01 2 6。益k吆-乂塞以W OAIIKE 8H0乂寸 乂9 5 寸 Ed I。职密甲盅廉乂匚是叹职乂汕 。敝酒甲口 j廿赵密泪 蔬倏邑o.泪迪 5/保证各决策变量的非负性，需满足+ x3 0.5，得3x = y 一 0.5x 0 I x 51/23 3 二 X 0，即 I x 136/231 30 T1，此时 x = 0 o6得到改善解(x ,x ,x ,x ,x ,x ) = (2,0,1,0,1,0)。在(5)123456式中将x变为单位变量，且目标函数行视为同样地位3化简。l=Jl=l3 最大能由minf = 13+3 x +x + x2 4 6x + 2 x + 2+2 x x = 21 2 4 6得到-5 x 一2 x + x =12 4 5x + x 一 3 x + 2 x = 1 2346再看如何改善由目标行看到X , x , x前的系数均246为正，而X ,X ,X的取值已达到下界，所以f已不能再246获得改善，即达到最优。其最优解是 (2,0,1,0,1,0) ，所求原问题的最优解为(2,0,1
