Lý thuyết cơ bản về quy hoạch tuyến tính-Một số ví dụ mở đầu

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

Đưa bài toán về dạng chính tắc bằng cách đưa vào các biến phụ w₁, w₂, w₃ ≥ 0 ( làm cho các ràng buộc bất đẳng thức thành đẳng thức ) . Ta được :

Thực hiện việc chuyển vế ta được bài toán ban đầu như sau :

(I)

Một phương án khả thi xuất phát ( chưa là phương án tối ưu ) của bài toán là :

x₁ = x₂ = x₃ = 0

w₁=5 w₂=11 w₃ = 8

Giá trị tương ứng của hàm mục tiêu là z(x) = 0

Người ta sẽ cải tiến phương án xuất phát này để được một phương án mới tốt hơn, nó làm cho giá trị của hàm mục tiêu giảm xuống. Người ta làm như sau :

Vì hệ số của x₁ trong hàm mục tiêu là âm và có giá trị tuyệt đối lớn nhất nên nếu tăng x₁ từ bằng 0 lên một giá trị dương ( càng lớn càng tốt ) và đồng thời vẫn giữ x₂ và x₃ bằng 0 thì giá trị của hàm của hàm mục tiêu sẽ giảm xuống. Khi đó các biến ở vế trái của bài toán (I) sẽ bị thay đổi theo nhưng phải thoả ≥ 0 . Sự thay đổi của chúng không ảnh hưởng đến sự thay đổi của hàm mục tiêu. Thực hiện ý tưởng trên ta được :

Suy ra : (dòng 1 được chọn)

Người ta chọn x1=52 size 12{x rSub { size 8{1} } = { {5} over {2} } } {} nên nhận được một phương án tốt hơn được xác định như sau :

Giá trị tương ứng của hàm mục tiêu là

Bước tiếp theo là biến đổi bài toán (I) thành một bài toán tương đương bằng cách từ dòng 1 ( dòng được chọn ) tính x₁ theo các biến còn lại và thế giá trị nhận được vào các dòng còn lại, ta được :

(II)

Thực hiện tương tự như trên, người ta tăng x₃ từ bằng 0 lên một giá trị dương cho phép và đồng thời vẫn giữ x₂ và w₁ bằng 0 thì giá trị của hàm của hàm mục tiêu sẽ giảm xuống. Khi đó các biến ở vế trái của bài toán (II) sẽ bị thay đổi theo nhưng phải thoả ≥ 0 . Ta được :

( dòng 3 được chọn )

Khi đó người ta chọn x₃=1 nên thu được một phương án tốt hơn được xác định như sau :

Giá trị tương ứng của hàm mục tiêu là z(x)=-13

Bước tiếp theo là biến đổi bài toán (II) thành một bài toán tương đương bằng cách từ dòng 3 ( dòng đựợc chọn ) tính x₃ theo các biến còn lại và thế giá trị nhận được vào các dòng còn lại, ta được :

(III)

Đến đây vì không có hệ số nào của hàm mục tiêu là âm nên không thể làm giảm giá trị của hàm mục tiêu theo cách như trên nữa. Phương án thu được ở bước sau cùng chính là phương án tối ưu của bài toán.

Đối với bài toán max, thay cho việc làm tăng biến có hệ số âm trong hàm mục tiêu người ta làm tăng biến có hệ số dương cho đến khi các hệ số trong hàm mục tiêu hoàn toàn âm.