Bài giảng Quy hoạch tuyến tính - Nguyễn Cảnh Hoàng

58 trang hapham 140

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Quy hoạch tuyến tính - Nguyễn Cảnh Hoàng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_quy_hoach_tuyen_tinh_nguyen_canh_hoang.pdf

Nội dung text: Bài giảng Quy hoạch tuyến tính - Nguyễn Cảnh Hoàng

Nguyễn Cảnh Hoàng Tpying by Đặng Minh Dũng – K56CA, UET
Tài liệu tham khảo: Nguyễn Đức Nghĩa: Tối ưu hóa (Quy hoạch tuyến tính và rời rạc), NXB Giáo dục 1998. Bùi Minh Trí & Bùi Thế Tâm: Giáo trình tối ưu hóa, NXB Giao thông Vận tải 1996. Bùi Thế Tâm & Trần Vũ Thiệu: Các phương pháp tối ưu hoá, NXB Giao thông Vận tải 1998 Lời nói đầu: Tối ưu hóa là một bộ phận kiến thức cần thiết của nhà tổ chức, thiết kế kỹ thuật, điều hành công việc, và ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của cuộc sống. Nó còn được gọi là vận trù học hay quy hoạch, được phát triển mạnh mẽ từ những năm 30-40 nhờ công lao của Kantorovic (Nga 1939) cũng như các nhà toán học Mỹ, những người tìm ra phương pháp đơn hình (Simplex method 1942) Giáo trình này nhằm mục đích nêu các khai niệm cơ sở và một số kết quả cơ bản của tối ưu hóa, nhằm trang bị những hành trang cần thiết cho các sinh viên của các trường kỹ thuật để tiếp xúc, ứng dụng và giải quyết các vấn đề liên quan trong tương lai.
Chương I. Mở đầu BÀI 1. ĐỐI TƯỢNG NGHIÊN CỨU Khi tiến hành thiết kế, tổ chức, điều hành một (hoặc một dãy) quá trình nào đó, người ta thường phải tự đặt câu hỏi: làm thế nào để có thể đạt được kết quả nhanh nhất, tiết kiệm thời gian, tiền của nhất, đạt chất lượng cao nhất ! Nói một cách khác, ta muốn đạt được cực trị của một mục tiêu nào đó được đề ra từ trước. Cơ sở lý thuyết và các phương pháp thực hành để giải quyết vấn đề đó được gọi là Tối ưu hóa hay Quy hoạch toán học. 1.1 Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát được phát biểu như sau: Hãy cực tiểu hóa (cực đại hóa) hàm số: ( ) → 푖푛( ) (1.1) Với các điều kiện: 푖( )(≤, =, ≥) 푖 푖 = 1,2, , (1.2) ∈ ⊂ 푅푛 (1.3) Trong đó: ( ) được gọi là hàm mục tiêu, cực tiểu hóa (cực đại hóa) là chọn giá trị của đối số x sao cho ( ) đạt giá trị bé nhất (lớn nhất) có thể. 푖( ) được gọi là các hàm rằng buộc, mỗi bất đẳng thức trong (1.2)được gọi là một rằng buộc, thể hiện điều kiện đòi hỏi của bài toán đối với biến x. Tập hợp = { ∈ : 푖( )(≤, =, ≥) 푖 푖 = 1,2, , } được gọi là miền rằng buộc (hay miền chấp nhận được, tập các phương án chấp nhận). Mỗi một điểm = ( 1, 2, , 푛) ∈ được gọi là một phương án chấp nhận được (hay gọi tắt là phương án, lời giải) của bài toán đã cho. Phương án ∗ ∈ sao cho hàm mục tiêu đạt được giá trị cực tiểu (cực đại), tức là: ( ∗) ≤ ( ) ∀ ∈ cho bài toán Min ( ∗) ≥ ( ) ∀ ∈ cho bài toán Max Được gọi là phương án tối ưu (lời giải tối ưu) và ( ∗) được gọi là giá trị tối ưu của bài toán. Ví dụ : Một người muốn xây một ngôi nhà với mức giá thấp nhất có thể. Tuy nhiên ông ta có một số điều kiện của ngôi nhà đó : . Diện tích mặt bằng, diện tích xây dựng . Số phòng, số tầng, số phòng vệ sinh
. Tiêu chuẩn kỹ thuật : Chất lượng kỹ thuật, tiêu chuẩn nguyên vật liệu, cửa sổ, nội thất, phòng vệ sinh, Dễ thấy ông ta có một bài toán tối ưu hóa giá thành xây dựng ngôi nhà đó (mà nó là một hàm số phụ thuộc vào giá cả nguyên vật liệu, công thợ, diện tích xây dượng, ) thỏa mãn các đòi hỏi (rằng buộc) của ông ta. 1.2 Phân loại các bài toán Rõ ràng ý tưởng đơn giản nhất để tìm các phương án tối ưu là duyệt toàn bộ các phương án đó : Tính tất cả mọi giá trị ( ) của mọi ∈ và so sánh để lấy ∗có ( ∗)có giá trị bé nhất (lớn nhất). Chẳng hạn để tìm sinh viên có điểm trung bình cao nhất trong Đại học Công nghệ, ta tính điểm trung bình của mọi sinh viên trong trường và sau đó so sánh lần lượt tất cả để chọn ra sinh viên có điểm trung bình cao nhất. Tuy nhiên cách làm này nhiều khi không thực hiện được, khi D quá lớn hoặc vô hạn, hoặc không xác định được một cách trực quan, chưa kể nhiều khi việc tính ( ) là một vấn đề kỹ thuật phức tạp (chẳng hạn đo sức nổ của 1 quả bong nguyên tử, chẳng lẽ ta lại thử nổ ak ?!). Do vậy thường ta chia bài toán tối ưu thành các lớp bài toán riêng biệt và nghiên cứu, tìm kiếm lời giải cho từng bài toán đó. Thông thường việc phân loại đó dựa vào hàm mục tiêu, rằng buộc, điều kiện cần và đủ của cực trị, tính chất của các đối tượng nghiên cứu Ta thường có các phân loại bài toán tối ưu như sau :  Quy hoạch tuyến tính (QHTT) : là các bài toán tối ưu mà trong đó hàm mục tiêu ( ) và các hàm rằng buộc 푖( ) là các hàm tuyến tính, còn tập X là một đa diện lồi.  Quy hoạch phi tuyến : là bài toán quy hoạch mà ( ) hoặc 1 trong các hàm 푖( ) là hàm phi tuyến.  Quy hoạch động : Đối tượng xét đến có nhiều giai đoạn mà hàm mục tiêu cũng như rằng buộc có thay đổi trong các giai đoạn đó (ví dụ xây nhà, giá cả nguyên vật liệu, tiền công thay đổi theo thời gian).  Quy hoạch rời rạc : Nếu D là một miền rời rạc.  Quy hoạch nguyên : Nếu D chỉ nhận các giá trị nguyên.  Quy hoạch Boole : Nếu D chỉ nhận các giá trị True/False.  Quy hoạch đa mục tiêu : Có nhiều hàm mục tiêu.
BÀI 2. MÔ HÌNH HÓA TOÁN HỌC Với một bài toán thực tế nào đó, việc tìm cách phát biểu nó theo ngôn ngữ toán học, đưa nó vào một lớp bài toán quyen thuộc được gọi là mô hình hóa bài toán đó. Nói một cách khác là xếp nó vào một mô hình tổng quát nào đó, và việc giải nó chẳng qua là giải một bài toán cụ thể của một lớp bài toán tổng quát mà thôi. Việc giải bài toán thường được tiến hành theo các bước sau: Bước 1: Xây dựng mô hình định tính, xác địn bằng lời một cách rõ ràng bài toán và các biểu đồ, đồ thị của bài toán thực tế. Bước 2: Xây dựng mô hình toán học: Phát biểu lại bài toán dưới dạng ngôn ngữ toán học, nói một cách khác là biểu diễn các mô hình định tính bằng các công thức toán học: ( ); 푖( ); ≤ ≥; Bước 3: Áp dụng các công cụ toán học để khảo sát và giải bài toán đã được phát biểu ở bước 2 để tìm lời giải phù hợp. Bước 4: Phân tích và kiểm định kết quả thu được ở bước 3. Đây là bước kiểm tra và đánh giá kết quả có phù hợp với bài toán đặt ra hay không, hiệu chỉnh, sửa đổi, thêm bớt các rằng buộc cho phù hợp với thực tế Ta xét một số mô hình cụ thể sau đây: 2.1 Bài toán lập kế hoạch Một nhà máy có khả năng sản xuất n loại sản phẩm từ m nguyên liệu khác nhau, với các định mức nguyên vật liệu cho từng loại sản phẩm. Hãy xây dựng phương án sản xuất để từ số nguyên liệu có trong kho, nhà máy thu được lợi nhuận cao nhất. Ta có sơ đồ sử dụng nguyên vật liệu như sau: 푖푗 – lượng nguyên liệu thứ i cần thiết để sản xuất P 1 một đơn vị sản phẩm thứ j. 푖 – số lượng nguyên liệu thứ i có trong kho. P2 bi 푗 – lợi nhuận của một sản phẩm thứ j. 푗 – số sản phẩm thứ j mà nhà máy sẽ sản xuất. Pm Khi đó việc xây dựng kế hoạch là bài toán tối ưu, phát biểu dưới dạng ngôn ngữ toán học như sau:
푛 ∑ → 푗 푗 푗=1 푛 ∑ 푖푗 푗 ≤ 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛) 2.2 Bài toán vận tải Có n kho hàng cùng chứ một loại hàng hóa cần được chuyển tới m cửa hàng tiêu thụ với các yêu cầu về số lượng và cước phí khác nhau. Hãy lập kế hoạch vận chuyển sao cho cước phí là bé nhất. Ta gọi: 푖 – số lượng hàng hóa có ở kho thứ i, 푖 = 1, 푛 푗 – lượng hàng hóa cấn chuyển tới cửa hàng thứ j, 푗 = 1, 푖푗 – lương hàng hóa sẽ chuyển thừ kho Ai tới kho Bj, 푖 = 1, 푛; 푗 = 1, 푖푗 – cước phí chuyên chở một đơn vị hàng từ kho Ai tới cửa àng tiêu thụ Bj, 푖 = 1, 푛; 푗 = 1, Mô hình toán học của bài toán vận tải sẽ là: X11 A1 a1 b1 B1 X12 A2 a2 b2 B2 X1m An an bm Bm Và ta có bài toán tối ưu:
푛 ∑ ∑ → 푖푛 푖푗 푖푗 푖=1 푗=1 ∑ 푖푗 = 푖 (푖 = 1, 푛) 푗=1 푛 ∑ 푖푗 = 푗 (푗 = 1, ) 푖=1 ≥ 0 (푖 = 1, 푛; 푗 = 1, ) 푖푗 푛 ∑ 푖 = ∑ 푗 { 푖=1 푗=1 Tổng quát, 푖푗 là các số thực không âm, chẳng hạn khi hàng hóa đó là xăng dầu, gạo, đường, Tuy nhiên ta thường hay “Nguyên hóa” chúng đi để trở thành các số nguyên, ví dụ ta dùng đơn vị đo là “thùng”, “tấn”, hoặc “bao”, “bình”, để các 푖푗 đó trở thành các số nguyên (không lẽ ta lại nói là chuyên chở 3.45 bao xi măng hay 3.2 bình ga à?). Do vậy mà bài toán quy hoạch của ta sẽ trở thành một bài toán quy hoạch nguyên, đơn giản hơn trong tính toán mặc dù lời giải lý thuyết không đổi ! 2.3 Bài toán cái túi Một kẻ trộm lẻn vào kho, mang theo 1 cái túi để đựng hàng. Trong kho có n loại đồ vật với khối lượng và giá trị khác nhau. Biết rằng túi chỉ có thể chứa được 1 khối lượng hàng hóa nhất định. Hãy chỉ cho tên trộm nên lấy những gì để có lợi nhất. Gọi : – khối lượng tối đa của túi. 푗 – khối lượng của 1 đồ vật loại j. 푗 – giá trị của 1 đồ vật loại j. 푗 – số đồ vật loại j sẽ được bỏ vào túi. Khi đó ta có bài toán quy hoạch nguyên như sau : 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푗 푗 ≤ 푗=1 { 푗 ≥ 0, 푗 ∈ (푗 = 1, 푛) (Giả thiết là trong kho có vô số hàng hóa các loại)
Trên đây là một số mô hình cơ bản của quy hoạch với các cách diễn giải nội dung thực tế của chúng. Các bài toán khác có thể được diễn giải, phải biểu dưới dạng tương tự các mô hình trên. BAI 3. MỘT SỐ KHAI NIỆM GIẢI TICH LỒI 3.1 Không gian Euclide Rn Một vector n chiều được xác định bởi bộ số : 푛 = ( 1, 2, , 푛) ∈ ℝ Trong đó 1, 2, 푛 ∈ ℝ được gọi là các thành phần của vector x. Vector x đó cũng đồng 푛 nhất với điểm A có tọa độ ( 1, 2, , 푛) ∈ ℝ Khi đó : . Hai vector x, y bằng nhau khi các thành phần của chúng bằng nhau đôi một : = ⟺ 1 = 1, 2 = 2, , 푛 = 푛 . Tổng vetor : + = ( 1 + 1, 2 + 2, , 푛 + 푛) . Tích của 1 số thực với 1 vector : 휆 = (휆 1, 휆 2, , 휆 푛) Tập các vector n chiều với 2 phép toán trên được gọi là không gian tuyến tính n chiều trên tập ℝ, kí hiệu là ℝ푛 Khi đó ta có một số khái niệm và tính chất sau : 푛 . Các vector 푖 ∈ ℝ , 푖 = 1, được gọi là độc lập tuyến tính nếu : ∑ 푖 푖 = 0 ⟺ 푖 = 0 ∀푖 = 1, 푖=1 (ngược lại, các vector đó được gọi là phụ thuộc tuyến tính) . Nếu = ∑푖=1 푖 푖 với ít nhất một 푖 ≠ 0 thì x được gọi là tổ hợp tuyến tính của các vector 푖. Nếu ∑푖=1 푖 = 1 và 푖 ≥ 0 ∀푖 = 1, 푛 thì ta gọi đó là 1 tổ hợp lồi của các vector 푖 . Trong ℝ푛, mỗi bộ n vector độc lập tuyến tính được gọi là cơ sở của ℝ푛, (mọi cơ sở đều đúng n vector, n được gọi là số chiều của không gian ℝ푛, trong ℝ푛 có vô số sơ sở khác nhau). Khi đó, mọi vector thuộc ℝ푛 đều có thể biểu diễn dưới dạng tổi hợp tuyến tính của các vector trong cơ sở đó. . Bao đóng tuyến tính Span( ) = {∑ 푖 푖 ∶ 푖 ∈ ℝ, 푖 ∈ }
. Tích vô hướng của 2 vector x và y, ký hiệu 〈 , 〉 được định nghĩa như sau : 푛 〈 , 〉 ≔ ∑ 푖 푖 푖=1 và có các tính chất sau : o 〈 , 〉 = 〈 , 〉 o 〈 1 + 2, 〉 = 〈 1, 〉 + 〈 2, 〉 o 〈휆 , 〉 = 휆〈 , 〉 o 〈 , 〉 ≥ 0, ấ = ả ℎ푖 푣à ℎỉ ℎ푖 = (0,0, ,0) . Độ dài của vector, ký hiệu | |được xác định bởi : 푛 2 | | ≔ √∑ 푖 = √〈 , 〉 푖=1 . Khoảng cách giữa 2 vector, ký hiệu ( , ) : 푛 2 ( , ) ≔ | − | = √∑( 푖 − 푖) 푖=1 Không gian tuyến tính ℝ푛 với tích vô hướng và khoảng cách d được gọi là không gian Euclide. 3.2 Tập Compact ∗ . Dãy { 푖} được gọi là có giới hạn x* khi 푖 → ∞ nếu lim ( 푖, ) = 0 và ta ký hiệu 푖→∞ ∗ lim 푖 = 푖→∞ . Hình cầu mở : 푆( 0, ) = { ∈ ∶ ( 0, ) < } Hình cầu đóng : 푆( 0, ) = { ∈ ∶ ( 0, ) ≤ } 0 . Mặt cầu : 푆 ( 0, ) = { ∈ ∶ ( 0, ) = . //Some text are missing . Mặt biên, cạnh biên, đỉnh : Mặt của một tập mà mọi điểm của nó là các điểm biên gọi là mặt biên. Giao của các mặt biên gọi là cạnh biên. Giao của nhiều cạnh biên gọi là đỉnh hoặc điểm cực biên. . //Some text are missing Ta có thể dễ dàng giải thích và lấy ví dụ trực quan về các khái niệm trên trong không gian Euclide.
3.3 Tập lồi – Hàm lồi Định nghĩa 3.1: Nếu ∀ , ∈ ta có [ , ] ⊂ trong đó [ , ] ≔ {훼 = 휆 + (1 − 휆) ∶ 휆 ∈ [0,1]} Thì M được gọi là tập lồi. ([ , ] là đoạn thẳng nối x và y) M x y Ý nghĩa : Với ∀ , ∈ đoạn thằng [ , ] nối 2 điểm x, y luôn nằm trọn trong tập lồi M. Định lý 3.1 : Giao của 2 tập lồi là một tập lồi. Chứng minh : ∀ , ∈ ∩ ta có , ∈ ⟹ [ , ] ⊂ . Tương tự [ , ] ⊂ Suy ra [ , ] ⊂ ∩ . Tức là ∩ là một tập lồi. Hệ quả 1 : Giao của n tập lồi là một tập lồi. Hệ quả 2 : Miền chứa nghiệm của hệ : 11 1 + 12 2 + ⋯ + 1푛 푛 ≤ 1 { 1 1 + 2 2 + ⋯ + 푛 푛 ≤ Là một tập lồi Chứng minh : Dễ thấy mỗi bất phương trình trong hệ trên là một nửa mặt phẳng trong không gian và đó là một tập lồi. Từ hệ quả 1 ta suy ra điều cần chứng mình. Định lý 3.2 : Cho tập lồi đa diện đóng X với ít nhất 1 đỉnh. Khi đó mỗi ∈ đều có thể biểu diễn dưới dạng : = ∑ 휆푖 푖 + ∑ 휇푗 푗 푖 푗 Trong đó : 휆푖 ≥ 0, ∑푖 휆푖 = 1 푖 là các đỉnh của đa diện lồi X, 푖 ∈ 푗 (푗 ∈ 퐽) là các phương vô hạn của đa diện lồi (Khi X giới nội không còn các cạnh vô hạn thì chỉ còn = ∑푖 휆푖 푖 , 휆푖 ≥ 0, ∑푖 휆푖 = 1 và khi đó ta gọi = ∑푖 휆푖 푖 là một tổ hợp lồi của các đỉnh – tức là khi đó mọi điểm x đề là tổ hợp lồi
của các đỉnh, còn khi X có các cạnh vô hạn thì x sẽ là tổng của 1 tổ hợp lồi các đỉnh ∑푖 훼푖 푖 cộng với tổ hợp các phương vô hạn) Chứng minh : Ta chứng minh cho các trường hợp sau : a. X là đa giác phẳng hữu hạn : d1 x d0 * y d2 Giả sử X có một đỉnh là 푖 nào đó. Nối 0 với x kéo dài cắt một cạnh của đa giác X tại y. Chắc chắn y nằm trên một cạnh của 2 đỉnh nào đó, ta ký hiệu là 1 & 2. Dễ thấy rằng : ∈ [ 0, ] ⟹ ∃휆 ∈ [0,1]: = 휆 0 + (1 − 휆) (1) ′ ′ ∈ [ 1, 2] ⟹ ∃휆 ∈ [0,1]: = 휆 1 + (1 − 휆 ) 2 (2) Thay (2) vào (1) ta được : ′ ′ = 휆 0 + (1 − 휆) = 휆 0 + (1 − 휆)[휆 1 + (1 − 휆 ) 2] ′ ′ = 휆 0 + (1 − 휆)휆 1 + (1 − 휆)(1 − 휆 ) 2 Dễ kiểm tra được là 휆 + (1 − 휆)휆′ + (1 − 휆)(1 − 휆′) = 1 và các hệ số trên đều thuộc [0,1] nên x là tổ hợp lồi của 3 đỉnh 0, 1, 2. b. X là một đa diện hữu hạn trong không gian : d1 d2 y x d0 d3
Hoàn toàn tương tự nối đỉnh 0 với x kéo dài cắt một mặt của đa diện X tại y. Giả sử mặt đó có các đỉnh 1, 2, , nào đó. Ta cũng sẽ có : ∈ [ 0, ] ⟹ ∃휆 ∈ [0,1]: = 휆 0 + (1 − 휆) (1’) Do y nằm trong đa giác có các đỉnh là 1, 2, , nên theo trường hợp (a), y là tổ hợp lồi của các đỉnh đó. Tức là : ′ ∃훼푖 ∈ [0,1], ∑ 훼푖 = 1 푠 표 ℎ표 = ∑ 훼푖 푖 (2 ) 푖=1 푖=1 Thay (2’) vào (1’) ta được : = 휆 0 + (1 − 휆) = 휆 0 + (1 − 휆) ∑ 훼푖 푖 = 휆 0 + ∑(1 − 휆)훼푖 푖 푖=1 푖=1 Dễ kiểm tra được là 휆 + ∑(1 − 휆)훼푖 = 휆 + (1 − 휆) ∑ 훼푖 = 휆 + (1 − 휆) = 1 푖=1 푖=1 Và hệ số đều thuộc [0,1] nên x là tổ hợp lồi của 0, 1, 2, , c. X là một đa giác phẳng vô hạn : X A * x d1 d 2 B O Nếu X là đa diện lồi có các cạnh vô hạn, ta có thể chứng minh như sau : Chọn điểm A trên 1 cạnh vô hạn có đỉnh d1, sao cho nối với x kéo dài sẽ cắt một cạnh khác của đa diện X tại B. Ta có 2 khả năng : Cạnh thứ 2 đó cũng là cạnh vô hạn, giả sử cạnh vô hạn đó có đỉnh d2 (trường hợp đa diện đó chỉ có mỗi 1 đỉnh d0 thì cả 2 đỉnh d1 và d2 phải trùng với d0).
Để đơn giản ta cũng xem như mọi chuyện xảy ra trong mặt phẳng và ta đồng nhất điểm A với vector a, điểm B với vector b, điểm x với vector x, đỉnh d1 với vector d1, đỉnh d2 với vector d2, gốc tọa độ là O. ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ ( 1 = 1; 2 = 2; ⃗⃗⃗⃗⃗ = ; ⃗⃗⃗⃗⃗ = ; O là gốc trục tọa độ trong không gian vector ℝ푛) Khi đó, do ∈ [ , ] ⟹ ∃휆 ∈ [0,1] sao cho = 휆 + (1 − 휆) (1’’) Mặt khác ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ = ⃗⃗⃗⃗⃗ = 1 + 1 = 1 + 1 ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ = ⃗⃗⃗⃗⃗ = 2 + 2 = 2 + 2 Thay vào (1’’) ta được: ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ = 휆 + (1 − 휆) = 휆( 1 + 1 ) + (1 − 휆)( 2 + 2 ) ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ = [휆 1 + (1 − 휆) 2] + [휆 1 + (1 − 휆) 2 Nghĩa là ta có x là tổng của 1 tổ hợp lồi 2 đỉnh d1 và d2 với 1 tổ hợp lồi của các ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ phương vô hạn 1 푣à 2 . Cạnh thứ 2 đó không phải là cạnh vô hạn, có nghĩa là B nằm giữa 2 đỉnh d2 và d3 nào đó. Khi đó, do ∈ [ , ] ⟹ ∃휆 ∈ [0,1] sao cho = 휆 + (1 − 휆) (1’’’) ′ ′ ′ Mặt khác ∈ [ 2, 3] ⟹ ∃휆 ∈ [0,1] sao cho = 휆 2 + (2 − 휆 ) 3 ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ ⃗⃗⃗⃗⃗⃗⃗ Ngoài ra: = ⃗⃗⃗⃗⃗ = 1 + 1 = 1 + 1 Thay a, b vào (1’’’) ta được: ⃗⃗⃗⃗⃗⃗⃗ ′ ′ = 휆 + (1 − 휆) = 휆( 1 + 1 ) + (1 − 휆)[휆 2 + (1 − 휆 ) 3] ′ ′ ⃗⃗⃗⃗⃗⃗⃗ = 휆 1 + (1 − 휆)휆 2 + (1 − 휆)(1 − 휆 ) 3 + 휆 1 ⃗⃗⃗⃗⃗⃗⃗ Nghĩa là x là tổ hợp lồi của các đỉnh d1, d2, d3 cộng với phương vô hạn 1 d. X là một đa diện lồi vô hạn : Hoàn toàn tương tự như trường hợp (c). Vì điều kiện thời gian có hạn nên chứng minh trên trình bày chưa thật chi tiết và chặt chẽ, cho dù ý tưởng là hoàn toàn chính xác. Ý nghĩa: Trong không gian vector nhiều chiều, mỗi điểm của một đa diện lồi là tổ hợp cửac ác đỉnh đa diện đó cộng với 1 tổ hợp tuyến tính các phương vô hạn (nếu đa diện là vô hạn). Định nghĩa 3.2: 푛 Hàm số f(x) được xác định trên tập lồi ⊂ ℝ được gọi là hàm lồi nếu ∀ 1, 2 ∈ , ∀휆 ∈ [0,1]: [휆 1 + (1 − 휆) 2] ≤ 휆 ( 1) + (1 − 휆) ( 2) Ý nghĩa:
y f(x2) M2 λf(x1) + (1-λ)f(x2) f(x) M f(x ) 2 M1 x O x x 1 x2 Gọi M1M2 là 2 điểm trên đồ thị ứng với x1, x2. Khi đó với = 휆 1 + (1 − 휆) 2 Ta có: ( ) = 휆 ( 1) + (1 − 휆) ( 2) Nghĩa là điểm = ( , ( )) nằm phía dưới đáy dây cung M1M2, tạo cảm giác đồ thị bị “lồi” tại điểm đó. Do vậy mà với hàm lồi ta hay xét tới khái niệm cực tiểu. Nếu dấu bất đẳng thức là ‘< ‘ trong định nghĩa trên thì ta gọi hàm f(x) là hàm lồi chặt. Ngược lại hàm f(x) được gọi là hàm lõm nếu − ( ) là hàm lồi (hay dấu bất đẳng thức là ≥). Với hàm lõm ta hay xét cực đại. Ta nói f(x) xác định trên X đạt cực tiểu tuyệt đối (Min) tại x* nếu: ( ∗) ≤ ( ) ∀ ∈ Còn f(x) đạt cực tiểu địa phương nếu tồn tại lân cân B của x* sao cho: ( ∗) ≤ ( ) ∀ ∈ Định lý 3.3: Bất kỳ cực tiểu địa phương của hàm lồi xác định trên tập lồi cũng là cực tiểu tuyệt đối. Chứng minh: Giả sử x* là cực tiểu địa phương tại lân cân Bε của x*, ta phải chứng minh nó cũng là cực tiểu tuyệt đối trên tập lồi đã cho.
Phản chứng nếu x* không là cực tiểu tuyệt đối, như vậy sẽ tồn tại x1 sao cho f(x*)>f(x1). Ta xét tổ hợp lồi: ∗ (휆) = 휆 1 + (1 − 휆) , 0 ≤ 휆 ≤ 1 Nếu λ = 0 thì x = x*, chứng tỏ tồn tại λ0, 0 < λ0 ≤ 1 sao cho (휆0) ∈ 휀 ∀휆 ∈ [0, 휆0]. Lấy 0 < 휆1 < 휆0 ⟹ (휆1) ∈ 휀 và khi đó: ∗ ∗ ∗ ∗ [ (휆1)] ≤ (1 − 휆1) ( ) + 휆1 ( 1) < (1 − 휆1) ( ) + 휆1 ( ) = ( ) Mâu thuẫn với việc x* là cực tiểu địa phương. Vậy x* phải là cực tiểu tuyệt đối (Min) Hệ quả: Bất kỳ cực đại địa phương của hàm lõm trên tập lồi cũng là cực đại tuyệt đối (Max) Các hàm lồi có một ý nghĩa cực kỳ quan trọng trong việc giải các bài toán tối ưu mà việc đó xuất phát từ một ý tưởng cực kỳ đơn giản sau: Nếu f(x) là hàm lồi xác định trên tập lồi thì ∀ , ∈ , 휆 ∈ (0,1) thì khi đó = 휆 + (1 − 휆) ∈ [ , ] và ta luôn có: ( ) = [휆 + (1 − 휆) ] ≤ 휆 ( ) + (1 − 휆) ( ) ≤ 휆 + (1 − 휆) = Trong đó: = max[ ( )] ∀ ∈ [ , ] Và dấu bằng xảy ra (nghĩa là ( ) = max[ ( )] ∀ ∈ [ , ]) khi và chỉ khi ( ) = ( ) = [ ( )] ∀ ∈ [ , ] Điều trên dễ dàng suy ra từ định nghĩa và nếu để ý rằng, = 휆 + (1 − 휆) ∈ [ , ] nghĩa là x nằm trong đoạn thẳng [a,b], nó dẫn đến mệnh đề sau: Với nếu hàm lồi f(x) đạt Max tại 1 điểm x nằm trong đoạn [a,b], nó phải đạt Max tại 2 đầu mút a, b của khoảng đó (điểm cứng nhất của đòn gánh nằm tại 1 trong 2 đầu mút của đòn gánh!) A B b E x * a C D
Bây giờ giả sử hàm lồi f đạt Max tại 1 điểm trong x nào đó thuộc hình lồi ABCDE. Lấy 1 điểm a bất kì khác x thuộc hình đó, nối với x và kéo dài đến 1 điểm b bất kỳ (khác x) nằm trong hình lồi. Theo nhận xét trên, do x nằm trong [a, b] và hàm lồi f đạt Max tại x thì f cũng đạt Max tại a (và b). Nghĩa là nếu hàm lồi đạt Max tại 1 điểm trong thuộc tập lồi, thì nó sẽ đạt Max tại bất kỳ điểm nào thuộc tập lồi đó, và khi đó hàm lồi đó là hằng số trong tập lồi đó (tập lồi này có thể là một đoạn thẳng [a,b], cạnh biên AE, một mặt biên hoặc là một đa diện lồi bất kỳ). Suy diễn tiếp theo, nếu hàm lồi f không là hằng số trên một đa diện lồi, nó chỉ có thể đạt Max tại các điểm biên, và nếu nó đạt Max tại điểm biên trong K của cạnh AE, nó phải đạt Max tại mọi điểm trên cạnh đó. Tổng quát hóa hơn nữa nhận xét trên, giá trị Max của một hàm lồi bất kỳ trên một tập lồi đa diện X phải đạt được tại ít nhất 1 trong các đỉnh của đa diện lồi X đó (nếu tồn tại giá trị cực đại). (Điểm cao nhất phải nằm ở đỉnh ngọn núi, đỉnh tòa nhà nào đó, chứ không nằm ở trong lòng núi, trong lòng tòa nhà). Đây là một ý tưởng đơn giản nhưng cực kỳ quan trọng, được sử dụng trọng thuật toán đơn hình để giải bài toán quy hoạch tuyến tính vì khi đó f(x) là hàm bậc nhất, là một trường hợp đặc biệt của hàm lồi, còn các rằng buộc cũng bậc nhất thì tạo nên tập các phương án là 1 đa diện lồi. BÀI 4. QUY HOẠCH TUYẾN TÍNH Quy hoạch tuyến tính là một trong các bài toán quy hoạch được nghiên cứu trọn vẹn cả về lý thuyết lẫn thực hành. Bắt nguồn từ các nghiên cứu của Kantorovic (1937) và Dantzig (1947), nó đã được phát triển khá đầy đủ để giải quyết các bài toán quy hoạch sản xuất. Nó có mô hình khá đơn giản để áp dụng. 4.1 Bài toán tổng quát Bài toán quy hoạch tuyến tính tổng quát có dạng: 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푖푗 푗 (≤, ≥, =) 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛) Trong trường hợp gặp bài toán Min, ta chỉ cần đảo dấu hàm mục tiêu là có bài toán Max, tức là nếu cần:
푛 ∑ 푗 푗 → 푖푛 푗=1 Ta chỉ cần đòi hỏi: 푛 − ∑ 푗 푗 → 푗=1 Là có được kết quả cho bài toán trên (để thất bại của ta là bé nhất, ta yêu cầu thành công của ta là lớn nhất hoặc ngược lại). 4.2 Dạng chuẩn tắc Dạng chuẩn tắc của bài toán quy hoạch là : 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푖푗 푗 ≤ 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛) 4.3 Dạng chính tắc 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푖푗 푗 = 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛) Nếu biểu diễn dưới dạng ma trận ta có thể viết là: 〈 , 〉 → { = 푗 ≥ 0 푗 = 1, 푛 Trong đó: 1 2 = [ ] – vector mục tiêu. 푛
11 12 1푛 21 22 2푛 = [ ⋮ ⋮ ⋱ ⋮ ] – Ma trận rằng buộc 1 2 푛 4.4 Đưa bài toán QHTT về dạng chuẩn hoặc chính tắc Bất kỳ bài toán QHTT nào cũng có thể đưa về dạng chuẩn tắc hoặc chính tắc dựa vào các thao tác sau đây : a. Biến đổi rằng buộc dạng ≥ thành ≤ : Nhân -1 vào cả hai vế của rằng buộc. b. Biến đổi rằng buộc dạng = thành ≥, ≤ : 푛 ∑ ≤ 푛 푖푗 푗 푖 푗=1 ∑ 푖푗 푗 = 푖 ⟺ 푛 푗=1 − ∑ 푖푗 ≤ − 푖 { 푗=1 c. Biến đổi rằng buộc ≥ thành =. Thêm biến phụ yi 푛 푛 ∑ 푖 푖 + 푖 = 푖 ∑ 푖푗 푗 ≥ 푖 ⟺ { 푖=1 푗=1 푖 ≥ 0 d. xi bất kỳ thành 푖 ≥ 0 : Biến đổi xi thảnh tổng 2 biến dương + − + − 푖 = 푖 − 푖 , 푖 ≥ 0, 푖 ≥ 0 4.5 Giải bài toán quy hoạch tuyến tính 2 biến bằng hình học Xét bài toán quy hoạch tuyến tính dưới dạng chuẩn tắc với 2 biến số : 1 1 + 2 2 → { 푖1 1 + 푖2 2 ≤ 푖 (푖 = 1, 푛) 1, 2, , 푛 ≥ 0 Ta xét ví dụ cụ thể sau : Xét bài toán : 2 1 + 3 2 → − ≥ −2 1 2 1 + 2 ≤ 4 1 1 − ≤ 2 1 2 2 { 1, 2 ≥ 0 Mối bất đẳng thức 1 + 2 ≤ xác định một nửa mặt phẳng, trong đó vector 푣 = ( , ) xác định chiều tăng của 1 + 2.
x1 B A C O D x2 Miền rằng buộc D của bài toán trên sẽ là đa giác OABCD. Ta xác định trên đồ thị đường mức 2 1 + 3 2 = 훼 và dễ thấy rằng khi tịnh tiến đường mức α theo hướng vector 푣 = (2,3) thì giá trị của mức sẽ tăng, do vậy khi tịnh tiến sao cho đường mức cắt D ở vị trí cuối cùng thì đó sẽ là điểm thuộc D mà có mức cao nhất, tức khi đó hàm mục tiêu đạt mức tối đa (và giá trị đường mức khi đó cũng chính là giá trị tối ưu của bài toán). Với bài toán cụ thể trên dễ thấy vị trí cuối cùng trong D mà đường mức đi qua là điểm B, dễ xác định là B(1,3) tà ta có = 11 Ta có thể có một số tính chất chung, được nêu mà không chứng minh chi tiết sau : a. Tập các phương án của bài toán QHTT là một tập lồi. b. Nếu bài toán QHTT có lời giải tối ưu, sẽ tồn tại ít nhất 1 phương án cực biên (đỉnh) tối ưu (do vậy mà ta chỉ cần tìm phương án tối ưu tại các đỉnh của tập phương án chấp nhận). Ngoài ra nếu hàm mục tiêu đạt giá trị tối ưu tại nhiều điểm thì nó cũng đạt giá trị tối ưu tại mọi tổ hợp lồi của các điểm đó. c. Ký hiệu 푗, 푗 = 1, 푛 là các cột của ma trận rằng buộc A. Khi đó hệ rằng buộc = có thể viết là : 1 1 + 2 2 + ⋯ + 푛 푛 = (1) Khi đó nếu các vector 푗, 푗 ∈ 퐽 là độc lập tuyến tính và thỏa mãn hệ rằng buộc (1) trong đó 푗 > 0, 푗 ∈ 퐽 thì điểm = ( 1, , 푗, , 푛), 푗 = 0, 푗 ∉ 퐽 sẽ là điểm cực biên (đỉnh) của tập phương án (do mỗi phương trình trong (1) là 1 mặt biên, giao 2 mặt biên sẽ là cạnh biên, giao từ 3 mặt biên trở lên là điểm cực biên). d. Để = ( 1, , 푗, , 푛) là phương án cực biên của bài toán QHTT, cần và đủ là các vector cột Aj của ma trận A ứng với các thành phần xj > 0 là độc lập tuyến tính.
e. Nếu bài toán QHTT có nhiều phương án tối ưu thì bất kỳ tổ hợp lồi của các phương án tối ưu đó cũng là phương án tối ưu (nếu có 2 phương án tối ưu a, b thì mọi điểm thuộc đoạn [a,b] đều là phương án tối ưu ; nếu có 3 điểm a, b, c là phương án tối ưu thì mọi điểm thuộc cạnh tam giác abc là phương án tối ưu, nếu có nhiều điểm a, b, c, d, là phương án tối ưu thì mọi điểm thuộc bao lồi của chúng là phương án tối ưu) Ý tưởng cơ bản của các tính chất trên là với bài toán quy hoạch tuyến tính có lời giải tối ưu, luôn tồn tại phương án tối ưu nằm tại 1 đỉnh nào đó của miền rằng buộc D. Do số đỉnh là hữu hạn nên để tìm phương án tối ưu, ta chỉ cần tìm phương án tối ưu tại các đỉnh mà thôi. Bài tập. 1. Hãy tự xây dựng và thiết lập mô hình một bài toán tối ưu thực tế nào đó. 2. Chuyển các bài toán sau về dạng chuẩn tắc, sau đó chuyển về dạng chính tắc : 3 + 4 − → 1 2 3 1 − 2 + 2 3 ≥ −3 a. 1 + 2 − 3 3 ≤ 4 2 1 − 2 + 3 ≤ 1 { 1, 2, 3 ≥ 0 + 3 − 2 → 1 2 3 1 − 2 2 + 2 3 ≥ 3 b. 2 1 + 3 2 − 3 3 ≤ −2 2 1 − 2 − 3 ≤ −1 { 1, 2, 3 ≥ 0 3. Giải các bài toán quy hoạch tuyến tính 2 biến sau : 3 + 4 → 1 2 1 − 2 ≥ −3 a. 1 + 2 ≤ 4 2 1 − 2 ≤ 1 { 1, 2 ≥ 0 3 + 4 + 2 → 1 2 1 − 2 ≥ −3 b. 1 + 2 ≤ 4 2 1 − 2 ≤ 1 { 1 ≥ 0; 2 ≥ 1 + 4 + 2 → 푖푛 1 2 2 1 + 2 ≤ 6 c. 1 − 2 ≥ −5 2 1 + 3 2 ≥ 4 { 1 ≥ 0; 2 ≥ 1 4. Hãy thử lý giải nhận xét c và d ở cuối chương. 5. Chứng minh nhận xét e ở cuối chương.
Chương 2. Lý thuyết Đối ngẫu BAI 1. BAI TOAN ĐỐI NGẪU Đối ngẫu là một khái niệm ngược lại với khái niệm ban đầu nào đó về một đối tượng nào đó, đại loại như là một thứ âm bản của đối tượng ban đầu. Ví dụ đối ngẫu của mua là bán, đối ngẫu của thắng là thua, của sản xuất là tiêu thụ, của tấn công là bảo vệ, Việc nghiên cứu của bài toán đối ngẫu với bài toán ban đầu nhiều khi cho phép ta có những kết luận và giải pháp hoàn toàn phù hợp, chính xác về bài toán đã cho ban đầu. Chẳng hạn nghiên cứu về khả năng tiêu thụ của sản phẩm nào đó sẽ giúp ích cho việc định hướng sản xuất sản phẩm. Trong việc giải các bài toán QHTT, việc nghiên cứu các bài toán đối ngẫu cho phép chúng ta tìm ra được lời giải của bài toán ban đầu dựa vào một số tính chất khá đơn giản. Xét bài toán QHTT dưới dạng chuẩn, viết theo dạng ma trận : ( ) = 〈 , 〉 → 푖푛 (푃) { ≥ ≥ 0 Khi đó ta nói bài toán : ( ) = 〈 , 〉 → (푃′) { ′ ≤ ≥ 0 Là bài toán đối ngẫu của bài toán (P) ban đầu, trong đó : A là ma trận rằng buộc cấp m × n. A’ là ma trận chuyển vị của A. x, c là vector cột cỡ n. y, b là vector cột cỡ m. 〈 , 〉 là tích vô hướng của 2 vector a, b ⃗⃗ Ta nói ⃗ ≤ ⟺ 1 ≤ 1, 2 ≤ 2, nghĩa là mọi thành phần của vector a bé thua hoặc bằng thành phần tương ứng của vector b. Nếu viết tường minh dưới dạng giải tích thì : 푛 ( ) = ∑ → 푖푛 푗 푗 푗=1 푛 (푃) ∑ 푖푗 푗 ≥ 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛)
Và bài toán đối ngẫu (P’) sẽ là : ′( ) = ∑ → 푖 푖 푖=1 (푃′) ∑ 푖푗 푖 ≥ 푗 (푗 = 1, 푛) 푖=1 { 푖 ≥ 0 (푖 = 1, ) Sự đối ngẫu thể hiện ở sự tương ứng Min và Max, ≤ và ≥, bi và cj, m và n, i và j, A và A’. Ví dụ : Cho QHTT ( ) = 3 + 4 + 5 + → 푖푛 1 2 3 4 1 + 2 2 − 3 + 3 4 ≥ 3 (푃) 2 1 + 3 − 4 4 ≥ 2 3 − + + 2 ≥ 4 1 2 3 4 { 푖 ≥ 0 (푖 = 1,4) Thì bài toán đối ngẫu của nó sẽ là : ( ) = 3 + 2 + 4 → 1 2 3 + 2 + 3 ≤ 3 1 2 3 2 − ≤ 4 (푃′) 1 3 − 1 + 2 + 3 ≤ 5 3 1 − 4 2 + 2 3 ≤ 1 { 푖 ≥ 0 (푖 = 1,2,3) Ta dễ dàng thấy được một số tính chất sau : Định lý 1.1 : Với mọi phương án chấp nhận = 1, 2, , 푛 của P và = 1, 2, , 푛 của P’ ta luôn có : ′( ) = 〈 , 〉 ≤ ( ) = 〈 , 〉. Chứng minh : Dễ thấy là : 〈 , 〉 ≤ 〈 , 〉 = 〈 , ′ 〉 ≤ 〈 , 〉 = 〈 , 〉 푛 푛 푛 〈 , 〉 = ∑ 푖 푖 ≤ ∑ (∑ 푖푗 푗) 푖 = ∑ (∑ 푖푗 푖) 푗 ≤ ∑ 푗 푗 = 〈 , 〉 푖=1 푖=1 푗=1 푗=1 푖=1 푗=1 Hệ quả 1 : Nếu x, y là phương án chấp nhận tương ứng của P & P’ và nếu 〈 , 〉 ≤ 〈 , 〉 : 1. 〈 , 〉 = 〈 , 〉 2. x, y là phương án tối ưu cho P và P’ tương ứng. Chứng minh : Điều 1 là hiển nhiên từ định lý trên. Giả sử 2 không đúng, tức là tồn tại x’ sao cho 〈 , ′〉 < 〈 , 〉 = 〈 , 〉 Mà điều này mâu thuẫn với định lý 1.1
Hệ quả 2. Nếu tồn tại 2 phương án chấp nhận x và y mà 〈 , 〉 = 〈 , 〉 Thì x, y là phương án tối ưu của P và P’ tương ứng. Định lý 1.2 : Nếu 2 QHTT đối ngẫu P và P’ cùng có phương án chấp nhận được thì chúng đều có phương án tối ưu và giá trị tối ưu của chúng bằng nhau. Chứng minh : Gọi x, y là các phương án chấp nhận được của P và P’ tương ứng. Theo định lý 1.1 ta có : 〈 , 〉 ≤ 〈 , 〉 Tức : f(x) bị chặn dưới, vậy P phải có phương án tối ưu x0. f’(y) bị chặn trên, vậy P’ phải có phương án tối ưu y0. Ngoài ra nếu như ta chuyển bài toán P và P’ về dạng chính tắc tương ứng (thay các ≤ và ≥ bởi dấu = ) thì trong chứng minh định lý 1.1 ta luôn có dấu =, như vậy dẫn tới 〈 , 0〉 = 〈 , 0〉, nghĩa là x0, y0 là phương án tối ưu và giá trị của chúng bằng nhau. Định lý đối ngẫu 1.3 : Cho 2 QHTT đối ngẫu P và P’ a. Nếu P và P’ có phương án chấp nhận được thì chúng có phương án tối ưu và giá trị của hàm mục tiêu bằng nhau. b. Nếu 1 trong 2 QHTT có phương án chấp nhận và hàm mục tiêu không bị chặn thì QHTT kia không có phương án chấp nhận. c. Nếu P có phương án chấp nhận mà P’ không có phương án chấp nhận thì các phương án của P có giá trị hàm mục tiêu không bị chặn (có thể thay P bởi P’ và ngược lại). d. Có thể xảy ra trường hợp cả P và P’ đều không có phương án chấp nhận. Chứng minh : a. Đây là nội dung của định lý 1.2 b. Hiển nhiên nếu P có phương án chấp nhận mà P’ cũng có thì theo a, cả 2 phương án trên là tối ưu. Vậy để P không chặn, tức không có phương án tối ưu, thì không thể như trên, tức P’ không thể có phương án chấp nhận được. c. Suy ra từ b. Định lý độ lệch bù 1.4 : Điều kiện cần và đủ để cặp bài toán đối ngẫu P và P’ có cặp 〈 − , 〉 = 0 phương án tối ưu x, y là : { 〈 − ′ , 〉 = 0 Chứng minh : Dễ thấy để P và P’ có phương án tối ưu x, y ; ta phải có 〈 , 〉 = 〈 , 〉, tức là trong phần chứng minh của định lý 1.1, các dấu bất đẳng thức phải là đẳng thức : 〈 , 〉 ≤ 〈 , 〉 ⟺ 〈 − , 〉 = 0 〈 , ′ 〉 ≤ 〈 , 〉 ⟺ 〈 , − ′ 〉 = 0
BAI 2. Ý NGHIA BAI TOAN ĐỐI NGẪU 2.1 Ý nghĩa toán học . Khi 푗 ≥ 0 ∀푗 : Khi đó bài toán đối ngẫu P’ : ′( ) = 〈 , 〉 → (푃′) { ′ ≤ ≥ 0 0 0 Có ngay 1 phương án cựu biên : = [ ] ⋮ 0 . Nếu y là phương án cực biên mà có thêm rằng buộc nữa vào P thì (y, 0) vẫn là phương án cực biên. . Trong một số trường hợp bài toán P’ dễ giải hơn, ví dụ P chỉ có 2 rằng buộc thì P’ là bài toán QHTT 2 biến, có thể giải một cách đơn giản bằng hình học được. . Giải gần đúng : Khi 〈 , 〉 ≅ 〈 , 〉 thì có thể xem như x, y là các nghiệm gần đúng của phương án tối ưu. 2.2 Ý nghĩa kinh tế Ta xét ví dụ : Một công ty A cần trang bị một số bàn, ghê, tủ tại một số phòng khách, phòng làm việc của công ty, với một số yêu cầu cụ thể về số lượng bàn, ghế, tủ tại các phòng đó. Công ty này cũng các định mức kinh phí cao nhất có thể dùng để trang bị cho mỗi phòng khách/phòng làm việc. Hãy xác định số phòng khách/phòng làm việc cần trang bị lại sao cho tổng kinh phí là bé nhất. Ta gọi : x1, x2 – số phòng khách và phòng làm việc cần trang bị lại a11, a12 – số bàn cần có cho 1 phòng khách và 1 phòng làm việc. a21, a22 – số ghế cần có cho 1 phòng khách và 1 phòng làm việc. a31, a32 – số tủ cần có cho 1 phòng khách và 1 phòng làm việc. c1, c2 – chi phí trang bị tối đa cho 1 phòng khách, 1 phòng làm việc. b1, b2, b3 – tổng số lượng tối thiểu bàn, ghế, tủ công ty cần trang bị (để phù hợp với số lượng nhân viên của công ty) f(x) – Tổng chi phí mà công ty A bỏ ra để trang bị. Ta sẽ có bài toán QHTT sau :
( ) = + → 푖푛 1 1 2 2 11 1 + 12 2 ≥ 1 (푃) 21 1 + 22 2 ≥ 2 31 1 + 32 2 ≥ 3 { 1, 2 ≥ 0 (Dễ thấy ta phải có c1, c2, b1, b2, b3 không âm). Cán bộ của công ty sẽ trình bày các điều kiện trên với 1 công ty B chuyên kinh doanh bàn, ghế, tủ văn phòng và cả 2 cùng tranh luận, trao đổi với nhau về giá cả của từng loại. Thự sự thì công ty B chẳng quan tâm tới x1, x2 mà chỉ quan tâm tới giá các loại bàn, ghế, tủ (với các số lượng tối thiều b1, b2, b3) mà thôi. Giả sử y1 – giá bàn, y2 – giá ghế, y3 – giá tủ (và các giá đó không âm) thì hiển nhiên công ty kinh doanh B mong muốn có doanh số cao nhất. Vậy công ty đó sẽ có bài toán QHTT sau : ′ ( ) = 1 1 + 2 2 + 3 3 → + + ≤ (푃′) { 11 1 21 2 31 3 1 12 1 + 22 2 + 32 3 ≤ 2 푖 ≥ 0 (푖 = 1,2,3) Dễ thấy bài toán P có phương án chấp nhận, chẳng hạn lấy x1, x2 thất lớn thì chắc chắn sẽ thỏa mãn các rằng buộc về số lượng bàn, ghế, tủ tối thiểu phải có. Tương tự bài toán P’ có lời giải chấp nhận được, đó là 1 = 2 = 3 = 0. Theo định lý 1.4 chắc chắn có phương án tối ưu cho P và P’. Vấn đề đặt ra là các công ty A và B có đủ hiểu biết để thấy đó là phương án tối ưu và giá cả, chất lượng của trang thiết bị có phù hợp với cả đôi bên để mà chấp nhận nó hay không ? Các rằng buộc c1, c2 trong bài toán trên là giá trần chi phí trang thiết bị cho 1 loại phòng, ví dụ phòng khách chỉ được chi không quá c1 tiền mà phải có được a11 bàn, a21 ghế, a31 tủ chẳng hạn. Công ty B không quan tâm tới số phòng x1, x2 mà chỉ quan tâm tới số bàn b1, số ghế b2, số tủ b3 mà họ sẽ bán được, trong khi công ty A chỉ quan tâm tới giá trần c1, c2 của từng loại phòng chứ không quan tâm tới giá y1, y2, y3 của từng loại bàn, ghế, tủ. Dễ thấy 2 công ty A, B có quyền lợi có vẻ đối kháng nhau : A muốn mua thật rẻ còn B muốn bán thật đắt. Hiển nhiên B không thể lấy giá quá cao, vì nếu giá y1, y2, y3 thì sẽ dẫn đến chẳng hạn 11 1 + 21 2 + 31 3 > 1, vượt quá giá sàn cho phép trang bị cho một phòng khách thì bên A sẽ không đồng ý. Vậy bên B chỉ có thể nâng giá bàn cao một chút, hạ giá ghế đi một chút, tóm lại điều chỉnh sao cho thảo mãn các rằng buộc của A. Hiển nhiên là việc điều chỉnh đó không đưa lại sự lời, lỗ đồng đều trong việc trang bị các loại phòng khác nhau, có thể với mức giá đó thì B chỉ có thể ăn lãi được ở phòng khách, còn lỗ ở phòng làm việc. Theo chiều hướng ngược lại, A lại phải điều chỉnh số lượng từng loại phòng cần trang bị, ví dụ phải tăng số phòng khách (để B có lãi một chút) mà giảm phòng làm việc đi (để B giảm bớt lỗ). Tóm lại hai bên sẽ cò cưa, mặc cả sao cho đến một lúc nào đó thống nhất với nhau và tiến hành hợp đồng. Số lương x1, x2 sẽ là
phương án tối ưu của A, còn giá trị y1, y2, y3 là phương án tối ưu của B và giá trị hợp dồng chính là giá trị tối ưu của bài toán bán lẫn bài toán mua. Bài toán P và P’ mới chỉ nói đến giá cả tối ưu chứ chưa hề nói đến chất lượng. Ta có thể thấy được điều này khi nhận xét rằng, với bất kỳ mức giá nào thì ta có chất lượng tương ứng, tiền nào của nấy mà lại. Do vậy khi đã có giá cả đó thì hai bên sẽ phải xem xét đến chất lượng của hàng hóa ! Bên B sẽ dựa vào giá trị y1, y2, y3 để làm ra các bàn, ghế, tủ có chất lượng tương ứng trong khi A thì xem xét liệu chất lượng hàng hóa đó có phù hợp với giá mà bên B nêu ra hay không ? Việc thương thảo giữa hai bên sẽ không thực hiện được khi mà bên A định giá trần cho việc trang bị phòng quá thấp so với chất lương yêu cầu về các loại bàn, ghế, tủ. Khi đó phương án tối ưu cho bài toán P’ là các mức giá y1, y2, y3 quá thấp, dẫn tới B thua lỗ nếu đảm bảo chất lượng hàng hóa như A yêu cầu, hoặc B sẽ phải sản xuất những bàn, ghế, tủ với chất lượng kém mà A không chấp nhận được. Nghĩa là bài toán P và P’ không thể có lời giải tối ưu khi cả hai bên đều đưa ra những mức giá không hợp lý với chất lượng hàng hóa : Bên mua muốn mua hàng chất lượng cao với giá bèo bọt, còn bên bán muốn bán hàng gia công với giá hàng hiệu  ! Tóm lại, cả hai bên sẽ phải mặc cả với nhau, bên bán hạ giá xuống một chút, bên mua nâng lên một chút cho tới khi 2 bên thống nhất đi đến một mức giá bằng nhau, trung hòa được các đòi hỏi về chất lượng và giá cả của cả hai bên. Đó chính là phương án tối ưu cho bài toán bán và mua hàng mà chúng ta gặp hàng ngày. Bài tập. 1. Nêu bài toán đối ngẫu của bài toán lập kế hoạch, bài toán cái túi. 2. Tử đi tìm ví dụ cụ thể và ý nghĩa bài toán đối ngẫu của 2 bài toán trên. 3. Trường hợp nào bài toán quy hoạch có phương án chấp nhận nhưng bài toán đối ngẫu không có ? Cho ví dụ bằng bài toán thực tế, hoặc cho mô hình toán học cụ thể. 4. Giải thích ý nghĩa của định lý đối ngẫu.
Chương 3. Bài toán Vận tải BAI 1. BAI TOAN 1.1 Mô hình Cho n kho hàng A1, A2, ,An có lượng hàng tương ứng a1, a2, , an cần được chuyển đến các kho hàng B1, B2, , Bm với các mức yêu cầu b1, b2, , bm. Biết rằng chi phí vận chuyển 1 đơn vị hàng hóa từ Ai tới Bj là cij, hãy xác định xij – lượng hàng cần chuyển từ Ai tới Bj sao cho tổng cước phí là bé nhất với điều kiện : 푛 ∑ 푖 = ∑ 푗 푖=1 푗=1 (điều kiện cân bằng thu – phát.) Như vậy đây là bài toán quy hoạch tuyến tính : 푛 ∑ ∑ _푖푗 → 푖푛 ① 푖푗 푖=1 푗=1 ∑ 푖푗 = 푖 (푖 = 1, 푛) ② 푗=1 푛 ∑ 푖푗 = 푗 (푗 = 1, ) ③ 푖=1 푛 ∑ = ∑ ④ 푖 푗 푖=1 푗=1 { 푖푗 ≥ 0 (푖 = 1, 푛; 푗 = 1, ) ⑤ Dễ thấy là hệ ②, ③ có m+ n phương trình nhưng chúng phụ thuộc tuyến tính, do tổng của n phương trình trong ② bằng tổng m phương trình trong ③, nghĩa là hạng của m + n phương trình đó cao nhất chỉ là m + n - 1 mà thôi (có thể kiểm chứng đc thực chất đúng bằng m + n - 1). Ta có thể đưa bài toán vận tải về dạng ma trận như sau : 〈 , 〉 → 푖푛 { = 푖푗 ≥ 0 (푖 = 1, 푛; 푗 = 1, ) Với : = ( 11, 12, 1 , 21, 푛1, 푛2, 푛 ) = ( 11, 12, 1 , 21, 푛1, 푛2, 푛 )
= ( 1, 2, 푛, 1, 2, ) 〈 , 〉 = 11 11 + 12 12 + ⋯ + 푛 푛 (푛+ )×(푛 ) : Ma trận A có (n+m) hàng và (n.m) cột, các cột được đánh số từ col11 → colnm. Tại cột colij có 2 số 1 ở dòng thứ i và dòng thứ n+j, các số hạng còn lại bằng 0. 표푙11 표푙1 표푙11 표푙1 표푙11 표푙1 표푤1 ⏞1 1 ⋯ 1 ⏞ ⏞ 표푤2 1 1 ⋯ 1 ⋯ ⋮ 표푤푛 = 1 1 ⋯ 1 표푤푛+1 1 1 1 표푤푛+2 1 1 ⋯ 1 ⋮ ⋱ ⋱ ⋱ 표푤푛+ [ 1 1 1 } ] Có thể kiểm tra hạng của ma trận A bằng m + n - 1 (tổng n hàng đầu tiên bằng tổng m hàng sau cùng !) Khi đó bài toán đối ngẫu của bài toán vận tải sẽ là : ′( ) = 〈 , 〉 → { ′ ≤ > 0 Với = ( 1, 2, , 푛+ ) ( = ở bài toán vận tải ta xem như ≥ để trong bài toán ′ đối ngẫu có ≤ ). Đổi biến = ( 1, 2, , 푛, 푣1, 푣2, , 푣 ) ta được 푛 푛 ∑ 푖 푖 + ∑ 푗푣푗 → 푖=1 푗=1 { 푖 + 푣푗 ≤ 푖푗 (푖 = 1, 푛; 푗 = 1, ) Mà nó đơn giản hơn rất nhiều so với bài toán vận tải ban đầu. Các giá trị ui, vj được gọi là các thế vị củ các ai, bj trong bài toán QHTT. 1.2 Nghiệm tối ưu Định lý 1.1 : Bài toán vận tải luôn có phương án tối ưu. Chứng minh : Đặt : 푛 푆 = ∑ 푖 = ∑ 푗 푖=1 푗=1 Ta thấy rằng : 푖 푗 = 푖푗 푆
Là một nghiệm do : 푖푗 ≥ 0 푖 푗 ∑푗=1 푗 푆 ∑ = ∑ = = = (푖 = 1, 푛) 푖푗 푆 푖 푆 푖 푆 푖 푗=1 푗=1 푛 푛 푛 푖 푗 ∑ 푆 ∑ = ∑ = 푖=1 푖 = = (푗 = 1, ) 푖푗 푆 푗 푆 푗 푆 푗 푖=1 푖=1 Vậy miền rằng buộc của bài toán vận tải luôn khác rỗng. Mặt khác hàm mục tiêu bị chặn bởi 0 nên phải có giá trị cực tiểu, tức bài toán có phương án tối ưu. BAI 2. TIEU CHUẨN NHẬN BIẾT PHƯƠNG AN TỐI ƯU Với một bài toán QHTT ta lập bảng phương án T gồm m hàng và n cột (không kể hàng đầu và cột đầu bảng làm tiêu đề). Các hàng được đánh số từ 1, 2, , 푛, các cột được đánh số 1, 2, , ; tại ô (i,j) ở hàng i và cột j ta ghi giá trị xij ở giữa ô và cij ở góc dưới bên trái. Nếu 푖푗 > 0 ⇒ ô (푖, 푗) được gọi là ô sử dụng, ngược lại nếu 푖푗 = 0 ⇒ ô đó không được sử dụng và để tránh rối mắt, ta không ghi 푖푗 = 0 vào ô đó. Bj b1 b2 bm-1 bm Ai x11 x12 x1(m-1) x1m a1 c11 c12 c1(m-1) c1m x21 x21 x2(m-1) x2m a2 c21 c22 c2(m-1) c2m ⁞ x(n-1)1 x(n-1)2 x(n-1)(m-1) x(n-1)m an-1 c(n-1)1 c(n-1)2 c(n-1)(m-1) c(n-1)m xn1 xn2 xn(m-1) xnm an cn1 cn2 cn(m-1) cnm Ta có các khái niệm sau : Ô cùng hàng : có dạng (푖, 푗1) (푖, 푗2) Ô cùng cột : có dạng (푖1, 푗) (푖2, 푗) Dây chuyền (hoặc xích) : Dãy các ô cùng hàng, cùng cột luân phiên nhau. (푖1, 푗1), (푖1, 푗2), (푖2, 푗2), hoặc (푖1, 푗1), (푖2, 푗1), (푖2, 푗2), Chu trình : Là một dây chuyền có điểm đầu và điểm cuối trùng nhau.
Gọi G là tập các ô sử dụng của T : = {(푖, 푗) : 푖푗 > 0} Ta có một số tính chất sau : Định lý 2.1 : Một tập K các ô của T chứa chu trình nếu mỗi dòng và mỗi cột của nó hoặc không chứa ô nào thuộc K, hoặc chứa từ 2 ô trở lên. Chứng minh : Giả sử ta lấy 1 ô bất kỳ (푖1, 푗1) ∈ 퐾, đánh dấu nó là dấu +. Trên hàng i1 còn có một ô khác thuộc K chẳng hạn ô (푖1, 푗2), đánh dấu nó là dấu –. Tiếp tục tìm trong cột j2 một ô (푖2, 푗2) đánh dấu nó là dấu + và tiếp tục quá trình trên để xác định một dây chuyền. Do số ô của K là hữu hạn cho nên đến một lúc nào đó quá trình trên sẽ gặp lại ô ta đã đánh dấu như trên, tức là ta có một dây chuyền khép kín chu trình. Định lý 2.2 : Hệ thống vector cột colij tương ứng với các ô (푖, 푗) ∈ 퐾 của bài toán vận tải là độc lập tuyến tính khi và chỉ khi các ô (푖, 푗) ∈ 퐾 đó không tạo chu trình. { ) (Nếu 퐾 = 푖 , 푗 : ∈ 퐾} không có chu trình ⇔ { 표푙푖 푗 } độc lập tuyến tính) Chứng minh : Thay vì chứng minh điều trên, ta chứng minh mệnh đề tương đương { ) Nếu 퐾 = 푖 , 푗 : ∈ 퐾} có chu trình ⇔ { 표푙푖 푗 } phụ thuộc tuyến tính. . Điều kiện đủ : Gọi 푖푗 = { 표푙푖푗: (푖, 푗) ∈ 퐾} Giả sử Cij chứa chu trình : (푖1, 푗1), (푖1, 푗2), (푖2, 푗2), , (푖푠, 푗1) Thì dễ thấy là : 표푙푖1푗1 − 표푙푖1푗2 + 표푙푖2푗2 − ⋯ − 표푙푖푠푗1 = 0 Tức là 표푙푖1푗1, 표푙푖1푗2, 표푙푖2푗2, 표푙푖푠푗1 phụ thuộc tuyến tính. . Điều kiện cần : Giả sử 표푙푖 푗 phụ thuộc tuyến tính, ta cần chứng minh K chứ chu trình. Nếu 표푙푖 푗 phụ thuộc tuyến tính, tức là tồn tại tổ hợp ∑ 표푙푖 푗 = 0 ( ≠ 0) ∈ ⊂ Lấy một ô (푖 , 푗 ) bất kỳ trong tập K mà có ≠ 0 trong tổ hợp trên. Do vector cột 표푙푖 푗 chỉ có hai số 1 ở vị trị thứ ik và m+jk (còn lại toàn số 0), cho nên tập K ở trên phải chứa ít nhất 2 ô ở hàng ik để chúng có thể khử số 1 ở vị trị ik và chứa ít nhất 2 ô trên cột jk để khủ được số 1 ở vị trí m+jk của tổ hợp tuyến tính trên. Tóm lại là trên mỗi cột hoặc hàng, hoặc không có ô nào thuộc K, hoặc phải có từ 2 ô trở lên. Vậy theo định ý 2.1 thì tập K chứa chu trình. Định lý 2.3 : Vector x của bài toán vận tải là phương án cực biên khi các ô sử dụng của nó không chứa chu trình.
Chứng minh : Ta thấy bài toán vận tải là một QHTT và theo định lý 2.2 thì các vector 표푙푖 푗 với xij > 0 độc lập tuyến tính khi và chỉ khi tập các ô sử dụng không chứ chu trình. Vậy theo nhận xét d ở cuối chương 1, phương án = ( 11, 12, , 1 , 21, , 푛1, , 푛 ) Là phương án cực biên khi và chỉ khi các ô sử dụng không chứa chu trình. Một phương án cực biên của bài toán vận tải được gọi là không thoái hóa nếu | | = + 푛 − 1, thoái hóa nếu | | < + 푛 − 1 trong đó | | là số ô sử dụng của phương án G. Bài toán vận tải được gọi là bài toán không thoái hóa nếu mọi phương án cực biên đều là không thoái hóa, ngược lại gọi là bài toán thoái hóa (bài toán vận tải thoái hóa có thể có cả phương án cực biên thoái hóa và phương án cực biên không thoái hóa). Định lý 2.4 : Nếu một phương án x của bài toán vận tải có tập G chứ chu trình thì ta có thể điều x trở thành x’ có giá trị hàm mục tiêu không lớn hơn và tập các ô sử dụng G’ tương ứng không chứa chu trình. Chứng minh : Ta xét một chu trình đơn giản sau : 퐾 = (푖1, 푗1), (푖1, 푗2), (푖2, 푗2), (푖2, 푗1) Nếu ta thêm vào ô thứ nhất một lượng hàng α, bớt ở ô thứ hai α, thêm vào ô thứ ba α, bớt ở ô thứ tư α thì ta thấy rằng : . Nếu 훼 ≤ 푖푛{ 푖1푗2, 푖2푗1} thì sau khi bớt α các ô này vẫn không âm . Tổng giá trị lượng hàng trên các hàng và cột sau khi thêm, bớt vẫn không thay đổi, nghĩa là ta vẫn có một phương án vận tải. . Cước phi vận chuyển thay đổi một lượng là : Δ = 훼[ 푖1푗1 + 푖2푗2 − 푖1푗2 − 푖2푗1] Nếu 푖1푗1 + 푖2푗2 < 푖1푗2 + 푖2푗1 thì rõ ràng là 훥 ≤ 0. . Nên lấy α bằng giá trị nhỏ nhất tại ô thứ hai hoặc ô thứ tư thì giá trị hàng hóa ở ô đó sẽ bằng 0 và ta sẽ không còn chu trình nữa. Tóm lại ta được một phương án mới không có chu trình và có cước phí không cao hơn so với phương án trước đây. Tổng quát : Với một chu trình K bất kỳ : 퐾 = (푖1, 푗1), (푖2, 푗1), (푖2, 푗2), , (푖 , 푗1) Ta lần lượt đánh số chẵn, lẽ cho các ô liên tiếp của chu trình. Gọi KE là tập các ô chẵn, còn KO là tập các ô lẽ. Giả sử : 푣푒푛 = ∑ 푖푗 ≤ ∑ 푖푗 = (푖,푗)∈퐾 (푖,푗)∈퐾 Lấy 훼 = 푖푛{ 푖푗: (푖, 푗) ∈ 퐾 } và chuyển x thành x’ theo công thức :
푖푗 (푖, 푗) ∉ 퐾 ′ 푖푗 = { 푖푗 + 훼 (푖, 푗) ∈ 퐾 푖푗 − 훼 (푖, 푗) ∈ 퐾 Khi đó : . x’ vẫn là phương án của bài toán vận tải, vì tổng các cột và các hàng không đổi, vẫn có 푖푗 ≥ 0. . Hàm mục tiêu giảm đi một lượng Δ = 훼( − 푣푒푛) (Nếu Even > Odd thì chỉ cần làm ngược lại) . Có ít nhất 1 ô (i, j) mà 푖푗 = 훼 = 푖푛{ 푖푗: (푖, 푗) ∈ 퐾 } trở thành ô không sử dụng, nghĩa là chu trình bị ngắt tại ô đó, ta không có chu trình nữa (tức là phương án x trở thành phương án cực biên x’ !). Việc làm trên được gọi là phá vỡ chu trình, thực chất đấy là việc từ 1 phương án không cực biên tìm ra một phương án cực biên có giá trị hàm mục tiêu không tồi hơn so với phương án đó. Trên thực tế việc phá vỡ chu trình rất giống với việc từ một điểm trên sườn núi đi tới đỉnh của chính ngọn núi đó (mà đỉnh núi thì chắc chắn không thấp hơn sườn núi của đỉnh núi đó). Hệ quả : Mọi phương án x đều có thể chuyển về phương án cực biên x’ không tồi hơn x. Định lý 2.5 : Mọi phương án x chứa lớn hơn hoặc bằng m + n ô sử dụng đều chứa chu trình. Chứng minh : Nếu x chứa m + n ô trở lên, tức tập các vector 표푙푖푗 ứng với các ô sử dụng lớn hơn m + n – 1, do hạng của ma trận A là m + n – 1 nên các vector đó phải phụ thuộc tuyến tính, tức tập các ô sử dụng phải có chu trình. BAI 3. TIEU CHUẨN TỐI ƯU Ta có bài toán vận tải là : 〈 , 〉 → 푖푛 { = 푖푗 ≥ 0 (푖 = 1, 푛; 푗 = 1, ) Và bài toán đối ngẫu của nó : 푛 푛 ∑ 푖 푖 + ∑ 푗푣푗 → 푖=1 푗=1 { 푖 + 푣푗 ≤ 푖푗 (푖 = 1, 푛; 푗 = 1, ) Theo lý thuyết đối ngẫu, nếu bài toán vận tải có lời giải tối ưu : = ( 11, 12, , 1 , 21, , 푛1, , 푛 ) Thì bài toán đối ngẫu cũng có lời giải tối ưu = ( 1, 2, 푛, 푣1, 푣2, , 푣 )
Và theo định lý về độ lệch bù , x là lời giải tối ưu của bài toán vận tải, y là lời giải tối ưu của bài toán đối ngẫu khi và chỉ khi : 〈 − , 〉 = 0 ① { 〈 , ′ − 〉 = 0 ② Dễ thấy là ① luôn đúng nếu đã có x là phương án của bài toán vận tải (do = ⇒ − = 0 ⇒ 〈 − , 〉 = 〈0, 〉 = 0. Ngoài ra theo định nghĩa tích vô hướng của hai vector thì ② sẽ tương đương với : ∑( 표푙푖푗 − 푖푗) 푖푗 = 0 ⟺ ∑( 푖 + 푣푗 − 푖푗) 푖푗 = 0 푖푗 푖푗 (do 표푙푖푗 là cột thứ ij của ma trận A nên 표푙푖푗 = 푖 + 푣푗) 푖푗 ≥ 0 nên tổng đó bằng 0 khi và chỉ khi 푖 + 푣푗 = _푖푗 nếu 푖푗 > 0 Vậy từ đó ta có điều kiện tối ưu của phương án x như sau : Định lý 3.1 : Phương án x của bài toán vận tải là phương án tối ưu khi và chỉ khi tồn tại (xác định được) các giá trị 푖, 푖 = 1, 푛 & 푣푗, 푣 = 1, sao cho Δ푖푗 = 푖 + 푣푗 − 푖푗 ≤ 0 ∀(푖, 푗) ∈ ③ { 푖 + 푣푗 = 푖푗 ∀ 푖푗 > 0 ④ Điều kiện (3) là cần thiết để ui, vj là các phương án của bài toán đối ngẫu). Các giá trị ui, vj được gọi là các thế vị của các điểm phát ai và các điểm thu bj. Ý nghĩa : . Các phương trình (4) cho phép ta tìm các thế vị 푖, 푖 = 1, 푛 & 푣푗, 푣 = 1, , còn các bất đẳng thức (3) được dùng để kiểm tra điều kiện tối ưu của phương án (và chỉ dành cho các ô không sử dụng, vì với các ô sử dụng ta luôn có Δij = 0). . Số các thế vị (ẩn số) là m + n, còn số phương trình ④ bằng số các ô sử dụng. Do ta sẽ chỉ thực hiện việc tính các thế vị khi phương án phải là cực biên nên khi đó số ô sử dụng k sẽ bé hơn n + m (thông thường với phương án không thoái hóa ta có số ô sử dụng là m + n – 1), tức khi đó ta có hệ phương trình bậc nhất vô định. Để giải nó ta có thể chọn n + m – k giá trị ui, vj ban đầu bất kỳ, thường ta hay lấy chúng bằng các giá trị nguyên, bé cho đơn giản các tính toán. Thế vị đầu tiên có thể tùy ý, chẳng hạn lấy u1 = 0, còn các giá trị tiếp theo phụ thuộc vào biến đó có liên quan tới u1 hay không. Trường hợp số ô sử dụng ít hơn m + n từ 2 trở lên thì việc lấy các thế vị tiếp theo phải bảo đảm chúng thực sự có liên quan với nhau (thông qua các phương trình ④) để tránh sự mâu thuẫn giữa các thế vị đó với nhau. Ta sẽ bàn về việc nên làm thế nào trong trường hợp đó cho tốt nhất trong phần nhận xét tại các ví dụ thực tế. . Trong lập luận dẫn đến điều kiện tối ưu trên ta có ∑푖푗( 푖 + 푣푗 − 푖푗) 푖푗 = 0 vậy nên nếu một giá trị nào 푖푗 = 0 thì Δ푖푗 = 푖 + 푣푗 − 푖푗 có thể là một giá trị bất kỳ, nghĩa
là với điều kiện tối ưu Δ푖푗 ≤ 0 với mọi ô sử dụng là cần và đủ chỉ cho phương án không thoái hóa, có ∀풙풊풋 > . BAI 4. PHƯƠNG AN SẢN XUẤT Với bài toán vận tải ta có nhiều cách để xác định một phương án xuất phát ban đầu. Sau đây là một số cách đó : 4.1 Phương pháp góc Tây-Bắc Tư tưởng của phương án này là tiến hành phân phối hàng từ trên xuống dưới, từ trái qua phải cho tới khi hết nhu cầu. Như vậy ta sẽ tiến hành đầu tiên cho ô (1,1) nằm ở góc Tây-Bắc và phân phối tối đa lượng hàng A1 vào đây. Nghĩa là ta lấy 11 = 푖푛( 1, 1) Có 2 khả năng xảy ra : . 11 = 1 : Đã hết hàng ở kho A1, coi như lúc đó ta chỉ còn lại n – 1 kho hàng còn lại, ′ và điểm thu B1 cần thêm một lượng 1 = 1 − 1 ′ . 11 = 1 : Cửa hàng B1 đã nhận đủ hàng, kho A1 còn lại một lượng hàng 1 = 1 − 1 và ta tiếp tục phân phối hàng tiếp cho cửa hàng tiếp theo. Tiếp tục quá trình trên cho đến cuối cùng thì ta sẽ được một phương án mà dễ nhận thấy là không có chu trình, nghĩa là cực biên và do vậy mà có không quá m + n – 1 ô sử dụng. Phương án này có nhược điểm là không quan tâm tới cước phí vận chuyển giữa các địa điểm. Ví dụ : Tìm phương án xuất phát cho bài toán vận tải với : = (50,70,41) = (0,60,46,25) 4 7 12 7 = [5 9 6 1] 8 2 9 1 Ta có phương án xuất phát như sau : ( ) = 969 Bj 30 60 46 25 Ai 50 30 20 4 7 12 7 70 40 30 5 9 6 1 41 16 25 8 2 9 1
4.2 Phương pháp cực tiểu cước phí Nếu quan tâm tới cước phí giữa các địa điểm khác nhau, ta có thể có các phương án xuất phát ban đầu với cước phí thấp hơn so với phương án xuất phát thu được theo phương pháp góc Tây – Bắc. Ta cũng phân phối hàng ở mức tối đa (để xóa các hàng hoặc cột) nhưng không phải cho ô ở góc Tây – Bắc mà cho ô có cước phí thấp nhất trong hàng (cột). Ví dụ vẫn bài toán trên ta có phương án xuất phát cực tiểu cước phí theo hàng như sau : Bj 30 60 46 25 Ai 50 30 20 4 7 12 7 70 45 25 5 9 6 1 41 40 1 8 2 9 1 Ta thấy hàm mục tiêu ( ) = 644 nhỏ hơn hẳn so với phương án góc Tây – Bắc. Phân phối hàng hóa tối đa cho ô nào có cước phí bé nhất trong toàn bảng : Bj 30 60 46 25 Ai 50 30 19 1 4 7 12 7 70 45 25 5 9 6 1 41 41 8 2 9 1 Và giá trị hàm mục tiêu cũng rất bé ( ) = 642
BAI 5. THUẬT TOAN THẾ VỊ Trên cơ sở các kiến thức đã nêu ở trên, ta có thuật toán thế vị giải bài toán vận tải như sau : Bước 1 : Tìm phương án xuất phát 풙 = (풙풊풋) theo các phương pháp mô tả ở Bài 4. Bước 2 : Kiểm tra tính tối ưu của phương án : a. Nếu các ô sử dụng lập thành chu trình thì phá vỡ chu trình để chuyển về phương án cực biên (không chứa chu trình). b. Xác định thế vị ui, vj từ hệ phương trình 푖 + 푣푗 = 푖푗 (푖 = 1, 푛; 푗 = 1, ) Với (푖, 푗) ∈ ( ) – tập các ô sử dụng của x. Với x là phương án không thoái hóa, ta có m + n ẩn số mà chỉ có m + n – 1 phương trình, ứng với m + n – 1 ô sử dụng của G(x). Do vậy mà có thể các định trước 1 giá trị nào đó cho ẩn số ui hoặc vj ban đầu tùy ý, thường ta lấy giá trị 0 cho dễ tính. Khi đó m + n – 1 ẩn số còn lại được xác định một các duy nhất từ các phương trình trên. Trường hợp x là phương án thoái hóa, khi số ô sử dụng là m + n – k với k > 1 thì ta phải xác định trước không phải 1 ẩn số mà là k ẩn số ! Quy tắc : . Thường lấy 푖1 = 0 (i1 là dòng đầu tiên hoặc dòng chứa ô sử dụng đầu tiên). . Xác định 푣푗 = 푖푗 − 푖 cho mọi cột j mà 푖푗 là sô sử dụng, . Xác định 푖 = 푖푗 − 푣푗 cho mọi hàng i mà 푖푗 là sô sử dụng. . Tiếp tục bước trên cho tới khi xác định được tất cả các ui, vj cho tất cả mọi dòng, mọi cột. Nếu như m + n – k > 1 thì số thế vị được nhận giá trị tùy ý sẽ tăng lên tương ứng, và thứ tự của các thế vị đó sẽ phụ thuộc vào trình tự tính toán cụ thể. c. Kiểm tra tính tối ưu : Với mọi ô (푖, 푗) ∉ ( ) ta xác định các giá trị : Δ푖푗 = 푖 + 푣푗 − 푖푗 ∀(푖, 푗) ∉ ( ) Khi đó sẽ xảy ra 1 trong 2 khả năng : . Δ푖푗 = 푖 + 푣푗 − 푖푗 ≤ 0, ∀(푖, 푗) ∉ ( ) : x là phương án tối ưu, tính f(x) và dừng lại. . ∃Δ푖푗 = 푖 + 푣푗 − 푖푗 > 0 : x chưa là phương án tối ưu, còn có thể điều chỉnh được ở bước 3 (với x thoái hóa, nếu chọn các thế vị không khéo, phương án đã tối ưu rồi mà ta vẫn có Δ푖푗 > 0, có thể xem và tránh điều này ở phần sau )
Bước 3 : Điều chỉnh : Giả sử có Δ푖푗 > 0, ta chọn (i*, j*) có Δi*j* lớn nhất (với hi vọng hàm mục tiêu giảm nhanh nhất) đưa vào làm ô sử dụng bằng cách cho xi*j* = 0 (ta gọi đó là “quy 0” ô (i* ,j*). Khi đó ( ) ∪ (푖∗, 푗∗) sẽ có m + n ô (với phương án thoái hóa thì có thể chưa đủ m + n ô, cần quy 0 thêm một số ô nữa cho đủ m + n), nên sẽ có chu trình. Lấy xi*j* = 0, tức là đưa ô (i*, j*) trở thành ô sử dụng và quay trở lại bước 2 để lại tiếp tục phá vỡ chu trình đó, tiến tới một phương án cực biên mới tốt hơn. Nhận xét về thuật toán : I. Với bài toán không thoái hóa. a. Để tính n + m thế vị, cần cho trước mộ giá trị nào đó, chẳng hạn u1 = 0 và xác định n + m – 1 thế vị còn lại (thông qua n + m – 1 ô sử dụng). Các giá trị đó phụ thuộc vào giá trị tùy chọn u1 ban đầu, biết được u1 thì biết được các thế vị khác. Khi đó ta nói rằng các thế vị đó là liên thông với nhau và nếu u1 tăng lên α thì mọi ui đều tăng lên α ; vọi vi đều giảm đi α. Điều đó dẫn tới việc giá trị của các hệ số Δij được xác định một cách duy nhất cho ô đó, dù ta lấy giá trị tùy chọn ban đầu là thế nào. b. Hệ số Δij xác định duy nhất đó có thể xem như là thước đo thể hiện mức độ hợp lý của các ô không sử dụng (i, j) : Nếu hệ số Δ푖푗 ≤ 0 có nghĩa việc ta không sử dụng (không phân hàng từ Ai chở đến Bj) ô (i, j) là hợp lý (vì giá cước của nó quá đắt !), ngược lại là bất hợp lý nếu giá cước của nó rẻ mà ta lại không phân hàng để chuyên chờ. Nếu tất cả mọi Δ푖푗 ≤ 0, có nghĩa là việc ta không sử các ô đó đều hợp lý, vậy phương án là tối ưu. Còn nếu có một ô không sử dụng nào có Δ푖푗 > 0, nghĩa là có một ô nào đó còn bất hợp lý (giá cước vận tải rẻ mà không được chuyên chở hàng) thì phương án chưa tối ưu. Khi đó ta sẽ cần thực hiện việc điều chỉnh với ô đó. Do mỗi lần chỉ điều chỉnh 1 ô nên nếu có nhiều ô bất hợp lý thì ta điều chỉnh với ô bất hợp lý nhất, tức có hệ số Δ푖푗 > 0 là lớn nhất. c. Việc “quy 0” trong bước điều chỉnh, chẳng qua là để số ô sử dụng đủ bằng m + n, dẫn tới có chu trình. Bằng cách đó ta có phương án mới, có cùng giá trị hàm mục tiêu và có chu trình. Khi đó ta có thể phá vỡ chu trình để có phương án tốt hơn. Nếu xem việc đi tìm phương án tối ưu như việc leo lên đỉnh núi cao nhất, thì đây chẳng qua là việc từ một đỉnh núi chưa cao nhất “bay sang” một điểm trên sườn núi khác có cùng độ cao như đỉnh núi đó mà thôi. Khi sang sườn núi này, ta lại tiếp tục leo lên đỉnh để đạt được vị trí cao hơn đỉnh lúc nãy và cứ thế mãi thì cuối cùng ta sẽ leo lên được đỉnh núi cao nhất. Do Δ푖푗 > 0 biểu thị rằng phương án chưa tối ưu, nghĩa là ô (i, j) chưa hợp lý nên ta sẽ thực hiện việc điều chỉnh với (i, j) đó. Ta có thể đưa ô bất kỳ nào đó Δ푖푗 > 0 vào làm ô sử dụng, tuy nhiên nên chọn ô có Δ푖푗 > 0 lớn nhất vì chắc đó là ô bất hợp lý nhất làm cho cước phí chưa tối ưu. Ý nghĩa thực tế của việc
đưa một ô nào đó vào làm ô sử dụng là : Khi thấy việc không cấp hàng từ Ai đến Bj với mức cước cij là bất hợp lý (do Δ푖푗 > 0), ta đưa đơn vị đó vào diện chờ để điều chỉnh, để cấp hàng. d. Nếu phương án x là không thoái hóa thì việc đưa quy 0 ô (i, j) có 휟풊풋 > làm ô sử dụng sẽ tạo nên phương án x’ có chu trình mà việc phá vỡ chu trình đó sẽ dẫn tới phương án cực biên mới có hàm mục tiêu tốt hơn. Nghĩa là quá trình điều chỉnh ô bất hợp lý của phương án không thoái hóa là thực sự có hiệu quả. Ta chứng minh điều đó như sau : Giả sử ta có Δ푖푗 > 0, ta đưa ô (i, j) vào làm ô sử dụng. Khi đó ta có m + n ô sử dụng và như vậy sẽ xuất hiện chu trình bắt đầu từ chính ô (i1, j1). Giả sử chu trình đó là : (푖1, 푗1), (푖1, 푗2), (푖2, 푗2), , (푖 , 푗 ), (푖 , 푗1) Và ta đánh dấu các đỉnh đó lần lượt là Odd, Even, Odd, ,Even. Với các thế vị trước đây ta có : Δ푖1푗1 > 0 ⟺ 푖1 + 푣푗1 − 푖1푗1 > 0 Δ > 0 ⟺ + 푣 − = 0 푖1푗2 푖1 푗2 푖1푗2 ① ⋯ Δ푖 푗1 > 0 ⟺ 푖 + 푣푗1 − 푖 푗1 = 0 Cộng các hàng lẻ và trừ đi các hàng chẵn các hệ thức trên, ta được : − 푖1푗1 + 푖1푗2 − 푖2푗2 + ⋯ + 푖 푗1 = 푣푒푛 − > 0 ② Điều đó có nghĩa tổng cước phí các ô chẵn cao hơn các ô lẻ và chúng ta sẽ điều chỉnh từ các ô chẵn sang các ô lẻ một lương hàng hóa 훼 = min { 푖푗} > 0. (do (푖,푗)∈ 푣푒푛 các ô sử dụng của phương án không thoái hóa đều có lượng hàng xij > 0). Việc điều chỉnh đó sẽ dẫn tới phương án cực biên mới x’ có hàm mục tiêu bé hơn một lượng Δ = 훼( 푣푒푛 − ) > 0 do cả 2 thừ số α và (CEven – COdd) đều lớn hơn 0. Điều trên không luôn đúng với các phương án không thoái hóa, lý do là khi đưa ô (i1, j1) vào làm ô sử dụng thì có thể ta vẫn chưa có chu trình (do số ô chưa đủ n + m) và do vậy mà số các đẳng thức ① trên chưa đủ để có thể loại trừ lẫn nhau các ui, vj để khi cộng chúng lại, ta có ②. Chứng minh trên chỉ ra rằng, việc điều chỉnh ô bất hợp lý của phương án cực biên không thoái hóa (bao gồm việc đưa thêm ô sử dụng mới vào và phá vỡ chu trình mới được tạo ra) để dẫn tới phương án cực biên mới là thực sự có hiệu quả với các ô Δ푖푗 > 0. Còn với các ô Δ푖푗 ≤ 0 thì việc điều chỉnh trên hoàn toàn vô nghĩa, vì khi đó ② có dẫu ngược lại, các ô lẻ là các ô có chi phí cao hơn, dẫn đến 훼 =
min { 푖푗} = 푖 푗 = 0, nghĩa là việc phá vỡ chu trình không giảm bớt được (푖,푗)∈ 1 1 lượng làng ở các ô có chi phí cao hơn. e. Khi phương án không thoái hóa có Δ푖푗 > 0 thì theo như điểm d nêu trên, việc điều chỉnh luôn có hiệu quả. Điều đó có nghĩa là khi có Δ푖푗 > 0 thì phương án đó chưa là tối ưu, hay nói một cách khác điều kiện ∀Δ푖푗 > 0 là cần và đủ để phương án không thoái hóa là tối ưu (đã được nói tại ý nghĩa của điều kiện tối ưu) II. Với bài toán thoái hóa. Có thể có phương án cực biên có m + n – k ô sử dụng với k > 1 : a. Các thế vị được gọi là liên thông với nhau nếu biết thế vị này có thể tính được thế vị kia. Như vậy với phương án thoái hóa cực biên có m + n – k ô sử dụng, ta sẽ có k nhóm thế vị liên thông với nhau, biết một thế vị nào đó sẽ chỉ biết được các thế vị khác trong nhóm đó mà thôi. Như vậy để xác định được tất cả các thế vị, với mỗi nhóm ta cần tùy chọn 1 giá trị cho một thế vị bất kỳ trong nhóm đó và tính các thế vị còn lại. Do giá trị tùy chọn của các nhóm độc lập với nhau cho nên khi ui, vj thuộc hai nhóm liên thông khác nhau, các Δij không được xác định duy nhất mà có thể thay đổi, có thể chấp nhận bất kể giá trị âm dương nào phụ thuộc vào các tùy chọn đó. Chẳng hạn như ví dụ dưới đây, phương án là thoái hóa và ta có hai nhóm thế vị liên thông là ( 1, 푣1, 푣2, 2, 푣4) và ( 3, 푣3). Nếu cho u1 = 0, ta tính được các thế vị của nhóm thứ nhất là 푣1 = 1, 푣2 = 3, 2 = 1, 4 = −2. Để tính thế vị nhóm còn lại, ta sẽ cho u3 nhận giá trị nào đó và tính được v3. Gia số Δ22 = −1 luôn cố định không phụ thuộc vào giá trị của u1, nhưng Δ31 do liên quan tới 2 nhóm thế vị khác nhau nên chỉ có thể thay đổi tùy ý, chẳng hạn nếu muốn gia số Δ31 = 100 > 0 ta cần chọn u3 = 100; còn muốn Δ31 = −10 < 0 ta chọn u3 = -10 ! v1 = 1 v2 = 3 Bj 80 50 30 Ai 40 10 u1 = 0 50 1 3 5 40 45 u2 = 1 40 2 5 7 30 30 1 7 3 40 u4 = -2 40 3 1 2
b. Do các thế vị không liên thông với nhau, dẫn tới Δij không được xác định một cách duy nhất như đã nêu ở trên. Chẳng hạn như ở bảng trên, nếu lấu u2 = -100 thì Δ31, Δ32 đều âm, còn lấy u2 = 100 thì Δ31, Δ32 đều dương ! Vì thế ta không thể dùng chúng làm thước đo tính hợp lý của các ô không sử dụng được. Nói một cách khác, với phương án cực biên thoái hóa, với cách duy nhất tùy chọn tùy ý k thế vị ban đầu cho k nhóm liên thông khác nhau, khi một ô (i, j) nào đó có Δ푖푗 > 0 ta không thể nói ô đó là bất hợp lý và do vậy không thể nói phương án đó chưa là tối ưu ! (các gia số Δij chỉ các định một cách duy nhất nếu ui, vj thuộc cùng một nhóm liên thông, và với các ô trong cùng nhóm liên thông đó ta có thể dùng Δij làm thước đo độ hợp lý, ví dụ với bất kỳ giá trị tùy ý chọn của u1 ta luôn có Δ22 = -1, Δ41 = -4 nên hai ô (2, 2) và (4, 1) là các ô hợp lý. c. Ta có thể thấy, với phương án thoái hóa có m + n – k ô sử dụng (k < 1) sẽ tồn tại một số ô (i, j) nào đó mà khi đưa vòa làm ô sử dụng bằng cách quy 0 thì vẫn chưa tạo nên chu trình (do chưa đủ m + n ô). Điều đó nghĩa là ta sẽ có một vài phương án x’ khác, cũng cực biên và có cùng giá trị hàm mục tiêu như x. Khi đó việc điều chỉnh có thể sẽ không có hiệu quả thực sự, chúng ta có thể sẽ chỉ di chuyển trên các điểm cực biên đó, tạo nên hiệu tượng xoay vòng mà không đi đến phương án cực biên tốt nhất. Hiện tượng đó giống như khi đứng trên sân thượng của 1 ngôi nhà, ta cứ đi xung quanh các điểm góc của sân thượng đó (cũng là đỉnh nhưng có cùng độ cao với mặt sân thượng) chứ không đi lên cao hơn (chóp của ngôi nhà). Ta có thể thấy qua ví dụ sau : Các phương án ở các bảng sau đều là phương án cực biên có cùng giá trị hàm mục tiêu. Bj Bj 80 50 30 80 50 30 Ai Ai 50 40 10 50 40 10 40 40 40 40 0 30 30 30 30 40 40 40 40
Bj Bj 80 50 30 80 50 30 Ai Ai 50 40 10 0 50 40 10 40 40 40 40 30 30 30 0 30 40 40 40 40 d. Việc điều chỉnh sẽ phức tạp hơn và có thể xuất hiện hiện tượng xoay vòng : . Việc đưa thêm ô sử dụng : Ta có thể sẽ phải đưa thêm không phải 1, mà có thể 2, 3, k ô sử dụng thì mới có thể xuất hiện chu trình. Khi đó rất có thể xảy ra hiện tượng lượng điều chỉnh 훼 = min { 푖푗} = 0 nếu 1 trong 2, (푖,푗)∈ 3, ô đó thuộc vào nhóm có cước phí cao hơn, hoặc ta có chu trình mà cước phí nhóm chẵn và nhóm lẻ bằng nhau (điều không thể xảy ra với phương ái không thoái hóa và ô có Δij > 0), dẫn tới việc phá vỡ chu trình không có hiệu quả thực sự Đây chính là hiện tượng xoay vòng, ta chỉ di chuyển trên các điểm cực biên có cùng độ cao ! . Do các Δij không được xác định một cách duy nhất như trên nên có thể xảy ra khả năng phương án của ta đã tối ưu rồi mà vẫn có Δij > 0, nghĩa là ta không biết nó đã tối ưu hay chưa ! Như ở ví dụ trên , phương án đó đã là tối ưi mà nếu muốn, ta vẫn có Δij > 0 ! S D A C B
Ví dụ về hiện tượng xoay vòng được nêu ở hình vẽ trên : Từ đỉnh A, thêm 1 ô sử dụng ta có thể chỉ được phương án chưa cực biên M nằm trên mặt của đa giác ABCD. Phá vỡ chu trình, tức từ M đi tới điểm cực biên có độ cao không thua so với M, có thể ta gặp lại 1 trong các đỉnh B, C, D có cùng độ cao với A (trường hợp đơn giản nhất là M nằm trên cạnh AB và ta liên tục đi từ A B và ngược lại, như thế sẽ chẳng bao giờ leo lên đến đỉnh S). Tuy nhiên, trên thực tế hiện tượng xoay vòng hiếm khi lặp đi lặp lại một cách vĩnh cửu. Thực tế là với tất cả các ô có Δij > 0 chắc chắn tồn tại tổ hợp ô mà khi quy 0 để chúng trở thành ô sử dụng thì ở bước tiếp theo ta sẽ “đi lên” điểm cực biên cao hơn, nghĩa là thoát hỏi hiện tượng xoay vòng. Nghĩa là khi thử nhiều lần ta sẽ gặp khả năng đó, nếu biết tránh không lặp đi lặp lại các khả năng đã sử dụng từ trước. Nói một cách khác, dó số đỉnh có cùng độ cao là hữu hạn, nên nếu sử dụng một biến để nhớ các đỉnh đó, ta sẽ không lặp lại các đỉnh đó và thoát khỏi khả năng xoay vòng. Thông thường với phương án thoái hóa, khi chọn ô có Δij > 0 lớn nhất làm ô sử dụng mà vẫn chưa có chu trình thì ta có thể chọn tiếp ô khác (cho đến khi có chu trình) sao cho việc điều chỉnh nó phải thực sự hiệu quả. Các ô này có thể lấy bất kỳ, không được lấy cùng hàng hoặc cột với các ô đã chọn trước đó (để tránh 훼 = min { 푖푗} = 0). Tốt nhất lên lấy các ô có Δij > 0 (푖,푗)∈ từ lớn đến bé. Việc chọn ô nào để thêm vào cần linh hoạt và kỹ năng đó đạt được thông qua kinh nghiệm xử lý thực tế trên các bài toán cụ thể. Ví dụ : Giải bài toán vận tải cho ở mục 4. Giải : Ta lấy phương án xuất phát theo phương pháp góc Tây – Bắc. v1 = 4 v2 = 7 v3 = 4 v4 = -4 Bj 30 60 46 25 Ai u1 = 0 50 30 20 4 7 12 7 u2 = 2 70 40 30 5 9 6 1 u3 = 5 41 16 25 8 2 9 1
Bước lặp 1 : Không cần phá vỡ chu trình do phương án không có chu trình Tìm các thế vị 1 = 0 푣1 = 11 − 1 = 4 − 0 = 4 푣2 = 12 − 1 = 7 − 0 = 7 2 = 22 − 푣2 = 9 − 7 = 2 푣3 = 23 − 2 = 6 − 2 = 4 3 = 33 − 푣3 = 9 − 4 = 5 푣4 = 34 − 3 = 1 − 5 = −4 Tìm Δij với mọ (푖, 푗) ∉ : Δ13 = 0 + 4 − 12 = −8 0 21 Δ24 = 2 + (−4) − 1 = −3 0 Δ13 = 5 + 7 − 2 = 10 > 0 Ta thấy Δ21, Δ31, Δ32 > 0 nên phương án x chưa là phương án tối ưu. Trong các giá trị đó Δ32 lớn nhất nên có vẻ ô (3, 2) là bất hợp lý nhất (cước phí của nó chỉ là 2 mà lại không phân hàng cho nó, trong khi ô (3, 3) có cước phí cao lại được phần hàng nhiều !). Do vậy ta điều chỉnh ô đó bằng cách đưa nó vào làm ô sử dụng x32 = 0 và chuyển tới bước lặp 2. Bước lặp 2 : Do (3, 2) bây giờ là ô sử dụng nên ta có chu trình : (3,2), (3,3), (2,3), (2,2) Trong đó :  KOdd có tổng cước phí Odd = 2 + 6 = 8  KEven có tổng cước phí Even = 9 + 9 = 19 Tổng cước phí tính theo một đơn vị hàng hóa tại các ô chẵn đắt hơn so với các ô lẻ 10 đơn vị nên ta sẽ tìm cách chuyển hàng từ ô chẵn sang ô lẻ lượng hàng tương ứng với 훼 = 푖푛{ 푖푗: (푖, 푗) ∈ 퐾 푣푒푛} = 33 = 16 Thực hiện việc phá vỡ chu trình bằng cách tăng hàng cho các ô lẻ thêm 16 , bớt các ô chẵn 16 (như vậy ta sẽ giảm cước phí đi 16 × 10 = 160 đơn vị) ta được phương án mới sau (trang bên): Tính các thế vị : 1 = 0 푣1 = 11 − 1 = 4 − 0 = 4 푣2 = 22 − 1 = 7 − 0 = 7
2 = 22 − 푣2 = 9 − 7 = 2 푣 = − = 6 − 2 = 4 3 23 2 3 = 32 − 푣2 = 2 − 7 = −5 푣4 = 34 − 3 = 1 − (−5) = 6 v1 = 4 v2 = 7 v3 = 4 v4 = 6 Bj 30 60 46 25 Ai u1 = 0 50 30 20 4 7 12 7 u2 = 2 70 24 46 5 9 6 1 u3 = -5 41 16 25 8 2 9 1 Tính Δij với mọi (푖, 푗) ∉ : Δ13 = 0 + 4 − 12 = −8 0 21 Δ24 = 2 + 6 − 1 = 7 > 0 Δ31 = −5 + 4 − 8 = −9 0 nên phương án trên vẫn chưa là tối ưu. Trong các giá trị đó Δ24 là lớn nhât nên ô (2, 4) là bất hợp lý nhất. Ta tiếp tục điều chỉnh ô đó bằng các đưa nó vào làm ô sử dụng, cho x24 = 0 và chuyển tới bước lặp 3. Bước lặp 3 : Do (2, 4) bây giờ là ô sử dụng nên ta có chu trình : (2,4), (2,2), (3,2), (3,4) Trong đó :  KOdd có tổng chi phí Odd = 1 + 2 = 3  KEven có tổng chi phí Even = 9 + 1 = 10 Nhóm các ô chẵn đắt hơn nhiều so với các ô lẻ nên ta tìm cách chuyển hàng từ các ô chẵn sang các ô lẻ một lượng tương ứng 훼 = 푖푛{ 푖푗: (푖, 푗) ∈ 퐾 푣푒푛} = 24 = 24 Thực hiện việc phá vỡ chu trình bằng cách tăng thêm các ô lẻ 24, bớt các ô chẵn 24 ( và giảm được 24 × 7 = 168 đơn vị cước phí) ta được phương án mới như sau :
v1 = 4 v2 = 7 v3 = 11 v4 = 6 Bj 30 60 46 25 Ai u1 = 0 50 30 20 4 7 12 7 u2 = -5 70 46 24 5 9 6 1 u3 = -5 41 40 1 8 2 9 1 Ta tính toán các thế vị từ đó ta thu được ∀훥푖푗 ≤ 0, vậy X là phương án tối ưu với ( ) = 641 là giá trị cước phí tối ưu (trên thực tế, từ phương án ban đầu với cước phí 969, sau 2 lần cải tiến chúng ta thu nhận được phương án tối ưu với cước phí giảm đi 160 + 168 = 328 đơn vị). Ta có thể thấy rằng phương án xuất phát góc Tây – Bắc không quan tâm tới cước phí cho nên chắc là có nhiều bất hợp lý hơn so với phương án cực tiểu theo bảng. Ta thử lấy phương án xuất phát theo phương pháp cực tiểu chi phí theo bảng xem sao. Ta có phương án xuất phát: v1 = 4 v2 = 7 v3 = 12 v4 = 7 Bj 30 60 46 25 Ai u1 = 0 50 30 19 1 4 7 12 7 u2 = -6 70 45 25 5 9 6 1 u3 = -5 41 41 8 2 9 1 Bước lặp 1: Không phá vỡ chu trình Tìm các thế vị = 0 1 푣1 = 11 − 1 = 4 − 0 = 4
푣2 = 12 − 1 = 7 − 0 = 7 푣3 = 13 − 1 = 12 − 0 = 12 2 = 23 − 푣3 = 6 − 12 = −6 푣4 = 24 − 2 = 1 + 6 = 7 3 = 32 − 푣2 = 2 − 7 = −5 Tính Δij với ∀(푖, 푗) ∉ : Δ14 = 0 + 7 − 7 = 0 Δ21 = −6 + 4 − 5 = −7 0 Ta có Δ34 > 0 nên phương án X chưa tối ưu. Đưa ô (3, 4) vào làm ô sử dụng bằng cách cho x34 = 0 và chuyển tới bước lặp 2. Bước lặp 2: Do (3, 4) bay giờ là ô sử dụng nên ta có chu trình: (3,4), (3,2), (1,2), (1,3), (2,3), (2,4) Trong đó:  KOdd có tổng cước phí Odd = 1 + 7 + 6 =14  KEven có tổng cước phí Even = 2 + 12 + 1 = 15 > Odd  훼 = 푖푛{ 푖푗: (푖, 푗) ∈ 퐾 푣푒푛} = 13 = 1 Như vậy ta sẽ thực hiện việc phá vỡ chu trình bằng cách tăng vào các ô lẻ thêm 1, bớt các ô chẵn 1 và được phương án mới như sau: v1 = 4 v2 = 7 v3 = 11 v4 = 6 Bj 30 60 46 25 Ai u1 = 0 50 30 19 4 7 12 7 u2 = -5 70 46 24 5 9 6 1 u3 = -5 41 40 1 8 2 9 1 Tính các thế vị: = 0 1 푣1 = 11 − 1 = 4 − 0 = 4
푣2 = 12 − 1 = 7 − 0 = 7 3 = 32 − 푣2 = 2 − 7 = −5 푣4 = 34 − 3 = 1 − (−5) = 6 2 = 24 − 푣4 = 1 − 6 = −5 푣3 = 23 − 2 = 6 − (−5) = 11 Tính Δij với ∀(푖, 푗) ∉ : Δ13 = 0 + (−5) − 12 = −17 < 0 Δ14 = 0 + 6 − 7 = −1 < 0 Δ = −5 + 4 − 5 = −6 < 0 21 Δ22 = −5 + 7 − 9 = −7 < 0 Δ31 = −5 + 4 − 8 = −9 < 0 Δ33 = −5 + 11 − 9 = −3 < 0 ∀훥푖푗 ≤ 0, vậy X là phương án tối ưu và ( ) = 641 là giá trị cước phí tối ưu. Cách này ta chỉ cần 2 bước lặp, trong khi cách giải trước cần đến 3 bước lặp mới cho kết quả cuối cùng. Nhận xét về các tính toán với các ví dụ cụ thể: a. Mỗi bước, chúng ta lại giảm bớt cước phí được một lượng bằng 훼|퐾 − 퐾 푣푒푛|. Vậy nếu xuất phát từ phương án góc Tây – Bắc với cước phí ban đầu ( ) = 696 trong khi cước phí tối ưu là 641, vậy để giảm bớt được 328 đơn vị cước phí chắc ta phải mất nhiều bước lặp thì ta mới tới được phương án tối ưu trên. Do đó nên tìm phương án xuất phát bằng phương pháp cực tiểu cước phí để ngay từ đầu đã có phương án xuất phát rất gần với phương án tối ưu (có giá trị cước phí bé, khá gần với cước phí tối ưu rồi), sẽ giảm bớt khối lượng tính toán rất nhiều. b. Tại một thời điểm nào đó, ta có 1 phương án chưa tối ưu thì luôn có thể xem nó là phương án xuất phát vậy chỉ cần kiểm tra nó có là phương án chấp nhận được hay không, bỏ qua các phương án trước đó có đúng, có chính xác hay không. Nói một cách khác, khi kiểm tra tính đúng/sai của bài làm, ta chỉ cần kiểm tra các số liệu tính toán của bước cuối cùng là được. c. Nếu ta luôn gặp phương án không thoái hóa (tức số các thành phần cơ sở khác 0 của nó bằng m + n – 1 và do vậy số các ô sử dụng khi đó sẽ là m + n – 1) thì việc phá vỡ chu trình luôn đưa tới phương án cực biên tốt hơn và thuật toán trên sẽ đi tới phương án cực biên tối ưu sau một số hữu hạn bược. d. Việc đưa thêm một ô sử dụng bằng 0, chẳng qua là làm cho số ô sử dụng đạt mức bằng m + n để phương án trở thành không cực biên. Thực tế đây là việc từ một phương án cực biên ta chuyển tới một phương án không cực biên có cùng độ cao, hay tương tự việc từ một đỉnh núi “bay ngang” sang một điểm trên sườn núi khác có cùng độ cao
mà thôi. Khi sang sườn núi này, ta lại tiếp tục leo lên đỉnh của ngọn núi tiếp theo đó (bằng cách phá vỡ chu trình). e. Khi tồn tại hệ thế vị mà 훥푖푗 ≤ 0 ∀(푖, 푗) thì phương án là tối ưu. Nhưng khi ∃훥푖푗 > 0 thì sẽ như thế nào? Ta xét cụ thể hai trường hợp sau: . Phương án là không thoái hóa: Có thể điều chỉnh thực sự hiệu quả phương án đó, nghĩa là chắc chắn phương án đó là chưa tối ưu. Nói cách khác, điều kiện 훥푖푗 ≤ 0 với mọi ô không sử dụng (i, j) là cần và đủ để phương án là tối ưu. . Với phương án cực biên thoái hóa, có m + n – k (với k > 1) ô sử dụng: Thực tế bài toán thoái hóa là bài toán mà ta có 2 điểm cực biên có cùng độ cao, và do vậy mà sẽ xuất hiện hiện tượng xoay voàng. Cũng có thể 2 điểm đó đã là 2 đỉnh cao nhất rồi, nghĩa là cả 2 phương án đó đều là phương án tối ưu. Tuy nhiên như đã nêu ở nhận xét B.a và B.b, phương án thoái hóa có thể đã là phương án tối ưu, nhưng có thể vẫn có Δij > 0 nếu ta lựa chọn một hệ thế vị nào đó không “may mắn”! Nghĩa là với phương án thoái hóa, điều kiện ∀Δ푖푗 ≤ 0 chỉ là đủ chứ không cần để phương án là tối ưu. Ta có thể thấy rõ điều đó qua ví dụ được trình bày dưới đây: Giả sử ta có bài toán vận tải và đã có phương án thoái hóa: v1 = 1 v2 = 3 Bj 80 50 30 Ai u1 = 0 50 40 10 1 3 5 u2 = 1 40 40 2 5 7 30 30 1 7 3 u4 = -2 40 40 3 1 2 Đây là bài toán thoái hóa, ta cần tính 7 thế vị mà chỉ có 5 phương trình tương ứng với 5 ô sử dụng, do vậy mà có thể chọn trước 2 thế vị nào đó. Lấy u1 = 0 ta dễ dàng suy ra 푣1 = 1, 푣2 = 3, 2 = 1, 4 = −2. Để tìm u3, v3 ta có thể cho u3 nhận một giá trị bất kỳ rồi từ đó suy ra giá trị của v3 và ví dụ lấy u3 = -1 ta được v3 = 4. Khi đó ∀훥푖푗 < 0, dẫn tới phương án là tối ưu.
Tuy nhiên nếu ta lấy u3 = -10, suy ra v3 = 13 và ta có Δ13 = 8 > 0, phương án trở thành không tối ưu mặc dù vẫn là phương án đó. Như vậy với một bài toán vận tải thoái hóa, có thể ta đã có phương án thoái hóa tối ưu, nhưng nếu lựa chọn hệ nghiệm của ④ không khéo, ta vẫn có thể có Δij > 0 và dễ lầm tưởng là phương án chưa tối ưu! ( lý do là tiêu chuẩn tối ưu chỉ nói tồn tại hệ thế vị ui, vj sao cho 휟풊풋 ≤ , chứ không phải với mọi hệ thế vị ui, vj nào cũng phải có 휟풊풋 ≤ , mà với bài toán thoái hóa thì giá trị của Δij lại thay đổi phụ thuộc vào cách chọn giá trị của thế vị tùy chọn của các nhóm liên thông khác nhau). Chính xác hơn trong điều kiện bài toán thoái hóa, rất có thể chúng ta đã có phương án tối ưu mà do Δij xác định không duy nhất nên việc chọn thêm các giá trị tùy chọn của thế vị tiếp tiếp theo không thích hợp dẫn tới Δij > 0. Vấn đề đặt ra: Với phương án thoái hóa, như trong bài toán trên, nên chọn u3 thế nào để khi gặp Δij > 0 ta có thể khẳng định được phương án là tối ưu chưa? Nói một cách khác, liệu có thể chọn giá trị tùy chọn của thế vị tiếp theo như thế nào đẻ có thể coi Δij như là độ đo sự hợp lý của các ô sử dụng như với phương án không thoái hóa? Trước hết ta phải thấy là, để là độ đo, cũng như độ dài của một quãng đường AB, thì độ dài đó không phụ thuộc vào việc gốc tọa độ ở đâu mà chỉ phụ thuộc vào hiệu số của các điểm A và B mà thôi. Do vậy giá trị của Δij phải là duy nhất và không phụ thuộc vào cách tùy chọn thế vị ban đầu. Nghĩa là ta phải làm thế nào để các tùy chọn tiếp theo không được tùy ý mà phải liên thông với tùy chọn u1 ban đầu, và phải bảo đảm nếu như phương án là tối ưu thì phải có ∀훥푖푗 ≤ 0. Ta sẽ đi tìm cách chọn các tùy chọn thế vị tiếp theo của phương án thoái hóa sao cho đảm bảo được điều đó. Ta xét với một ví dụ cụ thể sau: Cho bài toán vận tải với phương án thoái hóa như sau: v1 = 1 v2 = 3 v3 = 1 v4 = 3 Bj 80 20 60 50 Ai u1 = 0 50 30 20 1 3 5 3 u2 = 1 50 50 2 5 4 5
u3 = 2 80 60 20 10 7 3 5 u3 = 1 30 30 3 6 3 4 Phương án này có 2 nhóm thế vị liên thông 1, 2, 푣1, 푣2 và 3, 4, 푣3, 푣4. Với các giá trị thế vị như trên bảng, ta có ∀Δ푖푗 ≤ 0, suy ra phương án là tối ưu. Tuy nhiên hai nhóm thế vị trên không liên thông với nhau nên các Δij thay đổi khi u1, u3 thay đổi. Ta có 훥31 = −7, 훥32 = −2, 훥41 = −1, 훥42 = −2 với 훥41 = −1 là lớn nhất trong các gia số liên quan giữa các ui của nhóm thứ nhất và vj của nhóm thứ hai. Giả sử bây giờ ta đưa ô (4,1) có gia số lớn nhất vào làm ô sử dụng, ta sẽ có phương án mới mà mọi thế vị liên thông với nhau và ∀Δij ≤ 0. v1 = 1 v2 = 3 v3 = 0 v4 = 2 Bj 80 20 60 50 Ai u1 = 0 50 30 20 1 3 5 3 u2 = 1 50 50 2 5 4 5 u3 = 3 80 60 20 10 7 3 5 u3 = 2 30 0 30 3 6 3 4 Ta có thể thấy là việc đưa ô (4, 1) (mà u4, v1 thuộc hai nhóm liên thông khác nhau) làm ô sử dụng, tương đương với việc chọn u4 = 2. Tuy nhiên việc đưa ô (4, 1) làm ô sử dụng hay hơn nhiều vì lúc đó ta được một phương án cực biên có n + m – 1 ô sử dụng, hai nhóm thế vị 1, 2, 푣1, 푣2 và 3, 4, 푣3, 푣4 khi đó liên thông với nhau thành một nhóm, mọi thế vị đều tính được chỉ từ một tùy chọn u1 ban đầu và mọi Δij được xác định duy nhất, không thay đổi khi tùy chọn ban đầu thay đổi. Quan trọng hơn, các Δij vẫn đảm bảo ≤ 0 để khẳng định được là phương án tối ưu (điều mà ta không có được nếu chọn bất kỳ ô nào trong (3, 1), (3,2), (4, 2) làm ô sử dụng, vì khi đó sẽ có Δij > 0!!).
Ta có các mệnh đề sau: Mệnh đề 1: Nếu phương án thoái hóa có (m + n – 2) ô sử dụng là tối ưu thì luôn tồn tại tổ hợp một ô không sử dụng mà khi đưa nó vào làm ô sử dụng thì ta có phương án cực biên có n + m – 1 ô sử dụng với mọi thế vị liên thông với nhau và ∀훥푖푗 ≤ 0. Chứng minh: Như vậy phương án cực biên tối ưu thoái hóa trên sẽ có 2 nhóm thế vị liên thông, có n + m – 2 ô sử dụng. Không mất tính tổng quát, bằng cách đánh số lại, ta có 2 nhóm thế vị liên thông đó là 1, 2, , 푣1, 푣2, 푣푙 và +1, +2, 푛, 푣푙+1, 푣푙+2, 푣 . Nếu phương án là tối ưu, phải tồn tại một hệ thế vị 1, 2, 푛, 푣1, 푣2, 푣 sao cho 훥푖푗 ≤ 0 ∀(푖, 푗). Chọn hệ ′ ′ ′ thế vị mới 푖, 푣푗 bằng cách giữ nguyên 1, 2, , 푣1, 푣2, 푣푙 (tức chọn thế vị đầu tiên 1 = 1 ′ ′ và do nhóm thế vị đầu tiên liên thông nên ta sẽ có 푖 = 푖 (푖 = 1, ), 푣푗 = 푣푗 (푗 = 1, 푙). Để chọn nhóm thế vị tự do thứ hai cho nhóm thế vị liên thông thứ hai, ta lấy: ′ +1 = +1 − 휇 푣ớ푖 휇 = Δ푖0푗0 = Max Δ푖푗 ≤ 0 푖=1,푙 푗= +1,푛 Các thế vị liên quan trong nhóm liên thông thứ hai sẽ thay đổi tương ứng: ′ 푖 = 푖 − 휇 (푖 = + 1, 푛) ′ 푣푗 = 푣푗 + 휇 (푗 = 푖 + 1, 푛) Khi đó: 푖 + 푣푗 − 푖푗 = 훥푖푗 (푖 = 1, ; 푗 = 1, 푙) ′ ′ ′ 푖 + 푣푗 − 푖푗 − 휇 = 훥푖푗 − 휇 (푖 = + 1, 푛; 푗 = 1, 푙) Δ푖푗 = 푖 + 푣푗 − 푖푗 = 푖 + 푣푗 − 푖푗 + 휇 = 훥푖푗 + 휇 (푖 = 1, ; 푗 = 푙 + 1, ) { 푖 − 휇 + 푣푗 + 휇 − 푖푗 = 훥푖푗 (푖 = + 1, 푛; 푗 = 푙 + 1, ) ′ Từ cách xác định của μ, và do mọi 훥푖푗 ≤ 0 nên với hệ thế vị mới trên ta có ∀Δ푖푗 ≤ 0 (trong ′ ′ ′ ′ ′ ′ đó 훥푖0푗0 = 0). Hệ thế vị 1, 2, 푛, 푣1, 푣2, 푣푛 đó chính là tương đương với phương án x’, là x thêm ô (i0, j0) vào làm ô sử dụng vì có: Δ′ = + 푣 − − 휇 = Δ − 훥 = 0 푖0푗0 푖0 푗0 푖0푗0 푖0푗0 푖0푗0 Ta có thể nhận xét rằng, với nhóm thế vị +1, +2, 푛, 푣푙+1, 푣푙+2, 푣 khi thế vị uk+1 tăng thêm một lượng μ thì mọi Δij tại các ô không sử dụng (i, j) với 푖 = + 1, 푛; 푗 = 1, đều giảm đi một lượng μ. Do vậy mà với 휇 = Δ푖0푗0 = Max Δ푖푗 ≤ 0 ta có ∀Δ푖푗 ≥ 0, riêng Δ푖0푗0 = 0. Điều 푖=1,푙 푗= +1,푛 đó có nghĩa ô (i0, j0) là ô đáng phải đưa vào làm ô sử dụng nhất (có lý nhất) trong các ô đó (tương tự, tồn tại ô như vậy với 푖 = 1, ; 푗 = 푙 + 1, ). Mệnh đề 1 tương đương với mệnh đề 2 sau:
Mệnh đề 2: Với phương án thoái hóa có m + n – 2 ô sử dụng, với hệ thế vị được xác định ( ) như ở mệnh đề 1 (đưa ô 푖0, 푗0 : 휇 = Δ푖0푗0 = Max Δ푖푗 ≤ 0 vào làm ô sử dụng), nếu ta có một 푖=1,푙 푗= +1,푛 ′ 훥푖푗 > 0 thì phương án x chưa tối ưu. Chứng minh: Giả sử điều đó là sai, vậy phương án x đã là tối ưu. Mà nếu x tối ưu thì ∀훥푖푗 ≤ ′ 0, mâu thuẫn với giả thiết. Vậy nếu tồn tại 훥푖푗 > 0 thì phương án x chưa là tối ưu ′ Như vậy, việc chọn +1 = +1 − 휇 như trên, tương đương với việc đưa ô (푖0, 푗0) vào làm ô sử dụng làm cho hai nhóm thế vị 1, 2, , 푣1, 푣2, 푣푙 và +1, +2, 푛, 푣푙+1, 푣푙+2, 푣 liên thông với nhau, dẫn tới các gia số Δij được xác địnhkhông phụ thuộc vào tùy chọn của ul và uk . Nói một cách khác, với cách thêm ô (i0, j0) như trên vào làm ô sử dụng để tính thế vị, ta được ′ một phương án mới có cực biên với n + m – 1 ô sử dụng , mà khi đó gia số 훥푖푗 được xem là tiêu ′ chí đánh giá sự hợp lý như trường hợp phương án không thoái hóa: Nếu ∀훥푖푗 ≤ 0 thì phương ′ án đó là tối ưu, nếu tồn tại 훥푖푗 > 0 thì phương án đó chưa tối ưu. Như vậy, với phương án thoái hóa có 2 nhóm thế vị liên thông, để tính các thế vị, đầu tiên ta nên tiến hành với nhóm liên thông thứ nhất với giá trị tùy chọn u1 ban đầu. Với nhóm thế vị ′ đó nếu có 훥푖푗 > 0 thì phương án đó chưa tối ưu. Ngược lại chuyển sang nhóm liên thông tiếp theo, tạm thời cho thế bị bất kỳ ui trong nhóm đó nhận 1 giá trị tùy ý, tính các thế vị trong nhóm và tính gia số Δij của các ui của nhóm này với các vj của nhóm trước. Sau đó chọn ô có Δij lớn nhất làm ô sử dụng để 2 nhóm trở thành liên thông và tính lại các thế vị của nhóm thứ hai, dựa vào tùy chọn u1 và quay trở lại việc kiểm tra Δij > 0. Tóm lại, với cách chọn các ô để đưa vào sử dụng như vậy, từ một phương án cực biên thoái hóa, ta có được một phương án không thoái hóa có giá trị hàm mục tiêu tương đương mà các thế vị hoàn toàn liên thông với nhau. Khi đó các Δij được xác định một cách duy nhất không phụ thuộc tùy chọn thế vị ban đầu và đóng vai trò tham số chỉ sự hợp lý để có thể kiểm định, liệu phương án đã tối ưu hay chưa? Khi đó hoặc ∀훥푖푗 ≤ 0 thì phương án là tối ưu, hoặc ngược lại nếu ∃훥푖푗 > 0 thì phương án chưa tối ưu. Cách làm trên chỉ sử dụng được cho phương án thoái hóa có m + n – 2 ô sử dụng, với 2 nhóm thế vị liên thông. Trong trường hợp số nhóm thế vị liên thông nhiều hơn, ta chưa có thuật toán hữu hiệu để xử lý hiện tượng xoay vòng. BÀI 6. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT Ta xét bài toán vận tải khi: 푛 ∑ 푖 ≠ ∑ 푗 푖=1 푗=1
Ta có hai trường hợp cụ thể sau: 1. Số hàng trong kho nhiều hơn số yêu cầu: 푛 ∑ 푖 > ∑ 푗 푖=1 푗=1 Ta đưa vào thêm một cửa hàng ảo Bm + 1 với yêu cầu: 푛 +1 = ∑ 푖 − ∑ 푗 푣à 푖( +1) = 0 ∀푖 푖=1 푗=1 Ta có bài toán vận tải cân bằng thu phát với xi(m+1) là lượng hàng giữ lại ở kho hàng Ai không chuyển cho cửa hàng nào cả (nên cước phí bằng 0). 2. Khi hàng khan hiếm, các kho hàng không đáp ứng đủ nhu cầu của các cửa hàng: 푛 ∑ 푖 0. Chứng minh rằng điều chỉnh ô (i, j) đó (bao gồm việc đưa nó vào làm ô sử dụng và phá vỡ chu trình nếu có) chắc chắn sẽ dẫn tới một phương án x’ có ( ′) 0. 6. Chứng minh rằng với bài toán thoái hóa, ta luôn đi tới phương án cực biên tối ưu sau một số hữu hạn bước. 7. Giải các bài toán vận tải sau:
a. ( ) = (50,70,40,60) ( ) = (80,30,50,60) 2 3 4 2 3 4 5 2 = [ ] 4 3 2 4 3 4 2 2 b. ( ) = (50,20,20) ( ) = (15,20,25,30) 1 3 4 2 = [1 2 1 3] 4 3 1 2 c. ( ) = (30,40,50,60) ( ) = (50,60,70) 4 1 2 2 1 5 = [ ] 1 6 1 2 4 3 Đáp án: Min ( ) = 330 d. ( ) = (35,25,20,40) ( ) = (60,20,40) 4 1 2 2 1 5 = [ ] 1 6 1 2 4 3 Đáp án: Min ( ) = 290 e. ( ) = (80,70,50) ( ) = (30,40,60,70) 4 3 2 1 = [1 2 1 3] 2 1 2 3 Đáp án: Min ( ) = 220 f. ( ) = (40,50,60) ( ) = (20,30,40,10,50) 3 4 2 1 5 = [2 1 4 3 2] 3 4 3 2 1 Đáp án: Min ( ) = 220
g. ( ) = (30,40,50,60) ( ) = (100,20,60) 2 1 2 4 1 3 = [ ] 3 2 1 4 2 2 Đáp án: Min ( ) = 390 h. ( ) = (35,65,50) ( ) = (25,55,35,35) 2 1 3 4 = [4 3 2 5] 3 2 4 6 Đáp án: Min ( ) = 395 i. ( ) = (55,65,70,30) ( ) = (40,65,55,60) 3 2 5 4 6 4 3 5 = [ ] 5 3 4 6 4 5 5 4 Đáp án: Min ( ) = 740 j. ( ) = (30,40,70,80) ( ) = (60,50,40,70) 2 5 2 3 4 2 2 2 = [ ] 3 2 3 3 2 4 2 3 k. ( ) = (30,40,80) ( ) = (50,60,70) 3 5 7 = [2 6 4] 5 3 1 l. ( ) = (50,40,30) ( ) = (60,50,80) 3 5 6 = [7 4 5] 4 6 4
Lời giải một số bài. Chương II. 1. Bài toán cái túi có mô hình : 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푗 푗 ≤ 푗=1 { 푗 ≥ 0, 푗 ∈ ℕ (푗 = 1, 푛) Như vậy bài toán đối ngẫu sẽ là : 〈 , 〉 → 푖푛 { 푗 ≥ 푗 푗 = 1, 푛 ≥ 0 Trong đó y là mức tiền cao nhất cho 1 đơn vị dữ liệu trọng lượng hàng hóa mà tên trộm mang ra được còn 〈 , 〉 là tổng mức tiền tối đa mà tên trộm có thể được khi mạng túi tiền có trọng lượng b ra khỏi kho. Bài toán ban đầu là tên trộm muốn thu được nhiều tiền nhất, còn bài toán đối ngẫu là của chu kho muốn số tiền tối đa bị mất là ít nhất : Bài toán lập kế hoạch có mô hình : 푛 ∑ → 푗 푗 푗=1 푛 ∑ 푖푗 푗 ≤ 푖 (푖 = 1, ) 푗=1 { 푗 ≥ 0 (푗 = 1, 푛) Như vậy bài toán đối ngẫu sẽ là : ∑ → 푖푛 푖 푗 푖=1 ∑ 푖푗 푗 ≥ 푖 (푗 = 1, 푛) 푖=1 { 푗 ≥ 0 (푖 = 1, )
Ta xét ví dụ thực tế sau : Trong kho của nhà máy đóng tàu A có ông sắt, thép tấm và gỗ với số lượng 1, 2, 3. Từ số nguyên vật liệu đó, nhà máy có thể sản xuất ra xà lan hoặc tàu chở hàng với các nhu cầu về nguyên vật liệu khác nhau, bán với giá khác nhau 1, 2. Hãy lập kế hoạch sản xuất xà lan, tàu chở hàng sao cho tổng doanh thu cao nhất ? Bài toán lập kế hoạch là : ( ) = + → 1 1 1 2 2 11 1 + 12 2 ≤ 1 (푃) = 21 1 + 22 2 ≤ 2 31 1 + 32 2 ≤ 3 { 1, 2 ≥ 0 Trong đó : x1 – số xà lan, x2 – số tàu hàng cần sản xuất. c1 – giá xà lan, c2 – giá tàu chở hàng (mà nhà máy A định bán) Để sản xuất được 1 xà lan, cần a11 ống sắt, a21 thép tấm và a31 gỗ. Để sản xuất được 1 tàu, cần a12 ống sắt, a22 thép tấm và a32 gỗ. Bài toán đối ngẫu là : 2( ) = 1 1 + 2 2 + 3 3 → 푖푛 + + ≥ (푃′) { 11 1 12 2 13 3 1 21 1 + 22 2 + 23 3 ≥ 2 1, 2 ≥ 0 Trong đó : P’ là bài toán của một nhà kinh doanh B, muốn mua lại toàn bộ sản phẩm của nhà máy (được sản xuất từ số nguyên liệu kia). Nhà kinh doanh không quan tâm tới giá cả cụ thể của từng loại mà muốn giả tiền cả lô, chỉ cần biết là tàu và xà lan được sản xuất với đúng số thép, gỗ như thiết kế. Nhẩm tính giá cả, nhà kinh doanh B giả định 1, 2, 3 là mức giá thành phẩm chung của 1 đơn vị sắt, thép, gỗ (vừa tiền vốn nguyên vật liệu lẫn công sản xuất) sử dụng trong việc chế tạo xà lan, tàu hàng như vậy sẽ là mức giá tối thiểu (theo đánh giá của nhà kinh doanh) sử dụng trong việc chế tạo xà lan, tàu hàng như vậy sẽ là mức giá tối thiểu (theo đánh giá của nhà kinh hoanh) để có thể sản xuất được 1 cái xà lan, c2 – giá tối thiểu tàu hàng, ví dụ 11 1 + 12 2 + 13 3 là số sắt nhân với giá trị của sắt (đã kể công cả gia công), cộng với số thép nhân với giá thép, cộng với gỗ nhân với giá gỗ thì sẽ ra giá của xà lan tối thiểu theo đánh giá của nhà kinh doanh.
Vì nghĩ là nhà máy A sản xuất hết nguyên vật liệu cho nên thay vì trả tiền theo 1( ) = 1 1 + 2 2, B sẽ trả cho A số tiền 2( ) = 1 1 + 2 2 + 3 3. Tóm lại là thay vì trả giá cho từng loại hàng hóa, B trả tiền cho cả lô hàng gồm nhiều chủng loại hàng khác nhau. Hiển nhiên B chỉ có thể trả giá như vậy khi đã nhẩm tính được giá trị hàng hóa sau khi có được các ước lượng về khối lượng nguyên vật liệu và giá cả từng loại đó kể cả tiền công sản xuất, và B mong muốn mức giá 2( ) là bé nhất có thể. Chương III. 2. Với phương án thoái hóa, ta sẽ có m + n – k ô sử dụng (k > 1). Do vậy mà chắc chắn ta sẽ tìm được 1 ô (i, j) mà khi thêm nó vào làm ô sử dụng xij = 0 thì số ô sử dụng vẫn không quá m + n – 1 và vẫn không có chu trình, tức phương án đó vẫn là phương án cực biên mà hàm mục tiêu vẫn không thay đổi. 3. Do bài toán không thoái hóa nên với bất kỳ phương án cực biên nào ta cũng không có phương án cực biên có cùng độ cao với nó, nghĩa là quá trình leo lên của ta thực sử đi lên cao hơn, vậy chắc chắn cuối cùng ta phải lên tới đỉnh ??? 4. Với bài toán không thoái hóa, Δij không đổi dù ta chọn u1 ban đầu như thế nào. Do vậy khi phương án là tối ưu, ta phải có Δ푖푗 ≤ 0.