Luận văn: Bài toán tối ưu với hàm thuần nhất dương

Chia sẻ: Greengrass304 Greengrass304 | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

148
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hàm thực thuần nhất dương ( còn gọi đơn giản là hàm thuần nhất) rất quen thuộc và hay gặp trong nhiều ứng dụng, đặc biệt trong nghiên cứu kinh tế vi mô. Hàm tuyến tính, hàm bậc hai, hàm Cobb-Douglas, các hàm đa thức thuần nhât...là ví dụ về hàm thuần nhất dương. Hàm thuần nhất biểu lộ hành vi rất đều đặn, khi mọi biến tăng theo cùng 1 tỷ lệ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: Bài toán tối ưu với hàm thuần nhất dương

®¹i häc Th¸i Nguyªn Tr-êng ®¹i häc khoa häc -------------  0  ------------- NguyÔn Xu©n Huy Bµi to¸n tèi -u víi hµm thuÇn nhÊt d-¬ng LuËn v¨n th¹c sÜ to¸n häc Th¸i Nguyªn - 2009
®¹i häc Th¸i Nguyªn Tr-êng ®¹i häc khoa häc -------------  0  ------------- NguyÔn Xu©n Huy Bµi to¸n tèi -u víi hµm thuÇn nhÊt d-¬ng Chuyªn ngµnh: To¸n øng dông M· sè: 60.46.36 LuËn v¨n th¹c sÜ to¸n häc Ng-êi h-íng dÉn khoa häc GS-TS TrÇn Vò ThiÖu Th¸i Nguyªn - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
Å Ð Ä Ò Ùº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ¾ ½ Æ Ò ÒØ Ú ò Ø Ð ½º½ Ì Ô Ò Úñ Ø Ô Ð ººººººººººººººººººººººººº ½º¾ ÀñÑ Ð ººººººººººººººººººººººººººººººº ½ ¾ ô ñ ØÓôÒ Ø Ù ½ ¾º½ ô ô Ò Ñ òÒ ººººººººººººººººººººººº ½ ¾º¾ ñ ØÓôÒ Ø Ù Ò ÖñÒ Ù º º º º º º º º º º º º º º º º º º ¾¿ ¾º¿ ñ ØÓôÒ Ø Ù ÖñÒ Ù ºººººººººººººººººººº ¾ ¿ ñ ØÓôÒ Ø ÙÚ ñÑ Ø Ù Ò Ò Ø Ò ¿¾ ¿º½ ÀñÑ Ø Ù Ò Ò Ø ºººººººººººººººººººººººººº ¿¾ ¿º¾ ñ ØÓôÒ Ø ÙÚ ñÑ Ø Ù Ò Ò Ø Ò ººººººººººººº ¿ ¿º¿ ô Ø ÕÙò Ò Ù Ò ºººººººººººººººººººº ¿ ¿º Ì Ù ØÓñÒ º º º º º º º º º º º º º º º º º º º º º º º º º º º Ã Ø ÐÙ Ò ººººººººººººººººººººººººººººººººº ¿ Ìñ Ð Ù Ø Ñ òÓ ººººººººººººººººººººººººººº ½
ÄÒ Ù ÀñÑ Ø Ø Ù ÒÒ Ø Ò ´ Ò Ò òÒ Ðñ ñÑ Ø Ù Ò Ò Øµ Ö Ø ÕÙ Ò Ø Ù Úñ Ý Ô ØÖÓÒ Ò Ù Ò Ò ¸ Ø ØÖÓÒ Ò Ò Ù Ò ØÚ Ñ º ÀñÑ ØÙÝ Ò Ø Ò ¸ ñÑ ¸ ñÑ Ó ¹ ÓÙ Ð ×¸ ô ñÑ Ø Ø Ù Ò Ò Ø ººº Ðñ ô Ú Ú ñÑ Ø Ù Ò Ò Ø Ò º ÀñÑ Ø Ù Ò Ò Ø ÙÐ ñÒ Ú ÖØ Ù Ò¸ Ñ ÒØ Ò Ø Ó Ò Ñ ØØ Ð º øÒ õÒ¸ Ú ñÑ Ø Ù Ò Ò Ø ¼¸ ô ÒØ Ý Ø Ó Ò Ñ ØØ Ð Ø ô ØÖ ñÑ Ò Ø Ý Ú ñÑ Ø Ù Ò Ò Ø ½¸ ØÒ Ô ´ Ô µÑ ÒØ ô ØÖ ñÑ Ò Ø Ò Ô ´ Ô µº Å Ø ØÖ Ò ÕÙ Ò ØÖ Ò ñÑ ØÙÒÒ Ø Ðñ ô õÓ ñÑ Ö Ò ÑØ ñÑ Ø Ù Ò Ò Ø Ò Ðñ Ñ Ø ñÑ Ø Ù ÒÒ Ø Úñ ô ñÑ Ø Ù Ò Ò Ø Ø Ù Ò ÕÙ ô õÓ ñÑ Ö Ò Ò´ ÒÐ ÙÐ Öµº Øñ ÐÙ Ò Ú Ò ÔØ Ð Ô ñ ØÓôÒ Ø ÙÚ ô ñÑ Ø Ù Ò Ò Ø Ò¸ Ò Ðñ ñÑ Ñ Ø Ù Úñ ô ñÑ ÖñÒ Ù ñ ØÓôÒ Ù Ðñ ô ñÑ Ø Ù Ò Ò Ø´ Ø ô Ò Ùµº ÉÙ Óõ ØÙÝ Ò Ø Ò Úñ ÕÙ Óõ Ðñ Ò Ò ØÖ Ò ÔÖ Ò Ð Ô ñ ØÓôÒ ÒñÝº Î Ø Ñ Ù ñ ØÓôÒ Ø ÙÚ ô ñÑ Ø Ù Ò Ò Ø Ò Ðñ ÓñÒ ØÓñÒ Ò Ø Ø Úñ Ù ¸ ÔØ Ù× Ù Ò Ú ô ñ ØÓôÒ¸ Ô Ò Ô ôÔ Ø ÙÔ ØÙÝ Ò Úñ Ñ ÖÒ Ô õÑ Ú Ò Ò Òº Å Ø Ù ÐÙ Ò Ú Ò Ðñ Ø Ñ Ù Úñ ØÖ Ò ñÝ Ñ Ø × Ø ÕÙò òÒ Ð Ò ÕÙ Ò Ø ñ ØÓôÒ Ø ÙÚ ô ñÑ Ø Ù Ò Ò Ø Òº ô Ú Ò Ô ØÖÓÒ ÐÙ Ò Ú Ò ØÖ Ò ñÝ Ñ Ø ô Ø Ú Ñ Ø ØÓôÒ ¸ Ñ Ø × ôÒÑ Úñ × Ò Ò Ù ØÖÓÒ ÐÙ Ò Ú Ò ÑØ ÓÚ Úñ ÒÚ ÑÒ Óõº Æ ÙÒ ÐÙ Ò Ú Ò Ø ñÒ Ò Ò ½ ãÆ ä Ø Ù ÚúÒ ØúØ Ñ Ø × Ò Ò ÒØ Ú ò Ø Ð Ø òÒ¸ Ò Ø ØÚ ò Ø Ð Ò ô ô Ò ÑÚ ØÔ Ò Úñ Ó Ò ¸Ø ÔÐ Úñ ÓÐ ¸Ò ÒÐ Úñ Ø Ô Ð Ò¸ Ò Ú ô ôÒ Ñ Ò¸ õÒ ¸ Ò Ø ÔÐ Ò Úñ ô ô Ò ÑÚ ñÑ Ð ¸ ñÑ Ð Ø Ò ¾
Ñ Ø× ØÒ Ø òÒ ÒºÆ ÙÒ ØÖ Ò ñÝ ØÖÓÒ Ò ÒñÝ × Ò Ò Ò × Ù¸ Ò Ò Ù ô ñ ØÓôÒ Ø ÙÔ ØÙÝ Ò Ò ÙÒ Úñ ñ ØÓôÒ Ø ÙÚ ñÑ Ø Ù Ò Ò Ø ÒÒ Ö Òº Ò ¾ ã ô Ùä ØÖ Ò ñÝ ÚúÒ ØúØ ô ô Ò Ñ Úñ Ø ÕÙò ñ ØÓôÒ Ø Ú ñ ØÓôÒ Ø ÙÔ ØÙÝ Ò¸ Ô Ò ØØ Ù Ô Ò Úñ Ø Ù ØÓñÒ ¸ Ø Ù Ò ÖñÒ Ù Úñ Ø Ù ÖñÒ Ù ¸ ô Ù Ò Ò Úñ Ù Ò Ø Ù¸ Ø Ðñ Ù Ò ÃÃÌ Ó Ø Ù ÖñÒ Ù º ô ô Ò Ñ Ò Ò Ø Ô Ü ¸ ô Ò Ñ Ò ÕÙÝ¸ ñÑ Ä ÖÒ Úñ Ò ÒØ Ä ÖÒ Ò Ø Ùº Æ ÙÚ ó Ö ÑÒ Óõ Ó ô ô Ò Ñ Úñ Ø ÕÙò ØÖ Ò ñÝº Ò ¿ ã ñ ØÓôÒ Ø ä ÔØ ÐÔ ñ ÙÚ ñÑ Ø Ù Ò Ò Ø Ò ØÓôÒ Ø ÙÔ ØÙÝ Ò Ú ô ñÑ Ø Ù Ò Ò Ø Òº ñ ØÓôÒ ÜØ Ø Ò õØ Ò ÑØ ñ ØÓôÒ ãmin-maxä Ò òÒ¸ Ú ãmaxä Ðñ ñ ØÓôÒ ØÙÝ Ò ØÒ Ø Ò Ø Ò Ñ Ø ÖñÒ Ù ÙÝ Ò Øº Ì Ò Ù ô Ò õØ Ñ Ó ÕÙ Óõ ØÙÝ Ò Ø Ò Úñ ÕÙ Óõ ØÓñÒ Ô Ò ÖñÒ Ù ØÙÝ Ò Ø Ò º Î Ò Ò òØ ØÒ Ø Ò ¸ Ø Ö ñ ØÓôÒ Ø Ù ÒÐ Ø Ò ÒÚ ñ ØÓôÒ Ø ÙÐ º ÓØ Ò õÒ Ò Ò ÐÙ Ò Ú Ò ÒñÝ Ñ Ò Ðõ Ú ØÑ Ù Øñ Ð Ù¸ ×úÔ Ü Ô Úñ ØÖ Ò ñÝ ô Ø ÕÙò Ò Ò Ù ó Ø Ó ØÖº ÌÖÓÒ ÕÙô ØÖ Ò Ú Ø ÐÙ Ò Ú Ò Ò Ò ØÖÓÒ Ü Ð Ú Ò òÒ ú úÒ Ò ØÖôÒ Ò Ò × × ØÒ Ø Ò º Ìô ò ÐÙ Ò Ú Ò Ö Ø ÑÓÒ Ò Ò × Ô ô Ø Ý Úñ ô õÒ ÒÒ Ô ÐÙ Ò Ú Ò ÓñÒ Ø Ò Òº Æ Ò Ô ÒñÝ¸ Øô òÜÒ ñÝ Ø ÐÒ Ø Ò × Ù ×ú ÒØ Ý Ò Ò Ë¹ÌË ÌÖ Ò Î Ì Ù óØ ÒØÒ Ô ØÖÓÒ ×Ù Ø ÕÙô ØÖ Ò ÐñÑ ÐÙ Ò Ú Òº Ìô òÜÒ Ò Ø ñÒ òÑ Ò ô Ø Ý¸ ÎÒ Ò Ò Ø Ò Ø Ò¸ Î Ò ÌÓôÒ Àñ Æ ¸ Ã Ó ÒÒ Ø Ò Ø Ò¸ Ã Ó ÌÓôÒ Úñ È Ò ñÓ ØõÓ × Ù õ ØÖ Ò õ Ã Ó ¹ õ Ì ô Æ ÙÝ Ò óØ ÒØÒ òÒ õÝ Úñ ØõÓ Ñ Ù ÒØ Ù ÒÐ Ó Øô ò ØÖÓÒ ÕÙô ØÖ Ò Ø Ô Øõ ØÖ Òº ¿
Ìô ò Ò ÜÒ Ò Ø ñÒ òÑ Ò Ò ÐóÒ õÓ Ë ôÓ Úñ ñÓ ØõÓ ÉÙòÒ ÆÒ ¸ Ò ôÑ Ù Úñ ô Ø Ý ôÓ ÌÖ Ò ÌÀÈÌ ÀÓñÒ ÉÙ Î Ø¸ Ò Øô ò Ò Øô ó ØõÓ Ò Ò Ù ÒØ Ù ÒÐ Ò Ø Øô ò ÓñÒ Ø ñÒ Ò Ñ Ú Ø Ôº Ìô ò Ò Ü Ò ñÝ Ø × ÕÙ Ñ Ò Úñ Ð Ò Ø Ò × Ù ×ú Ø Ñ¸ Ò Úñ Ò Ø Ò ó ÐÙ Ò ÙÝ Ò ¸ Ò Ú Ò Øô ò ØÖÓÒ ×Ù Ø ÕÙô ØÖ Ò Ó Úñ Ú Ø ÐÙ Ò Ú Ò ÒñÝº Àñ Æ ¸ Ø ôÒ »¾¼¼ Ìô ò
Ò½ Æ Ò ÒØ Ú ò Ø Ð Ò ÒñÝ Ò ú Ðõ ÚúÒ ØúØ Ñ Ø × ÒØ òÒ¸ Ò Ø ØÚ ò Ø Ð ´Ø Ô Ð ¸ ñÑ Ð Úñ ô Ø Ò Øµ Ô Ú Ó Ø Ñ Ù Úñ Ò Ò Ù ô ñ ØÓôÒ Ø Ùº Æ ÙÒ ØÖ Ò ñÝ Ò ÒñÝ ÝÙ ØÖ Ò ô Øñ Ð Ù ½℄¸ ¾℄º ½º½ Ì Ô Ò Úñ Ø ÔÐ ½º½º½º Ì Ô Ò x1¸ x2 Ðñ x1¸ x2 Ðñ Ø Ô ô Rn º Ó Ñ ØÖÓÒ ÕÙ Ñ Ò Ø øÒ x = λx1 + (1 − λ)x2 = x2 + λ(x1 − x2 ) ¸ λ ∈ R ⊆ Rn Ì ÔM Ðñ Ø Ò ÙM Ò ò Ò Ø øÒ ÕÙ Ô Ò M ¸ Ø Ðñ ∀x1, x2 ∈ M ¸ λ ∈ R ⇒ λx1 + (1 − λ)x2 ∈ M º Ñ Ø ØÙ Æ ô ô ¸ M Ðñ Ø Ô Ò Ò ÙÒ Ø Ô ØÙÝ Ò Ø Ò Ñ Ø ØÙ MÚ Ø Ò ô × ÷Ò 1º Ì ÑØ Ñ x∈R õÒ k λi xi x= i=1 Ú λ1 , λ2, · · · , λk ∈ R Úñ k λi = 1 i=1
λ1 , λ2 , · · · , λk ∈ Rn º Æ Ù M ⊆ Rn Ðñ Ñ Ø Ø Ô Ðñ ô Ñ Ø Ô Ò x0 ∈ M Ø L = M − x0 = x − x0 | x ∈ M Ðñ Ñ Ø Ò Úñ ØÔ Ò Ò ÓÒ¸ Ø Ðñ Ò Ù a, b ∈ L Ø Ñ Ñ c = λa + µb Ú λ, µ ∈ R Ò Ø Ù L ´L ÒÚ Ô Ô Ò Úñ Ô Ô Ò ÒÚ Ò µº Î Ú Ý¸ Ñ Ø Ø Ô Ò Ø Ù Ò M = x0 + L = x0 + v | v ∈ L ¸ x0 ∈ M Úñ L Ðñ ØÖÓÒ Ò Ò ÓÒº Ã Ò Ò ÓÒ LØ Ò Ò Ú x0¸ Ø x0 Ðñ ØÔ Ò Ò Ô Ø Ù ÚñÓ ô Ò Ñ Ø ØÙ M Mº À Ò Ò ¸ Ò Ò ÓÒ L ÒñÝ Üô Ò ÙÝ Ò Øº Ì L Ðñ Ò Ò Ú Mº Ì Ò ÙÝ Ò ´ Ñ Ò× ÓÒµ Ý Ò Ðñ ØÔ ÓÒ ×ÓÒ ×ÓÒ × Ù Ò M Ðñ Ø Ò ÙÝ Ò Ò Ò ÓÒ ×ÓÒ ×ÓÒ Ú Òº E ⊆ Rn Ðñ Ó Ò´ Ò ÙÐÐµ Ñ ØØ Ô Ó Ø Ø ò ô Ø Ô Ò Eº Ðñ Ø Ô ÒÒ Ò Ø E¸ Ù Ðñ aﬀ E º ÌÔÒ Ñ M Ô Ò ØÖ Ò ØÙÝ Ò Ø Ò Ax = b¸ ØÖÓÒ Î ½º½º A Ðñ Ñ ØÖ Ò Ô m × n Úñ Ú Ø b ∈ Rm ¸ Ðñ Ñ Ø Ø Ô ÒºÌ Ø Ú Ý¸ Ú x1, x2 ∈ M ¸ ∀λ ∈ R¸ Ø A λx1 + (1 − λ)x2 = λAx1 + (1 − λ)Ax2 = λb + (1 − λ)b = b ⇒ λx1 + (1 − λ)x2 ∈ M E = x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 Ó Ò ØÔ Î ½º¾º aﬀ E = x ∈ R3 | x3 = 0 º Ðñ Ñ Ø Ô øÒ Ò ÚÙ Ò E ¸ Ø ½º½º¾º Ë Ù Úñ Ñ ØÖÓÒ Ø Ò M ⊆ Rn Ðñ × Ë Ù´ ÝØ Ò ÙÝ Òµ Ñ ØØ Ô Ù Ó Ò M ⊆ Rn dim M < nº Å Ø Ò¸ Ù Ðñ dim M º ÓØ Ô Ñ a∈M Ðñ ´Ö Ð Ø Ú ÒØ Ö ÓÖ ÔÓ ÒØµ M Ò Ù Ø Ò Øõ Ò Ñ ØÖÓÒ Ø Ò ÙÑ B (a, ǫ) × Ó Ó B (a, ǫ) ∩ aﬀ M ⊂ M º Ø Ô M¸ Ù Ðñ ri M ¸ Ðñ Ø Ô Ø Ø ò ô Ñ È Ò ØÖÓÒ Ø Ò M º Å Ø Ø Ô M ⊆ Rn ØÖÓÒ Ø Ò Ðñ Ø Ò ÙÝ Ò Ý ÒÙ dim M = nº Ø Ý Ö÷Ò Ø Ô M Ô Ò ØÖÓÒ ô Ö Ò ´int M = ∅µ Úñ Ò Ø Ò ÙÝ Ò Ý º
E = x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 ¸ Ø Ó Î ½º¿º int E = ∅¸ ri E = x ∈ R3 | 0 < x1 < 1, 0 < x2 < 1, x3 = 0 ¸ Úñ dim E = 2º ½º½º¿º Ì Ô Ð Úñ Ñ Ò x1, x2 ∈ Rn º Ì Ô Ø Ø ò ô Ó Ñ Ñ õÒ x = λx1 + (1 − λ)x2 = x2 + λ(x1 − x2)¸ 0 ≤ λ ≤ 1¸ x1 ¸ x2 ¸ x1 , x2 º Ðñ Ò Ù Ðñ ÓõÒ Ø øÒ M ⊆ Rn ÌÔ Ðñ Ø Ô Ð ´ ÓÒÚ Ü × Øµ Ò Ù Ò Ò ÓõÒ Ø øÒ ∀x1 , x2 ∈ M ¸ 0 ≤ λ ≤ 1 Ø Ò Ñ Ø Ø Ù Ò ¸ Ø Ðñ λx1 + (1 − λ)x2 ∈ M º ´µ ´µ ´µ ´ µ ÀÒ ½º½º ´ µ¸ ´ µ ¹ Ì Ô Ð ´ µ¸ ´ µ ¹ Ì Ô Ò Ð Ì ÒÒ Ø Ý Ö÷Ò Ó ÑØ Ø ô Ø Ô Ð Ðñ Ø Ô Ð º ÌÙÝ Ò Ò Ô ô Ø Ô Ð ú Ðñ Ø Ô Ð º x ∈ Rn Ì Ñ õÒ k λi xi x= i=1 Ú λ1 , λ2, · · · , λk ≥ 0 Úñ k λi = 1 i=1 Ñ x1 , x2 , · · · , xk ∈ Rn º Æ Ù λi ≥ 0 Ú ∀i = 1, 2, · · · , k Ðñ Ø ô ÔÐ x1, x2, · · · , xk ∈ Rn º Ø ØÒ x Ðñ Ø ÔÐ Ø M ⊂ Rn ÅÒ ½º½º Å ØØ Ô Ðñ Ð Úñ Ò Ø Ø ò ô Ø Ô Ð Ò Ò Ô ÒØ Ø Ù Ò º
ÅÒ ½º¾º M ⊂ Rn Ðñ Ø α ∈ Rn Ø αM = {y | y = αx, x ∈ M } µÆ Ù ÔÐ Úñ × Ø Ò Ðñ Ø ÔÐ º M1 , M2 ⊂ Rn µÆ Ù Ðñ Ø ÔÐ Ø M1 + M2 = x | x = x1 + x2, x1 ∈ M1 , x2 ∈ M2 Ò Ðñ Ø ÔÐ º E ⊂ Rn Ðñ ÓÐ ´ ÓÒÚ Ü ÙÐÐµ ØÔ Ó Ø Ø ò ô Ø Ô Ð E Úñ Ù Ðñ conv E º Ðñ Ø Ô Ð Ò Ò Ø Eº convE convE ÀÒ ½º¾º Î Ú ÓÐ E ⊂ Rn ÅÒ ½º¿º ÓÐ Ø Ô Ø Ø ò ô Ø ÔÐ ô Ô Ò Eº Ø Ø Ù M ⊂ Rn º Å Ø ÓØ ÔÐ Ñ Ðñ ´ ÜØÖ Ñ x∈M Ñ Ò ÔÓ ÒØµ M Ò Ùx ÒØ Ù Ò õÒ Ø ÔÐ Ø ÑÔ Ò Ø Ø ÒñÓ M ¸ Ø Ðñ ∃y, z ∈ M, y = z × Ó Ó x = λy + (1 − λ)z, 0 < λ < 1º Ì Ó ÒÒ ¸Ñ Ø Ñ Ò ÒØ Ðñ Ñ ØÖÓÒ Ø ÔÐ ºÎ Ú Ý Ø Ø ò ô Ñ Ò Ù Ðñ ô Ñ Òº Æ Ù Ø Ô Ô Ò ÒØ Ò Ò Ñ Òº M ⊂ Rn ÅÒ ½º º Å ØØ ÔÐ Ò ô Ö Ò Ñ Ò Úñ Ò Ò ÒÑ Ø Ò Ø øÒ ÒñÓº
´µ ´µ ÀÒ ½º¿º ´ µ ¹ À Ò ÚÙ Ò Ñ Ò ´ µ¹ÀÒ ØÖ Ò Ú × Ñ Ò ÅØ ØÖ Ò Ö Ø ÕÙ Ò ØÖ Ò Ø ÔÐ Ò Úñ Ò Ðñ Rn Ò Ð ½º½º ´ÃÖ Ò¹ Å ÐÑ Òµ Å ØØ ÔÐ Ò ¸ Ò ØÖÓÒ Ðñ ÓÐ ô Ñ Ò Ò º ½º½º º Ë Ù Ô øÒ ¸ Ò Ò Ò a ∈ Rn \ {0} Úñ α ∈ Rº Ì Ô Ó H := {x ∈ Rn | < a, x > = α} Ðñ Ñ Ø × ´ ÝÔ ÖÔÐ Ò µº Ðñ Ñ Ø Ø Ô Ò × Ù ÷Ò ÙÔ øÒ n − 1º Ì Ú Ø a Ðñ Ú Ø × Ù Ô øÒ ÒñÝº ô Ø Ô Ô ôÔ ØÙÝ Ò a < a, x >= α x0 x R2 ÀÒ ½º º Ë Ù Ô øÒ ØÖÓÒ {x ∈ Rn |< a, x > ≤ α} ´ Ó {x ∈ Rn |< a, x > ≥ α}µ a ∈ Rn \ {0} Úñ α ∈ Rn Ðñ Ú Úñ Ø Ô Ò Ò Ò Ò {x ∈ Rn |< a, x > < α} ´ Ó {x ∈ Rn |< a, x > > α}µ {x ∈ Rn | < a, x > = α} Ðñ Üô Ò × Ù Ô øÒ Ò Ò ÒÑ M ⊂ Rn ¸ Ú Ø a ∈ Rn \ {0} Úñ × Ø ÓØ Ô α ∈ Rº Ì × Ù Ô øÒ H := {x ∈ Rn | < a, x > = α}
M Øõ x0 ∈ M Ò Ù x0 ∈ H Úñ Ðñ ´×ÙÔÔÓÖØ Ò ÝÔ ÖÔÐ Ò µ × ÙÔ øÒ Ø M Ò÷Ñ Ò ØÖÓÒ Ò Ò Ò Ò Üô Ò H ¸ Ø Ðñ < a, x0 >= α Úñ < a, x > ≤ α, ∀x ∈ M º a x0 M x0 M ÀÒ ½º º Ë Ù Ô øÒ Ø Øõ x0 M ⊂ Rn Ò Ð ½º¾º ÉÙ Ñ Ñ Ò Ø ÔÐ Ø Ò Øõ ØÒ ØÑ Ø x0 º M × ÙÔ øÒ Ø Øõ M ⊂ Rn Ò Ð ½º¿º Å ØØ ÔÐ Ò ô Ö Ò Ðñ Ó ô Ò Ò ÒØ Ò º ½º½º º Æ Ò Úñ Ò Ò Ð M ⊂ Rn ÌÔ Ðñ ´ ÓÒ µ Ò Ù x ∈ M, λ ≥ 0 ⇒ λx ∈ M Ò Ò 0 ∈ Rn º Ì Ô M ⊂ Rn Å Ø Ò Ò ÐÙ Ò Ñ Ðñ ÒÙ Ò ÒÐ x1 , x2 ∈ M Úñ λ1 , λ2 ≥ 0 Ø MÚ Ðñ Ò Ò Ú Ðñ Ð ¸ Ò Ðñ Ú Ø λ1 x1 + λ2 x2 ∈ M º 0 0 ´ µ¹Æ Ò Ò Ð ÀÒ ½º º ´ µ ¹ Æ Ò Ð 0 ØÖÓÒ Rn ô Ø Ô × Ù Ý Ðñ ô Ò Ò Ð Ò Øõ Î ½º º ½¼
• Rn := {x = (x1, x2, · · · , xn) : xi ≥ 0, i = 1, 2, · · · , n} ´ÓÖØ ÒØ Ò + Ñµ • Rn := {x = (x1, x2, · · · , xn) : xi > 0, i = 1, 2, · · · , n} ´ÓÖØ ÒØ Òµ ++ M ⊂ Rn ÅÒ ½º º Ì Ô Ðñ Ò ÒÐ Úñ Ò Ø Ø ò ô Ø Ô ØÙÝ ÒØÒ Ò Ñ ô Ô ÒØ Ò º k Ú Ø v 1 , v 2, · · · , v k ∈ Rn º Ì Ô ÓØ Ô k 1 2 n n λi v i, λi ≥ 0, i = 1, · · · , k ⊂ Rn cone v , v , · · · , v := v ∈ R | v = i=1 v 1, v 2, · · · , v k º Î Ø v h ∈ v 1 , v 2, · · · , v k Ðñ Ò Ò × Ò ØÔ Ðñ ÒØ Ø Ý Ù ´ÒÓÒ ×× ÒØ Ðµ Ò Ù cone v 1 , · · · , v h−1, v h+1, · · · , v k = cone v 1, v 2, · · · , v k º v1 v1 v2 v3 v3 2 v 0 0 ´µ ´µ 2 v ÀÒ ½º º ´ µ ¹ Î Ø Ðñ Ò Ø ØÝ Ù v2 v3 ´ µ ¹ ÀÓ Ú Ø Ó Ú Ø Ðñ Ò Ø ØÝ Ù ½º½º º È Ò Ð Ü ¸Ô Ò Ò D ⊆ Rn º Î Ø d = 0 ÓØÔÐ ô Ö Ò Ðñ Ô Ò Ð Ü ´Ö ×× ÓÒ Ö Ø ÓÒµ DÒ Ù {x + λd | λ ≥ 0} ⊂ D Ú Ñ x ∈ Dº Å Ò Ò Ø øÒ ×ÓÒ ×ÓÒ Ú Ñ ØÔ ÒÐ Ü d ÜÙ Ø Ô ôØ Ø Ñ Ø Ñ Ø Ù Ò÷Ñ Ò ØÖÓÒ Dº Ê ÖñÒ Ö÷Ò Ø Ô D Ò Ò D Úñ D Ñ ØÔ ÒÐ Üº D ⊆ Rn Ò Ú Ø 0 ØõÓ Ø ñÒ Ì Ô Ø Ø ò ô Ô Ò Ð Ü ØÔÐ Ñ ØÒ ÒÐ ºÆ ÒÐ Ðñ Ò Ò Ð Ü ØÔ D Úñ Ù Ðñ rec Dº ½½
d1 Úñ d2 d1 = αd2 Ú ÌÒ Ô Ò ô Ø ´ ×Ø Ò Øµ Ò Ù α > 0º È Ò Ð Ü d ØÔ Ðñ ´ ÜØÖ Ñ Ö Ø ÓÒµ D Ô Ò Ò d1 Úñ d2 DÒÙ Ò Ø Ò Øõ ô Ô ÒÐ Ü ô Ø D× Ó Ó d = λ1d1 + λ2 d2 Ú λ1 , λ2 > 0º ½º½º º ô Ò Ð Øô Ø ÔÐ Ý Ðñ Ò Ò ÒÐ òÒ Ò Ø ò Ø Ð ¸ Ðñ Ò Ù Ù Ð Ø ÙÝ Ø Ø Ùº C, D ⊂ Rn Úñ × Ù Ô øÒ Ó ØÔ H := {x ∈ Rn | < a, x > = α} Ú a ∈ Rn \ {0} Úñ α ∈ R ÌÒ × Ù Ô øÒ ØÔ C Úñ D Ò Ù H Øô < a, x > ≤ α ≤ < a, y > ∀x ∈ C, ∀y ∈ D Úñ × Ù Ô øÒ ´ Ý µ ØÔ C, D Ò Ù H Øô øÒ Øô Ø < a, x > < α < < a, y > ∀x ∈ C, ∀y ∈ D C, D ⊂ Rn Ò Ð ½º º ´ Ò Ð Øô Áµ Æ Ù Ø ÔÐ Ò Ö Ò Úñ Ö Ò ÙØ Ñ Ø× ÙÔ øÒ Øô Ò º C, D ⊂ Rn Ò Ð ½º º ´ Ò Ð Øô ÁÁµ Æ Ù Ø ÔÐ Ò Ò Ö Ò ¸Ö Ò Ù Úñ ØÒ ØÑ Ø ØÖÓÒ Ø Ô Ý Ðñ ÓÑÔ Ø Ñ Ø× ÙÔ øÒ Øô øÒ Ò º a ∈ Rn m × nº A À ÕÙò ½º½º ´ Ö ×µ Ó Ú Ø Úñ Ñ ØÖ Ò Ô Ã ∃y ∈ Rn , y ≥ 0 < a, x > ≥ 0 Ax ≥ 0 x ¸ Ú Ñ Ø Óò ÑóÒ Úñ a = AT y º × Ó Ó Ö × Ö ØÒ ÙÒ Ò º Î Ñ Ø Ò ¸ ÒñÝ Ö Ö÷Ò K = {x ∈ Rn | Ax ≥ 0} Ò÷Ñ øÒ ØÖÓÒ Ò ÒÒ Ò Ò {x ∈ Rn |< a, x > ≥ 0} Úñ Ú Ø Ô ôÔ ØÙÝ Ò × Ù Ô øÒ {x ∈ Rn |< a, x > = 0} Ò÷Ñ ØÖÓÒ Ò Ò × Ò ô ñÒ Ñ ØÖ Ò Aº ½º½º º Ì Ô Ð Ò P ⊆ Rn Ðñ Ó Ñ Ø× Ù õÒ Ò Ò Ò Òº Ì ÔÐ Ò Æ ô ô ¸ Ò Ðñ Ø Ô Ò Ñ ÑØ Ù õÒ ô Ø øÒ Ø ØÙÝ Ò ½¾
ØÒ < ai , x > ≥ bi , i = 1, 2, · · · , m. ´½º½µ Å Ø øÒ Ø ØÖÓÒ Ðñ Ñ Ø º ÊñÒ Ù (1.1) ÖñÒ Ù k ∈ {i = 1, 2, · · · , m} Ðñ Ñ Ø ÖñÒ Ù ÒÙ Ø x |< ai , x > ≥ bi , i = 1, 2, · · · , m = x |< ai , x > ≥ bi, i ∈ {1, 2, · · · , m} \ {k } ai = (a1, a2 , · · · , an ), i = 1, 2, · · · , n¸ Ì Ù A Ðñ Ñ ØÖ Ò Ô m × n Ú b = (b1, b2, · · · , bm)T Úñ x = (x1, x2, · · · , xn)T Ø Ú Ø Ú Ø (1.1) õÒ Ñ ØÖ Ò Ò ×Ù Ax ≥ b Î Ñ ØÔ Ò ØÖ Ò ØÙÝ Ò Ø Ò Ø Ù ÒØ Ò Ò Ø Ô Ò ØÖ Ò ØÙÝ Ò Ø Ò ÒÒØÔÒ Ñ Ô Ò ØÖ Ò Úñ ØÔ Ò ØÖ Ò ØÙÝ Ò Ø Ò   < ai , x > = bi , i = 1, 2, · · · , m1  < ai , x > ≥ b , i = m + 1, · · · , m 1 i Ò Ðñ Ñ Ø Ø Ô Ð Òº Ø Ý Ö÷Ò Ø Ô Ð Ò Ðñ Ñ Ø Ø Ô Ð ¸ Ò ºÅ ØØ ÔÐ Ò Ò Ðñ Ý ØúØ Ðñ º ÒÐ Ò a1 a2 a3 a5 4 a ÀÒ ½º º Ò ÒñÝ Ðñ Ó Ò Ò Ò x0 ∈ D Ø Óò ÑóÒ ÓØÔÐ Ò D Üô Ò (1.1)º Æ Ù Ñ < ai , x0 >= bi¸ Ø x0 Ø Óò ÑóÒ Ø ÖñÒ ØÒ Ñ Ù iº Ì Ô ½¿
I (x0) := i ∈ {1, 2, · · · , m} < ai , x0 >= bi x0 ∈ D º Ðñ Ø Ô Ô ô × ô ÖñÒ Ù Ø Óò ÑóÒ Ø Øõ Å Ñ Ò Ø ÔÐ Ò Ðñ Ñ Ø Dº Ì Ô D Ò ÓÒ Ð Ðñ Ñ Ø DÒ ÙF ÑØ Ñ ØÖÓÒ Ø Ò F =∅ Ò ÑØ ÓõÒ Ø øÒ ÒñÓ ØÙ DØ F Ò ò ÓõÒ Ø øÒ ¸ Ò Ðñ y ∈ D, z ∈ D, x = λy + (1 − λ)z ∈ F Ú 0 < λ < 1 ⇒ y ∈ F, z ∈ F ½º¾ ÀñÑ Ð ½º¾º½º Ò Ò ñÑ Ð Úñ ñÑ Ð Ø D ⊆ Rn ÀñÑ Ðñ ´ ÓÒÚ Ü ÙÒ Ø ÓÒµ Üô Ò ØÖ Ò Ø Ô Ð f ñÑ Ð x1, x2 ∈ D Úñ Ò ÙÚ Ø Ø ×Ø λ ∈ [0, 1] Ø f λx1 + (1 − λ)x2 ≤ λf (x1) + (1 − λ)f (x2)º Ì f Ðñ ´×ØÖ ØÐÝ ÓÒÚ Ü ÙÒ Ø ÓÒµ ØÖ Ò Ø Ô Ð DÒ Ù ñÑ Ð Ø f λx1 + (1 − λ)x2 < λf (x1) + (1 − λ)f (x2)º x1, x2 ∈ D, x1 = x2 Úñ Ú Ø Ø ×Ø λ ∈ (0, 1)º Å Ò Üô Ò Ù Ù ñÑ f Ðñ dom f = {x ∈ D | f (x) < +∞} ´ØÖ Ò Ø µ ñÑ Ð f Ðñ Ø Ô Ô Ô Ö Ô epi(f ) := {(x, α) ∈ D × R | x ∈ D, α ≥ f (x)}º ÀñÑ Ð f : D −→ R ∪ {+∞} Ø Ñ Ö Ò Ø ñÒ ñÑ Ð ØÖ Ò ØÓñÒ Rn ÷Ò ô Ò Ò Ø f (x) = +∞, ∀x ∈ dom f º Î Ú Ý Ò òÒ¸ / Rn º ØØ Ò ÜØ f Ðñ ñÑ Ð ØÖ Ò ÅÒ ½º º D ⊆ Rn f µ ÀñÑ Üô Ò ØÖ ÒØ ÔÐ ô Ö Ò Ðñ ñÑ Ð Úñ epi(f ) Ðñ Ø ÔÐ º D ⊆ Rn g µ ÀñÑ Üô Ò ØÖ ÒØ ÔÐ ô Ö Ò Ðñ ñÑ Ð Ñ Úñ Ø Ô ÝÔÓ Ö Ô ´ Ø µ Ò Ðñ Ø ÔÐ ¸ ØÖÓÒ ½
hypo(g ) := {(x, α) ∈ D × R | x ∈ D, α ≤ g (x)}º ´µ ´µ ´ µ ¹ ÀÝÔÓ ÖÔ ÑØ ñÑ Ð Ñ ÀÒ ½º º ´ µ ¹ Ô ÖÔ ÑØ ñÑ Ð ½º¾º¾º ô Ô Ô ØÓôÒ Ú ñÑ Ð D1 ⊆ Rn ¸ ñÑ Ð Ó ñÑ Ð f1 Üô Ò ØÖ Ò Ø Ô Ð f2 Üô Ò ØÖ Ò Ø Ô D2 ⊆ Rn Úñ × Ø Ð λ > 0º ô Ô Ô ØÓôÒ λf1¸ f1 + f2¸ max{f1 , f2} ÒÒ Ò ×Ù (λf1)(x) := λf1 (x), ∀x ∈ D1 (f1 + f2)(x) := f1 (x) + f2 (x), ∀x ∈ D1 ∩ D2 max{f1, f2}(x) := max{f1(x), f2(x)}, ∀x ∈ D1 ∩ D2 º f1 D1 ¸ f2 D2 ÅÒ ½º º Ó ñÑ Ðñ Ð ØÖ Ò Ð ØÖ Ò Úñ × Ø max{f1, f2} Ðñ Ð D1 ∩ D2 º α > 0, β > 0º Ã αf1 + βf2 ¸ ô ñÑ Úñ ØÖ Ò ½º¾º¿º Ì Ò Ð Ò Ø Úñ õÓ ñÑ Ø Ó Ò ñÑ Ð D ⊆ Rn º Ì Ó ñÑ Ð f Üô Ò ØÖ Ò Ø Ô Ð Ñ D ⊆ Rn f f Ò Ð ½º º Æ Ù Ðñ ñÑ Ð Üô Ò ØÖ ÒØ ÔÐ Ñ Ø Ð Ò Ø Dº ØÖ Ò D ⊆ Rn f : D −→ R Ò Ð ½º º Æ Ù Ðñ Ñ Ø ñÑ Ð Üô Ò ØÖ ÒØ ÔÐ x0 ∈ dom f d ∈ R \ {0} Øõ Ø Ò õÓ ñÑ Ø ÓÑ Ò Ñ Ñ Úñ f ′ ( x 0 , d) ≤ f ( x 0 + d) − f ( x 0 ) f D f À ÕÙò ½º¾º Æ Ù Ðñ ñÑ Ð òÚ Üô Ò ØÖ ÒØ ÔÐ Ñ Ø õÓ x0 ∈ dom f d ∈ R \ {0} Øõ ñÑ Ø ÓÑ Ò Ñ Ñ Úñ < ▽f (x0), d >= f ′ (x0, d) ≤ f (x0 + d) − f (x0) ½
½º¾º º Ì Ù Ù ÒÒ Ò Ø ñÑ Ð òÚ D ⊆ Rn º f f Ò Ð ½º º Ó Ðñ ñÑ òÚ ØÖ ÒØ ÔÐ Ñ Ã ñÑ Ðñ D ñÑ Ð ØÖ Ò Úñ f (y ) − f (x) ≥ < ▽f (x), y − x >, ∀x, y ∈ D Ì ó ØÚ ñÑ Ñ Ø Ò f Üô Ò ØÖ Ò ÓòÒ Ñ D = (a, b) ⊆ R Ø f ′′ (x) ≥ 0, ∀x ∈ D f Ðñ ñÑ Ð ØÖ Ò Úñ D D ⊆ Rn º f f Ò Ð ½º º Ó Ðñ ñÑ òÚ Ð Ò ØÖ ÒØ ÔÐ Ñ Ã ▽2 f (x) Ðñ Ò D Ðñ ñÑ Ð ØÖ Ò Úñ Ñ ØÖ ÒÀ ×× Üô Ò Ò ∀x ∈ D D¸ Ø ØÖ Ò Ú Ø y T ▽2 f (x)y ≥ 0, ∀y ∈ Rn ▽2 f (x) Üô f D D¸ Ø ÀñÑ Ðñ ñÑ Ð Ø ØÖ Ò Ò Ù Ò Ò ØÖ Ò Ú x ∈ D¸ Ø Ñ y T ▽2 f (x)y > 0, ∀y ∈ Rn \ {0}. À ÕÙò ½º¿º Ó ñÑ ØÓñÒ Ô Ò 1 f (x) = < x, Qx > + < c, x > + α¸ 2 n¸ c ∈ Rn α ∈ Rº Q f ØÖÓÒ Ðñ Ñ ØÖ Ò ÚÙ Ò Ü Ò Ô Úñ Ã ¸ Ðñ Rn Q Ðñ Ñ f ñÑ Ð ØÖ Ò Ò Ù ØÖ ÒÒ Üô Ò Ò ´ Ðñ ñÑ Ð Ø ØÖ Ò Rn Q Ðñ Ñ Ò Ù ØÖ Ò Üô Ò Ò µº f ( x 1 , x 2 ) = 2x 2 + 3x 1 x 2 + 4x 2 º Ì Ó Î ½º º 1 2   4x1 3x2 ▽f (x) =   3x1 8x2   43 ▽2 f (x) =   38 ▽2 f (x) Üô Î Ñ ØÖ Ò À ×× × Ò Ò ÒÒ ñÑ f ó Ó Ðñ ñÑ Ð R2 º Ø ØÖ Ò ½
¸ Ò ÒñÝ ó Ò ú Ðõ ô ô Ò ÑÚ Ø ÔÐ ´Ø Ô Ò Úñ Ó Ì Ñ Ðõ Ò¸ØÔÐ Úñ ÓÐ ¸Ò ÒÐ Úñ Ø Ô Ð Ò¸ Ò Ú ô ôÒÑ Ò ¸ õÒ ¸ Ò Ø ÔÐ Òµ Úñ ô ô Ò ÑÚ ñÑ Ð ¸ ñÑ Ð Ø Ò Ñ Ø× ØÒ Ø òÒ Ò ºÆ ÙÒ ØÖ Ò ñÝ ØÖÓÒ Ò× Ò Ò ô Ò × Ù¸ Ò Ò Ù ô ñ ØÓôÒ Ô ØÙÝ Ò Ò ÙÒ Úñ ñ ØÓôÒ Ø ÙÚ ñÑ Ø Ù Ò Ò Ø ÒÒ Ö Òº ½
Ò¾ ô ñ ØÓôÒ Ø Ù Ò ÒñÝ ÔØ ô ñ ØÓôÒ Ø ÙÔ ØÙÝ Ò¸ Ó ÑØ Ù Ô Ò Úñ Ø Ù ØÓñÒ ¸ Ø Ù Ò ÖñÒ Ù Úñ Ø Ù ÖñÒ Ù º Î Ñ ÐÓõ ñ ØÓôÒ ÜØ Ò ô Ù Ò Ò Úñ Ø Ùº Æ ÙÒ Ò ÝÙ ØÖ Ò ô Øñ Ð Ù ½℄¸ ¾℄ Úñ ¿℄º ¾º½ ô ô Ò Ñ òÒ Å Ø ñ ØÓôÒ Ø Ù Ø Ò ÕÙôØ Ô ôØ ÙÒ ×Ù min f (x) Ú x∈D (P1 ) Ó max f (x) Ú x∈D (P2) D ⊆ Rn ØÖÓÒ Ðñ ÝØ Úñ Ø ÔÒ Ñ ÔÒ Ò Ô ÖñÒ Ù f : D −→ R Ðñ ºÅ Ñ Ðñ Ñ Ø x∈D ñÑ Ñ Ø Ù Ò Ñ Ô ÝÑ Ø ´ Ø ØúØ Ðñ Ñ Ø Ò Ò Ô Ò ôÒ ÔÒ Ò Ô Ò µº ôÒ x∗ ∈ D Ññ Ñ −∞ < f (x∗) ≤ f (x), ∀x ∈ D Ðñ ´Ò Ñ Ø Ùµ Ó Ò Ñ Ø Ù Ò Ñ Ø Ù ØÓñÒ ´Ò Ñ Ø Ù ØÓñÒ ¹ ÐÓ Ð Ñ Ò Ñ Þ Öµ¸ Ó Ò òÒ Ðñ Ò Ñ ½