Bạn được khuyến khích đọc Bài 16 trước khi đọc bài này. Nội dung trong bài viết này chủ yếu được dịch từ Chương 4 của cuốn Convex Optimization trong phần Tài liệu tham khảo.
Bạn đang xem: Linear programming là gì
.
Bài này cũng có rất nhiều khái niệm mới và nhiều lý thuyết 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ể bỏ qua vì không muốn các bạn hoàn toàn mất phương hướng khi đọc các bài sau.
Bạn đọc có thể xem bản pdf tại đây.
1. Giới thiệu
Tôi xin bắt đầu bài viết này bằng ba bài toán khá gần với thực tế:
1.1. Bài toán nhà xuất bản
Bài toán
Một nhà xuấn bản (NXB) nhận được đơn hàng 600 bản của cuốn “Machine Learning cơ bản” tới Thái Bình và 400 bản tới Hải Phòng. NXB đó có 800 cuốn ở kho Nam Định và 700 cuốn ở kho Hải Dương. Giá chuyể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 Hải Phòng là 100k. Giá chuyển phát một cuốn từ Hải Dương tới Thái Bình là 150k, trong khi tới Hải Phòng chỉ là 40k. Hỏi để tốn ít chi phí chuyển phát nhất, công ty đó nên 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 đơn giản, ta xây dựng bảng số lượng chuyển sách từ nguồn tới đích như sau:
| 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 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 là:
Chuyển 600 cuốn 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 quá 800: (x + y leq 800).
Lấy từ 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ố tự nhiên sẽ khiến cho bài toán rất khó giải nếu số lượng biến là rất lớn. Với bài toán 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 chúng không phải là số tự nhiên, ta sẽ lấy các giá trị tự nhiên gần nhất.
Vậy ta cần giải bài toán tối ưu sau đây:
Bài toán NXB:egin{eqnarray} (x, y, z, t) =& argmin_{x, y, z, t} 5x + 10y + 15z + 4t ~~~~ (1) ext{subject to:}~ & x + z = 600 ~~~~ (2) & y + t = 400 ~~~~ (3) & x + y leq 800 ~~~(4) & z + t leq 700 ~~~ (5) & x, y, z, t geq 0 ~~~ (6)end{eqnarray}>
Nhận thấy rằng hàm mục tiêu (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, đều là các ràng buộc tuyến tính (linear constraints). Bài toán tối ưu với cả objective function và constraints đều là linear được gọi là Linear Programming (LP). Dạng tổng quát và cách thức lập trình để giải một bài toán thuộc loại này sẽ được 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 ngay là (x = 600, y = 0, z = 0, t = 400). Nếu ràng buộc nhiều hơn và số biến 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. Bài toán canh tác
Bài toán
Một anh nông dân có tổng cộng 10ha (10 hecta) đất canh tác. Anh dự tính trồng cà phê và hồ tiêu trên số đất này với tổng chi phí cho việc trồng này là không quá 16T (triệu đồng). Chi phí để trồng cà phê là 2T cho 1ha, để trồng hồ tiêu là 1T/ha/. Thời gian trồng cà phê là 1 ngày/ha và hồ tiêu là 4 ngày/ha; trong khi anh chỉ có thời gian tổng cộng là 32 ngày. Sau khi trừ tất cả các chi phí (bao gồm chi phí trồng cây), mỗi ha cà phê mang lại lợi nhuận 5T, mỗi ha hồ tiêu mang lại lợi nhuận 3T. Hỏi anh phải trồng như thế nào để tối đa lợi nhuận? (Các số liệu có thể vô lý vì chúng đã được chọn để bài toán ra nghiệm đẹp)
Phân tích
Gọi (x) và (y) lần lượt là số ha cà phê và hồ tiêu mà anh nông dân nên trồng. Lợi nhuận anh ấy thu được là (f(x, y) = 5x + 3y) (triệu đồng).
Các ràng buộc trong bài toán này là:
Tổng diện tích trồng không vượt quá 10: (x + y leq 10).
Tổng chi phí trồng không vượt quá 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ồ tiêu là các số không âm: (x, y geq 0).
Vậy ta có bài toán tối ưu sau đây:
Bài toán canh tác:egin{eqnarray} (x, y) =& argmax_{x, y} 5x + 3y ~~~~ (7) ext{subject to:}~ & x + y leq 10 ~~~~ (8) & 2x + y leq 16 ~~~(9) & x + 4y leq 32 ~~~ (10) & x, y geq 0 ~~~ (11)end{eqnarray}>
Bài toán này hơi khác một chút là ta cần tối đa hàm mục tiêu thay vì tối thiểu nó. Việc chuyển bài toán này về bài toán tối thiểu có thể được thực hiện đơn giản bằng cách đổ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 bài toán Linear Programming (LP) nữa.
Bạn cũng có thể dựa vào hình minh hoạ dưới đây để suy ra nghiệm của bài toán:
Vùng màu xám có dạng polyhedron (trong trường 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 từ (8)) đến ((11)). Các đường nét đứt có màu chính là các đường đồng mức của hàm mục tiêu (5x + 3y), mỗi đường ứng với một giá trị khác nhau với đường càng đỏ ứng với giá trị càng cao. Một cách trực quan, nghiệm của bài toán có thể tìm được bằng cách 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 mục tiêu lớn hơn) đến khi nó không còn điểm chung với phần đa giác màu xám nữa.
Có thể nhận thấy nghiệm của bài toán chính là điểm màu xanh là giao điểm của hai đường thẳng (x + y = 10) và (2x + y = 16). Giải hệ phương trình này ta có (x^* = 6) và (y^* = 4). Tức anh nông dân nên trồng 6ha cà phê và 4ha hồ tiêu. Lúc đó lợi nhuận 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 ít, hưởng nhiều).
Đây chính là cách giải trong sách toán lớp 10 (ngày tôi học lớp 10).
Với nhiều biến hơn và nhiều ràng buộc hơn, chúng ta liệu có thể vẽ được hình như thế này để nhìn ra nghiệm hay không? Câu trả lời của tôi là nên tìm một công cụ để với nhiều biến hơn và với các ràng buộc khác nhau, chúng ta có thể tìm ra nghiệm gần như ngay lập tức.
1.3. Bài toán đóng thùng
Bài toán
Một công ty phải chuyển 400 (m^3) cát tới địa điểm xây dựng ở bên kia sông bằng cách thuê một chiếc xà lan. Ngoài chi phí vận chuyển một lượt đi về là 100k của chiếc xà lan, công ty đó phải thiết kế một thùng hình hộp chữ nhật đặt trên xà lan để đựng cát. Chiếc thùng này không cần nắp, chi phí cho các mặt xung quanh là 1T/(m^2), cho mặt đáy là 2T/(m^2). Hỏi kích thước của chiếc thùng đó như thế nào để tổng chi phí vận chuyển là nhỏ nhất. Để cho đơn giản, giả sử cát chỉ được đổ ngang hoặc thấp 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à chứa được sức nặng vô hạn, giả sử này khiến bài toán dễ giải hơn.
Phân tích
Giả sử chiếc thùng cần làm có chiều dài 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)). Có hai loại chi phí là:
Chi phí thuê xà lan: số chuyến xà lan phải thuê là (frac{400}{xyz}) (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ì chi phí vận chuyển một chuyến là nhỏ so với chi phí làm thùng). Số tiền phải trả cho xà lan sẽ là (0.1frac{400}{xyz} = frac{40}{xyz}).
Chi phí làm thùng: Diện tích 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)).
Tổng toàn bộ chi phí là (f(x, y, z) = 40x^{-1}y^{-1}z^{-1} + 2(xy + yz + zx)). Điều kiện ràng buộc duy nhất là kích thước thùng phải 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:egin{eqnarray} (x, y) =& argmin_{x, y, z} 40x^{-1}y^{-1}z^{-1} + 2(xy + yz + zx) ~~~~ (13) ext{subject to:}~ & x, y, z > 0 ~~~~ (14)end{eqnarray}>
Bài toán này thuộc loại Geometric Programming (GP). Định nghĩa của GP và cách dùng công cụ tối ưu sẽ được trình bày trong phần sau của bài viết.
Xem thêm: Endocytosis Là Gì – Endocytosis, Phagocytosis, And Pinocytosis Video
Nhận thấy rằng bài này hoàn toàn có thể dùng bất đẳng thức Cauchy để giải được, nhưng tôi vẫn muốn một lời giải cho bài toán tổng quát sao cho có thể lập trình được.
(Lời giải:egin{eqnarray} f(x, y, z) &=& frac{20}{xyz} + frac{20}{xyz} + 2xy + 2yz + 2zx &geq & 5sqrt{3200}end{eqnarray}>dấu bằng xảy ra khi và chỉ khi (x = y = z = sqrt{10}). Bài này có lẽ hợp với các kỳ thi vì dữ kiện quá đẹp. Cá nhân tôi thích các đề bài ra kiểu này hơn là yêu cầu đi tìm giá trị nhỏ nhất của một biểu thức nhàm chán, nhiều học sinh cho rằng không biết học bất đẳng thức để làm gì!)
Nếu có các ràng buộc về kích thước của thùng và trọng lượng mà xà lan tải được thì có thể tìm được lời giải đơn giản như thế này không?
Những bài toán trên đây đều là các bài toán tối ưu. Chính xác hơn nữa, chúng đều là các 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 lời giải có thể không mấy khó khăn, thậm chí giải bằng tay cũng có thể ra kết quả. Tuy nhiên, mục đích của bài viết này không phải là hướng dẫn các bạn giải các bài toán trên bằng tay, mà là cách nhận diện các bài toán và đưa chúng về các dạng mà các toolboxes sẵn có có thể giúp chúng ta. Trên thực tế, lượng dữ kiện và số biến cần tối ưu lớn hơn nhiều, chúng ta không thể giải các bài toán trên bằng tay được.
Trước hết, chúng ta cần hiểu các khái niệm về convex optimization problems và tại sao convex lại quan trọng. (Bạn đọc có thể đọc tới phần 4 nếu không muốn biết các khái niệm và định lý toán trong phần 2 và 3.)
2. Nhắc lại bài toán tối ưu
2.1. Các khái niệm cơ bản
Tôi xin nhắc lại bài toán tối ưu ở dạng tổng quát:egin{eqnarray}mathbf{x}^* &=& argmin_{mathbf{x}} f_0(mathbf{x}) text{subject to:}~ && f_i(mathbf{x}) leq 0, ~~ i = 1, 2, dots, m ~~~(15)&& h_j(mathbf{x}) = 0, ~~ j = 1, 2, dots, pend{eqnarray}>
Phát biểu bằng lời: Tìm giá trị của biến (mathbf{x}) để tối thiểu hàm (f_0(mathbf{x})) trong số các giá trị của (mathbf{x}) thoả mãn các điệu hiện ràng buộc. Ta có bảng các tên gọi tiếng Anh và tiếng Việt như sau:
| (mathbf{x} in mathbb{R}^n) | optimization variable | biến tối ưu |
| (f_0: mathbb{R}^n ightarrow mathbb{R}) | objective/los/cost function | hàm mục tiêu |
| (f_i(mathbf{x}) leq 0 ) | inequality constraints | bất đẳng thức ràng buộc |
| (f_i: mathbb{R}^n ightarrow mathbb{R}) | inequality constraint functions | – |
| (h_j(mathbf{x}) = 0 ) | equality constraints | đẳng thức ràng buộc |
| (h_j: mathbb{R}^n ightarrow mathbb{R}) | equality constraint functions | – |
| (mathcal{D} = igcap_{i=0}^m ext{dom}f_i cap igcap_{pj=1}^p ext{dom}h_i ) | domain | tập xác định |
Ngoài ra:
Khi (m = p = 0), bài toán ((15)) được gọi là unconstrained optimization problem (bài toán tối ưu không ràng buộc).
(mathcal{D}) chỉ là tập xác định, tức giao của tất cả các tập xác định của mọi hàm số xuất hiện trong bài toán. Tập hợp các điểm thoả mãn mọi điều kiện ràng buộc, thông thường, là một tập con của (mathcal{D}) được gọi là feasible set hoặc constraint set. Khi feasible set là một tập rỗng thì ta nói bài toán tối ưu ((15)) là infeasible. Nếu một điểm nằm trong feasible set, ta gọi điểm đó là feasible.
2.2. Optimal and locally optimal points
Một điểm (mathbf{x}^*) được gọi là một điểm optimal point (điểm tối ưu), hoặc là nghiệm của bài toán ((15)) nếu (mathbf{x}^*) là feasible và (f_0(mathbf{x}^*) = p^*). Tất hợp tất cả các optimal points được gọi là optimal set.
Nếu optimal set là một 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 optimal set là một tập rỗng, ta nói optimal value là không thể đạt được (not attained/ not achieved).
Ví dụ: xét hàm mục tiêu (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) nhưng optimal set là một tập rỗng vì không có giá trị nào của (x) để hàm mục tiêu đạt giá trị 0. Lúc này ta nói giá trị tối ưu là khô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ố nếu tại đó, hàm số đạt giá trị nhỏ nhất trong một lân cận (và lân cận này thuộc tập xác định của hàm số). Trong không gian 1 chiều, lân cận được hiểu là trị tuyệt tối của hiệu 2 điểm nhỏ hơn một giá trị nào đó.
Trong toán tối ưu (thường là không gian nhiều chiều), ta gọi một điểm (mathbf{x}) là locally optimal (cực tiểu) nếu tồn tại một giá trị (thường được gọi là bán kinh) (R) sao cho:egin{eqnarray} f_0(mathbf{x}) = & ext{inf}{f_0(mathbf{z}) | f_i(mathbf{z}) leq 0, i = 1, dots, m, & h_j(mathbf{z}) = 0, j = 1, dots, p, ||mathbf{z} – mathbf{x}||_2 leq R}end{eqnarray}>
Nếu một điểm feasible (mathbf{x}) thoả mãn (f_i(mathbf{x}) = 0), ta nói rằng bất đẳng thức ràng buộc thứ (i: f_i(mathbf{x}) = 0) là active. Nếu (f_i(mathbf{x})
2.3. Một vài lưu ý
Mặc 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 các điều kiện nhỏ hơn hoặc bằng 0, các bài toán tối ưu với tối đa hàm mục tiêu và điều kiện ràng buộc ở dạng khác đều có thể đưa về được dạng này:
(max f_0(mathbf{x}) Leftrightarrowmin -f_0(mathbf{x}) ).
(f_i(mathbf{x}) leq g(mathbf{x}) Leftrightarrow f_i(mathbf{x}) – g(mathbf{x}) leq 0).
(f_i(mathbf{x}) geq 0 Leftrightarrow -f_i(mathbf{x}) leq 0 ).
(a leq f_i(mathbf{x}) leq b Leftrightarrow f_i(mathbf{x}) -b leq 0) và (a – f_i(mathbf{x}) leq 0).
(f_i(mathbf{x}) leq 0 Leftrightarrow f_i(mathbf{x}) + s_i = 0 ) và (s_i geq 0). (s_i) được gọi là slack variable. Phép biến đổi đơn giản này trong nhiều trường hợp lại tỏ ra hiệu quả vì bất đẳng thức (s_i geq 0) thường dễ giải quyết hơn là (f_i(mathbf{x}) leq 0).
3. Bài toán tối ưu lồi
Trong toán tối ưu, chúng ta đặc biệt quan tâm tới những bài toán mà hàm mục tiêu là một hàm lồi, và feasible set cũng là một tập lồi.
3.1. Định nghĩa
Một bài toán tối ưu lồi (convex optimization problem) là một bài toán tối ưu có dạng:egin{eqnarray}mathbf{x}^* &=& argmin_{mathbf{x}} f_0(mathbf{x}) text{subject to:}~ && f_i(mathbf{x}) leq 0, ~~ i = 1, 2, dots, m ~~~(16)&& mathbf{a}_j^Tmathbf{x} – b_j = 0, j = 1, dots,end{eqnarray}>trong đó (f_0, f_1, dots, f_m) là các hàm lồi.
So với bài toán tối ưu ((15)), bài toán tối ưu lồi ((16)) có thêm ba điều kiện nữa:
Hàm mục tiêu là một hàm lồi.
Các hàm bất đẳng thức ràng buộc (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 một hẳng số nữa được gọi là affine).
Một vài nhận xét:
Tập hợp các điểm thoả mãn (h_j(mathbf{x}) = 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 thiểu một hàm mục tiêu lồi trên một tập lồi.
3.2. Cực tiểu của bài toán tối ưu lồi chính là điểm tối ưu.
TÍnh chất quan trọng nhất của bài toán tối ưu lồi chính là bất kỳ locally optimal point chính là một điểm (globally) optimal point.
Tính chất quan trọng này có thể chứng minh bằng phản chứng như sau. Gọi (mathbf{x}_0) là một điểm locally optimal, tức:
với (R > 0) nào đó. Giả sử (mathbf{x}_0) không phải là globally optimal point, tức tồn tại một feasible point (mathbf{y}) sao cho (f(mathbf{y}) &leq& (1 – heta)f_0(mathbf{x}_0) + heta f_0(mathbf{y}) & &=& f_0(mathbf{x}_0)end{eqnarray}>
điều này mâu thuẫn với giả thiết (mathbf{x}_0) là một điểm cực tiểu. Vậy giả sử sai, tức (mathbf{x}_0) chính là globally optimal point và ta có điều phải chứng minh.
Chứng minh bằng lời: giả sử một điểm cực tiểu không phải là điểm làm cho hàm số đạt giá trị nhỏ nhất. Với điều kiện feasible set và hàm mục tiêu là lồi, ta luôn tìm được một điểm khác trong lân cận của điểm cực tiểu đó sao cho giá trị của hàm mục tiêu tại điểm mới này nhỏ hơn giá trị của hàm mục tiêu tại điểm cực tiểu. Sự mâu thuẫn này chỉ ra rằng với một bài toán tối ưu lồi, điểm cực tiểu phải là điểm làm cho hàm số đạt giá trị nhỏ nhất.
Xem thêm: Garment Là Gì – Tiếng Anh Chuyên Ngành May Mặc
3.3. Điều kiện tối ưu cho hàm mục tiêu khả vi
Nếu hàm mục tiêu (f_0) là khả vi (differentiable), theo first-order condition, với mọi (mathbf{x}, mathbf{y} in ext{dom}f_0), ta có:
Đặt (mathcal{X}) là feasible set. Điều kiện cần và đủ để một điểm (mathbf{x}_0 in mathcal{X}) là optimal point là:Tôi xin được bỏ qua việc chứng minh điều kiện cần và đủ này, bạn đọc có thể tìm trong trang 139-140 của cuốn Convex Optimization trong Tài liệu tham khảo.
Chuyên mục: Hỏi Đáp
