Linear programming là gì

     

1. Trình làng 1.1. Câu hỏi nhà xuất phiên bản 1.2. Việc canh tác 1.3. Bài toán đóng thùng 2. Nói lại bài toán tối ưu 3. Việc tối ưu lồi 4. Linear Programming 5. Quadratic Programming 6. Geometric Programming

Bạn được khích lệ đọc bài bác 16 trước lúc đọc bài bác này. Ngôn từ trong bài viết này hầu hết được dịch từ Chương 4 của cuốn Convex Optimization vào phần tư liệu tham khảo.Bạn sẽ xem: linear programming là gì.

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

Bạn vẫn xem: Linear programming là gì

Đang xem: Linear programming là gì

Bài này cũng có không ít khái niệm mới và nhiều định hướng nên có thể không hấp dẫn như các bài khác. Tuy nhiên, tôi không thể làm lơ vì ko muốn các bạn hoàn toàn mất phương phía khi đọc những bài sau.

Bạn đọc có thể xem bạn dạng pdf tại đây.

1. Giới thiệu

Tôi xin bắt đầu bài viết này bằng tía bài toán khá sát với thực tế:

1.1. Việc nhà xuất bản

Bài toán

Một đơn vị xuấn phiên bản (NXB) dấn được giao dịch 600 phiên bản của cuốn “Machine Learning cơ bản” tới tỉnh thái bình và 400 bạn dạng tới Hải Phòng. NXB đó bao gồm 800 cuốn sinh hoạt kho phái mạnh Định cùng 700 cuốn nghỉ ngơi kho Hải Dương. Giá gửi phát một cuốn sách từ phái mạnh Định tới tỉnh 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ừ thành phố hải dương tới thái bình là 150k, trong những lúc tới tp. Hải phòng chỉ là 40k. Hỏi để tốn ít ngân sách chuyển phát nhất, công ty đó đề nghị 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 đối kháng giản, ta xây dừng bảng con số chuyển sách từ nguồn tới đích như sau:

nguồn Đích Đơn giá bán ((imes)10k) số lượng
Nam ĐịnhThái Bình5(x)
Nam ĐịnhHải Phỏng10(y)
Hải DươngThái Bình15(z)
Hải DươngHải Phòng4(t)

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 tập là:

Chuyển 600 cuốn cho 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 thật 800: (x + y leq 800).

Lấy trường đoản cú kho Hải Dương không thật 700: (z + t leq 700).

(x, y, z, t) là các số từ bỏ nhiên. Ràng buộc là số tự nhiên sẽ khiến cho bài toán rất cực nhọc giải nếu con số biến là khôn cùng lớn. Với việc này, ta giả sử rằng (x, y, z, t) là các số thực dương. Khi kiếm được nghiệm, nếu như chúng không hẳn là số tự nhiên, ta đang lấy các giá trị thoải mái và tự nhiên gần nhất.

Vậy ta phải giải việc tối ưu sau đây:

Bài toán NXB:

Nhận thấy rằng hàm phương châm (objective function) là 1 trong những hàm tuyến tính của những biến (x, y, z, t). Những điều kiện ràng buộc đều có dạng hyperplanes hoặc haflspaces, những là các ràng buộc tuyến đường tính (linear constraints). Câu hỏi tối ưu với tất cả objective functionconstraints đông đảo là linear được call là Linear Programming (LP). Dạng bao quát và phương thức lập trình để giải một việc thuộc nhiều loại này sẽ tiến hành cho trong phần sau của bài viết này.

Nghiệm cho bài toán này có thể nhận thấy tức thì là (x = 600, y = 0, z = 0, t = 400). Trường hợp ràng buộc nhiều hơn nữa và số vươn lên là nhiều hơn, chúng ta cần một lời giải có thể tính được bằng cách lập trình.

1.2. Việc canh tác

Bài toán

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

Phân tích

Gọi (x) với (y) thứu tự là số ha cafe và hồ nước tiêu cơ mà anh nông dân nên trồng. Roi anh ấy chiếm được là (f(x, y) = 5x + 3y) (triệu đồng).

Các buộc ràng trong vấn đề này là:

Tổng diện tích trồng ko vượt vượt 10: (x + y leq 10).

Tổng túi tiền trồng ko vượt thừa 16T: (2x + y leq 16).

Tổng thời gian trồng ko vượt vượt 32 ngày: (x + 4y leq 32).

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

Vậy ta có việc tối ưu sau đây:

Bài toán canh tác:

Bài toán này tương đối khác một chút ít là ta đề xuất tối đa hàm mục tiêu thay bởi tối thiểu nó. Vấn đề chuyển bài toán này về bài toán tối thiểu rất có thể được thực hiện đơn giản bằng phương pháp đổi vệt hàm mục tiêu. Lúc đó hàm kim chỉ nam vẫn là linear, các ràng buộc vẫn là những linear constraints, ta lại sở hữu một vấn đề Linear Programming (LP) nữa.

Bạn cũng hoàn toàn có thể dựa vào hình minh hoạ tiếp sau đây để suy ra nghiệm của bài xích toán:


*

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

Có thể phân biệt nghiệm của bài toán chính là điểm greed color là giao điểm của hai tuyến phố thẳng (x + y = 10) với (2x + y = 16). Giải hệ phương trình này ta có (x^* = 6) cùng (y^* = 4). Tức anh nông dân đề nghị trồng 6ha cafe và 4ha hồ nước tiêu. Thời điểm đó roi thu được là (5x^* + 3y^* = 42 ) triệu đồng, trong những lúc anh chỉ mất thời gian là 22 ngày. (Chịu đo lường và thống kê cái là khác ngay, làm cho ít, tận hưởng nhiều).

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

Với nhiều biến đổi hơn và nhiều ràng buộc hơn, chúng ta liệu hoàn toàn có thể vẽ được dường như thế này để xem ra nghiệm xuất xắc không? Câu trả lời của tôi là buộc phải tìm một cơ chế để với khá nhiều biến hơn với với các ràng buộc không giống nhau, chúng ta cũng có thể tìm ra nghiệm gần như ngay lập tức.

1.3. Câu hỏi đóng thùng

Bài toán

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

Phân tích

Giả sử mẫu thùng nên làm gồm chiều nhiều năm là (x) ((m)), chiều rộng là (y) và chiều cao là (z). Thể tích của thùng là (xyz) (đơn vị là (m^3)). Tất cả hai loại ngân sách chi tiêu là:

Chi giá thành thuê xà lan: số chuyến xà lan nên thuê là (frac400xyz) (ta hãy tạm đưa sử rằng đó là một số từ bỏ nhiên, việc làm tròn này đã không biến đổi kết quả đáng chú ý vì chi phí vận gửi một chuyến là nhỏ dại so với chi tiêu làm thùng). Số tiền yêu cầu trả mang đến xà lan sẽ là (0.1frac400xyz = frac40xyz).

Chi tổn phí làm thùng: diện tích s 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)).

Xem thêm: Statement Of Work Là Gì ? Tại Sao Cần Statement Of Work? Hướng Dẫn Chi Tiết Cách Viết Sow Cho Dự Án

Tổng toàn bộ giá thành là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều khiếu nại ràng buộc độc nhất là kích thước thùng cần 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: 0 ~~~~ (14)endeqnarray>

(Lời giải:3200endeqnarray>dấu bằng xảy ra khi và chỉ khi (x = y = z = sqrt10). Bài xích này có lẽ rằng hợp với những kỳ thi vì dữ kiện quá đẹp. Cá thể tôi thích những đề bài bác ra kiểu dáng này hơn là yêu thương cầu đi kiếm giá trị nhỏ dại nhất của một biểu thức nhàm chán, nhiều học viên cho rằng lưỡng lự học bất đẳng thức để gia công gì!)

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

Những vấn đề trên đây mọi là những bài toán buổi tối ưu. đúng chuẩn hơn nữa, chúng hồ hết là các bài toán buổi tối ưu lồi (convex optimization problems) như các các bạn sẽ thấy ở vị trí sau. Và việc tìm lời giải rất có thể không mấy khó khăn, thậm chí là giải thủ công cũng có thể ra kết quả. Tuy nhiên, mục tiêu của bài viết này không phải là hướng dẫn chúng ta giải các bài toán trên bằng tay, mà là bí quyết nhận diện các bài toán với đưa bọn chúng về những dạng mà những toolboxes sẵn có rất có thể giúp bọn chúng ta. Bên trên thực tế, lượng dữ kiện cùng số biến đề nghị tối ưu to hơn nhiều, bọn họ không thể giải các bài toán bên trên bằng tay được.

Trước hết, chúng ta cần hiểu những khái niệm về convex optimization problems và nguyên nhân convex lại quan lại trọng. (Bạn đọc hoàn toàn có thể đọc cho tới phần 4 còn nếu không muốn biết các khái niệm với định lý toán vào phần 2 cùng 3.)

2. Kể lại vấn đề tối ưu

2.1. Những khái niệm cơ bản

Tôi xin nhắc lại việc tối ưu sinh sống dạng tổng quát:

Phát biểu bằng lời: Tìm quý hiếm của thay đổi (mathbfx) để tối thiểu hàm (f_0(mathbfx)) trong các các cực hiếm của (mathbfx) thoả mãn các đ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 tiếng Việt như sau:

cam kết hiệu giờ Anh giờ Việt
(mathbfx in mathbbR^n)optimization variablebiến tối ưu
(f_0: mathbbR^n ightarrow mathbbR)objective/los/cost functionhàm mục tiêu
(f_i(mathbfx) leq 0 )inequality constraintsbấ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 )domaintập xác định

Ngoài ra:

Khi (m = p. = 0), vấn đề ((15)) được gọi là unconstrained optimization problem (bài toán về tối ưu không 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 phần nhiều hàm số xuất hiện thêm trong bài toán. Tập hợp những điểm toại ý mọi đk ràng buộc, thông thường, là 1 trong tập con của (mathcalD) được gọi là feasible set hoặc constraint set. Lúc feasible set là một trong tập trống rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Trường hợp một điểm nằm trong feasible set, ta gọi đặc điểm đó là feasible.

2.2. Optimal and locally optimal points

Một điểm (mathbfx^*) được gọi là 1 trong điểm optimal point (điểm về tối ưu), hay là nghiệm của việc ((15)) trường hợp (mathbfx^*) là feasible cùng (f_0(mathbfx^*) = p^*). Tất hợp tất cả các optimal points được điện thoại tư vấn là optimal set.

Nếu optimal set là một trong những tập không rỗng, ta nói vấn đề ((15)) là solvable (giải được). Ngược lại, nếu như optimal set là 1 trong những tập rỗng, ta nói optimal valuekhông thể đạt được (not attained/ not achieved).

Ví dụ: xét hàm phương châm (f(x) = 1/x) với ràng buộc (x > 0). Optimal value của câu hỏi này là (p^* = 0) tuy vậy optimal set là 1 tập rỗng vì không tồn tại giá trị như thế nào của (x) để hàm phương châm đạt quý hiếm 0. Lúc này ta nói giá trị tối ưukhô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ố ví như tại đó, hàm số đạt giá trị bé dại nhất trong một sát bên (và kề bên này ở trong tập xác minh của hàm số). Trong không khí 1 chiều, lân cận được hiểu là trị tuyệt về tối của hiệu 2 điểm nhỏ dại hơn một quý hiếm nào đó.

Trong toán buổi tối ưu (thường là không gian nhiều chiều), ta call một điểm (mathbfx) là locally optimal (cực tiểu) nếu như tồn trên một cực hiếm (thường được call là buôn bán kinh) (R) sao cho:

Nếu một điểm feasible (mathbfx) thoả nguyện (f_i(mathbfx) = 0), ta bảo rằng bất đẳng thức ràng buộc sản phẩm (i: f_i(mathbfx) = 0) là active. Nếu (f_i(mathbfx)

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

Mặc cho 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 những điều kiện nhỏ dại hơn hoặc bằng 0, những bài toán tối ưu với tối nhiều hàm mục tiêu và điều kiện ràng buộc sinh hoạt dạng khác đều rất có thể đưa 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ới (s_i geq 0). (s_i) được điện thoại tư vấn là slack variable. Phép đổi khác đơn giản này trong vô số nhiều trường thích hợp lại tỏ ra công dụng 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. Việc tối ưu lồi

Trong toán tối ưu, chúng ta đặc biệt thân thiện tới những bài toán mà hàm phương châm là một hàm lồi, với feasible set cũng là một trong những tập lồi.

3.1. Định nghĩa

Một bài toán tối ưu lồi (convex optimization problem) là 1 trong những bài toán tối ưu gồm dạng:trong đó (f_0, f_1, dots, f_m) là những hàm lồi.

So với việc tối ưu ((15)), vấn đề tối ưu lồi ((16)) có 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 buộc ràng (h_j) là affine (hàm linear cùng với một hẳng số nữa được hotline là affine).

Một vài nhấn xét:

Tập hợp các điểm ưng ý (h_j(mathbfx) = 0) là 1 trong những tập lồi bởi nó gồm dạng một hyperplane.

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

3.2. Rất tiểu của bài toán tối ưu lồi đó là điểm tối ưu.

TÍnh chất đặc biệt quan trọng nhất của việc tối ưu lồi chính là bất kỳ locally optimal point đó là một điểm (globally) optimal point.

Xem thêm: Hướng Dẫn Cách Gỡ Bỏ Phương Thức Thanh Toán Trên Iphone, Cách Xoá Thẻ Visa Trên Iphone Dễ Dàng

Tính chất đặc biệt quan trọng này bao gồm thể minh chứng bằng phản bệnh như sau. điện thoại tư vấn (mathbfx_0) là 1 trong những điểm locally optimal, tức:

với (R > 0) nào đó. Mang sử (mathbfx_0) chưa phải là globally optimal point, tức mãi sau 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>

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