Quy hoạch tuyến tính - Nguyễn Cảnh Hoàng

Nguyễn Cảnh Hoàng Tpying by Đặng Minh Dũng – K56CA, UET Tài liệu tham khảo:  Nguyễn Đức Nghĩa: Tối ưu hóa (Quy hoạch tuyến tính và rời rạc), NXB Giáo dục 1998.  Bùi Minh Trí & Bùi Thế Tâm: Giáo trình tối ưu hóa, NXB Giao thông Vận tải 1996.  Bùi Thế Tâm & Trần Vũ Thiệu: Các phương pháp tối ưu hoá, NXB Giao thông Vận tải 1998 Lời nói đầu: Tối ưu hóa là một bộ phận kiến thức cần thiết của nhà tổ chức, thiết kế kỹ thuật, điều hành công việc,… và ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của cuộc sống. Nó còn được gọi là vận trù học hay quy hoạch, được phát triển mạnh mẽ từ những năm 30-40 nhờ công lao của Kantorovic (Nga 1939) cũng như các nhà toán học Mỹ, những người tìm ra phương pháp đơn hình (Simplex method 1942) Giáo trình này nhằm mục đích nêu các khai niệm cơ sở và một số kết quả cơ bản của tối ưu hóa, nhằm trang bị những hành trang cần thiết cho các sinh viên của các trường kỹ thuật để tiếp xúc, ứng dụng và giải quyết các vấn đề liên quan trong tương lai. Chương I. Mở đầu BÀI 1. ĐỐI TƯỢNG NGHIÊN CỨU Khi tiến hành thiết kế, tổ chức, điều hành một (hoặc một dãy) quá trình nào đó, người ta thường phải tự đặt câu hỏi: làm thế nào để có thể đạt được kết quả nhanh nhất, tiết kiệm thời gian, tiền của nhất, đạt chất lượng cao nhất…! Nói một cách khác, ta muốn đạt được cực trị của một mục tiêu nào đó được đề ra từ trước. Cơ sở lý thuyết và các phương pháp thực hành để giải quyết vấn đề đó được gọi là Tối ưu hóa hay Quy hoạch toán học. 1.1 Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát được phát biểu như sau: Hãy cực tiểu hóa (cực đại hóa) hàm số: 𝑓(𝑥) → 𝑀𝑖𝑛(𝑀𝑎𝑥) (1.1) Với các điều kiện: 𝑔𝑖(𝑥)(≤, =,≥)𝑏𝑖 𝑖 = 1,2, … ,𝑚 (1.2) 𝑥 ∈ 𝑋 ⊂ 𝑅𝑛 (1.3) Trong đó:  𝑓(𝑥) được gọi là hàm mục tiêu, cực tiểu hóa (cực đại hóa) là chọn giá trị của đối số x sao cho 𝑓(𝑥) đạt giá trị bé nhất (lớn nhất) có thể.  𝑔𝑖(𝑥) được gọi là các hàm rằng buộc, mỗi bất đẳng thức trong (1.2)được gọi là một rằng buộc, thể hiện điều kiện đòi hỏi của bài toán đối với biến x.  Tập hợp 𝐷 = {𝑥 ∈ 𝑋: 𝑔𝑖(𝑥)(≤, =,≥)𝑏𝑖 𝑖 = 1,2, … ,𝑚} được gọi là miền rằng buộc (hay miền chấp nhận được, tập các phương án chấp nhận). Mỗi một điểm 𝑥 = (𝑥1, 𝑥2, … , 𝑥𝑛) ∈ 𝐷 được gọi là một phương án chấp nhận được (hay gọi tắt là phương án, lời giải) của bài toán đã cho.  Phương án 𝑥∗ ∈ 𝐷 sao cho hàm mục tiêu đạt được giá trị cực tiểu (cực đại), tức là: 𝑓(𝑥∗) ≤ 𝑓(𝑥) ∀𝑥 ∈ 𝐷 cho bài toán Min 𝑓(𝑥∗) ≥ 𝑓(𝑥) ∀𝑥 ∈ 𝐷 cho bài toán Max Được gọi là phương án tối ưu (lời giải tối ưu) và 𝑓(𝑥∗) được gọi là giá trị tối ưu của bài toán. Ví dụ : Một người muốn xây một ngôi nhà với mức giá thấp nhất có thể. Tuy nhiên ông ta có một số điều kiện của ngôi nhà đó :  Diện tích mặt bằng, diện tích xây dựng  Số phòng, số tầng, số phòng vệ sinh  Tiêu chuẩn kỹ thuật : Chất lượng kỹ thuật, tiêu chuẩn nguyên vật liệu, cửa sổ, nội thất, phòng vệ sinh,… Dễ thấy ông ta có một bài toán tối ưu hóa giá thành xây dựng ngôi nhà đó (mà nó là một hàm số phụ thuộc vào giá cả nguyên vật liệu, công thợ, diện tích xây dượng,…) thỏa mãn các đòi hỏi (rằng buộc) của ông ta. 1.2 Phân loại các bài toán Rõ ràng ý tưởng đơn giản nhất để tìm các phương án tối ưu là duyệt toàn bộ các phương án đó : Tính tất cả mọi giá trị 𝑓(𝑥) của mọi 𝑥 ∈ 𝐷 và so sánh để lấy 𝑥∗có 𝑓(𝑥∗)có giá trị bé nhất (lớn nhất). Chẳng hạn để tìm sinh viên có điểm trung bình cao nhất trong Đại học Công nghệ, ta tính điểm trung bình của mọi sinh viên trong trường và sau đó so sánh lần lượt tất cả để chọn ra sinh viên có điểm trung bình cao nhất. Tuy nhiên cách làm này nhiều khi không thực hiện được, khi D quá lớn hoặc vô hạn, hoặc không xác định được một cách trực quan, chưa kể nhiều khi việc tính 𝑓(𝑥) là một vấn đề kỹ thuật phức tạp (chẳng hạn đo sức nổ của 1 quả bong nguyên tử, chẳng lẽ ta lại… thử nổ ak ?!). Do vậy thường ta chia bài toán tối ưu thành các lớp bài toán riêng biệt và nghiên cứu, tìm kiếm lời giải cho từng bài toán đó. Thông thường việc phân loại đó dựa vào hàm mục tiêu, rằng buộc, điều kiện cần và đủ của cực trị, tính chất của các đối tượng nghiên cứu… Ta thường có các phân loại bài toán tối ưu như sau :  Quy hoạch tuyến tính (QHTT) : là các bài toán tối ưu mà trong đó hàm mục tiêu 𝑓(𝑥) và các hàm rằng buộc 𝑔𝑖(𝑥) là các hàm tuyến tính, còn tập X là một đa diện lồi.  Quy hoạch phi tuyến : là bài toán quy hoạch mà 𝑓(𝑥) hoặc 1 trong các hàm 𝑔𝑖(𝑥) là hàm phi tuyến.  Quy hoạch động : Đối tượng xét đến có nhiều giai đoạn mà hàm mục tiêu cũng như rằng buộc có thay đổi trong các giai đoạn đó (ví dụ xây nhà, giá cả nguyên vật liệu, tiền công thay đổi theo thời gian).  Quy hoạch rời rạc : Nếu D là một miền rời rạc.  Quy hoạch nguyên : Nếu D chỉ nhận các giá trị nguyên.  Quy hoạch Boole : Nếu D chỉ nhận các giá trị True/False.  Quy hoạch đa mục tiêu : Có nhiều hàm mục tiêu. BÀI 2. MÔ HÌNH HÓA TOÁN HỌC Với một bài toán thực tế nào đó, việc tìm cách phát biểu nó theo ngôn ngữ toán học, đưa nó vào một lớp bài toán quyen thuộc được gọi là mô hình hóa bài toán đó. Nói một cách khác là xếp nó vào một mô hình tổng quát nào đó, và việc giải nó chẳng qua là giải một bài toán cụ thể của một lớp bài toán tổng quát mà thôi. Việc giải bài toán thường được tiến hành theo các bước sau: Bước 1: Xây dựng mô hình định tính, xác địn bằng lời một cách rõ ràng bài toán và các biểu đồ, đồ thị của bài toán thực tế. Bước 2: Xây dựng mô hình toán học: Phát biểu lại bài toán dưới dạng ngôn ngữ toán học, nói một cách khác là biểu diễn các mô hình định tính bằng các công thức toán học: 𝑓(𝑥); 𝑔𝑖(𝑥);≤ ≥;… Bước 3: Áp dụng các công cụ toán học để khảo sát và giải bài toán đã được phát biểu ở bước 2 để tìm lời giải phù hợp. Bước 4: Phân tích và kiểm định kết quả thu được ở bước 3. Đây là bước kiểm tra và đánh giá kết quả có phù hợp với bài toán đặt ra hay không, hiệu chỉnh, sửa đổi, thêm bớt các rằng buộc cho phù hợp với thực tế… Ta xét một số mô hình cụ thể sau đây: 2.1 Bài toán lập kế hoạch Một nhà máy có khả năng sản xuất n loại sản phẩm từ m nguyên liệu khác nhau, với các định mức nguyên vật liệu cho từng loại sản phẩm. Hãy xây dựng phương án sản xuất để từ số nguyên liệu có trong kho, nhà máy thu được lợi nhuận cao nhất. Ta có sơ đồ sử dụng nguyên vật liệu như sau: 𝑎𝑖𝑗 – lượng nguyên liệu thứ i cần thiết để sản xuất một đơn vị sản phẩm thứ j. 𝑏𝑖 – số lượng nguyên liệu thứ i có trong kho. 𝑐𝑗 – lợi nhuận của một sản phẩm thứ j. 𝑥𝑗 – số sản phẩm thứ j mà nhà máy sẽ sản xuất. Khi đó việc xây dựng kế hoạch là bài toán tối ưu, phát biểu dưới dạng ngôn ngữ toán học như sau: bi P1 P2 Pm { ∑𝑐𝑗𝑥𝑗 𝑛 𝑗=1 → 𝑀𝑎𝑥 ∑𝑎𝑖𝑗𝑥𝑗 𝑛 𝑗=1 ≤ 𝑏𝑖 (𝑖 = 1,𝑚) 𝑗 ≥ 0 (𝑗 = 1, 𝑛) 2.2 Bài toán vận tải Có n kho hàng cùng chứ một loại hàng hóa cần được chuyển tới m cửa hàng tiêu thụ với các yêu cầu về số lượng và cước phí khác nhau. Hãy lập kế hoạch vận chuyển sao cho cước phí là bé nhất. Ta gọi: 𝑎𝑖 – số lượng hàng hóa có ở kho thứ i, 𝑖 = 1, 𝑛 𝑏𝑗 – lượng hàng hóa cấn chuyển tới cửa hàng thứ j, 𝑗 = 1,𝑚 𝑥𝑖𝑗 – lương hàng hóa sẽ chuyển thừ kho Ai tới kho Bj, 𝑖 = 1, 𝑛; 𝑗 = 1,𝑚 𝑐𝑖𝑗 – cước phí chuyên chở một đơn vị hàng từ kho Ai tới cửa àng tiêu thụ Bj, 𝑖 = 1, 𝑛; 𝑗 = 1, 𝑚 Mô hình toán học của bài toán vận tải sẽ là: Và ta có bài toán tối ưu: X11 X12 Bm a2 a1 an b1 b2 bm A1 A2 An B1 B2 X1m { ∑∑𝑐𝑖𝑗𝑥𝑖𝑗 → 𝑀𝑖𝑛 𝑚 𝑗=1 𝑛 𝑖=1 ∑𝑥𝑖𝑗 𝑚 𝑗=1 = 𝑎𝑖 (𝑖 = 1, 𝑛) ∑𝑥𝑖𝑗 𝑛 𝑖=1 = 𝑏𝑗 (𝑗 = 1,𝑚) 𝑥𝑖𝑗 ≥ 0 (𝑖 = 1, 𝑛; 𝑗 = 1,𝑚) ∑𝑎𝑖 𝑚 𝑖=1 =∑𝑏𝑗 𝑛 𝑗=1 Tổng quát, 𝑥𝑖𝑗 là các số thực không âm, chẳng hạn khi hàng hóa đó là xăng dầu, gạo, đường,… Tuy nhiên ta thường hay “Nguyên hóa” chúng đi để trở thành các số nguyên, ví dụ ta dùng đơn vị đo là “thùng”, “tấn”, hoặc “bao”, “bình”,… để các 𝑥𝑖𝑗 đó trở thành các số nguyên (không lẽ ta lại nói là chuyên chở 3.45 bao xi măng hay 3.2 bình ga à?). Do vậy mà bài toán quy hoạch của ta sẽ trở thành một bài toán quy hoạch nguyên, đơn giản hơn trong tính toán mặc dù lời giải lý thuyết không đổi ! 2.3 Bài toán cái túi Một kẻ trộm lẻn vào kho, mang theo 1 cái túi để đựng hàng. Trong kho có n loại đồ vật với khối lượng và giá trị khác nhau. Biết rằng túi chỉ có thể chứa được 1 khối lượng hàng hóa nhất định. Hãy chỉ cho tên trộm nên lấy những gì để có lợi nhất. Gọi : 𝑏 – khối lượng tối đa của túi. 𝑎𝑗 – khối lượng của 1 đồ vật loại j. 𝑐𝑗 – giá trị của 1 đồ vật loại j. 𝑥𝑗 – số đồ vật loại j sẽ được bỏ vào túi. Khi đó ta có bài toán quy hoạch nguyên như sau : { ∑𝑐𝑗𝑥𝑗 𝑛 𝑗=1 → 𝑀𝑎𝑥 ∑𝑎𝑗𝑥𝑗 𝑛 𝑗=1 ≤ 𝑏 𝑥𝑗 ≥ 0, 𝑥𝑗 ∈ 𝑁 (𝑗 = 1, 𝑛) (Giả thiết là trong kho có vô số hàng hóa các loại) Trên đây là một số mô hình cơ bản của quy hoạch với các cách diễn giải nội dung thực tế của chúng. Các bài toán khác có thể được diễn giải, phải biểu dưới dạng tương tự các mô hình trên. BAI 3. MỘT SỐ KHAI NIỆM GIẢI TICH LỒI 3.1 Không gian Euclide Rn Một vector n chiều được xác định bởi bộ số : 𝑥 = (𝑥1, 𝑥2, … , 𝑥𝑛) ∈ ℝ 𝑛 Trong đó 𝑥1, 𝑥2, … 𝑥𝑛 ∈ ℝ được gọi là các thành phần của vector x. Vector x đó cũng đồng nhất với điểm A có tọa độ (𝑥1, 𝑥2, … , 𝑥𝑛) ∈ ℝ 𝑛 Khi đó :  Hai vector x, y bằng nhau khi các thành phần của chúng bằng nhau đôi một : 𝑥 = 𝑦 ⟺ 𝑥1 = 𝑦1, 𝑥2 = 𝑦2, … , 𝑥𝑛 = 𝑦𝑛  Tổng vetor : 𝑥 + 𝑦 = (𝑥1 + 𝑦1, 𝑥2 + 𝑦2, … , 𝑥𝑛 + 𝑦𝑛)  Tích của 1 số thực với 1 vector : 𝜆𝑥 = (𝜆𝑥1, 𝜆𝑥2, … , 𝜆𝑥𝑛) Tập các vector n chiều với 2 phép toán trên được gọi là không gian tuyến tính n chiều trên tập ℝ, kí hiệu là ℝ𝑛 Khi đó ta có một số khái niệm và tính chất sau :  Các vector 𝑥𝑖 ∈ ℝ 𝑛 , 𝑖 = 1,𝑚 được gọi là độc lập tuyến tính nếu : ∑𝑎𝑖𝑥𝑖 𝑚 𝑖=1 = 0 ⟺ 𝑎𝑖 = 0 ∀𝑖 = 1,𝑚 (ngược lại, các vector đó được gọi là phụ thuộc tuyến tính)  Nếu 𝑥 = ∑ 𝑎𝑖𝑥𝑖 𝑚 𝑖=1 với ít nhất một 𝑎𝑖 ≠ 0 thì x được gọi là tổ hợp tuyến tính của các vector 𝑥𝑖. Nếu ∑ 𝑎𝑖 𝑚 𝑖=1 = 1 và 𝑎𝑖 ≥ 0 ∀𝑖 = 1, 𝑛 thì ta gọi đó là 1 tổ hợp lồi của các vector 𝑥𝑖  Trong ℝ𝑛, mỗi bộ n vector độc lập tuyến tính được gọi là cơ sở của ℝ𝑛, (mọi cơ sở đều đúng n vector, n được gọi là số chiều của không gian ℝ𝑛, trong ℝ𝑛 có vô số sơ sở khác nhau). Khi đó, mọi vector thuộc ℝ𝑛 đều có thể biểu diễn dưới dạng tổi hợp tuyến tính của các vector trong cơ sở đó.  Bao đóng tuyến tính Span(𝑀) = {∑𝑎𝑖𝑥𝑖 ∶ 𝑎𝑖 ∈ ℝ, 𝑥𝑖 ∈ 𝑀}  Tích vô hướng của 2 vector x và y, ký hiệu 〈𝑥, 𝑦〉 được định nghĩa như sau : 〈𝑥, 𝑦〉 ≔∑𝑥𝑖𝑦𝑖 𝑛 𝑖=1 và có các tính chất sau : o 〈𝑥, 𝑦〉 = 〈𝑦, 𝑥〉 o 〈𝑥1 + 𝑥2, 𝑦〉 = 〈𝑥1, 𝑦〉 + 〈𝑥2, 𝑦〉 o 〈𝜆𝑥, 𝑦〉 = 𝜆〈𝑥, 𝑦〉 o 〈𝑥, 𝑥〉 ≥ 0, 𝑑ấ𝑢 = 𝑥ả𝑦 𝑟𝑎 𝑘ℎ𝑖 𝑣à 𝑐ℎỉ 𝑘ℎ𝑖 𝑥 = (0,0, … ,0)  Độ dài của vector, ký hiệu |𝑥|được xác định bởi : |𝑥| ≔ √∑𝑥𝑖 2 𝑛 𝑖=1 = √〈𝑥, 𝑥〉  Khoảng cách giữa 2 vector, ký hiệu 𝑑(𝑥, 𝑦) : 𝑑(𝑥, 𝑦) ≔ |𝑥 − 𝑦| = √∑(𝑥𝑖 − 𝑦𝑖) 2 𝑛 𝑖=1 Không gian tuyến tính ℝ𝑛 với tích vô hướng và khoảng cách d được gọi là không gian Euclide. 3.2 Tập Compact  Dãy {𝑥𝑖} được gọi là có giới hạn x* khi 𝑖 → ∞ nếu lim 𝑖→∞ 𝑑(𝑥𝑖 , 𝑥 ∗) = 0 và ta ký hiệu lim 𝑖→∞ 𝑥𝑖 = 𝑥 ∗  Hình cầu mở : 𝑆(𝑥0, 𝑟) = {𝑥 ∈ 𝑋 ∶ 𝑑(𝑥0, 𝑥) < 𝑟} Hình cầu đóng : 𝑆(𝑥0, 𝑟) = {𝑥 ∈ 𝑋 ∶ 𝑑(𝑥0, 𝑥) ≤ 𝑟}  Mặt cầu : 𝑆0(𝑥0, 𝑟) = {𝑥 ∈ 𝑋 ∶ 𝑑(𝑥0, 𝑥) = 𝑟  //Some text are missing  Mặt biên, cạnh biên, đỉnh : Mặt của một tập mà mọi điểm của nó là các điểm biên gọi là mặt biên. Giao của các mặt biên gọi là cạnh biên. Giao của nhiều cạnh biên gọi là đỉnh hoặc điểm cực biên.  //Some text are missing Ta có thể dễ dàng giải thích và lấy ví dụ trực quan về các khái niệm trên trong không gian Euclide. 3.3 Tập lồi – Hàm lồi Định nghĩa 3.1: Nếu ∀𝑥, 𝑦 ∈ 𝑀 ta có [𝑥, 𝑦] ⊂ 𝑀 trong đó [𝑥, 𝑦] ≔ {𝛼 = 𝜆𝑥 + (1 − 𝜆)𝑦 ∶ 𝜆 ∈ [0,1]} Thì M được gọi là tập lồi. ([𝑥, 𝑦] là đoạn thẳng nối x và y) Ý nghĩa : Với ∀𝑥, 𝑦 ∈ 𝑀 đoạn thằng [𝑥, 𝑦] nối 2 điểm x, y luôn nằm trọn trong tập lồi M. Định lý 3.1 : Giao của 2 tập lồi là một tập lồi. Chứng minh : ∀𝑥, 𝑦 ∈ 𝐴 ∩ 𝐵 ta có 𝑥, 𝑦 ∈ 𝐴 ⟹ [𝑥, 𝑦] ⊂ 𝐴. Tương tự [𝑥, 𝑦] ⊂ 𝐵 Suy ra [𝑥, 𝑦] ⊂ 𝐴 ∩ 𝐵. Tức là 𝐴 ∩ 𝐵 là một tập lồi. Hệ quả 1 : Giao của n tập lồi là một tập lồi. Hệ quả 2 : Miền chứa nghiệm của hệ : { 𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 … 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 Là một tập lồi Chứng minh : Dễ thấy mỗi bất phương trình trong hệ trên là một nửa mặt phẳng trong không gian và đó là một tập lồi. Từ hệ quả 1 ta suy ra điều cần chứng mình. Định lý 3.2 : Cho tập lồi đa diện đóng X với ít nhất 1 đỉnh. Khi đó mỗi 𝑥 ∈ 𝑋 đều có thể biểu diễn dưới dạng : 𝑥 =∑𝜆𝑖𝑑𝑖 𝑖 +∑𝜇𝑗𝑔𝑗 𝑗 Trong đó :  𝜆𝑖 ≥ 0, ∑ 𝜆𝑖𝑖 = 1  𝑑𝑖 là các đỉnh của đa diện lồi X, 𝑖 ∈ 𝐼  𝑔𝑗 (𝑗 ∈ 𝐽) là các phương vô hạn của đa diện lồi (Khi X giới nội không còn các cạnh vô hạn thì chỉ còn 𝑥 = ∑ 𝜆𝑖𝑑𝑖𝑖 , 𝜆𝑖 ≥ 0,∑ 𝜆𝑖𝑖 = 1 và khi đó ta gọi 𝑥 = ∑ 𝜆𝑖𝑑𝑖𝑖 là một tổ hợp lồi của các đỉnh – tức là khi đó mọi điểm x đề là tổ hợp lồi y x M của các đỉnh, còn khi X có các cạnh vô hạn thì x sẽ là tổng của 1 tổ hợp lồi các đỉnh ∑ 𝛼𝑖𝑑𝑖𝑖 cộng với tổ hợp các phương vô hạn) Chứng minh : Ta chứng minh cho các trường hợp sau : a. X là đa giác phẳng hữu hạn : Giả sử X có một đỉnh là 𝑑𝑖 nào đó. Nối 𝑑0 với x kéo dài cắt một cạnh của đa giác X tại y. Chắc chắn y nằm trên một cạnh của 2 đỉnh nào đó, ta ký hiệu là 𝑑1 & 𝑑2. Dễ thấy rằng :  𝑥 ∈ [𝑑0, 𝑦] ⟹ ∃𝜆 ∈ [0,1]: 𝑥 = 𝜆𝑑0 + (1 − 𝜆)𝑦 (1)  𝑦 ∈ [𝑑1, 𝑑2] ⟹ ∃𝜆 ∈ [0,1]: 𝑦 = 𝜆 ′𝑑1 + (1 − 𝜆 ′)𝑑2 (2) Thay (2) vào (1) ta được : 𝑥 = 𝜆𝑑0 + (1 − 𝜆)𝑦 = 𝜆𝑑0 + (1 − 𝜆)[𝜆 ′𝑑1 + (1 − 𝜆 ′)𝑑2] = 𝜆𝑑0 + (1 − 𝜆)𝜆 ′𝑑1 + (1 − 𝜆)(1 − 𝜆 ′)𝑑2 Dễ kiểm tra được là 𝜆 + (1 − 𝜆)𝜆′ + (1 − 𝜆)(1 − 𝜆′) = 1 và các hệ số trên đều thuộc [0,1] nên x là tổ hợp lồi của 3 đỉnh 𝑑0, 𝑑1, 𝑑2. b. X là một đa diện hữu hạn trong không gian : d0 d 1 d 2 d 3 x y d0 x * d1 d2 y Hoàn toàn tương tự nối đỉnh 𝑑0 với x kéo dài cắt một mặt của đa diện X tại y. Giả sử mặt đó có các đỉnh 𝑑1, 𝑑2, … , 𝑑𝑘 nào đó. Ta cũng sẽ có :  𝑥 ∈ [𝑑0, 𝑦] ⟹ ∃𝜆 ∈ [0,1]: 𝑥 = 𝜆𝑑0 + (1 − 𝜆)𝑦 (1’)  Do y nằm trong đa giác có các đỉnh là 𝑑1, 𝑑2, … , 𝑑𝑘 nên theo trường hợp (a), y là tổ hợp lồi của các đỉnh đó. Tức là : ∃𝛼𝑖 ∈ [0,1],∑𝛼𝑖 𝑘 𝑖=1 = 1 𝑠𝑎𝑜 𝑐ℎ𝑜 𝑦 = ∑𝛼𝑖𝑑𝑖 𝑘 𝑖=1 (2′) Thay (2’) vào (1’) ta được : 𝑥 = 𝜆𝑑0 + (1 − 𝜆)𝑦 = 𝜆𝑑0 + (1 − 𝜆)∑𝛼𝑖𝑑𝑖 𝑘 𝑖=1 = 𝜆𝑑0 +∑(1 − 𝜆)𝛼𝑖𝑑𝑖 𝑘 𝑖=1 Dễ kiểm tra được là 𝜆 +∑(1 − 𝜆)𝛼𝑖 𝑘 𝑖=1 = 𝜆 + (1 − 𝜆)∑𝛼𝑖 𝑘 𝑖=1 = 𝜆 + (1 − 𝜆) = 1 Và hệ số đều thuộc [0,1] nên x là tổ hợp lồi của 𝑑0, 𝑑1, 𝑑2, … , 𝑑𝑘 c. X là một đa giác phẳng vô hạn : Nếu X là đa diện lồi có các cạnh vô hạn, ta có thể chứng minh như sau : Chọn điểm A trên 1 cạnh vô hạn có đỉnh d1, sao cho nối với x kéo dài sẽ cắt một cạnh khác của đa diện X tại B. Ta có 2 khả năng :  Cạnh thứ 2 đó cũng là cạnh vô hạn, giả sử cạnh vô hạn đó có đỉnh d2 (trường hợp đa diện đó chỉ có mỗi 1 đỉnh d0 thì cả 2 đỉnh d1 và d2 phải trùng với d0). A X B O d1 d 2 * x Để đơn giản ta cũng xem như mọi chuyện xảy ra trong mặt phẳng và ta đồng nhất điểm A với vector a, điểm B với vector b, điểm x với vector x, đỉnh d1 với vector d1, đỉnh d2 với vector d2, gốc tọa độ là O. (𝑂𝑑1⃗⃗ ⃗⃗ ⃗⃗ ⃗ = 𝑑1; 𝑂𝑑2⃗⃗ ⃗⃗ ⃗⃗ ⃗ = 𝑑2; 𝑂𝐴⃗⃗ ⃗⃗ ⃗ = 𝑎; 𝑂𝐵⃗⃗ ⃗⃗ ⃗ = 𝑏; O là gốc trục tọa độ trong không gian vector ℝ𝑛) Khi đó, do 𝑥 ∈ [𝑎, 𝑏] ⟹ ∃𝜆 ∈ [0,1] sao cho 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑏 (1’’) Mặt khác 𝑎 = 𝑂𝐴⃗⃗⃗⃗ ⃗ = 𝑂𝑑1⃗⃗ ⃗⃗ ⃗⃗ ⃗ + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ = 𝑑1 + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ 𝑏 = 𝑂𝐵⃗⃗ ⃗⃗ ⃗ = 𝑂𝑑2⃗⃗ ⃗⃗ ⃗⃗ ⃗ + 𝑑2𝐵⃗⃗⃗⃗ ⃗⃗ ⃗ = 𝑑2 + 𝑑2𝐵⃗⃗⃗⃗ ⃗⃗ ⃗ Thay vào (1’’) ta được: 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑏 = 𝜆(𝑑1 + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗) + (1 − 𝜆)(𝑑2 + 𝑑2𝐵⃗⃗⃗⃗ ⃗⃗ ⃗) = [𝜆𝑑1 + (1 − 𝜆)𝑑2] + [𝜆𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ + (1 − 𝜆)𝑑2𝐵⃗⃗⃗⃗ ⃗⃗ ⃗ Nghĩa là ta có x là tổng của 1 tổ hợp lồi 2 đỉnh d1 và d2 với 1 tổ hợp lồi của các phương vô hạn 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ 𝑣à 𝑑2𝐵⃗⃗⃗⃗ ⃗⃗ ⃗.  Cạnh thứ 2 đó không phải là cạnh vô hạn, có nghĩa là B nằm giữa 2 đỉnh d2 và d3 nào đó. Khi đó, do 𝑥 ∈ [𝑎, 𝑏] ⟹ ∃𝜆 ∈ [0,1] sao cho 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑏 (1’’’) Mặt khác 𝐵 ∈ [𝑑2, 𝑑3] ⟹ ∃𝜆 ′ ∈ [0,1] sao cho 𝑏 = 𝜆′𝑑2 + (2 − 𝜆 ′)𝑑3 Ngoài ra: 𝑎 = 𝑂𝐴⃗⃗⃗⃗ ⃗ = 𝑂𝑑1⃗⃗ ⃗⃗ ⃗⃗ ⃗ + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ = 𝑑1 + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ Thay a, b vào (1’’’) ta được: 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑏 = 𝜆(𝑑1 + 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗) + (1 − 𝜆)[𝜆 ′𝑑2 + (1 − 𝜆 ′)𝑑3] = 𝜆𝑑1 + (1 − 𝜆)𝜆 ′𝑑2 + (1 − 𝜆)(1 − 𝜆 ′)𝑑3 + 𝜆𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ Nghĩa là x là tổ hợp lồi của các đỉnh d1, d2, d3 cộng với phương vô hạn 𝑑1𝐴⃗⃗⃗⃗ ⃗⃗ ⃗ d. X là một đa diện lồi vô hạn : Hoàn toàn tương tự như trường hợp (c). Vì điều kiện thời gian có hạn nên chứng minh trên trình bày chưa thật chi tiết và chặt chẽ, cho dù ý tưởng là hoàn toàn chính xác. Ý nghĩa: Trong không gian vector nhiều chiều, mỗi điểm của một đa diện lồi là tổ hợp cửac ác đỉnh đa diện đó cộng với 1 tổ hợp tuyến tính các phương vô hạn (nếu đa diện là vô hạn). Định nghĩa 3.2: Hàm số f(x) được xác định trên tập lồi 𝑋 ⊂ ℝ𝑛 được gọi là hàm lồi nếu ∀𝑥1, 𝑥2 ∈ 𝑋, ∀𝜆 ∈ [0,1]: 𝑓[𝜆𝑥1 + (1 − 𝜆)𝑥2] ≤ 𝜆𝑓(𝑥1) + (1 − 𝜆)𝑓(𝑥2) Ý nghĩa: Gọi M1M2 là 2 điểm trên đồ thị ứng với x1, x2. Khi đó với 𝑥 = 𝜆𝑥1 + (1 − 𝜆)𝑥2 Ta có: 𝑓(𝑥) = 𝜆𝑓(𝑥1) + (1 − 𝜆)𝑓(𝑥2) Nghĩa là điểm 𝑀 = (𝑥, 𝑓(𝑥)) nằm phía dưới đáy dây cung M1M2, tạo cảm giác đồ thị bị “lồi” tại điểm đó. Do vậy mà với hàm lồi ta hay xét tới khái niệm cực tiểu. Nếu dấu bất đẳng thức là ‘< ‘ trong định nghĩa trên thì ta gọi hàm f(x) là hàm lồi chặt. Ngược lại hàm f(x) được gọi là hàm lõm nếu −𝑓(𝑥) là hàm lồi (hay dấu bất đẳng thức là ≥). Với hàm lõm ta hay xét cực đại. Ta nói f(x) xác định trên X đạt cực tiểu tuyệt đối (Min) tại x* nếu: 𝑓(𝑥∗) ≤ 𝑓(𝑥) ∀𝑥 ∈ 𝑋 Còn f(x) đạt cực tiểu địa phương nếu tồn tại lân cân B của x* sao cho: 𝑓(𝑥∗) ≤ 𝑓(𝑥) ∀𝑥 ∈ 𝐵 Định lý 3.3: Bất kỳ cực tiểu địa phương của hàm lồi xác định trên tập lồi cũng là cực tiểu tuyệt đối. Chứng minh: Giả sử x* là cực tiểu địa phương tại lân cân Bε của x*, ta phải chứng minh nó cũng là cực tiểu tuyệt đối trên tập lồi đã cho. O y x M2 M1 M f(x2) f(x 2 ) f(x) λf(x 1 ) + (1-λ)f(x2) x 1 x x 2 Phản chứng nếu x* không là cực tiểu tuyệt đối, như vậy sẽ tồn tại x1 sao cho f(x*)>f(x1). Ta xét tổ hợp lồi: 𝑥(𝜆) = 𝜆𝑥1 + (1 − 𝜆)𝑥 ∗, 0 ≤ 𝜆 ≤ 1 Nếu λ = 0 thì x = x*, chứng tỏ tồn tại λ0, 0 < λ0 ≤ 1 sao cho 𝑥(𝜆0) ∈ 𝐵𝜀 ∀𝜆 ∈ [0, 𝜆0]. Lấy 0 < 𝜆1 < 𝜆0 ⟹ 𝑥(𝜆1) ∈ 𝐵𝜀 và khi đó: 𝑓[𝑥(𝜆1)] ≤ (1 − 𝜆1)𝑓(𝑥 ∗) + 𝜆1𝑓(𝑥1) < (1 − 𝜆1)𝑓(𝑥 ∗) + 𝜆1𝑓(𝑥 ∗) = 𝑓(𝑥∗) Mâu thuẫn với việc x* là cực tiểu địa phương. Vậy x* phải là cực tiểu tuyệt đối (Min) Hệ quả: Bất kỳ cực đại địa phương của hàm lõm trên tập lồi cũng là cực đại tuyệt đối (Max) Các hàm lồi có một ý nghĩa cực kỳ quan trọng trong việc giải các bài toán tối ưu mà việc đó xuất phát từ một ý tưởng cực kỳ đơn giản sau: Nếu f(x) là hàm lồi xác định trên tập lồi thì ∀𝑎, 𝑏 ∈ 𝑋, 𝜆 ∈ (0,1) thì khi đó 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑎 ∈ [𝑎, 𝑏] và ta luôn có: 𝑓(𝑥) = 𝑓[𝜆𝑎 + (1 − 𝜆)𝑏] ≤ 𝜆𝑓(𝑎) + (1 − 𝜆)𝑓(𝑏) ≤ 𝜆𝑀 + (1 − 𝜆)𝑀 = 𝑀 Trong đó: 𝑀 = max[𝑓(𝑥)] ∀𝑥 ∈ [𝑎, 𝑏] Và dấu bằng xảy ra (nghĩa là 𝑓(𝑥) = max[𝑓(𝑥)] ∀𝑥 ∈ [𝑎, 𝑏]) khi và chỉ khi 𝑓(𝑎) = 𝑓(𝑏) = 𝑀𝑎𝑥[𝑓(𝑥)] ∀𝑥 ∈ [𝑎, 𝑏] Điều trên dễ dàng suy ra từ định nghĩa và nếu để ý rằng, 𝑥 = 𝜆𝑎 + (1 − 𝜆)𝑏 ∈ [𝑎, 𝑏] nghĩa là x nằm trong đoạn thẳng [a,b], nó dẫn đến mệnh đề sau: Với nếu hàm lồi f(x) đạt Max tại 1 điểm x nằm trong đoạn [a,b], nó phải đạt Max tại 2 đầu