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

Giai đoạn 2 : kiểm tra tính tối ưu

Đây là phương án tối ưu

Với cước phí là :

1.50+3.10+2.20+6.10+7.70=670

Khi sử dụng phương án ban đầu

thì cước phí là :

1.50+3.20+2.20+7.60+11.10=680

Các bài toán được đưa về bài toán vận tải

Có nhiều bài toán thực tế có tính chất không phải là ’’vận tải ’’ nhưng có mô hình toán học là bài toán vận tải. Một số bài toán như vậy là :

a- Bài toán bổ nhiệm

Giả sử tập hợp S gồm m người và tập hợp D gồm n công việc (chức vụ). Cước phí của việc bổ nhiệm người iS vào việc jD là cij (i=1m , j=1n). Bài toán đặt ra là tìm cách chia mỗi người đúng một việc sao cho cước phí bổ nhiệm là nhỏ nhất.

Người ta đặt biến (biến trên dòng) như sau :

$\begin{array}{}1\text{nÕu ng­êi i nhËn viÖc j}\\ 0\text{nÕu tr­êng hîp kh¸c}\\ \\ x_{\text{ij}}=\begin{array}{}\{\end{array}\\ \end{array}$

thì bài toán trở thành :

$\text{min}\sum _{i\in S}\sum _{j\in D}{c}_{\text{ij}}{x}_{\text{ij}}$

Vì mỗi người nhận đúng 1 việc nên : $\sum _{j\in D}{x}_{\text{ij}}=1(\forall i\in S)$

Vì mỗi việc chỉ giao cho một người nên : $\sum _{i\in S}{x}_{\text{ij}}=1(\forall j\in D)$

Đây là bài toán vận tải nhưng có thêm yêu cầu là các biến xij chỉ lấy giá trị 0 hoặc 1.

Bài toán bổ nhiệm cũng có khi được gọi là bài toán chọn (Choice Problem). Nhiều bài toán thực tế đa dạng có mô hình toán học là bài toán bổ nhiệm, chẳng hạn như bài toán phân bố hoả lực vào mục tiêu cần tiêu diệt.

b- Bài toán vận tải với cung ít hơn cầu

Xét một bài toán một bài toán vận tải với S là tập hợp m nút cung và D là tập hợp n nút cầu mà tổng nguồn cung nhỏ hơn tổng nhu cầu, tức là

Trong trường hợp này tất nhiên không thể đáp ứng đủ nhu cầu dj cho mỗi nút j=1n cho nên ràng buộc có dạng bất đẳng thức thay vì là đẳng thức. Vậy :

Người ta thường đưa bài toán này về bài toán vận tải (đóng) theo một trong hai trường hợp sau đây :

1.Trường hợp thứ nhất là có tính đến sự thiệt hại bằng tiền khi thiếu một đơn vị hàng hoá ở nút cầu j là rj (j=1n)

Lúc này người ta đưa thêm vào một nút cung giả (m+1) với nguồn cung là

$s_{m+1}=\sum _{j=1}^n{d}_j-\sum _{i=1}^n{s}_i$

và cước phí tương ứng là

c(m+1) j = rj(j=1n)

Khi đó ta nhận được một bài toán vận tải (đóng)

$\begin{array}{}\text{min}\sum _{i=1}^{m+1}\sum _{j=1}^n{c}_{\text{ij}}{x}_{\text{ij}}\\ \sum _{i=1}^{m+1}{x}_{\text{ij}}=d_j(j=1\to n)\\ \sum _{j=1}^n{x}_{\text{ij}}=s_i(i=1\to m)\\ x_{\text{ij}}\ge 0(i=1\to m+\text{1,j}=1\to n)\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$

2.Trường hợp thứ hai là không tính đến sự thiệt hại do thiếu hàng ở nút cầu

Lúc này ta cũng đưa về bài toán vận tải (đóng) như trên, nhưng vì không tính đến sự thiệt hại nên mục tiêu sẽ là

$\text{min}\sum _{i=1}^m\sum _{j=1}^n{c}_{\text{ij}}{x}_{\text{ij}}$

Ghi chú :

Với bài toán vận tải mở, nguồn chuyển không hết sang các nhu cầu, người ta có thể tính thêm cước phí lưu kho ở mỗi nguồn cho mỗi đơn vị hàng là ci (n+1) (i=1m) . Hoàn toàn tương tự như trên, khi đưa bài toán này về bài toán vận tải (đóng) bằng cách thêm vào nút cầu giả (n+1) thì hàm mục tiêu trở thành

$\text{min}\sum _{j=1}^{n+1}\sum _{i=1}^m{c}_{\text{ij}}{x}_{\text{ij}}$

Như vậy ta chỉ cần xét bài toán vận tải (đóng)

$\begin{array}{}\text{min}\sum _{j=1}^{n+1}\sum _{i=1}^m{c}_{\text{ij}}{x}_{\text{ij}}\\ \sum _{j=1}^n{x}_{\text{ij}}=s_i(i=1\to m)\\ \sum _{i=1}^m{x}_{\text{ij}}=d_j(j=1\to n)\\ x_{\text{ij}}\ge 0(i=1\to m\text{,j}=1\to n)\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$

c- Bài toán vận tải có đường cấm

Đây là bài toán vận tải nhưng không phải mỗi nguồn đều có cung nối với mọi đích. nghĩa là có đường cấm. Cách đưa về bài toán vận tải là dùng phương pháp M-lớn, tức là phương pháp phạt như sau :

Gọi E là tập các cung không cấm, tức là các cung (i,j), iS, jD và bài toán có thêm điều kiện