Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 3: Bài toán vận tải

Chia sẻ: Hoamaudon | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST

Báo xấu

36
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 3: Bài toán vận tải cung cấp cho người học những kiến thức như: Thiết lập bài toán vận tải (btvt); Phương án của bài toán vận tải; Giải bài toán vận tải; Bài toán vận tải mở; Bài toán vận tải có hàm mục tiêu max. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 3: Bài toán vận tải

Chương 3 BÀI TOÁN VẬN TẢI 1
2 NỘI DUNG CHƯƠNG 3.1 Thiết lập bài toán vận tải (btvt) 3.2 Phương án của bài toán vận tải 3.3 Giải bài toán vận tải 3.4 Bài toán vận tải mở 3.5 Bài toán vận tải có hàm mục tiêu max
3.1 Thiết lập bài toán vận tải (btvt) 3.1.1 Bài toán vận tải Một công ty cần vận chuyển hàng hóa từ các kho hàng Ai,(i=1,..,m) (gọi là trạm phát) có trữ lượng hàng hóa tương ứng là ai đến các cửa hàng Bj ,(j=1,..,n) (gọi là trạm thu) với nhu cầu tiếp nhận khối lượng hàng hóa tương ứng là bj . Giả sử tổng cung bằng tổng cầu, i.e., m n  ai   bj i 1 j 1 3
4 3.1.1 Bài toán vận tải Cho biết cước phí vận chuyển 1 đơn vị hàng hóa từ Ai đến Bj là cij, (i=1,..,m; j=1,..,n). Bài toán lập kế hoạch vận chuyển hàng hóa sao cho các trạm phát hết hàng, các trạm thu nhận đủ hàng và tổng cước phí vận chuyển thấp nhất gọi là bài toán vận tải.
5 3.1.2 Mô hình toán học của BTVT Gọi xij,(i=1,..,m; j=1,..,n) là số đơn vị hàng hóa cần vận chuyển từ Ai đến Bj. Điều kiện: xij0, i,j Khi đó mô hình toán học của btvt là bt QHTT sau:
6 3.1.2 Mô hình toán học của BTVT . m n BT (3.1.1) thỏa Z   cij xij  min i 1 j 1 điều kiện n  ai   bj  xij  ai , (i  1, m) (3.1.1) gọi là btvt đóng. j 1 m Nếu không thỏa  xij  b j , ( j  1, n) đk này thì gọi là i 1 btvt mở. xij  0, (i  1, m, j  1, n)
3.1.3 Dạng bảng của bài toán vận tải Thu b1 b2 … bn Phát a1 c11 c12 … c1n a2 c21 c22 … c2n … … … … … am cm1 cm2 … cmn Ma trận C=(cij)Mmn(R) gọi là ma trận cước phí của btvt. 7
3.1.4 Mô hình toán học dạng bảng . Thu b1 b2 .. bn Phát a1 c11 c12 … c1n x11 x12 x1n a2 c21 c22 … c2n x21 x22 x2n … … … … … am cm1 cm2 … cmn xm1 xm2 xmn 8
9 3.1.4 Mô hình toán học dạng bảng Trong mô hình dạng bảng thì mỗi ô chứa một biến nên mỗi ô được xem như một biến. Ma trận X=(xij) Mmn(R) gọi là ma trận hàng hóa và cũng là ma trận ẩn số của btvt.
3.2 Phương án của bài toán vận tải 3.2.1 Định nghĩa: Nếu x0ij là lượng hàng hóa vận chuyển từ Ai đến Bj thì phương án của btvt là ma trận X=(x0ij) Mmn(R) thỏa các Rb của (3.1.1). Ví dụ 3.2.1 Xét btvt  0 30 0  P T 20 40 40   X   0 0 30  0 30 2 1 3  20 10 10  0 30 0   30 4 0 5 0 2 30 là một PA của bài 40 2 20 3 10 6 10 toán. 10
11 3.2.2 Phương án cơ bản (PACB) của btvt i) Ô chọn (ô cơ sở) Trong một PA của btvt thì ô có lượng hàng dương gọi là ô chọn.Ô có lượng hàng bằng 0 gọi là ô loại hay ô không cơ sở. ii) Chu trình (vòng) Một dãy các ô chọn của một PA của btvt được gọi là tạo nên một chu trình nếu chúng tạo nên đường gãy khúc khép kín, chổ gãy là góc vuông và là ô chọn, đồng thời mỗi cạnh của đường này chỉ chứa 2 ô chọn.
3.2.2 Phương án cơ bản của btvt Một số chu trình thường gặp                      “” ký hiệu ô chọn. Nhận xét: Số ô chọn trong một chu trình luôn là số chẵn. 12
13 3.2.2 Phương án cơ bản của btvt iii) PACB Một PA của btvt được gọi là PACB nếu các ô chọn của PA đó không tạo nên một chu trình. P T 20 40 40 PA của Ví dụ 3.2.1 30 2 0 1  30 3 0 là một PACB. 30 4 5 2  0 0 30 40 2  3  6  20 10 10
14 3.2.2 Phương án cơ bản của btvt iv) PACB không suy biến Xét btvt có m trạm phát và n trạm thu. - PACB không suy biến là PACB của btvt có số ô chọn bằng m+n-1. - PACB có số ô chọn < m+n-1 thì gọi là PACB suy biến. Để một PACB suy biến trở thành PACB không suy biến ta bổ sung một số “ô chọn không”.
15 3.2.2 Phương án cơ bản của btvt Ví dụ 3.2.2 Xét btvt  0 0 20    P T 40 40 20 X   40 10 0  0  0 30 0  20 5 0 3 0 1 20   là PACB suy biến vì 50 7  40 6 10 8 0 số ô chọn 4 < 3+3-1 30 3 0 2 30 2 0 Để PA trên trở thành ko suy biến ta bổ sung một “ô chọn 0” là 1 trong các ô: (1,1), (1,2), (2,3) và (2,4). Ô (3,1) không được chọn vì ô này tạo với (3,2),(2,2) và (2,1) thành một chu trình.
16 3.2.3 Tính chất của btvt Xét btvt có m trạm phát và n trạm thu. i) Mọi btvt đều có phương án tối ưu. ii) Trong một bài toán vận tải thì số ô chọn của một PACB không bao giờ vượt quá m+n-1 ô. iii)Với một PACB không suy biến thì một ô loại bất kỳ cũng tạo với các ô chọn của PA đó thành một chu trình duy nhất.
17 3.3 Giải bài toán vận tải – PP thế vị Thuật toán được xây dựng trên ý tưởng: tiến dần đến tối ưu. Xuất phát từ một PACB không suy biến của bài toán, đánh giá tính tối ưu của PA đó. - Nếu tối ưu thì dừng thuật toán. - Ngược lại ta tìm cách xây dựng PACB mới tốt hơn, rồi đánh giá tính tối ưu của nó.
18 3.3 Giải bài toán vận tải – PP thế vị Thuật toán được tiến hành với 3 bước chính: Bước 1. Xây dựng PACB xuất phát Bước 2. Xây dựng tiêu chuẩn tối ưu Bước 3. Xây dựng PACB mới tốt hơn
19 3.3.1 Xây dựng PACB xuất phát Để chắc chắn có được một PACB ta xây dựng bằng 1 trong 3 PP sau: i) Phương pháp góc Tây-Bắc Ưu tiên phân phối hàng hóa (hh) vào ô góc trên bên trái cùa bảng. Bước 1: Phân phối hàng hóa tối đa vào ô (1,1). Bươc 2: Điều chỉnh lượng hh ở các trạm phát và trạm thu chứa ô phân phối hàng ở Bước 1
20 3.3.1 Xây dựng PACB xuất phát và bỏ đi dòng hoặc cột chứa trạm phát hoặc trạm thu có lượng hàng bằng 0. Bước 3: Phân phối hh tối đa vào ô góc trên bên trái của bảng còn lại. Bước 4: Lặp lại Bước 2. Quá trình này được lặp lại chó đến khi các trạm phát phát hết hàng và các trạn thu nhận đủ hàng ta sẽ được PACB của bài toán.