Cách giải bài toán quy hoạch tuyến tính

-

Phương pháp 1-1 hình-Giải những bài toán quy hoạch tuyến tính bao gồm:

bài toán đối ngẫu, bài toán đơn hình, bài toán khẩu phần thức ăn, câu hỏi lập chiến lược sản xuất, phân công lao động:


BÀI TOÁN QUY HOẠCH TUYẾN TÍNH.PHƯƠNG PHÁP ĐƠN HÌNH

Bài toán quy hoạch con đường tính

 Bài toán lập planer sản xuất:

Một cơ sở rất có thể sản xuất nhì loại thành phầm A và B, tự các nguyên liệu I, II, III.Chi mức giá từng loại nguyên liệu và chi phí lãi của một đơn vị chức năng sản phẩm, tương tự như dự trữ nguyên vật liệu cho trong bảng sau đây:Nguyên liệuSản phẩm. I II III Lãi A 2 0 1 3.B 1 1 0 5. Dự trữ 8 4 3. Hãy lập bài toán thể hiện chiến lược sản xuất sao để cho có tổng cộng lãi to nhất, trên cơ sở dự trữ vật liệu đã có.Lập bài bác toán:Gọi x, y thứu tự là số sản phẩm A và B được tiếp tế ( x, y ≥ 0 , đơn vị chức năng sản phẩm).Khi kia ta nên tìm x, y ≥ 0 làm thế nào để cho đạt lãi phệ nhất.f ()3 5 X xy =+→max với đk nguyên liệu:


 Bài toán phân lao động động:

Một lớp học tập cần tổ chức triển khai lao đụng với hai nhiều loại công việc: xúc khu đất và đưa đất.Lao động của lớp được chia làm 3 loại A, B, C, với số lượng lần lượt là 10, 20, 12.Năng suất của từng nhiều loại lao động trên từng quá trình cho vào bảng bên dưới đây

Lao động. Công việc. A(10) B(20) C(12). Xúc khu đất 6 5 4. đưa đất 4 3 2. Hãy tổ chức triển khai lao động làm sao cho có tổng năng suất lớn nhất.

Bạn đang xem: Cách giải bài toán quy hoạch tuyến tính


Lập bài toán:Gọi xij là số lao động nhiều loại j làm quá trình i(j=1,2;xij , nguyên). Khi đó, năng suất lao hễ của quá trình đào đất đang là: ≥ 0. 11 12 13 654 x + + x x ;còn đưa đất đang là : 21 22 23 432 x + x x + ;Ta thấy rằng để sở hữu năng suất lớn số 1 thì không thể tất cả lao động dư thừa, có nghĩa là phải cân đối giữa hai công việc. Vì chưng vậy ta có vấn đề sau:

Bài toán chế độ thức ăn:

Một khẩu phần thức nạp năng lượng có khối lượng P, tất cả thể cấu trúc từ n nhiều loại thức ăn. Gía muamột đơn vị thức ăn uống loại j là cj. Để bảo đảm cơ thể phát triển bình thường thì khẩu phầncần m một số loại chất dinh dưỡng. Chất dinh dưỡng thứ i cần tối thiểu cho chế độ là bi vàcó vào một đơn vị thức nạp năng lượng loại j là aij.Hỏi nên kết cấu một thực đơn thức ăn như thế nào để ăn uống nhiều no, đủ hóa học dinh. Dưỡng mà có chi tiêu rẻ nhất.Lập bài toán:Gọi xj (xj ) là số đơn vị thức nạp năng lượng loại j được kết cấu trong khẩu phần. Khi đó,giá thành của chế độ là:≥ 0Vì phải đảm bảo thoả mãn đk đủ no và đủ chất, tức là: P ax b i m1, . = =∑ ∑ = ≥=Ta có bài toán sau: 1với điều kiện. Ta thấy rằng cha bài toán trên đa số thuộc việc tổng quát.

Xem thêm: Báo Cáo Thuế: Hướng Dẫn Nộp Thuế Nhà Thầu Đối Với Nhà Thầu Nước Ngoài


Bài toán quy hoạch con đường tính tổng quát

Bài toán bao quát của QHTT gồm dạng :với điều kiện. Để tách biệt tính chất của các ràng buộc so với một phương án, ta làm quen với. Hai khái niệm : ràng buộc chặt và ràng buộc lỏng.

Phương án x thỏa mãn ràng buộc i

Định nghĩa 1: Nếu so với phương án x cơ mà ràng buộc i thỏa mãn với dấu đẳng. Thức, tức thị thì ta nói phương án x thỏa mãn chặt ràng buộc i. Nếu đối với phương án x mà lại ràng buộc i thỏa mãn với vệt bất đẳng thức thực sự. Nghĩa là thì ta nói cách thực hiện x thỏa mãn nhu cầu lỏng buộc ràng i

phương án thỏa mãn chặt n ràng buộc tự do tuyến tính

Định nghĩa 2 : Ta gọi một phương án thỏa mãn nhu cầu chặt n ràng buộc độc lập tuyến tính là phương pháp cực biên. Một giải pháp cực biên thỏa mãn nhu cầu chặt đúng n ràng buộc. Call là phương án cực biên ko suy biến, vừa lòng chặt hơn n ràng buộc call là cách thực hiện cực biên suy biến.. 

Phương án về tối ưu

Định nghĩa 3: Một giải pháp mà tại đó hàm phương châm đạt rất tiểu ( cực đại ) call là phương án buổi tối ưu. Câu hỏi có tối thiểu một phương án buổi tối ưu call là việc giải được, bài bác toán không tồn tại phương án hoặc tất cả phương án nhưng mà hàm mục tiêu không xẩy ra chặn dưới ( trên ) bên trên tập phương pháp gọi là không giải được.. Để đồng hóa trong lập luận, ta xét vấn đề tìm cực tiểu, tiếp nối ta xét phương pháp đưa việc tìm cực to về việc tìm cực tiểu.

* Chuyển câu hỏi tìm cực lớn về việc tìm cực tiểu :

Nếu gặp bài toán tìm kiếm max, tức là :thì không thay đổi ràng buộc, ta đưa nó về dạng bài toán tìm min :Chứng minh :Nếu vấn đề tìm min tất cả phương án buổi tối ưu là X* thì bài toán tìm max cũng có thể có phương án về tối ưu là X*và g(X)= – f(X).. Thật vậy, X* là phương án buổi tối ưu của việc tìm min, có nghĩa là  phương án buổi tối ưu của vấn đề max và

 Dạng bao gồm tắc của việc quy hoạch tuyến tính

Người ta hay xét vấn đề QHTT bên dưới dạng sau:: việc (1.1), (1.2), (1.3) được call là việc Quy hoạch con đường tính dạng thiết yếu tắc. Kí hiệu ma trận hàng 12 1 ( , ,…, )n n c cc c = × và những ma trận :

Dạng chuẩn tắc của bài toán tối ưu:

Đối với việc dạng bao gồm tắc ta có một số tính chất và khái niệm đặc biệt quan trọng của giải pháp cực biên như sau :