第十次线性规划.ppt

线性规划模型一. 生产计划问题例1 利润最大? 生产计划,才能使所获安排千元。问:该厂应如何、、单位产品的利润为、、同,如下表。耗费的加工时间各不相产品所需材料的数量和三种产品,它们的单位、、生产某工厂利用某种原材料 754CBA CBA 产品资源原材料工时 ABC 资源总量 21 32 100 150 解: 。、、的产量分别为、、设 321xxxCBA ,则设总利润为 S 321754xxxS??? 321???xxx3,2,1,0 150 22 321?????ix xxx i 321754 min xxxS????????????????3,2,1,0 150 22 100 .. 321 321ix xxx xxxts i 线性规划模型: 一组决策变量; )1( 一个线性目标函数; )2( 一组线性的约束条件。)3( 的一般形式: 线性规划模型)( LP?? ni iixc 1 (max) min ???????????????????????????????nix bxaxaxa bxaxaxa bxaxaxats i mn mn mm nn nn,,2,1,0),( ),( ),( ),(.. 2211 22222 121 11212 1 11?????标准型二. ?? ni iixc 1 max ???????????????????????nix bxaxaxa bxaxaxa bxaxaxats i mn mn mm nn nn,,2,1,0 .. 2211 22222 121 11212 1 11?????记为。则线性规划标准型可记 nm ij Tn Tm TnaA ?????)( ,),,,(,),,,(,),,,( 212121???xc T max ?????0 ..x b Ax ts 目标函数: )1(xc T min : 目标函数原问题 xc T?? max 约束条件: )2( in in iibxaxaxai????? 2211)(: 原问题条件????????????0 2211in iinn in iix bxxaxaxa?称为松弛变量。 inx ?in in iibxaxaxa ii????? 2211)(: 原问题条件????????????0 2211in iinn in iix bxxaxaxa?称为剩余变量。 inx ?。无非负约束,则令: 原问题??????0, )( ii iiiivu vuxx iii 为标准型。将下述线性规划模型化例1 4321332 min xxxx???????????????????????无约束 2431 4321 421 4321,0,, 634 7223 332..xxxx xxxx xxx xxxxts 解: 则令, 222vux?? 432213332 max xxvux??????????????????????????????0,,,,,, 6344 72223 332.. 2275431 743221 4221 543221vuxxxxx xxxvux xvux xxxvuxts 图解法三. 求解线性规划例2????????????0, 52 42.. 34 max 21 21 21 21xx xx xxts xxz 解: 。画出可行解的范围)1(1x 2xo ABC 求极值点。利用等值线平移的方法)2( 表示一族等值平行线。为参数,则方程以zxxz?? 213442 21??xx52 21??xx 。顶点极大值点为 B?。中的目标函数改为将例例 21223xxz?? 1x 2xo ABC42 21??xx52 21??xx 解: 。分析同例 2。等值线: zxx?? 212 任一点。上的极大值点为线段 AB ? 1x 2xo AB C 2 21??xx2 21??xx 解: 。分析同例 2。等值线: zxx?? 2134 求解线性规划例4????????????0, 2 2.. 34 max 21 21 21 21xx xx xxts xxz 不存在最大值。?