华南理工大学-运筹学-第3章-线性规划的对偶理论(简)-工商管理学院

1第3章线性规划的对偶理论(DualityTheory)基本概念任意一个线性规划问题都有一个与其关联的线性规划问题，这两个相互对应的问题被称为“原问题”和“对偶问题”，它们不仅在数学形式上呈一定的对称关系，而且在目标函数值、基本解上都有一定的对应。2引例(例1-1)F公司每周根据原材料M1和M2的采购数量来安排其产品A、B和C的生产计划。问：这3种产品各应生产多少，能使F公司获得最大的利润？3单位消耗产品A产品B产品C可用资源原材料M1845320原材料M2221100单位产品利润542引例企业F决定不安排生产，而是将本周所采购的原材料M1和M2全部转让出售，那么这两种原材料的单位转让收益分别应为多少才是可接受的？【注】企业卖出相同数量关系的原材料，收益应不低于用其生产出最终产品而获得的利润。4引例5引例6基本概念1-原问题的目标函数系数(行)向量对应于对偶问题约束条件的右端常数(列)向量。同理，原问题约束条件的右端常数(列)向量对应于对偶问题的目标函数系数(行)向量。7基本概念2-原问题与对偶问题约束不等式的不等号方向相反。8基本概念3-如果原问题的目标函数是求最大值，则对偶问题的目标函数是求最小值，反之亦然。9基本概念4-原问题约束条件中变量的系数矩阵，是对偶问题约束条件中变量系数矩阵的转置。因此，原问题的约束条件的个数等于对偶问题变量的个数。同理，对偶问题约束条件的个数等于原问题变量的个数。10基本概念11基本概念12两个问题互为对偶问题，即对称性。对偶问题的性质13对偶问题的性质14对偶问题的经济意义影子价格（shadowprice）又称最优计划价格，它是指依据一定原则确定的，能够反映资源稀缺程度、使资源得到合理配置的价格。影子价格反映了某种最优状态下的资源稀缺程度和对最终产品的需求情况，有利于资源的最优配置。15对偶问题的经济意义1-某种资源的影子价格表明了该资源的稀缺性，影子价格越高则该资源越为稀缺。2-影子价格应被理解为一种机会成本或附加价值。3-资源的市场价格是已知的且相对稳定的，而其影子价格的价格形成机制取决于最优生产计划。16对偶问题的经济意义4-影子价格只是一种边际价格，它只是相应的资源在发生微量的变化时为最优总利润带来的边际贡献。5-最优生产计划中某种资源未充分利用时，其影子价格必然为0。这意味着增加该资源的供应量不会为企业带来利润或产出的增加。17对偶单纯形法对偶单纯形法并不是求解原问题的（线性规划问题的）对偶问题的单纯形法，而是应用对偶原理和单纯形法来求解原问题的一种方法。18对偶单纯形法基本单纯形法求解过程在基本可行解的前提下，寻找检验数全部小于等于零的最优解。（在始终保持基的可行性(b=0)的前提下，通过基变换逐步找到一个对偶可行基。）对偶单纯形法求解思路在检验数全部小于等于零的基本解的前提下，寻找可行解。（从一个对偶可行基出发（此基对原问题不一定可行），在始终保持基的对偶可行性的前提下，通过基变换逐步找到一个可行基。）19对偶单纯形法20对偶单纯形法21对偶单纯形法对偶单纯形法并不是所有线性规划问题的通用解法，它只能从检验数已经符合最优化条件的基本解开始求解。22对偶单纯形法1-约束条件为“≥”初始解可以是非可行解。当检验数都为负数时，就可以进行基变换，不需要加入人工变量。2-变量多于约束条件对于变量多于约束条件的线性规划问题，用对偶单纯形法计算可以减少计算工作量。变量少，约束条件很多的线性规划问题，可以将其变换为对偶问题，然后用对偶单纯形法求解。23对偶单纯形法示例124对偶单纯形法示例125对偶单纯形法示例126灵敏度分析线性规划问题的最优解，是在设定问题模型中的𝑎𝑖𝑗、𝑏𝑖、𝑐𝑗都为已知常数的前提下求解得到的。对于许多实际问题，这些系数都是采用经验法或统计、预测方法得到的估计值。当数学模型中的某些系数与现实状况存在偏差时，模型的最优解不一定就是实际问题的最优解。即使数学模型很好地反映出了现实状况，但环境的多变性也会使现时条件下成立的最优解在短期内就变得不再最优。27灵敏度分析例如，在生产计划问题例1-1中，产品市场的销售状况发生变化将会影响产品的销售价格，进而影响产品的利润系数𝑐𝑗；资源供应量的变化，就会影响到𝑏𝑖；技术进步会影响产品的生产工艺和原材料消耗，将导致模型中约束条件的系数𝑎𝑖𝑗发生变化。当这些变化发生时，已经求得的最优生产组合可能不再是最优解。28灵敏度分析因此，仅仅求出给定系数设定下特定线性规划问题的最优解无法完全满足现实生产经营活动的需求，还需要进一步解决以下问题：1.当某个系数发生变化时，原来求得的最优解有没有变化或有什么样的变化？2.当某个系数在一个什么样的范围内变化时，原来求得的最优解或最优基不变？3.当某个系数的变化已经引起最优解变化时，如何用最简单的方法求得新的最优解？29灵敏度分析灵敏度分析（Sensitivityanalysis，又称敏感性分析）1.目标函数中系数的变化（产品价格和成本的变化）2.约束条件右端常数向量的变化（有限资源的变化）3.约束条件的变化，包括：(1)加入新的决策变量(2)约束矩阵系数列向量的变化(3)增加新的约束条件30灵敏度分析31灵敏度分析的起点一般为最优单纯形表，而基本的分析是在改进单纯形法中的矩阵形式单纯形表基础上，直观分析和计算不同系数变化对最优解的影响。灵敏度分析示例132F公司每周根据采购的原材料𝑀1和𝑀2安排产品A，B和C的生产活动，已知生产3种产品的单件资源消耗和利润如表所示。求F公司最优的产品生产组合。灵敏度分析示例133灵敏度分析示例1341-目标函数中非基变量系数的变化目标函数中非基变量系数的变化只会影响该非基变量的检验数。灵敏度分析示例135例3-7中产品C的单位利润在什么范围内变化时，原最优解仍为最优？当产品C的单位利润增加至4元时，最优解是什么？灵敏度分析示例136产品C的单位利润增加至4元时：（采用基本单纯形法继续计算）灵敏度分析示例1372-目标函数中基变量系数的变化目标函数中基变量系数的变化将影响所有非基变量的检验数！灵敏度分析示例138在例3-7中，最优基变量组合为{𝑥1,𝑥2}，现考虑改变𝑥1的目标函数系数，亦即产品A的单位利润𝑐1。问：产品A的单位利润在什么范围内变化时，原最优解维持最优？当A的单位利润增加至10元时，最优解是什么？灵敏度分析示例139灵敏度分析示例140当A的单位利润增加至10元时，最优解：灵敏度分析示例13-基变量和非基变量的目标函数系数同时变化目标函数的系数发生变化，只会影响当前最优解的非基变量的检验数！41灵敏度分析示例1例3-7中产品A、B、C的单位利润变为6、3、4元，最优解是什么？42灵敏度分析示例1434-右端常数向量b的变化常数向量b的变化不会影响解的最优性。但由式XB=B-1b可知，b的变化必然影响解的数值。灵敏度分析示例1在例3-7中，如果原材料𝑀1的周供应量由320千克增至360千克，最优解有什么变化？𝑀1的周供应量𝑏1在什么范围内变化时，原生产组合（仅生产A和B）仍为最优组合？𝑏1增加至500时，最优解是什么？44灵敏度分析示例145灵敏度分析示例146灵敏度分析示例147灵敏度分析示例148灵敏度分析示例149常数向量b的变化可能使得最终单纯形表向量b中出现负元素从而影响原最优基的可行性，进而使最优解发生变化。因为b的变化不会直接影响非基变量的检验数，那么只要b的变化没有造成最优基的变化，则资源的影子价格保持不变，此时可直接用影子价格乘以新增/减少的资源数量得出最优利润的变化。灵敏度分析示例150在本例中，只要𝑏1落在[200,400]内，最优基维持不变，原材料𝑀1和𝑀2的影子价格仍然分别为1/4和3/2，𝑀1周供应量的增量Δ𝑏1所带来的最优利润增值为(1/4)Δ𝑏1。Z=240=230+40*(1/4)灵敏度分析示例151当𝑏1=500时，最优基发生了变化。此时，原材料𝑀1和𝑀2的影子价格分别变为2/3和2/3，就不能再简单地使用影子价格乘以资源的增量来计算其对最优利润的贡献了。灵敏度分析示例1F公司在采购完本周的320千克的𝑀1后，原材料市场上𝑀1发生了缺货，如需再购进𝑀1则需在原价的基础上另外承担0.2元/千克的溢价。问：在保持产品A、B仍为最优组合的前提下，F公司是否应购入𝑀1扩大生产？如应购入𝑀1，应购入多少？52灵敏度分析示例1在原最优表中，𝑀1的影子价格为1/4。在本例中，虽然𝑀1的价格上涨了0.2，但是剔除此额外成本后，购入𝑀1仍然能产生正的边际贡献0.05(=0.25−0.2)，正确的决策是应继续采购𝑀1。分析可知，只要𝑀1的供应量在200至400之间时，原最优基仍为最优基，产品A、B仍为最优生产组合，亦即F公司最多应再采购400−320=80千克𝑀1用于扩大生产，能带来的额外收益为0.05×80=4元。53灵敏度分析示例1545-引入新的决策变量新的决策变量的引入，在当前的最优单纯形表中，其表现为非基变量。因此，只需要判定该变量的检验数为非负，最优基将不变。灵敏度分析示例155在例3-7中，经过技术创新，F公司已经具备了生产一种市场需求旺盛的新产品D的能力。生产1件产品D消耗3千克M1和2千克M2，单位利润为3元。问：此时的最优解是什么？当产品D的单位利润为4元时，最优解又是什么？灵敏度分析示例156灵敏度分析示例157灵敏度分析示例1586-约束矩阵中的系数列向量的变化在生产计划问题中，改变生产单位某产品的资源消耗系数，等价于改变对应决策变量xi在约束矩阵系数列向量pi。灵敏度分析示例159这里需注意区分xi是最优表中的基变量还是非基变量：如果xi为非基变量，如产品C的原材料消耗系数pi发生变化时，判断和求解的方法与前一种情况相同，即检查xi的检验数是否满足最优条件；灵敏度分析示例160如果xi是基变量（例如产品A或产品B的资源消耗系数p1或p2发生变化），那么p𝑗的变化将引起基矩阵B的变化。B的变化将影响单纯形法迭代过程中几乎所有的计算项目，问题只能重新迭代。灵敏度分析示例17-引入新的约束条件在例3-7中，由于劳动力市场出现劳动力短缺，F公司每周能够使用的劳动力工时被限制在720个小时，而生产单位产品A、B、C分别需要12、10、6个小时。问：此时的最优解是什么？61灵敏度分析示例1对于这类问题，不急于写出新的线性规划模型。首先检验原最优解是否满足新引入的约束条件，如果满足，则原最优解不受新约束的影响仍为最优。62灵敏度分析示例1如果例3-14中每周能够使用的劳动力工时为480个小时，最优解是什么？因为12𝑥1+10𝑥2+6𝑥3=560480当前最优解不满足新的约束条件。这时，可以将新约束加入原始模型，作为一个新的问题重新求解，但这不是灵敏度分析推崇的方式。较为便捷的作法是：将新约束条件加入原最优表，经过简单的改写，就可以应用对偶单纯形法求出新的最优解。63灵敏度分析示例164灵敏度分析示例165参数线性规划灵敏度分析所涉及的问题多数是一个系数的变化如何影响最优解和最优目标函数值。参数线性规划(Parameterlinearprogramming)则是研究系数连续变化时，最优解变化的临界点问题。66参数线性规划参数线性规划的内容：研究线性规划问题的最优解、目标函数值以及其它特征随参数𝜇取值不同时的不变性和变化规律。67参数线性规划68参数线性规划示例169参数线性规划示例170参数线性规划示例171参数线性规划示例172参数线性规划示例173参数线性规划示例174参数线性规划示例175Excel工具分析76