Sau đó chuyển sang bước tiếp theo (xem bảng ). Bảng . Bảng đơn hình cải biên bước 3 Hệ số hàm mục tiêu cB –2 –3 0 0 T z = cB xB = – 38/3 Biến cơ sở x2 x1 x5 x6 Phương án B–1 4/3 10/3 3 2/3 T Hàng cB B–1 B−1 Cột mới 0 0 0 0 1 Cột α 2/3 –1/3 0 0 –1/3 –1 –2/3 –1/3 2/3 0 0 1 1 0 1/3 0 1 –4/3 0 0 Chúng ta đi tính các số gia hàm mục tiêu ứng với các biến ngoài cơ sở: ⎡a T T [Δ3, Δ4] = [c3, c4] – cB. | Sau đó chuyển sang bước tiếp theo xem bảng . . Bảng đơn hình cải biên bước 3 Hệ số hàm mục tiêu cB Biến cơ sở Phương án B 1 Cột a B-1 Cột mới -2 x2 4 3 2 3 -1 3 0 0 0 -3 x1 10 3 -1 3 2 3 0 0 0 0 x5 3 -1 1 1 0 0 0 x6 2 3 -2 3 1 3 0 1 0 z - cBxB - - 38 3 Hàng cg B 1 -1 3 -4 3 0 0 1 Chúng ta đi tính các số gia hàm mục tiêu ứng với các biến ngoài cơ sở As A4 - c3 c4 - cT B 1 a3 34 - - CB B -1 a3 a4 C4 1 0 0 1 - - -1 3 -4 3 0 0 1 x 0 - 1 3 4 3 . 0 0 0 00 Vậy phương án tối ưu đã tìm được là x1 - 10 3 x2 - 4 3 x3 - 0 x4 - 0 x5 - 3 x6 - 2 3 với giá trị nhỏ nhất của hàm mục tiêu là zmin - -38 3. Chú ý - Phương pháp đơn hình cải biên cho phép tính ma trận nghịch đảo của ma trận cơ sở ở bước k 1 theo công thứcB L Vk 1Bk1 . Vk 1Vk .V. 1B 1. Hơn nữa dạng của các ma k I kk kk I II trận Vị 1 Vi cũng rất đơn giản. Do đó có thể thấy phương pháp đơn hình cải biên giảm được khối lượng tính toán khá nhiều khi so sánh với phương pháp đơn hình. - Có thể áp dụng phương pháp hai pha cho phương pháp đơn hình cải biên. Lúc này các dấu hiệu dừng không có gì thay đổi Nếu pha 1 kết thúc với phương án tối ưu chứa biến giả nhận giá trị dương thì bài toán không có phương án. Nếu trong khi tiến hành pha 2 ta tìm được cột xoay mà không tìm được hàng xoay thì bài toán có hàm mục tiêu không bị chặn. Bài toán sẽ có phương án tối ưu nếu pha 2 kết thúc với dấu hiệu tối ưu với BTQHTT dạng Min thì dấu hiệu tối ưu là Aj 0 Vj . Để trình bày vấn đề đơn giản sau đây chúng ta phát biểu thuật toán đơn hình cải biên một cách sơ bộ cho trường hợp đã biết một phương án xuất phát BTQHTT dạng Min . 39 Khung thuật toán đơn hình cải biên Bước khởi tạo - Tìm một phương án cực biên ban đầu. - Xác định các biến cơ sở xB các hệ số hàm mục tiêu tương ứng cB. Xác định chỉ số của m biến cơ sở r 1 r 2 . r m . - Tìm ma trận cơ sở B ứng với các cột với chỉ số r 1 r 2 . r m ma trận nghịch đảo B 1 ma trận bao B-1 với C3B-1 là hàng cuối của ma trận bao. - Thiết lập ma trận mở rộng A N B và tính các số gia hàm mục tiêu
