第一节线性规划问题及其数学模型第二节线性规划问题

《第一节线性规划问题及其数学模型第二节线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*第一节  线性规划问题及其数学模型*第二节线性规划问题的图解法*第三节单纯形法*第四节线性规划的对偶问题*第五节线性规划在卫生管理中的应用第二章线性规划第四节线性规划的对偶问题*线性规划对偶问题的概念*线性规划的对偶单纯形法*线性规划的灵敏度分析（一）对偶问题的提出（二）对偶规划的形式1.对称形式的对偶问题2.非对称形式的对偶问题3.一般形式对偶问题（三）对偶规划的基本性质一、线性规划对偶问题的概念对称形式的对偶问题Max，≤，变量皆非负Min，≥，变量皆非负变量约束条件价值系数右端常数系数矩阵为AA转置矩阵AT对偶问题的对应关系(二)对偶规划的形

2、式一般形式的对偶关系非对称形式的对偶规划的对应关系非对称形式含有等式约束和变量无符号限制变量无符号限制等式约束见下表所示(二)对偶规划的形式返回设有原线性规划问题，它的矩阵表示如下：(三)对偶规划的基本性质式中其对偶规划的矩阵表示是这里A，B，C与上面的原规划相同下面我们用矩阵表示法说明对偶问题的基本性质：(三)对偶规划的基本性质(三)对偶规划的基本性质性质1线性规划对偶问题的对偶是原问题。性质2若分别为互为对偶线性规划问题的可行解，则有性质3若分别为互为对偶线性规划问题的可行解，则当时，是最优解。性质4若互为对偶的两个线性规划问题中，有一个有最

3、优解，那么另一个也一定有最优解，且最优的目标函数值相等。性质5原问题的判别数对应着对偶问题的一个解。有了性质5，在求解线性规划问题时，原规划问题单纯形表中的判别数，就是对偶问题的一个解，但符号相反。返回(四)对偶单纯形法我们前面介绍的一般单纯形法，是从“可行”(右端项非负）开始，逐步地迭代运算，直到得出最优解。而应用对偶规划的性质，可以找到一种求解线性规划的新方法——对偶单纯形法。对偶单纯形法则是从“不可行”(右端项含负）开始，在保持最优性之下逐步迭代，直到不可行变为可行，即得到可行最优解为止。当对偶问题的约束条件的数目较原问题为少时，应用对偶单纯形法求

4、解较为方便。单纯形法思路（保持可行性）对偶单纯形法思路（保持最优性）可行(右端项非负）非最优（检验数非负）最优（检验数非正）不可行(右端项含负）可行(右端项非负）非最优（检验数非负）最优（检验数非正）不可行(右端项含负）可行(右端项非负）最优解（检验数非正）最优（检验数非正）可行解(右端项非负）检验数可正可负可行(右端项非负）右端项可正可负检验数非正非最优（检验数非负）可行(右端项非负）不可行(右端项含负）检验数非正最优解（检验数非正）可行(右端项非负）最优解(右端项非负）检验数非正1.从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行

5、解（检验数非正）,从一个对偶可行解出发.对偶单纯形法的基本思想2.检验原规划的基本解是否可行，即是否有负的分量，如果得到的基本解的分量皆非负,则该基本解为最优解。3.如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。例7利用对偶单纯形法求解解：将原问题化成再化成标准形列表用对偶单纯形法求解：0S50S6[-1]-21-11021-4-101-3←-2Z

6、jCj-Zj000000-1-40-3000-1x10S612-11-100-3[-2]-3213-8←ZjCj-Zj-1-21-1100-2-1-2-10-3-1x10x317/205/2-2-1/203/213/2-1-1/274ZjCj-Zj-1-7/20-5/221/20-1/20-1/2-2-1/2-7Cj－1－40－300x1x2x3x4s5s6b1232/31/22/3对偶单纯形法的步骤(1)将原问题化成标准形式：建立初始对偶单纯形表,若b列全为非负，判别数行Cj–Zj≤0,则已得最优解，计算停止；若b列中至少有一个负分量，且判别数Cj–Z

7、j≤0，则进行下一步；(2)以对应的基变量作为换出变量;（3）检查所在行的系数若所有的则无可行解，计算停止。若存在则计算确定为换入变量；（4）以为主元素，进行迭代运算，得新表。重复步骤（1）—（4）对偶单纯形法的步骤1．确定换出变量：选择最负的基本变量为换出变量。2．确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解。3．初等行运算:使枢元变为1,其他枢列位置变为0。4．最优解检查。如果所得的基本解都是非负的，则此解即为最优解。如果基本解中还有负的数值，则重

8、复第一步继续迭代，直到所有基变量为非负数为止。对偶单纯形法迭代的要点1．初始解可