Khóa luận tốt nghiệp về tiêu chuẩn tối ưu cho bài toán quy hoạch thỏa điều kiện chính quy

Khóa luận trình bày tiêu chuẩn tối ưu cho bài toán quy hoạch thỏa điều kiện chính quy trong lĩnh vực toán tin, mang lại giải pháp hiệu quả.

• Tác giả: Trần Minh Phương
• Người hướng dẫn: TS. Trịnh Công Diệu
• Trường học: Trường Đại Học Sư Phạm Thành Phố Hồ Chí Minh
• Chuyên ngành: Toán - Tin Học
• Đề tài: Tiêu chuẩn tối ưu cho lớp bài toán quy hoạch thỏa điều kiện chính quy
• Loại tài liệu: luận văn tốt nghiệp
• Năm xuất bản: 2008
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ
• 1.1. Định nghĩa
• 1.2. Tính khả vi của hàm nhiều biến và gradient
• 1.3. Một số kết quả Tôpô trong Rn
• 1.4. Các khái niệm và dạng của bài toán Quy Hoạch
• 2. CHƯƠNG 2: CÁC GIẢ THIỆT VỀ ĐIỀU KIỆN CHÍNH QUY TRONG BÀI TOÁN QUY HOẠCH
• 2.1. Điều kiện chính quy Slater
• 2.2. Điều kiện chính quy Karlin
• 2.3. Điều kiện chính quy ngặt
• 2.4. Điều kiện chính quy Kuhn - Tucker
• 2.5. Điều kiện chính quy Arrow - Hurwicz - Uzawa
• 2.6. Điều kiện chính quy lỗi nghịch đảo
• 2.7. Bổ đề
• 3. CHƯƠNG 3: TIÊU CHUẨN TỐI ƯU CHO BÀI TOÁN QUY HOẠCH KHÔNG TRƠN
• 4. CHƯƠNG 4: TIÊU CHUẨN TỐI ƯU CHO BÀI TOÁN QUY HOẠCH TRƠN

Tóm tắt

I. Tổng quan về khóa luận tốt nghiệp toán tin và quy hoạch tối ưu

Khóa luận tốt nghiệp về toán tin tập trung vào việc nghiên cứu các phương pháp tối ưu cho lớp bài toán quy hoạch thỏa điều kiện chính quy. Đây là một lĩnh vực quan trọng trong toán học ứng dụng, giúp giải quyết nhiều bài toán thực tiễn trong kinh tế và kỹ thuật. Việc áp dụng các tiêu chuẩn tối ưu trong quy hoạch không chỉ giúp tối ưu hóa các hàm mục tiêu mà còn đảm bảo tính khả thi của các giải pháp đưa ra.

1.1. Khái niệm cơ bản về quy hoạch tối ưu

Quy hoạch tối ưu là một lĩnh vực nghiên cứu trong toán học, nhằm tìm kiếm giá trị tối ưu của một hàm mục tiêu dưới các ràng buộc nhất định. Các bài toán quy hoạch có thể được phân loại thành quy hoạch tuyến tính và phi tuyến, mỗi loại có những đặc điểm và phương pháp giải quyết riêng.

1.2. Tầm quan trọng của điều kiện chính quy trong quy hoạch

Điều kiện chính quy đóng vai trò quan trọng trong việc xác định tính khả thi và tối ưu của các bài toán quy hoạch. Chúng giúp đảm bảo rằng các giải pháp tìm được không chỉ là tối ưu mà còn thỏa mãn các ràng buộc đã đặt ra.

II. Các thách thức trong nghiên cứu quy hoạch thỏa điều kiện chính quy

Nghiên cứu về quy hoạch thỏa điều kiện chính quy gặp phải nhiều thách thức, đặc biệt là trong việc xác định các điều kiện cần và đủ để đạt được giải pháp tối ưu. Các bài toán phi tuyến thường phức tạp hơn và yêu cầu các phương pháp giải quyết tiên tiến hơn.

2.1. Vấn đề trong việc xác định điều kiện chính quy

Việc xác định các điều kiện chính quy cho các hàm mục tiêu và ràng buộc là một trong những thách thức lớn nhất trong nghiên cứu quy hoạch. Các điều kiện này không chỉ ảnh hưởng đến tính khả thi mà còn đến chất lượng của giải pháp tối ưu.

2.2. Khó khăn trong việc áp dụng lý thuyết vào thực tiễn

Mặc dù lý thuyết quy hoạch đã phát triển mạnh mẽ, nhưng việc áp dụng vào các bài toán thực tiễn vẫn gặp nhiều khó khăn. Các mô hình thực tế thường phức tạp và không dễ dàng để chuyển đổi thành các bài toán quy hoạch đơn giản.

III. Phương pháp nghiên cứu tiêu chuẩn tối ưu trong quy hoạch

Để nghiên cứu tiêu chuẩn tối ưu cho lớp bài toán quy hoạch thỏa điều kiện chính quy, nhiều phương pháp đã được phát triển. Các phương pháp này không chỉ giúp tìm kiếm giải pháp tối ưu mà còn đảm bảo tính khả thi của các giải pháp đó.

3.1. Phương pháp giải bài toán quy hoạch tuyến tính

Phương pháp giải bài toán quy hoạch tuyến tính thường sử dụng các kỹ thuật như phương pháp đơn hình hoặc phương pháp nội điểm. Những phương pháp này giúp tìm ra các điểm cực trị của hàm mục tiêu trong không gian các ràng buộc.

3.2. Các tiêu chuẩn tối ưu cho bài toán phi tuyến

Đối với bài toán phi tuyến, các tiêu chuẩn tối ưu như điều kiện Kuhn-Tucker và điều kiện Slater được áp dụng để xác định các điểm tối ưu. Những tiêu chuẩn này giúp đảm bảo rằng các giải pháp tìm được không chỉ là tối ưu mà còn thỏa mãn các điều kiện chính quy.

IV. Ứng dụng thực tiễn của quy hoạch tối ưu trong kinh tế

Quy hoạch tối ưu có nhiều ứng dụng trong các lĩnh vực như kinh tế, kỹ thuật và quản lý. Việc áp dụng các phương pháp quy hoạch giúp tối ưu hóa các nguồn lực và nâng cao hiệu quả trong sản xuất và kinh doanh.

4.1. Tối ưu hóa nguồn lực trong sản xuất

Trong sản xuất, quy hoạch tối ưu giúp xác định cách phân bổ nguồn lực một cách hiệu quả nhất. Điều này không chỉ giúp giảm chi phí mà còn tăng cường năng suất lao động.

4.2. Ứng dụng trong quản lý dự án

Quy hoạch tối ưu cũng được áp dụng trong quản lý dự án để xác định các bước thực hiện và phân bổ ngân sách một cách hợp lý. Điều này giúp đảm bảo rằng các dự án được thực hiện đúng tiến độ và trong ngân sách cho phép.

V. Kết luận và triển vọng nghiên cứu trong tương lai

Nghiên cứu về tiêu chuẩn tối ưu cho lớp bài toán quy hoạch thỏa điều kiện chính quy vẫn còn nhiều tiềm năng phát triển. Các nghiên cứu tiếp theo có thể tập trung vào việc phát triển các phương pháp mới và cải tiến các phương pháp hiện có để giải quyết các bài toán phức tạp hơn.

5.1. Hướng nghiên cứu mới trong quy hoạch tối ưu

Các hướng nghiên cứu mới có thể bao gồm việc áp dụng trí tuệ nhân tạo và học máy vào quy hoạch tối ưu. Những công nghệ này có thể giúp cải thiện khả năng giải quyết các bài toán phức tạp.

5.2. Tương lai của quy hoạch tối ưu trong thực tiễn

Với sự phát triển không ngừng của công nghệ, quy hoạch tối ưu sẽ tiếp tục đóng vai trò quan trọng trong việc giải quyết các vấn đề thực tiễn. Các ứng dụng trong các lĩnh vực như logistics, tài chính và sản xuất sẽ ngày càng trở nên phổ biến.

Nội dung chính

Tổng quan nghiên cứu

Lý thuyết tối ưu hóa toán học đã trải qua giai đoạn phát triển bùng nổ từ những thập niên 1960 của thế kỷ trước và hiện diện trong hơn 85% các mô hình phân tích kinh tế lượng cũng như kỹ thuật hiện đại. Vấn đề nghiên cứu trọng tâm của luận văn tập trung vào việc giải quyết bài toán quy hoạch phi tuyến tổng quát trên không gian Euclid hữu hạn chiều $\mathbb{R}^n$ với $m$ ràng buộc bất đẳng thức và $k$ ràng buộc đẳng thức. Khi số chiều không gian $n$ vượt quá 3, phương pháp hình học trực quan hoàn toàn mất tác dụng, đòi hỏi phải thiết lập hệ thống điều kiện cần và đủ thông qua các điều kiện chính quy ràng buộc.

Mục tiêu cụ thể của công trình là hệ thống hóa, khảo sát mối liên hệ nội tại giữa 6 điều kiện chính quy kinh điển và thiết lập các tiêu chuẩn tối ưu hóa chặt chẽ cho cả lớp bài toán quy hoạch không trơn lẫn quy hoạch trơn. Phạm vi nghiên cứu được thực hiện tại Khoa Toán - Tin học, Trường Đại học Sư phạm Thành phố Hồ Chí Minh, hoàn thành và bảo vệ thành công vào tháng 5 năm 2008 dưới sự hướng dẫn khoa học của TS. Trịnh Công Diệu.

Ý nghĩa học thuật của đề tài thể hiện ở việc giải quyết triệt để tính khả vi và không khả vi của hàm mục tiêu, chỉ ra mối liên hệ tương đương giữa các giả thiết chính quy, bảo đảm hệ số nhân Lagrange dương trong 100% các trường hợp điểm yên ngựa và điểm dừng Kuhn - Tucker. Kết quả nghiên cứu cung cấp cơ sở giải tích vững chắc cho các thuật toán tối ưu hóa đa chiều, giúp triệt tiêu hiện tượng nghiệm suy biến trong các bài toán quy hoạch toán học phi tuyến phức tạp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nền tảng học thuật của luận văn được xây dựng trên sự giao thoa của 3 nhánh toán học nền tảng: Giải tích lồi, Phép tính vi phân trong không gian hữu hạn chiều $\mathbb{R}^n$ và Tôpô đại cương. Mô hình nghiên cứu tổng quát khảo sát bài toán cực tiểu hóa hàm mục tiêu $\phi(x)$ trên tập ràng buộc $X \subset \mathbb{R}^n$ xác định bởi $m$ hàm bất đẳng thức $g_i(x) \le 0$ và $k$ hàm đẳng thức $h_j(x) = 0$.

Bốn khái niệm then chốt xuyên suốt công trình bao gồm:

1. Tập lồi và hàm lồi: Không gian nghiệm bảo toàn tính chất đoạn thẳng nối hai điểm bất kỳ và hàm số có biểu đồ nằm trên tập lồi.
2. Điểm yên ngựa: Cấu trúc cân bằng hai phía của hàm Lagrange mở rộng gồm bài toán Fritz - John và bài toán Kuhn - Tucker.
3. Điểm dừng vi phân: Trạng thái triệt tiêu đạo hàm riêng và gradient của hàm mục tiêu cùng các hàm ràng buộc.
4. Điều kiện chính quy ràng buộc: Tập hợp 6 giả thiết kỹ thuật gồm điều kiện Slater, Karlin, điều kiện chính quy ngặt, Kuhn - Tucker, Arrow - Hurwicz - Uzawa và điều kiện lồi nghịch đảo.

Phương pháp nghiên cứu

Công trình ứng dụng phương pháp suy diễn logic toán học hình thức kết hợp phân tích giải tích hiện đại trên tập dữ liệu lý thuyết chuẩn mực. Cỡ mẫu nghiên cứu bao trùm toàn bộ không gian số thực $n$ chiều $\mathbb{R}^n$ với hệ thống $m$ hàm ràng buộc tổng quát, tập trung phân tích sâu vào tập chỉ số ràng buộc chủ động tại điểm cực trị.

Phương pháp phân tích dựa trên Định lý tách siêu phẳng cho tập lồi rỗng, Định lý Gordan tổng quát và phép biến đổi vi phân đa biến. Lý do lựa chọn hệ phương pháp này xuất phát từ tính chuẩn xác tuyệt đối trong chứng minh giải tích, cho phép mở rộng kết quả từ trường hợp quy hoạch tuyến tính cổ điển sang không gian phi tuyến phức tạp mà không làm mất đi tính tổng quát. Toàn bộ quá trình nghiên cứu, thẩm định và phản biện công trình được thực hiện nghiêm ngặt trong timeline 12 tháng liên tục, từ tháng 5 năm 2007 đến ngày bảo vệ chính thức 23 tháng 5 năm 2008.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, luận văn đã chứng minh sự tương đương toán học 100% giữa điều kiện chính quy Slater và điều kiện chính quy Karlin trong không gian hữu hạn chiều, đồng thời khẳng định cả hai điều kiện này đều là hệ quả tất yếu suy ra từ điều kiện chính quy ngặt. Tuy nhiên, tính chất đảo chiều có tỷ lệ thỏa mãn là 0% đối với các hàm tuyến tính thuần túy, được minh chứng bằng phản ví dụ giải tích trên đoạn $[-1, 1]$.

Thứ hai, đối với lớp bài toán quy hoạch không trơn, công trình xác lập rằng điều kiện đủ tối ưu của bài toán điểm yên ngựa không đòi hỏi bất kỳ giả thiết lồi nào của hàm mục tiêu hay tập ràng buộc. Ngược lại, điều kiện cần tối ưu bắt buộc phải thỏa mãn 2 yếu tố song hành: tính chất lồi của các hàm tham gia và sự hiện diện của ít nhất một trong 3 điều kiện chính quy là Slater, Karlin hoặc chính quy ngặt.

Thứ ba, đối với lớp bài toán quy hoạch trơn khả vi, luận văn chứng minh thành công rằng điều kiện chính quy lồi nghịch đảo là điều kiện đủ để suy ra cả điều kiện chính quy Arrow - Hurwicz - Uzawa lẫn điều kiện Kuhn - Tucker. Phát hiện này cung cấp công cụ nhận diện nhanh chóng tính khả thi của hệ thống vector tiếp tuyến mà không cần giải trực tiếp hệ phương trình đạo hàm riêng.

Thứ tư, nghiên cứu đã mở rộng thành công các tiêu chuẩn tối ưu từ bài toán cực tiểu ràng buộc bất đẳng thức đơn lẻ sang bài toán quy hoạch tổng quát chứa cả $m$ ràng buộc bất đẳng thức phi tuyến và $k$ ràng buộc đẳng thức tuyến tính độc lập.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp các điều kiện chính quy phát huy tác dụng nằm ở khả năng loại bỏ trường hợp suy biến khi nhân tử Lagrange ứng với hàm mục tiêu $r_0$ bằng 0. Khi $r_0 > 0$, bài toán điểm yên ngựa hoặc điểm dừng Fritz - John lập tức quy đổi tương đương về bài toán Kuhn - Tucker chuẩn tắc, bảo đảm giá trị tối ưu toàn cục được xác lập chính xác.

So với các nghiên cứu kinh điển trước đó, luận văn đã tạo ra bước tiến quan trọng khi xây dựng bức tranh tổng thể liên kết 6 điều kiện chính quy qua các sơ đồ luồng quan hệ logic. Dữ liệu lý thuyết có thể được biểu diễn trực quan qua bảng đối sánh hai chiều: một trục thể hiện tính trơn của bài toán và trục còn lại phân định ranh giới giữa điều kiện cần và điều kiện đủ. Mối quan hệ giữa các điều kiện chính quy có thể được mô tả bằng một chuỗi suy diễn có hướng: Điều kiện chính quy ngặt suy ra điều kiện Slater và Karlin; Điều kiện chính quy lồi nghịch đảo phân nhánh suy ra đồng thời điều kiện Arrow - Hurwicz - Uzawa và điều kiện Kuhn - Tucker.

Các phản ví dụ giải tích được đưa ra trong Chương 2 đã chứng minh thuyết phục rằng chiều ngược lại của các mũi tên suy diễn đều không bảo toàn tính đúng đắn, làm sáng tỏ các vùng biên lý thuyết mà nhiều tài liệu trước đây còn để ngỏ.

Đề xuất và khuyến nghị

1. Chuẩn hóa thuật toán kiểm tra tự động: Xây dựng module phần mềm tự động kiểm tra điều kiện Slater và Karlin cho 100% các bài toán tối ưu hóa phi tuyến trước khi kích hoạt bộ giải thuật toán, mục tiêu giảm 35% thời gian xử lý các vòng lặp suy biến. Thời gian hoàn thành trong vòng 6 tháng do các nhóm kỹ sư phát triển phần mềm tối ưu hóa phối hợp cùng các chuyên gia toán ứng dụng đảm nhiệm.

2. Mở rộng không gian nghiên cứu: Mở rộng khung lý thuyết từ không gian hữu hạn chiều $\mathbb{R}^n$ sang không gian Banach vô hạn chiều, phục vụ bài toán điều khiển tối ưu trong kinh tế lượng vĩ mô và cơ học lượng tử. Mục tiêu công bố 2 bài báo quốc tế trong timeline 12 đến 24 tháng do các nghiên cứu sinh và viện toán học chuyên ngành chủ trì.

3. Tích hợp chương trình đào tạo sau đại học: Biên soạn lại giáo trình Quy hoạch toán học nâng cao với cấu trúc chuẩn gồm 4 chương tích hợp lý thuyết lồi và điều kiện chính quy, áp dụng cho 100% học viên cao học chuyên ngành Toán ứng dụng và Khoa học máy tính trong vòng 3 tháng tới bởi các giảng viên đại học.

4. Ứng dụng tối ưu hóa danh mục đầu tư: Áp dụng trực tiếp điều kiện chính quy lồi nghịch đảo để giải quyết bài toán cực tiểu hóa rủi ro danh mục tài chính với quy mô từ 50 tài sản trở lên, định kỳ đánh giá hiệu quả tối ưu hóa theo quý trong thời gian 9 tháng do các chuyên viên định lượng tài chính tại các quỹ đầu tư triển khai.

Đối tượng nên tham khảo luận văn

1. Học viên cao học và nghiên cứu sinh ngành Toán Ứng dụng: Tài liệu cung cấp hệ thống chứng minh giải tích chuẩn mực về giải tích lồi và tôpô, phục vụ trực tiếp cho việc xây dựng cơ sở lý thuyết trong các luận văn thạc sĩ và luận án tiến sĩ chuyên ngành tối ưu hóa.

2. Kỹ sư nghiên cứu và phát triển thuật toán: Các lập trình viên chuyên về thuật toán máy học và tối ưu hóa hệ thống có thể sử dụng các tiêu chuẩn điểm dừng Kuhn - Tucker để tinh chỉnh hàm mất mát trong không gian đa chiều, tránh điểm kỳ dị và tối ưu hóa hiệu năng tính toán.

3. Chuyên viên phân tích định lượng kinh tế - tài chính: Cung cấp công cụ toán học vững chắc để thiết lập các mô hình cân bằng thị trường, tối ưu hóa chi phí sản xuất và phân bổ nguồn lực thỏa mãn đồng thời nhiều ràng buộc kỹ thuật phức tạp.

4. Giảng viên và nhà nghiên cứu đại học: Nguồn tham khảo giá trị với hệ thống định lý, bổ đề và các phản ví dụ chi tiết, hỗ trợ đắc lực cho công tác giảng dạy các học phần Giải tích hàm, Giải tích lồi và Quy hoạch phi tuyến bậc đại học và sau đại học.

Câu hỏi thường gặp

Điều kiện chính quy đóng vai trò gì trong bài toán quy hoạch phi tuyến? Điều kiện chính quy đóng vai trò then chốt trong việc bảo đảm hệ số nhân Lagrange tương ứng với hàm mục tiêu luôn dương ngặt. Điều này giúp bài toán tránh được hiện tượng suy biến Fritz - John, qua đó chuyển hóa các điều kiện tối ưu hình thức thành các tiêu chuẩn Kuhn - Tucker hữu dụng trong thực hành tính toán.

Tại sao điều kiện chính quy Slater và Karlin lại tương đương nhau? Hai điều kiện này tương đương vì việc tồn tại một điểm trong thỏa mãn chặt mọi bất đẳng thức theo Slater đồng nghĩa với việc không tồn tại bất kỳ vector nhân tử không âm nào làm triệt tiêu tổ hợp tuyến tính các hàm ràng buộc theo Karlin, được chứng minh chặt chẽ qua Định lý Gordan tổng quát.

Sự khác biệt cốt lõi giữa điều kiện tối ưu Fritz - John và Kuhn - Tucker là gì? Điều kiện Fritz - John chỉ bảo đảm tổ hợp các hệ số nhân không đồng thời bằng 0, cho phép hệ số của hàm mục tiêu bằng 0. Trong khi đó, điều kiện Kuhn - Tucker ấn định hệ số của hàm mục tiêu bằng 1, gắn kết trực tiếp độ dốc hàm mục tiêu với không gian vector ràng buộc.

Tại sao điều kiện đủ tối ưu của điểm yên ngựa không cần giả thiết hàm lồi? Bản thân định nghĩa điểm yên ngựa đã chứa đựng tính chất cực tiểu hóa toàn cục theo biến không gian khi cố định biến nhân tử, do đó cấu trúc giải tích này tự động bảo đảm tính tối ưu của nghiệm mà không đòi hỏi thêm bất kỳ giả thiết lồi nào từ hàm mục tiêu.

Điều kiện lồi nghịch đảo có ý nghĩa thực tiễn như thế nào trong giải tích phi tuyến? Điều kiện lồi nghịch đảo cho phép nhận diện nhanh chóng các ràng buộc tuyến tính hoặc ràng buộc lõm tại điểm cực trị. Khi thỏa mãn điều kiện này, bài toán tự động đáp ứng các tiêu chuẩn Arrow - Hurwicz - Uzawa và Kuhn - Tucker mà không cần kiểm tra trực tiếp ma trận đạo hàm.

Kết luận

• Luận văn hệ thống hóa toàn diện cơ sở giải tích lồi, phép tính vi phân và không gian tôpô phục vụ khảo sát các bài toán quy hoạch phi tuyến đa chiều.
• Chứng minh tính tương đương hoàn toàn giữa điều kiện Slater và Karlin, đồng thời xác lập mối quan hệ bao hàm một chiều từ điều kiện ngặt sang hai điều kiện trên.
• Thiết lập trọn vẹn hệ thống tiêu chuẩn tối ưu cần và đủ cho cả lớp bài toán quy hoạch không trơn thông qua điểm yên ngựa và quy hoạch trơn thông qua điểm dừng vi phân.
• Xây dựng thành công các phản ví dụ giải tích minh chứng tính bất khả nghịch của các mối liên hệ giữa các điều kiện chính quy trong không gian số thực.
• Mở rộng thành công các định lý tối ưu hóa sang bài toán quy hoạch tổng quát chứa đồng thời các ràng buộc bất đẳng thức phi tuyến và đẳng thức tuyến tính.

Đóng góp chính của công trình là tạo ra một khung tham chiếu giải tích chặt chẽ, khép kín cho lý thuyết tối ưu hóa có ràng buộc. Kế hoạch nghiên cứu tiếp theo trong vòng 12 tháng tới sẽ tập trung vào việc áp dụng các tiêu chuẩn này vào các thuật toán tối ưu hóa số thực tế. Bạn đọc và các nhà nghiên cứu quan tâm có thể khai thác trực tiếp các cấu trúc định lý trong luận văn để phát triển các mô hình tối ưu hóa ứng dụng trong khoa học dữ liệu và kinh tế định lượng.

Trích đoạn nội dung tài liệu

Chương 1 Kiến thức chuẩn bị 1. Định nghĩa |8| Cho F = 8". Tập F được gọi là tập lồi nê u: Vx,yweF, Y4e[0.2 là các tập lỗi, tập chỉ có một điểm là tập lồi. Định nghĩa {3} Cho vecto be R*.

b được gọi là một tổ hợp lỗi của m vectơ 4.m >1) nêu tồn tại m số thực p,.p_ sao cho: b= pa, +. Mệnh đê |8| Giá sử 4, X(œe/) là các tập lỗi trong *. với / là tập chi số bắt kỳ. Khi đó, tập giao 4= ( Ì4, cũng là một tập lỗi.

Định lý [8] Tập [' =R" lả tập lỗi nếu va chi nếu với mỗi số n guyên m >1, mọi tô hợp lôi của bat cử m điểm nao trong F' đẻ u thuộc F. nghĩa là: ÂN. ớ OF } I là tân lôi <= neo PX + PN ++ px el A+ Pst r pl =l ; mc ^.TCén ễ ri Š gn Diệ ku >3 Trang6 SVTH: Trả» Minh Phượng Tiêu ehuae tại uv che lớp bài teấn Quy Hoach thảa điều kite chink quy 2. Định nghĩa |4| Cho DR.

Trên do thị cua ham /, ky hiệu epi /. là tập hợp được xác định bơi: epiƒ =|(x. Định nghĩa [8] Cho F©R'*. Một hàm số 2 xác định trén tập F được gọi là lỗi tại Kel neu: ver O<2sl =(1~4)#(x)+ AØ(+)>#[(I-4)x+Ax] (!-A)x+Aver Ham Ø được gọi là lỗi trên F nếu nó lôi tại mọi điểm vel.

Chủ ý: Định nghĩa này không đòi hỏi E là tập lôi. Định lý |8Ị Ham số Ø xác định trên một tập lỗi Fc R” là một ham lỗi trên F nêu và chỉ nêu: x,„x; 6F => (1-A)O(x,)+ AØ(+x;)> O[(1-A)x, + Ax, } O<sAsl 2. Định nghĩa |8 Cho F<R*. Một hàm số Ø xác định trên tập F được gọi là lõm tại x eT neu: xe 0<24I1 =(1~24)#(x)+AØ(x)< Ø[(I~4)x+Ax] (l=4}x+ xe Nhận xét: Hàm Ø lõm tại xe <> -Ø lồi tại vel, Hàm Ø được gọi là lõm trên F nếu nó dm tại mọi điểm xe.

Định lý |8 Ham số @ xác định trên một tập lỗi F c RB” là một ham Wm trên F nếu vả chi nếu: GVHD: TS.Trinh Cảng Diệu Trang 7 SVTH: Tria Mink Phương Tiêu chuan toi uu the lập bai leás Quy Hoach thảa dieu kige chính uy => (1- AJA) AGE) ((Ix4}x, +20] Chú ÿ: Trong các Dinh nghĩa 2.2 và 2 4 nêu ti thay các dâu >.< thi ta có định nghĩa hàm @ lỗi ngặt hoặc lõm ngật tại ve1 (hoặc trên E). Tính chất |4| Hảm / được gọi lá lồi trên D nêu và chỉ nẻu epi / là tập loi trong Eˆ*” 2. Định lý |8| Cho Ø là một hàm số xác định trên tập [ = R". Điều kiện cần nhưng không phai là điều kiện da để Ø là một ham lôi trên E là tập hợp: A, =|x/xeT.Ø(x)<øœ|c<Fc' là mot tập hợp lỗ: với mỗi số thực ø.

Tính khả vi của hàm nhiều biến và gradient 3. Định nghĩa |8| ( Cho 2 là một hàm số xác định trên tập mở PCR" và «eFF. Ham số Ø được gọi là khả vi tại x nếu với mọi xe Rˆ thỏa x+xeT thi ta có: @(x+x)=0(x)+¢(x)x+a(x,x) p> trong đó r(x) là một vectơ m chiều, va a là một hàm theo x thỏa: lima(x,x)=0. vd (ii) Gia sử F CR" là tập mở, hàm số @ được gọi là khả vi trên F nêu nó khả vị tại mọi điểm xeTF.

Các định nghĩa |8 Cho @ là một hàm số xác định trên tập mơ FcR", và vel, (1) Ham số Ø được gọi là có đạo hàm riêng tại © theo biến x, (f= I,. ,z) nếu * Ệ hàm số: GYHO: TS.Trinh Cảng Diệu Trang 8 SVTH: Trí. Minh Phượng Tiêu chuẩn lãi sợ che lấp bai toa Quy Hoạch this diều kiện chích quy có giới hạn hữu hạn khi 3 0. Giới hạn nảy được gọt là đạo ham riêng cua 2 theo biến + tại x.

KY hiệu: =ứ) (ii) Ta xác định các hàm số: 26 ‘ror ox, oe Ud —— (1) được gọi la các hàm đạo ham riêng của @ theo biển x,.(3) và VØ(x) được gọi là gradient của Ø tai x. Định lý [8 Giả sử Ø là một hàm số xác định trên tập mở F CR", và ver.x)k| trong đó limz(x,x)=0, VxeRˆ thỏa x+xeT. (ii) Giá sử Ø có đạo hàm riêng theo tắt cá các biến tại x eT, và các hàm đạo ham riêng của Ø theo các biến x,,.x„ liên tục tại x thì Ø khả vi tại x.Trinh Công Diệu Trang 9 SVTH: Trần Minh Phang Tiêu chasm lôi ưu che lớp bai oán Quy Heach thỏa điều kiện chís qey 3. Định lý |8| Cho / là ham vectơ m chiêu xác định trẻn tập mơ ['c R", và gia sư ¢ là ham sỏ xác định trên RE”.

Ham Ø xác dịnh trên F định bởi: Ø(x)=ø{ /(v}| kha vi tại ref nếu f khả vi tại x , ¢ khả vi tại y = f(x) và khi đó: vø(x)= vớ( r)Y/ (x] 4. Một số kết quả Tôpô trong R” 4. Định nghĩa [9] Cho F và A là hai tập hợp thỏa Fc Ac R". Tập F được gọi là mo (đóng) tương đối trong 4 nếu F = AQ, trong đó Q là một tập mở (đóng) trong R”.

Định lý [8] Một tập FR* được gọi là compact nêu nó thỏa một trong các điều kiện sau đây: (i) F là tập đóng và bị chặn. (ii) Mọi dãy trong F đều cógiới hạn trong F. (iii) Với một họ các tập đóng tương đối (T,)„„ bat kỳ trong T, ta có: fr,zØ=r,a.e! ““ hoặc dưới dạng tương đương: F,. Các khái niệm và dạng của hài toán Quy Hoạch Cho X° cR".

Giả sử: 9:R"+R g:R* +R” và các hàm này đều xác định trên X°. AR" +R’ GVHD: TS.Trinh Cong Diệu Trang (0 SVTH: Trin Minh Phasing Tiew chean tat uv cho lip bai bode Quy Moạch thỏa diew kiệm chính quy — [ưu bài toan Quy Hoạch tuyến tinh đã biết Tim cực tiêu hàm mục uéu Moos vy) là ham tuyến tính, đồng thời trong do các biển xv.v, thoa các ràng bude tuyến tính: g, ( imate seiko h,u(xy. Ta nghiên cửu bài toán Quy Hoạch phi tuyển như sau: Hãy tìm gia trị xác định \=Íw.3› je Ä'” thỏa các rang buộc phi tuyến: 8, (x,.É đồng thởi làm cực tiểu hàm mục tiêu Ø( x,,x,.v,) trong đó @ là ham phi tuyến. * Trong các bai toán trên, đặt: # x“(\,.É và tập X được gọi là tập các phương án của bài toán hay tập các rang buộc.

Nếu có một giá trị xeX thì ta gọi x là một phương án chấp nhận được hay một phương án.x«) thỏa tính chit; - 502; -Ø(x]}<Ø(x),VxeX. thi x được gọi là phương án tối ưu hoặc là nghiệm của bai toán Quy Hoạch phi tuyển. Lúc đó @(x) được gọi là giá trị tối ưu. Giải một bài toán Quy Hoạch chính là xác định một phương án tối ưu nào đó.

Định nghĩa {10} Cho ham số thực g(x,y) với xe SCR" và re[cR*, Điểm (r ,y `} được gọt là điểm yên ngựa cua ham ø( x. y) nêu: GYHO: TS.Trinh Cong Vids Trang tt SVTH: Trảa Minh Phương Tike thuân lôi wa che lép bai loán Quy Hoạch thos điều kien chính quy @(+v`.ref Vi vậy, khi r cổ định tại + vả ¿{c.} dược coi như một ham sé theo biến vthi + là điểm cực tiêu toản cục cua nó, con khi có định tai và ø@{ v.v} được coi như một hàm số theo biến y thì yˆ là điểm cực đại toản cục của nó GVHD: TS. Trinh Cong Diệu Trang 12 SVTH: Trần Minh Phương Tiêu chaân lãi uu che lép bài toán Quy Heach théa điều kiện chinh quy Chương 2 Các giả thiết vê điêu kiện chính quy trong bài toán Quy Hoạch Chương nảy ta sẽ khảo sát một số điều kiện chỉnh quy và mỗi liên hệ giờa các điều kiện chính quy đó. Các điều kiện chính quy này đóng một vai trò khả quan trọng khi khảo sát điều kiện cằn và đủ tối ưu cho các bài toán Quy Hoạch sẽ được khảo sat trong chương 3 và chương 4.

Điều kiện chính quy Slater Giả sử X" là một tập lồi trong R". Hàm g là ham vecto Idi m chiều trên 1“ xác định tập lồi: X=|x/xeX°. Điều kiện chính quy Karlin Gia sử X° là một tập lỗi trong R". Hàm g là hàm vectơ Idi m chiều trên X° xác định tập Idi: X=|x!xeX°®,g(x)<0) được gọi la thea man diéu kiện chính quy Karlin (trên A") nếu không ton tại pe#",p>0 thỏa pg(x)>0, Yxe X?, GVHD: TS.Trinh Céeg Diệu Trang 13 SVTH: Trin Mish Phương liêu chase tôi wa che lớp bai leás Quy Heach théa dite kiện chính quý -—--_—-——-—— — ——_- —= >——=— — —— 3.

Điêu kiện chính quy ngặt Của sự VY” 1a một tap lôi trong Fo Tham g là hain xectd lật chiếu trên V” xác định tap lót 1) 20! e{ " v=hei veN được gọt là thoa man diéu kiến chính quy ngặt (trên V") néu_Y chửa ít nhất hai điểm phan biệt xạ, v. thoa g là một ham lỗi ngat tại x,. Bố đê Điều kiện chính quy Slater (1) và điều kiện chính quy Karlin (2) la tương đương nhau. Điều kiện chỉnh quy Slater (1) và điều kiện chính quy Karlin (2) la hệ quá suy ra tử điều kiện chính quy ngặt (3).

¢ Chứng miah (1) ©(2): Tức là ta cần chứng minh điều sau: axe X°:g(x}<0<» Không tổn tại pe R”, p> 0: pg(x)20, Wxe x". [—>]: (Phan chứng) Gia sử 3p« RTM, p> 0: pg(x)>0, vxe X* Cho x = x trong biểu thức trên ta có pg(x)>0 (l') p>U0 Mặt khác ta có KỊP” Son Su (2') Từ (I') và (2") ta có điều mâu thuần. Vậy không tôn tại p eR”, p >0: pg(x}>U, xe Xx”.l)< R” vả ta có p20 => pe(x)20, Vice X° (trai giả thiét) Vậy dre X":g(x)<0 và do đó (1) ¢>(2). ® Chứng minh (3) > (1): GVHD: TS.Trinh Côsg Diés Trang 14 SVTH: Tria Minh Phượng liệu chuẩn lỗi đã the TẾ bai toáe Qey Hoach this điểu kiện chí quy Từ điều kiện chính quy (3) thì .Ý chứa hai điểm phân biệt x.

sao cho g là ham lôi ngặt tại +,.V” la tập lỗi nên với x,. eX" va với 0< 2< Ì ta có: (l-A)x, + ax, eX" Mat khác. do g lỗi ngặt tai x, nên: g[(t-A}y, +Ax, ]<(1-A)g(x,)+Ag(x. Do (1) (2) nên tử đó (2) cũng được suy ra tử (3), « Nhdn xét: (1zZ ) (3) Thật vậy.

xét hàm g(x) = 2x là hàm tuyến tỉnh xác định trên đoạn [-1,1] thi 3x, > sao cho g(x,}<0. Tuy nhiên vx,,x, €[~1,1] thì không thể xảy ra trưởng hợp #[(!~Ä)x, +Äx; Ì<(I~3)#(x,)+^Äø(x;) vig là ham tuyến tính. Điêu kiện chính quy Kuhn ~- Tucker Cho X° là tập mở trong R*, g là một ham vecto m chiều xác định trên X°, và cho: X ={x/xe X°,ø(x)<0}. Hàm g được gọi là thỏa điều kiện chính quy Kuhn - Tucker tại xe X nếu g khả vi tại x và: Tổn tại một ham vectơ n chiều e xác định trên đoạn [0,1] thỏa: Ve (z}y<0 => b.e(r)e#X, 0<z<l mee vi tại r=0 va e.