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

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

Chương này trình bày một phương pháp để giải bài toán quy hoạch tuyến tính đó là phương pháp đơn hình. Phương pháp đơn hình được George Bernard Dantzig đưa ra năm 1947 cùng lúc với việc ông khai sinh ra quy hoạch tuyến tính. Đây là một phương pháp thực sự có hiệu quả để giải những bài toán quy hoạch tuyến tính cở lớn trong thực tế. Với cách nhìn hiện đại ý tưởng của phương pháp đơn hình rất đơn giản. Có nhiều cách tiếp cận phương pháp đơn hình, chương này trình bày một trong các cách đó.

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 :

$\begin{array}{}\text{max}\text{z}(x)=c^{T}x\\ \text{Ax}=b\\ x\ge 0\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Giả sử rằng B0 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 :

a-Gán B = B0 và l=0 ( số lần lặp )

b-l = l+1

c-Với cơ sở hiện thời B tính :

$\begin{array}{}{x}_B=B^{-1}b\\ x_N=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$ : phương án cơ sở khả thi tương ứng

$\overline{b}=B^{-1}b$

${\overline{c}}_N^T=c_N^T-c_N^T{B}^{-1}N$ : dấu hiệu tối ưu

d-Nếu thì giải thuật dừng và bài toán có phương án tối ưu là x .

Ngược lại, nếu tồn tại s sao cho ${\overline{c}}_s>0$ ( ${\overline{c}}_s$ là thành phần thứ s của ${\overline{c}}_N$ ) thì sang bước e

e-Tính : ${\overline{A}}_s=B^{-1}{A}_s$ ( As là cột thứ s của A )

Nếu thì giải thuật dừng và phương án tối ưu không giới nội.

Ngược lại, nếu tồn tại ${\overline{a}}_{\text{is}}\in {\overline{A}}_s$ mà ${\overline{a}}_{\text{is}}>0$ thì tính :

${\stackrel{}{x}}_s=\text{min}\left\{\frac{{\overline{b}}_i}{{\overline{a}}_{\text{is}}},{\overline{a}}_{\text{is}}>0\right\}=\frac{{\overline{b}}_r}{{\overline{a}}_{\text{rs}}}$ ( i = 1  m)

${\overline{a}}_{\text{is}}$ là các thành phần của ${\overline{A}}_s$ .

${\stackrel{}{x}}_s$ là thành phần thứ s của phương án mới $\stackrel{}{x}$ .

f-Gọi xt là biến tương ứng với cột thứ r của cơ sở B. Khi đó biến xs sẽ nhận giá trị ${\stackrel{}{x}}_s>0$ ( vào cơ sở ), biến xt sẽ nhận giá trị ${\stackrel{}{x}}_t=0$ ( ra khỏi cơ sở ). Như vậy phương án mới $\stackrel{}{x}$ tương ứng với cơ sở mới $\stackrel{}{B}$ ( thay đổi cơ sở ) được xác định như sau :

$\stackrel{}{B}$ = B  { t } - { s }

g-Gán B = $\stackrel{}{B}$ và quay về b .

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ề B0 B1 B2 ......... mà các phương án cơ sở tương ứng x0 x1 x2........ là ngày càng tốt hơn, tức là :

z(x0)<z(x1)<z(x2) .............

Chú ý :

Nếu cơ sở ban đầu B0 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

$\begin{array}{}\text{min/max}z(x)=c^{T}x\\ \text{Ax}=b\\ x\ge 0\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

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 :

A = [ B N ]

$c^T=[c_B{c}_N]ư$

$x^T=[x_B{x}_N]ư$

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