1. Giới thiệu 1.1. Bài tân oán bên xuất phiên bản 1.2. Bài toán thù canh tác 1.3. Bài toán thù đóng thùng 2. Nhắc lại bài xích tân oán về tối ưu 3. Bài tân oán tối ưu lồi 4. Linear Programming 5. Quadratic Programming 6. Geometric Programming

quý khách được khuyến nghị hiểu Bài 16 trước khi phát âm bài này. Nội dung trong nội dung bài viết này đa phần được dịch trường đoản cú Chương thơm 4 của cuốn Convex Optimization trong phần Tài liệu tham khảo.quý khách vẫn xem: Linear programming là gì.

Bạn đang xem: Linear programming là gì

Bài này cũng có nhiều quan niệm bắt đầu cùng những định hướng bắt buộc rất có thể ko hấp dẫn nhỏng những bài bác khác. Tuy nhiên, tôi cần yếu bỏ qua mất vị không thích các bạn trọn vẹn mất phương thơm hướng Khi phát âm những bài sau.

Quý khách hàng đọc rất có thể coi bạn dạng pdf tại phía trên.

1. Giới thiệu

Tôi xin ban đầu nội dung bài viết này bởi cha bài toán thù khá gần cùng với thực tế:

1.1. Bài toán thù bên xuất bản

Bài toán

Một nhà xuấn bản (NXB) nhận được đơn hàng 600 phiên bản của cuốn nắn “Machine Learning cơ bản” cho tới Tỉnh Thái Bình và 400 phiên bản tới TP Hải Phòng. NXB đó tất cả 800 cuốn nắn sinh sống kho Nam Định với 700 cuốn nắn sinh sống kho Hải Dương. Giá chuyển phâ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 TP.. Hải Phòng là 100k. Giá đưa phân phát một cuốn nắn tự Hải Dương cho tới Tỉnh Thái Bình là 150k, trong lúc đến TP Hải Phòng chỉ nên 40k. Hỏi để tốn không nhiều ngân sách đưa phát duy nhất, chủ thể kia cần phân phối mỗi kho gửi từng nào cuốn nắn cho tới mỗi địa điểm?

Phân tích

Để mang lại dễ dàng, ta xây dừng bảng con số gửi sách tự mối cung cấp tới đích nlỗi sau:

Nguồn Đích Đơn giá bán ((imes)10k) Số lượng
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) đang là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Các ĐK 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 nắn 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 từ kho Nam Định không thật 800: (x + y leq 800).

Lấy từ bỏ kho Hải Dương không thực sự 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ố thoải mái và tự nhiên đã để cho bài toán thù siêu nặng nề giải giả dụ con số biến chuyển là rất lớn. Với bài bác toán thù này, ta trả sử rằng (x, y, z, t) là các số thực dương. khi kiếm được nghiệm, giả dụ bọn chúng chưa hẳn là số tự nhiên, ta vẫn mang những giá trị tự nhiên và thoải mái sớm nhất.

Vậy ta cần giải bài xích toán thù buổi tối ưu sau đây:

Bài toán thù NXB:

Nhận thấy rằng hàm mục tiêu (objective sầu function) là một trong hàm tuyến đường tính của các biến (x, y, z, t). Các ĐK ràng buộc đều phải có dạng hyperplanes hoặc haflspaces, đa số là các buộc ràng tuyến tính (linear constraints). Bài toán buổi tối ưu với tất cả objective function cùng constraints đa số là linear được Gọi là Linear Programming (LP). Dạng tổng quát và cách thức thiết kế để giải một bài bác toán ở trong nhiều loại này sẽ được mang đến vào phần sau của bài viết này.

Nghiệm cho bài toán này có thể nhận biết ngay lập tức là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn thế cùng số biến hóa nhiều hơn, họ nên một giải mã rất có thể tính được bằng phương pháp lập trình.

1.2. Bài toán canh tác

Bài toán

Một anh nông dân gồm tổng số 10ha (10 hecta) đất canh tác. Anh dự tính tLong cafe và hồ tiêu bên trên số khu đất này với tổng chi phí mang đến bài toán tLong này là không thật 16T (triệu đồng). giá thành để tdragon cà phê là 2T đến 1ha, để tdragon hồ nước tiêu là 1T/ha/. Thời gian tdragon cafe là một trong ngày/ha cùng hồ nước tiêu là 4 ngày/ha; trong những khi anh chỉ gồm thời hạn tổng cộng là 32 ngày. Sau lúc trừ toàn bộ các chi phí (bao hàm chi phí tdragon cây), từng ha cà phê đem về ROI 5T, từng ha hồ tiêu đem đến ROI 3T. Hỏi anh phải tdragon ra sao nhằm buổi tối đa lợi nhuận? (Các số liệu rất có thể vô lý vày bọn chúng đã làm được lựa chọn nhằm bài tân oán ra nghiệm đẹp)

Phân tích

Gọi (x) và (y) theo thứ tự là số ha coffe với hồ nước tiêu mà lại anh nông dân đề xuất tLong. Lợi nhuận anh ấy chiếm được là (f(x, y) = 5x + 3y) (triệu đồng).

Các ràng buộc vào bài bác toán này là:

Tổng diện tích tLong ko quá quá 10: (x + y leq 10).

Tổng ngân sách tdragon ko thừa quá 16T: (2x + y leq 16).

Tổng thời hạn trồng ko thừa quá 32 ngày: (x + 4y leq 32).

Diện tích coffe và hồ nước tiêu là các số không âm: (x, y geq 0).

Vậy ta gồm bài bác tân oán tối ưu sau đây:

Bài toán canh tác:

Bài tân oán này tương đối khác một ít là ta đề nghị tối nhiều hàm mục tiêu thế vày về tối tphát âm nó. Việc chuyển bài xích toán thù này về bài bác toán tối thiểu rất có thể được thực hiện dễ dàng và đơn giản bằng phương pháp đổi vệt hàm mục tiêu. Lúc kia hàm phương châm vẫn chính là linear, các ràng buộc vẫn là các linear constraints, ta lại có một bài bác tân oán Linear Programming (LP) nữa.

Quý khách hàng cũng hoàn toàn có thể dựa vào hình minch hoạ sau đây nhằm suy ra nghiệm của bài toán:


*

Vùng màu sắc xám bao gồm dạng polyhedron (trong ngôi trường hợp này là nhiều giác) chính là tập vừa lòng những điểm toại nguyện những buộc ràng từ (8)) mang lại ((11)). Các mặt đường đường nét đứt gồm màu sắc đó là các mặt đường đồng nấc của hàm mục tiêu (5x + 3y), từng đường ứng với cùng 1 quý hiếm khác nhau cùng với mặt đường càng đỏ ứng với cái giá trị càng tốt. Một bí quyết trực quan, nghiệm của bài xích toán rất có thể tìm kiếm được bằng cách di chuyển mặt đường nét đứt màu xanh lá cây về phía bên yêu cầu (phía tạo cho cực hiếm của hàm mục tiêu phệ hơn) cho đến lúc nó không hề điểm chung cùng với hầu hết giác color xám nữa.

Có thể nhận biết nghiệm của bài bác tân oán chính là điểm màu xanh là giao điểm của hai tuyến đường trực tiếp (x + y = 10) cùng (2x + y = 16). Giải hệ phương thơm trình này ta gồm (x^* = 6) và (y^* = 4). Tức anh nông dân bắt buộc trồng 6ha cafe với 4ha hồ tiêu. Lúc kia ROI nhận được là (5x^* + 3y^* = 42 ) triệu đ, trong khi anh chỉ mất thời hạn là 22 ngày. (Chịu đựng tính toán thù chiếc là không giống ngay lập tức, làm ít, hưởng nhiều).

Đây đó là phương pháp giải vào sách toán thù lớp 10 (ngày tôi học tập lớp 10).

Với nhiều biến hóa rộng và các buộc ràng hơn, họ liệu rất có thể vẽ được hình như vậy này để nhìn ra nghiệm xuất xắc không? Câu vấn đáp của tớ là đề nghị tìm kiếm một qui định để với rất nhiều vươn lên là hơn với với những ràng buộc khác nhau, bạn có thể tìm ra nghiệm gần như là ngay lập tức mau chóng.

1.3. Bài toán đóng góp thùng

Bài toán

Một cửa hàng bắt buộc đưa 400 (m^3) cat cho tới vị trí phát hành ngơi nghỉ bên đó sông bằng cách thuê một chiếc xà lan. Ngoài chi phí đi lại một lượt đi về là 100k của dòng xà lan, công ty kia cần kiến tạo một thùng hình vỏ hộp chữ nhật để trên xà lan để đựng mèo. Chiếc thùng này sẽ không bắt buộc nắp, chi phí cho các mặt xung quanh là 1T/(m^2), mang lại dưới đáy là 2T/(m^2). Hỏi size của mẫu thùng đó thế nào để tổng ngân sách tải là nhỏ duy nhất. Để đến đơn giản, giả sử cát chỉ được đổ ngang hoặc thấp 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 cùng cất được mức độ nặng nề vô hạn, đưa sử này khiến cho bài xích toán thù dễ dàng giải rộng.

Phân tích

Giả sử mẫu thùng buộc phải làm có chiều dài là (x) ((m)), chiều rộng lớn là (y) với độ cao là (z). Thể tích của thùng là (xyz) (đơn vị chức năng là (m^3)). Có nhị nhiều loại ngân sách là:

túi tiền thuê xà lan: số chuyến xà lan cần mướn là (frac400xyz) (ta hãy trợ thời trả sử rằng đây là một số tự nhiên và thoải mái, câu hỏi làm cho tròn này sẽ không biến hóa hiệu quả đáng chú ý vì chưng ngân sách chuyển động một chuyến là bé dại so với ngân sách có tác dụng thùng). Số chi phí nên trả cho xà lan vẫn là (0.1frac400xyz = frac40xyz).

Ngân sách chi tiêu làm thùng: Diện tích bao quanh của thùng là (2 (x + y)z ). Diện tích đáy là (xy). Vậy tổng ngân sách làm cho thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).

Tổng toàn cục chi phí là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều khiếu nại buộc ràng tốt nhất là kích 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 này hoàn toàn rất có thể dùng bất đẳng thức Cauchy để giải được, mà lại tôi vẫn ước ao một giải thuật mang đến bài xích tân oán tổng thể làm sao để cho hoàn toàn có thể lập trình được.

Xem thêm: " Cầu Vượt Tiếng Anh Là Gì, Cách Nói Cầu Vượt Trong Tiếng Anh

(Lời giải:3200endeqnarray>dấu bởi xảy ra khi và chỉ khi (x = y = z = sqrt10). Bài này chắc hẳn rằng phù hợp với những kỳ thi vị dữ kiện thừa rất đẹp. Cá nhân tôi ưa thích các đề bài ra mẫu mã này rộng là yên cầu đi kiếm quý giá nhỏ độc nhất của một biểu thức buồn rầu, nhiều học sinh nhận định rằng đắn đo học bất đẳng thức để gia công gì!)

Nếu tất cả các ràng buộc về kích thước của thùng cùng trọng lượng mà lại xà lan cài đặt được thì rất có thể kiếm được giải mã dễ dàng như vậy này không?

Những bài toán bên trên phía trên các là các bài bác toán về tối ưu. Chính xác hơn thế nữa, bọn chúng số đông là những bài bác toán thù về tối ưu lồi (convex optimization problems) nlỗi những các bạn sẽ thấy ở vị trí sau. Và việc tìm và đào bới giải mã có thể ko mấy trở ngại, thậm chí giải bằng tay thủ công cũng rất có thể ra tác dụng. Tuy nhiên, mục đích của bài viết này chưa phải là hướng dẫn các bạn giải những bài bác tân oán bên trên bởi tay, mà là bí quyết thừa nhận diện các bài bác toán thù với chuyển bọn chúng về những dạng nhưng những toolboxes sẵn tất cả hoàn toàn có thể góp chúng ta. Trên thực tế, lượng dữ kiện cùng số biến đổi phải tối ưu lớn hơn nhiều, họ bắt buộc giải các bài xích tân oán bên trên bởi tay được.

Trước hết, họ buộc phải đọc những quan niệm về convex optimization problems với tại sao convex lại đặc biệt. (quý khách hàng gọi hoàn toàn có thể hiểu cho tới phần 4 nếu như không ý muốn biết những định nghĩa với định lý toán thù vào phần 2 và 3.)

2. Nhắc lại bài xích toán về tối ưu

2.1. Các khái niệm cơ bản

Tôi xin kể lại bài toán tối ưu làm việc dạng tổng quát:

Phát biểu bằng lời: Tìm quý giá của đổi thay (mathbfx) nhằm buổi tối tphát âm hàm (f_0(mathbfx)) trong số các cực hiếm của (mathbfx) mãn nguyện các điệu hiện tại buộc ràng. Ta gồm bảng những tên thường gọi tiếng Anh cùng giờ đồng hồ Việt nhỏng sau:

Ký hiệu Tiếng Anh Tiếng Việt
(mathbfx in mathbbR^n) optimization variable biến hóa buổ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 ) ineunique 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 xích toán ((15)) được Hotline là unconstrained optimization problem (bài xích toán thù tối ưu ko ràng buộc).

(mathcalD) chỉ với tập xác định, tức giao của toàn bộ các tập khẳng định của các hàm số mở ra vào bài bác toán. Tập phù hợp các điểm vừa lòng đều điều kiện ràng buộc, thông thường, là một trong tập nhỏ của (mathcalD) được Call là feasible set hoặc constraint set. Khi feasible set là một trong những tập trống rỗng thì ta nói bài tân oán buổi tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta Hotline đặc điểm này là feasible.

2.2. Optimal và locally optimal points

Một điểm (mathbfx^*) được điện thoại tư vấn là 1 điểm optimal point (điểm về tối ưu), hay những nghiệm của bài xích tân oán ((15)) ví như (mathbfx^*) là feasible cùng (f_0(mathbfx^*) = p^*). Tất đúng theo toàn bộ những optimal points được Hotline là optimal set.

Nếu optimal set là 1 trong tập không trống rỗng, ta nói bài bác toán thù ((15)) là solvable (giải được). trái lại, nếu như optimal set là 1 trong những tập trống rỗng, ta nói optimal valuebắt buộc đạ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 toán này là (p^* = 0) cơ mà optimal set là một tập trống rỗng do không có cực hiếm làm sao của (x) nhằm hàm mục tiêu đạt quý giá 0. Lúc bấy giờ ta nói quý hiếm về tối ưukhông đạt được.

Với hàm một trở thành, một điểm là rất tiểu của một hàm số giả dụ tại đó, hàm số đạt giá trị nhỏ độc nhất trong một bên cạnh (cùng ở kề bên này ở trong tập xác định của hàm số). Trong không khí một chiều, lân cận được hiểu là trị giỏi tối của hiệu 2 điểm nhỏ tuổi rộng một giá trị làm sao đó.

Trong toán thù về tối ưu (thường là không gian các chiều), ta hotline một điểm (mathbfx) là locally optimal (cực tiểu) nếu như lâu dài một quý giá (hay được call là chào bán kinh) (R) sao cho:

Nếu một điểm feasible (mathbfx) toại nguyện (f_i(mathbfx) = 0), ta nói rằng bất đẳng thức buộc ràng lắp thêm (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)

2.3. Một vài ba lưu ý

Mặc dù vào tư tưởng bài bác toán buổi tối ưu ((15)) là mang lại bài bác toán thù buổi tối thiểu hàm mục tiêu với những buộc ràng thoả mãn những điều kiện nhỏ dại rộng hoặc bởi 0, các bài bác tân oán tối ưu cùng với buổi tối đa hàm mục tiêu cùng ĐK ràng buộc sinh hoạt dạng khác mọi có thể mang 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à (a - f_i(mathbfx) leq 0).

(f_i(mathbfx) leq 0 Leftrightarrow f_i(mathbfx) + s_i = 0 ) cùng (s_i geq 0). (s_i) được Gọi là slachồng variable. Phnghiền đổi khác dễ dàng này trong vô số ngôi trường vừa lòng lại tỏ ra kết quả do bất đẳng thức (s_i geq 0) thường 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 về tối ưu, chúng ta quan trọng đặc biệt quan tâm cho tới đông đảo bài tân oán cơ mà hàm kim chỉ nam là một trong hàm lồi, và feasible set cũng là 1 trong những tập lồi.

3.1. Định nghĩa

Một bài bác toán thù tối ưu lồi (convex optimization problem) là một bài bác toán về tối ưu có dạng:trong các số ấy (f_0, f_1, dots, f_m) là những hàm lồi.

So với bài bác toán về tối ưu ((15)), bài bác tân oán về tối ưu lồi ((16)) tất cả thêm bố ĐK nữa:

Hàm mục tiêu là một trong hàm lồi.

Các hàm bất đẳng thức buộc ràng (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 cùng 1 hẳng số nữa được Điện thoại tư vấn là affine).

Một vài dìm xét:

Tập đúng theo các điểm vừa lòng (h_j(mathbfx) = 0) là 1 trong những tập lồi vày nó bao gồm dạng một hyperplane.

Vậy, trong một bài xích toán thù buổi tối ưu lồi, ta tối tphát âm một hàm mục tiêu lồi bên trên một tập lồi.

3.2. Cực tè của bài bác tân oán tối ưu lồi đó là điểm về tối ưu.

TÍnh chất đặc trưng tốt nhất của bài bác tân oán về tối ưu lồi chính là bất kỳ locally optimal point đó là một điểm (globally) optimal point.

Tính hóa học đặc trưng này hoàn toàn có thể minh chứng bằng bội nghịch bệnh nlỗi sau. Hotline (mathbfx_0) là một trong những điểm locally optimal, tức:

cùng với (R > 0) như thế nào kia. Giả sử (mathbfx_0) chưa phải là globally optimal point, tức mãi mãi một feasible point (mathbfy) làm sao để cho (f(mathbfy) &leqvà (1 - heta)f_0(mathbfx_0) + heta f_0(mathbfy) và &=và f_0(mathbfx_0)endeqnarray>

vấn đề này mâu thuẫn cùng với giả thiết (mathbfx_0) là 1 trong điểm rất tiểu. Vậy giả sử không đúng, tức (mathbfx_0) chính là globally optimal point và ta có điều đề nghị minh chứng.

3.3. Điều kiện về tối ưu cho hàm kim chỉ nam khả vi

Nếu hàm phương châm (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 buộc phải với đủ nhằm một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ lỡ câu hỏi chứng tỏ điều kiện bắt buộc cùng đủ này, độc giả có thể tìm vào trang 139-140 của cuốn Convex Optimization trong Tài liệu xem thêm.

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *