Tổng quát tháo những câu hỏi quy hoạch tuyến tính cụ thể trên, một việc quy hoạch tuyến tính là một mô hình toán tìm kiếm 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 các ràng buộc là bất đẳng thức với đẳng thức tuyến tính. Dạng tổng quát mắng của một câu hỏi 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 nào đó nhưng mà ta cần phải thân thiết của bài xích toán.
(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ố, ra đời từ điều kiện của bài toán.
(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 diễn bài 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 tất cả :
Người ta gọi :
- A là ma trận hệ số các ràng buộc.
- c là vectơ giá thành (cT là chuyển vị của c)
- b là vectơ giới hạn những ràng buộc.
Quy hoạch tuyến tính dạng thiết yếu tắc
Bài toán quy hoạch tuyến tính thiết yếu tắc là vấn đề quy hoạch tuyến tính nhưng mà trong đó những ràng buộc chỉ tất cả dấu = và những biến số đều ko âm.
Người ta bao gồm thể biến đổi bài toán quy hoạch tuyến tính dạng tổng quát thành câu hỏi 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 gồm dạng ≤ thì người ta cộng cung ứng vế trái của ràng buộc một biến phụ xn+i ≥ 0 để được dấu = .
- Nếu gặp ràng buộc i có 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 tạo điều kiện cho ta biến những 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 cần không xuất hiện trong 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 ráng vào bài bác toán.
- Nếu biến xj là tuỳ ý thì ta đặt
- vào trường hợp trong số các ràng buộc bao gồm dòng nhưng vế phải của loại đó là giá trị âm thì đổi dấu cả nhị vế để được vế phải là một giá trị không âm.
Dựa vào các phép biến đổi trên nhưng mà 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à việc quy hoạch tuyến tính nhưng mà trong đó các ràng buộc chỉ có dấu = , vế phải và các biến số đều ko âm.
Ví dụ :
Biến đổi việc quy hoạch tuyến tính sau đây về dạng thiết yếu tắc :
Bằng các thay thế :
ta được :
hay :
Phương án
Xét câu hỏi quy hoạch tuyến tính chủ yếu tắc :
Một phương án tối ưu của (P) là một phương án khả thi của (P) nhưng mà giá trị của hàm mục tiêu tương ứng đạt min/max.
