Giải Bài Toán Đơn Hình

Phương pháp đơn hình-Giải các 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, bài toán lập kế hoạch 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 tuyến tính

Bài toán lập kế hoạch sản xuất:

Một cơ sở có thể sản xuất hai loại sản phẩm A và B, từ các nguyên liệu I, II, III.Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản phẩm, cũng như dự trữ nguyên 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 kế hoạch sản xuất sao cho có tổng số lãi lớn nhất, trên cơ sở dự trữ nguyên liệu đã có.Lập bài toán:Gọi x, y lần lượt là số sản phẩm A và B được sản xuất ( x, y ≥ 0 , đơn vị sản phẩm).Khi đó ta cần tìm x, y ≥ 0 sao cho đạt lãi lớn nhất.f ()3 5 X xy =+→max với điều kiện nguyên liệu:

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

Một lớp học cần tổ chức lao động với hai loại công việc: xúc đất và chuyển đấ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 loại lao động trên từng công việc cho trong bảng dưới đây

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

Bạn đang xem: Giải bài toán đơn hình

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

Bài toán khẩu phần thức ăn:

Một khẩu phần thức ăn có khối lượng P, có thể cấu tạo từ n loại thức ăn. Gía muamột đơn vị thức ăn loại j là cj. Để đảm bảo cơ thể phát triển bình thường thì khẩu phầncần m loại chất dinh dưỡng. Chất dinh dưỡng thứ i cần tối thiểu cho khẩu phần là bi vàcó trong một đơn vị thức ăn loại j là aij.Hỏi nên cấu tạo một khẩu phần thức ăn như thế nào để ăn đủ no, đủ chất dinh. dưỡng mà có giá thành rẻ nhất.Lập bài toán:Gọi xj (xj ) là số đơn vị thức ăn loại j được cấu tạo trong khẩu phần. Khi đó,giá thành của khẩu phần là:≥ 0Vì phải đảm bảo thoả mãn điều kiện đủ 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 ba bài toán trên đều thuộc bài toán tổng quát.

Xem thêm: Hướng Dẫn Vào Safe Mode Win 8.1, Cách Vào Safe Mode Trong Windows 8

Bài toán quy hoạch tuyến tính tổng quát

Bài toán tổng quát của QHTT có dạng :với điều kiện. Để phân biệt tính chất của các ràng buộc đối 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 đối với phương án x mà ràng buộc i thỏa mãn với dấu đẳng. thức, nghĩa là 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à ràng buộc i thỏa mãn với dấu bất đẳng thức thực sự. nghĩa là thì ta nói phương án x thỏa mãn lỏng ràng buộc i

phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính

Định nghĩa 2 : Ta gọi một phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính là phương án cực biên. Một phương án cực biên thỏa mãn chặt đúng n ràng buộc. gọi là phương án cực biên không suy biến, thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến..

Phương án tối ưu

Định nghĩa 3: Một phương án mà tại đó hàm mục tiêu đạt cực tiểu ( cực đại ) gọi là phương án tối ưu. Bài toán có ít nhất một phương án tối ưu gọi là bài toán giải được, bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn dưới ( trên ) trên tập phương án gọi là không giải được.. Để nhất quán trong lập luận, ta xét bài toán tìm cực tiểu, sau đó ta xét cách đưa bài toán tìm cực đại về bài toán tìm cực tiểu.

* Chuyển bài toán tìm cực đại về bài toán tìm cực tiểu :

Nếu gặp bài toán tìm max, tức là :thì giữ nguyên ràng buộc, ta đưa nó về dạng bài toán tìm min :Chứng minh :Nếu bài toán tìm min có phương án tối ưu là X* thì bài toán tìm max cũng có phương án tối ưu là X*và g(X)= – f(X).. Thật vậy, X* là phương án tối ưu của bài toán tìm min, tức là phương án tối ưu của bài toán max và

Dạng chính tắc của bài toán quy hoạch tuyến tính

Người ta thường xét bài toán QHTT dưới dạng sau:: Bài toán (1.1), (1.2), (1.3) được gọi là Bài toán Quy hoạch tuyến tính dạng chính tắc. Kí hiệu ma trận hàng 12 1 ( , ,…, )n n c cc c = × và các ma trận :