[理学]线性规划上课ppt课件

1、从可行域中某个基可行解一个顶点开从可行域中某个基可行解一个顶点开场称为初始基可行解。场称为初始基可行解。从可行域中某个基可行解一个顶点开从可行域中某个基可行解一个顶点开场称为初始基可行解。场称为初始基可行解。如可能，从可行域中求出具有更优目的函如可能，从可行域中求出具有更优目的函数值的另一个基可行解另一个顶点，数值的另一个基可行解另一个顶点，以改进初始解。以改进初始解。产品产品/资源资源甲甲乙乙可利用可利用的资源的资源总量总量原材料原材料1（吨）（吨）1 12 28 8原材料原材料2（吨）（吨）4 40 01616加工时间（小时）加工时间（小时）0 04 41212检验数最大，检验数最大，最小

2、比值原那么最小比值原那么 x25040302010 x1Q1Q2 X4X2 Q4X1 OX3 Q3 由1-171-18 . 0,kmkmxkmx000zxzxzzkmkmjjX X 0010)(zxzxzXNBCCbBCzkmkmjnmjjNBNB)0,0,(21)0(mbbbX0, 0,kmikma)1(Xkmjnmjjxkmxkmiaibix,1,0)1()1(0,)1(.0,0)1(,ikmixa)1(X,0kmzz.,znmjaccmiijijj, 1,10,010jBnmjjjbBCzxzz cj c1 cm cm+1 cn CB XB b x1 xm xm+1 xn i i c1

3、x1 b11 0 a1,m+1 a1,n 1 1 c2 x2 b20 0 a2,m+1 a2,n 2 2 0 0 cm xm bm0 1 am,m+1 am,n n n -Z - c cibi0 0 cm+1 - c ci iai,m+1 cn - c ci iai,nnmjaccmiijijj, 1,1行第 laaaaPmklkkkk010021有有B-1=I, B-1b=b, B-1A=A,单纯性表如下：单纯性表如下： cj 23000 CB XB b x1 x2 x3 x4 x5 i i0 x381210040 x41640010 -0 x5120 40013 -Z023000 cj 2

4、3000 CB XB b x1 x2 x3 x4 x5 i i0 x32 1010-0.520 x4164001043 x2301000.25 - -Z-92000-0.75 cj 23000 CB XB b x1 x2 x3 x4 x5 i i2 x121010-0.5 -0 x4800-41243 x2301000.2512 -Z-1300-200.25 cj 23000 CB XB b x1 x2 x3 x4 x5 i i2 x141000.25020 x5400-20.5143 x22010.5-0.1250 - -Z-14000-0.1250 cj c1 cm cm+1 cn CB

5、XB b x1 xm xm+1 xn i i c1 x1 b11 0 a1,m+1 a1,n 1 1 c2 x2 b20 0 a2,m+1 a2,n 2 2 0 0 cm xm bm0 1 am,m+1 am,n n n -Z -c cibi0 0 cm+1 -c ci iai,m+1 cn -c ci iai,nnmjaccmiijijj, 1,1行第 laaaaPmklkkkk010021时达到最优。化时，当是任意大的数。求最小07 , 2 , 1, 012324112003min31532143217654321jjMjxxxxxxxxxxxxxxxxxxz7 76 6x xx xMMM

6、M3,2,1,0123241123min31321321321jxxxxxxxxxxxxzj 一.大M法 时达到最优。化时，当是任意大的数。求最小07 , 2 , 1, 012324112003min7316532143217654321jjMjxxxxxxxxxxxxxMxMxxxxxxz3,2,1,0123241123min31321321321jxxxxxxxxxxxxzj cj-31100 M M CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x4111-21100011 M x63-4120-110 3|2 M x71-20 100011 j 6M-3 1-M 1-

7、3M0 M0 00 0时达到最优。化时，当是任意大的数。求最小07 , 2 , 1, 012324112003min7316532143217654321jjMjxxxxxxxxxxxxxMxMxxxxxxz cj -31100 M M0 CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x412 3001-22-541 x210100-11-21 x31-2010001jj-10001 M-1 M+1 -3 1 1 0 0 M M cj CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x4103-20100-1 M x610 100-11-211 x31-201

8、0001 j-1 1-M00 M0 0 3M-1 CB XB b x1 x2 x3 x4 x5 x6 x7 i-3 x14100 1|3 -0.667 2|3 -1.666671 x210100-11-21 x39001 2|3 -1.333 4|3 -2.33333jj000 1|3 1|3 M-1|3 M-2|3 cj -3 1 1 0 0 M M2, 0, 9, 1, 407654321zxxxxxxxj 3,2,1,0123241123min31321321321jxxxxxxxxxxxxzj: 7 , 2 , 1, 012324112min73165321432176jxxxxxxx

9、xxxxxxxxzj cj 0000011 CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x4111-211000111 x63-4120-110 3|21 x71-20 100011 j6-1-3010 00 07 , 2 , 1, 012324112min73165321432176jxxxxxxxxxxxxxxxzj cj 00000110 CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x4123001-22-540 x210100-11-20 x31-2010001jj00000011人工变量已经换出，那么=0，得到基可行解，将第一阶段的人工变量取消

10、，填入原问题的目的函数的系数，进展第二阶段运算。 cj 0 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 x7 i0 x4103-20100-11 x610 100-11-210 x31-2010001 j0-10010 03 cj-31100 CB XB b x1 x2 x3 x4 x5 i0 x412 3001-241 x210100-11 x31-20100jj-10001人工变量已经换出，那么=0，得到基可行解，将第一阶段的人工变量取消，即上表中划去人工变量所在列，填入原问题的目的函数的系数，进展第二阶段运算。 cj -31 1 0 0 CB XB b x

11、1 x2 x3 x4 x5 i-3 x14100 1|3 -0.6671 x210100-11 x39001 2|3-1.333jj2000 1|3 1|3最优解为：x 1,=4 ,x 2,=1, x 3=9, 最优值z=-2. 产品名称 规格要求单价元/kg A 原材料C不少于50， 原材料P不超过25 50 B原材料C不少于25， 原材料P不超过50 35 D 不限 25)xx(x)xx(x)xx(x)xx(x)xx(x)xx(xzijxxxxxxxxxx)xx(xx)xx(xx)xx(xx)xx(xx33231335322212253121116533323125232221351312

12、1150max0603323131003222121003121112322212122232221412113121141121312112111产品名称 规格要求单价元/kg A 原材料C不少于50， 原材料P不超过25 50 B原材料C不少于25， 原材料P不超过50 35 D 不限 25 原材料 产品 C P H A x11 x12 x13 B x21 x22 x23 D x31 x32 x33 1 2 3 4 5 A B C D 300000,400000; 5 , 4 , 3 , 2 , 1, 0,03. 104. 103. 104. 103. 104. 103. 1100000003. 108. 105. 104. 1max234353244213331222115234CBiDiCiBiADADDADADADBADDCADADCBAxxixxxxxxxxxxxxxxxxxxxxxxxxxxz cj 2100 CB XB b x1 x2 x3 x4 i0 x35-11100 x4102-50150 x5120 400121000 cj 2100 CB XB b x1 x2 x3 x4 i0 x3100-1.510.52 x151-2.500.50 x5120 40010600 cj2