机械优化设计2-2

1、线性规划线性规划线性规划：线性规划：目标函数和约束条件都是线性目标函数和约束条件都是线性的，对目的，对目标函数求优化问题。标函数求优化问题。第一节第一节 线性规划的标准形式和基本性质线性规划的标准形式和基本性质一、线性规划实例：一、线性规划实例：1 1、甲乙两种产品：、甲乙两种产品：产品产品材料材料工时工时用电用电利润利润甲甲X19kg9kg3h3h4kWh4kWh6060元元乙乙X24kg4kg10h10h5kWh5kWh120120元元总供应总供应360kg360kg300h300h200kWh200kWh? ?212112060,maxxxxxf212112060,minxxxxf约束条

2、件：约束条件：0, 0200543001033604921212121xxxxxxxx2 2、有、有m m个产粮区分别产粮个产粮区分别产粮 , , 有有n n个贮粮区分个贮粮区分别储粮别储粮 , , 从从i i产粮区运到产粮区运到j j贮粮区的每吨运费贮粮区的每吨运费 , ,求如何调拨粮食使运费最省求如何调拨粮食使运费最省? ?1,2,3,ma a aa123,nb b bbijd设设 从从i i产粮区运到产粮区运到j j贮粮区的数量。贮粮区的数量。ijx 11minnmijijjif xd x约束条件：约束条件：njjmiiba11imiijnjax 11jmiijnjbx 11(i=1,2

3、,(i=1,2,m),m)运出运出(j=1,2,(j=1,2,n),n)运进运进二、线性规划的标准形式二、线性规划的标准形式线性规划数学模型的一般形式为线性规划数学模型的一般形式为求设计变量求设计变量Tnxxx,21x使目标函数使目标函数 min2211nnxcxcxcfx约束条件：且满足约束条件：且满足1111221121122222112201,2,01,2,nnnnmmmnnmjia xa xa xba xa xaxbaxaxaxbbjmxinmn同时同时12(,) (1,2,3,)Tiiiikinaaaaaim组成的向量互不相关（线性无关）。组成的向量互不相关（线性无关）。也可写成如下

4、的简化形式也可写成如下的简化形式Tnixxxx,21x求求 min1niiixcf x使目标函数使目标函数11,2,01,2,0(1,2,)njiijiija xbjmxinbjm要求满足约束条件要求满足约束条件约束条件包括两部分：约束条件包括两部分：一是等式约束条件一是等式约束条件二是变量的非负要求，它是标准形式中出现的唯一不等式形式。二是变量的非负要求，它是标准形式中出现的唯一不等式形式。通过引入松弛变量将不等式约束化成上述等式约束形式。通过引入松弛变量将不等式约束化成上述等式约束形式。1211121134nnnnxliilliinliinnxsiissiinsiittnna xba xx

5、ba xba xxbxxxx 线性规划问题的线性规划问题的标准形式标准形式可写成如下的可写成如下的矩阵形式矩阵形式 min. .00Tfstbxc xAxbx求求x使使其中，其中， ，而，而0 0代表零向量。代表零向量。 ,Tjijim nabcAbc三、线性规划的基本性质三、线性规划的基本性质在线性规划中有在线性规划中有n n个变量个变量，m m个方程个方程，则当向量，则当向量X X 中中n-mn-m个个变量为零变量为零时，其基本解个数时，其基本解个数! !mmnnmmPnCPmn n若若基本解满足基本解满足 ，称为基本可行解。称为基本可行解。通过作图，在通过作图，在 平面内作出约束条件组成

6、的多边形，作平面内作出约束条件组成的多边形，作出出 的等值线。的等值线。0 x 12x Ox f x发现最优点取在多边形的顶点：发现最优点取在多边形的顶点：1220,24xx则则 4080f x最优最优基本变量：基本可行解中取基本变量：基本可行解中取正值的变量。正值的变量。可作为基底变量可作为基底变量（列向量）。（列向量）。非基本变量：基本可行解非基本变量：基本可行解取零值的变量。取零值的变量。特殊情况下出现：无穷多最优解，无解，无可行解。特殊情况下出现：无穷多最优解，无解，无可行解。第二节第二节 基本可行解的转换基本可行解的转换一、从一个基本解转换到另一个基本解一、从一个基本解转换到另一个基

7、本解 对于约束条件组成的方程组，对于约束条件组成的方程组， Axb11 11221121 1222221 122nnnnmmmnnma xa xa xba xa xa xba xaxaxb1112111212222212nnmmmnnmaaaxbaaaxbaaaxb采用高斯约当（采用高斯约当（Gauss-JordanGauss-Jordan）法进行消元，则上面方程）法进行消元，则上面方程将变成下列形式将变成下列形式11 11221121 1222221 1221 1220010knnknnllklnnlmmkmnnma xa xxa xba xa xxa xba xa xxa xba xaxx

8、a xb重复进行这样的转轴运算，则可得：重复进行这样的转轴运算，则可得：121111112211221211100010001mmmnnmmmnnmmmmmnnmxxxaxa xbxxxaxa xbxxxaxa xb这一方程称作正则方程组。这一方程称作正则方程组。从而得到一组基本解：从而得到一组基本解：1,2,01,2,iiixbimximmn若若 非负，这组解为非负，这组解为基本可行解基本可行解。ib前前m m个变量称作基本变量，个变量称作基本变量，基本解中所有基本变量的全体称作它的基。基本解中所有基本变量的全体称作它的基。对于上述方程，可任选对于上述方程，可任选 为转轴元素，（为转轴元素，

9、（s s任意，任意， ），），x xt t作为转轴变量进行一次附加的转轴运算，就可实现该一个作为转轴变量进行一次附加的转轴运算，就可实现该一个基本可行解转换到另一个基本可行解。基本可行解转换到另一个基本可行解。statm二、从一个基本可行解转到另一个基本可行解二、从一个基本可行解转到另一个基本可行解121111111221122212111211100.010.00.10.001.mmmkknnmmmkknnlmlmmlkklnnlmmmmmkkmnnmxxxaxa xaxbxxxaxa xaxbxxxxaxa xaxbxxxaxa xaxb对于上述方程，若对于上述方程，若 ，则该基本解为基本

10、可行解。，则该基本解为基本可行解。0ib 如取如取 为转轴元素，为转轴元素，x xk k为转轴变量，则由原基本可行解，为转轴变量，则由原基本可行解，用用x xk k替换替换x xl l。lka111112222200kkkkkkklllkkllkmmmkkmmkxxba xbaxba xbaxba xbaxbaxba要保证替换后的基本解为基本可行解，则要保证替换后的基本解为基本可行解，则000lkxx0llkba因此因此00lklab 并使并使minlklkbxa规则规则三、初始基本可行解的求法三、初始基本可行解的求法简单方法：选择初始基本可行解时，把松弛变量选为基本简单方法：选择初始基本可行

11、解时，把松弛变量选为基本变量即可；如还不行则引进人工变量。变量即可；如还不行则引进人工变量。第三节第三节 单纯形法单纯形法对于可行解，目标函数可以写成：对于可行解，目标函数可以写成： 1 122100nllmmlfc bc bc bc bx如果还有另一组可行解，它的基本变量中包含有如果还有另一组可行解，它的基本变量中包含有 ，即，即kxkm111222kklllkmmmkkxbaxbaxbaxbaxx其中的其中的 。它对应的目标函数是。它对应的目标函数是0lllkxbalm 111mmmlllkkllllkklllfc baccbc acx1mkllklf ac a令令则则 kffcffrkx

12、xax式中式中 相对价值系数，相对价值系数， rkrcfka1 1、求极小值时：要求、求极小值时：要求 ，则，则 是负值，是负值， 是负值，是负值，故故 还没有到极小，还可以下降直至还没有到极小，还可以下降直至 为正值，才说明为正值，才说明 到达极小值。到达极小值。 ffxxrr f xr fx2 2、求极大值时：则相反，、求极大值时：则相反， 为负值，才说明为负值，才说明 到达极大值。到达极大值。r fx因此线性规划有以下两个原则：因此线性规划有以下两个原则：1.1.规则：（确定转轴变量）规则：（确定转轴变量）min0lkllklkbxaa 2.2.最速变化规则：（确定最优值）最速变化规则：

13、（确定最优值）minjjkkjcfcfaa当目标函数表示成只是非基本变量的函数时，对应于基本当目标函数表示成只是非基本变量的函数时，对应于基本变量的系数变量的系数 ，则，则 ，最速变，最速变化规则又可表示为化规则又可表示为01,2,lclm10mjlljlfc aaminjkjcc 对于极大值问题，则最速变化规则应取对于极大值问题，则最速变化规则应取maxmax号。号。1 1、某工厂用甲、乙两台机床，加工、某工厂用甲、乙两台机床，加工A A、B B、C C三种零件，已知三种零件，已知在一生产周期内甲只能工作在一生产周期内甲只能工作8080机时，乙只能工作机时，乙只能工作100100机时。机时。

14、一生产周期内要加工一生产周期内要加工A A、B B、C C的件数分别为的件数分别为7070、5050、2020。两。两台机床加工每个零件的时间和成本如下表，问应如何安排两台机床加工每个零件的时间和成本如下表，问应如何安排两台机床生产一周期的加工任务，才能使成本最低？台机床生产一周期的加工任务，才能使成本最低？解：设甲机床生产解：设甲机床生产A,B,C的零件的数量分别为：的零件的数量分别为：123,x xx则乙机床生产则乙机床生产A,B,CA,B,C的零件的数量分别为：的零件的数量分别为：12370,50,20 xxx123123280702(50)3(20)100 xxxxxx则：则：生产成本

15、为：生产成本为：123123( )2353(70)4(50)6(20)f xxxxxxx归纳为：归纳为：123123123123( )530. .28023130705020f xxxxstxxxxxxxxx标准形式为：标准形式为：123123412356172839( )530min. .28023130705020f xxxxstxxxxxxxxxxxxxxx经计算后：经计算后：12330,50,0,( )450 xxxf xyuan第四节第四节 单纯形法应用举例单纯形法应用举例212112060,minxxxxf约束条件：约束条件：0, 0200543001033604921212121xxxxxxxx212112060,minxxxxf1231241251294360310300452000,0 xxxxxxxxxxxCk解解-60-120000ClP1P2P3P4P5b0X394100360900X4310010300300X54500120040f(ak)00000r-60-120000Ck解解-60-120000ClP1P2P3P4P5b0X3-120X20.3100.10301000X5f(ak)rCk解解-60-120000ClP1P2P3P4P5b0X37.801