Toán kinh tế: Hướng dẫn giải bài tập - Phần 2

"Toán kinh tế: Hướng dẫn giải bài tập" dùng làm tài liệu học tập, nghiên cứu cho sinh viên hệ chính quy, hệ tại chức và những thí sinh cần ôn luyện về toán kinh tế để dự tuyển hệ cao học kinh tế. Phần 2 của tài liệu gồm 3 chương sau, trình bày về: bài toán vận tải; một số bài toán ứng dụng của quy hoạch động; một số mô hình của lý thuyết điều khiển dự trữ;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Toán kinh tế: Hướng dẫn giải bài tập - Phần 2 Chương IV BÀI TOÁN VẬN TẢI §1 MÓ HÌNH TOÁN HỌC CỦA BÀI TOÁN VẬN TẢI Tìm mn sô thực 'X,)} thoả mãn các điểu kiện sau: m n Zj5LC‘JXU ~► min(max) (4.1) i=l J = 1 = 3ị,i = l,ni (4.2) j=l ỉxu =bpj = l,n (4.3) 1=1 X.Ị > 0. i = l,m; j - l.n (4.4) ỉa- =Ẻbi (4.5) 1-1 ,j = l Nhận xét Bài toán vận tải là một bài toán'quy hoạch tuyến tính dạng chính tác, vì vậy các định nghĩa , các định lý đối với bài toán quy hoạch tuyến tính đều có thê áp dụng cho bài toán vận tải và đương nhiên có thể giải nổ bàng phương pháp đơn hình. Nhưng do cấu tạo đặc biệt của bài toán vận tải, người ta đã xây dựng một số phương pháp khác đê giải nó đơn giản và tiện lợi hơn. Ta có thể mô tả bài toán vận tải dưói dạng bản như sau: Ta xây dựng một bảng gồm m hàng, n cột. Mỗi hàng đặc trưng cho một trạm phát, còn mỗi cột đặc trưng cho một trạm thu. 182 - Hàng trên cùng ghi tên các trạm thu B,và nhu cẩu b, tương ứng (i = l.w). - Cột đầu ghi tên các trạm phát A, và khả năng cung cấp a, tương ứng (i - ỉ.m ). - Trong bảng, giao của hàng i và cột j gọi là ô (i, j) - đặc trưng cho đoạn đường nối trạm phát A, tới trạm thu Bj, nên ở góc trên bên trái mỗi ô này ta ghi c,j (tính theo km hoặc cước phí vận chuyển một đơn vị hàng hoá từ trạm phát A, đến trạm thu Bj). Mỗi ô (i,j) còn tương ứng với một biến X,J (lượng hàng cần xác định để vận chuyển từ Aj đến Bj ), đồng thời tương ứng VỚI một vectơ Aị/hệ sô của biến Xịj) trong hệ ràng buộc (4.2) và (4.3). Như vậy mọi dữ liệu của bài toán vận tải đều được thể hiện trên bảng 4.1, gọi là bảng vận tải. Bảng 4.1 \^Thu B, B, B„ 1 hát (b|) (bj) (b) 1 (b„) A, (ã,) c„ c,2 Cũ c,n X,, x12 x,i x,„ A2 (a2) C21 C22 C2j C'2n X’2I x.„ x,i x2u A, (a,) cu Cl2 Cu Cịn Xi, x12 x.i Xin A,„ (a,„) c v III1 C|,|2 c Hi.l r X Xrnl ___ xm. ____________ ±1X111 Ta ký hiệu A là ma trận hệ số của các ẩn trong hệ (4.2) và (4.3), thì A có dạng: .1 11.. .1 11.. .1 11.. A= 1 1 1 1 1 1 1 1 1 Véc tơ A,J - hệ số của Xịj có thành phần thứ i và (m+j) bằng 1, còn (m + n - 2) thành phần còn lại đều bằng 0. 0 0 0 0 0 §2. CÁC TÍNH CHÁT cơ BÀN CỦA BÀI TOÁN VẬN TÀI Ngoài những tính chất chung của bài toán quy hoạch tuyến tính, bài toán vận tải còn có những tính chất riêng sau đây; Dịnh lý 4.1. Bài toán vận tải cần bằng thu phát bao giò cũng có phương án cực biên tôi ưu. 184 DỊnh lý 4.2. Ma trận hệ sô A cùa hệ ràng buộc (4.2) va (4.3) có hạng bằng (m+n-1). Nóị cách khác hệ (4.2) và (4.3) có m-ì- n- 1 ráng buộc độc lập tuyên tính. Từ đây liên hệ với phương án cực biên của bài toán quy hoạch tuyến tính ta suy ra: - Phương án cực biên của bài toán vận tải có không quá (m + n - 1) thành phấn dương. - Phương án cực biên của bài toán vận tải gọi là không suy biến nếu nó có dũng (ni+n-1) thành phần dương và gọi là suy biến nếu nó cỏ it hơn (m+n-1) thành phần dương. - Mỗi phương rán cực biên đểu ứng vơi ít nhất một cơ sở gồm (m+n-1) véctơ A„ độc lập tuyến tính. Nếu X = {x,jl là phương án cực biên không suy biến, thì chi’ có một cơ sở duy nhất, đó là hệ |A,.:Xij > OỊ gồm (m+n-l) vec tơ độc lập tuyên tính. Trò' lại bảng vận tải, ta tháy giữa các ô (1. j) và các véctơ A„ của an xi; có sự tương ứng (1-1) - O(i,j) dược gọi là ớ chọn nếu có lượng hàng phân phối x„ > (ì và gọi la ô loại nếu xh = 0. Như vậy một'phương án cực biên có không quá (m+n-1) ó chọn. - Phương án cực bièn dược gọi là không suy biến nếu nó có dũng (m+n-1) ô chọn và là suy biến nếu nó có ít hơn (m+n-1) ỏ chọn. Đê thay rỏ hơn tinh dộc lập hay phụ ihuộc của hệ véctơ |A„| gắn với sự phan bò cùa các ô tương ứng với chúng trong bảng vặn tải. ta xét hệ vec tơ: trong (16 tất ca các chi số thứ nhất (chí hàng) và các chỉ sô thứ hai (chi cột) chi xuất hiện đúng 2 lần. 185 Nếu ta nôi những ô tương ứng cúa báng vơi hệ véctơ trên bơi những đoạn nằm ngang và thang đứng, chúng ta sẽ nhận ra được một chu trình khép kín hay còn gọi là vòng. Một sô ví dụ về vòng được chỉ ra trên hình 4.1,2,3 Hình 4.1 Hình 4.2 Hình 4.3 đứng trưốc nó. đồng thòi nằm cùng cột (cùng hàng) chỉ vói một ô đứng sau nó. Từ dinh nghĩa trên ta thấy: Một hàng hoặc một cột mà vòng đi qua bao giờ cũng chỉ có hai ô thuộc vòng. Do đó tổng sô ô trên vòng là một sô chẵn và ít nhất là bôn ô. Định lý 4.3. Điêu kiện cần và đủ để một tập hợp ô đà cho có chứa vòng là hệ vec tơ {AijỊ tương ứng phụ thuộc tuyến tính. Hệ quả 4.1. Một tập hợp gồm (m+n) ô của bảng vận tải bao giò cũng chứa vòng. Hệ quả 4.2. Một phương án của bài ...