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

bài toán đối ngẫu, bài toán đối kháng 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 trạng độ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 kế hoạch sản xuất:

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


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

Một lớp học tập cần tổ chức lao động với hai nhiều loại công việc: xúc đất và gửi đất.Lao hễ của lớp được chia thành 3 nhiều 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 các loại lao cồn 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 khu đất 6 5 4. Gửi đấ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 béo nhất.

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


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

Bài toán thực đơn thức ăn:

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


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

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

Xem thêm: Ki-Tê-Rét-Sư Và Cuốn Từ Điển Kì Bí (Kiteretsu Daihyakka) 1988

Phương án x vừa lòng ràng buộc i

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

phương án vừa lòng chặt n ràng buộc độc lập tuyến tính

Định nghĩa 2 : Ta hotline một phương án thỏa mãn chặt n ràng buộc chủ quyền tuyến tính là phương án cực biên. Một giải pháp cực biên thỏa mãn chặt đúng n ràng buộc. điện thoại tư vấn là giải pháp cực biên ko suy biến, thỏa mãn chặt rộng n ràng buộc call là giải pháp cực biên suy biến.. 

Phương án buổi tối ưu

Định nghĩa 3: Một giải pháp mà tại đó hàm kim chỉ nam đạt rất tiểu ( cực lớn ) gọi là phương án về tối ưu. Bài toán có ít nhất một phương án về tối ưu gọi là câu hỏi giải được, bài xích toán không có phương án hoặc bao gồm phương án nhưng hàm mục tiêu không biến thành 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 điệu trong lập luận, ta xét việc tìm cực tiểu, kế tiếp ta xét phương pháp đưa vấn đề tìm cực đại về việc tìm cực tiểu.

* Chuyển bài toán tìm cực lớn về việc tìm rất tiểu :

Nếu chạm chán bài toán tìm max, tức là :thì giữ nguyên ràng buộc, ta đưa nó về dạng việc tìm min :Chứng minh :Nếu việc tìm min tất cả phương án về tối ưu là X* thì bài toán tìm max cũng đều 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 việc tìm min, có nghĩa là  phương án buổi tối ưu của bài toán max và

 Dạng chính tắc của vấn đề quy hoạch đường tính

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

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

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