Bài viết Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính thuộc chủ đề về Giải Đáp Thắc Mắt đang được rất nhiều bạn quan tâm đúng ko nào !! Hôm nay, Hãy cùng https://thpttranhungdao.edu.vn/ tìm hiểu Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính trong bài viết hôm nay nha !
Các bạn đang xem bài viết : “Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính”
1. Giới thiệu 1.1. Bài toán nhà xuất bản 1.2. Bài toán canh tác 1.3. Bài toán đóng thùng 2. Nhắc lại bài toán tối ưu 3. Bài toán tối ưu lồi 4. Linear Programming 5. Quadratic Programming 6. Geometric Programming
Bạn được khuyến khích đọc Bài 16 trước lúc đọc bài này. Nội dung trong bài viết này chủ yếu được dịch từ Chương 4 của cuốn Convex Optimization trong phần Tài liệu tham khảo.
Bạn đang xem: Linear programming là gì
.
Bài này cũng có rất nhiều khái niệm mới và nhiều lý thuyết nên khả năng ko quyến rũ như các bài khác. mặc khác, tôi ko thể bỏ qua vì ko muốn các bạn hoàn toàn mất phương hướng lúc đọc các bài sau.
Độc giả khả năng xem bản pdf tại đây.
1. Giới thiệu
Tôi xin khởi đầu bài viết này bằng ba bài toán khá gần với thực tiễn:
1.1. Bài toán nhà xuất bản
Bài toán
Một nhà xuấn bản (NXB) thu được đơn hàng 600 bản của cuốn “Machine Learning cơ bản” tới Thái Bình và 400 bản tới Hải Phòng. NXB đó có 800 cuốn ở kho Nam Định và 700 cuốn ở kho Hải Dương. Giá chuyển phát một cuốn sách từ Nam Định tới Thái Bình là 50,000 VND (50k), tới Hải Phòng là 100k. Giá chuyển phát một cuốn từ Hải Dương tới Thái Bình là 150k, trong lúc tới Hải Phòng chỉ là 40k. Hỏi để tốn ít chi phí chuyển phát nhất, doanh nghiệp đó nên phân phối mỗi kho chuyển bao nhiêu cuốn tới mỗi vị trí?
Phân tích
Để cho đơn giản, ta xây dựng bảng số lượng chuyển sách từ nguồn tới đích như sau:
Nam Định | Thái Bình | 5 | (x) |
Nam Định | Hải Phỏng | 10 | (y) |
Hải Dương | Thái Bình | 15 | (z) |
Hải Dương | Hải Phòng | 4 |
Tổng chi phí (objective function) sẽ là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Các điều kiện ràng buộc (constraints) viết dưới dạng biểu thức toán học là:
Chuyển 600 cuốn tới Thái Bình: (x + z = 600).
Chuyển 400 cuốn tới Hải Phòng: (y + t = 400).
Lấy từ kho Nam Định ko quá 800: (x + y leq 800).
Lấy từ kho Hải Dương ko quá 700: (z + t leq 700).
(x, y, z, t) là các số một cách tự nhiên. Ràng buộc là số một cách tự nhiên sẽ làm cho bài toán rất khó giải nếu số lượng biến là rất lớn. Với bài toán này, ta giả sử rằng (x, y, z, t) là các số thực dương. Lúc tìm được nghiệm, nếu chúng ko phải là số một cách tự nhiên, ta sẽ lấy các tổng trị giá một cách tự nhiên gần nhất.
Vậy ta cần giải bài toán tối ưu sau đây:
Bài toán NXB:egineqnarray (x, y, z, t) =& argmin_x, y, z, t 5x + 10y + 15z + 4t ~~~~ (1) extsubject to:~ & x + z = 600 ~~~~ (2) & y + t = 400 ~~~~ (3) & x + y leq 800 ~~~(4) & z + t leq 700 ~~~ (5) & x, y, z, t geq 0 ~~~ (6)endeqnarray>
Nhận thấy rằng hàm mục tiêu (objective function) là một hàm tuyến tính của các biến (x, y, z, t). Các điều kiện ràng buộc đều có dạng hyperplanes hoặc haflspaces, đều là các ràng buộc tuyến tính (linear constraints). Bài toán tối ưu với cả objective function và constraints đều là linear được gọi là Linear Programming (LP). Dạng tổng quát và hình thức lập trình để giải một bài toán thuộc loại này sẽ được cho trong phần sau của bài viết này.
Nghiệm cho bài toán này khả năng nhận thấy ngay là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn và số biến nhiều hơn, chúng ta cần một lời giải khả năng tính được bằng cách lập trình.
1.2. Bài toán canh tác
Bài toán
Một anh nông dân có tổng cộng 10ha (10 hecta) đất canh tác. Anh dự trù trồng cà phê và hồ tiêu trên số đất này với tổng chi phí cho việc trồng này là ko quá 16T (triệu đồng). Chi phí để trồng cà phê là 2T cho 1ha, để trồng hồ tiêu là 1T/ha/. Thời kì trồng cà phê là 1 ngày/ha và hồ tiêu là 4 ngày/ha; trong lúc anh chỉ có thời kì tổng cộng là 32 ngày. Sau lúc trừ tất cả các chi phí (bao gồm chi phí trồng cây), mỗi ha cà phê đem lại lợi nhuận 5T, mỗi ha hồ tiêu đem lại lợi nhuận 3T. Hỏi anh phải trồng như thế nào để tối đa lợi nhuận? (Các số liệu khả năng vô lý vì chúng đã được chọn để bài toán ra nghiệm đẹp)
Phân tích
.ub1fd97b28fe20cc50223b9c4e5119af8 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8:active, .ub1fd97b28fe20cc50223b9c4e5119af8:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ub1fd97b28fe20cc50223b9c4e5119af8 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Thúy Nga Music Box #22 | Mạnh Quỳnh & Hương Thủy | Gặp Lại Cố Nhân
Gọi (x) và (y) tuần tự là số ha cà phê và hồ tiêu nhưng anh nông dân nên trồng. Lợi nhuận anh đó thu được là (f(x, y) = 5x + 3y) (triệu đồng).
Các ràng buộc trong bài toán này là:
Tổng diện tích trồng ko vượt quá 10: (x + y leq 10).
Tổng chi phí trồng ko vượt quá 16T: (2x + y leq 16).
Tổng thời kì trồng ko vượt quá 32 ngày: (x + 4y leq 32).
Diện tích cà phê và hồ tiêu là các số ko âm: (x, y geq 0).
Vậy ta có bài toán tối ưu sau đây:
Bài toán canh tác:egineqnarray (x, y) =& argmax_x, y 5x + 3y ~~~~ (7) extsubject to:~ & x + y leq 10 ~~~~ (8) & 2x + y leq 16 ~~~(9) & x + 4y leq 32 ~~~ (10) & x, y geq 0 ~~~ (11)endeqnarray>
Bài toán này hơi khác một tẹo là ta cần tối đa hàm mục tiêu thay vì tối thiểu nó. Việc chuyển bài toán này về bài toán tối thiểu khả năng được thực hiện đơn giản bằng cách đổi dấu hàm mục tiêu. Lúc đó hàm mục tiêu vẫn là linear, các ràng buộc vẫn là các linear constraints, ta lại có một bài toán Linear Programming (LP) nữa.
Bạn cũng khả năng dựa vào hình minh hoạ dưới đây để suy ra nghiệm của bài toán:
Vùng màu xám có dạng polyhedron (trong trường hợp này là đa giác) chính là tập trung các điểm thoả nguyện các ràng buộc từ (8)) tới ((11)). Các đường nét đứt có màu chính là các đường đồng mức của hàm mục tiêu (5x + 3y), mỗi đường ứng với một tổng trị giá không giống nhau với đường càng đỏ ứng với tổng trị giá càng cao. Một cách trực quan, nghiệm của bài toán khả năng tìm được bằng cách vận chuyển đường nét đứt màu xanh về phía bên phải (phía làm cho tổng trị giá của hàm mục tiêu lớn hơn) tới lúc nó ko còn điểm chung với phần đa giác màu xám nữa.
khả năng nhận thấy nghiệm của bài toán chính là điểm màu xanh là giao điểm của hai đường thẳng (x + y = 10) và (2x + y = 16). Giải hệ phương trình này ta có (x^* = 6) và (y^* = 4). Tức anh nông dân nên trồng 6ha cà phê và 4ha hồ tiêu. Lúc đó lợi nhuận thu được là (5x^* + 3y^* = 42 ) triệu đồng, trong lúc anh chỉ mất thời kì là 22 ngày. (Chịu tính toán cái là khác ngay, làm ít, hưởng nhiều).
Đây chính là phương pháp giải trong sách toán lớp 10 (ngày tôi học lớp 10).
Với nhiều biến hơn và nhiều ràng buộc hơn, chúng ta liệu khả năng vẽ được hình như thế này để nhìn ra nghiệm hay ko? Câu trả lời của tôi là nên tìm một phương tiện để với nhiều biến hơn và với các ràng buộc không giống nhau, chúng ta khả năng tìm ra nghiệm gần như ngay tức khắc.
1.3. Bài toán đóng thùng
Bài toán
Một doanh nghiệp phải chuyển 400 (m^3) cát tới vị trí xây dựng ở bên kia sông bằng cách thuê một chiếc xà lan. Ngoài chi phí vận chuyển một lượt đi về là 100k của chiếc xà lan, doanh nghiệp đó phải thiết kế một thùng hình hộp chữ nhật đặt trên xà lan để đựng cát. Chiếc thùng này ko cần nắp, chi phí cho các mặt xung quanh là 1T/(m^2), cho mặt đáy là 2T/(m^2). Hỏi kích thước của chiếc thùng đó như thế nào để tổng chi phí vận chuyển là nhỏ nhất. Để cho đơn giản, giả sử cát chỉ được đổ ngang hoặc thấp hơn với phần trên của thành thùng, ko có ngọn. Giả sử thêm rằng xà lan rộng vô hạn và chứa được sức nặng vô hạn, giả sử này khiến bài toán dễ giải hơn.
Phân tích
Giả sử chiếc thùng cần làm có chiều dài là (x) ((m)), chiều rộng là (y) và chiều cao là (z). dung tích của thùng là (xyz) (đơn vị là (m^3)). Có hai loại chi phí là:
Chi phí thuê xà lan: số chuyến xà lan phải thuê là (frac400xyz) (ta hãy tạm giả sử rằng đây là một vài một cách tự nhiên, việc làm tròn này sẽ ko thay đổi ngay kết quả một cách đáng kể vì chi phí vận chuyển một chuyến là nhỏ so với chi phí làm thùng). Số tiền phải trả cho xà lan sẽ là (0.1frac400xyz = frac40xyz).
Chi phí làm thùng: Diện tích xung quanh của thùng là (2 (x + y)z ). Diện tích đáy là (xy). Vậy tổng chi phí làm thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).
Tổng toàn thể chi phí là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều kiện ràng buộc duy nhất là kích thước thùng phải là các số dương. Vậy ta có bài toán tối ưu sau:
Bài toán vận chuyển:egineqnarray (x, y) =& argmin_x, y, z 40x^-1y^-1z^-1 + 2(xy + yz + zx) ~~~~ (13) extsubject to:~ & x, y, z > 0 ~~~~ (14)endeqnarray>
Bài toán này thuộc loại Geometric Programming (GP). Khái niệm của GP và cách dùng phương tiện tối ưu sẽ được trình diễn trong phần sau của bài viết.
.ue61bcfe3ef9416e82ce9b90fc2ab49fa { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:active, .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Chả cá trôi siêu ngon dễ làm – Best Grilled chopped rohu fish ever made
Xem thêm: Endocytosis Là Gì – Endocytosis, Phagocytosis, And Pinocytosis Video
Nhận thấy rằng bài này hoàn toàn khả năng dùng bất đẳng thức Cauchy để giải được, nhưng tôi vẫn muốn một lời giải cho bài toán tổng quát sao cho khả năng lập trình được.
(Lời giải:egineqnarray f(x, y, z) &=& frac20xyz + frac20xyz + 2xy + 2yz + 2zx &geq & 5sqrt3200endeqnarray>dấu bằng xảy ra lúc và chỉ lúc (x = y = z = sqrt10). Bài này có nhẽ hợp với các kỳ thi vì dữ kiện quá đẹp. Tư nhân tôi thích các đề bài ra kiểu này hơn là buộc phải đi tìm tổng trị giá nhỏ nhất của một biểu thức nhàm chán, nhiều học trò cho rằng ko biết học bất đẳng thức để làm gì!)
Nếu có các ràng buộc về kích thước của thùng và trọng lượng nhưng xà lan tải được thì khả năng tìm được lời giải đơn giản như thế này ko?
Những bài toán trên đây đều là các bài toán tối ưu. Chuẩn xác hơn nữa, chúng đều là các bài toán tối ưu lồi (convex optimization problems) như các bạn sẽ thấy ở phần sau. Và việc tìm lời giải khả năng ko mấy điều kiện, thậm chí giải bằng tay cũng khả năng ra kết quả. mặc khác, mục tiêu của bài viết này ko phải là hướng dẫn các bạn giải các bài toán trên bằng tay, nhưng là phương pháp nhận diện các bài toán và đưa chúng về các dạng nhưng các toolboxes sẵn có khả năng giúp chúng ta. Trên thực tiễn, lượng dữ kiện và số biến cần tối ưu lớn hơn nhiều, chúng ta ko thể giải các bài toán trên bằng tay được.
Trước hết, chúng ta cần hiểu các khái niệm về convex optimization problems và vì sao convex lại quan trọng. (Độc giả khả năng đọc tới phần 4 nếu ko muốn biết các khái niệm và định lý toán trong phần 2 và 3.)
2. Nhắc lại bài toán tối ưu
2.1. Các khái niệm cơ bản
Tôi xin nhắc lại bài toán tối ưu ở dạng tổng quát:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(15)&& h_j(mathbfx) = 0, ~~ j = 1, 2, dots, pendeqnarray>
Phát biểu bằng lời: Tìm tổng trị giá của biến (mathbfx) để tối thiểu hàm (f_0(mathbfx)) trong số các tổng trị giá của (mathbfx) thoả nguyện các điệu hiện ràng buộc. Ta có bảng các tên gọi tiếng Anh và tiếng Việt như sau:
(mathbfx in mathbbR^n) | optimization variable | biến tối ưu |
(f_0: mathbbR^n ightarrow mathbbR) | objective/los/cost function | hàm mục tiêu |
(f_i(mathbfx) leq 0 ) | inequality constraints | bất đẳng thức ràng buộc |
(f_i: mathbbR^n ightarrow mathbbR) | inequality constraint functions | – |
(h_j(mathbfx) = 0 ) | equality constraints | đẳng thức ràng buộc |
(h_j: mathbbR^n ightarrow mathbbR) | equality constraint functions | – |
(mathcalD = igcap_i=0^m extdomf_i cap igcap_pj=1^p extdomh_i ) | domain | tập xác định |
mặt khác:
Lúc (m = p = 0), bài toán ((15)) được gọi là unconstrained optimization problem (bài toán tối ưu ko ràng buộc).
(mathcalD) chỉ là tập xác định, tức giao của tất cả các tập xác định của mọi hàm số xuất hiện trong bài toán. Tập trung các điểm thoả nguyện mọi điều kiện ràng buộc, thông thường, là một tập con của (mathcalD) được gọi là feasible set hoặc constraint set. Lúc feasible set là một tập rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta gọi điểm đó là feasible.
2.2. Optimal and locally optimal points
Một điểm (mathbfx^*) được gọi là một điểm optimal point (điểm tối ưu), hoặc là nghiệm của bài toán ((15)) nếu (mathbfx^*) là feasible và (f_0(mathbfx^*) = p^*). Tất hợp tất cả các optimal points được gọi là optimal set.
Nếu optimal set là một tập ko rỗng, ta nói bài toán ((15)) là solvable (giải được). Trái lại, nếu optimal set là một tập rỗng, ta nói optimal value là ko thể đạt được (not attained/ not achieved).
Ví dụ: xét hàm mục tiêu (f(x) = 1/x) với ràng buộc (x > 0). Optimal value của bài toán này là (p^* = 0) nhưng optimal set là một tập rỗng vì ko có tổng trị giá nào của (x) để hàm mục tiêu đạt tổng trị giá 0. Lúc này ta nói tổng trị giá tối ưu là ko đạt được.
Với hàm một biến, một điểm là cực tiểu của một hàm số nếu tại đó, hàm số đạt tổng trị giá nhỏ nhất trong một phụ cận (và phụ cận này thuộc tập xác định của hàm số). Trong ko gian 1 chiều, phụ cận được hiểu là trị tuyệt tối của hiệu 2 điểm nhỏ hơn một tổng trị giá nào đó.
Trong toán tối ưu (thường là ko gian nhiều chiều), ta gọi một điểm (mathbfx) là locally optimal (cực tiểu) nếu tồn tại một tổng trị giá (thường được gọi là bán kinh) (R) sao cho:egineqnarray f_0(mathbfx) = & extinf f_i(mathbfz) leq 0, i = 1, dots, m, & h_j(mathbfz) = 0, j = 1, dots, p, endeqnarray>
Nếu một điểm feasible (mathbfx) thoả nguyện (f_i(mathbfx) = 0), ta nói rằng bất đẳng thức ràng buộc thứ (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)
2.3. Một vài xem xét
Mặc dù trong khái niệm bài toán tối ưu ((15)) là cho bài toán tối thiểu hàm mục tiêu với các ràng buộc thoả nguyện các điều kiện nhỏ hơn hoặc bằng 0, các bài toán tối ưu với tối đa hàm mục tiêu và điều kiện ràng buộc ở dạng khác đều khả năng đưa về được dạng này:
.u6473a9fe8a15dd544bfd68e2c537f097 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097:active, .u6473a9fe8a15dd544bfd68e2c537f097:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .u6473a9fe8a15dd544bfd68e2c537f097 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Que Hàn Tiếng Anh Là Gì ? Máy Hàn Tiếng Anh Là Gì ? Các ngôn từ Anh
(max f_0(mathbfx) Leftrightarrowmin -f_0(mathbfx) ).
(f_i(mathbfx) leq g(mathbfx) Leftrightarrow f_i(mathbfx) – g(mathbfx) leq 0).
(f_i(mathbfx) geq 0 Leftrightarrow -f_i(mathbfx) leq 0 ).
(a leq f_i(mathbfx) leq b Leftrightarrow f_i(mathbfx) -b leq 0) và (a – f_i(mathbfx) leq 0).
(f_i(mathbfx) leq 0 Leftrightarrow f_i(mathbfx) + s_i = 0 ) và (s_i geq 0). (s_i) được gọi là slack variable. Phép chuyển đổi đơn giản này trong nhiều trường hợp lại tỏ ra hiệu quả vì bất đẳng thức (s_i geq 0) thường dễ khắc phục hơn là (f_i(mathbfx) leq 0).
3. Bài toán tối ưu lồi
Trong toán tối ưu, chúng ta đặc trưng quan tâm tới những bài toán nhưng hàm mục tiêu là một hàm lồi, và feasible set cũng là một tập lồi.
3.1. Khái niệm
Một bài toán tối ưu lồi (convex optimization problem) là một bài toán tối ưu có dạng:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(16)&& mathbfa_j^Tmathbfx – b_j = 0, j = 1, dots,endeqnarray>trong đó (f_0, f_1, dots, f_m) là các hàm lồi.
So với bài toán tối ưu ((15)), bài toán tối ưu lồi ((16)) có thêm ba điều kiện nữa:
Hàm mục tiêu là một hàm lồi.
Các hàm bất đẳng thức ràng buộc (f_i) là các hàm lồi.
Hàm đẳng thức ràng buộc (h_j) là affine (hàm linear cùng với một hẳng số nữa được gọi là affine).
Một vài nhận xét:
Tập trung các điểm thoả nguyện (h_j(mathbfx) = 0) là một tập lồi vì nó có dạng một hyperplane.
Vậy, trong một bài toán tối ưu lồi, ta tối thiểu một hàm mục tiêu lồi trên một tập lồi.
3.2. Cực tiểu của bài toán tối ưu lồi chính là điểm tối ưu.
TÍnh chất quan trọng nhất của bài toán tối ưu lồi chính là bất kỳ locally optimal point chính là một điểm (globally) optimal point.
Tính chất quan trọng này khả năng chứng minh bằng phản chứng như sau. Gọi (mathbfx_0) là một điểm locally optimal, tức:
với (R > 0) nào đó. Giả sử (mathbfx_0) ko phải là globally optimal point, tức tồn tại một feasible point (mathbfy) sao cho (f(mathbfy) &leq& (1 – heta)f_0(mathbfx_0) + heta f_0(mathbfy) & &=& f_0(mathbfx_0)endeqnarray>
điều này tranh chấp với giả thiết (mathbfx_0) là một điểm cực tiểu. Vậy giả sử sai, tức (mathbfx_0) chính là globally optimal point và ta có điều phải chứng minh.
Chứng minh bằng lời: giả sử một điểm cực tiểu ko phải là điểm làm cho hàm số đạt tổng trị giá nhỏ nhất. Với điều kiện feasible set và hàm mục tiêu là lồi, ta luôn tìm được một điểm khác trong phụ cận của điểm cực tiểu đó sao cho tổng trị giá của hàm mục tiêu tại điểm mới này nhỏ hơn tổng trị giá của hàm mục tiêu tại điểm cực tiểu. Sự tranh chấp này chỉ ra rằng với một bài toán tối ưu lồi, điểm cực tiểu phải là điểm làm cho hàm số đạt tổng trị giá nhỏ nhất.
Xem thêm: Garment Là Gì – Tiếng Anh Chuyên Ngành May Mặc
3.3. Điều kiện tối ưu cho hàm mục tiêu khả vi
Nếu hàm mục tiêu (f_0) là khả vi (differentiable), theo first-order condition, với mọi (mathbfx, mathbfy in extdomf_0), ta có:
Đặt (mathcalX) là feasible set. Điều kiện cần và đủ để một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua việc chứng minh điều kiện cần và đủ này, độc giả khả năng tìm trong trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.
Phân mục: Hỏi Đáp
Các câu hỏi về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Team Asinana nhưng cụ thể là Ý Nhi đã biên soạn bài viết dựa trên tư liệu sẵn có và tri thức từ Internet. Đương nhiên tụi mình biết có nhiều câu hỏi và nội dung chưa thỏa mãn được buộc phải của các bạn.
Thế nhưng với ý thức tiếp thu và phát triển hơn, Mình luôn đón nhận tất cả các ý kiến khen chê từ các bạn & Quý đọc giả cho bài viêt Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Nếu có bắt kỳ câu hỏi thắc mắt nào vê Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính hãy cho chúng mình biết nha, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình phát triển hơn hơn trong các bài sau nha
Các Hình Ảnh Về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Các từ khóa tìm kiếm cho bài viết #Linear #Programming #Là #Gì #Linear #Programming #Quy #Hoạch #Tuyến #Tính
Xem thêm dữ liệu, về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính tại WikiPedia
Bạn hãy tìm thông tin cụ thể về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính từ web Wikipedia tiếng Việt.◄
Tham Gia Cộng Đồng Tại
💝 Nguồn Tin tại: https://thpttranhungdao.edu.vn
💝 Xem Thêm Câu Hỏi Quanh Ta tại : https://thpttranhungdao.edu.vn/la-gi/
[toggle title=”xem thêm thông tin chi tiết về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính” state=”close”]
Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Hình Ảnh về: Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Video về: Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Wiki về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính -
Bài viết Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính thuộc chủ đề về Giải Đáp Thắc Mắt đang được rất nhiều bạn quan tâm đúng ko nào !! Hôm nay, Hãy cùng https://thpttranhungdao.edu.vn/ tìm hiểu Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính trong bài viết hôm nay nha !
Các bạn đang xem bài viết : “Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính”
1. Giới thiệu 1.1. Bài toán nhà xuất bản 1.2. Bài toán canh tác 1.3. Bài toán đóng thùng 2. Nhắc lại bài toán tối ưu 3. Bài toán tối ưu lồi 4. Linear Programming 5. Quadratic Programming 6. Geometric Programming
Bạn được khuyến khích đọc Bài 16 trước lúc đọc bài này. Nội dung trong bài viết này chủ yếu được dịch từ Chương 4 của cuốn Convex Optimization trong phần Tài liệu tham khảo.
Bạn đang xem: Linear programming là gì
.
Bài này cũng có rất nhiều khái niệm mới và nhiều lý thuyết nên khả năng ko quyến rũ như các bài khác. mặc khác, tôi ko thể bỏ qua vì ko muốn các bạn hoàn toàn mất phương hướng lúc đọc các bài sau.
Độc giả khả năng xem bản pdf tại đây.
1. Giới thiệu
Tôi xin khởi đầu bài viết này bằng ba bài toán khá gần với thực tiễn:
1.1. Bài toán nhà xuất bản
Bài toán
Một nhà xuấn bản (NXB) thu được đơn hàng 600 bản của cuốn “Machine Learning cơ bản” tới Thái Bình và 400 bản tới Hải Phòng. NXB đó có 800 cuốn ở kho Nam Định và 700 cuốn ở kho Hải Dương. Giá chuyển phát một cuốn sách từ Nam Định tới Thái Bình là 50,000 VND (50k), tới Hải Phòng là 100k. Giá chuyển phát một cuốn từ Hải Dương tới Thái Bình là 150k, trong lúc tới Hải Phòng chỉ là 40k. Hỏi để tốn ít chi phí chuyển phát nhất, doanh nghiệp đó nên phân phối mỗi kho chuyển bao nhiêu cuốn tới mỗi vị trí?
Phân tích
Để cho đơn giản, ta xây dựng bảng số lượng chuyển sách từ nguồn tới đích như sau:
Nam Định | Thái Bình | 5 | (x) |
Nam Định | Hải Phỏng | 10 | (y) |
Hải Dương | Thái Bình | 15 | (z) |
Hải Dương | Hải Phòng | 4 |
Tổng chi phí (objective function) sẽ là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Các điều kiện ràng buộc (constraints) viết dưới dạng biểu thức toán học là:
Chuyển 600 cuốn tới Thái Bình: (x + z = 600).
Chuyển 400 cuốn tới Hải Phòng: (y + t = 400).
Lấy từ kho Nam Định ko quá 800: (x + y leq 800).
Lấy từ kho Hải Dương ko quá 700: (z + t leq 700).
(x, y, z, t) là các số một cách tự nhiên. Ràng buộc là số một cách tự nhiên sẽ làm cho bài toán rất khó giải nếu số lượng biến là rất lớn. Với bài toán này, ta giả sử rằng (x, y, z, t) là các số thực dương. Lúc tìm được nghiệm, nếu chúng ko phải là số một cách tự nhiên, ta sẽ lấy các tổng trị giá một cách tự nhiên gần nhất.
Vậy ta cần giải bài toán tối ưu sau đây:
Bài toán NXB:egineqnarray (x, y, z, t) =& argmin_x, y, z, t 5x + 10y + 15z + 4t ~~~~ (1) extsubject to:~ & x + z = 600 ~~~~ (2) & y + t = 400 ~~~~ (3) & x + y leq 800 ~~~(4) & z + t leq 700 ~~~ (5) & x, y, z, t geq 0 ~~~ (6)endeqnarray>
Nhận thấy rằng hàm mục tiêu (objective function) là một hàm tuyến tính của các biến (x, y, z, t). Các điều kiện ràng buộc đều có dạng hyperplanes hoặc haflspaces, đều là các ràng buộc tuyến tính (linear constraints). Bài toán tối ưu với cả objective function và constraints đều là linear được gọi là Linear Programming (LP). Dạng tổng quát và hình thức lập trình để giải một bài toán thuộc loại này sẽ được cho trong phần sau của bài viết này.
Nghiệm cho bài toán này khả năng nhận thấy ngay là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn và số biến nhiều hơn, chúng ta cần một lời giải khả năng tính được bằng cách lập trình.
1.2. Bài toán canh tác
Bài toán
Một anh nông dân có tổng cộng 10ha (10 hecta) đất canh tác. Anh dự trù trồng cà phê và hồ tiêu trên số đất này với tổng chi phí cho việc trồng này là ko quá 16T (triệu đồng). Chi phí để trồng cà phê là 2T cho 1ha, để trồng hồ tiêu là 1T/ha/. Thời kì trồng cà phê là 1 ngày/ha và hồ tiêu là 4 ngày/ha; trong lúc anh chỉ có thời kì tổng cộng là 32 ngày. Sau lúc trừ tất cả các chi phí (bao gồm chi phí trồng cây), mỗi ha cà phê đem lại lợi nhuận 5T, mỗi ha hồ tiêu đem lại lợi nhuận 3T. Hỏi anh phải trồng như thế nào để tối đa lợi nhuận? (Các số liệu khả năng vô lý vì chúng đã được chọn để bài toán ra nghiệm đẹp)
Phân tích
.ub1fd97b28fe20cc50223b9c4e5119af8 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8:active, .ub1fd97b28fe20cc50223b9c4e5119af8:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ub1fd97b28fe20cc50223b9c4e5119af8 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Thúy Nga Music Box #22 | Mạnh Quỳnh & Hương Thủy | Gặp Lại Cố Nhân
Gọi (x) và (y) tuần tự là số ha cà phê và hồ tiêu nhưng anh nông dân nên trồng. Lợi nhuận anh đó thu được là (f(x, y) = 5x + 3y) (triệu đồng).
Các ràng buộc trong bài toán này là:
Tổng diện tích trồng ko vượt quá 10: (x + y leq 10).
Tổng chi phí trồng ko vượt quá 16T: (2x + y leq 16).
Tổng thời kì trồng ko vượt quá 32 ngày: (x + 4y leq 32).
Diện tích cà phê và hồ tiêu là các số ko âm: (x, y geq 0).
Vậy ta có bài toán tối ưu sau đây:
Bài toán canh tác:egineqnarray (x, y) =& argmax_x, y 5x + 3y ~~~~ (7) extsubject to:~ & x + y leq 10 ~~~~ (8) & 2x + y leq 16 ~~~(9) & x + 4y leq 32 ~~~ (10) & x, y geq 0 ~~~ (11)endeqnarray>
Bài toán này hơi khác một tẹo là ta cần tối đa hàm mục tiêu thay vì tối thiểu nó. Việc chuyển bài toán này về bài toán tối thiểu khả năng được thực hiện đơn giản bằng cách đổi dấu hàm mục tiêu. Lúc đó hàm mục tiêu vẫn là linear, các ràng buộc vẫn là các linear constraints, ta lại có một bài toán Linear Programming (LP) nữa.
Bạn cũng khả năng dựa vào hình minh hoạ dưới đây để suy ra nghiệm của bài toán:
Vùng màu xám có dạng polyhedron (trong trường hợp này là đa giác) chính là tập trung các điểm thoả nguyện các ràng buộc từ (8)) tới ((11)). Các đường nét đứt có màu chính là các đường đồng mức của hàm mục tiêu (5x + 3y), mỗi đường ứng với một tổng trị giá không giống nhau với đường càng đỏ ứng với tổng trị giá càng cao. Một cách trực quan, nghiệm của bài toán khả năng tìm được bằng cách vận chuyển đường nét đứt màu xanh về phía bên phải (phía làm cho tổng trị giá của hàm mục tiêu lớn hơn) tới lúc nó ko còn điểm chung với phần đa giác màu xám nữa.
khả năng nhận thấy nghiệm của bài toán chính là điểm màu xanh là giao điểm của hai đường thẳng (x + y = 10) và (2x + y = 16). Giải hệ phương trình này ta có (x^* = 6) và (y^* = 4). Tức anh nông dân nên trồng 6ha cà phê và 4ha hồ tiêu. Lúc đó lợi nhuận thu được là (5x^* + 3y^* = 42 ) triệu đồng, trong lúc anh chỉ mất thời kì là 22 ngày. (Chịu tính toán cái là khác ngay, làm ít, hưởng nhiều).
Đây chính là phương pháp giải trong sách toán lớp 10 (ngày tôi học lớp 10).
Với nhiều biến hơn và nhiều ràng buộc hơn, chúng ta liệu khả năng vẽ được hình như thế này để nhìn ra nghiệm hay ko? Câu trả lời của tôi là nên tìm một phương tiện để với nhiều biến hơn và với các ràng buộc không giống nhau, chúng ta khả năng tìm ra nghiệm gần như ngay tức khắc.
1.3. Bài toán đóng thùng
Bài toán
Một doanh nghiệp phải chuyển 400 (m^3) cát tới vị trí xây dựng ở bên kia sông bằng cách thuê một chiếc xà lan. Ngoài chi phí vận chuyển một lượt đi về là 100k của chiếc xà lan, doanh nghiệp đó phải thiết kế một thùng hình hộp chữ nhật đặt trên xà lan để đựng cát. Chiếc thùng này ko cần nắp, chi phí cho các mặt xung quanh là 1T/(m^2), cho mặt đáy là 2T/(m^2). Hỏi kích thước của chiếc thùng đó như thế nào để tổng chi phí vận chuyển là nhỏ nhất. Để cho đơn giản, giả sử cát chỉ được đổ ngang hoặc thấp hơn với phần trên của thành thùng, ko có ngọn. Giả sử thêm rằng xà lan rộng vô hạn và chứa được sức nặng vô hạn, giả sử này khiến bài toán dễ giải hơn.
Phân tích
Giả sử chiếc thùng cần làm có chiều dài là (x) ((m)), chiều rộng là (y) và chiều cao là (z). dung tích của thùng là (xyz) (đơn vị là (m^3)). Có hai loại chi phí là:
Chi phí thuê xà lan: số chuyến xà lan phải thuê là (frac400xyz) (ta hãy tạm giả sử rằng đây là một vài một cách tự nhiên, việc làm tròn này sẽ ko thay đổi ngay kết quả một cách đáng kể vì chi phí vận chuyển một chuyến là nhỏ so với chi phí làm thùng). Số tiền phải trả cho xà lan sẽ là (0.1frac400xyz = frac40xyz).
Chi phí làm thùng: Diện tích xung quanh của thùng là (2 (x + y)z ). Diện tích đáy là (xy). Vậy tổng chi phí làm thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).
Tổng toàn thể chi phí là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều kiện ràng buộc duy nhất là kích thước thùng phải là các số dương. Vậy ta có bài toán tối ưu sau:
Bài toán vận chuyển:egineqnarray (x, y) =& argmin_x, y, z 40x^-1y^-1z^-1 + 2(xy + yz + zx) ~~~~ (13) extsubject to:~ & x, y, z > 0 ~~~~ (14)endeqnarray>
Bài toán này thuộc loại Geometric Programming (GP). Khái niệm của GP và cách dùng phương tiện tối ưu sẽ được trình diễn trong phần sau của bài viết.
.ue61bcfe3ef9416e82ce9b90fc2ab49fa { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:active, .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Chả cá trôi siêu ngon dễ làm - Best Grilled chopped rohu fish ever made
Xem thêm: Endocytosis Là Gì – Endocytosis, Phagocytosis, And Pinocytosis Video
Nhận thấy rằng bài này hoàn toàn khả năng dùng bất đẳng thức Cauchy để giải được, nhưng tôi vẫn muốn một lời giải cho bài toán tổng quát sao cho khả năng lập trình được.
(Lời giải:egineqnarray f(x, y, z) &=& frac20xyz + frac20xyz + 2xy + 2yz + 2zx &geq & 5sqrt3200endeqnarray>dấu bằng xảy ra lúc và chỉ lúc (x = y = z = sqrt10). Bài này có nhẽ hợp với các kỳ thi vì dữ kiện quá đẹp. Tư nhân tôi thích các đề bài ra kiểu này hơn là buộc phải đi tìm tổng trị giá nhỏ nhất của một biểu thức nhàm chán, nhiều học trò cho rằng ko biết học bất đẳng thức để làm gì!)
Nếu có các ràng buộc về kích thước của thùng và trọng lượng nhưng xà lan tải được thì khả năng tìm được lời giải đơn giản như thế này ko?
Những bài toán trên đây đều là các bài toán tối ưu. Chuẩn xác hơn nữa, chúng đều là các bài toán tối ưu lồi (convex optimization problems) như các bạn sẽ thấy ở phần sau. Và việc tìm lời giải khả năng ko mấy điều kiện, thậm chí giải bằng tay cũng khả năng ra kết quả. mặc khác, mục tiêu của bài viết này ko phải là hướng dẫn các bạn giải các bài toán trên bằng tay, nhưng là phương pháp nhận diện các bài toán và đưa chúng về các dạng nhưng các toolboxes sẵn có khả năng giúp chúng ta. Trên thực tiễn, lượng dữ kiện và số biến cần tối ưu lớn hơn nhiều, chúng ta ko thể giải các bài toán trên bằng tay được.
Trước hết, chúng ta cần hiểu các khái niệm về convex optimization problems và vì sao convex lại quan trọng. (Độc giả khả năng đọc tới phần 4 nếu ko muốn biết các khái niệm và định lý toán trong phần 2 và 3.)
2. Nhắc lại bài toán tối ưu
2.1. Các khái niệm cơ bản
Tôi xin nhắc lại bài toán tối ưu ở dạng tổng quát:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(15)&& h_j(mathbfx) = 0, ~~ j = 1, 2, dots, pendeqnarray>
Phát biểu bằng lời: Tìm tổng trị giá của biến (mathbfx) để tối thiểu hàm (f_0(mathbfx)) trong số các tổng trị giá của (mathbfx) thoả nguyện các điệu hiện ràng buộc. Ta có bảng các tên gọi tiếng Anh và tiếng Việt như sau:
(mathbfx in mathbbR^n) | optimization variable | biến tối ưu |
(f_0: mathbbR^n ightarrow mathbbR) | objective/los/cost function | hàm mục tiêu |
(f_i(mathbfx) leq 0 ) | inequality constraints | bất đẳng thức ràng buộc |
(f_i: mathbbR^n ightarrow mathbbR) | inequality constraint functions | – |
(h_j(mathbfx) = 0 ) | equality constraints | đẳng thức ràng buộc |
(h_j: mathbbR^n ightarrow mathbbR) | equality constraint functions | – |
(mathcalD = igcap_i=0^m extdomf_i cap igcap_pj=1^p extdomh_i ) | domain | tập xác định |
mặt khác:
Lúc (m = p = 0), bài toán ((15)) được gọi là unconstrained optimization problem (bài toán tối ưu ko ràng buộc).
(mathcalD) chỉ là tập xác định, tức giao của tất cả các tập xác định của mọi hàm số xuất hiện trong bài toán. Tập trung các điểm thoả nguyện mọi điều kiện ràng buộc, thông thường, là một tập con của (mathcalD) được gọi là feasible set hoặc constraint set. Lúc feasible set là một tập rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta gọi điểm đó là feasible.
2.2. Optimal and locally optimal points
Một điểm (mathbfx^*) được gọi là một điểm optimal point (điểm tối ưu), hoặc là nghiệm của bài toán ((15)) nếu (mathbfx^*) là feasible và (f_0(mathbfx^*) = p^*). Tất hợp tất cả các optimal points được gọi là optimal set.
Nếu optimal set là một tập ko rỗng, ta nói bài toán ((15)) là solvable (giải được). Trái lại, nếu optimal set là một tập rỗng, ta nói optimal value là ko thể đạt được (not attained/ not achieved).
Ví dụ: xét hàm mục tiêu (f(x) = 1/x) với ràng buộc (x > 0). Optimal value của bài toán này là (p^* = 0) nhưng optimal set là một tập rỗng vì ko có tổng trị giá nào của (x) để hàm mục tiêu đạt tổng trị giá 0. Lúc này ta nói tổng trị giá tối ưu là ko đạt được.
Với hàm một biến, một điểm là cực tiểu của một hàm số nếu tại đó, hàm số đạt tổng trị giá nhỏ nhất trong một phụ cận (và phụ cận này thuộc tập xác định của hàm số). Trong ko gian 1 chiều, phụ cận được hiểu là trị tuyệt tối của hiệu 2 điểm nhỏ hơn một tổng trị giá nào đó.
Trong toán tối ưu (thường là ko gian nhiều chiều), ta gọi một điểm (mathbfx) là locally optimal (cực tiểu) nếu tồn tại một tổng trị giá (thường được gọi là bán kinh) (R) sao cho:egineqnarray f_0(mathbfx) = & extinf f_i(mathbfz) leq 0, i = 1, dots, m, & h_j(mathbfz) = 0, j = 1, dots, p, endeqnarray>
Nếu một điểm feasible (mathbfx) thoả nguyện (f_i(mathbfx) = 0), ta nói rằng bất đẳng thức ràng buộc thứ (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)
2.3. Một vài xem xét
Mặc dù trong khái niệm bài toán tối ưu ((15)) là cho bài toán tối thiểu hàm mục tiêu với các ràng buộc thoả nguyện các điều kiện nhỏ hơn hoặc bằng 0, các bài toán tối ưu với tối đa hàm mục tiêu và điều kiện ràng buộc ở dạng khác đều khả năng đưa về được dạng này:
.u6473a9fe8a15dd544bfd68e2c537f097 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097:active, .u6473a9fe8a15dd544bfd68e2c537f097:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .u6473a9fe8a15dd544bfd68e2c537f097 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Que Hàn Tiếng Anh Là Gì ? Máy Hàn Tiếng Anh Là Gì ? Các ngôn từ Anh
(max f_0(mathbfx) Leftrightarrowmin -f_0(mathbfx) ).
(f_i(mathbfx) leq g(mathbfx) Leftrightarrow f_i(mathbfx) – g(mathbfx) leq 0).
(f_i(mathbfx) geq 0 Leftrightarrow -f_i(mathbfx) leq 0 ).
(a leq f_i(mathbfx) leq b Leftrightarrow f_i(mathbfx) -b leq 0) và (a – f_i(mathbfx) leq 0).
(f_i(mathbfx) leq 0 Leftrightarrow f_i(mathbfx) + s_i = 0 ) và (s_i geq 0). (s_i) được gọi là slack variable. Phép chuyển đổi đơn giản này trong nhiều trường hợp lại tỏ ra hiệu quả vì bất đẳng thức (s_i geq 0) thường dễ khắc phục hơn là (f_i(mathbfx) leq 0).
3. Bài toán tối ưu lồi
Trong toán tối ưu, chúng ta đặc trưng quan tâm tới những bài toán nhưng hàm mục tiêu là một hàm lồi, và feasible set cũng là một tập lồi.
3.1. Khái niệm
Một bài toán tối ưu lồi (convex optimization problem) là một bài toán tối ưu có dạng:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(16)&& mathbfa_j^Tmathbfx – b_j = 0, j = 1, dots,endeqnarray>trong đó (f_0, f_1, dots, f_m) là các hàm lồi.
So với bài toán tối ưu ((15)), bài toán tối ưu lồi ((16)) có thêm ba điều kiện nữa:
Hàm mục tiêu là một hàm lồi.
Các hàm bất đẳng thức ràng buộc (f_i) là các hàm lồi.
Hàm đẳng thức ràng buộc (h_j) là affine (hàm linear cùng với một hẳng số nữa được gọi là affine).
Một vài nhận xét:
Tập trung các điểm thoả nguyện (h_j(mathbfx) = 0) là một tập lồi vì nó có dạng một hyperplane.
Vậy, trong một bài toán tối ưu lồi, ta tối thiểu một hàm mục tiêu lồi trên một tập lồi.
3.2. Cực tiểu của bài toán tối ưu lồi chính là điểm tối ưu.
TÍnh chất quan trọng nhất của bài toán tối ưu lồi chính là bất kỳ locally optimal point chính là một điểm (globally) optimal point.
Tính chất quan trọng này khả năng chứng minh bằng phản chứng như sau. Gọi (mathbfx_0) là một điểm locally optimal, tức:
với (R > 0) nào đó. Giả sử (mathbfx_0) ko phải là globally optimal point, tức tồn tại một feasible point (mathbfy) sao cho (f(mathbfy) &leq& (1 – heta)f_0(mathbfx_0) + heta f_0(mathbfy) & &=& f_0(mathbfx_0)endeqnarray>
điều này tranh chấp với giả thiết (mathbfx_0) là một điểm cực tiểu. Vậy giả sử sai, tức (mathbfx_0) chính là globally optimal point và ta có điều phải chứng minh.
Chứng minh bằng lời: giả sử một điểm cực tiểu ko phải là điểm làm cho hàm số đạt tổng trị giá nhỏ nhất. Với điều kiện feasible set và hàm mục tiêu là lồi, ta luôn tìm được một điểm khác trong phụ cận của điểm cực tiểu đó sao cho tổng trị giá của hàm mục tiêu tại điểm mới này nhỏ hơn tổng trị giá của hàm mục tiêu tại điểm cực tiểu. Sự tranh chấp này chỉ ra rằng với một bài toán tối ưu lồi, điểm cực tiểu phải là điểm làm cho hàm số đạt tổng trị giá nhỏ nhất.
Xem thêm: Garment Là Gì – Tiếng Anh Chuyên Ngành May Mặc
3.3. Điều kiện tối ưu cho hàm mục tiêu khả vi
Nếu hàm mục tiêu (f_0) là khả vi (differentiable), theo first-order condition, với mọi (mathbfx, mathbfy in extdomf_0), ta có:
Đặt (mathcalX) là feasible set. Điều kiện cần và đủ để một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua việc chứng minh điều kiện cần và đủ này, độc giả khả năng tìm trong trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.
Phân mục: Hỏi Đáp
Các câu hỏi về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Team Asinana nhưng cụ thể là Ý Nhi đã biên soạn bài viết dựa trên tư liệu sẵn có và tri thức từ Internet. Đương nhiên tụi mình biết có nhiều câu hỏi và nội dung chưa thỏa mãn được buộc phải của các bạn.
Thế nhưng với ý thức tiếp thu và phát triển hơn, Mình luôn đón nhận tất cả các ý kiến khen chê từ các bạn & Quý đọc giả cho bài viêt Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Nếu có bắt kỳ câu hỏi thắc mắt nào vê Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính hãy cho chúng mình biết nha, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình phát triển hơn hơn trong các bài sau nha
Các Hình Ảnh Về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Các từ khóa tìm kiếm cho bài viết #Linear #Programming #Là #Gì #Linear #Programming #Quy #Hoạch #Tuyến #Tính
Xem thêm dữ liệu, về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính tại WikiPedia
Bạn hãy tìm thông tin cụ thể về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính từ web Wikipedia tiếng Việt.◄
Tham Gia Cộng Đồng Tại
💝 Nguồn Tin tại: https://thpttranhungdao.edu.vn
💝 Xem Thêm Câu Hỏi Quanh Ta tại : https://thpttranhungdao.edu.vn/la-gi/
[rule_{ruleNumber}]
[box type=”note” align=”” class=”” ez-toc-section” >1. Giới thiệu
Tôi xin bắt đầu bài viết này bằng ba bài toán khá gần với thực tế:
1.1. Bài toán nhà xuất bản
Bài toán
Một nhà xuấn bản (NXB) nhận được đơn hàng 600 bản của cuốn “Machine Learning cơ bản” tới Thái Bình và 400 bản tới Hải Phòng. NXB đó có 800 cuốn ở kho Nam Định và 700 cuốn ở kho Hải Dương. Giá chuyển phát một cuốn sách từ Nam Định tới Thái Bình là 50,000 VND (50k), tới Hải Phòng là 100k. Giá chuyển phát một cuốn từ Hải Dương tới Thái Bình là 150k, trong khi tới Hải Phòng chỉ là 40k. Hỏi để tốn ít chi phí chuyển phát nhất, công ty đó nên phân phối mỗi kho chuyển bao nhiêu cuốn tới mỗi địa điểm?
Phân tích
Để cho đơn giản, ta xây dựng bảng số lượng chuyển sách từ nguồn tới đích như sau:
Nam Định | Thái Bình | 5 | (x) |
Nam Định | Hải Phỏng | 10 | (y) |
Hải Dương | Thái Bình | 15 | (z) |
Hải Dương | Hải Phòng | 4 |
Tổng chi phí (objective function) sẽ là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Các điều kiện ràng buộc (constraints) viết dưới dạng biểu thức toán học là:
Chuyển 600 cuốn tới Thái Bình: (x + z = 600).
Chuyển 400 cuốn tới Hải Phòng: (y + t = 400).
Lấy từ kho Nam Định không quá 800: (x + y leq 800).
Lấy từ kho Hải Dương không quá 700: (z + t leq 700).
(x, y, z, t) là các số một cách tự nhiên. Ràng buộc là số một cách tự nhiên sẽ khiến cho bài toán rất khó giải nếu số lượng biến là rất lớn. Với bài toán này, ta giả sử rằng (x, y, z, t) là các số thực dương. Khi tìm được nghiệm, nếu chúng không phải là số một cách tự nhiên, ta sẽ lấy các tổng giá trị một cách tự nhiên gần nhất.
Vậy ta cần giải bài toán tối ưu sau đây:
Bài toán NXB:egineqnarray (x, y, z, t) =& argmin_x, y, z, t 5x + 10y + 15z + 4t ~~~~ (1) extsubject to:~ & x + z = 600 ~~~~ (2) & y + t = 400 ~~~~ (3) & x + y leq 800 ~~~(4) & z + t leq 700 ~~~ (5) & x, y, z, t geq 0 ~~~ (6)endeqnarray>
Nhận thấy rằng hàm mục tiêu (objective function) là một hàm tuyến tính của các biến (x, y, z, t). Các điều kiện ràng buộc đều có dạng hyperplanes hoặc haflspaces, đều là các ràng buộc tuyến tính (linear constraints). Bài toán tối ưu với cả objective function và constraints đều là linear được gọi là Linear Programming (LP). Dạng tổng quát và cách thức lập trình để giải một bài toán thuộc loại này sẽ được cho trong phần sau của bài viết này.
Nghiệm cho bài toán này khả năng nhận thấy ngay là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn và số biến nhiều hơn, chúng ta cần một lời giải khả năng tính được bằng cách lập trình.
1.2. Bài toán canh tác
Bài toán
Một anh nông dân có tổng cộng 10ha (10 hecta) đất canh tác. Anh dự tính trồng cà phê và hồ tiêu trên số đất này với tổng chi phí cho việc trồng này là không quá 16T (triệu đồng). Chi phí để trồng cà phê là 2T cho 1ha, để trồng hồ tiêu là 1T/ha/. Thời gian trồng cà phê là 1 ngày/ha và hồ tiêu là 4 ngày/ha; trong khi anh chỉ có thời gian tổng cộng là 32 ngày. Sau khi trừ tất cả các chi phí (bao gồm chi phí trồng cây), mỗi ha cà phê đem lại lợi nhuận 5T, mỗi ha hồ tiêu đem lại lợi nhuận 3T. Hỏi anh phải trồng như thế nào để tối đa lợi nhuận? (Các số liệu khả năng vô lý vì chúng đã được chọn để bài toán ra nghiệm đẹp)
Phân tích
.ub1fd97b28fe20cc50223b9c4e5119af8 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8:active, .ub1fd97b28fe20cc50223b9c4e5119af8:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ub1fd97b28fe20cc50223b9c4e5119af8 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ub1fd97b28fe20cc50223b9c4e5119af8 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ub1fd97b28fe20cc50223b9c4e5119af8:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Thúy Nga Music Box #22 | Mạnh Quỳnh & Hương Thủy | Gặp Lại Cố Nhân
Gọi (x) và (y) lần lượt là số ha cà phê và hồ tiêu mà anh nông dân nên trồng. Lợi nhuận anh ấy thu được là (f(x, y) = 5x + 3y) (triệu đồng).
Các ràng buộc trong bài toán này là:
Tổng diện tích trồng không vượt quá 10: (x + y leq 10).
Tổng chi phí trồng không vượt quá 16T: (2x + y leq 16).
Tổng thời gian trồng không vượt quá 32 ngày: (x + 4y leq 32).
Diện tích cà phê và hồ tiêu là các số không âm: (x, y geq 0).
Vậy ta có bài toán tối ưu sau đây:
Bài toán canh tác:egineqnarray (x, y) =& argmax_x, y 5x + 3y ~~~~ (7) extsubject to:~ & x + y leq 10 ~~~~ (8) & 2x + y leq 16 ~~~(9) & x + 4y leq 32 ~~~ (10) & x, y geq 0 ~~~ (11)endeqnarray>
Bài toán này hơi khác một chút là ta cần tối đa hàm mục tiêu thay vì tối thiểu nó. Việc chuyển bài toán này về bài toán tối thiểu khả năng được thực hiện đơn giản bằng cách đổi dấu hàm mục tiêu. Khi đó hàm mục tiêu vẫn là linear, các ràng buộc vẫn là các linear constraints, ta lại có một bài toán Linear Programming (LP) nữa.
Bạn cũng khả năng dựa vào hình minh hoạ dưới đây để suy ra nghiệm của bài toán:
Vùng màu xám có dạng polyhedron (trong trường hợp này là đa giác) chính là tập hợp các điểm thoả mãn các ràng buộc từ (8)) đến ((11)). Các đường nét đứt có màu chính là các đường đồng mức của hàm mục tiêu (5x + 3y), mỗi đường ứng với một tổng giá trị khác nhau với đường càng đỏ ứng với tổng giá trị càng cao. Một cách trực quan, nghiệm của bài toán khả năng tìm được bằng cách di chuyển đường nét đứt màu xanh về phía bên phải (phía làm cho tổng giá trị của hàm mục tiêu lớn hơn) đến khi nó không còn điểm chung với phần đa giác màu xám nữa.
khả năng nhận thấy nghiệm của bài toán chính là điểm màu xanh là giao điểm của hai đường thẳng (x + y = 10) và (2x + y = 16). Giải hệ phương trình này ta có (x^* = 6) và (y^* = 4). Tức anh nông dân nên trồng 6ha cà phê và 4ha hồ tiêu. Lúc đó lợi nhuận thu được là (5x^* + 3y^* = 42 ) triệu đồng, trong khi anh chỉ mất thời gian là 22 ngày. (Chịu tính toán cái là khác ngay, làm ít, hưởng nhiều).
Đây chính là phương pháp giải trong sách toán lớp 10 (ngày tôi học lớp 10).
Với nhiều biến hơn và nhiều ràng buộc hơn, chúng ta liệu khả năng vẽ được hình như thế này để nhìn ra nghiệm hay không? Câu trả lời của tôi là nên tìm một công cụ để với nhiều biến hơn và với các ràng buộc khác nhau, chúng ta khả năng tìm ra nghiệm gần như ngay lập tức.
1.3. Bài toán đóng thùng
Bài toán
Một công ty phải chuyển 400 (m^3) cát tới địa điểm xây dựng ở bên kia sông bằng cách thuê một chiếc xà lan. Ngoài chi phí vận chuyển một lượt đi về là 100k của chiếc xà lan, công ty đó phải thiết kế một thùng hình hộp chữ nhật đặt trên xà lan để đựng cát. Chiếc thùng này không cần nắp, chi phí cho các mặt xung quanh là 1T/(m^2), cho mặt đáy là 2T/(m^2). Hỏi kích thước của chiếc thùng đó như thế nào để tổng chi phí vận chuyển là nhỏ nhất. Để cho đơn giản, giả sử cát chỉ được đổ ngang hoặc thấp hơn với phần trên của thành thùng, không có ngọn. Giả sử thêm rằng xà lan rộng vô hạn và chứa được sức nặng vô hạn, giả sử này khiến bài toán dễ giải hơn.
Phân tích
Giả sử chiếc thùng cần làm có chiều dài là (x) ((m)), chiều rộng là (y) và chiều cao là (z). dung tích của thùng là (xyz) (đơn vị là (m^3)). Có hai loại chi phí là:
Chi phí thuê xà lan: số chuyến xà lan phải thuê là (frac400xyz) (ta hãy tạm giả sử rằng đây là một vài một cách tự nhiên, việc làm tròn này sẽ không thay đổi ngay kết quả một cách đáng kể vì chi phí vận chuyển một chuyến là nhỏ so với chi phí làm thùng). Số tiền phải trả cho xà lan sẽ là (0.1frac400xyz = frac40xyz).
Chi phí làm thùng: Diện tích xung quanh của thùng là (2 (x + y)z ). Diện tích đáy là (xy). Vậy tổng chi phí làm thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).
Tổng toàn bộ chi phí là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều kiện ràng buộc duy nhất là kích thước thùng phải là các số dương. Vậy ta có bài toán tối ưu sau:
Bài toán vận chuyển:egineqnarray (x, y) =& argmin_x, y, z 40x^-1y^-1z^-1 + 2(xy + yz + zx) ~~~~ (13) extsubject to:~ & x, y, z > 0 ~~~~ (14)endeqnarray>
Bài toán này thuộc loại Geometric Programming (GP). Định nghĩa của GP và cách dùng công cụ tối ưu sẽ được trình bày trong phần sau của bài viết.
.ue61bcfe3ef9416e82ce9b90fc2ab49fa { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:active, .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .ue61bcfe3ef9416e82ce9b90fc2ab49fa:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Chả cá trôi siêu ngon dễ làm – Best Grilled chopped rohu fish ever made
Xem thêm: Endocytosis Là Gì – Endocytosis, Phagocytosis, And Pinocytosis Video
Nhận thấy rằng bài này hoàn toàn khả năng dùng bất đẳng thức Cauchy để giải được, nhưng tôi vẫn muốn một lời giải cho bài toán tổng quát sao cho khả năng lập trình được.
(Lời giải:egineqnarray f(x, y, z) &=& frac20xyz + frac20xyz + 2xy + 2yz + 2zx &geq & 5sqrt3200endeqnarray>dấu bằng xảy ra khi và chỉ khi (x = y = z = sqrt10). Bài này có lẽ hợp với các kỳ thi vì dữ kiện quá đẹp. Cá nhân tôi thích các đề bài ra kiểu này hơn là bắt buộc đi tìm tổng giá trị nhỏ nhất của một biểu thức nhàm chán, nhiều học sinh cho rằng không biết học bất đẳng thức để làm gì!)
Nếu có các ràng buộc về kích thước của thùng và trọng lượng mà xà lan tải được thì khả năng tìm được lời giải đơn giản như thế này không?
Những bài toán trên đây đều là các bài toán tối ưu. Chính xác hơn nữa, chúng đều là các bài toán tối ưu lồi (convex optimization problems) như các bạn sẽ thấy ở phần sau. Và việc tìm lời giải khả năng không mấy điều kiện, thậm chí giải bằng tay cũng khả năng ra kết quả. mặc khác, mục đích của bài viết này không phải là hướng dẫn các bạn giải các bài toán trên bằng tay, mà là phương pháp nhận diện các bài toán và đưa chúng về các dạng mà các toolboxes sẵn có khả năng giúp chúng ta. Trên thực tế, lượng dữ kiện và số biến cần tối ưu lớn hơn nhiều, chúng ta không thể giải các bài toán trên bằng tay được.
Trước hết, chúng ta cần hiểu các khái niệm về convex optimization problems và tại sao convex lại quan trọng. (Bạn đọc khả năng đọc tới phần 4 nếu không muốn biết các khái niệm và định lý toán trong phần 2 và 3.)
2. Nhắc lại bài toán tối ưu
2.1. Các khái niệm cơ bản
Tôi xin nhắc lại bài toán tối ưu ở dạng tổng quát:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(15)&& h_j(mathbfx) = 0, ~~ j = 1, 2, dots, pendeqnarray>
Phát biểu bằng lời: Tìm tổng giá trị của biến (mathbfx) để tối thiểu hàm (f_0(mathbfx)) trong số các tổng giá trị của (mathbfx) thoả mãn các điệu hiện ràng buộc. Ta có bảng các tên gọi tiếng Anh và tiếng Việt như sau:
(mathbfx in mathbbR^n) | optimization variable | biến tối ưu |
(f_0: mathbbR^n ightarrow mathbbR) | objective/los/cost function | hàm mục tiêu |
(f_i(mathbfx) leq 0 ) | inequality constraints | bất đẳng thức ràng buộc |
(f_i: mathbbR^n ightarrow mathbbR) | inequality constraint functions | – |
(h_j(mathbfx) = 0 ) | equality constraints | đẳng thức ràng buộc |
(h_j: mathbbR^n ightarrow mathbbR) | equality constraint functions | – |
(mathcalD = igcap_i=0^m extdomf_i cap igcap_pj=1^p extdomh_i ) | domain | tập xác định |
mặt khác:
Khi (m = p = 0), bài toán ((15)) được gọi là unconstrained optimization problem (bài toán tối ưu không ràng buộc).
(mathcalD) chỉ là tập xác định, tức giao của tất cả các tập xác định của mọi hàm số xuất hiện trong bài toán. Tập hợp các điểm thoả mãn mọi điều kiện ràng buộc, thông thường, là một tập con của (mathcalD) được gọi là feasible set hoặc constraint set. Khi feasible set là một tập rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta gọi điểm đó là feasible.
2.2. Optimal and locally optimal points
Một điểm (mathbfx^*) được gọi là một điểm optimal point (điểm tối ưu), hoặc là nghiệm của bài toán ((15)) nếu (mathbfx^*) là feasible và (f_0(mathbfx^*) = p^*). Tất hợp tất cả các optimal points được gọi là optimal set.
Nếu optimal set là một tập không rỗng, ta nói bài toán ((15)) là solvable (giải được). Ngược lại, nếu optimal set là một tập rỗng, ta nói optimal value là không thể đạt được (not attained/ not achieved).
Ví dụ: xét hàm mục tiêu (f(x) = 1/x) với ràng buộc (x > 0). Optimal value của bài toán này là (p^* = 0) nhưng optimal set là một tập rỗng vì không có tổng giá trị nào của (x) để hàm mục tiêu đạt tổng giá trị 0. Lúc này ta nói tổng giá trị tối ưu là không đạt được.
Với hàm một biến, một điểm là cực tiểu của một hàm số nếu tại đó, hàm số đạt tổng giá trị nhỏ nhất trong một lân cận (và lân cận này thuộc tập xác định của hàm số). Trong không gian 1 chiều, lân cận được hiểu là trị tuyệt tối của hiệu 2 điểm nhỏ hơn một tổng giá trị nào đó.
Trong toán tối ưu (thường là không gian nhiều chiều), ta gọi một điểm (mathbfx) là locally optimal (cực tiểu) nếu tồn tại một tổng giá trị (thường được gọi là bán kinh) (R) sao cho:egineqnarray f_0(mathbfx) = & extinf f_i(mathbfz) leq 0, i = 1, dots, m, & h_j(mathbfz) = 0, j = 1, dots, p, endeqnarray>
Nếu một điểm feasible (mathbfx) thoả mãn (f_i(mathbfx) = 0), ta nói rằng bất đẳng thức ràng buộc thứ (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)
2.3. Một vài lưu ý
Mặc dù trong định nghĩa bài toán tối ưu ((15)) là cho bài toán tối thiểu hàm mục tiêu với các ràng buộc thoả mãn các điều kiện nhỏ hơn hoặc bằng 0, các bài toán tối ưu với tối đa hàm mục tiêu và điều kiện ràng buộc ở dạng khác đều khả năng đưa về được dạng này:
.u6473a9fe8a15dd544bfd68e2c537f097 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#eaeaea; border:0!important; border-left:4px solid #2980B9!important; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097:active, .u6473a9fe8a15dd544bfd68e2c537f097:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .u6473a9fe8a15dd544bfd68e2c537f097 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .u6473a9fe8a15dd544bfd68e2c537f097 .ctaText { font-weight:bold; color:inherit; text-decoration:none; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097 .postTitle { color:#27AE60; text-decoration: underline!important; font-size: 16px; } .u6473a9fe8a15dd544bfd68e2c537f097:hover .postTitle { text-decoration: underline!important; } Nhiều Bạn Cũng Xem Que Hàn Tiếng Anh Là Gì ? Máy Hàn Tiếng Anh Là Gì ? Các ngôn từ Anh
(max f_0(mathbfx) Leftrightarrowmin -f_0(mathbfx) ).
(f_i(mathbfx) leq g(mathbfx) Leftrightarrow f_i(mathbfx) – g(mathbfx) leq 0).
(f_i(mathbfx) geq 0 Leftrightarrow -f_i(mathbfx) leq 0 ).
(a leq f_i(mathbfx) leq b Leftrightarrow f_i(mathbfx) -b leq 0) và (a – f_i(mathbfx) leq 0).
(f_i(mathbfx) leq 0 Leftrightarrow f_i(mathbfx) + s_i = 0 ) và (s_i geq 0). (s_i) được gọi là slack variable. Phép biến đổi đơn giản này trong nhiều trường hợp lại tỏ ra hiệu quả vì bất đẳng thức (s_i geq 0) thường dễ giải quyết hơn là (f_i(mathbfx) leq 0).
3. Bài toán tối ưu lồi
Trong toán tối ưu, chúng ta đặc biệt quan tâm tới những bài toán mà hàm mục tiêu là một hàm lồi, và feasible set cũng là một tập lồi.
3.1. Định nghĩa
Một bài toán tối ưu lồi (convex optimization problem) là một bài toán tối ưu có dạng:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(16)&& mathbfa_j^Tmathbfx – b_j = 0, j = 1, dots,endeqnarray>trong đó (f_0, f_1, dots, f_m) là các hàm lồi.
So với bài toán tối ưu ((15)), bài toán tối ưu lồi ((16)) có thêm ba điều kiện nữa:
Hàm mục tiêu là một hàm lồi.
Các hàm bất đẳng thức ràng buộc (f_i) là các hàm lồi.
Hàm đẳng thức ràng buộc (h_j) là affine (hàm linear cộng với một hẳng số nữa được gọi là affine).
Một vài nhận xét:
Tập hợp các điểm thoả mãn (h_j(mathbfx) = 0) là một tập lồi vì nó có dạng một hyperplane.
Vậy, trong một bài toán tối ưu lồi, ta tối thiểu một hàm mục tiêu lồi trên một tập lồi.
3.2. Cực tiểu của bài toán tối ưu lồi chính là điểm tối ưu.
TÍnh chất quan trọng nhất của bài toán tối ưu lồi chính là bất kỳ locally optimal point chính là một điểm (globally) optimal point.
Tính chất quan trọng này khả năng chứng minh bằng phản chứng như sau. Gọi (mathbfx_0) là một điểm locally optimal, tức:
với (R > 0) nào đó. Giả sử (mathbfx_0) không phải là globally optimal point, tức tồn tại một feasible point (mathbfy) sao cho (f(mathbfy) &leq& (1 – heta)f_0(mathbfx_0) + heta f_0(mathbfy) & &=& f_0(mathbfx_0)endeqnarray>
điều này mâu thuẫn với giả thiết (mathbfx_0) là một điểm cực tiểu. Vậy giả sử sai, tức (mathbfx_0) chính là globally optimal point và ta có điều phải chứng minh.
Chứng minh bằng lời: giả sử một điểm cực tiểu không phải là điểm làm cho hàm số đạt tổng giá trị nhỏ nhất. Với điều kiện feasible set và hàm mục tiêu là lồi, ta luôn tìm được một điểm khác trong lân cận của điểm cực tiểu đó sao cho tổng giá trị của hàm mục tiêu tại điểm mới này nhỏ hơn tổng giá trị của hàm mục tiêu tại điểm cực tiểu. Sự mâu thuẫn này chỉ ra rằng với một bài toán tối ưu lồi, điểm cực tiểu phải là điểm làm cho hàm số đạt tổng giá trị nhỏ nhất.
Xem thêm: Garment Là Gì – Tiếng Anh Chuyên Ngành May Mặc
3.3. Điều kiện tối ưu cho hàm mục tiêu khả vi
Nếu hàm mục tiêu (f_0) là khả vi (differentiable), theo first-order condition, với mọi (mathbfx, mathbfy in extdomf_0), ta có:
Đặt (mathcalX) là feasible set. Điều kiện cần và đủ để một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua việc chứng minh điều kiện cần và đủ này, bạn đọc khả năng tìm trong trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.
Chuyên mục: Hỏi Đáp
Các câu hỏi về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Team Asinana mà chi tiết là Ý Nhi đã biên soạn bài viết dựa trên tư liệu sẵn có và kiến thức từ Internet. Dĩ nhiên tụi mình biết có nhiều câu hỏi và nội dung chưa thỏa mãn được bắt buộc của các bạn.
Thế nhưng với tinh thần tiếp thu và nâng cao hơn, Mình luôn đón nhận tất cả các ý kiến khen chê từ các bạn & Quý đọc giả cho bài viêt Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Nếu có bắt kỳ câu hỏi thắc mắt nào vê Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính hãy cho chúng mình biết nha, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình nâng cao hơn hơn trong các bài sau nha
Các Hình Ảnh Về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính
Các từ khóa tìm kiếm cho bài viết #Linear #Programming #Là #Gì #Linear #Programming #Quy #Hoạch #Tuyến #Tính
Xem thêm dữ liệu, về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính tại WikiPedia
Bạn hãy tìm thông tin chi tiết về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính từ web Wikipedia tiếng Việt.◄
Tham Gia Cộng Đồng Tại
💝 Nguồn Tin tại: https://thpttranhungdao.edu.vn
💝 Xem Thêm Câu Hỏi Quanh Ta tại : https://thpttranhungdao.edu.vn/la-gi/
[/box]
#Linear #Programming #Là #Gì #Linear #Programming #Quy #Hoạch #Tuyến #Tính
[/toggle]
Bạn thấy bài viết Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính có khắc phục đươc vấn đề bạn tìm hiểu ko?, nếu ko hãy comment góp ý thêm về Linear Programming Là Gì, Linear Programming / Quy Hoạch Tuyến Tính bên dưới để thpttranhungdao.edu.vn có thể thay đổi & cải thiện nội dung tốt hơn cho độc giả nhé! Cám ơn bạn đã ghé thăm Website Trường THPT Trần Hưng Đạo
Phân mục: Là gì?
#Linear #Programming #Là #Gì #Linear #Programming #Quy #Hoạch #Tuyến #Tính
Trả lời