例4试用对偶理论证明该线性规划问题无最优解。证：该问题存在可行解，X=（0，0，0）；对偶问题为：由第一个约束条件可知对偶问题无可行解，因此，原问题有可行解，无最优解。第30页，共36页，星期日，2025年，2月5日例5：试用对偶理论找出原问题的最优解。解：原问题的对偶问题为：已知其对偶问题的最优解为：第31页，共36页，星期日，2025年，2月5日代入对偶问题的约束条件，得2,3,4式为严格不等式，由互补松弛性得因原问题的约束条件应取等式为：求解后得到原问题的最优解为:第32页，共36页，星期日，2025年，2月5日原问题的最优解为:Z*=CBB-1b=CX*=Y*b对偶问题的经济解释---影子价格z=CX=CBB-1b+σNXN=CBB-1bσN=CN-CBB-1NY=CBB-1为单纯形乘子当b为变量的情况下,当bi发生变化:yi的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化.yi是bi的一种估价,估价是有条件的替代方案.第33页，共36页，星期日，2025年，2月5日1.5.3对偶单纯形法单纯形法原问题基可行解，对偶问题基解（非可行解）原问题基可行解，对偶问题基可行解….原问题基可行解，对偶问题基可行解原问题基解，对偶问题基可行解….对偶单纯形法第34页，共36页，星期日，2025年，2月5日第35页，共36页，星期日，2025年，2月5日例1-21用对偶单纯形法求解下述LP问题解：引入松弛变量转换成如下的标准形式：第36页，共36页，星期日，2025年，2月5日第3讲对偶理论和灵敏度分析*第1页，共36页，星期日，2025年，2月5日第3讲对偶理论对偶问题的提出线性规划的对偶理论对偶单纯形法对偶问题的经济解释---影子价格重点：对偶理论，对偶单纯形法难点：对偶理论基本要求：掌握对偶关系，理解对偶性质，掌握对偶单纯形法，会求影子价格，第2页，共36页，星期日，2025年，2月5日引例：经营策略问题。甲工厂有设备和原料A、B这些设备和原料可用于Ⅰ、Ⅱ两种产品的加工，每件产品加工所需机时数，原料A、B消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备购买资源A和B。问甲厂采取哪种经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料A,B的底价应是多少？对偶问题的提出ⅠⅡ设备原料A原料B14020480台时160kg120kg23盈利第3页，共36页，星期日，2025年，2月5日自己生产：原问题引例分析：第4页，共36页，星期日，2025年，2月5日设y1,y2和y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额ω=80y1+160y2+120y3出售资源对偶问题显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数min第5页，共36页，星期日，2025年，2月5日例1它的对偶问题是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）第6页，共36页，星期日，2025年，2月5日1.5.1原问题与对偶问题的关系(对称形式)线性规划的对偶理论第7页，共36页，星期日，2025年，2月5日第8页，共36页，星期日，2025年，2月5日原关系minw对偶关系maxzxy原问题与对偶问题的对称形式第9页，共36页，星期日，2025年，2月5日标准(max,?)型的对偶变换目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m对偶问题约束为?型，有n行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义第10页，共36页，星期日，2025年，2月5日原问题与对偶问题的结构关系原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常数项对偶问题中的系数