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

Phương án tối ưu của bài toán (P) là :

$\begin{array}{}\frac{1}{g_2}=\frac{\text{23}}{\text{107}}\\ y_1=\frac{q_1}{g_2}=\frac{7}{\text{107}}\\ y_2=\frac{q_2}{g_2}=\frac{6}{\text{107}}\\ y_3=\frac{q_3}{g_2}=\frac{\text{10}}{\text{107}}\\ \text{suy ra}\\ \\ g_2=\frac{\text{107}}{\text{23}}\\ q_1=\frac{7}{\text{23}}\\ q_2=\frac{6}{\text{23}}\\ q_3=\frac{\text{10}}{\text{23}}\\ \\ \begin{array}{}\{\{\{\end{array}\\ \end{array}$

Phương án tối ưu của bài toán đối ngẫu (D) được tính bằng công thức sau : $\begin{array}{}{x}^T=\left[\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right]=c_B^T{B}^{-1}=\left[\begin{array}{ccc}1& 1& 1\end{array}\right]\left[\begin{array}{ccc}\frac{\text{37}}{\text{214}}& -\frac{\text{16}}{\text{107}}& \frac{7}{\text{214}}\\ \frac{\text{13}}{\text{107}}& \frac{9}{\text{107}}& -\frac{\text{12}}{\text{107}}\\ -\frac{\text{23}}{\text{107}}& \frac{\text{17}}{\text{107}}& \frac{\text{13}}{\text{107}}\end{array}\right]\\ =\left[\begin{array}{ccc}\frac{\text{17}}{\text{214}}& \frac{\text{10}}{\text{107}}& \frac{9}{\text{214}}\end{array}\right]\end{array}$

$w=\frac{1}{g_1}=b^{T}x=\left[\begin{array}{ccc}1& 1& 1\end{array}\right]\left[\begin{array}{c}\frac{\text{17}}{\text{214}}\\ \frac{\text{10}}{\text{107}}\\ \frac{9}{\text{214}}\end{array}\right]=\frac{\text{23}}{\text{107}}$

Ta có :

$\begin{array}{}w=\frac{1}{g_1}=\frac{\text{23}}{\text{107}}\\ x_1=\frac{p_1}{g_1}=\frac{\text{17}}{\text{214}}\\ x_2=\frac{p_2}{g_1}=\frac{\text{10}}{\text{107}}\\ x_3=\frac{p_3}{g_1}=\frac{9}{\text{214}}\\ \text{suy ra}\\ \\ g_1=\frac{\text{107}}{\text{23}}\\ p_1=\frac{\text{17}}{\text{46}}\\ p_2=\frac{\text{10}}{\text{23}}\\ p_3=\frac{9}{\text{46}}\\ \\ \\ \begin{array}{}\{\{\{\end{array}\\ \end{array}$

Bài toán vận tải

Mở đầu

Bài toán vận tải là bài toán quan trọng nhất trong các bài toán quy hoạch tuyến tính. Người ta tổng kết rằng 85% các bài toán quy hoạch tuyến tính gặp trong ứng dụng là bài toán vận tải hoặc mở rộng của nó. Thuật ngữ bài toán vận tải thường được hiểu là bài toán vận chuyển sao cho cước phí nhỏ nhất.

Các khái niệm cơ bản

Bài toán vận tải được mô tả như là một bài toán về dòng dữ liệu gồm tập hợp các nút N được chia thành hai phần rời nhau : các nút nguồn S và các nút đích D, tức là :

$\begin{array}{}N=S\cup D\\ S\cap D=\varnothing \\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

và mỗi cung (i,j) trong tập các cung A đều có gốc trong S và có ngọn trong D.

S:Các nút nguồnD:Các nút đích

Các nút thuộc S được gọi là các nút nguồn (cung), các nút thuộc D được gọi là các nút đích (cầu). Một cách tổng quát, bài toán vận tải trình bày được bằng đồ thị.

Ở bài toán vận tải đôi khi còn có thêm giả thiết nữa là mỗi nút nguồn đều có cung nối với mọi nút đích. Ở đây ta chỉ đề cập đến bài toán vận tải có thêm giả thiết này và sẽ gọi tắt là bài toán vận tải.

Đối với bài toán vận tải người ta thường ký hiệu

si  S là nguồn phát ở nút i(i=1m)

dj  D là nhu cầu thu của nút j (j=1n)

Trong trường hợp các nguồn phát không chuyển hết sang các nút cầu vì đã đủ nhu cầu thì bài toán vận tải được gọi là bài toán vận tải mở. Có thể đưa một bài toán vận tải mở về một bài toán vận tải (đóng) bằng cách thêm vào một nút cầu giả thứ (n+1) với nhu cầu được xác định như sau : 

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

Bài toán vận tải cân bằng thu phát

a- Thiết lập bài toán

Có m nơi A1, A2,....,Am cung cấp một loại hàng với khối lượng tương ứng là a1, a2,....,am. Hàng được cung cấp cho n nơi B1, B2,...., Bn với khối lượng tiêu thụ tương ứng là b1, b2,....,bn.

Cước phí chuyên chở một đơn vị hàng từ điểm phát Ai đến điểm thu Bj là cij .

Hãy lập kế hoạch vận chuyển từ mỗi điểm phát đến mỗi điểm thu bao nhiêu hàng để :

- Các điểm phát đều phát hết hàng

- Các điểm thu đều nhận đủ hàng

- Tổng cước phí phải trả là ít nhất

Gọi xij là lượng hàng chuyển từ điểm phát Ai đến điểm thu Bj , xij  0 .

Vì tổng lượng hàng phát đi từ mỗi điểm phát Ai đến mọi điểm thu Bj bằng lượng hàng phát từ Ai nên :

$x_{\mathrm{i1}}+x_{\mathrm{i2}}+\text{.}\text{.}\text{.}\text{.}+x_{\text{in}}=a_i(i=\text{1,2,}\text{.}\text{.}\text{.}\text{,m})$

Vì tổng lượng hàng thu được tại mỗi điểm thu Bj từ mọi điểm phát Ai bằng lượng hàng cần thu tại Bj nên :

$x_{\mathrm{1j}}+x_{\mathrm{2j}}+\text{.}\text{.}\text{.}\text{.}+x_{\text{mj}}=b_{\text{ji}}(j=\text{1,2,}\text{.}\text{.}\text{.}\text{, n})$

Để tổng cước phí là ít nhất cần phải có :