LINEAR PROGRAMMING LÀ GÌ

     

Tổng vừa lòng Linear Programming Là Gì, Linear Programming / Quy Hoạch con đường Tính là chủ thể trong content bây giờ của blog làm đẹp Reviews. Đọc bài viết để biết cụ thể nhé.

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


1. Ra mắt 1.1. Bài toán nhà xuất bạn dạng 1.2. Vấn đề canh tác 1.3. Bài toán sơ vin đóng thùng 2. đề cập 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 khuyến khích đọc bài xích 16 trước lúc đọc bài này. Văn bản trong nội dung bài viết này đa số được dịch trường đoản cú Chương 4 của cuốn Convex Optimization vào phần tài liệu tham khảo.

Bạn sẽ xem: Linear programming là gì

.

Bài này cũng có không ít khái niệm bắt đầu và nhiều lý thuyết nên rất có thể không lôi kéo như các bài khác. Tuy nhiên, tôi ko thể làm lơ vì không muốn chúng ta hoàn toàn mất phương phía khi đọc những bài sau.

Bạn đọc có thể xem phiên bản pdf trên đây.


Mục Lục


1. Giới thiệu2. Nhắc lại bài toán tối ưu3. Việc tối ưu lồi

1. Giới thiệu

Tôi xin bắt đầu nội dung bài viết này bằng ba bài toán khá ngay gần với thực tế:

1.1. Vấn đề nhà xuất bản

Bài toán

Một công ty xuấn phiên bản (NXB) nhận được đơn hàng 600 bạn dạng của cuốn “Machine Learning cơ bản” tới thái bình và 400 phiên bản tới Hải Phòng. NXB đó có 800 cuốn ngơi nghỉ kho nam giới Định với 700 cuốn nghỉ ngơi kho Hải Dương. Giá chuyển phát một cuốn sách từ nam giới Định tới thái bình là 50,000 VND (50k), tới tp. Hải phòng là 100k. Giá gửi phát một cuốn từ hải dương tới tỉnh thái bình là 150k, trong những lúc tới hải phòng chỉ là 40k. Hỏi để tốn ít giá cả chuyển phân phát nhất, doanh nghiệp đó đề nghị phân phối từng kho chuyển từng nào cuốn tới mỗi địa điểm?

Phân tích

Để cho solo giản, ta kiến tạo 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) con số
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 giá cả (objective function) đang là (f(x, y, z, t) = 5x + 10y + 15z + 4t). Những điều kiện ràng buộc (constraints) viết dưới dạng biểu thức toá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 từ bỏ kho phái nam Định không thực sự 800: (x + y leq 800).

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

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

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

Bài toán NXB:egineqnarray (x, y, z, t) =& argmin_x, y, z, t 5x + 10y + 15z + 4t ~~~~ (1) extsubject to:~ và x + z = 600 ~~~~ (2) và y + t = 400 ~~~~ (3) & x + y leq 800 ~~~(4) và z + t leq 700 ~~~ (5) và x, y, z, t geq 0 ~~~ (6)endeqnarray>

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

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

1.2. Vấn đề canh tác

Bài toán

Một anh dân cày có tổng cộng 10ha (10 hecta) khu đất canh tác. Anh dự trù trồng cà phê và hồ nước tiêu trên số đất này cùng với tổng chi tiêu cho việc trồng này là không thật 16T (triệu đồng). Chi tiêu để trồng cà phê là 2T cho 1ha, để trồng hồ tiêu là 1T/ha/. Thời hạn trồng cà phê là một ngày/ha cùng 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 khoản thời gian trừ toàn bộ các túi tiền (bao gồm túi tiền trồng cây), từng ha cà phê mang đến lợi nhuận 5T, từng ha hồ tiêu đem về lợi nhuận 3T. Hỏi anh đề xuất trồng như thế nào để tối đa lợi nhuận? (Các số liệu có thể vô lý vày chúng đang được lựa chọn để vấn đề ra nghiệm đẹp)

Phân tích

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

Các ràng buộc trong việc này là:

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

Tổng giá cả trồng ko vượt thừa 16T: (2x + y leq 16).

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

Diện tích cà phê 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:egineqnarray (x, y) =& argmax_x, y 5x + 3y ~~~~ (7) extsubject to:~ và x + y leq 10 ~~~~ (8) và 2x + y leq 16 ~~~(9) & x + 4y leq 32 ~~~ (10) và x, y geq 0 ~~~ (11)endeqnarray>

Bài toán này hơi khác một chút ít là ta cần tối nhiều hàm mục tiêu thay bởi tối thiểu nó. Vấn đề chuyển câu hỏi này về vấn đề tối thiểu hoàn toàn có thể được tiến hành đơn giản bằng phương pháp đổi dấu hàm mục tiêu. Khi đó hàm mục tiêu vẫn là linear, các ràng buộc vẫn là các linear constraints, ta lại có một vấn đề Linear Programming (LP) nữa.

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


*

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

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

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

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

1.3. Việc đóng thùng

Bài toán

Một doanh nghiệp phải đưa 400 (m^3) mèo tới địa điểm xây dựng ở bên đó sông bằng cách thuê một loại xà lan. Ngoài ngân sách chi tiêu vận đưa một lượt đi về là 100k của loại xà lan, doanh nghiệp đó phải thiết kế một thùng hình hộp chữ nhật ném lên xà lan để đựng cát. Mẫu thùng này không cần nắp, giá thành cho các mặt bao phủ là 1T/(m^2), cho mặt đáy là 2T/(m^2). Hỏi size của loại thùng đó như thế nào để tổng túi tiền vận gửi là bé dại nhất. Để cho 1-1 giản, mang sử cat chỉ được đổ ngang hoặc thấp hơn với phần trên của thành thùng, không tồn tại ngọn. Trả sử thêm rằng xà lan rộng vô hạn và cất được sức nặng nề vô hạn, đưa sử này khiến cho bài toán dễ giải hơn.

Phân tích

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

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

Chi giá tiền làm thùng: diện tích s xung xung quanh của thùng là (2 (x + y)z ). Diện tích s đáy là (xy). Vậy tổng giá thành làm thùng là (2(x +y)z + 2xy = 2(xy + yz + zx)).

Tổng toàn bộ giá cả là (f(x, y, z) = 40x^-1y^-1z^-1 + 2(xy + yz + zx)). Điều kiện ràng buộc tốt nhất là form size thùng bắt buộc là các số dương. Vậy ta có việc tối ưu sau:

Bài toán vận chuyển:egineqnarray (x, y) =& argmin_x, y, z 40x^-1y^-1z^-1 + 2(xy + yz + zx) ~~~~ (13) extsubject to:~ & x, y, z > 0 ~~~~ (14)endeqnarray>

Bài toán này thuộc các loại Geometric Programming (GP). Định nghĩa của GP và phương pháp dùng cơ chế tối ưu đã được trình bày trong phần sau của bài xích viết.

Xem thêm: Hạn Tam Tai Là Gì ? Cách Tính Và Hóa Giải Tam Tai Ra Sao? Cách Tính Và Hóa Giải Tam Tai Ra Sao

Nhận thấy rằng bài bác này hoàn toàn có thể dùng bất đẳng thức Cauchy nhằm giải được, nhưng lại tôi vẫn ước ao một lời giải cho việc tổng quát tháo sao cho có thể lập trình được.

(Lời giải:egineqnarray f(x, y, z) &=& frac20xyz + frac20xyz + 2xy + 2yz + 2zx &geq & 5sqrt3200endeqnarray>dấu bằng xẩy ra khi còn chỉ khi (x = y = z = sqrt10). Bài xích này có lẽ hợp với những kỳ thi vì chưng dữ khiếu nại quá đẹp. Cá thể tôi thích những đề bài bác ra mẫu mã này hơn là yêu cầu đi kiếm giá trị bé 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ần khần học bất đẳng thức để làm gì!)

Nếu có những ràng buộc về kích cỡ của thùng và trọng lượng cơ mà xà lan download được thì hoàn toàn có thể tìm được lời giải đơn giản như nuốm này không?

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

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

2. đề cập lại việc tối ưu

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

Tôi xin kể lại câu hỏi tối ưu sinh sống dạng tổng quát:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(15)&& h_j(mathbfx) = 0, ~~ j = 1, 2, dots, pendeqnarray>

Phát biểu bằng lời: Tìm quý giá của biến hóa (mathbfx) để về tối thiểu hàm (f_0(mathbfx)) trong số 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 bao gồm bảng các tên thường gọi tiếng Anh cùng tiếng Việt như sau:

ký hiệu giờ đồng hồ 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 = phường = 0), câu hỏi ((15)) được hotline là unconstrained optimization problem (bài toán tối ưu ko ràng buộc).

(mathcalD) chỉ cần tập xác định, tức giao của tất cả các tập xác minh của đều hàm số mở ra trong bài toán. Tập hợp các điểm bằng lòng mọi đk ràng buộc, thông thường, là 1 tập bé của (mathcalD) được gọi là feasible set hoặc constraint set. Khi feasible set là 1 trong tập rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Nếu như một điểm bên 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 những nghiệm của vấn đề ((15)) nếu (mathbfx^*) là feasible với (f_0(mathbfx^*) = p^*). Vớ hợp toàn bộ 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 bài toán ((15)) là solvable (giải được). Ngược lại, nếu như optimal set là một 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 mục tiêu (f(x) = 1/x) với buộc ràng (x > 0). Optimal value của việc này là (p^* = 0) dẫu vậy optimal set là một tập trống rỗng vì không tồn tại giá trị nào của (x) để hàm phương châm đạt cực hiếm 0. Lúc này ta nói giá trị buổi 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á bán trị nhỏ dại nhất trong một lân cận (và lân cận này nằm trong tập xác minh của hàm số). Trong không khí 1 chiều, lân cận được gọi là trị tuyệt về tối của hiệu 2 điểm nhỏ 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) giả dụ tồn tại một quý giá (thường được gọi là bán kinh) (R) sao cho:egineqnarray f_0(mathbfx) = &extinff_0(mathbfz) endeqnarray>

Nếu một điểm feasible (mathbfx) thoả mã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 lại ý

Mặc mặc dù trong định nghĩa việc tối ưu ((15)) là cho việc tối thiểu hàm mục tiêu với những ràng buộc thoả mãn các điều kiện nhỏ hơn hoặc bằng 0, các bài toán buổi tối ưu với tối nhiều hàm mục tiêu và đk ràng buộc nghỉ ngơi dạng không giống đề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 ) cùng (s_i geq 0). (s_i) được điện thoại tư vấn là slack variable. Phép biến hóa đơn giản này trong nhiều trường phù hợp lại tỏ ra hiệu quả vì bất đẳng thức (s_i geq 0) hay dễ giải quyết hơn là (f_i(mathbfx) leq 0).

3. Câu hỏi tối ưu lồi

Trong toán buổi tối ưu, bọn họ đặc biệt ân cần tới những việc mà hàm kim chỉ nam là một hàm lồi, cùng feasible set cũng là 1 trong 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 buổi tối ưu bao gồm dạng:egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(16)&& mathbfa_j^Tmathbfx – b_j = 0, j = 1, dots,endeqnarray>trong đó (f_0, f_1, dots, f_m) là những hàm lồi.

So với việc tối ưu ((15)), việc 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à một 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 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 nhận xét:

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

Vậy, vào một việc tối ưu lồi, ta tối thiểu một hàm phương châm lồi bên trên một tập lồi.

3.2. Rất tiểu của việc tối ưu lồi đó là điểm buổi tối ưu.

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

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

với (R > 0) nào đó. Trả sử (mathbfx_0) không phải là globally optimal point, tức sống thọ một feasible point (mathbfy) làm sao cho (f(mathbfy) &leq& (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 đưa thiết (mathbfx_0) là một trong những điểm rất tiểu. Vậy trả sử sai, tức (mathbfx_0) chính là globally optimal point với ta bao gồm điều buộc phải chứng minh.

Chứng minh bởi lời: đưa sử một điểm cực tiểu ko phải là điểm làm mang đến hàm số đạt giá trị nhỏ tuổi nhất. Với điều kiện feasible sethàm mục tiêu là lồi, ta luôn tìm được một điểm khác trong ở kề bên của điểm rất tiểu đó sao cho giá trị của hàm kim chỉ nam tại điểm bắt đầu này bé dại hơn quý hiếm của hàm kim chỉ nam tại điểm rất tiểu. Sự mâu thuẫn này cho rằng với một việc tối ưu lồi, điểm rất tiểu phải là điểm làm đến hàm số đạt giá bán trị nhỏ dại nhất.

Xem thêm: Dịch Từ " After Là Gì ? Cấu Trúc After Bạn Cần Nắm Vững Dịch Từ After Từ Anh Sang Việt

3.3. Điều kiện buổi tối ưu mang đế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 mọi (mathbfx, mathbfy in extdomf_0), ta có:

Đặt (mathcalX) là feasible set. Điều kiện buộc 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 điều kiện yêu cầu và đủ này, các bạn đọc có thể tìm vào trang 139-140 của cuốn Convex Optimization trong tài liệu tham khảo.