tailieunhanh - Công nghệ thông tin - Chương 10

Như trên đã phân tích, một đơn vị hàng đưa vào ô (3, 2) làm giảm tổng chi phí vận tải 2 USD. Ta cần tìm q, lượng hàng tối đa có thể đưa vào ô (3, 2). Đường đi qua ô (3, 2) và một số ô đã được sử dụng là: (3, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 2), với các ô được đánh dấu cộng trừ xen kẽ (ô (3, 2) mang dấu +). | - Nhập Cj aj Vj 1 2 . n và b. Đặt k 0. - Nếu ràng buộc dạng thì đặt F0 y 0 Vy 0 b . - Nếu ràng buộc dạng thì đặt F0 0 0 và F0 y - x Vy 1 b . Các bước lặp Bước 1 Đặt k k 1. Bước 2 Vy 0 b i Tính Fk y theo hệ thức truy toán Fk y Max ckxk Fk -i y - akxk trong đó Jk 0 1 . y ak xk eJk hoặc theo hệ thức Dantzig F w _ Max Fk-1 y ck Fk y- ak y ak Fk y -11 Fk-i y y ak. ii Tính jk y Khi k 1 thì j1 y 0 nếu F1 y 0 và j1 y 1 nếu F1 y 0. . jk-i y khi Fk-i y - Fk y Còn với k 1 thì L y - ._ . J y k khi Fk-i y Fk y . Bước 3 Nếu k n thì quay về bước 1. Bước kết thúc i Zmax Fn b . Giả sử jn b m n và m 0 thì có xn xn-1 . xm 1 0. Đặt b b i m. ii Nếu gọi s là số nguyên không âm sao cho jn b jn b - ai jn b - 2ai . jn b - sxai jn b - sxai jn b - s 1 xai thì x 1 s. iii Đặt b b - s 1 xai i jn b . Nếu i 0 thì quay về bước ii còn nếu trái lại thì in lưu trữ kết quả và dừng. . Hợp nhất hóa các ràng buộc của bài toán quy hoạch tuyến tính nguyên Ví dụ 6. Xét BTQHTT nguyên với miền ràng buộc cho bởi 3x1 2x2 10 x1 4 x2 11 3x1 3x2 13 x1 x2 0 và nguyên. 3x1 2x2 x3 - 10 x1 4 x2 x4 - 11 3x1 3x2 x5 - 13 x1 x2 . x5 0 và nguyên. 100 Hệ ràng buộc trên có ba ràng buộc dạng đẳng thức không kể điều kiện nguyên không âm của các biến . Để đưa BTQHTT nguyên trên đây về bài toán cái túi chúng ta cần hợp nhất hóa các ràng buộc này thành một ràng buộc dạng đẳng thức. Trước hết chúng ta xét cách hợp nhất hóa hai đẳng thức. Định lý 1. Xét hệ hai phương trình Ẻa1jXj b1 L a2jXj b2 . I j 1 Trong đó các hệ số aij 0 bi 0 Vj 1 n và Vi 1 2. Nếu t1 và t2 thỏa mãn các điều kiện - t1 t2 e N và t1 t2 1 - t1 không là ước của b2 - t2 không là ước của b1 - t1 b2 - amin t2 b1 - amin trong đó amin Min aij Vj 1 n và i 1 2 . thì tập nghiệm nguyên không âm của hệ sẽ trùng với tập nghiệm nguyên không âm của phương trình t1a1j t2a2j Xj t1b1 t2b2 . j i Chứng minh Rõ ràng mọi phương án nguyên không âm của cũng là phương án nguyên không âm của . Chúng ta sẽ đi chứng minh chiều