下载文档原格式
第二章线性规划的对偶理论1．对偶问题的提出2．原问题与对偶问题3．对偶问题的基本性质4．影子价格5对偶单纯形法5．对偶单纯形法6．灵敏度分析7．参数线性规划1§1．对偶问题的提出原问题设某企业有m种资源用于生产n种不同产品，各种（i=1m）又生产单位第j种资源的拥有量分别为b i （i=1，…，m），又生产单位第j种产品（j=1，…，n）消费第i种资源a ij 单位，产值为c j 元。
用x 代表第j种产品的生产数量，为使该企业产值最大，可将上述问题建立线性规划模型j 将上述问题建立线性规划模型：max z =c 1x 1+c 2x 2+…+c n x n a 11x 1+a 12x 2+…+a 1n x n ≤b 1a 21x 1+a 22x 2+…+a 2n x n ≤b 2………………2a m 1x 1+a m 2x 2+…+a m n x n ≤b m x 1，x 2，…，x n ≥0§1．对偶问题的提出现在从另一角度提出问题：假定有另一企业欲将上述企业拥有的资源收买过来，至少应付出多少代价，才能使前一拥有的资源收买过来，至少应付出多少代价，才能使前企业愿意放弃生产活动，出让资源。
设用y i 代表收买该企业一单位i种资源时付给的代价，则总收买价为：ωb ω = b1y 1＋…＋b m y m 前一企业生产一单位第j种产品时，消耗各种资源的数量分别为a 1j ，a 2j ，…，a mj ，如果出让这些资源，价值应不低于单位j种产品的价值c j 元，因此：a 1 j y 1+ a 2 j y 2 + …+ a m j y m ≥ c j 3j j j j （j =1，…，n）§1．对偶问题的提出对后一企业来说，希望用最小代价把前一企业所有资源收过来此有有资源收买过来，因此有：min ω=b1y 1＋b 2y 2＋…＋b m y m a11y 1+a 21y 2+…+a m 1y m ≥c 1a 12y 1+a 22y 2+…+a m 2y m ≥c 2………………a 1n y 1+a 2n y 2+…+a mn y m ≥c ny 1，y 2，…，y m ≥04§1对偶问题的提出§1．对偶问题的提出max z = c 1x 1+ c 2x 2+ … + c n x na x +a x ++a xb a 1 1x 1+ a 1 2x 2 + … + a 1 n x n ≤b 1a 2 1x 1+ a 2 2x 2 + … + a 2 n x n ≤b 2………………a m 1x 1+ a m 2x 2 + … + a m n x n ≤b mmin ω = b 1y 1＋b 2y 2＋…＋b m y mx 1 ，x 2 ，… ，x n ≥0a 1 1y 1+ a 21 y 2 + … + a m 1y m ≥c 1a 1 2y 1+ a 22y 2 + … + a m 2y m ≥c 2………………a 1n y + a 2n y 2+ … + a y ≥c 51 n 12 n 2 mn m ny 1，y 2，… ，y m ≥0§2．原问题与对偶问题后一个线性规划问题是前一个问题从不同角度作的阐述如前者称为线性规划问的话的阐述。
