Tham khảo tài liệu 'chương 3: bài toán vận tải - bài 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | CHƯƠNG 3- BÀI TOÁN VẬN TẢI íBài S giải btvt đóng bằng thuật Toán thế vị 1 Cơ sở toán học Với bài toán vậntảidạng tổng quát P n m f x XX CiiXii min i 1 i 1 z m X Xj a í 1 n X X b i 1 X 0 i 1 n i 1 m chương 3- BÀI TOÁN VẬN TẢI Bài SGIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 1 Cơ sở toán học Ta có bài toán đốingẫu D tương ứng như sau g u V X aiui X bivi max i 1 i 1 u7 V C-- i 1 n i 1 m I 7 J iJ Và các cặp ràng buộc đốingẫucủa P D có dạng xii 0 và u Vj Cj i 1 n i 1 m 2 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI GIẢI BTVT ĐÓNG BẰNG THUẬT Toán thế vị sở toán học Giả sử P có PACB không suy biến X Xij Khi đó theo định lý độ lệch bù yếu để x0 là PATU của bài toán P thì phảitồntạimộtphương án ui Vj của D u v cij V X0 0 ii Vx0 0 i 1 n j 1 m ii u v c i j ij Đây là tiêu chuẩntối ưucủa PA x0. 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢI GIẢI BTVT ĐÓNG BẰNG THUẬT Toán thế vị sở toán học Giả sử P có PACB không suy biến X Xij Khi đó theo định lý độ lệch bù yếu để x0 là PATU của bài V X0 0 ij toán P thì phảitồntạimộtphương án ui vj của D ui v c 0 U v c VX 0 i 1 n j 1 m 1 j lj ij ỵ y -J J y Đây là tiêu chuẩntối ưucủa PA x0. Uị Vj lầnlượt đượcgọilàthế vị dòng thế vị cột A. ui v - C-. hệ sốướclượng. u 1 j u 4 2 CHƯƠNG 3- BÀI TOÁN VẬN TẢI GIẢI BTVT ĐÓNG BẰNG THUẬT Toán thế vị i dung thuâttoán Với X0 0 ta có đẳng thức Uị Vj Cj - ở các ô chọn nếubiết Uị thì sẽ xác định được Vj và ngượclại nếubiết Vj thì sẽ xác định được Uị. Từ hệ U vj vừatìm được nếutấtcả các cặp u Vj đềuthoả mãn hệ ràng buộc D thì x0 là PATU của P Ngượclại nếutồntạiítnhất1 HSUL Aij ui Vj cij 0 thì x0 chưalàPATU. 5 chương 3- BÀI TOÁN VẬN TẢI íBài S giải btvt Đóng bằng thuật Toán thế vị 3 Điềuchỉnh phương án khi tồntai HSUL dương Tìm giá trị lớnnhấtcủa Aij để xác định ô được đưa vào hệ thống ô chọn giả sử là ô i0 j0 . Từ ô này ta tìm vòng điềuchỉnh. Trên vòng điềuchỉnh ta đánh vị trí chẵn lẻ của các ô chọn xuất phát từ ô i0 j0 được đánh vị trí lẻ. Ô chẵnvớilượng hàng q nhỏ nhấtlà ô đượcchọn đưara khỏihệ thống ô chọnvàq lúcnày đượcgọilà lượng hàng .
