线性规划的对偶理论与灵敏度分析习题二

线性规划的对偶理论与灵敏度分析 习题二1题目：写出下列线性规划问题的对偶问题（1） s.t. 解答： s.t. 令 s.t. s.t. (2) s.t. 解： s.t. 令 s.t. s.t. 2 题目 ： 写出下列（P）的对偶问题（D） s.t. 用讨论（D）的方法（不准用单纯形法求解），给出（P）的最优值 解： s.t. 4 显而易见 ，当时，当U1=7/5时，符合条件，即maxz=607/5=84，所以， 因此（D）的最优值为84，根据对偶性定理可知（P）最优值也为84.3、用对偶理论来说明下列线性规划的目标函数无下界：（P） s.t. Xj无限制，j-1,2,3 解：写出 （D） s.t. 由于且，故（D）无可行解而对于（P），显然，故 即目标函数无下界。4设(LP): minCTXAX=b，x0有最优解，又(LP，)： minCTXAX=b，x0有可行解其中bb，试用对偶理论证明(LP，)必有最优解证明：(LP) min f=CTX (LP，) min f，=CTXs.t. AX=b s.t. AX=b，x0 x0(LD) maxZ= bTU (LD，) maxZ，=（b，）TUs.t. ATUC s.t. ATUCU（-，+） U（-，+）（LP）有最优解,根据对偶理论，（LP）和(LD)都有可行解。而(LD)和(LD，)的可行域是一样的。根据已知条件，现在(LP，)有可行解。于是，(LP，)和(LD，)都有可行解，根据对偶理论，(LP，)和(LD，)都有最优解。5、现有一个线性规划问题（P1）：max f1=CTXs.t. AXbx0其对偶问题有最优解 ： U*=（U1* ，Um*）。另一线性规划 （P2） max f2=CTXs.t. AXb+dx0其中d=(d1,dm)T。求证：max f2max f1+dTU*证明 ：分别写出它们的对偶问题(D1)和(D2)minZ1=bTU minZ2=( b+d)TUs.t. ATUC s.t. ATUC (D2) u0 (D1) u0 显然，u*K D2bTU*+dTU*minZ2= max f2而bTU*= max f1于是有max f1+dTU*max f27题目：用对偶单纯形法求解下列线性规划 s.t. 解： s.t. 108某线性规划问题为 max z=c1x1+c2 x2+ c3 x3stAXb X=（x1，x2，x3）0将它化成标准型后可得它的一张单纯形表，如表所示，其中x4，x5为松弛变量。（1） 写出原有线性规划问题；（2） 写出对偶问题；解： 由检验数公式可知： - c2-1/2 c3-1/2 c1=4， 1/2 c3-1/6 c1=4， 1/3 c1=2得c1=6 c2=-12 c3=10。根据表知道：原线性规划 max z=6 x1-12 x2+ x3st- x2 +2 x35 3 x1-2 x2+ x310xj 0 j=1，2，3 对偶问题 min f=5u1+10 u2 st u2 2 u1 +2 u212 2 u1 + u2 10 ui 0 I=1，29.若第一章习题一第1题的标准型的最优单纯形表为。（1） 试问和各在何范围内变动，最优解不变。（2） 若工厂的最优生产计划仍然是两种产品都生产，试分析确定三种资源的变化范围及影子价格。解答： 由(1) 得此时最优解不变 (2) 10 题目： 若习题一中第2题的标准型的最优单纯形表为 解答： 11题目： 某工厂生产两种产品，分别需在A，B，C，D设备上加工有关