Tối ưu hóa được vận dụng trong nhiều nghành nghề như sản xuất, gớm tế, tài chính, điều khiển, thống kê, giao thông, v.v…. Phần này xin reviews về câu hỏi quy hoạch đường tính, một lĩnh vực đặc trưng của về tối ưu hóa.
Bạn đang xem: Bài toán quy hoạch tuyến tính
Bài toán quy hoạch tuyến đường tínhBài toán tối ưu tổng quát tất cả dạng như sau: <eginaligned mminimize~ & f_0(x)\ msubject~to~ &f_i(x) leq b_i ,i=1,…,m.endaligned> vào đó, vector (x=(x_1,ldots,x_n)in mathbfR^n) là vươn lên là số. Hàm (f_0(x)) được call là hàm mục tiêu. Tất cả (m) ràng buộc trong câu hỏi tối ưu trên. Ràng buộc trang bị (i) là (f_i(x) leq b_i).
Ta hoàn toàn có thể đưa một việc tối ưu ngẫu nhiên về dạng như trên. Nếu câu hỏi tối ưu là về tối đa hóa hàm phương châm (f_0(x)), ví dụ về tối đa hóa lợi nhuận, thì ta rất có thể thay hàm mục tiêu bằng (min. -f_0(x)). Các ràng buộc cũng rất có thể đưa về dạng như trên.
Ta cần một trong những định nghĩa trước sau khi ra mắt về vấn đề quy hoạch con đường tính:
Siêu phẳng (hyperplane) là tập hợp các điểm thỏa mãn (a^T x = b).Nửa không gian (half space) định nghĩa vì siêu phẳng (a^T x leq b), (x in mathbfR^n) (xem Hình 1. Vì thế siêu phẳng (a^T x = b) vẫn chia không khí (mathbfR^n) ra thành nhị nửa không khí (a^T x leq b) với (a^T x geq b)
Bài toán quy hoạch đường tính là 1 bài toán buổi tối ưu trong số ấy các hàm kim chỉ nam và hàm ràng buộc (f_i(x), i=0,ldots,m) đều sở hữu dạng tuyến đường tính: <eginaligned mminimize~ &c^Tx qquad qquad qquad qquad (1)\ msubject~to~ &a_i^Tx leq b_i ,i=1,ldots, m.endaligned> Ta cũng rất có thể biểu diễn ràng buộc dạng ma trận (Ax leq b), trong đó (c,a_1,ldots,a_m in mathbfR^n), (A=left<eginmatrixa_1^T\ldots\a_m^Tendmatrix ight>), với (b=left<eginmatrixb_1\ldots\b_mendmatrix ight>).
Sau đây là vài lấy một ví dụ về vấn đề quy hoạch con đường tính.
Xem thêm: Cách Ủ Lạnh Tóc Như Thế Nào, Cách Ủ Tóc Mềm Mượt Đúng Chuẩn Ai Cũng Phải Biết!
Ví dụ 1
<eginalignedmathrmmin.~ và f = x_1+x_2 qquad qquad qquad qquad (2)labeleq:chap1_ex1\mathrms.t.~ và x_1+2x_2geq 2, onumber\& 3x_1+x_2geq 2, onumber\& x_1 geq 0, onumber\& x_2 geq 0. onumber endaligned>
Hình 2 miêu tả hàm phương châm và miền khả thi (feasible region) của bài toán trên khiến cho bạn đọc có cảm hứng về nghiệm của bài toán tối ưu. Miền khả thi có nghĩa là tập hợp những điểm thỏa mãn nhu cầu các ràng buộc. Miền khả thi của một việc quy hoạch con đường tính là một trong những đa diện (polyhedron).
Trong những sách về quy hoạch tuyến đường tính truyền thống lâu đời mà lời giải đơn hình (simplex) được giới thiệu như một phương pháp chính để giải bài xích toán, bài toán LP được trình làng ở dạng chính tắc như sau: <eginaligned mmaximize~ &c^Tx qquad qquad qquad qquad (2)\ msubject~to~ &a_i^Tx leq b_i ,i=1,ldots, m\& x geq 0.labeleq-standardLPendaligned> vấn đề dạng chủ yếu tắc là nguồn vào của giải thuật đơn hình.
Thực ra, ta có thể thay đổi một việc LP bất kỳ về dạng thiết yếu tắc (2), ví dụ như như:
Nếu hàm mục tiêu là ( mmin.~c^Tx) thì hoàn toàn có thể thay bằng ( mmax.~ -c^Tx).Nếu ràng buộc là (a_i^Tx geq b_i) thì hoàn toàn có thể thay bằng (-a_i^Tx leq -b_i).Nếu buộc ràng là (a_i^Tx = b_i) thì hoàn toàn có thể thay bởi hai ràng buộc tương đương: (a_i^Tx geq b_i) cùng (a_i^Tx leq b_i).Nếu không tồn tại ràng buộc (x_i geq 0) thì có thể thay trở nên (x_i = x_i^+ – x_i^-), trong những số ấy (x_i^+, x_i^- geq 0).Ví dụ 2 – câu hỏi dinh dưỡng
Để bảo đảm được dinh dưỡng, một fan trung bình cần cho mỗi ngày:
Không thấp hơn 200 gam chất bột đường (carbohydrate)Không ít hơn 20 gam chất đạm (protein)Hàm lượng dinh dưỡng những chất này vào 04 một số loại lương thực hiện có vào một shop trong 1000 gram được liệt kê làm việc bảng sau:
| Cà rốt | 300 | 30 | 50 |
| Gạo | 400 | 10 | 20 |
| Khoai tây | 400 | 20 | 10 |
| Bột mì | 500 | 50 | 30 |
Ghi chú: các số liệu trên chỉ dùng để minh họa cho ví dụ.
Như vậy người đó cần tối thiểu là bao nhiêu tiền đề bảo đảm được bồi bổ cho bữa ăn. Việc dinh chăm sóc được mô hình dưới dạng bài toán quy doạch tuyến tính như sau: hotline (x_c, x_g, x_k, x_b) là số gram cà rốt, gạo, khoai tây với bột mì đề xuất mua. Hàm mục tiêu là tổng số tiền: <eginaligned50x_c+20x_g+10x_k+30x_bendaligned> các ràng buộc bao gồm:
Đảm bảo về hàm vị bột đường: <eginaligned300x_c+400x_g+400x_k+500x_b geq 200endaligned>Đảm bảo về hàm lượng đạm: <eginaligned30x_c+10x_g+20x_k+50x_bgeq20endaligned>Ngoài ra còn tồn tại ràng buộc không âm cho các biến: (x_cgeq0, x_g geq 0,x_k geq 0,x_bgeq0).Như vậy, câu hỏi quy hoạch tuyến đường tính cho dinh dưỡng sẽ là: <eginalignedmathrmmin.~& 50x_c+20x_g+10x_k+30x_b qquad qquad qquad qquad (3)\mathrms.t.~ & 300x_c+400x_g+400x_k+500x_bgeq200, onumber\& 30x_c+10x_g+20x_k+50x_bgeq20, onumber\& x_cgeq0, x_ggeq0,x_kgeq0,x_bgeq0. onumber endaligned>
Giải việc quy hoạch tuyến đường tính bởi CVXPY solver
Có nhiều thư viện có thể chấp nhận được giải một việc quy hoạch tuyến tính. Sách này xin ra mắt thư viện CVXPY cần sử dụng trong ngôn từ Python.
