Giải bài toán đơn hình

GiẢI BÀI TOÁN ĐƠN HÌNH Cho bài toán đơn hình sau Z= 4x1 + 6x2 +8x3 -> MAX x1 + 2x2 – 3x3 ≤ 12 3x1 + x2 +x3 ≤ 4 2x1 + 2x2 +5x3 ≤ 5 xj ≥ 0 , j = 1,3 B1- chuyển về bài toán phụ Z= 4x1 + 6x2 +8x3 -> MAX x1 + 2x2 – 3x3 + x4 = 12 3x1 + x2 + x3 + + x5 = 4 2x1 + 2x2 + 5x3 + + x6 = 5 xj ≥ 0 , j = 1,6 B2- Nhận xét vài câu như bên dưới: Trong đó x4, x5, x6 là 3 biến phụ.NX: BT phụ có dạng chuẩn, có 3 biến cơ sở là x4, x5, x6 Lập bảng đơn hình 20/4/2012 1 GiẢI BÀI TOÁN ĐƠN HÌNH Z= 4x1 + 6x2 +8x3 + 0x4 + 0x5 +0x6 -> MAX x1 + 2x2 – 3x3 + x4 = 12 3x1 + x2 + x3 + + x5 = 4 2x1 + 2x2 + 5x3 + + x6 = 5 xj ≥ 0 , j = 1,6 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 20/4/2012 2 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj = 00 0 X 12 4 5 -> 0 0 * 12 + 0 * 4 + 0 *5 = 0 20/4/2012 3 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 = 00 0 X 1 3 4 4- -> -4 0 * 1 + 0 * 3 + 0 *4 = 0 20/4/2012 4 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 = 00 0 X 2 1 2 6- -> -6 0 * 2 + 0 * 1 + 0 * 2 = 0 20/4/2012 5 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 = 00 0 X -3 1 5 8- -> -8 0 * (-3) + 0 * 1 + 0 *5 = 0 20/4/2012 6 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 -8 0 0 0 Tương tự làm cho x4, x5, x6, sẽ cho ra kết quả là 0 0 0 20/4/2012 7 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 -8 0 0 0 Bài toán Max nên Với mọi denta j ≥ 0 thì bài toán mới tối ưu, bài toán chưa thỏa điều kiện -> xác định cột xoay BT Max -> cột xoay là số âm nhỏ nhất (hoặc số âm có trị tuyệt đối lớn nhất) 20/4/2012 8 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 (-8) 0 0 0 Đã có cột xoay -> tìm lamda để xác định dòng xoay = 12 / -3 -> -4 Vì là số -4 (sốâm) nên sẽ ghi vào dấu - 20/4/2012 9 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 (-8) 0 0 0 Tìm lamda để xác định dòng xoay = 4 / 1 -> 4 20/4/2012 10 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 5 0 0 1 Δj 0 -4 -6 (-8) 0 0 0 Tìm lamda để xác định dòng xoay = 5 / 5 -> 1 20/4/2012 11 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 5 0 0 1 1 Δj 0 -4 -6 (-8) 0 0 0 Dòn xoay sẽ là dòng có lamda dương nhỏ nhất số 1 là lamda dương nhỏ nhất 20/4/2012 12 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 Đã xác định được dòng xoay -> tại sao phải xác định dòng xoay vào cột xoay ? Thật ra xác định để biết được biến vào và biến ra cơ sở ở đây biến vào là cột xoay (x3) và biến ra là dòng xoay (x6) Ra khỏi cơ sở 20/4/2012 13 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 Δj = -> 15 / 5 20/4/2012 14 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 1 Δj = -> 2/52 / 5 20/4/2012 15 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 2/5 1 Δj = -> 2/52 / 5 20/4/2012 16 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 2/5 2/5 1 Δj = -> 15 / 5 20/4/2012 17 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj làm tương tự để có kết quả như bảng 20/4/2012 18 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 0 = ->1-1 ? * Số ở đây bắt buộc là số 0, vậy ta phải tìm hệ số. có hệ số sẽ tìm được giá trị dòng này 1 hehe, hệ số là 1, khỏe rồi. 20/4/2012 19 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 0 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->2/5-1 1 * nếu là hệ số 1, không cần phải nhân cho 2/5. có thể trừ trực tiếp cho 2/5 3/5 20/4/2012 20 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3/5 0 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->2/5-3 13/5 20/4/2012 21 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 13/5 3/5 0 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->1-4 3 20/4/2012 22 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj Tương tự làm sẽ có kết quả như bảng 20/4/2012 23 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 0 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 0 = ->1--3 ? * Số ở đây bắt buộc là số 0, vậy ta phải tìm hệ số. có hệ số sẽ tìm được giá trị dòng này -3 hehe, hệ số là -3, không khỏe chút nào 20/4/2012 24 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 0 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->2/5-2 -3 * 16/5 2 + 6/5 =16/5 cái này cộng trừ phân số thôi 20/4/2012 25 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 16/5 0 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->2/5-1 -3 * 11/5 1 + 6/5 =11/5 hehe 20/4/2012 26 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 11/5 16/5 0 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = ->1-12 -3 * 15 12 + 3=15 hehe 20/4/2012 27 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj Làm tương tự ta có như bảng trên 20/4/2012 28 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj = 00 8 X 15 3 1 -> 8 0 * 15 + 0 * 3 + 8 * 1 = 820/4/2012 29 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 8 = 00 8 X 44/5 3 1 -> 4 0 * 44/5 + 0 * 3 + 8 * 1 = 8 - 4 20/4/2012 30 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 8 4 = 00 8 X 16/5 3/5 2/5 -> -14/5 0 * 16/5 + 0 * 3/5 + 8 * 2/5 = 16/5 - 6 20/4/2012 31 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 8 4 -14/5 = 00 8 X 0 0 1 -> 0 0 * 0 + 0 * 0 + 8 * 1 = 8 - 8 20/4/2012 32 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 2 x5 0 3 13/5 3/5 0 0 0 -1/5 3 x3 8 1 2/5 2/5 1 0 0 1/5 Δj 8 4 -14/5 0 0 0 8/5 Làm tương tự ta có như bảng trên 20/4/2012 33 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 2/5 1 0 0 1/5 5/2 Δj 8 4 (-14/5) 0 0 0 8/5 lấy phương án chia cho cột xoay -> lamda = / 20/4/2012 34 GiẢI BÀI TOÁN ĐƠN HÌNH i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 lamda dương bé nhất làm dòng xoay ta có x3 ra và x2vào cơ sở 20/4/2012 35 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3 x2 6 = -> 12/5 / 2/5 20/4/2012 36 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3 x2 6 1 = -> 12/5 / 2/5 20/4/2012 37 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3 x2 6 1 1 = -> 5/21 / 2/5 20/4/2012 38 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->/ 2/5 20/4/2012 39 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->/ 2/5 Làm tương tự sẽ có kết quả như bảng 20/4/2012 40 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 0 3 x2 6 5/2 1 1 5/2 0 0 1/2 0 = ->1-3/5 ? * Số ở đây bắt buộc là số 0, vậy ta phải tìm hệ số. có hệ số sẽ tìm được giá trị dòng này 3/5 20/4/2012 41 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 0 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->1-13/5 3/5 * 2 13/5-3/5 =10/5=2 20/4/2012 42 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 2 0 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->5/2-3 3/5 * 3/2 3-3/5*5/2= 3- 3/2= 3/2 20/4/2012 43 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Làm tương tự để có kết quả như bảng 20/4/2012 44 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 0 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 0 = ->1-16/5 ? * Số ở đây bắt buộc là số 0, vậy ta phải tìm hệ số. có hệ số sẽ tìm được giá trị dòng này 16/5 20/4/2012 45 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 11/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 0 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->1-11/5 16/5 * -1 11/5-16/5 = -5/5 =-1 hehe 20/4/2012 46 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 -1 0 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 = ->5/2-15 16/5 * 7 15 – 16/5*5/2 = 7 20/4/2012 47 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Tính tương tự ta sẽ có kết quả 20/4/2012 48 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Δj = 00 6 X 7 3/2 5/2 -> 1 5 0 * 7 + 0 * 3/2 + 6 * 5/2 = 820/4/2012 49 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Δj 15 = 00 6 X 28/5 2 1 -> 2 0 *28/5 + 0 * 2 + 6 * 1 = 6 - 4 20/4/2012 50 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Δj 15 2 = 00 6 X 0 0 1 -> 0 0 *0 + 0 * 0 + 6 * 1 = 6 - 6 20/4/2012 51 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Δj 15 2 0 7 0 0 3 Tính tương tự ta sẽ có kết quả 20/4/2012 52 i Cơ sở Ci Bi P/a x1 x2 x3 x4 x5 x6 λ 4 6 8 0 0 0 1 x4 0 12 1 2 -3 1 0 0 - 2 x5 0 4 3 1 1 0 1 0 4 3 x6 0 5 2 2 (5) 0 0 1 (1) Δj 0 -4 -6 (-8) 0 0 0 1 x4 0 15 44/5 16/5 0 1 0 3/5 75/16 2 x5 0 3 13/5 3/5 0 0 0 -1/5 5 3 x3 8 1 2/5 (2/5) 1 0 0 1/5 (5/2) Δj 8 4 (-14/5) 0 0 0 8/5 1 x4 0 7 28/5 0 -8 1 0 -1 2 x5 0 3/2 2 0 3/2 0 0 1/2 3 x2 6 5/2 1 1 5/2 0 0 1/2 Δj 15 2 0 7 0 0 3 Vì Δj ≥ 0 với mọi j nên phương án cơ bản ở bảng 3 là phương án tối ưu phương án tối ưu là X* = (0 , 5/2, 0) Zmax = 15 20/4/2012 53