tailieunhanh - Bài toán về quy hoạch tuyến tính

Trong toán học, quy hoạch tuyến tính (QHTT) (tiếng Anh: linear programming - LP) là bài toán tối ưu hóa, trong đó hàm mục tiêu (objective function) và các điều kiện ràng buộc đều là tuyến tính. Trong bài toán này, cho một đa tạp (polytope) (chẳng hạn một đa giác hoặc một đa diện), và một hàm tuyến tính (affine) nhận giá trị thực f(x_1, x_2, \dots, x_n)=a_1x_1+a_2x_2+\cdots +a_nx_n+b\, xác định trên đa tạp đó, mục đích là tìm một điểm trên đa tạp tại đó hàm có giá trị nhỏ nhất (hoặc lớn nhất). Các điểm như. | CHƯƠNG 1 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH Ths. Nguyễn Công Trí chương i 0j BÁI TOÁN Ssề . QUY HOÁCH TUYEN TÍNH taMn-MnglỄ 1. THIET LÁP MỘHÌNH bái toán 2 CÁC DÁNG cUá bái toán quy HOÁCH TUYENTÍNH Cỏng xêm 3. CÁC KHÁI NIỆM Cơ BÁN VỆ BÁI TOÁN QUY HOÁCH TUYENTÍNH 4. CÁC PHƯƠNG PHÁP GIAI BÁI TOÁN QUY HOÁCH TUYEN TÍNH . Xêm Ths. Nguyên Cõng jrj 5. BÁI TÁP CDpyrighi 2 Xêm MỘT VÁI VÍ DU VỆ BÁI TOÁN QHTT Ví du . Bái toán Láp ke HOÁCH sán XUÁT Mỏt xí nghiêp dung 3 toai nguyên liêu N1 N2 N3 đê san xuat ra mỏt toai san phâ m thêỏ 3 phượng phap khác nhau PP1 PP2 PP3. Định mức nguyên liêu va sỏ lượng san pha m san xuat ra trỏng 1 già được chỏ ợ bang sau __ Nguyêân Liêu Sỏ lượng hiên cỏ đv Định mưc nguyên liêu PP1 PP2 PP3 N1 250 4 5 3 N2 350 2 4 1 n3 450 3 6 4 Sỏ san pham sp giợ 10 12 9 Hay lap mỏ hình bai tỏan saỏ chỏ xí nghiêp san xuat ra nhiêu san pha m nhat -41 MỘT VAI VÍ DU VỆ BAI TOÁN QHTT Gọi x1 x2 x3 lần lượt la thài gian san xuất ra san phẩm thêỏ 3 phượng phap PP PP2 PP3. Tô ng san pham san xuat can lam cực đại f x 10x1 12x2 9x3- max Dọ xí nghiệp chi cỌ 250 nguyên liệu N1 nen x1 x2 x3 phai thỏa man 4x1 5x2 3x3 250 Tựàng tựchọ cac nguyên liệu N2 N3 ta cỏ 2x1 4x2 x3 350 va 3x1 6x2 4x3 450 Dì nhiên ta phai cỏ x1 x2 x3 không am Vậy mỏ hình bai tỏan được phat biê u như sau Tìm cac biên x1 x2 x3saỏ chỏ f x 10x1 12x2 9x3 - max thỏa cac điêu kiện 4x1 5x2 3x3250 - A 2x1 4x2 x3 350 f 3x1 6x2 4x3 450 x1 0 x2 0 x3 0 MỘT VÁI VÍ DU VỆ BÁI TOÁN QHTT Ví du . BÁI TOÁN PHÁ CÁT VÁT LIỆU Mỏt xí nghiêp may mặc can san xuat đung quan va ít nhat aỏ. Mỏi tấm vai cỏ 6 cach Cach cat Quan Áỏ 1 90 35 2 80 55 3 70 70 4 60 90 5 120 0 6 0 100 Hay tìm phượng an cat quan aỏ saỏ chỏ tỏ ng sỏ tam vai la ít nhat MỘT VÁI VÍ DU VỆ BÁI TOÁN QHTT Gỏi xj j 1 2 6 la sỏ tấm vai được cat thêỏ cach thứj. Tô ng sỏ tam vai dung đê san xuat can lam cực tiê u la f x x1 x2 x3 x4 x5 x6 - min Dỏ xí nghiêp can san xua t đung quan nên cac xj phải thỏa man 90x1 80x2 70x3 60x4 J 20x5 .