特许经营法律实务(二)

线性规划

LinearProgrammingLudongUniversity线性规划

LinearProgrammingLudon2024/4/1LudongUniversity2线性规划线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析对偶问题的提出对偶规划对偶理论对偶单纯形算法2024/3/31LudongUniversity2线性规2024/4/1LudongUniversity3线性规划的对偶理论这里的对偶是指对同一事物(问题)从不同的角度(立场)观察,有两种对立的表述。如“平面中矩形的面积与周长的关系。”1.周长一定，面积最大的矩形是正方形；2.面积一定，周长最短的矩形是正方形。本节所讨论的对偶理论是线性规划理论中一个重要而又有趣的概念。对偶理论告诉我们：对于每个一个线性规划(P)，总存在另一个线性规划(D)，两者之间存在着密切的联系，甚至人们常常通过求解对偶问题(D)来获得原规划(P)的最优解。2024/3/31LudongUniversity3线性规2024/4/1LudongUniversity4对偶问题的提出引例美佳公司计划制造两种产品。已知各制造一件时分别占用的设备A、B的台时、调试工序时间、每天可用于生产这两种产品的能力以及出售每件产品可获得利润如表2.5.1所示，试制订总利润最大的生产计划。项目产品Ⅰ产品Ⅱ每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润（元）21表2.5.1模型LP12024/3/31LudongUniversity4对偶问2024/4/1LudongUniversity5对偶问题的提出假设有某个公司想把美佳公司的资源收买过来，它至少应付出多大的代价，才能使美佳公司愿意放弃生产，出让自己的资源。显然美佳公司出让自己资源的条件是：出让代价应不低于用同等数量资源由自己组织生产时获得的利润。项目产品Ⅰ产品Ⅱ每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润（元）21表2.5.1现在从另外一个角度提出上述问题2024/3/31LudongUniversity5对偶问2024/4/1LudongUniversity6对偶问题的提出可控因素：受制条件：目标：蕴含约束：2024/3/31LudongUniversity6对偶问2024/4/1LudongUniversity7对偶问题的提出？模型LP2模型LP1上述LP1和LP2两个线性规划问题，通常称LP1为原问题，LP2是LP1者的对偶问题。？2024/3/31LudongUniversity7对偶问2024/4/1LudongUniversity8对偶规划标准形式线性规划的对偶规划规范形式线性规划的对偶规划一般形式线性规划的对偶规划实例2024/3/31LudongUniversity8对偶规2024/4/1LudongUniversity9标准形式LP的对偶规划2024/3/31LudongUniversity9标准形2024/4/1LudongUniversity10标准形式LP的对偶规划

（Ⅱ）反之亦然。2024/3/31LudongUniversity10标准2024/4/1LudongUniversity11两个规划的最优解之间存在着密切的关系，通过一个规划的最优解可以得到另一个规划的最优解。标准形式LP的对偶规划对偶规划原规划2024/3/31LudongUniversity112024/4/1LudongUniversity12规范形式LP的对偶规划标准化其对偶规划是2024/3/31LudongUniversity12规范2024/4/1LudongUniversity13规范形式LP的对偶规划对偶规划原规划2024/3/31LudongUniversity13规范2024/4/1LudongUniversity14一般形式LP的对偶规划通过把其转化为标准形式,同样可以得到其对偶规划为：2024/3/31LudongUniversity14一般2024/4/1LudongUniversity15原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数min目标函数max右端向量价值向量价值向量右端向量2024/3/31LudongUniversity15原问2024/4/1LudongUniversity16实例

其对偶规划为2024/3/31LudongUniversity16实例2024/4/1LudongUniversity17对偶理论﹡﹡﹡2024/3/31LudongUniversity17对偶2024/4/1LudongUniversity18定理2.5.12024/3/31LudongUniversity18定理2024/4/1LudongUniversity19定理2.5.22024/3/31LudongUniversity19定理2024/4/1LudongUniversity20定理2.5.52024/3/31LudongUniversity20定理2024/4/1LudongUniversity21问题对偶问题的对偶问题是原问题。关于原问题和对偶问题的解下述三种情况恰有一种出现。

1.都有最优解；

2.一个问题无界，另一个无可行解；

3.均无可行解。如果对偶问题与原问题都有最优解，则它们的最优解之间有什么关系？它们的最优值是否相等？2024/3/31LudongUni