运筹学1线性规划课件.ppt

1、第1页，共72页。产产品品（万万件件）原原料料（公公斤斤）A B C D 提提供供量量 甲 3 2 10 4 18 乙 0 0 2 1/2 3 利利润润（万万元元/万万件件）9 8 50 19 第2页，共72页。第3页，共72页。第4页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 18 0 x6 0 0(2)1/2 0 1 3 9 8 50 19 0 0 第5页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 18 0 x6

2、 0 0 1 1/4 0 1/2 3/2 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 18 0 x6 0 0(2)1/2 0 1 3 9 8 50 19 0 0 第6页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 0 3/2 1-5 3 50 X3 0 0 1 1/4 0 1/2 3/2 9 8 0 13/2 0-25 75 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 1

3、8 0 x6 0 0 1 1/4 0 1/2 3/2 第7页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 0 3/2 1-5 3 50 X3 0 0 1 1/4 0 1/2 3/2 9 8 0 13/2 0-25 75 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 0 3/2 1-5 3 50 X3 0 0 1 1/4 0 1/2 3/2 9 8 0 13/2 0-25 75 第8页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5

4、 x6 b 9 X1 1 2/3 0 1/2 1/3-5/3 1 50 X3 0 0 1 1/4 0 1/2 3/2 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 0 3/2 1-5 3 50 X3 0 0 1 1/4 0 1/2 3/2 9 8 0 13/2 0-25 75 第9页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 9 X1 1 2/3 0 1/2 1/3-5/3 1 50 X3 0 0 1 1/4 0 1/2 3/2 0 2 0 2-3-10 84 cj 9 8 50 1

5、9 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 0 3/2 1-5 3 50 X3 0 0 1 1/4 0 1/2 3/2 9 8 0 13/2 0-25 75 第10页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 8 X2 3/2 1 0 3/4 1/2-5/2 3/2 50 X3 0 0 1 1/4 0 1/2 3/2 -3 0 0 1/2-4-5 37 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 9 X1 1 2/3 0 1/2 1/3-5/3 1 50 X3

6、0 0 1 1/4 0 1/2 3/2 0 2 0 2-3-10 84 第11页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 8 X2 2 4/3 0 1 2/3-10/3 2 50 X3 0 0 1 1/4 0 1/2 3/2 -3 0 0 1/2-4-5 37 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 8 X2 3/2 1 0 3/4 1/2-5/2 3/2 50 X3 0 0 1 1/4 0 1/2 3/2 -3 0 0 1/2-4-5 37 第12页，共72页。cj 9 8 50 19 0

7、0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 8 X2 2 4/3 0 1 2/3-10/3 2 50 X3 0 0 1 1/4 0 1/2 3/2 -3 0 0 1/2-4-5 37 第13页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/

8、3 1 -4-2/3 0 0-13/3-10/3 88 第14页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 18 0 x6 0 0 2 1/2 0 1 3 9 8 50 19 0 0 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第15页，共72页。第16页，共72页。cj 9 8 50 19 0 0 cB X

9、B x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 0 x5 3 2 10 4 1 0 18 0 x6 0 0 2 1/2 0 1 3 9 8 50 19 0 0 第17页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/

10、6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第18页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第19页，共72页。第20页，共72页。cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4+a-2/3 0 0-13/

11、3-10/3 88 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第21页，共72页。第22页，共72页。cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4+a-2/3 0 0-13/3-10/3 88 cj 9+a 8 50 19 0 0 cB

12、XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4+a-2/3 0 0-13/3-10/3 88 第23页，共72页。cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 1 2/3 0 1/2 1/3-5/3 1 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4+a-2/3 0 0-13/3-10/3 88 cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0

13、1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4+a-2/3 0 0-13/3-10/3 88 第24页，共72页。cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 9+a X1 1 2/3 0 1/2 1/3-5/3 1 50 X3 0 0 1 1/4 0 1/2 3/2 0 6-2a 3 0 4-a 2-9-a 3 5a-30 3 84+a cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 1 2/3 0 1/2 1/3-5/3 1 50 X3-1/2-1/3

14、1 0-1/6 4/3 1 -4+a-2/3 0 0-13/3-10/3 88 第25页，共72页。cj 9+a 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 9+a X1 1 2/3 0 1/2 1/3-5/3 1 50 X3 0 0 1 1/4 0 1/2 3/2 0 6-2a 3 0 4-a 2-9-a 3 5a-30 3 84+a 第26页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3

15、 0 0-13/3-10/3 88 第27页，共72页。cj 9 8 50+a 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50+a X3-1/2-1/3 1 0-1/6 4/3 1 a-8 2 a-23 0 0 a-266-4a-10 3 88+a 第28页，共72页。cj 9 8 50+a 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50+a X3-1/2-1/3 1 0-1/6 4/3 1 a-8 2 a-23 0 0 a-266-4a-

16、10 3 88+a 第29页，共72页。cj 9 8 50+a 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50+a X3-1/2-1/3 1 0-1/6 4/3 1 a-8 2 a-23 0 0 a-266-4a-10 3 88+a 第30页，共72页。第31页，共72页。第32页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-

17、10/3 88 第33页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2+(2/3)a 50 X3-1/2-1/3 1 0-1/6 4/3 1-(1/6)a -4-2/3 0 0-13/3-10/3 88+(13/3)a 第34页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2+(2/3)a 50 X3 3/2 1-3 0 1/2-4 (1/2)a-3 -4-2/3 0 0-13/3-10/3

18、 88+(13/3)a cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2+(2/3)a 50 X3-1/2-1/3 1 0-1/6 4/3 1-(1/6)a -4-2/3 0 0-13/3-10/3 88+(13/3)a 第35页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2+(2/3)a 50 X3 3/2 1-3 0 1/2-4 (1/2)a-3 -4-2/3 0 0-13/3-10/3 88+(1

19、3/3)a cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 0 0 4 1 0 2 6 8 X2 3/2 1-3 0 1/2-4 (1/2)a-3 -3 0-2 0-4-6 90+4a 第36页，共72页。cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 0 0 4 1 0 2 6 8 X2 3/2 1-3 0 1/2-4 (1/2)a-3 -3 0-2 0-4-6 90+4a 第37页，共72页。第38页，共72页。第39页，共72页。第40页，共72页。第41页，共72页。cj 9 8 50

20、19 0 0 17 cB XB x1 x2 x3 x4 x5 x6 x 7 b 19 X4 2 4/3 0 1 2/3-10/3-4/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 5/6 1 -4-2/3 0 0-13/3-10/3 2/3 88 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第42页，共72页。cj 9 8 50 19 0 0 17 cB XB x1 x2 x3 x4

21、 x5 x6 x 7 b 19 X4 2 4/3 0 1 2/3-10/3-4/3 2 50 X3-3/5-2/5 6/5 0-1/5 8/5 1 6/5 cj 9 8 50 19 0 0 17 cB XB x1 x2 x3 x4 x5 x6 x 7 b 19 X4 2 4/3 0 1 2/3-10/3-4/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 5/6 1 -4-2/3 0 0-13/3-10/3 2/3 88 第43页，共72页。cj 9 8 50 19 0 0 17 cB XB x1 x2 x3 x4 x5 x6 x 7 b 19 X4 6/5 4/5 8/5 1 2

22、/5-6/5 0 18/5 17 X7-3/5-2/5 6/5 0-1/5 8/5 1 6/5 -18/5-2/5-4/5 0-21/5-22/5 0 88(4/5)cj 9 8 50 19 0 0 17 cB XB x1 x2 x3 x4 x5 x6 x 7 b 19 X4 2 4/3 0 1 2/3-10/3-4/3 2 50 X3-3/5-2/5 6/5 0-1/5 8/5 1 6/5 第44页，共72页。cj 9 8 50 19 0 0 17 cB XB x1 x2 x3 x4 x5 x6 x 7 b 19 X4 6/5 4/5 8/5 1 2/5-6/5 0 18/5 17 X7-3

23、/5-2/5 6/5 0-1/5 8/5 1 6/5 -18/5-2/5-4/5 0-21/5-22/5 0 88(4/5)第45页，共72页。第46页，共72页。第47页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 4 3 5 2 0 0 1 8 -4-2/3 0 0-13/3-10/3 0 88 cj 9 8 50 19 0 0 cB XB x1 x2 x3 x4 x5 x6 b 19 X4 2 4/3

24、 0 1 2/3-10/3 2 50 X3-1/2-1/3 1 0-1/6 4/3 1 -4-2/3 0 0-13/3-10/3 88 第48页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 4 3 5 2 0 0 1 8 -4-2/3 0 0-13/3-10/3 0 88 第49页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/

25、3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 0 1/3 5 0-4/3 20/3 1 4 cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 4 3 5 2 0 0 1 8 -4-2/3 0 0-13/3-10/3 0 88 第50页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3

26、 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 5/2 2 0 0-1/2 0 1-1 cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 0 1/3 5 0-4/3 20/3 1 4 第51页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3

27、-1/2-1/3 1 0-1/6 4/3 0 1 0 X7 5/2 2 0 0-1/2 0 1-1 第52页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7-5 -4 0 0 1 0-2 2 cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7

28、 5/2 2 0 0-1/2 0 1-1 第53页，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 16/3 4 0 1 0-10/3 4/3 2/3 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7-5 -4 0 0 1 0-2 2 cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 2 4/3 0 1 2/3-10/3 0 2 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7-5 -4 0 0 1 0-2 2 第54页，共72

29、页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 16/3 4 0 1 0-10/3 4/3 2/3 50 X3-4/3-1 1 0 0 4/3-1/3 4/3 0 X5-5 -4 0 0 1 0-2 2 -77/3-18 0 0 0-10/3-26/3 79.5 cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 16/3 4 0 1 0-10/3 4/3 2/3 50 X3-1/2-1/3 1 0-1/6 4/3 0 1 0 X7-5 -4 0 0 1 0-2 2 第55页

30、，共72页。cj 9 8 50 19 0 0 0 cB XB x1 x2 x3 x4 x5 x6 X7 b 19 X4 16/3 4 0 1 0-10/3 4/3 2/3 50 X3-4/3-1 1 0 0 4/3-1/3 4/3 0 X5-5 -4 0 0 1 0-2 2 -77/3-18 0 0 0-10/3-26/3 79.5 第56页，共72页。第57页，共72页。第58页，共72页。影子价格是对系统资源的最优估计，影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为最与资源这种价值。因此，也称为最优价格。优价格。第5

31、9页，共72页。第60页，共72页。第61页，共72页。第62页，共72页。第63页，共72页。第64页，共72页。第65页，共72页。第66页，共72页。如果某资源的影子价格高于市场价格，表明如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。该资源在系统内有获利能力，应买入该资源。第67页，共72页。如果某资源的影子价格高于市场价格，表明该如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。该资源在系统内无获利能力，应卖出该资源。第68页，共72页。第69页，共72页。如果某资源的对偶解大于零，表明该资源在系如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。统内有获利能力，应买入该资源。第70页，共72页。如果某资源的对偶解大于零，表明该资源在系如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。统内有获利能力，应买入该资源。如果某资源的对偶解小于零，表明该资源如果某资源的对偶解小于零，表明该资源在系统内无获利能力，应卖出该资源。在系统内无获利能力，应卖出该资源。第71页，共72页。第72页，共72页。