Phương pháp góc tây bắc trong bài toán vận tải năm 2024

Dữ liệu và nguồn

• TTKHCNQG, CTv63PDF
  • Thông tin thêm
  • Đến nguồn

Thông tin bộ dữ liệu

Nhan đề ứng dụng phương pháp "Góc Tây bắc" để giải bài toán vận tải hở trên các mỏ lộ thiên ở Việt Nam Lĩnh vực Tác giả

• Đoàn Trọng Luật
• Bùi Xuân Nam Nguồn trích (Bao gồm Số, ISSN, trang, địa chỉ) Công nghiệp Mỏ Năm xuất bản 2016 Tổ chức chủ trì nhiệm vụ Sản phẩm của nhiệm vụ

Chương 3: BÀI TOÁN VẬN TẢI

NỘI DUNG 3.1 Nội dung và đặc điểm bài toán vận tải 3.1.1 Nội dung kinh tế và mô hình toán học 3.1.2 Phương án cực biên 3.1.3 Các tính chất của bài toán vận tải 3.2 Phương pháp tìm phương án cực biên ban đầu 3.2.1 Phương pháp min cước 3.2.2 Phương pháp góc Tây - Bắc 3.2.3 Phương pháp Foghen 3.3 Phương pháp thế vị giải bài toán vận tải 3.3.1 Bài toán đối ngẫu và tiêu chuẩn tối ưu 3.3.2 Thuật toán thế vị

NỘI DUNG 3.4 Một số dạng đặc biệt của bài toán vận tải 3.4.1 Bài toán chỉ có hai trạm phát hoặc hai trạm thu 3.4.2 Bài toán vận tải không cân bằng thu phát 3.4.3 Bài toán vận tải cực đại 3.4.4 Bài toán vận tải có ô cấm 3.4.5 Bài toán lập kho trạm hợp lý 3.4.6 Bài toán vận tải theo thời gian

TÌM PHƯƠNG ÁN XUẤT PHÁT CHO BÀI TOÁN

VẬN TẢI

Phương pháp góc tây bắc (northwest - conner rule)

Ta ưu tiên phân phối lượng hàng nhiều nhất vào ô ở góc tây bắc trên bảng vận

tải. Khi đó, nếu:

•Điểm phát nào đã hết hàng thì ta xóa dòng chứa điểm phát đó.

•Điểm thu nào đã đủ hàng thì ta xóa cột chứa điểm thu đó.

Lặp lại quá trình trên đối với những ô còn lại.

Cụ thể, trước tiên, ta lập bảng vận tải Tvới các số liệu ai, bj, cij , i \=1, m, j \=

1, n.

1. Bắt đầu từ ô ở vị trí góc tây bắc của bảng vận tải T(ô (1,1)), ta điền lượng

hàng x11 lớn nhất có thể vào đó (tức cho chuyển một lượng hàng lớn nhất có

thể từ điểm phát 1đến điểm thu 1). Dễ thấy

x11 \=min{a1, b1}.

Khi đó sẽ có ba trường hợp có thể xảy ra:

•Trường hợp 1: Nếu x11 \=a1< b1(điểm phát 1 đã hết hàng, điểm thu 1

còn cần b1−a1đơn vị hàng), xóa hàng thứ nhất của bảng Tta thu được

bảng T′gồm (m−1) hàng và ncột với lượng phát, thu tương ứng:

a′

i\=ai, i \=2, m,

b′

1\=b1−x11 \=b1−a1;b′

j\=bj, j \=2, n;

•Trường hợp 2: Nếu x11 \=b1< a1(điểm phát 1 còn a1−b1đơn vị hàng,

điểm thu 1 đã thỏa mãn nhu cầu), xóa cột thứ nhất của bảng Tta thu