0.3 Ứng dụng quy hoạch tuyến tính  (Page 5/9)

$\text{min}\text{z}(x)=\sum _i\sum _j{c}_{\text{ij}}{x}_{\text{ij}}$

Với các phân tích trên ta có mô hình của bài toán như sau :

$\begin{array}{}\text{min}\text{z}(x)=\sum _{i=1}^n\sum _{j=1}^n{c}_{\text{ij}}{x}_{\text{ij}}(1)\\ \sum _{j=1}^n{x}_{\text{ij}}=a_i(i=\text{1,2,}\text{.}\text{.}\text{.}\text{,m})\\ \sum _{i=1}^m{x}_{\text{ij}}=b_j(j=\text{1,2,}\text{.}\text{.}\text{.}\text{,n})\\ (2)\\ \\ \\ \begin{array}{}{x}_{\text{ij}}\ge 0(3)\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Phương án - Phương án tối ưu

Một ma trận X=[xij]m.n thỏa (2) và (3) được gọi là phương án, thỏa thêm (1) được gọi là phương án tối ưu.

b- Dạng bảng của bài toán vận tải

Có thể giải bài toán vận tải theo cách của quy hoạch tuyến tính. Tuy nhiên do tính chất đặc biệt của bài toán vận tải nên người ta nghĩ ra một thuật toán hiệu quả hơn. Trước tiên người ta trình bày bài toán vận tải dưới dạng bảng như sau :

Trong bảng mỗi hàng mô tả một điểm phát, mỗi cột mô tả một điểm thu, mỗi ô mô tả một tuyến đường đi từ một điểm phát tới một điểm thu.

Dây chuyền - Chu trình

Một dãy các ô của bảng mà hai ô liên tiếp nằm trong cùng một hàng hoặc một cột, ba ô liên tiếp không cùng nằm trên một hàng hoặc một cột được gọi là một dây chuyền. Ta thấy rằng hai ô liền nhau trong một dây chuyền có chỉ số hàng hoặc chỉ số cột bằng nhau

Dây chuyền : (1,2) (1,3) (2,3) (2,4) (4,4) (4,1)

Một dây chuyền khép kín, ô đầu tiên và ô cuối cùng bằng nhau, được gọi là một chu trình.Ta thấy rằng số ô trong một chu trình là một số chẵn.

Chu trình : (1,1) (1,3) (2,3) (2,4) (4,4) (4,1) (1,1)

Ô chọn - Ô loại

Giả sử ma trận X=[xij]m.n (i=1,2,...,m) (j=1,2,...,n) là một phương án của bài toán vận tải.

Những ô trong bảng tương ứng với xij>0 được gọi là ô chọn, những ô còn lại được gọi là ô loại.

Phương án cơ bản

Một phương án mà các ô chọn không tạo thành một chu trình được gọi là phương án cơ bản.

Một phương án có đủ m+n-1 ô chọn được gọi là không suy biến, có ít hơn m+n-1 ô chọn được gọi là suy biến. Trong trường hợp suy biến người ta chọn bổ sung vào phương án cơ bản một số ô loại có lượng hàng bằng 0 để phương án cơ bản trở thành không suy biến

c- Giải bài toán vận tải

Xét bài toán vận tải có số lượng phát, số lượng thu và ma trân cước phí ở dạng bảng như sau :

LẬP PHƯƠNG ÁN CƠ BẢN BAN ĐẦU

Phương án cơ bản ban đầu được xác định bằng cách ưu tiên phân phối nhiều nhất vào ô có cước phí nhỏ nhất (r,s) ( gọi là ô chọn). Khi đó : nếu điểm phát r đã phát hết hàng thì xóa hàng r của bảng và số lượng cần thu tại điểm s chỉ còn là bs-ar ; nếu điểm thu s đã nhận đủ hàng thì xóa cột s của bảng và số lượng phát còn lại tại điểm phát r là ar-bs

Bảng mới thu được có kích thước giảm đi. Tiếp tục phân phối như trên cho đến khi hết hàng.

Các ô chọn trong quá trình phân phối, sẽ không chứa chu trình, là một phương án cơ bản. Nếu phương án cơ bản suy biến, chưa đủ m+n-1 ô, thì bổ sung thêm một số " ô chọn 0 "

Áp dụng vào bài toán đang xét :

1- Phân vào ô (1,3) 50 . Hàng (1) bị xóa . Cột (3) còn thu 60-50=10

2- Phân vào ô (2,2) 20 . Cột (2) bị xóa . Hàng (2) còn phát 40-20=20