ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA BÁO CÁO BÀI TẬP LỚN Môn: PHƯƠNG PHÁP ĐỊNH LƯỢNG Đề tài : MỘT SỐ BÀI TOÁN ĐẶC BIỆT CÓ LIÊN QUAN ĐẾN QUY HOẠCH TUYẾN TÍNH GVHD: Ths. Võ Thị Ngọc Trân Lớp: L04 – HK232 STT Họ và Tên MSSV Mức độ hoàn thành 1 Nguyễn Tất Phú 2212591 100% Ngô Tấn Tiền 2213479 100% 2 Nguyễn Anh Nhân 2212360 100% 3 Phan Thị Kim Chi 2210372 100% 4 Trương Thị Kim Ngọc 2212277 100% 5 Ngô Hồng Ánh 2210160 100% 6 Võ Gia Lạc 2211805 100% 7 TP.Hồ Chí Minh, T4/2024 MỤC LỤC Phần 1. BÀI TOÁN VẬN TẢI .1 Bài toán vận tải: .2 Giải bài toán vận tải bằng phương pháp chi phí bé nhất .3 Tìm nghiệm tối ưu của bài toán vận tải .2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro.
BÀI TOÁN PHÂN CÔNG .1 Bài toán phân công .2 Giải bài toán phân công bằng phương pháp Hungarian .2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro. BÀI TOÁN DÒNG CHẢY TỐI ĐA .1 Bài toán dòng chảy tối đa .2 Giải bài toán bằng thuật gán nhãn Ford-Fulkerson .2 Xây dựng mô hình và giải bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro. 53 TÀI LIỆU THAM KHẢO. BÀI TOÁN VẬN TẢI 1.1 Bài toán vận tải: Giả sử có m điểm cung cấp hàng và n điểm tiêu thụ hàng.
Khả năng cung cấp tối đa của điểm cung cấp thứ cấp i (i=1, 2,. Nhu cầu tối thiểu của điểm tiêu thụ thứ j (j=1, 2,. Giả sử rằng khả năng vận chuyển trên mọi tuyến đường nối liền các điểm cung cấp và điểm tiêu thụ là vô hạn và chi phí vận chuyển một đơn vị sản phẩm từ điểm cung cấp i đến điểm tiêu thụ j là cij. Xác định kế hoạch vận chuyển hàng hóa sao cho chi phí vận chuyển là thấp nhất., n) là lượng hàng vận chuyển từ điểm cung cấp i đến điểm tiêu thụ j.
Bài toán tối ưu được thiết lập như sau: m n Hàm mục tiêu: Minimize chi phí Z= cij xij i =1 j =1 Các ràng buộc: +Lượng hàng vận chuyển từ một điểm cung cấp không thể vượt quá khả năng tối đa của nó: 1 n x s i =1 ij i i=1, 2, .,m +Lượng hàng vận chuyển đến một điểm tiêu thụ phải thỏa mãn nhu cầu tại điểm tiêu thụ đó: m x s i =1 ij i j=1, 2, .,m +Ràng buộc về vùng giá trị của biến: Xij ≥0 i=1, 2, .,m Bài toán trên có (m+n) ràng buộc chính, (m×n) biến quyết định và có thể biểu diễn tóm tắt như sau: m n Min Z= cij xij i =1 j =1 n s.,m Lưu ý: Điều kiện bài toán vận tải chỉ có vùng nghiệm khả dĩ khi tổng lượng cung cấp m n không nhỏ hơn tổng lượng cung yêu cầu: si d j i =1 j =1 1.2 Giải bài toán vận tải bằng phương pháp chi phí bé nhất -Ô ứng với chi phí vận chuyển đơn vị nhỏ nhất trong bảng vận tải sẽ được ưu tiên đáp ứng tối đa. -Loại bỏ điểm nguồn đã hết khả năng hoặc điểm đích đã được cung cấp đủ cùng các ô liên quan và xác định lại ô có chi phí nhỏ nhất. -Thực hiện lặp lại hai bước trên cho đến khi toàn bộ nhu cầu đã được thỏa mãn.3 Tìm nghiệm tối ưu của bài toán vận tải Bước 1: Tính toán chỉ số cải tiến Iij cho tất cả các ô rỗng (i,j) trong bảng vận tải. Chỉ số này được tính như sau: +Ứng với mỗi ô rống (i,j) nào đó, vẽ một đường đi kín nối ô này với các ô có gán giá trị trong bảng vận tải bằng các đoạn nằm ngang hoặc thẳng đứng.
+Gán dấu cho các đỉnh của đường đi vẽ trong phần trên sao cho 2 đỉnh thuộc cùng một đoạn có dấu khác nhau, bắt đầu bằng dấu cộng cho ô rỗng nhận xét. + Tính toán chỉ số cải tiến Iij cho ô đang xét. Chỉ số này bằng tổng đại số chi phí vận chuyển của các ô liên quan đến đường đi tương ứng với dấu là dấu được gán trong b. Bước 2: Nếu chỉ sô Iij của mỗi ô rỗng đều có giá trị không âm, lời giải trên là tối ưu.
Nếu tồn tại một số giá trị Iij âm, chọn ra ô có Iij nhỏ nhất và điều chỉnh lượng hàng vận chuyển trên các ô liên quan như sau: 𝑚𝑖𝑛 +Xác định giá trị nhỏ nhất 𝑥𝑖𝑗 trong các ô được gán dấu trừ. 𝑚𝑖𝑛 +Lượng hàng vận chuyển trên các ô được gán dấu trừ sẽ trừ đi một lượng 𝑥𝑖𝑗. +Lượng hàng vận chuyển trên các ô được gán dấu cộng sẽ được cộng thêm một 𝑚𝑖𝑛 lượng 𝑥𝑖𝑗. Bước 3: Xác định lại bảng vận tải và quay trở lại bước 1.1 Bài toán 1 Bài 3 trang 454, Chapter 10, Sách Quantitative Methods for Business, 12th ed Công ty Cơ sở Hạ tầng Tri-County, Inc., cung cấp khí đốt tự nhiên cho khách hàng trong khu vực ba quận.
Công ty mua khí đốt tự nhiên từ hai công ty: Southern Gas và Northwest Gas. Dự báo nhu cầu cho mùa đông sắp tới như sau: Quận Hamilton 400 đơn vị; Quận Butler 200 đơn vị; và Quận Clermont 300 đơn vị; Hợp đồng cung cấp theo như sau: Southern Gas cung cấp 500 đơn vị, và Northwest Gas, 400 đơn vị. Chi phí phân phối cho các 3 quận thay đổi tùy theo vị trí của các nhà cung cấp. Chi phí phân phối trên mỗi đơn vị (tính bằng nghìn đô la) như sau: Từ/Đến Hamilton Butler Clermont Southern Gas 10 20 15 Northwest Gas 12 15 18 a.
Hãy phát triển một biểu đồ mạng lưới đại diện cho bài toán này. Phát triển một mô hình quy hoạch tuyến tính có thể được sử dụng để xác định kế hoạch nhằm giảm thiểu tổng chi phí phân phối. Mô tả kế hoạch phân phối và tính toán tổng chi phí phân phối. Sự tăng trưởng dân số và công nghiệp gần đây ở Quận Butler có khả năng tăng thêm nhu cầu lên đến 100 đơn vị.
Nhà cung cấp nào mà Công ty Tri-County nên ký hợp đồng để cung cấp thêm khả năng phân phối này? 1.2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống Câu a) 4 Câu b) *Mô hình hóa bài toán i = 1, 2 với 1 = Southern Gas, 2 = Northwest Gas j = 1, 2, 3 với 1 = Hamilton, 2 = Butler, 3 = Clermont xij: Lượng hàng chuyên chở từ điểm nguồn i đến điểm đích j Hàm mục tiêu: Minimize 𝑍 = 10x11 + 20x12 + 15x13 + 12x21 + 15x22 + 18x23 Ràng buộc hàm: Nguồn cung: 𝑥11 + 𝑥12 + 𝑥13 ≤ 500 𝑥21 + 𝑥22 + 𝑥23 ≤ 400 Nhu cầu: 𝑥11 + 𝑥21 = 400 𝑥12 + 𝑥22 = 200 𝑥13 + 𝑥23 = 300 Ràng buộc biến: 𝑥𝑖𝑗 ≥ 0 i=1, 2; j=1, 2, 3 Câu c) Giải bằng phương pháp chi phí bé nhất ta được lời giải ban đầu Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Trước tiên ô (1,1) được xét do ô có chi phí thấp nhất, giá trị phân phối được gán cho ô này với bằng với nhu cầu của Hamilon là 400. Sau khi gán giá trị cho ô (1,1), khu vực Hamilton không còn nhu cầu nên ô (2,1) sẽ không được xem xét tiếp. 5 Ô có chi phí thấp nhất kế tiếp là ô (1,3) và (2,2): giá trị cung cấp tối đa được gán cho 2 ô này là 100 và 200 nên ô (2,2) được ưu tiên gán giá trị 200 trước. Sau khi gán, khu vực Butler đã được cung cấp đủ nhu cầu nên ô (1,2) sẽ bị loại bỏ trong bước tiếp theo Trong 2 ô còn lại là (1,3) và (2,3), các giá trị của lượng hàng duy nhất có thể gán được là 100 và 200 Sau khi ta được bảng lời giải ban đầu, ta tiếp tục thực hiện bước cải thiện nghiệm ban đầu cho đến khi đạt được điều kiện tối ưu Xét ô (1,2): đường đi ứng với ô (1,2) được trình bày như trong hình vẽ ở bảng : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Chỉ số cải tiến ứng với ô (1,2) là : I12 = +20 – 15 +18 -15 = 8 => Thỏa điều kiện tối ưu Xét ô (2,1): đường đi ứng với ô (2,1) được trình bày như trong hình vẽ ở bảng : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 6 I21 = +12 -10 +15 -18 = -1 => Chưa thỏa điều kiện tối ưu Như vậy ô (2,1) là ô rỗng duy nhất mà tại đó điều kiện tối ưu bị vi phạm.
Việc cải tiến nghiệm được thực hiện như sau: 𝑚𝑖𝑛 Ta có : 𝑥21 = 𝑚𝑖𝑛(400,200) = 200 Do vậy, các giá trị gán mới tại các ô là: 𝑥11 = 400 − 200 = 200 𝑥23 = 200 − 200 = 0 𝑥13 = 100 + 200 = 300 𝑥21 = 0 + 200 = 200 Bảng vận tải sau điều chỉnh có dạng sau : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 200 300 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Kiểm tra chỉ số cải tiến tại ô (1,2) ta được 𝐼12 = 7 => Thỏa điều kiện tối ưu Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 200 300 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 7 Tương tự tại ô (2,3) ta được 𝐼23 = 1=> thỏa điều kiện tối ưu Như vậy kết quả này là kết quả cuối cùng của bài toán Số lượng Chi phí Southern Gas – Hamilto 200 2000 Southern Gas – Clermon 300 4500 Northwest Gas – Hamilto 200 2400 Northwest Gas – Butle 200 3000 Tổng chi phí $11900 Câu d) Để giải quyết bài toán này, ta tăng nhu cầu ở khu vực Butler thêm 100 và tăng nguồn cung của cả 2 nhà cung cấp Southern Gas và Northwest Gas thêm 100.