GIẢI THUẬT ĐƠN HÌNH

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

Phương pháp đơn hình là một phương pháp đại số thông minh thay vì khảo sát toàn bộ các lời giải mà chỉ khảo sát một số ít lời giải để tìm lời giải tối ưu.

a. Quy tắc giải thuật đơn hình

Các quy tắc của giải thuật đơn hình như sau:

     a. Điều kiện tối ưu

         - Biến vào là biến không cơ bản trên hàng z có hệ số

• Dương nhất với bài toán cực tiểu
• Âm nhất với bài toán cực đại

         - Điều kiện dương / âm nhất có thể chọn là dương / âm khi chọn biến vào

         - Điều kiện tối ưu: Mọi hệ số của biến không cơ bản trên hàng z đều

• Âm với bài toán cực tiểu
• Dương với bài toán cực đại

     b. Điều kiện khả thi

         - Biến ra là biến cơ bản có tỷ số không âm nhỏ nhất

         - Điều kiện tỷ số không âm nhỏ nhất có thể thay bằng tỷ số không âm

     c. Biến đổi Gauss Jordan

         - Với hàng quay:

Hàng mới = hàng cũ / điểm quay

         - Các hàng khác:

Hàng mới = hàng cũ – hệ số tương ứng trên cột quay * hàng quay mới

b. Giải thuật đơn hình

Các bước của giải thuật đơn hình:

1. Bước 1: Xác định lời giải cơ bản khả thi  ban đầu
2. Bước 2: Kiểm tra điều kiện tối ưu

            - Dừng khi thỏa, lời giải cuối là lời giải tối ưu

            - Không thỏa, chọn biến vào, chuyển sang bước 3.

3. Bước 3: Chọn biến ra theo điều kiện khả thi.
4. Bước 4:

      - Xác định lời giải mới với phép biến đổi Gauss Jordan

      - Chuyển sang bước 2.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010