Linear programming là gì

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

quý khách được khuyến khích gọi Bài 16 trước khi gọi bài xích này. Nội dung vào nội dung bài viết này đa phần được dịch từ bỏ Cmùi hươ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 đã xem: Linear programming là gì.

You watching: Linear programming là gì

Bài này cũng có khá nhiều định nghĩa bắt đầu và nhiều triết lý yêu cầu hoàn toàn có thể không thu hút như các bài xích không giống. Tuy nhiên, tôi cần thiết bỏ qua vị không thích chúng ta trọn vẹn mất phương thơm hướng lúc hiểu các bài sau.

Quý Khách phát âm hoàn toàn có thể xem bản pdf trên đây.

1. Giới thiệu

Tôi xin ban đầu nội dung bài viết này bởi cha bài bác toán hơi sát 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 công ty xuấn phiên bản (NXB) cảm nhận deals 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ới 400 bản tới Hải Phòng Đất Cảng. NXB đó gồm 800 cuốn ngơi nghỉ kho Nam Định và 700 cuốn nắn 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 Tỉnh Thái Bình là 50,000 VND (50k), cho tới Hải Phòng là 100k. Giá chuyển phân phát một cuốn nắn từ Hải Dương tới Tỉnh Thái Bình là 150k, vào khi đến TP. Hải Phòng chỉ với 40k. Hỏi nhằm tốn ít chi phí chuyển phát nhất, cửa hàng đó cần phân păn năn mỗi kho đưa từng nào cuốn nắn cho tới mỗi địa điểm?

Phân tích

Để đến dễ dàng, ta tạo ra 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á chỉ ((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 ràng buộc (constraints) viết 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ừ bỏ kho Tỉnh Nam Định không thực sự 800: (x + y leq 800).

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

(x, y, z, t) là những số thoải mái và tự nhiên. Ràng buộc là số tự nhiên và thoải mái vẫn khiến cho bài xích tân oán rất khó giải giả dụ số lượng trở thành là rất cao. Với bài bác toán này, ta đưa sử rằng (x, y, z, t) là các số thực dương. lúc tìm được nghiệm, trường hợp bọn chúng không hẳn là số tự nhiên, ta vẫn đem những giá trị thoải mái và tự nhiên sớm nhất.

Vậy ta đề xuất giải bài xích tân oá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 sầu function) là 1 hàm đường tính của các thay đổi (x, y, z, t). Các điều kiện buộc ràng đều phải có dạng hyperplanes hoặc haflspaces, hầu hết là những buộc ràng tuyến tính (linear constraints). Bài toán thù về tối ưu đối với cả objective sầu functionconstraints rất nhiều là linear được Gọi là Linear Programming (LP). Dạng tổng quát cùng cách thức xây dựng nhằm giải một bài xích toán nằm trong loại này sẽ được cho trong phần sau của bài viết này.

Nghiệm mang đến bài tân oán này rất có thể nhận biết ngay lập tức là (x = 600, y = 0, z = 0, t = 400). Nếu buộc ràng nhiều hơn thế nữa và số biến chuyển nhiều hơn nữa, họ bắt buộc 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 tân oán canh tác

Bài toán

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

Phân tích

Điện thoại tư vấn (x) và (y) lần lượt là số ha cà phê và hồ nước tiêu mà lại anh nông dân cần tLong. Lợi nhuận anh ấy nhận được là (f(x, y) = 5x + 3y) (triệu đồng).

Các buộc ràng trong bài tân oán này là:

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

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

Tổng thời gian tdragon ko quá quá 32 ngày: (x + 4y leq 32).

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

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

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

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

Quý khách hàng cũng rất có thể phụ thuộc hình minc hoạ tiếp sau đây nhằm suy ra nghiệm của bài xích toán:


*

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

Có thể nhận biết nghiệm của bài xích toán chính là điểm blue color 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 thơm trình này ta gồm (x^* = 6) cùng (y^* = 4). Tức anh nông dân buộc phải tLong 6ha cafe và 4ha hồ tiêu. Lúc đó lợi nhuận thu được là (5x^* + 3y^* = 42 ) triệu đ, trong những lúc anh chỉ mất thời gian là 22 ngày. (Chịu tính tân oán dòng là không giống tức thì, làm cho không nhiều, hưởng nhiều).

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

Với các trở nên hơn và các ràng buộc rộng, bọn họ liệu hoàn toàn có thể vẽ được hình như thế này để xem 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 lý lẽ nhằm với tương đối nhiều biến hóa hơn cùng cùng với các buộc ràng khác nhau, chúng ta có thể tìm thấy nghiệm gần như là tức thì chớp nhoáng.

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

Bài toán

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

Phân tích

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

giá cả thuê xà lan: số chuyến xà lan bắt buộc mướn là (frac400xyz) (ta hãy tạm thời mang sử rằng đó là một trong những thoải mái và tự nhiên, bài toán làm tròn này sẽ không biến đổi tác dụng đáng kể vì chưng ngân sách chuyên chở một chuyến là bé dại so với chi phí làm thùng). Số chi phí yêu cầu trả mang lại xà lan sẽ 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 khiếu nại buộc ràng duy nhất là kích cỡ thùng nên là các số dương. Vậy ta gồm bài 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 có thể cần sử dụng bất đẳng thức Cauchy nhằm giải được, nhưng mà tôi vẫn mong một lời giải cho bài toán tổng quát làm thế nào để cho hoàn toàn có thể lập trình sẵn được.

See more: Seo Toolkit Là Gì - Toolkit Nghĩa Là Gì

(Lời giải:3200endeqnarray>vệt bằng xẩy ra lúc và chỉ còn lúc (x = y = z = sqrt10). Bài này có lẽ hợp với những kỳ thi do dữ kiện quá đẹp mắt. Cá nhân tôi thích các đề bài bác ra loại này rộng là hưởng thụ đi tìm cực hiếm nhỏ tuổi tuyệt nhất của một biểu thức nhàm chán, những học sinh nhận định rằng lần khần học bất đẳng thức để triển khai gì!)

Nếu bao gồm những ràng buộc về kích thước của thùng và trọng lượng nhưng mà xà lan download được thì rất có thể tìm kiếm được giải thuật đơn giản như thế này không?

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

Trước không còn, họ cần đọc những có mang về convex optimization problems cùng tại vì sao convex lại đặc trưng. (Bạn phát âm có thể gọi tới phần 4 còn nếu như không mong mỏi biết những khái niệm với định lý toán vào phần 2 cùng 3.)

2. Nhắc lại bài bác toán buổi tối ưu

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

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

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

Ký hiệu Tiếng Anh Tiếng Việt
(mathbfx in mathbbR^n) optimization variable phát triển thành 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 ) inequality constraints bất đẳng thức ràng buộc
(f_i: mathbbR^n ightarrow mathbbR) inechất lượng 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:

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

(mathcalD) chỉ với tập khẳng định, tức giao của tất cả những tập xác minh của phần nhiều hàm số lộ diện vào bài bác tân oán. Tập phù hợp những điểm toại ý mọi điều kiện ràng buộc, thông thường, là một trong tập bé của (mathcalD) được gọi là feasible set hoặc constraint set. lúc feasible set là một trong tập rỗng thì ta nói bài tân oán về tối ưu ((15)) là infeasible. Nếu một điểm bên trong feasible set, ta Gọi đặ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 trong những điểm optimal point (điểm tối ưu), Hoặc là nghiệm của bài xích toán thù ((15)) nếu như (mathbfx^*) là feasible cùng (f_0(mathbfx^*) = p^*). Tất phù hợp toàn bộ những optimal points được call là optimal set.

Nếu optimal set là 1 trong những tập không trống rỗng, ta nói bài xích toán thù ((15)) là solvable (giải được). Ngược lại, nếu optimal set là 1 tập rỗng, ta nói optimal valuechẳng thể đạt được (not attained/ not achieved).

Ví dụ: xét hàm mục tiêu (f(x) = 1/x) với buộc ràng (x > 0). Optimal value của bài toán này là (p^* = 0) nhưng mà optimal set là một tập trống rỗng do không tồn tại quý giá làm sao của (x) để hàm kim chỉ nam đạt quý giá 0. Lúc này ta nói quý hiếm tối ưuko đạt được.

Với hàm một vươn lên là, một điểm là rất tiểu của một hàm số ví như tại kia, hàm số đạt cực hiếm bé dại tuyệt nhất trong một cạnh bên (với bên cạnh 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 hiểu là trị hay buổi tối của hiệu 2 điểm bé dại rộng một giá trị nào đó.

Trong toán thù buổi tối ưu (hay là không khí nhiều chiều), ta Điện thoại tư vấn một điểm (mathbfx) là locally optimal (rất tiểu) trường hợp mãi mãi một quý giá (thường được Hotline là phân phối 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 ràng buộc trang 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 có mang bài xích toán buổi tối ưu ((15)) là mang đến bài bác tân oán buổi tối tđọc hàm mục tiêu cùng với các buộc ràng ưng ý những điều kiện nhỏ dại hơn hoặc bằng 0, những bài xích tân oán về tối ưu cùng với về tối nhiều hàm mục tiêu cùng ĐK ràng buộc ở dạng khác đa số có thể đem đến đượ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 ) với (s_i geq 0). (s_i) được Điện thoại tư vấn là slack variable. Phép đổi khác dễ dàng và đơn giản này trong không ít ngôi trường hòa hợp lại trầm trồ hiệu quả do bất đẳng thức (s_i geq 0) thường rất dễ giải quyết rộng là (f_i(mathbfx) leq 0).

3. Bài toán về tối ưu lồi

Trong tân oán buổi tối ưu, chúng ta đặc trưng quyên tâm cho tới hầu hết bài tân oán mà lại hàm phương châm là 1 trong hàm lồi, với feasible set cũng là một trong tập lồi.

3.1. Định nghĩa

Một bài bác toán tối ưu lồi (convex optimization problem) là một trong bài xích tân oán buổi tối ưu bao gồm dạng:trong số đó (f_0, f_1, dots, f_m) là các hàm lồi.

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

Hàm mục tiêu là 1 trong những hàm lồi.

Các hàm bất đẳng thức buộc ràng (f_i) là những hàm lồi.

Hàm đẳng thức buộc ràng (h_j) là affine (hàm linear cùng với cùng một hẳng số nữa được Hotline là affine).

Một vài ba nhận xét:

Tập hợp những điểm thoả mãn (h_j(mathbfx) = 0) là một trong tập lồi vày nó có dạng một hyperplane.

Vậy, vào một bài toán buổi tối ưu lồi, ta về tối tphát âm một hàm kim chỉ nam lồi trên một tập lồi.

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

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

Tính chất quan trọng đặc biệt này hoàn toàn có thể chứng minh bởi phản nghịch hội chứng nhỏng sau. gọi (mathbfx_0) là 1 điểm locally optimal, tức:

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

điều này mâu thuẫn với mang thiết (mathbfx_0) là 1 trong những điểm rất đái. Vậy mang sử sai, tức (mathbfx_0) chính là globally optimal point với ta có điều nên minh chứng.

See more: " Đối Với Tiếng Anh Là Gì - Ví Dụ Và Cách Dùng Đúng Văn Phạm

3.3. Điều khiếu nại về tối ưu đến hàm phương châm 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 kiện cần cùng đủ nhằm một điểm (mathbfx_0 in mathcalX) là optimal point là:Tôi xin được bỏ qua mất việc chứng minh điều kiện yêu cầu và đầy đủ này, bạn đọc rất có thể search vào trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.


Chuyên mục: Giải Đáp