Cơ sở xây dựng giải thuật đơn hình cơ bản

Xét bài toán quy hoạch tuyến tính chính tắc :

Giả sử rằng B⁰ là một cơ sở khả thi xuất phát của bài toán ( không nhất thiết là m cột đầu tiên của ma trận A ) . Thuật toán đơn hình cơ bản được xây dựng dựa trên các bước sau :

Về mặt hình học, giải thuật này được hiểu như là một quá trình duyệt qua các điểm cực biên của đa diện lồi S các phương án khả thi của bài toán.

Về mặt đại số, giải thuật này được hiểu như là một quá trình xác định một chuỗi các ma trận cơ sở kề B⁰ B¹ B² ......... mà các phương án cơ sở tương ứng x⁰ x¹ x²........ là ngày càng tốt hơn, tức là :

z(x⁰) < z(x¹) < z(x²) .............

Chú ý :

Nếu cơ sở ban đầu B⁰ chính là m cột đầu tiên của ma trận A thì trong giải thuật trên t chính là r .

Định lý về sự hội tụ

Với giả thiết bài toán không suy biến, giải thuật đơn hình trên đây sẽ hội tụ về phương án tối ưu sau một số hữu hạn lần lặp.

Bằng sự thống kê người thấy rằng nói chung giải thuật đơn hình sẽ hội tụ với số lần lặp ít nhất phải là từ m đến 3m ( m là số ràng buộc ) .

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

Xét bài toán quy hoạch tuyến tính chính tắc

Giả sử rằng sau khi hoán vị các cột trong A ta chọn được ma trận cơ sở B thoả sự phân hoạch sau đây :

Giải thuật đơn hình cơ bản được thực hiện như sau :

a- Tính ma trận nghịch đảo B^-1

b- Tính các tham số :

. Phương án cơ sở khả thi tốt hơn

. Giá trị hàm mục tiêu $z(x)=c_B^T{x}_B$

$$ . Ma trận $\stackrel{\text{\_\_}}{N}$= B^-1N

c- Xét dấu hiệu tối ưu :

d- Xác định chỉ số của phần tử pivot trong ma trận $\overline{N}$

e- Thực hiện các hoán vị :

. Cột thứ s trong ma trận N với cột thứ r trong ma trận B

. Phần tử thứ s trong $c_N^T$ với phần tử thứ r trong $c_B^T$

. Biến x_s trong $x_N^T$ với biến x_r trong $x_B^T$

f- Quay về (a)

Ví dụ : Tìm phương án tối ưu cho bài toán quy hoạch tuyến tính chính tắc sau đây bằng giải thuật đơn hình cơ bản

Lần lặp1

a- Tính ma trận nghịch đảo B^-1

b- Tính các tham số

. Phương án cơ sở khả thi tốt hơn :

c- Xét dấu hiệu tối ưu :

Chuyển sang bước d

d- Xác định chỉ số của pivot

. Xác định chỉ số cột pivot s :

${\overline{c}}_s=\text{max}\left\{{\overline{c}}_k>0\in {\overline{c}}_N\right\}$ $=\text{max}\left\{\text{2 , 1}\right\}=2={\stackrel{\text{\_\_}}{c}}_1$

Vậy s=1

Ma trận cột s=1 trong ma trận $\overline{N}$ là $\begin{array}{}1\\ 1\\ -1\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ {\overline{N}}_1=\\ \end{array}$

. Xác định chỉ số dòng pivot r :

Vậy r = 1

e- Hoán vị

. Cột thứ s=1 trong ma trận N và cột thứ r=1 trong ma trận B

. Phần tử thứ s=1 trong $c_N^T$ với phần tử thứ r=1 trong $c_B^T$

. Biến thứ s=1 trong $x_N^T$ với biến thứ r=1 trong $x_B^T$

f- Quay về bước a

Lần lặp 2

a. Tính ma trận nghịch đảo B^-1

b- Tính các tham số

. Phương án cơ sở khả thi tốt hơn :

. Giá trị hàm mục tiêu :

. Tính ma trận :

c- Xét dấu hiệu tối ưu :

Chuyển sang bước d

d- Xác định chỉ số của pivot

. Xác định chỉ số cột pivot s :

e- Hoán vị

. Cột thứ s=2 trong ma trận N và cột thứ r=2 trong ma trận B

. Phần tử thứ s=2 trong $c_N^T$ với phần tử thứ r=2 trong $c_B^T$

. Biến thứ s=2 trong $x_N^T$ với biến thứ r=2 trong $x_B^T$

f- Quay về bước a

Lần lặp 3

a. Tính ma trận nghịch đảo B^-1

b- Tính các tham số

. Phương án cơ sở khả thi tốt hơn :

. Giá trị hàm mục tiêu :

$$

. Tính ma trận :

$$

c- Xét dấu hiệu tối ưu :

: dừng

Vậy phương án tối ưu sẽ là :

Giá trị hàm mục tiêu là z(x) = 9 với x₁ = 4 và x₂ = 1

Chú ý trong trường hợp suy biến

Trong trường hợp bài toán suy biến, nghĩa là ${\overline{b}}_r=0$, ta có :

${\stackrel{}{x}}_s=\frac{{\overline{b}}_r}{{\overline{a}}_{\text{rs}}}=0$

cho nên giá trị của hàm mục tiêu không thay đổi khi thay đổi cơ sở, vì :

$z(\stackrel{}{x})=z(x)+{\overline{c}}_s{\stackrel{}{x}}_s=z(x)$

Vậy thì, có thể sau một số lần thay đổi cơ sở lại quay trở về cơ sở đã gặp và lặp như vậy một cách vô hạn. Người ta có nhiều cách để khắc phục hiện tượng này bằng cách xáo trộn một chút các dữ liệu của bài toán, sử dụng thủ tục từ vựng, quy tắc chọn pivot để tránh bị khử.