线性规划综合案例,总结,例1:某工厂 用甲、乙两种原料生产A、B、C、D四种产品，每种产品的利润、现有的原料数及每种产品消耗原料定量如表问题1,怎样组织生产，才能使总利润最大？,解：设生产A、B、C、D产品各X1， X2， X3， X4万 件，数学模型为：max S=9x1+8x2 +50x3+19x4 3x1+2x2 +10x3 + 4x4 182x3+(1/2)x4 3 x1，x2 ， x3 ， x4 0,问题2,写出该线性规划的标准形式,化成标准型max S = 9x1+8x2 +50x3+19x4 3x1+2x2 +10x3 + 4x4 + x5 = 182x3+ (1/2)x4 + x6 = 3 x1,x2,x3, x4 ,x5 ,x6 0,问题三,应用单纯形法解算该线性规划问题列出初始单纯形表）,初始基 B1=（P5，P6）,第二行除以2,第一行加上第二行的（-10）,B3=（P1，P3）第一行除以3,B3=（P1，P3）,B4=（P2，P3）第一行乘以（3/2）,第一行乘以（4/3）,B5=（P4，P3）第二行减去第一行1/4倍,最优基 B5=（P4，P3） 最优解=（0，0，1，2） S = 88,问题4,对比初始单纯形表和最终单纯形表；找出基矩阵B；非基矩阵N；B的逆矩阵B-1。
初始基 B1=（P5，P6）,最优解: X=（0，0，1，2） 最优值：S = 88,最优基 B5=（P4，P3）,对应原松驶变量的位置即为B-1,,初始表,最优表,（A,I）= 3 2 10 4 1 00 0 2 1/2 0 1,,B= 4 101/2 23 2 N= 0 01 0 I= 0 1,,,,B-1（A,I)= 2 4/3 0 1 2/3 -10/3-1/2 -1/3 1 0 -1/6 4/3B-1（N,B,I)= 2 4/3 0 1 2/3 -10/3-1/2 -1/3 1 0 -1/6 4/3,,,B-1N= 2 4/3-1/2 -1/31 0 B-1B= 0 12/3 -10/3 B-1I= -1/6 4/3 =B-1,,,,问题5,写出该线性规划的对偶问题,解：原问题：Max S=9x1+8x2 +50x3+19x4 3x1+2x2 +10x3 + 4x4 182x3+(1/2)x4 3 x1，x2 ，x3 ，x4 0对偶问题：Min W=18y1+3y23y1 ≥92y2 ≥810y1+2y2 ≥504y1+0.5y2 ≥19y1,y2 ≥0,问题6,已知原问题的最优解为X=(0,0,1,2);试应用松紧定理求对偶问题的最优解。
要求写出计算步骤，并进行必要说明）,解：1、因为原问题有最优解，因此其对偶问题也一定有最优解2、因为X3=1;X4=2 均不为0，因此根据松紧定理可知其对偶问题要达到最优解的充要条件是其第3、第4个约束条件中的松弛变量Y3、Y4均0因此有：10y1+2y2 =50 4y1+0.5y2 =19 解方程组得到：Y1=13/3；Y2=10/3 对偶问题最优解为Y*=（13/3,10/3),问题7,若A、C产品的利润产生波动，波动范围多大，最优基不变？ 1、目标函数中C1=9在多大范围内变化，原问题最优解不变？ 2、目标函数中C3=50在多大范围内变化，原问题最优解不变？,B= 4 10 B-1= 2/3 -10/31/2 2 -1/6 4/3,,,B-1A= 2 4/3 0 1 2/3 -10/3-1/2 -1/3 1 0 -1/6 4/3,,CB=（C4，C3）=（19，50） C=（9，8，50，19，0，0） 当目标函数的C1= 9 有波动，设波动为C1= 9 + a, CB = CB, C=（9+ a ，8，50，19，0，0） 得到检验数的变化为 ：=(-4+a,-2/3,0,0, -13/3, -10/3), =(-4+a,-2/3,0,0,-13/3,-10/3),仅当 -4 + a4时，即每万件A产品的利润超过13万元时，B 已经不是最优基，继续进行最优化。
当a>4时，-4+a>0,第一行除以2,第二行加上第一行（1/2）重新计算检验数，为了保证B为最优，必须满足 6-2a 0 , 4-a 0, -9-a 0, 5a -30 0 得到4 a 6,当4 a 6时，即每万件A产品的利润在13-15万元之间，得到新的最优基=（P1,P3）最优决策方案=（1,0,3/2,0）,最优利润=84+ a，最大利润在88-90之间当目标函数的C3= 50 有波动，设波动为C3= 50 + a, CB = CB, 原最优表如下,当目标函数的C3= 50有波动，设波动为C3= 50+a, CB = CB, 重新计算检验数如下,为保证最优，满足 a-8 0, a-2 0, a-26 0, -10-4a 0得到 -5/2 a 2，即产品C的利润在47.5-52万元之间，原最优决策方案不变，最优利润在85.5-90万元之间同理可以讨论：a 2时，只要X2进基变量问题8,若想增加甲种原料，增加多少时，原最优基不变？ 设b1发生变化，问b1在多大范围内变化，原问题最优解不变？,解：设b1发生了变化a，故b1=18+a， b=( 18+a,3) 2/3 -10/3 18+a 2+(2/3)a B-1 b= -1/6 4/3 3 = 1-(1/6)a,,,,解： 2+(2/3) a 0 , 1-(1/6)a 0 得到：-3 a 6 即 15 b1 24 原最优基不变，但最优解与目标函数最优值都是 a 的函数： X*=（0,0,1- a/6，2+(2/3)a） S*=88+(13/3)a（万元）,当 a >6 , a6 情形：原问题最优基。
2+(2/3)a 用 B-1 b= 1-(1/6)a 代替常数项 因为 a>6， 则1-(1/6) a<0，原始不可行，但是对偶可行用对偶单纯形法求解用对偶单纯形法求解第二行乘以（-3）,用对偶单纯形法求解第一行加上第二行（-4/3）,当-3+(1/2)a 0，即 a>6新的最优基, B,=(P4,P2) 最优解=(0, -3+(1/2) a,0,6) 最大利润=90+4a (万元),问题9,若考虑要生产产品E，且生产1万件E产品要消耗甲原料3公斤，消耗乙原料1公斤那么，E产品的每万件利润是多少时有利于投产？,解：增加变量；设生产E产品X7万件，每万件利润是C7万元，则模型为： max S = 9x1 + 8x2 + 50x3 + 19x4 + C7 x7 3x1+2x2 +10x3 + 4x4 + x5 +3x7 = 182x3+ (1/2)x4 + x6 +x7 = 3 x1,x2, x3 , x4 ,x5 ,x6 , x7 0,A=(P1,P2,P3,P4,P5,P6,P7) P7=(3,1)t 原最优解=(0,0,1,2,0,0) 则 X =(0,0,1,2,0,0,0） 一定是原问题的可行解，但不一定 是原问题的最优解。
若要生产E，在原最优表中增加非基变量X7，其中P7=B-1 P7= 2/3 -10/3 3 = -4/3-1/10 4/3 1 5/6相应的检验数= -49/3 + C7> 0 时，才有利生产 令C7 =17，相应的检验数= 2/3,,,,插入原最优表，继续求解第二行乘以6/5,第一行加上第二行乘以4/3,得到新的最优解= (0,0,0,18/5,0,0,6/5) 最优值=88(4/5)最优方案生产D产品18/5(万件),E产品6/5 (万件) ,利润达到88.8(万元)问题10,假设该工厂又增加了用电不超过8千瓦的限制，而生产A、B、C、D四种产品各1万件分别消耗电4、3、5、2千瓦此约束是否改变了原最优决策方案？,只需在模型中增加新的约束条件： 4x1+3x2 +5x3 + 2x4 8 标准化后有 4x1+3x2 +5x3 + 2x4 + x7 =8 加入模型中：,X4,X3,X7是基变量,使增加一行元素(5)、(2)为零,第三行加上第一行的（-2）倍,第三行加上第二行的（-5）倍,,第三行不可行,第三行乘以（-2）,第一行加上第三行乘以（-2/3）。
第二行加上第三行乘以（1/6）计算检验数得最优表,增加用电约束后，最优生产方案：生产4/3万件C产品，2/3万件D产品，总利润为79.5万元,问题11,对偶解的经济含义是什么？,,如果把线性规划的约束看成广义资源约束，右边项则代表某种资源的可用量 约束条件右端某一常数项增加一个单位而引起目标函数最优值的变化量，通常称为影子价格,对偶解对应于影子价格,证明：在最优解情况下有:z=C X（0）= CBXB（0）= CBB-1b= Y（0）b因为Y（0）是对偶问题的最优解，而且表示随资源量b增加1个单位，目标函数值的变化量 因此，影子价格就是该约束条件相对应的对偶变量的最优值当yi＞0时，当bi增加后，z将增加当yi =0时，当bi增加后，z不会增加 所以可见，影子价格是与原始问题约束条件相联系，而不是与决策变量相联系影子价格的特征,1、影子价格是一种虚拟的价格而不是真实价格,是对系统内部资源的客观估计 2、影子价格是对系统资源的最优估计，只有系统达到最优状态时才可以赋与资源这种价值 3、影子价格的取值受系统状态变化的影响，系统内部资源数量和价格的变化都会引起影子价格的变化，它是一种动态的价格体系。
影子价格的特征,4、影子价格的大小客观反映了资源在系统内的稀缺程度如果某资源在系统内供大于求，尽管它有市场价格，但它的影子价格等于零增加这种资源的供应不会引起系统目标的任何变化如果某资源是稀缺资源，其影子价格必然大于零影子价格越高，这种资源在系统中越稀缺 5、影子价格是一种边际价值，它与经济学中边际成本的概念相同因而在经济管理中有十分重要的价值企业管理者可以根据资源在企业内部影子价格的 大小决定企业的经营策略问题12,如何进行生产经营决策,,由最优单纯形表可知，对偶问题最优解为Y*=（13/3,10/3)，因此系统中资源的影子价格为：资源一的影子价格为13/3，资源二的影子价格为10/3因此若能够在P1= 13/3，P2= 10/3的价格以下适当增加两种资源均可以使企业收益增加。