Bài Toán Quy Hoạch Tuyến Tính Dạng Chính Tắc
Tổng quát những bài toán thù quy hoạch tuyến tính cụ thể trên, một bài toán quy hoạch tuyến tính là một mô hình tân oán tra cứu cực tiểu (min) hoặc cực đại (max) của hàm mục tiêu tuyến tính với những ràng buộc là bất đẳng thức cùng đẳng thức tuyến tính. Dạng tổng quát của một bài xích tân oán quy hoạch tuyến tính là :
Trong đó :
(I) Hàm mục tiêu
Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng làm sao đó mà ta cần phải quan tâm của bài bác toán.
Bạn đang xem: Bài toán quy hoạch tuyến tính dạng chính tắc
(II) Các ràng buộc của bài xích toán
Là các phương trình hoặc bất phương trình tuyến tính n biến số, xuất hiện từ điều kiện của bài bác toán thù.
(III) Các những hạn chế về dấu của những biến số
Người ta cũng thường trình bày bài bác toán quy hoạch tuyến tính dưới dạng ma trận như sau :
Gọi ai (i=1→m) thuộc dòng thứ i của ma trận A, ta bao gồm :
Người ta gọi :
- A là ma trận hệ số các ràng buộc.
- c là vectơ chi phí (cT là chuyển vị của c)
- b là vectơ giới hạn các ràng buộc.
Quy hoạch tuyến tính dạng bao gồm tắc
Bài tân oán quy hoạch tuyến tính chính tắc là bài bác tân oán quy hoạch tuyến tính mà trong đó các ràng buộc chỉ bao gồm dấu = cùng những biến số đều ko âm.
Người ta có thể biến đổi bài bác tân oán quy hoạch tuyến tính dạng tổng quát tháo thành bài tân oán quy hoạch tuyến tính dạng chính tắc nhờ các quy tắc sau đây :
- Nếu gặp ràng buộc i tất cả dạng ≤ thì người ta cộng phân phối vế trái của ràng buộc một biến phụ xn+i ≥ 0 để được dấu = .
Xem thêm: Là Gì? Nghĩa Của Từ Rvp Là Gì ''Scheme'' Trong Rap Là Gì
- Nếu gặp ràng buộc i gồm dạng ≥ thì người ta trừ vào vế trái của ràng buộc một biến phụ xn+i ≥ 0 để được dấu = .
Các biến phụ chỉ là những đại lượng giúp chúng ta biến các ràng buộc dạng bất đẳng thức thành đẳng thức, nó phải không ảnh hưởng gì đến hàm mục tiêu yêu cầu ko xuất hiện vào hàm mục tiêu.
- Nếu biến xj ≤ 0 thì ta đặt xj = -x’j với x’j ≥ 0 rồi nỗ lực vào bài tân oán.
- Nếu biến xj là tuỳ ý thì ta đặt
- Trong trường hợp vào số những ràng buộc bao gồm chiếc nhưng vế phải của mẫu đó là giá trị âm thì đổi dấu cả nhị vế để được vế phải là một giá bán trị ko âm.
Dựa vào những phxay biến đổi bên trên nhưng người ta gồm thể nói rằng b ài toán quy hoạch tuyến tính chính tắc là bài bác toán quy hoạch tuyến tính nhưng vào đó những ràng buộc chỉ bao gồm dấu = , vế phải và những biến số đều ko âm.
Xem thêm: Bột Ngọt ( Msg Là Gì Và Nó Được Làm Như Thế Nào? Msg Có Thực Sự Không Tốt Như Lời Đồn
Ví dụ :
Biến đổi bài toán thù quy hoạch tuyến tính sau đây về dạng chủ yếu tắc :
Bằng những vắt thế :
ta được :
hay :
Phương án
Xét bài toán quy hoạch tuyến tính bao gồm tắc :
Một phương án tối ưu của (P) là một phương án khả thi của (P) cơ mà giá bán trị của hàm mục tiêu tương ứng đạt min/max.
