<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

Các Phương Pháp Tối Ưu

Bài Toán Vận Tải

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

Danh sách thành viên

1 Trương Minh Hoàng 20200248 Hoàn thành 8 2 Đỗ Khánh Huyền 20206148 Hồn thành tốt, rất tích cực 10 3 Nguyễn Thị Thu Huyền 20200291 Hồn thành tốt, tích cực 9.75 4 Nguyễn Đức Huynh 20206149 Hồn thành tốt, rất tích cực 10 5 Bùi Quốc Khải 20206150 Hoàn thành tốt, tích cực 9.5 6 Hồng Kim Khánh 20216839 Hồn thành tốt, tích cực 9.5 7 Vương Tuấn Kiệt 20206152 Hồn thành tốt, tích cực 9.5 8 Lê Thị Linh 20206201 Hồn thành tốt, rất tích cực 10 9 Nguyễn Bùi Khánh Linh 20206202 Hoàn thành 8 10 Nguyễn Thị Diệu Linh 20206153 Hồn thành tốt, tích cực 9.75

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

Lời cảm ơn

Báo cáo này của nhóm 5 được hồn thành dưới sự hướng dẫn chỉ dạy tận tình của TS. Phạm Thị Hồi, Viện Tốn Ứng dụng Và Tin học. Nhóm chúng em xin được gửi lời cảm ơn chân thành và sâu sắc nhất đến cơ vì cô đã giảng dạy, giúp đỡ tạo điều kiện thuận lợi để chúng em có thể hồn thiện báo cáo này.

<b>Bài báo cáo tìm hiểu về Bài tốn vận tải là công sức của tất cả các thành viên trong nhóm</b>

trong một khoảng thời gian dài, tuy nhiên vẫn cịn nhiều khiếm khuyết trong bài báo cáo, chúng em rất mong được nhận lời nhận xét góp ý từ cơ.

Một lần nữa, chúng em xin cảm ơn cô và chúc cơ nhiều sức khỏe.

<b>Nhóm trưởng</b>

<b>Lê Thị Linh</b>

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

<b>4Phương án xuất phát cho thuật toán thế vị27</b> 4.1 <i>Phương pháp góc tây bắc (Northwest - conner rule) . . . .</i> 27

4.1.1 Ý tưởng phương pháp . . . . 27

4.1.2 Thuật toán . . . . 27

4.1.3 Ví dụ . . . . 27

4.2 <i>Phương pháp cực tiểu chi phí (The least-cost Method) . . . .</i> 30

4.2.1 Ý tưởng phương pháp và thuật toán . . . . 30 5.1 Bài tốn vận tải khơng cân bằng thu - phát . . . . 40

5.1.1 Tổng lượng phát lớn hơn tổng lượng thu . . . . 40

5.1.2 Tổng lượng thu lớn hơn tổng lượng phát . . . . 41

5.1.3 Ví dụ . . . . 41

5.2 Bài toán vận tải với ràng buộc bất đẳng thức . . . . 44

5.3 Bài toán lập kho nhận hàng . . . . 47

5.4 Bài toán vận tải có ơ cấm . . . . 51

5.5 Bài toán vận tải dạng max . . . . 54

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

Lời mở đầu

Trong ngành Toán ứng dụng, tìm kiếm lời giải tối ưu cho các bài toán thực tế là vấn đề được các nhà khoa học đặc biệt rất quan tâm. Mục đích chính của các thuật tốn tìm kiếm lời giải là tìm ra lời giải tối ưu nhất cho bài toán trong thời gian nhỏ nhất.

Bài toán vận tải (Transportation problem) trong quy hoạch tuyến tính cũng đã khá quen thuộc trong Tốn ứng dụng. Bài toán thiết yếu này lần đầu tiên được xây dựng dưới dạng một bài tốn lập trình tuyến tính vào đầu những năm 1940 và được gọi phổ biến là bài tốn giao thơng vận tải. Theo thống kê của Mỹ, có đến 85% các bài tốn quy hoạch tuyến tính gặp trong các ứng dụng thực tế có dạng bài tốn vận tải hoặc dạng mở rộng của nó. Về cơ bản, mục tiêu của bài tốn là giảm thiểu tổng chi phí vận chuyển một loại hàng hóa từ các điểm phát đến các điểm thu. Do chi phí vận chuyển nói chung khơng thể kiểm sốt được, nên việc giảm thiểu tổng chi phí đòi hỏi phải đưa ra các quyết định định tuyến sản phẩm tốt nhất.

Trong bài báo cáo này, chúng ta sẽ nghiên cứu sâu hơn về Phương pháp thế vị (cịn gọi là phương pháp đơn hình vận tải) để giải quyết Bài toán vận tải và một số Bài toán vận tải mở rộng.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

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

<b>1.1 Giới thiệu</b>

Bài toán vận tải (Transportation Problem) là một mơ hình bài tốn vận chuyển hàng hóa từ một số nguồn, kho (điểm bắt đầu) đến một số điểm tiêu thụ (điểm kết thúc) thỏa mãn một số những ràng buộc cho trước với tổng chi phí tối thiểu. Để có được giải pháp tối ưu (Optimal Solution) cho bài tốn, cần có giải pháp khả thi ban đầu (Intial Feasible Solution) cho các quy trình giải pháp hiện có. Lịch sử của bài tốn vận tải có từ rất lâu, và là một trong những dạng biến thể của bài tốn lập trình tuyến tính (Linear Programming), bài tốn vận tải có tác động lớn đến việc thiết lập thuật tốn giải cho bài tốn lập trình tuyến tính.

Bài tốn được F.L.Hitchcock xây dựng lần đầu tiên vào năm 1941, ơng cũng đưa ra một quy trình tính tốn gần giống với phương pháp đơn hình được thành lập sau này để giải quyết vấn đề. Trong giai đoạn chiến tranh thế giới 2 đang bùng nổ, T.C.Koopmans gặp phải vấn đề tương tự liên quan đến cơng việc của mình khi đang là thành viên của Joint Shipping Board.

Phương pháp đơn hình được phát triển bởi G.B.Dantzig để giải quyết bài tốn lập trình tuyến tính một cách hiệu quả trong hầu hết các trường hợp. Sau đó, phương pháp đơn hình được Dantzig áp dụng để giải bài toán vận tải và thu được phương án tối ưu được cơng bố vào năm 1951. Ngồi ra, Dantzig đề xuất một phương pháp riêng biệt mới để tìm phương án khả thi ban đầu cho bài toán vận tải, sau này được Charnes và Cooper đặt tên là quy tắc North West Corner(NWC).

Sự phát triển lý thuyết của một thuật toán giải pháp tối ưu như vậy là quan trọng. Là một lớp của bài toán lập trình tuyến tính (LP), bài tốn vận tải ln là một giải pháp khả thi và tồn tại ít nhất một giải pháp tối ưu. Tuy nhiên, điều kiện khả thi của bài tốn khơng dẫn đến điều kiện tối ưu.

<b>1.2 Mơ hình tốn học</b>

<i>Người ta cần vận chuyển một loại hàng hóa từ m kho chứa hàng ( gọi là điểm phát ) đến nđiểm tiêu thụ ( gọi là điểm thu ). Biết rằng: Điểm phát thứ i chứa a</i>_i đơn vị hàng, i = 1, ..., m; Điểm thu thứ j cần b_jđơn vị hàng, j = 1, ..., n. Chi phí vận chuyển một đơn vị hàng từ điểm xuất phát i đến điểm thu j là c_{i j}, i = 1, ..., m và j = 1, ..., n. Vấn đề đặt ra là cần xác định lượng hàng cần chuyển từ mỗi điểm phát đến từng điểm tiêu thụ như thế nào để chi phí vận chuyển là cực tiểu. Ký hiệu x_{i j}là số lượng hàng cần vận chuyển từ điểm phát thứ i đến điểm thu thứ j, i = 1, ..., m, j= 1, ..., n. Các đại lượng x_{i j} <i>tạo thành ma trận phân phối hàng hóa</i>

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

Để đơn giản, người ta xét bài toán vận tải với giả thiết:

i) x_{i j} ≥ 0, i = 1, ..., m, j = 1, ..., n. Điều đó có nghĩa là hàng hóa được chuyển theo một hướng từ các điểm phát đến các điểm thu, tức là các điểm thu không được trả lại hàng. Dễ thấy rằng x_i_o_j_o= 0 có nghĩa là hàng khơng được chuyển từ điểm phát i_ođến điểm thu j_o; ii) Hàng có thể chuyển từ một điểm phát đến một điểm thu bất kì và ngược lại, một điểm thu

cũng có thể nhận hàng từ một điểm phát tùy ý sao cho các điểm phát phải phát hết hàng và các điểm thu phải thỏa mãn nhu cầu cần có, tức là:

<i>Người ta gọi đây là điều kiện cân bằng thu phát.</i>

Vì chi phí vận chuyển hàng từ điểm phát i đến điểm thu j là c_{i j}x_{i j} nên tổng chi phí vận chuyển hàng từ tất cả các điểm phát đến tất cả các điểm thu là:

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

Như vậy ta thấy ngay điều kiện cân bằng thu phát chính là điều kiện cần và đủ để bài tốn vận tải có nghiệm tối ưu. Vector x = (x₁₁, x₁₂, ..., x_1n, x₂₁, ..., x_2n, ..., x_m1, ..., x_mn)^T thỏa mãn các

<i>ràng buộc trên được gọi là một phương án chấp nhận được của bài toán vận tải. Để đơn giản, ta</i>

thường viết là x = (x_{i j}). Cách biểu diễn phương án x dưới dạng ma trận phân phối hàng hóa và các cước phí c_{i j} ta đã đề cập ở trên.

Ta thấy bài toán vận tải là một bài tốn quy hoạch tuyến tính chính tắc vì ta có thể đưa bài tốn về dạng tìm min của:

trong đó e ∈ R^m×nlà vector có tất cả các thành phần đều bằng 1. Do đó rank A ≤ m + n − 1. Bất kì m + n − 1 hàng nào của A cũng độc lập tuyến tính. Thật vậy, chẳng hạn ta chứng minh nếu

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

Xét các toạ độ n+1, 2n+1,..., (m-1)n+1 của đẳng thức vector này, ta lại có u₂+ v₁= u₃+ v₁= ... = u_m+ v₁= 0

nên ta suy ra u₂= u₃= ... = u_m= 0. Vậy rank A = m + n − 1

<b>Hệ quả 1.1.</b>

i) Phương án cực biên của bài tốn vận tải khơng có nhiều hơn m + n − 1 thành phần dương. ii) Ta nói phương án cực biên cuả bài tốn vận tải là khơng suy biến nếu nó có đúng m + n − 1

thành phần dương và là suy biến nếu nó có ít hơn m + n − 1 thành phần dương.

iii) Mỗi phương án cực biên x^o= (x^o_{i j}) tương ứng với ít nhất một cơ sở gồm m + n − 1 vector A_{i j} độc lập tuyến tính. Trong trường hợp x^o= (x^o_{i j}) là phương án cực biên khơng suy biến thì nó tương ứng với một cơ sở duy nhất là hệ {A_{i j}: x<small>o</small>

<small>i j</small> > 0} gồm m + n − 1 vector độc lập tuyến tính.

<b>1.3 Sự tồn tại của phương án tối ưu</b>

Điều kiện để bải toán vận tải giải được trong bài báo cáo này là khi tổng cung bằng tổng cầu, tức là ∑^m_i=1a_i= ∑ⁿ_j=1b_j. trong đó m biểu thị cho tổng số điểm phát và n biểu thị cho tổng số điểm thu. Nhưng chúng ta cũng biết rằng bài tốn vận tải khơng cân bằng vẫn có thể giải được khi ∑^m_i=1a_i> ∑ⁿ_j=1b_j. Do đó điều kiện khả thi cho bài tốn vận tải khơng đủ để ln chứng minh được bài tốn vận tải ln thật sự giải được. Ta sẽ tìm điều kiện khả thi mới cho bài toán để chứng minh bài tốn ln giải được. Ngồi ra, giới hạn trên được đặt cho các biến cơ bản trong giải pháp khả thi đối với bài tốn vận tải khơng cân bằng. Các định lý dưới đây chỉ ra rằng bài toán vận tải có cả phương án chấp nhận được và phương án tối ưu.

<i><b>Định lý 1.1 (Sự tồn tại phương án chấp nhận được). Giải pháp cho bài toán vận tải sẽ khả thi</b></i>

<i>với x</i>_{i j} <i>là số lượng hàng cần vận chuyển từ điểm phát i đến điểm thu j ,b</i>_j<i>là lượng cầu cho điểmthu j và ailà lượng cung cho điểm phát i</i>

<b>Chứng minh: Giả sử bài toán có phương án tối ưu x</b>^o= (x^o_{i j}) thỏa mãn các ràng buộc ∑ⁿ_j=1x^o_{i j}= a_i, i = 1, ..., m và ∑^m_i=1x^o_{i j} = b_j, j = 1, ..., n. Tính tổng a_itheo i và tổng b_jtheo j ta thu

thỏa mãn các ràng buộc, do đó nó là một phương án chấp nhận

<i>được của bài toán vận tải (đpcm).</i>

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

2Bảng vận tải, chu trình

<i><b>2.1 Bảng vận tải - Transportation table</b></i>

Bài tốn vận tải có thể viết dưới dạng bảng sau đây (gọi là bảng vận tải):

• Lượng phát a_iđược ghi vào ơ (i, 0).

• Lượng thu b_jđược ghi vào ơ (0, j).

• Tập các ơ

T = { (i, j) | i = 1, · · · , m, j = 1, · · · , n}

<i><b>được gọi là phần chính của bảng vận tải.</b></i>

• Chi phí vận chuyển c_{i j} được ghi ở góc trên bên trái ơ (i, j) ∈ T .

• Phương án của bài toán x = (x_{i j}) > 0 được ghi vào góc dưới, bên phải của ơ (i, j) ∈ T .

<i><b>Nhận xét:</b></i>

• Có sự tương ứng 1 − 1 giữa các ô (i, j) ∈ T và các vecto cột của ma trận A. Ký hiệu: G(x) = {(i, j) ∈ T |x_ij> 0}

• |G(x)| là số phần tử của G(x).

• <i>Ơ (i, j) ∈ G(x) là một ơ chọn và ơ (i, j) /∈ G(x) là ơ loại.</i>

• <b>Phương án cực biên có khơng q (m + n − 1) ơ chọn hay ơ sử dụng.</b>

• <b>Phương án cực biên khơng suy biến có đúng (m + n − 1) ơ chọn.</b>

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

<b>2.2 Chu trình</b>

<i><b>Định nghĩa 2.1. Một tập được sắp thứ tự các ô của bảng vận tải được gọi là chu trình nếu nó</b></i>

<i>thỏa mãn đồng thời ba tính chất sau:</i>

• <i>Hai ơ cạnh nhau trong cùng một hàng hay một cột</i>

• <i>Khơng có ba ơ trên cùng một hàng hay một cột</i>

• <i>Ô đầu tiên nằm trong cùng một hàng hay một cột với ơ cuối cùng.</i>

<i><b>Ví dụ 2.1. Dãy các ơ sau đây của bảng vận tải thành lập chu trình</b></i>

• Chu trình là tập hợp các ơ trong bảng vận tải mà trong đó mỗi ơ đều nằm trên cùng một hàng (hoặc cùng một cột) chỉ với một ô đứng trước, đồng thời nằm trên cùng một hàng (hoặc cùng một cột) chỉ với một ơ đứng sau nó.

• Từ định nghĩa, ta thấy một hàng hoặc một cột mà chu trình đi qua bao giờ cũng chỉ có hai ơ thuộc chu trình, do đó tổng số ơ trên chu trình là chẵn và ít nhất là bốn ô.

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

Giả sử G ∈ T là một tập các ơ nào đó của bảng vận tải.

<i><b>Định nghĩa 2.2. Ta nói G ∈ T chứa chu trình nếu ta có thể xây dựng được ít nhất một chu trình</b></i>

<i>gồm các ơ thuộc G</i>⁰<i><b>⊆ G. Trong trường hợp ngược lại, ta nói G khơng chứa chu trình.</b></i>

<i><b>Bổ đề 2.1 (Dấu hiệu nhận biết một tập các ô G có chứa chu trình hay khơng). Giả sử tập các ô G</b></i>

<i>của bảng vận tải thỏa mãn tính chất: trong mỗi hàng và mỗi cột của bảng vận tải hoặc khơngchứa ơ nào của G hoặc có ít nhất là hai ơ của G. Khi đó G chứa chu trình.</i>

<b>Chứng minh bổ đề:</b>

Gọi các ô trong tập G là các ô chọn.

Theo giả thiết, trong mỗi hàng và mỗi cột của bảng vận tải hoặc khơng có ơ chọn nào hoặc có ít nhất hai ơ chọn.

Bắt đầu từ ơ chọn (i₁, j₁) nào đó, ta đánh dấu ơ này bởi dấu (+).

Theo giả thiết, trên hàng i₁có ít nhất một ô chọn khác là (i₁, j₂). Ta đánh dấu ô này bởi dấu (−).

Vì (i₁, j₂) không phải ô chọn duy nhất trên cột j₂nên đi theo cột này đến được ô chọn khác là (i₂, j₂) và đánh dấu (+).

Tiếp tục dịch chuyển tiếp trên hàng i₂đến (i₂, j₃) và đánh dấu (−) v.v...

Q trình này khơng thể kéo dài vơ tận vì số ơ của bảng vận tải là hữu hạn. Vì vậy, đến một lúc nào đó ta sẽ quay trở lại một ơ nào đó mà trước đó ta đã đi qua, tức là phát hiện ra một chu

<i>trình (đpcm).</i>

<i><b>Định lý 2.1. Cho tập các ô G ⊂ T . Khi đó, hệ vecto {A</b></i>_ij<i>|(i, j) ∈ G} độc lập tuyến tính khi và chỉ</i>

<i>khi G khơng chứa chu trình.</i>

<b>Chứng minh</b>

⇒ Giả sử hệ vecto {A_ij|(i, j) ∈ G} độc lập tuyến tính. Ta chứng minh G khơng chứa chu trình. Giả thiết phản chứng rằng G chứa một chu trình là:

Trong đó: e^k, k ∈ {i₁, ..., i_s, m + j₁, ..., m + j_s} là vecto đơn vị thứ k trong không gian R<small>m+n</small>

Theo định nghĩa, hệ véc tơ {A_i₁_j₁, A_i₁_j₂, ..., A_i_s_j_s, A_i_s_j₁} phụ thuộc tuyến tính vì: {A_i₁_j₁, A_i₁_j₂, ..., A_i_s_j_s, A_i_s_j₁} ⊆ {A_{i j}|(i, j) ∈ G}

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Nên hệ {A_{i j}|(i, j) ∈ G} phụ thuộc tuyến tính (mâu thuẫn). Chứng tỏ G khơng chứa chu trình.

⇐ Giả sử các ơ thuộc G khơng chứa chu trình. Ta sẽ chứng minh {A_{i j}|(i, j) ∈ G} độc lập tuyến tính. Xét đẳng thức:

<small>(i, j)∈G</small>

<b>Vì G khơng chứa chu trình, theo Bổ đề 2.1, tồn tại một ơ (r, s) ∈ G mà nó là ơ duy nhất trên</b>

hàng r hoặc trên cột s. Chẳng hạn, (r, s) là ô duy nhất trên hàng r, tức là trong hệ {A_{i j}|(i, j) ∈ G} có duy nhất một vec tơ A_{i j} với i = r.

<i><b>Hệ quả 2.1. Phương án x = (x</b></i>_{i j}<i>) là phương án cực biên khi và chỉ khi tập các ô chọn G(x) =</i>

{(i, j)|x_{i j}<i>} > 0 khơng chứa chu trình.</i>

<b>Chứng minh:</b>

Bài tốn vận tải là một quy hoạch tuyến tính nên phương án x = x_{i j} là một phương án cực biên khi và chỉ khi các véc tơ {A_{i j}|x_{i j}} > 0 độc lập tuyến tính. Do đó tập các ơ sử dụng G(x) khơng chứa chu trình.

<i>Từ các kết quả trên, người ta còn hay gọi phương án cực biên của bài toán vận tải là phương</i>

<i>án khơng chứa chu trình</i>.

<i><b>Hệ quả 2.2. Cho bảng vận tải T = {(i, j)|i = 1, ..., m, j = 1, ..., n} với m ≥ 2, n ≥ 2. Mọi tập</b></i>

G<i>⊂ T có |G| ≥ m + n đều chứa chu trình.</i>

<b>Chứng minh:</b>

Vì rankA = m + n − 1 và |G| ≥ m + n nên hệ các véc tơ {A_{i j}|(i, j) ∈ G} phụ thuộc tuyến tính. Do đó tập G phải chứa chu trình.

<i><b>Hệ quả 2.3. Cho tập P ⊂ T là tập gồm (m + n − 1) ô . Giả sử P không chứa chu trình và</b></i>

(i₀, j₀) /<i>∈ P. Khi đó P ∪ (i</i>₀, j₀<i>) sẽ chứa một chu trình duy nhất.</i>

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

<b>Chứng minh:</b>

Vì tập P ∪ (i₀, j₀) có m + n ơ nên nó phải chứa chu trình. Vì tập P khơng chứa chu trình nên chu trình này phải đi qua (i₀, j₀) và đó là chu trình duy nhất.

Thật vậy, giả sử phản chứng P ∪ (i₀, j₀) chứa hai chu trình khác nhau là K và K^′sau: 1. Bài tốn này có nghiệm tối ưu hay không?

2. Xét phương án sau và kiểm tra xem đây có phải là một phương án cực biên của bài tốn trên khơng.Vì sao?

b_j= 370, tức là điều kiện cân bằng thu phát được thỏa mãn. Nên bài tốn có nghiệm tối ưu.

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

2. Vì x ≥ 0 và ta kiểm tra lượng:

<i>Ta thấy: G(x) khơng chứa chu trình (do hàng thứ 3 của bảng vận tải chỉ chứa một ô của G)</i>

Nên phương án x là một phương án cực biên.

3. Chi phí phải trả nếu thực hiện theo phương án này là:

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

3Phương pháp thế vị giải bài toán vận tải

<i>Trong mục này, ta sẽ xét trường hợp các phương án cực biên của bài tốn (PT) đều khơng</i>

suy biến (trường hợp cịn lại sẽ được trình bày trong mục thuật toán) Cho phương án x⁰. Ký hiệu: G(x⁰) =ⁿ(i, j) ∈ T | x⁰_{i j} > 0^o

<b>Định lý 3.1 (Điều kiện cần và đủ để x</b>⁰<i><b>là phương án tối ưu). Phương án x</b></i>⁰= (x⁰_{i j}<i>) của bài toán</i>

<i>vận tải (PT) là phương án tối ưu khi và chỉ khi tồn tại các số u</i>_i<i>, i =1, m và v</i>_j<i>, j =1, n thỏa mãn:</i>

u_i+ v_j≤ c_{i j} ∀(i, j) ∈ T (3.1) u_i+ v_j= c_{i j} ∀(i, j) ∈ G(x⁰) (3.2)

<b>Chứng minh:</b>

<b>(⇒): Giả sử phương án x</b>⁰= (x⁰_{i j}<i>) là phương án tối ưu của bài toán vận tải (PT)</i>

<i>Theo định lý đối ngẫu mạnh, bài toán đối ngẫu (DT) có phương án tối ưu y</i>⁰= (u₁, ..., u_m, v₁, ..., v_n)^T. Do y⁰phải là phương án chấp nhận được của bài tốn đối ngẫu nên nó thỏa mãn mọi ràng buộc của bài toán, tức:

u_i+ v_j≤ c_{i j} i= 1, m và j = 1, n ⇒ Điều kiện (1) thỏa mãn.

Hơn nữa, vì x⁰<i>là phương án tối ưu của bài toán gốc (PT) và y</i>⁰là phương án tối ưu của bài

<i>toán đối ngẫu (DT) nên theo định lý về độ lệch bù ta có:</i>

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

c− A<small>T</small>y⁰ E

= 0 ⇒ nếu x⁰_{i j} > 0 thì u_i+ v_j= c_{i j}, ⇒ Điều kiện (2) thỏa mãn.

Như vậy chiều thuận được chứng minh.

<b>(⇐): Cho phương án x</b>⁰= (x⁰_{i j}). Giả sử tồn tại các số u_i, i = 1, m và v_j, j = 1, n thỏa mãn (1.1.1) và (1.1.2). Ta cần chứng minh x⁰là phương án tối ưu.

Vậy x⁰là phương án tối ưu của bài toán vận tải đang xét ⇒ chiều nghịch đã được chứng minh.

<b>Chú ý: Giả sử x</b>⁰là phương án cực biên khơng suy biến. Ta có các véc tơⁿA_{i j} | (i, j) ∈ G(x⁰)^o độc lập tuyến tính và |G(x⁰)| = m + n - 1. Do đó hệ (2) tương ứng:

u_i+ v_j= c_{i j}, (i, j) ∈ G(x⁰)

có m + n - 1 phương trình độc lập tuyến tính với nhau và m + n biến u_i, i = 1,...,m và v_j, j = 1,...,n. Do đó để giải hệ này, có thể cho một biến giá trị tùy ý (thông thường cho u₁= 0) và các ẩn còn lại được xác định duy nhất bằng phương pháp thế. Như vậy, mỗi phương án cực biên không suy biến x⁰= (x⁰_{i j}) tương ứng với một bộ số u_i, i = 1,...,m và v_j, j = 1,...,n (sai khác một hằng số ) thoả mãn (1.1.2). Ta gọi các số u_i, v_j này là các thế vị. Các đại lượng ∆_{i j} := u_i+ v_j− c_{i j} là được

<i>gọi là các ước lượng. Khi đó, điều kiện (1) được viết lại là:</i>

∆_{i j} ≤ 0 với mọi (i, j) ∈ T

Định lý sau đây cho ta biết dấu hiệu nhận biết phương án cực biên không suy biến x⁰chưa phải tối ưu và từ đó chuyển sang một phương án cực biên x¹mà tại đó giá trị hàm mục tiêu tốt hơn x⁰.

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

<i><b>Định lý 3.2. Giả sử x</b></i>⁰<i>là một phương án cực biên không suy biến của bài toán vận tải và u</i>_i, v_j<i>, i= 1,...,m và j = 1,...,n là bộ các thế vị tương ứng với nó. Nếu:</i>

∃(i, j) /∈ G(x⁰<i>) sao cho ∆</i><small>i</small>_k<small>j</small>_k> 0 (3.4)

<i>thì x</i>⁰<i>khơng phải là phương án tối ưu và từ x</i>⁰<i>ta chuyển đến được một phương án cực biên x</i>¹<i>tốthơn x</i>⁰<i>, tức:</i>

f(x¹) < f (x⁰)

<b>Chứng minh:</b>

Nhắc lại một số định lý và hệ quả trước:

<b>Định lý: Cho tập các ơ G ⊂ T . Khi đó, hệ véc tơ</b>A_i| (i, j) ∈ G độc lập tuyến tính khi và chỉ khi G khơng chứa chu trình.

<b>Hệ quả 1: Phương án x = x</b>_{1 j}
là phương án cực biên khi và chỉ khi tập các ô chọn G(x) =(i, j) | x_i> 0 khơng chứa chu trình.

<b>Hệ quả 4.2. Cho bảng vận tải T = {(i, j) | i = 1, · · · , m, j = 1, · · · , n} với m ≥ 2, n ≥ 2. Mọi</b>

tập G ⊂ T có |G| ≥ m + n đều chứa chu trình.

<b>Hệ quả 4.3. Cho tâp P ⊂ T là tập gồm (m + n − 1) ô. Giả sử P không chứa chu trình và</b>

(i₀, j₀) /∈ P. Khi đó P ∪ (i₀, j₀) sẽ chứa một chu trình duy nhất.

Giả sử có điều kiện (4). Ta sẽ chứng minh rằng, từ x⁰có thể chuyển sang được phương án cực biên x¹thỏa mãn f (x¹) < f (x⁰).

Theo hệ quả 1, do x⁰ là phương án cực biên không suy biến nên |G(x⁰)| = m + n − 1 và G(x⁰) không chứa chu trình.

Theo hệ quả 3, tập |G(x⁰)| ∪(i_k, j_k) chứa một chu trình K duy nhất đi qua (i_k, j_k). Đánh dấu các ô trong K bởi các dấu + và -, xuất phát từ ô (i_k, j_k) với dấu +, sao cho khơng có hai ơ nào cạnh nhau trong K lại được đánh dấu bởi cùng một dấu. Ký hiệu:

K⁺:=các ô trong K được đánh dấu + K⁻:=các ô trong K được đánh dấu - Xây dựng phương án x¹= (x¹_{i j}) theo công thức:

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

Vì x⁰ là phương án cực biên khơng suy biến nên θ > 0. Theo cách xây dựng chu trình K và

Vì K là chu trình duy nhất chứa trong G(x⁰) ∪(i_k, j_k), mà theo cách chọn thì (i_r, j_r) ∈ K nên ô chọn mới là (i_k, j_k) không thể tạo thành chu trình với các ơ thuộc G(x⁰)\(i_r, j_r), tức là G(x¹) khơng chứa chu trình. Điều đó chứng tỏ x¹là phương án cực biên. Do u_i+ v_i= c_{i j} với mọi (i, j) ∈ G(x⁰) và x⁰_{i j} = 0 với mọi (i, j) /∈ G(x<small>0</small>) nên giá trị hàm mục tiêu tại x⁰là: Do G(x⁰)\(i_r, j_r) = G(x<small>1</small>)\(i_k, j_k) nên :

u_i+ v_j= c_{i j} với (i, j) ∈ G(x¹)\(i_k, j_k) (3.9) Để cho đơn giản cách viết, ta ký hiệu ˆG := G(x¹)\(i_k, j_k). Ta có:

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

Vì θ > 0 và ∆<small>i</small>_k<small>j</small>_k> 0 nên:

f(x¹) = f (x⁰) − θ ∆<small>i</small>_k<small>j</small>_k < f (x⁰) Định lý đã được chứng minh.

<b>Chú ý: Cho phương án cực biên không suy biến x</b>⁰ và bộ thế vị u_i, v_jtương ứng x⁰. Theo chứng minh vừa rồi, nếu x⁰chưa phải phương án tối ưu thì ta chuyển sang được phương án cực biên x¹và giá trị hàm mục tiêu tại x¹giảm được một lượng là θ ∆_i_k_j_k, tức phụ thuộc cả vào θ và ∆_i_k_j_k, trong đó θ đươc tính theo (6). Với mong muốn giá trị hàm mục tiêu giảm được nhiều nhất có thể và vừa đơn giản việc tính tốn, trong trường hợp có nhiều ô (i, j) /∈ G(x<small>0</small>) cùng có ∆<small>i j</small> > 0 thuật toán thế vị giải bài toán vận tải chọn ô (i_s, j_s) sao cho:

∆_i_k_j_k= max ⁿ∆_{i j}> 0 | (i, j) /∈ G(x⁰)^o

và gọi ô (i_s, j^s<i>) là ô điều chỉnh. Sau đó xây dựng phương án cực biên x</i>¹theo (5) với ô (i_k, j_k) được thay bởi (i_s, j_s<i>). Chu trình K được gọi là chu trình điều chỉnh.</i>

<i><b>Định lý 3.3. Nếu bài tốn vận tải khơng suy biến thì thuật tốn thế vị là hữu hạn. Tức là sau hữu</b></i>

<i>hạn phép tính ta sẽ nhận được nghiệm tối ưu.</i>

<b>Chứng minh: Bài toán vận tải thỏa mãn điều kiện cân bằng thu phát nên ln có nghiệm tối</b>

ưu. Do bài tốn khơng suy biến nên tại mỗi bước lặp ta đều có θ > 0 và giá trị hàm mục tiêu giảm thực sự. Vì vậy, sau một số hữu hạn bước lặp, ta sẽ nhận được phương án tối ưu

<i><b>Mệnh đề 3.1. Nếu các lượng phát a</b></i>_i<i>,, i = 1,...,m và các lượng thu b</i><small>j, j = 1,...,n đều là các số</small>

<i>ngun thì bài tốn vận tải sẽ có nghiệm tối ưu với các thành phần đều ngun.</i>

<b>Chứng minh: Trong các bước tính tốn của thuật tốn thế vị ta khơng phải dùng phép chia.</b>

Do đó, nếu dữ liệu ban đầu a_i, b_j đều là các số nguyên thì theo các cách tìm phương án cực biên, phương án xuất phát cũng sẽ có các thành phần nguyên. Vì thế, các bước lặp cho đến phương án tối ưu ta ln có các thành phần của phương án tối ưu đều là số nguyên.

<b>3.2 Thuật toán thế vị</b>

Thuật toán thế vị giải bài toán vận tải xuất phát từ một phương án cực biên. Thuật toán này dùng để tối ưu phương án của bài toán vận tải không suy biến. Tức là tối ưu các phương án cực biên có đúng (m + n − 1) thành phần dương, với giả thiết là ta đã biết 1 phương án cực biên.

<b>Thuật toán</b>

<b>Khởi tạo: Giả thiết đã biết phương án cực biên không suy biến x</b>⁰= (x⁰_{i j}). Tập ô chọn tương ứng với x⁰là G(x⁰) = {(i, j)|x⁰_{i j} > 0} gồm (m + n − 1) phần tử khơng chứa chu trình.

Bước 1: Tìm các thế vị u_i, i = 1,...,m và v_j, j = 1,...,n tương ứng với phương án cực biên x⁰. Các thế vị thỏa mãn hệ (n + m − 1) phương trình:

u_i+ v_j= c_{i j} ∀(i, j) ∈ G(x<small>0</small>)

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

Hệ phương trình trên có (m + n − 1) phương trình, xác định m + n ẩn. Như vậy, sẽ có một u_ihoặc một v_iđược xác định tùy ý và (m + n − 1) ẩn còn lại sẽ xác định duy nhất.

<i>Quy tắc:</i>

<b>-</b> Đầu tiên, cho u_i₀ = 0 (i₀thường là dòng đầu tiên hoặc là dịng chứa 1 ơ sử dụng).

<b>-</b> Sau đó xác định v_j= c_{i j}− u_i₀ cho những cột cắt dòng i₀ở một ơ sử dụng.

<b>-</b> Tiếp đó, xác định u_i= c_{i j}− v_j cho dòng i cắt cột ở một ô sử dụng. Bằng quy tắc đó ta xác định được u_ivà v_jcho mỗi dịng và cột Bước 2: Tính các ước lượng và kiểm tra điều kiện tối ưu

Với mọi ô (i, j) /∈ G ta xác định các ước lượng ∆<small>i j</small> như sau: ∆_{i j} = (u_i+ v_j) − c_{i j}

<b>-</b> Nếu ∆_{i j} ≤ 0 ∀(i, j) thì phương án đã cho tối ưu.

<b>-</b> Nếu ∆_{i j} ≥ 0 với ít nhất một ơ (i, j) thì phương án đã cho chưa tối ưu. Ta có thể điều chỉnh để hạ nữa hàm mục tiêu

Bước 3: Điều chỉnh phương án

Giả sử ô vi phạm tiêu chuẩn tối ưu là (i_s, j_s) tức là ∆<small>i j</small> > 0 (nếu có nhiều ơ vi phạm ta chọn ơ tương ứng max ∆_{i j} với hi vọng hàm mục tiêu giảm nhanh nhất).

Ô (i_s, j_s) /∈ G. Bây giờ ta thêm ơ (i_s, j_s) vào tập G, khi đó có tất cả (m + n) ơ sử dụng. Ơ (i_s, j_s) sẽ lập với các ô của G một chu trình K duy nhất. Chia K thành hai phần : K⁺ Quay lại bước 2.

Ta lại xác định hệ thống thế vị mới ứng với phương án X’ và G’. Tiếp tục quá trình cho đến khi nào xảy ra tình huống θ_{i j}≤ 0, ∀(i, j) ⇐⇒ lúc đó ta nhận được phương án tối ưu.

<b>Chú ý: Nếu số ơ sử dụng N < m+n-1 thì thêm (m+n-1) - N ô mới với x</b>_{i j} = 0 sao cho khơng tạo thành chu trình.

<i><b>Chú ý: (Dấu hiệu nhận biết phương án cực biến và cách khắc phục) Tương tự như khi giải</b></i>

bài tốn quy hoạch tuyến tính, trong trường hợp bài tốn vận tải suy biến ta có hai dấu hiệu nhận biết sau:

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

i) θ = 0. Khi đó, ta vẫn thực hiện thuật tốn bình thường. Ơ điều chỉnh (i<small>s</small>, j_s) sẽ trở thành ô chọn của phương án cực biên mới x’ với x^′_i

<small>sjs</small> = θ . Cịn ơ (i_r, j_r ứng với x_i_r_j_r = θ ở trên chu trình điều chỉnh sẽ trở thành ô loại đối với phương án x’. Tuy nhiên, kết quả điều chỉnh không làm thay đổi phương án cực biên mà chỉ thay đổi tập vecto cơ sở ứng với phương án đó

ii) θ đạt tại nhiều ơ khác nhau. Khi đó, ta sẽ loại một trong những ô này theo quy tắc ngẫu nhiên

<i><b>Chú ý: (Dấu hiệu bài tốn có phương án tối ưu duy nhất và không duy nhất)</b></i>

i) Nếu phương án cực biên không suy biến x⁰thỏa mãn tiêu chuẩn: ∆_{i j} = u_i+ v_j− c_{i j} < 0 ∀(i, j) /∈ G(x<small>0</small>) thì đó là phương án tối ưu duy nhất của bài toán vận tải

ii) Ngược lại, nếu bài toán cực biên không suy biến x⁰ là phương án tối ưu và tồn tại ơ (i_p, j_p) /∈ G(x<small>0</small>) có ∆<small>ipjp</small> = 0 thì x⁰khơng phải phương án tối ưu duy nhất của bài toán vận tải. Tương tự thuật toán đơn hình giải quy hoạch tuyến tính, muốn tìm một phương án cực biên tối ưu khác x⁰, ta chọn (i_p, j_p) làm ô điều chỉnh và thực hiện tiếp một số bước lặp theo

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

<b>Nhận xét: Vì có ∆</b>₂₄= 2 > 0 do đó phương án cực biên này chưa phải là phương án tối ưu. Ta tiến hành điều chỉnh phương án.

<b>Nhận xét: Ta thấy rằng ô (3,1) tuy là ô loại nhưng ước lượng vẫn bằng 0. Do đó bài tốn</b>

này sẽ có vơ số phương án tối ưu.Tuy nhiên ở đây, chúng ta sẽ chỉ tìm ra 1 nghiệm tối ưu của bài tốn. Do chỉ có ∆₂₄> 0 nên chọn ln ơ (2, 4) làm ô điều chỉnh. Ghép ô (2, 4) vào tập G(x⁰) ta

Ta có θ = min{x_{i j} ∈ K⁻} = 1 = x₂₃, loại ô (2,3) ra khỏi phương án cực biên. Và đưa ô (2, 4) vào phương án. Ta có bảng vận tải mới

</div><span class="text_page_counter">Trang 24</span><div class="page_container" data-page="24">

<b>Nhận xét: Vẫn có ∆</b>₃₁ = 2 > 0 do đó phương án cực biên này chưa phải là phương án tối ưu. Ta tiến hành điều chỉnh phương án. Ghép ơ (3, 1) vào tập G(x⁰) ta có chu trình K = {(2, 1), (3, 1), (2, 4), (3, 4)} với K⁺ = {(3, 1), (2, 4)} và K⁻= {(2, 1), (3, 4)}

</div><span class="text_page_counter">Trang 25</span><div class="page_container" data-page="25">

Ta có θ = min{x<small>i j</small> ∈ K⁻} = 15 = x₃₄, loại ô (3, 4) ra khỏi phương án cực biên. Và đưa ơ (3, 1) vào tập G. Ta có phương án mới:

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

4Phương án xuất phát cho thuật tốn thế vị

<i><b>4.1 Phương pháp góc tây bắc (Northwest - conner rule)</b></i>

<b>4.1.1 Ý tưởng phương pháp</b>

Phương pháp góc tây bắc là phương pháp đơn giản nhất được sử dụng để tìm phương án cực biên xuất phát cho bài toán vận tải thỏa mãn điều kiện cân bằng thu phát. Trong phương pháp này, ta sẽ bắt đầu từ ơ trên cùng bên trái( góc tây bắc).

<b>4.1.2 Thuật toán</b>

<b>Khởi tạo: Lập bảng vận tải T với các số liệu a</b>_i, b_j, c_{i j}, i = 1, m, j = 1, n.

Bước 1: Bắt đầu từ ô trên cùng bên trái (vị trí góc tây bắc) của bảng T, ta điền lượng hàng lớn nhất có thể x₁₁= min(a₁, b₁) từ ô phát 1 đến ô thu 1.

Bước 2: Ở cả ô thu và ô phát, trừ đi lượng hàng đã chuyển. Từ đây có 3 trường hợp có thể xảy ra:

• a₁= 0 (Lượng hàng cịn cần thu ở ơ thu 1 là b₁− a₁đơn vị hàng). Xóa hàng thứ nhất đi, ta thu được bảng T’ gồm (m - 1) hàng và n cột.

• b₁= 0 (Lượng hàng cịn cần phát ở ơ phát 1 là a₁− b₁đơn vị hàng). Xóa cột thứ nhất đi, ta thu được bảng T’ gồm m hàng và (n - 1) cột.

• a₁= b₁= 0 (Lượng hàng cịn cần thu và phát ở ô thứ nhất là 0). Ta quy ước xóa cột thứ nhất đi, ta thu được bảng T’ gồm m hàng và (n - 1) cột.

Bước 3: Lặp lại bước 1 và 2 cho đến khi lượng thu và phát còn lại là 0.

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

Chọn ô (1, 1) của bảng và phân phối lượng hàng tối đa có thể chuyển (ở đây là 50 đơn vị

Giảm cả ô thu b₁và ô phát a₁đi 50 đơn vị hàng đó, ta thấy hàng a₁= 40, cột b₁= 0 nên ta xóa cột đó đi. Lúc này ơ (1, 2) sẽ là ô (1, 1) của bảng mới

</div>