quý khách hàng được khuyến nghị đọc Bài 16 trước khi phát âm bài xích này. Nội dung trong nội dung bài viết này đa phần được dịch từ bỏ Chương thơm 4 của cuốn Convex Optimization trong phần Tài liệu tham khảo.Quý Khách đã xem: Linear programming là gì.
Bạn đang xem: Linear programming là gì
Bài này cũng có không ít quan niệm new với các lý thuyết đề xuất có thể không cuốn hút nlỗi các bài khác. Tuy nhiên, tôi quan yếu bỏ qua mất do không thích các bạn trọn vẹn mất phương hướng Lúc đọc những bài sau.
Bạn hiểu rất có thể xem bạn dạng pdf trên trên đây.
1. Giới thiệu
Tôi xin bước đầu bài viết này bởi bố bài bác toán khá gần cùng với thực tế:
1.1. Bài toán thù nhà xuất bản
Bài toánMột công ty xuấn bạn dạng (NXB) nhận được deals 600 bản của cuốn nắn “Machine Learning cơ bản” tới Thái Bình với 400 bạn dạng tới Hải Phòng Đất Cảng. NXB đó tất cả 800 cuốn ngơi nghỉ kho Tỉnh Nam Định và 700 cuốn nắn sinh hoạt kho Thành Phố Hải Dương. Giá đưa phân phát một cuốn nắn sách trường đoản cú Tỉnh Nam Định cho tới Tỉnh Thái Bình là 50,000 VND (50k), cho tới Hải Phòng là 100k. Giá chuyển vạc một cuốn nắn từ bỏ Thành Phố Hải Dương cho tới Thái Bình là 150k, trong khi tới Hải Phòng chỉ với 40k. Hỏi nhằm tốn ít ngân sách chuyển phân phát tuyệt nhất, chủ thể kia đề xuất phân phối mỗi kho chuyển từng nào cuốn cho tới từng địa điểm?
Phân tíchĐể mang lại đơn giản và dễ dàng, ta xuất bản bảng số lượng chuyển sách từ mối cung cấp cho tới đích nlỗi 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) |
Tổng chi phí (objective sầu function) đã là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Các điều kiện buộc ràng (constraints) viết bên dưới dạng biểu thức tân oán học là:
Chuyển 600 cuốn cho tới Thái Bình: (x + z = 600).
Chuyển 400 cuốn cho tới Hải Phòng: (y + t = 400).
Lấy trường đoản cú kho Nam Định không thật 800: (x + y leq 800).
Lấy từ bỏ kho Thành Phố Hải Dương không thật 700: (z + t leq 700).
(x, y, z, t) là những số tự nhiên và thoải mái. Ràng buộc là số tự nhiên và thoải mái đã để cho bài tân oán siêu khó khăn giải trường hợp con số biến hóa là không nhỏ. Với bài xích tân oá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 như bọn chúng chưa hẳn là số thoải mái và tự nhiên, ta vẫn rước các cực hiếm thoải mái và tự nhiên sớm nhất.
Vậy ta nên giải bài bác toán buổi tối ưu sau đây:
Bài toán thù NXB:
Nhận thấy rằng hàm kim chỉ nam (objective sầu function) là một trong những hàm đường tính của những phát triển thành (x, y, z, t). Các ĐK buộc ràng đều phải sở hữu dạng hyperplanes hoặc haflspaces, đa số là những ràng buộc tuyến tính (linear constraints). Bài tân oán về tối ưu với tất cả objective sầu function cùng constraints phần đông là linear được hotline là Linear Programming (LP). Dạng tổng quát và cách thức lập trình sẵn nhằm giải một bài bác toán trực thuộc loại này sẽ được đến trong phần sau của nội dung bài viết này.
Nghiệm mang lại bài bác tân oán này có thể nhận thấy ngay là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn thế nữa với số biến đổi nhiều hơn, chúng ta bắt buộc một lời giải hoàn toàn có thể tính được bằng phương pháp lập trình sẵn.
1.2. Bài toán thù canh tác
Bài toánMột anh nông dân bao gồm tổng cộng 10ha (10 hecta) đất canh tác. Anh dự tính tLong coffe cùng hồ nước tiêu trên số khu đất này cùng với tổng ngân sách mang lại câu hỏi tdragon này là không thật 16T (triệu đồng). giá thành để tLong coffe là 2T cho 1ha, nhằm trồng hồ nước tiêu là 1T/ha/. Thời gian trồng cafe là 1 ngày/ha và hồ nước tiêu là 4 ngày/ha; trong lúc anh chỉ bao gồm thời hạn tổng cộng là 32 ngày. Sau Lúc trừ tất cả những chi phí (bao hàm ngân sách tdragon cây), mỗi ha coffe mang lại lợi nhuận 5T, từng ha hồ nước tiêu đem về lợi tức đầu tư 3T. Hỏi anh cần tLong như thế nào để buổi tối nhiều lợi nhuận? (Các số liệu rất có thể vô lý vì chưng bọn chúng đã có được lựa chọn nhằm bài xích toán thù ra nghiệm đẹp)
Phân tíchhotline (x) và (y) thứu tự là số ha coffe với hồ nước tiêu cơ mà anh dân cày phải tLong. Lợi nhuận anh ấy nhận được là (f(x, y) = 5x + 3y) (triệu đồng).
Các ràng buộc trong bài bác tân oán này là:
Tổng diện tích tdragon ko vượt quá 10: (x + y leq 10).
Tổng chi phí tdragon không vượt thừa 16T: (2x + y leq 16).
Tổng thời hạn tdragon không quá vượt 32 ngày: (x + 4y leq 32).
Diện tích cafe và hồ nước tiêu là các số không âm: (x, y geq 0).
Vậy ta tất cả bài bác toán về tối ưu sau đây:
Bài tân oán canh tác:
Bài toán này tương đối khác một ít là ta nên buổi tối nhiều hàm mục tiêu chũm vì tối tgọi nó. Việc gửi bài bác tân oán này về bài tân oán buổi tối thiểu có thể được tiến hành dễ dàng bằng cách đổi vết hàm mục tiêu. khi kia hàm kim chỉ nam vẫn luôn là linear, những buộc ràng vẫn luôn là các linear constraints, ta lại có một bài xích tân oán Linear Programming (LP) nữa.
quý khách hàng cũng hoàn toàn có thể nhờ vào hình minh hoạ dưới đây nhằm suy ra nghiệm của bài xích toán:
Vùng màu xám tất cả dạng polyhedron (vào ngôi trường đúng theo này là nhiều giác) chính là tập đúng theo các điểm thoả nguyện những ràng buộc từ bỏ (8)) mang đến ((11)). Các đường đường nét đứt tất cả màu sắc đó là các con đường đồng nút của hàm kim chỉ nam (5x + 3y), từng con đường ứng với một cực hiếm không giống nhau với con đường càng đỏ ứng với cái giá trị càng tốt. Một giải pháp trực quan, nghiệm của bài bác toán thù có thể tìm kiếm được bằng cách dịch rời con đường nét đứt màu xanh về phía bên phải (phía tạo nên quý hiếm của hàm kim chỉ nam phệ hơn) đến khi nó không còn điểm chung với phần đông giác color xám nữa.
Có thể nhận thấy nghiệm của bài bác toán đó là điểm greed color là giao điểm của hai tuyến đường trực tiếp (x + y = 10) và (2x + y = 16). Giải hệ pmùi hương trình này ta tất cả (x^* = 6) và (y^* = 4). Tức anh dân cày bắt buộc tLong 6ha cà phê với 4ha hồ nước tiêu. Lúc đó lợi tức đầu tư nhận được là (5x^* + 3y^* = 42 ) triệu đ, trong những khi anh chỉ mất thời hạn là 22 ngày. (chịu đựng tính toán chiếc là khác tức thì, làm ít, hưởng trọn nhiều).
Đây chính là bí quyết giải vào sách toán lớp 10 (ngày tôi học lớp 10).
Với nhiều đổi thay hơn với nhiều buộc ràng hơn, chúng ta liệu rất có thể vẽ được hình như thế này để nhìn ra nghiệm hay không? Câu trả lời của tớ là nên tra cứu một phương pháp nhằm với tương đối nhiều biến hơn với với các ràng buộc khác nhau, bạn có thể tìm thấy nghiệm gần như là ngay mau chóng.
1.3. Bài toán thù đóng thùng
Bài toánMột công ty cần chuyển 400 (m^3) mèo cho tới địa điểm xây dựng làm việc vị trí kia sông bằng phương pháp thuê một dòng xà lan. Ngoài ngân sách vận chuyển một lượt trở về là 100k của loại xà lan, cửa hàng đó phải xây dựng một thùng hình vỏ hộp chữ nhật để lên xà lan nhằm đựng mèo. Chiếc thùng này không yêu cầu nắp, chi phí cho các phương diện bao phủ là 1T/(m^2), đến mặt dưới là 2T/(m^2). Hỏi form size của chiếc thùng kia như thế nào để tổng chi phí đi lại là nhỏ dại độc nhất. Để mang lại đơn giản và dễ dàng, đưa sử cat chỉ được đổ ngang hoặc phải chăng hơn cùng với phần bên trên của thành thùng, không có ngọn gàng. Giả sử thêm rằng xà lan rộng lớn vô hạn và chứa được sức nặng trĩu vô hạn, giả sử này khiến cho bài bác toán thù dễ giải rộng.
Phân tíchGiả sử chiếc thùng nên làm cho tất cả chiều lâu năm là (x) ((m)), chiều rộng là (y) cùng độ cao là (z). Thể tích của thùng là (xyz) (đơn vị là (m^3)). Có nhị nhiều loại ngân sách là:
túi tiền mướn xà lan: số chuyến xà lan cần thuê là (frac400xyz) (ta hãy tạm bợ trả sử rằng đấy là một trong những thoải mái và tự nhiên, việc làm cho tròn này sẽ không chuyển đổi hiệu quả đáng kể vì chi phí vận động một chuyến là nhỏ so với chi phí làm cho thùng). Số tiền nên trả mang lại xà lan đã là (0.1frac400xyz = frac40xyz).
túi tiền làm thùng: Diện tích bao bọc của thùng là (2 (x + y)z ). Diện tích đáy là (xy). Vậy tổng ngân sách có tác dụng thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).
Tổng toàn cục ngân sách là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều kiện ràng buộc tuyệt nhất là kích thước thùng phải là các số dương. Vậy ta bao gồm bài toán thù về tối ưu sau:
Bài toán vận chuyển: 0 ~~~~ (14)endeqnarray>
Nhận thấy rằng bài xích này hoàn toàn rất có thể cần sử dụng bất đẳng thức Cauchy nhằm giải được, cơ mà tôi vẫn ước ao một giải thuật mang đến bài tân oán bao quát sao cho rất có thể lập trình được. Xem thêm: Sinhvienit Adobe Illustrator Cs6 Full Crack, Illustrator Cs6 Portable X64
(Lời giải:3200endeqnarray>vết bằng xảy ra Lúc còn chỉ lúc (x = y = z = sqrt10). Bài này chắc rằng phù hợp với các kỳ thi do dữ kiện vượt rất đẹp. Cá nhân tôi mê thích các đề bài ra đẳng cấp này hơn là đề nghị đi kiếm quý hiếm nhỏ nhất của một biểu thức chán nản, nhiều học sinh cho rằng trù trừ học bất đẳng thức để làm gì!)
Nếu gồm những ràng buộc về form size của thùng với trọng lượng nhưng mà xà lan cài được thì có thể kiếm được lời giải dễ dàng và đơn giản như thế này không?
Những bài toán trên phía trên các là những bài bác toán tối ưu. Chính xác không chỉ có thế, bọn chúng đều là các bài bác tân oán về tối ưu lồi (convex optimization problems) như những các bạn sẽ thấy tại phần sau. Và việc đào bới tìm kiếm giải mã rất có thể không mấy khó khăn, thậm chí giải thủ công bằng tay cũng hoàn toàn có thể ra tác dụng. Tuy nhiên, mục đích của bài viết này chưa hẳn là hướng dẫn chúng ta giải những bài xích tân oán trên bằng tay, mà lại là biện pháp nhấn diện những bài bác tân oán và chuyển bọn chúng về những dạng mà lại những toolboxes sẵn gồm có thể giúp họ. Trên thực tiễn, lượng dữ kiện với số đổi mới bắt buộc tối ưu to hơn các, chúng ta bắt buộc giải những bài xích toán thù trên bởi tay được.
Trước hết, bọn họ bắt buộc hiểu những quan niệm về convex optimization problems và tại vì sao convex lại đặc trưng. (Quý khách hàng gọi hoàn toàn có thể gọi tới phần 4 nếu như không hy vọng biết những khái niệm với định lý toán thù trong phần 2 với 3.)
2. Nhắc lại bài bác toán về tối ưu
2.1. Các định nghĩa cơ bản
Tôi xin nói lại bài xích toán về tối ưu nghỉ ngơi dạng tổng quát:
Phát biểu bởi lời: Tìm quý giá của trở nên (mathbfx) nhằm tối tgọi hàm (f_0(mathbfx)) trong những các quý giá của (mathbfx) đồng tình những điệu hiện tại ràng buộc. Ta tất cả bảng các tên thường gọi tiếng Anh cùng giờ Việt nhỏng sau:
| (mathbfx in mathbbR^n) | optimization variable | biến đổi tối ưu |
| (f_0: mathbbR^n ightarrow mathbbR) | objective/los/cost function | hàm mục tiêu |
| (f_i(mathbfx) leq 0 ) | inechất lượng constraints | bất đẳng thức ràng buộc |
| (f_i: mathbbR^n ightarrow mathbbR) | ineunique 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 |
Ngoài ra:
lúc (m = p = 0), bài bác tân oán ((15)) được Điện thoại tư vấn là unconstrained optimization problem (bài toán thù buổi tối ưu không ràng buộc).
(mathcalD) chỉ cần tập khẳng định, tức giao của toàn bộ các tập xác định của số đông hàm số lộ diện trong bài xích tân oán. Tập hợp các điểm mãn nguyện các điều kiện buộc ràng, thông thường, là 1 trong những tập con của (mathcalD) được điện thoại tư vấn là feasible set hoặc constraint set. lúc feasible set là một tập rỗng thì ta nói bài bác toán thù buổi tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta Điện thoại tư vấn đặc điểm đó là feasible.
2.2. Optimal & locally optimal points
Một điểm (mathbfx^*) được Hotline là 1 điểm optimal point (điểm tối ưu), hoặc là nghiệm của bài bác tân oán ((15)) nếu như (mathbfx^*) là feasible với (f_0(mathbfx^*) = p^*). Tất thích hợp tất cả các optimal points được call là optimal set.
Nếu optimal set là một trong tập không trống rỗng, ta nói bài toán ((15)) là solvable (giải được). trái lại, giả dụ optimal set là một tập trống rỗng, ta nói optimal value là thiết yếu đạt được (not attained/ not achieved).
Ví dụ: xét hàm kim chỉ nam (f(x) = 1/x) với ràng buộc (x > 0). Optimal value của bài tân oán này là (p^* = 0) tuy nhiên optimal set là 1 tập rỗng bởi vì không tồn tại quý hiếm như thế nào của (x) để hàm mục tiêu đạt giá trị 0. Trong thời điểm này ta nói quý hiếm về tối ưu là ko đạt được.
Với hàm một đổi mới, một điểm là rất tiểu của một hàm số nếu như tại đó, hàm số đạt giá trị bé dại tốt nhất trong một kề bên (với ở bên cạnh này nằm trong tập xác minh của hàm số). Trong không gian 1 chiều, lấn cận được phát âm là trị tuyệt tối của hiệu 2 điểm nhỏ tuổi hơn một giá trị như thế nào kia.
Trong toán thù về tối ưu (thường xuyên là không gian những chiều), ta điện thoại tư vấn một điểm (mathbfx) là locally optimal (cực tiểu) trường hợp vĩnh cửu một cực hiếm (hay được điện thoại tư vấn là buôn bán kinh) (R) sao cho:
Nếu một điểm feasible (mathbfx) vừa ý (f_i(mathbfx) = 0), ta nói rằng bất đẳng thức buộc ràng sản phẩm công nghệ (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)
2.3. Một vài giữ ý
Mặc cho dù trong có mang bài xích tân oán buổi tối ưu ((15)) là mang lại bài bác tân oán về tối tgọi hàm mục tiêu cùng với những buộc ràng vừa lòng các ĐK nhỏ dại rộng hoặc bởi 0, các bài bác tân oán buổi tối ưu với buổi tối nhiều hàm mục tiêu cùng ĐK buộc ràng sinh hoạt dạng khác rất nhiều rất có thể đem về được dạng này:
(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ới (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 Điện thoại tư vấn là slaông chồng variable. Phxay thay đổi dễ dàng này trong không ít trường hợp lại trầm trồ công dụng vày bất đẳng thức (s_i geq 0) thường rất dễ giải quyết và xử lý rộng là (f_i(mathbfx) leq 0).
3. Bài toán thù về tối ưu lồi
Trong tân oán tối ưu, bọn họ đặc biệt quan trọng quyên tâm tới phần đông bài toán thù mà hàm mục tiêu là 1 trong hàm lồi, và feasible set cũng là 1 tập lồi.
3.1. Định nghĩa
Một bài xích tân oán tối ưu lồi (convex optimization problem) là 1 bài xích toán thù buổi tối ưu bao gồm dạng:trong những số ấy (f_0, f_1, dots, f_m) là những hàm lồi.
So cùng với bài tân oán về tối ưu ((15)), bài toán tối ưu lồi ((16)) tất cả thêm cha điều kiện nữa:
Hàm mục tiêu là 1 hàm lồi.
Các hàm bất đẳng thức ràng buộc (f_i) là những 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 Điện thoại tư vấn là affine).
Một vài ba nhận xét:
Tập hòa hợp những điểm thoả nguyện (h_j(mathbfx) = 0) là một trong những tập lồi vị nó gồm dạng một hyperplane.
Vậy, trong một bài xích toán tối ưu lồi, ta tối tgọi một hàm phương châm lồi bên trên một tập lồi.
3.2. Cực đái của bài toán thù buổi tối ưu lồi chính là điểm buổi tối ưu.
TÍnh chất quan trọng nhất của bài bác tân oán về tối ưu lồi đó là bất kỳ locally optimal point đó là một điểm (globally) optimal point.
Tính chất quan trọng này rất có thể minh chứng bằng phản bội triệu chứng nhỏng sau. Gọi (mathbfx_0) là một điểm locally optimal, tức:
với (R > 0) làm sao đó. Giả sử (mathbfx_0) không phải là globally optimal point, tức tồn tại một feasible point (mathbfy) làm sao cho (f(mathbfy) &leqvà (1 - heta)f_0(mathbfx_0) + heta f_0(mathbfy) & &=và f_0(mathbfx_0)endeqnarray>
điều này xích míc cùng với đưa thiết (mathbfx_0) là 1 trong điểm rất tè. Vậy đưa sử sai, tức (mathbfx_0) chính là globally optimal point cùng ta bao gồm điều yêu cầu chứng tỏ.
3.3. Điều khiếu nại tối ưu cho hàm mục tiêu khả vi
Nếu hàm kim chỉ nam (f_0) là khả vi (differentiable), theo first-order condition, với tất cả (mathbfx, mathbfy in extdomf_0), ta có:
Đặt (mathcalX) là feasible set. Điều khiếu nại phải và đủ nhằm một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua Việc minh chứng ĐK bắt buộc cùng đủ này, bạn đọc hoàn toàn có thể kiếm tìm trong trang 139-140 của cuốn nắn Convex Optimization trong Tài liệu xem thêm.
