Bài giảng Quy hoạch tuyến tính - Nguyễn Đình Thi

 ta tính ra toàn bộ các thế vị còn lại theo công 
 thức: 
 vj + ui = cij tại các ô (i , j) là các ô chọn 
 tức là: vj = cij - ui và ui = cij - vj 
 Bƣớc 2: Kiểm tra điều kiện tối ƣu 
 Sau khi xây dựng xong hệ thống thế vị, ta tính Δij = ui + vj - cij tại các ô loại. 
 1) Nếu Δij ≤ 0 với mọi i, j thì PA đang xét là PATƢ, thuật toán kết thúc. 
 2) Nếu tồn tại Δij > 0 thì ta phải điều chỉnh phƣơng án và chuyển sang bƣớc 3. 
 Bƣớc 3: Điều chỉnh phƣơng án 
 1) Tìm ô đƣa vào: Giả sử ô (i* , j*) có Δi*j* > 0 lớn nhất. Ô (i* , j*) là ô đƣa 
 vào. 
 2) Tìm vòng điều chỉnh: Bổ xung ô (i* , j*) vào (m + n – 1) ô chọn ban đầu sẽ 
 xuất hiện một vòng duy nhất là V gọi là vòng điều chỉnh. 
 3) Phân ô chẵn lẻ của vòng V: 
 Ta đánh dấu các ô của vòng V bắt đầu từ ô (i* , j*) có dấu “+”, ô tiếp theo có 
 dấu “ - ”, ô tiếp theo lại đánh dấu “+” . . . cứ nhƣ thế cho đến khi ta đánh dấu 
 xong vòng V . Khi đó, vòng V phân thành 2 lớp: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 128 
 Bài giảng Quy hoạch tuyến tính 
 V - : Các ô đánh dấu “ – ” 
 V+ : Các ô đánh dấu “+” (chứa “ô chọn 0” là ô(i* , j*)) 
 4) Tìm ô đƣa ra và lƣợng điều chỉnh: 
 Giả sử: min xij x rs 
 (i,j) V 
 Khi đó: ô (r , s) là ô đƣa ra và xrs là lƣợng điều chỉnh 
 5) Lập phƣơng án mới: X’ = [x’ij]mxn đƣợc tính nhƣ sau: 
 xij x rs khi (i, j) V
 , 
 xij x ij x rs khi (i, j) V 
 x khi (i, j) V
 ij
 Sau khi lập phƣơng án mới, ta lại quay lại bƣớc 1, rồi bƣớc 2 . . . Cứ tiếp tục 
nhƣ vậy, vì bài toán vận tải luôn có phƣơng án tối ƣu và số phƣơng án cơ bản là hữu 
hạn nên sau hữu hạn lần điều chỉnh phƣơng án, ta có phƣơng án tối ƣu. 
 Ví dụ 4: Giải bài toán vận tải cho bởi bảng sau: 
 Bj 
 B1 = 76 B2 = 62 B3 = 88 B4 = 45 B5 = 40 
 Ai 
 A1 = 79 10 19 15 6 7 
 A2 = 102 13 11 8 7 4 
 A3 = 70 12 17 10 5 3 
 A4 = 60 12 18 18 9 10 
 Đây là bài toán cân bằng thu phát ∑ Ai = ∑ Bj = 311 
 1) Chọn PACB ban đầu: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 129 
 Bài giảng Quy hoạch tuyến tính 
 Bj 
 B1 = 76 B2 = 62 B3 = 88 B4 = 45 B5 = 40 
 Ai 
 10 19 15 6 7 
 A1 = 79 
 64 15 
 13 11 8 7 4 
 A2 = 102 
 14 88 
 12 17 10 5 3 
 A3 = 70 
 30 40 
 12 18 18 9 10 
 A4 = 60 
 12 48 
 Lập hệ thống thế vị và kiểm tra điều kiện tốt nhất ta sẽ đƣợc kết quả. Cách làm 
nhƣ sau: 
 Lặp lần 1: 
 Bƣớc 1: Lập hệ thống thế vị: 
 Từ bảng PACB ban đầu, kẻ thêm các ô phụ ở cuối hàng và cuối đã có (nhƣ bảng 
dƣới). Cho một thế vị nào đó bằng 0 (cụ thể là cho u1 = -2, không nhất thiết cứ phải 
cho bằng 0 mà có thể u1 bằng 1 số bất kỳ). Từ thế vị đó ta tính các thế vị khác dựa 
trên các ô chọn với công thức tính là: 
 vj = cij - ui và ui = cij - vj. 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 130 
 Bài giảng Quy hoạch tuyến tính 
 10 19 15 6 7 
 u1 = -2 
 64 15 
 13 11 8 7 4 
 u2 = -7 
 14 88 
 12 17 10 5 3 
 u3 = -3 
 30 40 
 12 18 18 9 10 
 u4 = 0 
 12 48 
 v1 = 12 v2 = 18 v3 = 15 v4 = 8 v5 = 6 
 Bƣớc 2: Tính các Δij = ui + vj - cij tại các ô loại 
 Δ21 = -8 ; Δ31 = -3 ; Δ12 = -3 ; Δ32 = -2 
 Δ13 = -2 ; Δ33 = 2 ; Δ43 = -3 ; Δ24 = -6 
 Δ44 = -1 ; Δ15 = -3 ; Δ25 = -5 ; Δ45 = -4 
 Tồn tại Δ33 = 2 > 0 nên phƣơng án đang xét chƣa phải là phƣơng án tối ƣu, ta 
tìm ô đƣa vào, đó là ô đƣa vào là ô (3, 3), tìm vòng điều khiển: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 131 
 Bài giảng Quy hoạch tuyến tính 
10 19 15 6 7 
 - + u1 = -2 
 64 15 
13 11 8 7 4 
 + - u2 = -7 
 14 88 
12 17 10 5 3 
 + - u3 = -3 
 * 30 40 
12 18 18 9 10 
 + - u4 = 0 
 12 48 
v1 = 12 v2 = 18 v3 = 15 v4 = 8 v5 = 6 
 Chuyển sang bƣớc 3. 
 Bƣớc 3: Điều chỉnh phƣơng án 
 * Ô đƣa vào là ô (3,3) 
 * Lƣợng điều chỉnh là min{30, 64, 48, 88} = 30 
 các ô đánh dấu “ - ” trừ đi một lƣợng hàng hóa là 30, còn các ô đánh 
 dấu “ + ” cộng vào một lƣợng hàng hòa là 30 ô đƣa ra là ô (3,4) 
 * Ta có bảng sau: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 132 
 Bài giảng Quy hoạch tuyến tính 
 10 19 15 6 7 
 u1 = -2 
 34 45 
 13 11 8 7 4 
 u2 = -7 
 44 58 
 12 17 10 5 3 
 u3 = -5 
 30 40 
 12 18 18 9 10 
 u4 = 0 
 42 18 
 v1 = 12 v2 = 18 v3 = 15 v4 = 8 v5 = 8 
 Lặp lần 2: 
 Tính các Δij = ui + vj - cij tại các ô loại 
 Δ21 = -8 ; Δ31 = -5 ; Δ12 = -3 ; Δ32 = -6 
 Δ13 = -2 ; Δ43 = -3 ; Δ24 = -6 ; Δ43 = -2 
 Δ44 = -1 ; Δ15 = -1 ; Δ25 = -3 ; Δ45 = -2 
 Ta thấy tất cả các Δịj tại các ô loại đều < 0 nên PA đang xét là PATƢ 
 Kết luận: PATƢ tìm đƣợc là: x11 = 34; x14 = 45; x23 = 58; x33 = 30; x35 = 40; 
 x41 = 42; x42 = 18 và tổng cƣớc phí Fmin = 2806. 
3.2. MỘT SỐ BÀI TOÁN VẬN TẢI ĐẶC BIỆT 
3.2.1. Bài toán vận tải không cân bằng thu phát 
 Trong trƣờng hợp tổng lƣợng hàng hoá ở trạm phát và thu không cân bằng ta phải 
lập các trạm thu phát giả, cụ thể nhƣ sau: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 133 
 Bài giảng Quy hoạch tuyến tính 
 Trƣờng hợp 1: Tổng phát lớn hơn tổng thu 
 Tổng lƣợng hàng hoá ở các trạm phát lớn hơn tổng lƣợng hàng hoá ở các trạm 
thu: 
 m n
 ai  b j 
 i 1 j 1
 m n
 Đặt: bn + 1 = ai  b j 
 i 1 j 1
 Ta lập một trạm thu giả Bn+1 có nhu cầu bn +1 nhƣng tiền cƣớc trở từ mọi nơi đến 
trạm thu này đều bằng không. 
 Ta hiểu là khi bị điều hàng từ kho Ai đến Bn + 1 coi nhƣ giữ lại tại kho Ai lƣợng 
hàng đó. Sau khi bổ sung trạm giả bài toán giải bình thƣờng bằng 1 trong 2 phƣơng 
pháp đã trình bày ở trên. 
 Trƣờng hợp 2: Tổng thu lớn hơn tổng phát 
 Tổng lƣợng hàng hoá ở các trạm thu lớn hơn tổng lƣợng hàng hoá ở các trạm 
phát: 
 mn
 aij < b 
 i 1 j 1
 nm
 Đặt: am + 1 = bji a 
 j 1 i 1
 Ta lập một trạm phát giả Am+1 có lƣợng hàng là am +1 nhƣng tiền cƣớc trở từ 
trạm phát này đến mọi trạm thu đều bằng không. 
 Ta hiểu là khi bị điều hàng từ kho Am+1 đến Bj coi nhƣ lƣợng hàng xuất đi là 
không có. 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 134 
 Bài giảng Quy hoạch tuyến tính 
 Ví dụ 1: Giải bài toán vận tải sau 
 B 
 30 40 50 
 A 
 30 5 1 3 
 20 4 5 2 
 60 2 2 4 
 30 2 6 1 
Ta thấy tổng phát lớn hơn tổng thu là 20 đơn vị hàng hóa, do đó ta bổ xung thêm một 
trạm thu giả với lượng hàng bằng 20 và cước phí vận chuyển tới trạm thu này đều 
bằng 0. Sau đó ta giải bình thƣờng bằng một trong 2 phƣơng pháp đã học ở trên. Dƣới 
đây ta dùng phƣơng pháp quy O ô chọn. 
Lặp lần 1: 
 B 
 30 40 50 20 
 A 
 5 1 3 0 
 30 
 30 
 4 5 2 0 
 20 
 20 
 2 2 4 0 
 60 
 30 10 20 
 2 6 1 0 
 30 
 0 30 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 135 
 Bài giảng Quy hoạch tuyến tính 
 5 1 3 0 
 0 
 30 
 4 5 2 0 
 -2 
 20 
 2 2 4 0 
 -1 
 30 10 20 
 2 6 1 0 
 -1 
 0 30 
 -1 -1 0 1 
 4 0 3 1 
 30 
 1 2 0 -1 
 20 * 
 0 0 3 0 
 30 10 20 
 0 4 0 0 
 0 30 
Lặp lần 2 
 4 0 3 1 
 0 
 30 
 1 2 0 -1 
 1 
 20 0 
 0 0 3 0 
 0 
 30 10 20 
 0 4 0 0 
 1 
 30 
 0 0 -1 0 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 136 
 Bài giảng Quy hoạch tuyến tính 
 4 0 2 1 
 30 
 2 3 0 0 
 20 0 
 0 0 2 0 
 30 10 20 
 1 5 0 1 
 30 
Kết luận: 
 0 30 0
 0 0 20
 x* 
 30 10 0
 0 0 30
 f(x*) = 30 × 2 + 30 × 1 + 10 × 2 + 20 × 2 + 30 × 1 = 180 
 Chú ý: Khi kết luận thì trạm thu giả không cần viết vào nữa. 
 Ví dụ 2: Giải bài toán vận tải cho bởi bảng sau: 
 Thu 
 70 40 100 90 
 Phát 
 60 10 9 3 6 
 80 11 6 7 4 
 100 4 12 15 8 
 Ta thấy ∑Bi > ∑Aj, khi đó ta lập thêm một trạm phát giả A4 có lƣợng hàng là: 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 137 
 Bài giảng Quy hoạch tuyến tính 
 ∑Bi - ∑Aj = (70 + 40 + 100 + 90) - (60 + 80 + 100) = 60. 
Lập bảng chọn phƣơng án đầu tiên đƣợc: 
 Thu 
 70 40 100 90 
Phát 
 10 9 3 6 
 60 
 60 
 11 6 7 4 
 80 
 * 80 
 4 12 15 8 
 100 
 70 20 10 
 0 0 0 0 
 60 
 20 40 
Sau khi điều chỉnh ta đƣợc kết quả: 
 10 9 3 6 
 60 
 11 6 7 4 
 20 60 
 4 12 15 8 
 70 30 
 0 0 0 0 
 20 40 
Kiểm tra thấy đây là phƣơng án tối ƣu. 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 138 
 Bài giảng Quy hoạch tuyến tính 
3.2.2. Bài toán vận tải có ô cấm 
 Trong thực tế có một số tuyến đƣờng (đặc trƣng bởi các ô) không thể chuyển 
hàng qua đƣợc, chẳng hạn nhƣ: cầu phà bị hỏng, cự ly quá xa không thể chuyển kịp 
thời gian, hoặc chuyển đến nơi thì hàng bị hỏng do không có điều kiện bảo quản tốt 
trên đƣờng vận chuyển, không có phƣơng tiện vận tải thích hợp, kế hoạch vẩn chuyển 
phải đảm bảo cho một trạm phát nào đó phát hết hàng hoặc trạm thu nào đó phải thu đủ 
hàng khi không cân bằng thu phát v.v . . . Các ô ứng với các tuyến đƣờng này gọi là 
các “ô cấm”. 
 Để áp dụng các thuật toán trên, ta thay cij ở các ô cấm là M (một số lớn hơn bất 
kỳ số nào cần so sánh), lúc này cƣớc phí ở các ô sẽ có dạng: 
cij = a + b M 
(trong đó a, b là 2 hằng số nào đó) 
 Sau đó giải bình thƣờng. 
Lƣu ý: 
 1) Đặt j = aj + bj M để xét dấu j và so sánh chúng với nau, ta dùng quy tắc 
 sau: 
 bjj 0 , a 0
 j < 0 nếu 
 b 0 , a _ tuú ý
 jj
 bjj 0 , a 0
 j > 0 nếu 
 b 0 , a _ tuú ý
 jj
 bm b n , a m a n
 m < n nếu 
 b b , a ,a _ tuú ý
 m n m n 
2) Nếu ở PATƢ nhận đƣợc mà có ít nhất một ô cấm là ô chọn, thì bài toán vận tải 
không có PATƢ 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 139 
 Bài giảng Quy hoạch tuyến tính 
Ví dụ 3: Giải bài toán vận tải có ô cấm sau: 
 B 
 50 70 60 40 
 A 
 30 1 5 4 3 
 50 2 3 3 1 
 60 4 1 Ô cấm 2 
Lặp lần 1: 
 B 
 50 70 60 40 
 A 
 1 5 4 3 
 30 
 30 
 2 3 3 1 
 50 
 10 40 
 4 1 M 2 
 60 
 60 
 0 0 0 0 
 80 
 10 10 60 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 140 
 Bài giảng Quy hoạch tuyến tính 
 1 5 4 3 
 0 
 30 
 2 3 3 1 
 -1 
 10 40 
 4 1 M 2 
 0 
 60 
 0 0 0 0 
 1 
 10 10 60 
 ui 
 -1 -1 -1 0 
 vj 
 0 4 3 3 
 30 
 0 1 1 0 
 10 40 
 3 0 M-1 2 
 60 
 0 0 0 1 
 10 10 60 
Kết luận: 
 30 0 0 0
 x* = 10 0 0 40 
 0 60 0 0
 f(x*) = 30*1 + 10*2 + 60*1 + 40*1 = 150 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 141 
 Bài giảng Quy hoạch tuyến tính 
 BÀI TẬP CHƢƠNG 3 
GIẢI BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT SAU 
3.1. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 40 60 90 70 
 A 
 40 3 1 2 7 
 60 4 2 4 2 
 70 1 5 6 3 
 90 3 3 4 1 
 Đáp số: f(x*) = 570 
3.2. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 50 60 30 40 
 A 
 50 3 7 4 3 
 60 1 2 3 1 
 40 5 4 5 4 
 30 2 3 1 2 
 Đáp số: f(x*) = 420 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 142 
 Bài giảng Quy hoạch tuyến tính 
3.3. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 40 50 80 40 
 A 
 40 2 1 2 5 
 60 4 3 4 1 
 40 2 5 6 3 
 70 1 3 4 2 
 Đáp số: f(x*) = 510 
3.4. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 40 50 90 70 
 A 
 40 2 1 2 2 
 50 3 2 4 5 
 90 1 4 1 3 
 70 5 2 3 2 
 Đáp số: f(x*) = 410 
3.5. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 20 60 90 30 
 A 
 60 3 4 1 3 
 40 4 2 5 2 
 70 1 1 2 4 
 30 2 5 6 2 
 Đáp số: f(x*) = 300 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 143 
 Bài giảng Quy hoạch tuyến tính 
3.6. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 20 40 80 60 
 A 
 40 3 4 1 5 
 70 4 2 5 1 
 60 1 1 2 3 
 30 2 5 6 2 
 Đáp số: f(x*) = 280 
3.7. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 20 60 90 30 
 A 
 60 1 6 4 3 
 40 2 2 5 2 
 70 5 1 2 4 
 30 2 5 6 2 
 Đáp số: f(x*) = 440 
3.8. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 20 40 80 60 
 A 
 40 3 5 3 5 
 70 4 2 1 6 
 60 7 6 2 3 
 30 1 5 6 2 
 Đáp số: f(x*) = 440 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 144 
 Bài giảng Quy hoạch tuyến tính 
GIẢI BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT SAU 
3.9. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 50 40 60 
 A 
 60 2 4 3 
 40 1 5 4 
 70 5 6 3 
 50 3 2 5 
 Đáp số: f(x*) = 320 
3.10. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 30 40 50 
 A 
 30 6 4 3 
 20 4 1 2 
 60 5 2 4 
 30 2 6 5 
 Đáp số: f(x*) = 270 
3.11. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 20 40 80 30 
 A 
 60 4 4 1 2 
 70 3 6 2 8 
 30 1 5 4 4 
 Đáp số: f(x*) = 360 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 145 
 Bài giảng Quy hoạch tuyến tính 
3.12. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 50 60 80 30 
 A 
 30 3 2 5 2 
 70 2 7 2 1 
 30 4 5 1 3 
 Đáp số: f(x*)=200 
3.13. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 30 40 50 
 A 
 30 5 1 3 
 20 4 5 2 
 60 2 2 4 
 30 2 6 1 
 Đáp số: f(x*) = 180 
3.14. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 20 40 80 30 
 A 
 60 4 2 5 2 
 70 2 1 1 8 
 30 5 2 4 4 
 Đáp số: f(x*) = 290 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 146 
 Bài giảng Quy hoạch tuyến tính 
3.15. Giải bài toán vận tải sau bằng phƣơng pháp quy O ô chọn 
 B 
 50 60 80 30 
 A 
 30 3 4 5 2 
 70 2 2 2 1 
 30 5 5 2 6 
 Đáp số: f(x*) = 350 
3.16. Giải bài toán vận tải sau (dùng phƣơng pháp bất kỳ): 
 B 
 60 80 70 50 
 A 
 30 4 2 1 4 
 40 3 3 4 1 
 50 1 4 5 3 
 Đáp số: f(x*) = 120 
3.17. Giải bài toán vận tải sau (dùng phƣơng pháp bất kỳ): 
 B 
 50 70 30 40 
 A 
 60 1 4 5 2 
 40 2 3 3 1 
 50 4 5 2 3 
 Đáp số: f(x*) = 290 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 147 
 Bài giảng Quy hoạch tuyến tính 
GIẢI BÀI TOÁN VẬN TẢI CÓ Ô CẤM 
3.18. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 40 80 60 70 
 A 
 50 5 3 1 4 
 40 2 Ô cấm 5 3 
 60 1 4 2 5 
 Đáp số: f(x*) = 230 
3.19. Giải bài toán vận tải sau bằng phƣơng pháp thế vị 
 B 
 50 80 60 70 
 A 
 50 1 4 Ô cấm 1 
 30 3 1 2 4 
 60 2 3 1 3 
 Đáp số: f(x*) = 140 
3.20. Giải bài toán vận tải sau bằng phƣơng pháp quy “O ô chọn” 
 B 
 20 40 30 80 
 A 
 60 5 2 4 4 
 70 2 1 Ô cấm 3 
 30 4 5 2 6 
 Đáp số: f(x*) = 410 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 148 
 Bài giảng Quy hoạch tuyến tính 
3.21. Giải bài toán vận tải sau bằng phƣơng pháp quy “O ô chọn” 
 B 
 50 90 80 30 
 A 
 30 Ô cấm 4 5 2 
 70 2 1 3 1 
 30 6 5 2 Ô cấm 
 Đáp số: f(x*) = 190 
3.22. Giải bài toán vận tải sau bằng phƣơng pháp quy “O ô chọn” 
 B 
 50 90 80 30 
 A 
 30 1 Ô cấm 5 2 
 70 2 1 4 1 
 30 6 5 2 6 
 Đáp số: f(x*) = 160 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 149 
 Bài giảng Quy hoạch tuyến tính 
3.23. Giải bài toán vận tải sau: 
 B 
 50 90 80 30 
 A 
 30 1 4 3 2 
 70 2 Ô cấm 2 1 
 30 3 5 1 6 
 120 4 2 4 7 
 Đáp số: f(x*) = 470 
3.24. Giải bài toán vận tải sau: 
 B 
 50 90 80 30 
 A 
 30 5 4 5 2 
 70 2 Ô cấm 2 1 
 100 1 5 2 Ô cấm 
 50 4 5 3 2 
 Đáp số: f(x*) = 660 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 150 
 Bài giảng Quy hoạch tuyến tính 
 TÀI LIỆU THAM KHẢO 
[1] Đặng Hấn, Quy hoạch tuyến tính, Trƣờng ĐH Kinh tế TP.HCM, 1995 
[2] Phạm Quốc Khánh, Trần Huệ Nƣơng, Quy hoạch tuyến tính, NXB Giáo dục, 2003 
[3] Nguyễn Đức Nghĩa, Tối ƣu hóa, NXB Giáo dục, 1999 
[4] Lê Văn Phi, Quy hoạch tuyến tính ứng dụng trong kinh tế, NXB Giáo dục, 2004 
[5] Trần Vũ Thiệu, Giáo trình Quy hoạch tuyến tính, NXB ĐH Quốc gia Hà Nội, 2004 
[6] Bùi Minh Trí, Tối ƣu hóa, Tập 1 + 2, NXB Khoa học và Kỹ thuật, 2005 
 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 151