《管理运筹学》课件03-对偶原理

1、，第3章，对偶原理，DP，对偶原理，第3章，2，3.1线性规划的对偶关系3.2线性规划的对偶性质3.3对偶关系的经济解释3.4对偶单纯形法3.5交替单纯形法，第3章对偶原理，3，3.1线性规划的对偶关系，3。1.1二元性问题，y1 y2 y3，因为一个A工作小时和三个C工作小时原本打算用来生产每个A产品可以创造300元的利润，租用上述资源的利润至少应该不低于300元。1Y10y23Y33，0Y12y24Y35，w=8Y12Y236Y3，Y1，Y2，y3 0，第3章，对偶原理，4，3.1线性规划的对偶关系，最小w=8y 12y 236y 33y 24y 35y 1，Y2，Y30，s.t .y *

2、=(0，1/2，1) t w *=42，x *=(4，6) t，z *=42，第3章，对偶原理，5，3。1.2对偶性关系，关系1第3章对偶性原理，6，3.1线性规划的对偶性关系，1Y10y23Y33，0Y12y24Y35，最小W=8Y12Y236Y3，Y1，Y2，y3 0，s.t .最小类型，第3章对偶性原理，7，3.1线性规划的对偶性关系，关系2:第3章对偶原理，8，3.1线性规划的对偶关系，示例1最大Z=3x1-1x2-2x3 3x1 2x2-3x3=61x1 9，3.1线性规划的对偶关系，关系3:一般对偶关系，第3章对偶原理，10，3.1线性规划的对偶关系，例2，最大Z=2Y 15Y 2

3、1Y 32Y 31 Y1-5Y 21Y 323 Y1 3-1，=，Y10，Y20，Y3 Free，S.T .解，第3章对偶原理，11，3.2线性规划的对偶性质2的弱对偶假设x和y分别是(P1)和(D1)的任意可行解第三章，对偶原理，12，3.2线性规划的对偶性质，以及(P1)和(D1)的线性规划的性质4对偶定理：(1)如果一个问题有最优解，另一个问题也有最优解，且最优值相等。(强对偶)(2)如果一个问题的解是无界的，那么另一个问题就没有可行的解。(无界)注：(2)的逆命题不成立。因为当一个问题没有可行解时，另一个问题可能有无界解或没有可行解。第三章，对偶原理，13，3.2线性规划的对偶性质，性

4、质5，相容原生问题的测试向量，给出了对偶问题的基本解。x *=(4，6，4，0，0) t，z *=42，y1，y2，y3，y4，y5，y *=(0，1/2，1，0，0) t，w *=42，3，4，5，0。14，3.2线性规划的对偶性质，x *=(4，6) t，y *=(0，1) t，* b (4，6，4，0，0) t，*=(0，1，0) t，我们称之为这样一对基本解和(p)与(d)的互补基本解。，第3章，对偶原理，16，3.2线性规划的对偶性质，6。互补松弛让=(x1，x2，xn，xn1，xnm) t=(y1，y2，ym，ym1，ymn) t是(P1) (D1)的一对互补基本解。J=1，2，n

5、 xnyi=0，i=1，2，m特别适用于非退化和。如果可行，则存在xj 0 ym j=0，j=1，2，n xnyi=0，i=1，2，m如果可行，则存在YMJ 0XJ=J=1，2，n yi 0 xn i=0，I=1，2，m，第3章，对偶原理，17，3.2线性规划的对偶性质，7。互补松弛假设是(P1) (D1)的可行解，则和是(P1) (D1)的最优解，当且仅当：Xni0yi=0yi0xni=0，xj0ymj=0ymj0xj=0，j=1，2，n，I=1，2，m，第3章，对偶原理，18，3.3对偶关系的经济学解释，根据对偶性质，线性规划的互补基本解的目标函数值z=cjxj bi yi=w， 求出z相

6、对于bi的偏导数，得到，=yi，可以看出对偶变量yi在经济上代表了原问题第I个资源的边际值，即当bi单独增加一个单位时，相应目标值z的增量z； 特别是对于最优解，用对偶变量的值yi*表示的第I个资源的边值称为影子值。等于：=，z，第3章二元性原理，19，3.3二元关系的经济解释，3。3.1二元变量的经济解释当目标函数值z代表总产值时，yi*相应地被称为影子价格；当z代表总利润时，yi*相应地被称为影子利润。1.当yi*代表影子价格(即企业的目标是实现最大的总产值)时，(1)评估资源I的总库存。让资源I的市场价格为pi，那么当yi* pi时，企业可以购买资源，即增加其总库存；当易*皮时，企业可以

7、出售资源，即减少其总库存；这样做很经济。第3章，二元原则，20，3.3，二元关系的经济解释，(2)资源一的当前分配的评估。当资源一在市场上缺货时，其总库存不能增加，但其在企业内的当前分配可以适当调整，以获得最佳的经济效益。第二，当yi*代表影子利润(即企业的目标是实现总利润最大化)时：(1)资源总存量的评价(2)当前资源配置的评价(1)，第3章，二元性原则，21，3.3，二元关系的经济解释，3。3.二、二元性问题的经济学解释。从前面可知，一个单位资源对总产值的贡献是在这N个商业活动中。资源投入量一个单位的第一个J个业务活动所创造的产值一个单位的第一个J个业务活动所消耗的资源量意味着这些M个资源

8、对一个单位的第一个J个业务活动的贡献应该至少与一个单位的第一个J个业务活动所创造的产值一样多，否则，这些资源的利用就不完美。问题(D1):第3章二元原理，22，3.3二元关系的经济解释，该公式意味着资源1对产值的单位贡献不应为负，否则该资源不能使用。公式意味着：确定各种业务活动消耗的各种资源的隐含总价值的最低可接受限度。3。3.3互补松弛的经济解释，考虑到属性7(1): xj 0 ym j=0存在，因此ym j=0将不可避免地导致，因此，属性7(1)的经济解释是，当一个单位的任何业务活动j在严格正水平(xj 0)上运行时，它消耗的各种资源的边际价值的总和必须等于该活动。第3章，对偶性原理，23

9、，3.3对偶性关系的经济解释，例如，已知X*=(4，6，4，0，0)T，y *=(0，1，0，0) t x1=40 y4=0，让y1 3y3 -y4=3 y1 3y3=3类似地考虑性质7(4): xn i0Yi=0，I=1，2，m，其中xn i是约束I的松弛变量，xn i 0意味着约束I具有松弛部分。因此，财产7 (4)的经济解释是，当资源I的供给没有被各种商业活动耗尽时，这种资源根据供求规律，供过于求的商品不可避免地会降价，导致无利可图甚至亏损。例如：xn 1=x3=4 0，这表明除了满足产品A和B的需求之外，一个工作小时的供应是4个工作小时，这导致其影子利润y1=0。这意味着，即使它的供应

10、量增加，它也不会对产品A和B的总利润有任何贡献，也就是说，它不会盈利。第3章对偶原理，24，3.4对偶单纯形法，基本思想：所有互补的基本解都是可行的，都必须是最优的，原始SM，前进(始终保持)，基本解的进化路线，原始可行b 0，对偶可行B0，对偶可行SM，判断和结果无解，原始解无可行解无上限对偶，原始不可行。25，3.4对偶单纯形法，3。4.1标准对偶单纯形法1将m阶线性规划问题转化为标准形式(允许其右常数为负)，在其系数矩阵中找到或构造m阶置换矩阵作为初始基，并建立初始单纯形表。如果所有检验编号为j0，则转到2；否则，应采用人工对偶单纯形法或其他算法。2最优性测试：求解清单中的每个数值BI；

11、如果所有bi0，则问题已经获得最优解，并且计算停止；否则，转到3。3无可行解判断：只要有一个br0和所有arj0在它的行中，原问题就没有可行解，对偶问题也没有下界，所以停止；否则，转到4。第3章，对偶原理，26，3.4对偶单纯形法，4主成分的确定：首先，确定根变量，根据最小bibi 0=bl确定第一行的根变量xBl，第一行为主线；然后确定基变量，并根据最大比值原则确定基变量xk和主成分alk:max j/alj LJ 0=k/alk。5.根据主元素alk对当前表执行基改变操作，以获得新的单纯形表，并返回到2。第3章，对偶原理，27，3.4对偶单纯形法，示例3，解决方案，最大Z=-3x1-2x2

12、，标准差，2x 13 x2 x3=18x 1-x2x 4=2x 13 x2 X5=10x 1，x2，x3，x4，x50，x1x2x4=2，第3章对偶原理，28，3.4对偶单纯形法，-3，-2/3，最大，-3，比值，第3章对偶原理，29，3.4对偶单纯形法，cj，基，3 X1X2X3x5，-3-2000，2000，-1 -3 0 0 1，0 3 2 0 0，x3 x1 x2，0 -3 -2，4 1 0 0 -3/4 -1/4，4 0 0 1 3/4 5/4，2 0 1 0 1 0 1/4-1/4，-16 0 0 0 7/4 5/4，x3 x4 x2，0 0 -2，8 10101，10/31/31

13、00-1/3，-16 0 0 0 7/4 5/4 4.2人工对偶单纯形法当以置换矩阵的形式获得初始基时，如果测试数不都是负的，则有必要引入人工变量x0 0和人工约束：(3-7)，x0 x j1 x j2 x jt=M，其中x jr所有的变量对应于负的测试数(r=1，2，t)，找出变量xp对应于最小测试数，并将(3-7)改写成， 第三章对偶原理，31，3.4对偶单纯形法，并将其代入目标函数和除(3-7)以外的所有约束，得到人工问题。 建立初始单纯形表，所有测试必须为j 0。下面可以根据规范的对偶单纯形法。否则，停止迭代。此时，如果除了人工变量x0之外的所有变量都是有限的，那么将获得原问题的最优解。否则，原始问题是无界的