Chứng minh Trước hết, chúng ta sẽ chỉ rằng với hệ thống thế vị {ui, ∀i = 1,m , vj, ∀j = 1,n } thu được ứng với phương án vận tải {xij} đã cho, ta luôn có Δ ij = eij = cij − (u i + v j ) , ∀ô (i, j). Để cho dễ hiểu, chúng ta xét lại ví dụ 5 và bảng . | Chứng minh Trước hết chúng ta sẽ chỉ rằng với hệ thống thế vị ui Vi 1 m Vj Vj 1 n thu được ứng với phương án vận tải xij đã cho ta luôn có Aịj eij cij - Ui Vj Vô i j . Để cho dễ hiểu chúng ta xét lại ví dụ 5 và bảng . Lúc này hệ thống thế vị được xác định từ hệ phương trình U1 V1 3 u2 V1 7 u2 v2 5 u2 V3 2 u3 V3 4 _ u3 V4 5. Bảng . Tính hiệu suất các ô chưa sử dụng 3 5000 2 7 6 7 1000 5 4000 2 1000 3 2 - 7 5 - 2 4 1000 5 1500 5000 6000 2500 6000 4000 2000 1500 13500 Hệ phương trình gồm 6 phương trình và 7 ẩn hạng của ma trận hệ số như đã biết là hạng At 6. Vậy hệ có vô số nghiệm phụ thuộc vào một tham số tức là các giá trị của các ẩn cơ sở xác định duy nhất khi cho ẩn ngoài cơ sở ẩn tự do nhận một giá trị tùy ý . Giả sử v4 0 ở đây v4 được coi là ẩn tự do lúc đó ta có íu 3 5 - V3 4 - u3 -1 V4 u2 2 - V3 3 - V4 V2 5 - u2 V1 7 - u2 4 V4 _ui 3 - Vi -1 - V4 u3 u3 V1 5 -1 4 -1. u2 3 V2 5 l u1 Do đó khi cho một thế vị chọn bất kỳ nhận một giá trị tùy ý thì luôn tính được các thế vị còn lại một cách duy nhất. Hơn nữa cij - ui vj luôn không thay đổi dù thế vị đầu tiên chọn giá trị nào hãy quan sát kỹ hệ phương trình trên để suy ra điều này . Như vậy có thể chọn v4 0 để việc tính toán được đơn giản. 77 Theo cách xây dựng y ui u2 u3 V1 v2 v3 v4 T trên đây thì có y cBB 1 T với B là ma trận cơ sở gồm các cột véc tơ cơ sở của ma trận A . Theo tính chất của cặp bài toán đối ngẫu ta có Aij Ọj -cBB-1Aij cij - yTAịj. Chẳng hạn A11 C11 - Ui U2 U3 Vi V2 V3 V4 1 0 0 1 0 0 0 T C11 - Ui Vi . Một cách tổng quát chúng ta có Aij eij cij - u i Vj ứng với tất cả các ô i j . Từ đây theo định lý 1 của chương II và dựa theo lời chứng minh định lý 2 của chương III cần thay BTG là bài toán Min còn BTĐN là bài toán Max chúng ta có thể chỉ ra được bạn đọc hãy tự chứng minh điều kiện cần và đủ để một phương án vận tải là tối ưu là hệ thống số thế vị tương ứng phải thỏa mãn ui Vj Ọj Vi 1 m Vj 1 n u Vj cij V i j xij 0. Đây chính là đpcm. Bài tập chương III Bài 1. Xét BTQHTT Max z 2x1 5x2 8x3
