线性规划理论与模型应用02

《线性规划理论与模型应用02》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容2.1对偶规划2.2对偶定理2.3对偶单纯形法2.4灵敏度分析2.1对偶规划1.食谱问题设有n种食物,各含m种营养素,第j种食物中第i种营养素的含量为aij,所有n种食物价格分别为c1,c2,…,cn,营养素的价格分别为w1,w2,…,wm,要求食谱中m种营养素的含量分别不低于b1,b2,…,bm,食谱中n种食物的数量为x1,x2,…,xn,如下表所示:对偶规划消费者希望费用最低且满足营养要求，则有食谱厂家在确定营养素价格时，希望收益最大且能吸引消费者，则有对偶规划前述的两个规划是同一问题的两个方面:消费者希望费用最低；营养厂家希望收益最大。这一对问题即是我们要研究的线性规划的对偶问

2、题.对偶规划对称形式下对偶规划考虑以下两种形式的线性规划问题对偶规划定义2.1称以上两种形式的线性规划问题为一对对偶线性规划问题，其中LP问题为原规划，LD问题为对偶规划。其矩阵形式表示为其中定义2.2满足下列条件的线性规划问题为成为具有对称形式：变量均具有非负约束；当目标求极小时约束条件均为“”，当目标求极大时约束条件均为“≤”。对偶规划如果将对偶规划(LD)作为原规划，其形式为其对偶规划是即是原规划定理2.1对偶规划的对偶规划是原规划，即LD是LP的对偶规划时，LP也是LD的对偶规划。对偶规划对称形式下原规划和对偶规划转换规则：原规划min问题，对偶规划max问题右端项与目标系数互相转

3、换；系数矩阵互为转置关系；原规划约束条件对应对偶规划的变量‘’约束，对偶规划对应的变量0；原规划的变量对应对偶规划的约束条件变量0，对偶规划中对应的约束为‘≤’约束非对称形式下的特点线性规划问题的约束条件有‘’、‘=’、‘≤’约束，变量中有0、≤0、自由变量对偶规划非对称形式下对偶规划例2.1写出下述线性规划问题的对偶规划对偶规划将约束全变为“”此问题的对偶问题为对偶规划此问题的对偶问题为对偶规划非对称形式下原规划和对偶规划转换规则：原规划min问题，对偶规划max问题右端项与目标系数互相转换；系数矩阵互为转置关系；原规划约束条件‘≤’约束，对偶规划对应的变量≤0；‘’约束，对

4、偶规划对应的变量0；‘=’约束，对偶规划对应的变量无约束(自由变量)；原规划的变量约束0的变量，对偶规划中对应的约束为‘≤’约束；≤0的变量，对偶规划中对应的约束为‘’约束；自由变量，对偶规划中对应的约束为‘=’约束。对偶规划例2.2写出下述线性规划问题的对偶规划2.2对偶定理为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形式的对偶规划同样可证明类似的结论。为方便起见，LP简称为P,LD简称为D。对偶定理1.弱对偶定理定理2.2设x0是P的可行解，w0是D的可行解，则cx0w0b；若x*、w*分别是P、D的可行解且cx*=w*b，则x*、w*分别是P、D的最优解；若P、D中有

5、一个目标函数值无界，则另一个可行域为空集；P、D都有最优解的充要条件是P、D都有可行解。证：1)因为Ax0b，x00，w0A≤c，w00，对Ax0b两边左乘w0则有w0Ax0w0b；对w0A≤c两边右乘x0则有w0Ax0≤cx0；从而有cx0w0b。2)设x0是P的任意可行解，由1)有cx0w*b=cx*从而x*是P的最优解；同样可证w*是D的最优解。用1)的结论可容易证明3)和4)成立。对偶定理2.强对偶定理定理2.3一对对偶规划P和D中的一个有最优解的充要条件是另一个有最优解，且两问题的最优值相等。证：对问题P引入松弛变量v=(xn+1,…,xn+m)T将其变成设该问题的最

6、优解为x*，B为最优基，则有令w*=cBB-1，则有w*是D的可行解又w*b=cBB-1b=cx*，由定理2.2可知w*是D的最优解。对偶定理3.互补松弛定理及其应用定理2.4(互补松弛定理)已知x*,w*分别是P和D的可行解，则它们分别是P和D的最优解的充要条件是w*(Ax*-b)=0,(c-w*A)x*=0证：因为x*,w*分别是P和D的可行解，从而w*b≤w*Ax*≤cx*必要性：若x*,w*分别是P和D的最优解，则w*b=cx*，从而上式中两“≤”号等式成立，显然结论成立。充分性：若w*(Ax*-b)=0，则w*Ax*=w*b，若(c-w*A)x*=0，则cx*=w*Ax*从而cx*

7、=w*b，即x*,w*分别是P和D的最优解对偶定理将互补松弛定理的结论写成如下形式：以上两式表示P规划的约束严格不等号成立(松)时，D规划相应的变量必取0(紧)；D规划的约束严格不等号成立(松)时，P规划相应的变量必取0(紧)，非基变量；第二式也就是λjxj=0(j=1,2,…,n)表示在P规划中检验数与变量互为松弛。对偶定理例2.3求解线性规划问题其对偶问题：对偶定理对偶规划是两个变量的问题可用图解法求解，