thắc mắc về bài toán vận tải tìm fmax !

các bạn ơi ai biết bài toán tìm fmax khác fmin ở những điểm nào ?

thanks bạn trước nhé . . .

lên lớp anh nói cho . nói qua diễn đàn khó hiểu lắm . trà đá nha !!!!!

fmax cũng như fmin chỷ khác mấy chỗ thôy..=))

bạn ơi mình muốn hỏi mấy chỗ là những chỗ nào ?

có gì ko hiểu lên lớp t nói cho, chứ nói qua diễn đàn hơi khó mà ko rõ dc.

bạn nào đây nhỉ .thanks trước nha !

giải bài toán vận tải tìm Fmin
ta có thể thực hiện theo các bước sau:
Bước 1: lập phương án cơ bản không suy biến xuất phát.
1) Xây dựng phương án cơ bản xuất phát bằng phương pháp "cước phí thấp nhất".
2) Kiểm tra tính không suy biến của phương án cơ bản xuất phát:
Trường hợp 1: Nếu tổng số ô chọn là m+n-1 thì phương án cơ bản xuất phát là phương án không suy biến, ta chuyển qua bước 2.
Trường hợp 2: Nếu tổng số ô chọn nhỏ hơn m+n-1 ô thì ta phải bổ xung vào phương án cơ bản xuất phát 1 số "ô chọn không" để được 1 phương án không suy biến trước khi chuyển qua bước 2.
Bước 2: đánh giá tính tối ưu của phương án cơ bản xuất phát
1) Xây dựng hệ thống thế vị (Ui;Vj).
Hệ thống thế vị (Ui;Vj) của phương án cơ bản xuất phát được xây dựng theo công thức Ui+Vj=Cij như sau:
+ Cho thế vị dòng U1 nhận 1 giá trị tùy ý và ghi bên phải dòng 1 của bảng (thường cho U1=0).
+ Tìm trên dòng 1 ô chọn(1,j) và lấy cước phí C1j của ô chọn đó trừ cho thế vị dòng U1 ta sẽ được thế vị cột Vj tương ứng và ghi phía dưới cột j của bảng.
+ Biết thế vị cột Vj, ta tìm trên cột j ô chọn (i,j) và lấy cước phí Cij của ô chọn đó trừ cho Vj ta được thế vị dòng Ui tương ứng và ghi bên phải dòng i của bảng.
+ Biết thế vị dòng Ui, ta tìm trên dòng i ô chọn (i,j') và lấy cước phí Cij của ô chọn đó trừ cho Ui, ta được thế vị cột Vj tương ứng và ghi phía dưới cột j' của bảng.
Qúa trình đó được thực hiện liên tục cho đến khi xác định được toàn bộ hệ thống thế vị (Ui;Vj).
2) Tính các hệ số ước lượng delta ij:
Các hệ số ước lượng của các ô được tính theo quy tắc sau:
+ Hệ số ước lượng của các ô chọn là 0.
+ Hệ số ước lượng của ô loại (i,j) được tính theo công thức:
Delta = Ui + Vj - Cij.
Chú ý: Hệ số ước lượng của mỗi ô được ghi ở phía đông bắc của ô đó. Các ô chọn có thể không cần ghi hệ số ước lượng 0.
3) Đánh giá tính tối ưu của phương án cơ bản xuất phát.
Trường hợp 1: Nếu các hệ số ước lượng ở các ô đều không dương thì phương án cơ bản xuất phát là phương án tối ưu của bài toán, thuật toán kết thúc với phương án tối ưu là phương án cơ bản xuất phát.
Trường hợp 2: Nếu có 1 ô loại có hệ số ước lượng dương thì phương án cơ bản xuất phát chưa tối ưu, thuật toán tiếp tục bằng cách lập phương án cơ bản mới.
Chú ý: nếu các hệ số ước lượng của các ô loại đều là số âm thì phương án cơ bản xuất phát là phương án tối ưu duy nhất của bài toán. ngược lại thì bài toán có thể có nhiều phương án cơ bản tối ưu.
Bước 3: xây dựng phương án cơ bản mới.
để xây dựng phương án cơ bản mới ta thực hiện theo các bước sau:
1) tìm ô loại đưa ra khỏi hệ thống ô chọn
ô loại được chọn đưa vào làm ô chọn trong phương án cơ bản mới là ô có hệ số ước lượng dương lớn nhất.
2) tìm ô đưa ra khỏi hệ thống ô chọn
để xác định được ô đưa ra khỏi hệ thống ô chọn ta phải thực hiện các công việc sau:
+tìm vòng điều chỉnh: từ ô chọn ta mới đưa vào, ta nối với các ô chọn còn lại để tìm 1 vòng gọi là vòng điều chỉnh.
+xác định ô chẵn, lẻ trong vòng điều chỉnh: lấy ô mới đưa vào làm ô số 1, ta đánh số các ô trong vòng điều chỉnh. các ô 1,3,5,.... là ô lẻ; các ô 2,4,6,... là các ô chẵn. (các ô lẻ ta ghi dấu +, các ô chẵn ta ghi dấu - ở phía dưới, bên trái của ô).
+tìm ô chẵn có lượng hàng nhỏ nhất.
ô chẵn có lượng hàng q nhỏ nhất là ô được đưa ra khỏi hệ thống ô chọn. lượng hàng q gọi là lượng hàng điều chỉnh.
3) cải tiến phương án
phương án cơ bản mới được xây dựng theo quy tắc sau:
+các ô lẻ trong vòng điều chỉnh được cộng vào lượng hàng điều chỉnh.
+các ô chẵn trong vòng điều chỉnh bị trừ đi lượng hàng điều chỉnh.
+các ô còn lại giữ nguyên lượng hàng.
bước 4: đánh giá tính tối ưu của của phương án cơ bản mới
việc đánh giá tính tối ưu của phương án cơ bản mới được thực hiện như bước 2.
thuật toán sẽ kết thúc sau 1 số hữu hạn làn xây dựng phương án cơ bản. khi đó ta sẽ tìm được phương án tối ưu và giá trị tối ưu của bài toán vận tải.
chú ý: khi bổ xung "ô chọn không" hay chọn ô đưa vào: nếu có nhiều ô cùng thỏa mãn điều kiện thì ta nên ưu tiên chọn các ô ở phía tây-bắc (phía trên và bên trái) của bảng.
khi tìm ô đưa ra, nếu lượng hàng nhỏ nhất trong các ô chẵn của vòng điều chỉnh là 0 thì ô đó vãn được chọn làm ô đưa ra.
trong trường hợp này, phương án cơ bản vẫn không thay đổi nhưng hệ thống ô chọn có thay đổi, kết quả đánh giá tính tối ưu của phương án cơ bản có thể khác.

giải bài toán vận tải tìm Fmax
cách giải bài toán vận tải Fmax giống cách giải 1 bài toán vận tải thông thường chỉ cần chú ý các vấn đề sau:
1) khi lập phương án cơ bản xuất phát thì ta phải ưu tiên phân phối vào các ô có "cước phí lớn nhất".
2) khi kết luận tính tối ưu của phương án cơ bản thì điều kiện tối ưu là các hệ số ước lượng phải không âm.
3) khi tìm ô đưa vào thì ta tìm ô có hệ số ước lượng âm nhỏ nhất.
đến đây cậu tự so sánh sự khác nhau giữa 2 bài toán nhé.
chúc cậu thành công!!
[You must be registered and logged in to see this link.] sưu tầm

thanks mrtran nhé !

bài trên là mình lấy từ quyển bài tập của tớ ra, nếu cậu chưa hiểu hoặc muốn lấy ví dụ cụ thể thì thứ 5 mình mang cho cậu mượn nhé.

có j` cứ hỏi a ...THiên thân mag TÊN QUYẾT hâm..=))...

cang hoc cang quen .hot it quen it hoc nhieu quen nhieu .=>hoc it hoc nhieu nhu nhau . chi suong thang khong hoc thoi .

vậy cậu nghỉ học luôn đi cho rảnh