1. Giới thiệu 1.1. Bài toán thù công ty 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 bác tân oán về tối ưu 3. Bài toán thù buổi 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 hiểu bài xích này. Nội dung vào bài viết này đa phần được dịch trường đoản cú Chương 4 của cuốn nắn Convex Optimization vào phần Tài liệu tìm hiểu thêm.Quý khách hàng vẫn xem: Linear programming là gì.

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

Bài này cũng có khá nhiều định nghĩa mới cùng các lý thuyết phải hoàn toàn có thể ko lôi kéo nlỗi các bài bác không giống. Tuy nhiên, tôi bắt buộc bỏ qua bởi vì không thích các bạn trọn vẹn mất phương thơm hướng khi hiểu các bài bác sau.

quý khách phát âm hoàn toàn có thể coi bạn dạng pdf tại đây.

1. Giới thiệu

Tôi xin ban đầu bài viết này bởi cha bài xích tân oán khá ngay gần với thực tế:

1.1. Bài toán thù công ty xuất bản

Bài toán

Một đơn vị xuấn phiên bản (NXB) nhận được đơn hàng 600 phiên bản của cuốn “Machine Learning cơ bản” tới Tỉnh Thái Bình với 400 bạn dạng cho tới TP. Hải Phòng. NXB kia tất cả 800 cuốn nắn sinh hoạt kho Tỉnh Nam Định cùng 700 cuốn nắn sinh sống kho Hải Dương. Giá đưa phát một cuốn sách trường đoản cú Nam Định cho tới Thái Bình là 50,000 VND (50k), cho tới TPhường. Hải Phòng là 100k. Giá gửi vạc một cuốn tự Thành Phố Hải Dương cho tới Tỉnh Thái Bình là 150k, trong khi đến TP.. Hải Phòng chỉ là 40k. Hỏi nhằm tốn không nhiều chi phí đưa phạt độc nhất vô nhị, cửa hàng kia buộc phải phân păn năn từng kho gửi bao nhiêu cuốn cho tới mỗi địa điểm?

Phân tích

Để đến dễ dàng, ta xây dừng bảng con số chuyển sách từ nguồn tới đích nlỗi sau:

Nguồn Đích Đơn giá ((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 ngân sách (objective 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 Tỉnh Nam Định không thật 800: (x + y leq 800).

Lấy từ kho Thành Phố Hải Dương không thật 700: (z + t leq 700).

(x, y, z, t) là các số tự nhiên và thoải mái. Ràng buộc là số tự nhiên vẫn làm cho bài bác toán thù cực kỳ nặng nề giải trường hợp số lượng đổi mới là rất lớn. Với bài xích toán thù 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 phải là số tự nhiên, ta đã lấy các cực hiếm tự nhiên sớm nhất.

Vậy ta đề xuất giải bài toán 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 function) là 1 trong những hàm con đường tính của các đổi thay (x, y, z, t). Các ĐK ràng buộc đều có dạng hyperplanes hoặc haflspaces, hầu như là các buộc ràng tuyến đường tính (linear constraints). Bài toán tối ưu với cả objective sầu function với constraints hồ hết là linear được Hotline là Linear Programming (LP). Dạng tổng thể với phương pháp thiết kế để giải một bài bác toán thuộc một số loại này sẽ tiến hành mang đến trong phần sau của nội dung bài viết này.

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

1.2. Bài tân oán canh tác

Bài toán

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

Phân tích

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

Các ràng buộc vào bài xích toán thù này là:

Tổng diện tích S trồng không thừa quá 10: (x + y leq 10).

Tổng chi phí tLong ko quá quá 16T: (2x + y leq 16).

Tổng thời hạn tdragon không vượt quá 32 ngày: (x + 4y leq 32).

Diện tích coffe cùng hồ tiêu là những số ko âm: (x, y geq 0).

Vậy ta gồm bài xích toán về tối ưu sau đây:

Bài tân oán canh tác:

Bài tân oán này tương đối không giống một chút là ta nên tối nhiều hàm mục tiêu thay vì chưng về tối tđọc nó. Việc gửi bài xích tân oán này về bài xích tân oán về tối thiểu có thể được thực hiện dễ dàng và đơn giản bằng cách thay đổi lốt hàm kim chỉ nam. Lúc kia hàm mục tiêu vẫn chính là linear, các buộc ràng vẫn luôn là các linear constraints, ta lại sở hữu một bài bác tân oán Linear Programming (LP) nữa.

Quý Khách cũng hoàn toàn có thể phụ thuộc hình minch hoạ dưới đây nhằm suy ra nghiệm của bài toán:


*

Vùng màu sắc xám gồm dạng polyhedron (trong trường thích hợp này là nhiều giác) đó là tập phù hợp các điểm thoả nguyện các ràng buộc từ bỏ (8)) cho ((11)). Các con đường nét đứt có màu sắc chính là những con đường đồng nút của hàm kim chỉ nam (5x + 3y), mỗi mặt đường ứng với một cực 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 biện pháp trực quan, nghiệm của bài xích toán thù có thể kiếm được bằng cách di chuyển đường đường nét đứt màu xanh về phía mặt phải (phía tạo cho quý giá của hàm phương châm béo hơn) cho đến lúc nó không thể điểm thông thường với những giác màu sắc xám nữa.

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

Đây đó là bí quyết giải vào sách toán lớp 10 (ngày tôi học tập lớp 10).

Với các biến rộng cùng các ràng buộc hơn, họ liệu rất có thể vẽ được hình như thế này để xem ra nghiệm tuyệt không? Câu trả lời của tớ là phải tìm một phép tắc để với tương đối nhiều trở nên rộng và cùng với những buộc ràng khác biệt, chúng ta cũng có thể tìm ra nghiệm gần như ngay lập tức mau chóng.

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

Bài toán

Một chủ thể cần đưa 400 (m^3) mèo cho tới địa điểm xây đắp ở bên kia sông bằng cách thuê một cái xà lan. Ngoài chi phí vận động một lượt đi về là 100k của cái xà lan, cửa hàng đó cần xây dựng một thùng hình vỏ hộp chữ nhật bỏ lên xà lan nhằm đựng cát. Chiếc thùng này không cần nắp, chi phí cho các mặt bao bọc là 1T/(m^2), mang lại mặt đáy là 2T/(m^2). Hỏi size của mẫu thùng kia ra làm sao nhằm tổng chi phí vận tải là nhỏ dại nhất. Để đến dễ dàng, mang sử mèo chỉ được đổ ngang hoặc rẻ 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à cất được sức nặng trĩu vô hạn, trả 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ử cái thùng phải làm cho bao gồm chiều dài là (x) ((m)), chiều rộng lớn là (y) và độ cao là (z). Thể tích của thùng là (xyz) (đơn vị chức năng là (m^3)). Có nhì các loại ngân sách là:

túi tiền thuê xà lan: số chuyến xà lan bắt buộc thuê là (frac400xyz) (ta hãy nhất thời đưa sử rằng đó là một trong những tự nhiên, câu hỏi có tác dụng tròn này sẽ không còn biến đổi công dụng đáng kể bởi vì chi phí chuyên chở một chuyến là nhỏ dại so với ngân sách có tác dụng thùng). Số tiền buộc phải trả mang lại xà lan đã là (0.1frac400xyz = frac40xyz).

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 lòng 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 cục bộ 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 độc nhất là form size thùng yêu cầu là các số dương. Vậy ta gồm bài bác tân oán tối ưu sau:

Bài tân oán vận chuyển: 0 ~~~~ (14)endeqnarray>

Nhận thấy rằng bài xích này hoàn toàn hoàn toàn có thể sử dụng bất đẳng thức Cauchy nhằm giải được, nhưng mà tôi vẫn hy vọng một giải thuật mang đến bài xích tân oán tổng quát làm thế nào để cho hoàn toàn có thể lập trình sẵn được.

Xem thêm:

(Lời giải:3200endeqnarray>lốt bằng xẩy ra Khi còn chỉ lúc (x = y = z = sqrt10). Bài này có lẽ rằng phù hợp với các kỳ thi vị dữ kiện vượt đẹp nhất. Cá nhân tôi mê thích những đề bài xích ra giao diện này hơn là hưởng thụ đi tìm kiếm giá trị nhỏ tuổi tuyệt nhất của một biểu thức rầu rĩ, những học viên nhận định rằng phân vân học tập bất đẳng thức để gia công gì!)

Nếu gồm những buộc ràng về form size của thùng với trọng lượng mà lại xà lan tải được thì hoàn toàn có thể kiếm được giải thuật dễ dàng như vậy này không?

Những bài bác tân oán trên đây mọi là những bài xích toán buổi tối ưu. Chính xác hơn nữa, chúng phần đông là các bài bác toán buổi tối ưu lồi (convex optimization problems) nlỗi những các bạn sẽ thấy tại phần sau. Và việc tìm kiếm giải thuật hoàn toàn có thể ko mấy khó khăn, thậm chí còn giải bằng tay thủ công cũng rất có thể ra kết quả. 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 tân oán trên bằng tay, nhưng là bí quyết dìm diện các bài xích toán thù với đưa bọn chúng về các dạng nhưng mà những toolboxes sẵn gồm hoàn toàn có thể giúp chúng ta. Trên thực tiễn, lượng dữ khiếu nại với số trở thành cần về tối ưu lớn hơn các, họ bắt buộc giải các bài toán thù bên trên bởi tay được.

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

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

2.1. Các định nghĩa cơ bản

Tôi xin nhắc lại bài toán về tối ưu ngơi nghỉ dạng tổng quát:

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

Ký hiệu Tiếng Anh Tiếng Việt
(mathbfx in mathbbR^n) optimization variable biến chuyể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 ) echất lượng constraints đẳng thức ràng buộc
(h_j: mathbbR^n ightarrow mathbbR) echất lượng 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:

Khi (m = p = 0), bài bác toán thù ((15)) được Gọi là unconstrained optimization problem (bài toán thù về tối ưu ko ràng buộc).

(mathcalD) chỉ nên tập xác minh, tức giao của toàn bộ các tập xác định của rất nhiều hàm số xuất hiện trong bài toán. Tập đúng theo những điểm hài lòng mọi ĐK buộc ràng, thường thì, là một tập bé 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 trong những tập trống rỗng thì ta nói bài tân oán tối ưu ((15)) là infeasible. Nếu một điểm phía bên trong feasible set, ta Call đặc điểm này là feasible.

2.2. Optimal and locally optimal points

Một điểm (mathbfx^*) được điện thoại tư vấn là một đ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à (f_0(mathbfx^*) = p^*). Tất hòa hợp tất cả những optimal points được điện thoại tư vấn là optimal set.

Nếu optimal set là 1 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, ví như optimal set là một trong những tập trống rỗng, ta nói optimal valuequan yếu đạt được (not attained/ not achieved).

Ví dụ: xét hàm kim chỉ nam (f(x) = 1/x) cùng với ràng buộc (x > 0). Optimal value của bài xích tân oán này là (p^* = 0) mà lại optimal set là 1 tập rỗng bởi vì không có quý giá làm sao của (x) nhằm hàm phương châm đạt giá trị 0. Hiện giờ ta nói quý giá về tối ưuko đạt được.

Với hàm một thay đổi, một điểm là rất tiểu của một hàm số ví như tại đó, hàm số đạt giá trị nhỏ dại duy nhất vào một bên cạnh (với kề bên này ở trong tập khẳng định của hàm số). Trong không gian 1 chiều, lạm cận được đọc là trị tuyệt buổi tối của hiệu 2 điểm nhỏ tuổi rộng một cực hiếm nào kia.

Trong toán tối ưu (thường xuyên là không khí các chiều), ta Gọi một điểm (mathbfx) là locally optimal (cực tiểu) giả dụ mãi sau một quý giá (thường được Gọi là cung cấp kinh) (R) sao cho:

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 buộc ràng thiết bị (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)

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

Mặc mặc dù trong tư tưởng bài bác toán thù tối ưu ((15)) là mang đến bài bác toán thù tối tgọi hàm mục tiêu với các ràng buộc hài lòng những điều kiện nhỏ dại hơn hoặc bởi 0, các bài bác toán buổi tối ưu với về tối nhiều hàm mục tiêu và ĐK buộc ràng sinh hoạt dạng không giống đa số rất 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ớ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 Call là slachồng variable. Phxay biến đổi dễ dàng và đơn giản này trong nhiều trường hợp lại tỏ ra kết quả bởi vì bất đẳng thức (s_i geq 0) thường sẽ dễ xử lý rộng là (f_i(mathbfx) leq 0).

3. Bài toán buổi tối ưu lồi

Trong tân oán về tối ưu, bọn họ đặc trưng quyên tâm cho tới các bài toán cơ mà hàm kim chỉ nam là một trong những hàm lồi, cùng feasible set cũng là 1 trong những tập lồi.

3.1. Định nghĩa

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

So cùng với bài toán thù buổi tối ưu ((15)), bài xích toán buổi tối ưu lồi ((16)) bao gồm thêm ba điều kiện nữa:

Hàm mục tiêu là 1 trong 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 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 hợp những đ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 tgọi một hàm kim chỉ nam lồi trên một tập lồi.

3.2. Cực tè của bài xích toán về tối ưu lồi chính là điểm về tối ưu.

TÍnh hóa học đặc biệt tuyệt nhất của bài toán thù buổi tối ưu lồi đó là bất kỳ locally optimal point đó là một điểm (globally) optimal point.

Tính hóa học quan trọng này rất có thể chứng minh bằng phản nghịch triệu chứng nhỏng sau. Điện thoại tư vấn (mathbfx_0) là một điểm locally optimal, tức:

với (R > 0) như thế nào đó. Giả sử (mathbfx_0) chưa hẳn là globally optimal point, tức lâu dài một feasible point (mathbfy) làm sao cho (f(mathbfy) &leq& (1 - heta)f_0(mathbfx_0) + heta f_0(mathbfy) & &=& f_0(mathbfx_0)endeqnarray>

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

3.3. Điều khiếu nại buổi 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 đa số (mathbfx, mathbfy in extdomf_0), ta có:

Đặt (mathcalX) là feasible set. Điều kiện bắt buộc với đủ để một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua mất Việc minh chứng điều kiện buộc phải cùng đủ này, độc giả hoàn toàn có thể tìm kiếm vào trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.

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 *