1 (1) & 2014 4 9 ( ) (1) 2014 4 9 1 / 39
2013 ( ) (1) 2014 4 9 2 / 39
OR 1 OR 2 OR Excel ( ) (1) 2014 4 9 3 / 39
1 (4 9 ) 2 (4 16 ) 3 (4 23 ) 4 (4 30 ) 5 (5 7 ) 6 (5 14 ) 7 1 (5 21 ) ( ) (1) 2014 4 9 4 / 39
8 ( ) (5 28 ) 9 ( ) (6 4 ) 10 ( ) (6 11 ) 11 2 (6 18 ) 12 ( ) (6 25 ) 13 ( ) (7 2 ) 14 ( ) (7 9 ) 15 ( ) (7 16 ) ( ) ( ) (1) 2014 4 9 5 / 39
( ) 6 10 61022 : 14:50 16:20 E-mail jgoto@indsys.chuo-u.ac.jp Web www.indsys.chuo-u.ac.jp/ jgoto/ Web www.indsys.chuo-u.ac.jp/ jgoto/opt.html 20 ( ) (1) 2014 4 9 6 / 39
70 20 14:50 16:20 ( ) (1) 2014 4 9 7 / 39
20 ( ) (1) 2014 4 9 8 / 39
2 1 2 4 1 25 60 110 100 100 ( ) (1) 2014 4 9 9 / 39
OK ( ) (1) 2014 4 9 10 / 39
( ) (1) 2014 4 9 11 / 39
1 2 3 ( ) (1) 2014 4 9 12 / 39
(linear program) x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 R ( ) (linear programming) ( ) (1) 2014 4 9 13 / 39
(linear programming) JISZ8121 D5 1 1 LP 4 ( ) (1) 2014 4 9 14 / 39
x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 R x 1 = 3, x 2 = 0 6 ( ) 2 1 2 1 x 2 x 1 2x 2 = 2 2x 1 3x 2 = 6 O 3 ( ) (1) 2014 4 9 15 / 39 x 1
x 1,x 2 x 1 x 2 x 1 x 2 1, x 1 + x 2 1, x 1 0, x 2 0, x 1, x 2 R x 2 x 1 +x 2 = 1 ( ) 1 1 1 O 1 x 1 x 2 = 1 x 1 ( ) (1) 2014 4 9 17 / 39
x 1,x 2 2x 1 3x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 R ( ) 2 3 2 x 2 x 1 2x 2 = 2 1 2x 1 3x 2 = 6 O 3 x 1 ( ) (1) 2014 4 9 18 / 39
1 1 ) ( ) 2 1 2 1 O x2 x1 2x2 = 2 2x1 3x2 = 6 x1 3 ( ) 1 1 1 O x 2 1 x 1 +x 2 = 1 x 1 x 2 = 1 x 1 ( ) 1 1 1 O x 2 1 x 1 +x 2 = 1 x 1 x 2 = 1 x 1 ( ) (1) 2014 4 9 19 / 39
2 2 ( ) 2 3 2 x 2 x 1 2x 2 = 2 1 2x 1 3x 2 = 6 O 3 x 1 ( ) (1) 2014 4 9 20 / 39
(simplex methods) Dantzig ( ) (interior-point methods) Karmarkar ( ) ( ) (1) 2014 4 9 21 / 39
1 2 3 ( ) (1) 2014 4 9 22 / 39
(integer program) x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 Z ( ) (integer programming) ( ) (1) 2014 4 9 23 / 39
(mixed integer program) x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1 Z, x 2 R ( ) (mixed integer programming) ( ) (1) 2014 4 9 24 / 39
(linear programming) JISZ8121 D10 4 R n S f : S R ( ) A R m n b R m c R n x = (x 1, x 2,..., x n ) R n P 0 : {c x Ax = b, x j 0 (j = 1,..., n), x j (j = 1,..., n 1 )} n 1 n ( ) (1) 2014 4 9 25 / 39
x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 Z x 1 = 3, x 2 = 0 6 ( ) 2 1 2 1 x 2 x 1 2x 2 = 2 2x 1 3x 2 = 6 O 3 ( ) (1) 2014 4 9 26 / 39 x 1
x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1 Z, x 2 R x 1 = 3, x 2 = 0 6 ( ) 2 1 2 1 x 2 x 1 2x 2 = 2 2x 1 3x 2 = 6 O 3 ( ) (1) 2014 4 9 27 / 39 x 1
0-1 0-1 (0-1 integer program) x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 {0, 1} 0 1 ( ) 0-1 (integer programming) 0-1 0-1 ( ) (1) 2014 4 9 28 / 39
0-1 0-1 x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1, x 2 {0, 1} x 1 = 1, x 2 = 0 2 ( ) 2 1 2 1 x 2 x 1 2x 2 = 2 2x 1 3x 2 = 6 O 3 ( ) (1) 2014 4 9 29 / 39 x 1
0-1 0-1 x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1, x 2 {0, 1} x 1,x 2 2x 1 + x 2 2x 1 3x 2 6, x 1 2x 2 2, x 1 0, x 2 0, x 1 1, x 2 1, x 1, x 2 Z 0-1 ( ) (1) 2014 4 9 30 / 39
LP IP MIP ( ) (1) 2014 4 9 31 / 39
( ) ( ) (1) 2014 4 9 32 / 39
R. Bixby (2012) 1991 2012 475,000 2,000 http://www.orie.cornell.edu/news/index.cfm?news id=62130 ( ) (1) 2014 4 9 33 / 39
1 2 3 ( ) (1) 2014 4 9 34 / 39
3 ( ) ( ) (1) 2014 4 9 35 / 39
50 2005 2014 ( ) (1) 2014 4 9 36 / 39
( ) ( ) ( ) ( ) ( ) ( ) (1) 2014 4 9 37 / 39
( ) OK ( ) (1) 2014 4 9 38 / 39
1 2 3 ( ) (1) 2014 4 9 39 / 39