TLHT Quy hoạch tuyến tính.chuẩn [PDF]

Zitiervorschau

TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN Biên soạn: ThS. Hà Anh Dũng (chủ biên) ThS. Trần Chí Lê

TÀI LIỆU HỌC TẬP

QUY HOẠCH TUYẾN TÍNH

Hà Nội, 2019

-1-

-2-

Mục lục Lời mở đầu..............................................................................................................................5 Một số ký hiệu và chữ viết tắt...............................................................................................6 Chương I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH.......................................................7 1.1. Một số kiến thức đại số bổ trợ..................................................................................7 1.1.1. Không gian véctơ thực n – chiều Rn.....................................................................7 1.1.2. Đường thẳng, đoạn thẳng trong Rn.......................................................................7 1.1.3. Tập lồi…………………………………..………………………………………8 1.2. Khái niệm về bài toán quy hoạch tuyến tính..........................................................8 1.2.1. Các ví dụ dẫn đến bài toán quy hoạch tuyến tính….............................................8 1.2.2. Bài toán quy hoạch tuyến tính tổng quát............................................................13 1.2.3. Phép khử Gauss - Jordan....................................................................................16 1.2.4. Các tính chất của bài toán quy hoạch tuyến tính................................................19 1.3. Phương pháp đơn hình...........................................................................................19 1.3.1. Đặc điểm của tập phương án..............................................................................19 1.3.2. Giải bài toán quy hoạch tuyến tính bằng phương pháp hình học……………..20 1.3.3. Ý tưởng của phương pháp đơn hình……………………………………………20 1.3.4. Trường hợp bài toán quy hoạch tuyến tính có dạng chuẩn..…………………..21 1.3.5. Trường hợp bài toán quy hoạch tuyến tính không có dạng chuẩn…...........….28 1.4. Bài toán quy hoạch tuyến tính đối ngẫu...............................................................35 1.4.1. Khái niệm về bài toán đối ngẫu..........................................................................35 1.4.2. Quy tắc thành lập bài toán đối ngẫu...................................................................37 1.4.3. Các định lý đối ngẫu...........................................................................................40 1.4.4. Thuật toán của phương pháp đơn hình đối ngẫu................................................44 Câu hỏi thảo luận chương 1…………………………………………………………...51 BÀI TẬP CHƯƠNG I....................................................................................................52 Chương II. BÀI TOÁN VẬN TẢI......................................................................................61 2.1. Khái niệm về bài toán vận tải................................................................................61 2.1.1. Bài toán chi phí vận tải.......................................................................................61 2.1.2. Một số khái niệm cơ bản....................................................................................63 2.1.3. Các tính chất của bài toán vận tải.......................................................................63 2.1.4. Các phương pháp xây dựng phương án cực biên cho bài toán vận tải………..65 -3-

2.2. Phương pháp thế vị.................................................................................................67 2.2.1. Bài toán đối ngẫu của bài toán vận tải fmin.........................................................67 2.2.2. Thuật toán thế vị để giải bài toán vận tải cân bằng thu – phát fmin...................68 2.2.3. Bài toán vận tải không cân bằng thu - phát........................................................78 2.2.4. Giải bài toán vận tải với hàm mục tiêu fmax........................................................81 Câu hỏi thảo luận chương 2…………………...………………………………………83 BÀI TẬP CHƯƠNG II…………..…………………………………………………….84 Chương III. MÔ HÌNH SƠ ĐỒ MẠNG – PERT…………..………………..………….88 3.1. Khái niệm về sơ đồ mạng........................................................................................88 3.1.1. Ví dụ dẫn đến sơ đồ mạng..................................................................................88 3.1.2 Các khái niệm cơ bản.........................................................................................88 3.1.3. Các quy tắc thực hành lập sơ đồ mạng lưới PERT…………………………….91 3.2. Các chỉ tiêu thời gian trong sơ đồ mạng................................................................93 3.2.1. Các chỉ tiêu thời gian đối với sự kiện.................................................................93 3.2.2. Các chỉ tiêu thời gian đối với công việc.............................................................94 3.2.3. Đường Găng trên sơ đồ mạng............................................................................95 3.3. Bài toán xác định nhân lực và tài nguyên trên sơ đồ mạng................................97 3.4. Rút ngắn đường găng của sơ đồ mạng..................................................................98 Câu hỏi thảo luận chương 3…………………………………………………..…..…100 BÀI TẬP CHƯƠNG III……………………………………………………...………101 ĐÁP SỐ CỦA CÁC BÀI TẬP.....................................................................................106 Tài liệu tham khảo.......................................................................................................109

-4-

Lời mở đầu Trong những năm gần đây, toán học có rất nhiều ứng dụng trong các ngành kinh tế xã hội, quân sự, du lịch, bưu chính viễn thông, giao thông vận tải...Trong sản xuất kinh doanh ta thường gặp các tình huống cần phải đưa ra kế hoạch sản xuất như: cần phải sản xuất với số lượng bao nhiêu để đạt được doanh thu lớn nhất; hoặc với lượng vốn và tài nguyên hữu hạn thì nên đầu tư vào các ngạch nào là có hiệu quả nhất. Trong giao thông vận tải ta phải vận chuyển như thế nào sao cho chi phí vận tải là thấp nhất. Trong ngành điện lực người ta phải đặt các trạm biến áp ở những chỗ nào để tổng độ dài của đường dây điện là ngắn nhất... Để giải quyết được các vấn đề trên thì ta cần phải lập được mô hình toán học, sau đó dùng các phương pháp để giải các bài toán đó. Bài toán Quy hoạch tuyến tính là một trong các mô hình toán bao gồm hàm mục tiêu và hệ các điều kiện ràng buộc đều là các phương trình và bất phương trình tuyến tính. Bài toán quy hoạch tuyến tính đã được các nhà toán học Nga đưa ra đầu những năm 40 của thế kỷ trước. Năm 1947 nhà toán học Dantzig (Mỹ) là người đầu tiên đề xuất thuật toán đơn hình để giải bài toán quy hoạch tuyến tính. Hiện nay đã có nhiều phương pháp giải khác nhau nhưng thuật toán đơn hình vẫn là phương pháp hiệu quả tiện lợi nhất về mặt tính toán. Quy hoạch tuyến tính là môn toán ứng dụng và là môn học bắt buộc đối với sinh viên các ngành khối kinh tế của Trường Đại học Kinh tế - Kỹ thuật Công nghiệp. Để phục vụ cho việc học tập và giảng dạy môn học này, được sự phân công của đồng chí Trưởng khoa Ts. Trần Thị Hoàng Yến và được sự đóng góp ý kiến của các thầy cô Bộ môn toán - Khoa Khoa học cơ bản Trường Đại học Kinh tế - Kỹ thuật Công nghiệp chúng tôi biên soạn cuốn tài liệu học tập này. Cuốn Tài liệu học tập này gồm 3 chương và được học trong 2 tín chỉ. Chương I: Bài toán Quy hoạch tuyến tính Chương II: Bài toán vận tải Chương III: Mô hình sơ đồ mạng PERT Trong đó chương I và chương II do thạc sỹ Hà Anh Dũng biên soạn còn chương III do thạc sỹ Trần Chí Lê biên soạn. Khi viết tài liệu này chúng tôi cố gắng dùng ngôn ngữ diễn tả để người đọc dễ hiểu. Các công thức đều có đi kèm diễn giải và hướng dẫn. Các ký hiệu, viết tắt đều được Việt hóa.Vì đây là phiên bản đầu tiên nên sẽ không tránh khỏi được các sai sót, rất mong được nhận các ý kiến đóng góp của các thầy cô, sinh viên và bạn đọc. Xin chân thành cảm ơn! Hà nội, ngày 10 tháng 03 năm 2019 Các tác giả -5-

Một số ký hiệu và chữ viết tắt < X, Y > [X1, X2] AT A~B ,   

min max (G) (P) (D) │x│ QHTT CPSX CS BT BT QHTT BTVT DN đltt đvhh đpcm Đ/vị G-J GPA hpttt HSCS KSB NSLĐ PA PACB PATƯ pttt PTƯ SĐM PERT

Tích vô hướng của 2 véctơ X và Y Cạnh, đoạn thẳng X1X2 Ma trận chuyển vị của ma trận A Ma trận A tương đương ma trận B Thuộc, không thuộc Tồn tại Với mọi Giá trị nhỏ nhất Giá trị lớn nhất Bài toán gốc Bài toán phụ Bài toán đối ngẫu Giá trị tuyệt đối của x Quy hoạch tuyến tính Chi phí sản xuất Cơ sở Bài toán Bài toán quy hoạch tuyến tính Bài toán vận tải Doanh nghiệp Độc lập tuyến tính Đơn vị hàng hóa Điều phải chứng minh Đơn vị Gauss - Jordan Giả phương án Hệ phương trình tuyến tính Hệ số cơ sở Không suy biến Năng suất lao động Phương án Phương án cực biên Phương án tối ưu Phụ thuộc tuyến tính Giá trị tối ưu của P Sơ đồ mạng Program Evaluation and Review Technique

-6-

Chương I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Mục đích: Mục đích của chương này là trang bị cho người học những kiến thức cơ bản về môn Quy hoạch tuyến tính và một số phương pháp giải các bài toán quy hoạch tuyến tính. Qua đó, người học có thể mô hình toán học các bài toán trong thực tế và sử dụng các phương pháp cơ bản như phương pháp đơn hình, phương pháp đơn hình đối ngẫu, phương pháp hai pha,… để tìm lời giả cho các mô hình này. Đồng thời có thể lập được bài toán quy hoạch tuyến tính đối ngẫu và hiểu được ý nghĩa của bài toán đối ngẫu.

1.1. Một số kiến thức đại số bổ trợ 1.1.1. Không gian véctơ thực n – chiều Rn a. Khái niệm Một bộ n số thực được sắp xếp theo thứ tự (x1, x2, …, xn) được gọi là một vectơ n – chiều. Cho hai vectơ X = (x1, x2, …, xn) và Y = (y1, y2, …, yn) và số thực λ. Ta định nghĩa phép cộng hai vectơ và nhân một vectơ với số thực như sau: (i) X + Y = (x1 + y1, x2 + y2, …, xn + yn); (ii) λ.X = (λx1, λx2, …, λxn). Tập hợp tất cả các vectơ n – chiều cùng với hai phép toán trên được gọi là không gian vectơ thực n – chiều Rn (không gian tuyến tính n – chiều). Hệ vectơ độc lập tuyến tính (đltt): Hệ k vectơ {X1, X2, …, Xk} là hệ đltt nếu : λ1X1 + λ2X2 + … + λkXk = 0n

(1.1)

khi và chỉ khi λ1 = λ2 = ... = λk = 0. Ngược lại nếu tồn tại λi ≠ 0 mà (1.1) thỏa mãn thì hệ vectơ trên là phụ thuộc tuyến tính. b. Tích vô hướng của hai vectơ Định nghĩa 1.1.1 : Tích vô hướng của 2 vectơ X = (x1, x2, …, xn) và Y = (y1, y2, …, yn) được ký hiệu và định nghĩa như sau : < X, Y > = x1.y1 + x2.y2 + ... + xn.yn

(1.2)

Tính chất 1.1.1: (i) Tính chất giao hoán: < X1, X2 > = < X2, X1 >; (ii) Tính chất phân phối: < X1 + X2, X3 > = < X1, X3 > + < X2, X3 > ; (iii) Tính chất kết hợp với số thực: < λ.X1, X2 > = < X1, λ.X2 > = λ. < X1, X2 >. 1.1.2. Đường thẳng, đoạn thẳng trong Rn -7-

Phương trình đường thẳng đi qua điểm M0 = (x10, x20, …, xn0) và vectơ chỉ phương u = (a1, a2, …, an): M = M0 + t.u (phương trình tham số), với t  R là tham số, M là 1 điểm thuộc đường thẳng đó. Ở phương trình trên nếu t có dấu xác định (t ≥ 0, hoặc t ≤ 0) thì ta có nửa đường thẳng (cạnh vô hạn). Phương trình đường thẳng đi qua 2 điểm M1 = (x11, x21, …, xn1) và M2 = (x12, x22, …, xn2): M = α.M1 + (1 – α).M2 , với α  R. Ở phương trình trên nếu α  [0, 1] thì ta có đoạn thẳng [M1, M2]. 1.1.3. Tập lồi Một tập hợp Ω  Rn được gọi là tập lồi nếu có 2 điểm bất kỳ M1 và M2 thuộc Ω thì cả đoạn thẳng [M1, M2] cũng thuộc Ω.

1.2. Khái niệm về bài toán quy hoạch tuyến tính Có nhiều cách giải quyết một vấn đề trong thực tế nhưng cách thông thường nhất là người ta xây dựng mô hình toán học của các vấn đề này và sau đó dùng các kiến thức toán học để tìm lời giải cho các mô hình đã xây dựng. Để bắt đầu cho môn học, chúng ta cùng xét các ví dụ thực tế và tìm cách xây dựng mô hình toán học cho các ví dụ này. 1.2.1. Các ví dụ dẫn đến bài toán quy hoạch tuyến tính Ví dụ 1.2.1: Bài toán lập kế hoạch sản xuất Giả sử xí nghiệp dệt X ở Nam Định cần lập kế hoạch sản xuất vải. Nguyên liệu chính để sản xuất vải là sợi cotton và sợi polyester. Xí nghiệp có thể sản xuất ba loại vải Kate (ký hiệu là A), Kaki (B) và Len (C). Mức tiêu hao nguyên liệu để sản xuất ra 1 mét vải A, B, C và giá bán một mét mỗi loại được cho trong bảng sau (được gọi là Bảng hệ số kỹ thuật) : Nguyên liệu

Hiện có

A

B

C

Cotton (kg)

5500 kg

0.5

0.8

0.6

Polyester (kg)

3800 kg

0.4

0.3

0.2

27

36

30

Giá bán (nghìn/ m)

Bài toán được đặt ra là với nguyên vật liệu hiện có như trên thì xí nghiệp cần phải sản xuất bao nhiêu mét vải mỗi loại để số tiền thu được là tối đa (giả sử bán được hết). -8-

Xây dựng mô hình toán Gọi x1, x2, x3 là số mét vải A, B, C cần sản xuất (x1, x2, x3  0). Ta có bài toán sau: tìm x1, x2, x3 sao cho: f(x) = 27x1 + 36x2 + 30x3 → max 0.5x1 + 0.8x2 + 0.6x3 ≤ 5500 0.4x1 + 0.3x2 + 0.2x3 ≤ 3800 x1, x2, x3  0 Ví dụ 1.2.2: Bài toán dinh dưỡng của người thợ mỏ Theo nghiên cứu của Viện Dinh dưỡng Quốc gia thì mỗi người thợ mỏ, để có thể sinh hoạt và làm việc bình thường, cần tiêu thụ ít nhất 60g protit, 50g lipid và 70g glucid. Các thành phần dinh dưỡng này có trong 1g cá và 1g thịt như trong bảng dưới đây. Biết rằng giá 1g cá và 1g thịt là 40 và 90 VNĐ. Chất dinh dưỡng

Cá

Thịt

Protit (gam)

0.2

0.4

Lipid (gam)

0.25

0.1

Glucid (gam)

0.4

0.3

Bài toán đặt ra cho một công ty than ở Uông Bí là cần lập khẩu phần ăn cho mỗi người thợ mỏ mỗi ngày bao nhiêu gam thịt, gam cá sao cho số tiền phải chi cho một người là ít nhất nhưng vẫn đảm bảo lượng dinh dưỡng cần thiết trong ngày. Xây dựng mô hình toán Gọi x1 và x2 là số gam cá thịt cần mua trong ngày (x1, x2 ≥ 0). Ta cần giải bài toán sau: tìm x1, x2 sao cho: f(x) = 40x1 + 90x2 → min 0.2x1 + 0.4x2 ≥ 60 0.25x1 + 0.1x2 ≥ 50 0.4x1 + 0.3x2 ≥ 70 x1, x2 ≥ 0 Ví dụ 1.2.3: Bài toán lập kế hoạch kinh doanh khởi nghiệp Một sinh viên nghèo vừa tốt nghiệp đại học trong lúc chờ xin việc đã quyết định khởi nghiệp với số vốn vỏn vẹn chỉ có một triệu đồng. Với số tiền như vậy sinh viên đó quyết định buôn bán rau củ quả. Sau một ngày khảo sát ở chợ đầu mối và chợ phường, sinh viên đó thu được kết quả sau: -9-

Loại rau,

Giá mua ở chợ đầu

củ, quả

mối (nghìn/kg)

1

Rau muống

8

11

15

2

Cà chua

17

22

12

3

Bắp cải

12

16

20

4

Khoai tây

25

32

30

5

Bí

27

33

25

6

Hành

48

58

2

7

Chanh

40

48

5

8

Táo

36

45

22

STT

Giá bán ở chợ

Nhu cầu tối đa tại

phường (nghìn/kg) chợ phường (kg/ngày)

Bài toán được đặt ra là với số tiền vốn như vậy thì sinh viên đó phải mua các loại rau củ quả trên với số lượng bao nhiêu để bán được hết hàng và thu được lợi nhuận lớn nhất. Ta có mô hình bài toán sau: Gọi x1, x2,…, x8 là khối lượng (kg) rau củ quả cần mua lần lượt theo thứ tự như bảng trên, ta có mô hình bài toán sau: Tìm x1, x2,…, x8 sao cho: f(x) = 3x1 + 5x2 + 4x3 + 7x4 + 6x5 + 10x6 + 8x7 + 9x8 (nghìn đ) → max 8x1 + 17x2 + 12x3 + 25x4 + 27x5 + 48x6 + 40x7 + 36x8 ≤ 1000 (nghìn đ) x1 ≤ 15 (kg)

x5 ≤ 25 (kg)

x2 ≤ 12 (kg)

x6 ≤ 2 (kg)

x3 ≤ 20 (kg)

x7 ≤ 5 (kg)

x4 ≤ 30 (kg)

x8 ≤ 22 (kg)

x1, x2, x3, x4, x5, x6, x7, x8  0. Trong đó hàm mục tiêu là tổng lợi nhuận, lợi nhuận từ mặt hàng thứ i được tính như sau: (giá bán/kg – giá mua/kg).xi Ví dụ 1.2.4: Bài toán lập kế hoạch quảng cáo sản phẩm Một công ty dự định quảng cáo sản phẩm của mình trên truyền hình và truyền thanh. Biết rằng quảng cáo trên truyền thanh có đơn giá 2 triệu đồng/phút, còn trên truyền hình là 10 triệu đồng/phút. Ngoài ra Đài phát thanh yêu cầu mỗi hợp đồng quảng cáo phải có thời lượng tối thiểu là 5 phút, còn bên Đài truyền hình yêu cầu mỗi hợp đồng quảng cáo tối thiểu là 1 phút và tối đa là 4 phút. Theo các khảo sát thống kê thì 1 phút quảng cáo trên truyền hình có hiệu quả tương đương 6 phút trên truyền thanh. Công ty dự toán chi tối đa 30 triệu - 10 -

để quảng cáo. Bài toán được đặt ra là công ty đó cần đặt thời lượng quảng cáo như thế nào cho hiệu quả nhất. Gọi x1 và x2 là thời lượng quảng cáo trên truyền thanh và truyền hình (phút). Ta có mô hình bài toán sau: Gọi x1 và x2 là thời lượng quảng cáo trên truyền thanh và truyền hình (phút). Tìm x1, x2 sao cho: f(x) = x1 + 6x2 → max 2x1 + 10x2 ≤ 30 (triệu) x1 ≥ 5 (phút) 1 ≤ x2 ≤ 4 (phút) x1, x2  0 Ví dụ 1.2.5: Bài toán phân bổ vốn đầu tư Một nhà đầu tư với số vốn 10 tỷ đồng dự định đầu tư vào 4 lĩnh vực : chứng khoán, kinh doanh tạp hóa, gửi tiết kiệm và bất động sản. Biết lãi suất hàng năm của các lĩnh vực đầu tư này như sau : Lĩnh vực đầu tư

Lãi suất hàng năm (%)

Chứng khoán

20

Kinh doanh tạp hóa

12

Gửi tiếp kiệm

8

Bất động sản

15

Ngoài ra theo các khảo sát thực tế, để giảm thiểu rủi ro, nhà đầu tư thấy rằng không nên đầu tư vào chứng khoán vượt quá 30% tổng số vốn đầu tư, còn đầu tư vào kinh doanh tạp hóa và gửi tiếp kiệm phải ít nhất 40% tổng số vốn đầu tư và số tiền để đầu tư vào bất động sản ít nhất phải là 2 tỷ nhưng không quá 50% tổng số vốn đầu tư. Hãy lập kế hoạch phân bổ vốn đầu tư sao cho tổng lợi nhuận hàng năm là lớn nhất. Mô hình bài toán như sau : Gọi x1, x2, x3 và x4 tương ứng là số tiền (tỷ đổng) sẽ đầu tư vào chứng khoán, kinh doanh tạp hóa, gửi tiết kiệm và bất động sản. Với lợi nhuận thì mục tiêu luôn phải cực đại : f(x) = 0,2x1 + 0,12x2 + 0,08x3 + 0,15x4 (tỷ đồng) → max Các ràng buộc kinh doanh : Tổng số vốn đầu tư không vượt quá số vốn hiện có : x1 + x2 + x3 + x4 ≤ 10 (tỷ đồng) - 11 -

Đầu tư vào chứng khoán không vượt quá 30% tổng số vốn đầu tư : x1 ≤ 0,3(x1 + x2 + x3 + x4)  – 0,7x1 + 0,3x2 + 0,3x3 + 0,3x4 ≥ 0 Đầu tư vào kinh doanh tạp hóa và gửi tiếp kiệm phải ít nhất 40% tổng số vốn đầu tư : x2 + x3 ≥ 0,4(x1 + x2 + x3 + x4)  – 0,4x1 + 0,6x2 + 0,6x3 – 0,4x4 ≥ 0 Số tiền để đầu tư vào bất động sản ít nhất phải là 2 tỷ nhưng không quá 50% tổng số vốn đầu tư : x4 ≥ 2 và x4 ≤ 0,5(x1 + x2 + x3 + x4)  0,5x1 + 0,5x2 + 0,5x3 – 0,5x4 ≥ 0. Vậy nhà đầu tư phải giải bài toán sau : f(x) = 0,2x1 + 0,12x2 + 0,08x3 + 0,15x4 → max x1 + x2 + x3 + x4 ≤ 10 – 0,7x1 + 0,3x2 + 0,3x3 + 0,3x4 ≥ 0 – 0,4x1 + 0,6x2 + 0,6x3 – 0,4x4 ≥ 0 0,5x1 + 0,5x2 + 0,5x3 – 0,5x4 ≥ 0. x4 ≥ 2 x1, x2, x3, x4 ≥ 0. Ví dụ 1.2.6: Bài toán chia cắt vật liệu Một công trình xây dựng X cần cắt những cây thép nguyên dài 4 m thành các đoạn ngắn hơn T1, T2 và T3 có độ dài tương ứng là 1,8 m; 1,4 m và 1,0 m để ghép cốt thép. Các kiểu mẫu cắt và số lượng đoạn ngắn được cho trong bảng dưới đây: Loại đoạn

Mẫu cắt

Số đoạn

ngắn

1

2

3

4

5

6

cần có

T1 dài 1,8 m

2

1

1

0

0

0

200

T1 dài 1,4 m

0

1

0

2

1

0

400

T1 dài 1,0 m

0

0

2

1

2

4

900

Phần thừa

0,4 m 0,8 m 0,2 m 0,2 m 0,6 m 0,0 m

–

Bài toán được đặt ra là phải cắt theo mỗi mẫu bao nhiêu cây thép nguyên để có đủ số đoạn ngắn cần có và số thép thừa phải là ít nhất. Mô hình bài toán như sau : Gọi xj (j =1, …, 6) là số cây thép nguyên cắt theo mẫu j.

- 12 -

Tổng số sắt thừa là : f(x) = 0,4x1 + 0,8x2 + 0,2x3 + 0,2x4 + 0,6x5 (mét). Để có đủ số đoạn ngắn các loại ta phải có : 2x1 + x2 + x3 = 200, x2 + 2x4 + x5 = 400, 2x3 + x4 + 2x5 + 4x6 = 900. Ta có bài toán. Tìm x1, x2, x3, x4, x5 và x6 sao cho : f(x) = 0,4x1 + 0,8x2 + 0,2x3 + 0,2x4 + 0,6x5 → min 2x1 + x2 + x3 = 200 x2 + 2x4 + x5 = 400 2x3 + x4 + 2x5 + 4x6 =900 xj ≥ 0, j = 1, …, 6. Từ các ví dụ trên đây ta thành lập Bài toán quy hoạch tuyến tính (BT QHTT) tổng quát. 1.2.2. Bài toán quy hoạch tuyến tính tổng quát a. Bài toán QHTT dạng tổng quát Tìm các giá trị x1, x2,…xn sao cho: n

f  x    c j x j  min (max) (1) j1

 n      i = 1, m  a ij x j   bi j1            x    j= 1,n (3)   j     Tùy ý 







(2)



Trong đó (1) là hàm mục tiêu, (2) là các ràng buộc chung, (3) là các ràng buộc về dấu. Một số khái niệm Phương án (PA): Vectơ X = (x1, x2, ..., xn) thoả mãn tất cả các ràng buộc của bài toán được gọi là một phương án. Ràng buộc thỏa mãn với dấu “=” được gọi là ràng buộc “chặt”; ràng buộc thỏa mãn với dấu “” là ràng buộc “lỏng”. Phương án tối ưu (PATƯ ): Một PA mà tại đó giá trị hàm mục tiêu đạt giá trị nhỏ nhất (min), hoặc lớn nhất (max) được gọi là phương án tối ưu (PATƯ). - 13 -

b. BT QHTT dạng chính tắc BT QHTT dạng chính tắc là bài toán có các ràng buộc chung là chặt, còn các ràng buộc về dấu là không âm. Đó là: n

f x    c j x j  min (max) j1

n  a ij x j  b i (i  1, m)  j1 x  0 (j  1, n )  j Dạng ma trận của bài toán chính tắc f(x) = < c, X > → min (max) A.XT = b X ≥ 0n Trong đó c = (c1, c2, …, cn) là các hệ số của hàm mục tiêu, A là ma trận hệ số của hệ các ràng buộc chung, b = (b1, b2, …, bm)T là các hệ số tự do, 0n = (0, 0, ..., 0). Mọi BT QHTT tổng quát đều có thể đưa về bài toán dạng chính tắc tương đương theo nghĩa giá trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia. Cách đưa bài toán về dạng chính tắc - Nếu một ràng buộc có dấu “≤” thì ta cộng vào vế trái một biến phụ không âm để được ràng buộc chặt. - Nếu một ràng buộc có dấu “≥” thì ta trừ đi vế trái một biến phụ không âm để được ràng buộc chặt. - Các biến phụ có hệ số bằng 0 trong hàm mục tiêu. - Nếu xj ≤ 0 thì ta đổi biến xj’= − xj ≥ 0. - Nếu xj không có ràng buộc về dấu thì đặt xj = xj’− xj’’, với xj’, xj’’≥ 0. Ví dụ 1.2.7: Đưa bài toán sau về dạng chính tắc: f(x) = –2x1 + x2 + 3x3 + 5x4  min x1 – 3x2 + 5x3 – x4  16 2x1 – x2 – 2x3 + 2x4 ≥ – 4 4x1 + 3x2 + x3 + x4 = 9 x1, x2 ≥ 0; x3  0; x4 tùy ý

- 14 -

Ta sẽ cộng vào vế trái ràng buộc 1 biến phụ x5, trừ đi vế trái ràng buộc 2 biến phụ x6. Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’ với x4’, x4’’ ≥ 0. Ta được bài toán chính tắc tương đương sau: f(x) = –2x1 + x2 – 3x3’ + 5x4’ – 5x4’’  min x1 – 3x2 – 5x3’ – x4’ + x4’’ + x5 = 16 2x1 – x2 + 2x3’ + 2x4’ – 2x4’’ – x6 = –4 4x1 + 3x2 – x3’ + x4’ – x4’’ = 9 x1, x2 , x3’, x4’, x4’’, x5, x6 ≥ 0 c. BT QHTT dạng chuẩn - tắc Bài toán dạng chuẩn tắc là bài toán dạng chính tắc với mỗi phương trình đều có một biến số với hệ số bằng 1 ở phương trình đó đồng thời không có trong các phương trình khác (hệ số bằng 0). Các biến đó được gọi là biến cơ sở. Biến không phải là cơ sở được gọi là phi cơ sở (biến tự do). n

f  x    c j x j  min (max) j1

 x1  a1m 1x m 1  a1m  2 x m  2  ......  a1n x n  b1  a 2m 1x m 1  a 2m  2 x m  2  ......  a 2n x n  b 2  x2   ......................................................................   x m  a mm 1x m 1  a mm  2 x m  2  ......  a mn x n  b m   x j  0 (j  1,n)  Trong đó các biến cơ sở là x1, x2,…, xm (trên thực tế các biến cơ sở có thể là các biến khác), các biến còn lại là phi cơ sở (biến tự do). Nghiệm riêng cơ bản (nghiệm cơ sở) là nghiệm riêng của hệ phương trình tuyến tính khi ta cho các biến phi cơ sở bằng 0. Ở dạng chuẩn tắc trên ta có nghiệm riêng cơ bản là: X0 = (b1, b2, .., bm, 0, 0, .., 0). Lưu ý, hệ phương trình tuyến tính ở dạng chuẩn tắc cho ta ngay nghiệm tổng quát khi cho các biến tự do giá trị tùy ý và chuyển chúng sang vế phải ta được: n   x = b –  i i  a ij x j  với xi là biến cơ sở. j = m+1  

Mọi bài toán dạng chính tắc đều có thể chuyển về bài toán dạng chuẩn tắc bằng phép khử Gauss–Jordan, được trình bày dưới đây d. Bài toán QHTT dạng chuẩn - 15 -

Bài toán dạng chuẩn là bài toán dạng chuẩn tắc với vế phải của các phương trình là không âm (mọi bi ≥ 0). Phương án cực biên (PACB) của BT QHTT là đỉnh của tập PA. Khái niệm đỉnh của tập PA theo quan điểm hình học thì nó không thể nằm bên trong một cạnh của tập PA. Nhận xét : i) Với BT QHTT dạng tổng quát, PACB là 1 PA nếu nó thỏa mãn ’’chặt’’ n ràng buộc đltt, bởi vì mỗi ràng buộc chặt là 1 mặt biên của tập PA. ii) Với BT QHTT dạng chính tắc, PACB là nghiệm riêng cơ bản của hệ các ràng buộc chung và thỏa mãn các ràng buộc về dấu. Bởi vì 1 PACB, ngoài m ràng buộc chung độc lập tuyến tính là các ràng buộc chặt, sẽ phải thỏa mãn (n – m) phương trình xj = 0 (trong đó m < n), do đó ta có n ràng buộc chặt và chúng đltt. iii) Ở dạng chuẩn ta nhận ra ngay PACB là: X0 = (b1, b2, ...,bm, 0, 0, ..., 0). 1.2.3. Phép khử Gauss – Jordan Cho hệ phương trình tuyến tính tổng quát:

a11x1  a12 x12  ...  a1v x1v  ...  a1n x n  b1  a 21x1  a 22 x 22  ...  a 2v x 2v  ...  a 2n x n  b 2 .................................................................  a r1x1  a r2 x r2  ...  a rv x rv  ...  a rn x n  b r ...................................................................  a m1x1 +a m2 x m2  ...  a mv x mv  ...  a mn x n  b 2  x j  0 (j  1,n)  Ta có ma trận mở rộng:

b1   a11 a12 ...a1v ...a1n    a 21 a 22 ...a 2 v ...a 2n b 2   .................................    br   a r1 a r 2 .. a rv  ..a rn  .................................     a a ..a ..a bm  mv mn  m1 m 2  Giả sử cần chọn xv là biến cơ sở của hàng thứ r ta chọn phần tử arv được gọi là phần tử trục (phần tử xoay). Đánh dấu phần tử trục bằng dấu [ ]. Lưu ý phần tử trục phải khác 0. Hàng chứa phần tử trục được gọi là hàng xoay, cột chứa phần tử trục được gọi là cột xoay. - 16 -

Mục đích của phép khử Gauss - Jordan là đưa phần tử arv về 1 còn các phần tử khác trên cột xoay về 0. Để được như vậy ta sẽ thực hiện các bước sau đây: Bước 1: Chia hàng xoay cho arv, Bước 2: Lấy hàng i trừ đi ki lần hàng r, trong đó ki = aiv / arv. Lưu ý: Các phần tử không thuộc hàng xoay và cột xoay được tính lại theo qui tắc hình chữ nhật như sau: [arv]

arj

a ij'  a ij  a rj . aiv

a iv a rv

(1. 3)

aij

Như vậy ta được ma trận mới: , , ,  a11 a12 ...0....a 1n b1'   ,  , , b '2   a 21 a 22 ...0....a 2n  .................................    '  a ,r1 a ,r2 ...1.....a ,rn br     .................................   a , a , ..a , ..a , b 'm  mv mn  m1 m2 

Các tính chất: Tính chất 1.2.1: Nếu trên hàng xoay có phần tử 0 thì sang bảng mới cả cột chứa phần tử 0 đó giữ nguyên. Nhận xét: Các biến cơ sở ở các hàng khác hàng xoay (nếu có) vẫn được giữ nguyên, biến cơ sở cũ ở hàng xoay sẽ bị loại. Chính vì vậy phép khử Gauss – Jordan còn được gọi là phép biến đổi cơ sở. Tính chất 1.2.2: Nếu trên cột xoay có sẵn phần tử 0 thì sang bảng mới cả hàng chứa phần tử 0 đó giữ nguyên. Tính chất 1.2.3: Nếu trên cột xoay có phần tử = arv (hoặc = −arv) thì ta lấy hàng chứa phần tử đó trừ đi (hoặc cộng với) hàng xoay. Tính chất 1.2.4: Nếu trên hàng xoay có phần tử = arv (hoặc = −arv) thì ta lấy cột chứa phần tử đó trừ đi (hoặc cộng với) cột xoay. Các tính chất trên đều được suy ra từ công thức (1.3) ở trên. Ví dụ 1.2.8: Cho ma trận mở rộng: - 17 -

 1   1  3   2

2 4 5 3

0 [2] 2 4

3 5  2 0  1  2  1 7

Giả sử cần thực hiện phép khử Gauss – Jordan với phần tử trục a23 = 2, ta thực hiện các bước sau: - Chia hàng 2 (hàng xoay) cho 2; - Các phần tử khác trên cột 3 (cột xoay) sang bảng mới nhận giá trị = 0; - Trên hàng xoay có a25 = 0 nên cột 5 được giữ nguyên; - Trên cột xoay có a13 = 0 nên hàng 1 được giữ nguyên; - Có a33 = phần tử trục nên ta lấy hàng 3 trừ đi hàng 2; - Có a24 = − a23 nên ta lấy cột 3 cộng vào cột 4. Ta được:

 1   1 2   4  a  41

2 0 3 5  2 1 1 0   1 0 3  2 a 42 0 5 7 

Còn lại a41 và a42 ta áp dụng quy tắc hình chữ nhật: a41 = 2 – (–1).4/2 = 4; a43 = 3 – 4.4/2 = – 5. Ví dụ 1.2.9: Tìm 1 nghiệm riêng cơ bản và nghiệm tổng quát của hệ phương trình sau: x2 + 2x3 + 4x4 + 2x5 = 18 x1 + 2x2 + 3x3 + 6x4 + 5x5 = 33 2x1 + 3x2 + 7x3 + 10x4 +14x5 = 56 Ta biến đổi ma trận mở rộng:

 0 1 2 4 2  1 2 3 6 5  2 3 7 10 14 

0 1 2 4  1 0  1  2  0 0 3 [2] 

18  0 1 2 4   33  ~  1 0  1  2  2 0 1 2 56  

18   1 3  ~ 8 2  2

 0 1  4 0  10 2 18    1  3  ~ 1 0 2 0 7  6 8  0 0 3 1 3  2

2  5  4  - 18 -

Lần lượt trên mỗi hàng ta chọn 1 phần tử trục (nên chọn các phần tử = ±1 hoặc ±2 cho tiện tính toán) để tạo ra 3 biến cơ sở. Ở bảng 4 ta có dạng chuẩn tắc với các biến cơ sở là x 2, x1 và x4, các biến còn lại x3 và x5 là phi cơ sở (biến tự do). Cho x3 = x5 = 0 ta có 1 nghiệm riêng cơ bản X1 = (5, 2, 0, 4, 0). Để tìm nghiệm tổng quát ta cho các biến phi cơ sở x3, x5 giá trị tùy ý và chuyển chúng sang vế phải, ta được: X = (5 – 2x3 – 7x5, 2 + 4x3 + 10x5, x3, 4 – 3/2x3 – 3x5, x5). 1.2.4. Các tính chất của bài toán quy hoạch tuyến tính Định lý 1.2.1: Số PACB của BT QHTT dạng chính tắc là hữu hạn và  Cn , trong đó m là m

hạng của hệ ràng buộc chung. Định lý 1.2.2: Số thành phần dương của một PACB không vượt quá hạng của hệ ràng buộc chung m. Nếu số thành phần dương đúng bằng m thì PACB đó là không suy biến (KSB), nếu số thành phần dương nhỏ hơn m thì PACB đó là suy biến. Định lý 1.2.3: Một PA của BT QHTT dạng chính tắc là PACB nếu các véc tơ cột ứng với các thành phần dương là độc lập tuyến tính. Định lý 1.2.4: BT QHTT dạng tổng quát nếu có PA và hạng của hệ các ràng buộc (kể cả ràng buộc về dấu) là n thì sẽ có PACB. Hệ quả 1.2.1: BT QHTT dạng chính tắc nếu có PA thì sẽ có PACB (các ràng buộc về dấu có hạng = n). Định lý 1.2.5: BT QHTT có PATƯ khi và chỉ khi nó có PA và hàm mục tiêu bị chặn dưới với bài toán tìm min (chặn trên với bài toán tìm max).

1.3. Phương pháp đơn hình 1.3.1. Đặc điểm của tập phương án Định lý 1.3.1: Tập PA của BT QHTT dạng chính tắc là một tập lồi. Tức là nếu X1 và X2 là 2 PA thì  X  [X1, X2] cũng là PA. Chứng minh: Với X = α.X1 + (1 – α).X2 trong đó 0 ≤ α ≤ 1 ta có: AX = A.[α.X1 + ( 1 – α ).X2] = α.AX1 + ( 1 – α ).AX2 = α.b + ( 1 – α ).b = b, và với X1, X2 ≥ 0n thì X = α.X1 + ( 1 – α ).X2 ≥ 0n với 0 ≤ α ≤ 1. Định lý 1.3.2: Nếu f(X1) ≤ f(X2) thì f(X1) ≤ f(X) ≤ f(X2) với mọi X thuộc cạnh [X1, X2]. Chứng minh: f(X) = < c, X > = < c, α.X1 + ( 1 – α ).X2 > = < c, α.X1 > + < c, (1 – α).X2 > = α.f(X1) + (1 – α).f(X2) ≥ α.f(X1) + (1 – α).f(X1) = f(X1). Suy ra f(X) ≥ f(X1), tương tự ta có f(X) ≤ f(X2). - 19 -

Hệ quả 1.3.1: Nếu f(X1) = f(X2) thì f(X1) = f(X) = f(X2) với mọi X thuộc cạnh [X1, X2]. Hệ quả 1.3.2: Nếu X1 và X2 là 2 PATƯ thì mọi X thuộc cạnh [X1, X2], tức là X = α.X1 + (1 – α).X2 với 0 ≤ α ≤ 1, cũng là PATƯ. Hệ quả 1.3.3: Một PATƯ không thể là 1 điểm đơn độc bên trong 1 cạnh thuộc tập PA. Định lý 1.3.3: Nếu X1, X2,…, Xk là các PATƯ thì X = α1.X1 + α2.X2 + … + αk.Xk với mọi αi ≥ 0 và α1 + α2 + … + αk = 1 cũng là PATƯ. Định lý 1.3.4: PATƯ chỉ có thể là các điểm cực biên (PACB), cạnh biên hoặc một phần của mặt biên giới hạn bởi các điểm cực biên. Như vậy trong tập PATƯ có ít nhất 1 điểm PACB. Định lý 1.3.5 (giá trị trung gian): Nếu X1, X2 là 2 PA và f(X1) ≤ f(X2) thì với mọi λ  [f(X1), f(X2)] luôn tìm được PA X  [X1, X2] sao cho f(X) = λ. Cụ thể là X = α.X1 + (1 – α).X2, trong đó α được xác định từ phương trình: α.f(X1) + (1 – α).f(X2) = λ. 1.3.2. Giải bài toán quy hoạch tuyến tính bằng phương pháp hình học Để giải BT QHTT bằng phương pháp hình học ta cần xác định được tập PA, từ đó tìm được các điểm cực biên (PACB). Tính giá trị cuả f(X) tại các điểm cực biên đó và từ đó ta tìm được PATƯ. Ví dụ 1.3.1: Giải BT QHTT sau bằng phương pháp hình học. f(x) = 3x1 – 2x2 → min (max) x1 + x2 ≤ 4

x2 A

2x1 + x2 ≤ 6 x1 , x2 ≥ 0

B

Tập PA là miền bên trong tứ giác OABC, giới hạn bởi các đường: OA: x1 = 0 AB: x1 + x2 = 4 BC: 2x1 + x2 = 6 và OC: x2 = 0

O

C

x1

Hình 1.3.1

Dễ dàng tìm được tọa độ các điểm cực biên O(0, 0), A(0, 4), B(2, 2) và C(3, 0). Tính giá trị hàm mục tiêu tại các điểm này ta được: f(O) = 0, f(A) = – 8, f(B) = 2 và f(C) = 9. So sánh các giá trị này ta thấy f(x)min = – 8 khi X = (0, 4) và f(x)max = 9 khi X = (3, 0). Lưu ý: Phương pháp hình học chỉ áp dụng cho BT QHTT với 2 biến. Để giải bài toán với 3 biến trở lên ta sẽ sử dụng phương pháp đơn hình, được đề cập ở dưới đây. 1.3.3. Ý tưởng của phương pháp đơn hình - 20 -

Nội dung của phương pháp đơn hình là tìm PATƯ ở các PACB (xem Định lý 1.3.4 ở trên). Cụ thể là xuất phát từ một PACB, đánh giá xem PACB đó tối ưu chưa, nếu chưa phải là PATƯ thì ta tìm PACB tốt hơn (có giá trị hàm mục tiêu tốt hơn), cứ như vậy tới khi tìm được PATƯ, hoặc sẽ kết luận được rằng không tồn tại PATƯ. Vì số PACB là hữu hạn nên số bước thực hiện cũng hữu hạn. 1.3.4. Trường hợp bài toán quy hoạch tuyến tính có dạng chuẩn a. Bài toán tìm fmin Thuật toán dưới đây áp dụng cho bài toán QHTT ở dạng chuẩn, tức là mỗi phương trình đều có một biến cơ sở, không mất tính tổng quát ta giả thiết các biến cơ sở đó là: {x1, x2,…, xm} và PACB xuất phát là X0 = (b1, b2, …,bm , 0, 0, ...,0). Thuật toán giải BT QHTT fmin gồm các bước sau: Bước 1: Lập bảng đơn hình xuất phát: Cơ sở

Hệ số

PACB

cơ sở

x1

x2 … xr … xm xm+1 … xk … xv … xn

c1

c2 … cr … c m

cm+1 … ck … cv … cn

x1

c1

b1

1

0 … 0 …0

a1,m+1… a1k … a1v… a1n

x2

c2

b2

0

1 … 0 …0

a2,m+1… a2k … a2v … a2n

…

…

…

...…………………………………………….

xr

cr

br

0

…

…

…

...…………………………………………….

xm

cm

bm

0

0 … 0 … 1

am,m+1…amk …amv ... amn

f(x)

Δ0

0

0 … 0 … 0

∆m+1 … ∆k … ∆v … ∆n

0 … 1 …0

ar,m+1… ark … arv … arn

Hàng dưới cùng được gọi là hàng đặc trưng, trong đó: Δ0 = là giá trị của hàm mục tiêu ứng với PACB X0; Δk = – ck là ước lượng của biến xk, trong đó cB là véc tơ cột hệ số cơ sở, b là véc tơ cột tự do, Ak là véc tơ cột k. Ta thấy nếu xk là biến cơ sở thì ∆k = 0. Bước 2: Kiểm tra dấu hiệu tối ưu: +) Nếu  ∆k ≤ 0 thì X0 là PATƯ và fmin = Δ0 . Thuật toán kết thúc. - Nếu mọi ước lượng của các biến phi cơ sở < 0 thì PATƯ là duy nhất. - Nếu  Δk = 0 với k không thuộc tập cơ sở thì PATƯ không phải là duy nhất, vì nếu ta chọn cột k là cột xoay thì các giá trị trên hàng đặc trưng vẫn giữ nguyên (xem tính chất 1.2.2). Như vậy biến xk có thể được đưa vào cơ sở và ta được PATƯ mới. Trong trường hợp này nếu  aik ≤ 0 (mọi phần tử trên cột k ≤ 0) thì tập PATƯ là 1 nửa đường thẳng (xem đoạn cuối phần chứng minh dưới đây). - 21 -

+) Nếu  ∆k > 0 thì X0 không phải là PATƯ, có 2 trường hợp xảy ra: - Nếu tồn tại một ∆k > 0 mà  aik ≤ 0 (mọi phần tử trên cột k ≤ 0) thì hàm mục tiêu không bị chặn, bài toán không có PATƯ. Thuật toán kết thúc. - Nếu với mỗi ∆k > 0 đều có ít nhất một phần tử aik > 0 thì ta chuyển sang bước 3. Bước 3: Cải tiến PACB: +) Ta sẽ đưa một biến mới vào cơ sở, đồng thời sẽ loại một biến ra khỏi cơ sở để được PACB mới tốt hơn với giá trị của hàm mục tiêu nhỏ hơn. +) Để cải thiện nhiều nhất ta sẽ chọn biến có ước lượng dương lớn nhất để đưa vào cơ sở. Giả sử ∆v > 0 lớn nhất thì xv sẽ được đưa vào cơ sở. +) Trên cột v ta sẽ chọn phần tử trục (giả sử là arv) theo hai điều kiện sau: arv > 0 và tỷ số (br / arv) là nhỏ nhất. Ta đánh dấu phần tử trục arv bằng dấu [ ]. Cột v sẽ là cột xoay, còn hàng r là hàng xoay. +) Thực hiện phép khử Gauss-Jordan (phép biến đổi cơ sở) với phần tử trục arv ta được bảng đơn hình mới. Trên hàng xoay ta có biến cơ sở mới là x v, biến cơ sở cũ trên hàng xoay bị loại ra khỏi cơ sở (các biến cơ sở khác giữ nguyên) thay xv vào vị trí ở cột thứ nhất, và cv vào vị trí ở cột thứ hai. Sau đó trở lại bước 2. Vì số PACB là hữu hạn nên sau hữu hạn bước thì thuật toán kết thúc. Lưu ý: Các giá trị trên hàng đặc trưng cũng được tính lại theo qui tắc hình chữ nhật (bạn đọc có thể tự chứng minh dựa vào các định nghĩa ở bước 1), vì vậy các chứng minh dưới đây sẽ dựa trên cơ sở của phép khử Gauss-Jordan. Chứng minh thuật toán: Không mất tính tổng quát, ta giả sử các biến cơ sở là từ x1 đến xm (vì vai trò của các biến là bình đẳng nhau), các biến còn lại là phi cơ sở (xem bảng đơn hình xuất phát). i) Chứng minh dấu hiệu tối ưu: Giả sử PACB X0 có mọi ∆k ≤ 0 và X là một PA bất kỳ, khi đó: n

m

f(X)=  c j x j =  ci x i + j=1

i=1

m

  ci b i – i=1

n



j=m+1

n



j=m+1

i=1

m

n

i=1





n

a ijx j )+

j=m+1

x j ( ci a ij – c j )=Δ 0 – n

Vì mọi xj ≥ 0 và ∆j ≤ 0 nên

m

c j x j =  ci (b i –

n



cx j

j

j=m+1

x jΔ j

j=m+1

x jΔ j  0 suy ra f(X) ≥ ∆0 với mọi X. Như vậy: fmin =

j = m+1

∆0 và X0 là PATƯ. ii) Chứng minh điều kiện chọn phần tử trục arv: Điều kiện arv > 0 để khi chia hàng xoay cho arv ta vẫn có br’ ≥ 0. - 22 -

Điều kiện tỷ số br / arv nhỏ nhất để đảm bảo sao khi thực hiện phép khử Gauss – Jordan ta có mọi bi ≥ 0. iii) Chứng minh bước cải tiến PACB: Sau khi thực hiện phép khử Gauss – Jordan với phần tử trục arv ta có: Δ  '0   0  br . v   0 vì br ≥ 0, arv > 0 và ∆v > 0. a rv Ta thấy PACB mới X0’ tốt hơn vì có giá trị hàm mục tiêu ∆0’ nhỏ hơn. iv) Chứng minh trường hợp không tồn tại PATƯ: Giả sử tồn tại một ∆k > 0 mà  aik ≤ 0. Khi đó ta cho xk = t > 0 tùy ý, các biến phi cơ sở khác = 0, ta có PA: X = (b1 – a1k.t, b2 – a2k.t, …, bm – amk.t, 0, 0…, t, 0,…, 0) ( xem bảng đơn hình xuất phát, chuyển biến xk sang vế phải ). Đây là PA vì với aik ≤ 0 và t > 0 thì bi – aik.t ≥ 0. Khi đó ta có: n

m

m

j=1

i=1

i=1

f(X) =  c j x j =  ci x i + c k x k =  ci (bi – a ik .t)+c k .t m

m

i=1

i=1

(1.4)

=  ci bi – ( ci a ik – c k ).t = Δ 0 – Δ k .t Vì ∆k > 0 và t > 0 tùy ý nên f(X) không bị chặn dưới do đó không tồn tại PATƯ.

Lưu ý: Trường hợp có dấu hiệu tối ưu nhưng có biến phi cơ sở xk có ∆k = 0 và mọi aik ≤ 0 thì ta cũng cho xk = t > 0 tùy ý, các biến phi cơ sở khác = 0, thì theo công thức (1.4) ở trên ta có f(X) = ∆0 – ∆k.t = ∆0 nên ta có vô số PATƯ: X = (b1 – a1k.t, b2 – a2k.t, …, bm – amk.t, 0, 0…, t, 0,…, 0) = X0 + t.u PATƯ tổng quát trên là 1 nửa đường thẳng (cạnh vô hạn) với điểm đầu là X0 và vectơ chỉ phương là u = ( – a1k, – a2k, …, – amk, 0, 0…, 1, 0,…, 0). Ví dụ 1.3.2: Giải bài toán QHTT sau: f(x) = 2x1 + 3x2 – x3 – 1/2x4  min x1 – x2 + x3 + 1/2x4 = 18 x2 – 4x3 + 8x4  8 2x2 – 2x3 + 3x4 ≥ – 20 xj ≥ 0 (j =1…4) Giải: Trước tiên ta đưa bài toán về dạng chính tắc bằng cách cộng vào vế trái ràng buộc 2 biến phụ x5 và trừ đi vế trái ràng buộc 3 biến phụ x6. Ta có: f(x) = 2x1 + 3x2 – x3 – 1/2x4  min - 23 -

x1 – x2 + x3 + 1/2x4

=

18

x2 – 4x3 +

=

8

8x4 + x5

2x2 – 2x3 + 3x4 – x6 = – 20 xj ≥ 0 (j =1…4) Đổi dấu 2 vế ràng buộc 3 ta sẽ có BT dạng chuẩn: f(x) = 2x1 + 3x2 – x3 – 1/2x4  min x1 – x2 + x3 + 1/2x4

= 18

x2 – 4x3 +

= 8

8x4 + x5

– 2x2 + 2x3 – 3x4 + x6 = 20 xj ≥ 0 (j =1…4) Các biến cơ sở là {x1, x5, x6} và PACB xuất phát là X0 thể lập ngay được bảng đơn hình ứng với PACB X0. Cơ Hệ PA x1 x2 x3 x4 x5 Sở Số CB 2 3 – 1 – 1/2 0 x1 2 18 1 –1 1 1/2 0

= (18, 0, 0, 0, 8, 20), do đó ta có x6 0 0

x5

0

8

0

1

–4

8

1

0

x6

0

20

0

–2

[2]

–3

0

1

B1

f(x)

36

0

–5

3

3/2

0

0

Ở bước 1 ta thấy PACB tương ứng chưa tối ưu. Biến được đưa vào cơ sở là x 3 ứng với 3 = 3 lớn nhất. So sánh tỷ số 18/1 và 20/2 ta thấy tỷ số 20/2 là bé nhất nên hàng thứ 3 sẽ là hàng xoay, phần tử trục sẽ là a33 = [2], trên hàng xoay biến x6 sẽ bị loại khỏi cơ sở. Thực hiện phép khử Gauss-Jordan với phần tử trục a33 ta có bảng mới dưới đây: Cơ sở x1

Hệ số 2

PA CB 8

x1 2 1

x2 3 0

x3 –1 0

x4 – 1/2 [2]

x5 0 0

x6 0 – 1/2

x5

0

48

0

–3

0

2

1

2

x3

–1

10

0

–1

1

– 3/2

0

1/2

B2

f(x)

6

0

–2

0

6

0

– 3/2

Ở bảng thứ 2 ta có 4 = 6 > 0 nên biến x4 sẽ được đưa vào cơ sở. Tỷ số 8/2 là nhỏ nhất nên hàng thứ nhất sẽ là hàng xoay. Tiếp tục biến đổi ta sẽ có bảng thứ 3: - 24 -

Cơ Sở

Hệ Số

PA CB

x1

x2

x3

x4

x5

x6

3 0

–1 0

– 1/2 1

0 0

0 – 1/4

x4

–1/2

4

2 1/2

x5

0

40

–1

–3

0

0

1

[5/2]

x3

–1

16

3/4

–1

1

0

0

1/8

B3

f(x)

– 18

–3

–2

0

0

0

0

Ở bảng thứ 3 ta thấy  ∆k ≤ 0 nên PACB tương ứng là tối ưu và f min = – 18. Vậy ta có PATƯ X1 = (0, 0, 16, 4, 40, 0). Nhưng ta thấy PATƯ X1 không phải là duy nhất vì 6 = 0 nên ta có thể đưa x6 vào cơ sở mà vẫn giữ nguyên các giá trị của hàng đặc trưng (xem tính chất 1.2.2 trang 17). Phần tử trục được chọn là [5/2] vì tỷ số 40 chia 5/2 là bé nhất. Biến đổi tiếp ta được bảng thứ 4: Cơ sở x4

Hệ số –1/2

PA CB 8

x1 2 2/5

x2 3 – 3/10

x3 –1 0

x4 – 1/2 1

x5 0 1/10

x6 0 0

x6

0

16

– 2/5

– 6/5

0

0

2/5

1

x3

–1

14

4/5 –17/20

1

0

– 1/20

0

B4

f(x)

– 18

–3

0

0

0

0

–2

Ta có PATƯ thứ hai là X2 = ( 0, 0, 14, 8, 0, 16 ). Từ đó ta có vô số PATƯ là: X = α.X1 + (1 – α).X2 = α.(0, 0, 16, 4, 40, 0) + (1 – α).(0, 0, 14, 8, 0, 16) = (0, 0, 14 + 2α, 8 – 4α, 40α, 16 – 16α), với  α  [0, 1]. Ví dụ 1.3.3: Giải BT QHTT sau: f(x) = −2x1 − 6x2 + 8x3 – 5x4 → min x1 + 2x2 − 3x3 + x4 = 8 5x2 − 5x3 − 3x4  18 x2 − 4x3 + 2x4 ≤ 12 xj ≥ 0 (j = 1…4) Giải: Đưa bài toán về dạng chính tắc: f(x) = −2x1 − 6x2 + 8x3 – 5x4  min x1 + 2x2 – 3x3 + x4 5x2 − 5x3 − 3x4 + x5

= 8 = 18 - 25 -

x2 − 4x3 + 2x4

+ x6 = 12

xj ≥ 0 (j =1…6) Ta có bài toán dạng chuẩn và điền vào bảng đơn hình xuất phát: Cơ Hệ PA x1 x2 x3 x4 x5 x6 sở số CB –2 –6 8 –5 0 0 x1 –2 8 1 2 −3 1 0 0 x5

0

18

0

5

−5

−3

1

0

x6

0

12

0

1

−4

[2]

0

1

B1

f(x)

− 16

0

2

−2

3

0

0

x1

–2

2

1

3/2

−1

0

0

− 1/2

x5

0

36

0

13/2

− 11

0

1

3/2

x4

–5

6

0

1/2

−2

1

0

1/2

B2

f(x)

− 34

0

1/2

4

0

0

−3/2

Ở bảng thứ 2 ta có 3 = 4 > 0, nhưng mọi hệ số trên cột tương ứng đều ≤ 0 nên bài toán không có PATƯ (f(x) không bị chặn dưới). Lưu ý: - Khi lập bảng đơn hình xuất phát ta phải có bài toán ở dạng chuẩn (mỗi phương trình có 1 biến cơ sở và vế phải không âm). - Trong quá trình tính toán, các giá trị phải ở dạng chính xác (dạng phân số). - Các bảng có thể được trình bầy dạng nối tiếp nhau, phần giải thích có thể ghi ở bên phải bảng (có thể bỏ phần giải thích), phần kết luận ghi bên dưới. b. Bài toán tìm fmax Thuật toán tương tự như bài toán tìm fmin , có hai điểm khác đó là: - Ở bước 2 để có PATƯ thì Δk ≥ 0. - Ở bước 3 để chọn biến cơ sở mới ta chọn Δk có giá trị âm nhỏ nhất. Cách thứ 2: Ta có thể chuyển từ bài toán tìm max thành bài toán tìm min bằng cách đặt: g(x) = – f(x) và ta có: fmax = – gmin PATƯ của gmin chính là PATƯ của fmax . Ví dụ 1.3.4 Giải BT QHTT sau:

- 26 -

f(x) = 8x1 + 3x2  2x3  2x4 + 2x5 + 4x6  x7  x8 → max x1 + x2  x3

+ x5 + 2x6

= 2

2x1

+ x3  x4 + 2x5 + x6

+ x8 = 3

8x1

+ 6x3  6x4 + 3x5 + 4x6 + x7

= 18

xj ≥ 0, j = 1,...,8 Ta có dạng chuẩn xuất phát. Cơ sở

Hệ số

PA CB

x1

x2

x3

x4

x5

x6

x7

x8

3 1

–2 1

–2 0

2 1

4 2

1 0

1 0

x2

3

2

8 1

x8

1

3

[2]

0

1

1

2

1

0

1

x7

–1

18

8

0

6

6

3

4

1

0

B1

f(x) –15 –15

0

–8

9

4

3

0

0

x2

3

1/2

0

1

–3/2

1/2

0

3/2

0

–1/2

x3

2

3/2

1

0

[1/2] 1/2

1

1/2

0

1/2

x7

1

6

0

0

2

–2

5

0

1

4

B2

f(x) 15/2

0

0

–1/2

3/2

11

9/2

0

8

x2

3

5

3

1

0

1

3

3

0

1

x3

2

3

2

0

1

1

2

1

0

1

x7

1

0

4

0

0

0

9

2

1

6

B3

f(x)

9

1

0

0

1

12

5

0

8

Ở bảng thứ 3 ta có ∆k > 0 với mọi biến phi cơ sở, BT kết thúc với PATƯ duy nhất là: X = (0, 5, 3, 0, 0, 0, 0, 0) và fmax = 9. Nhận xét: Ở bước cải tiến PACB không nhất thiết ta phải chọn biến có ước lượng dương lớn nhất với BT fmin, hoặc âm nhỏ nhất với BT fmax để đưa vào cơ sở nhưng điều kiện chọn phần tử trục: {arv > 0 và br/arv nhỏ nhất} (*) phải được đảm bảo với cả bài toán fmin và fmax. Thực chất, khi đưa biến có ∆k > 0 vào cơ sở thì giá trị hàm mục tiêu giảm xuống, ngược lại khi đưa biến có ∆k < 0 thì giá trị hàm mục tiêu tăng lên (xem phần chứng minh thuật toán). Để cải thiện hàm mục tiêu nhiều nhất (khi đó số bảng sẽ ít nhất) thì ngoài điều kiện (*) ta - 27 -

cần có điều kiện nữa là │br.Δv/arv│ lớn nhất, nhưng điều kiện này mất thêm thời gian kiểm tra nên thường ta chọn theo điều kiện │Δv│ lớn nhất. Trở lại ví dụ trên, ở bảng 1, các biến có ∆k < 0 là x1, x3, x5, x6, ta có thể chọn phần tử trục trên 1 trong 4 cột đó. Trong các phần tử thỏa mãn điều kiện (*) (các số được gạch chân) nếu ta chọn a23 = 1 làm phần tử trục thì sẽ cải thiện hàm mục tiêu nhanh nhất và BT sẽ kết thúc ở bảng thứ 2. 1.3.5. Trường hợp bài toán quy hoạch tuyến tính không có dạng chuẩn Ta sẽ giải BT QHTT không có dạng chuẩn bằng phương pháp dùng bài toán phụ (còn gọi là phương pháp 2 pha). Trước hết ta chuyển về bài toán dạng chính tắc với mọi bi ≥ 0 (nếu ràng buộc nào có vế phải âm thì ta đổi dấu hai vế). Nếu ràng buộc thứ i chưa có biến cơ sở thì ta cộng thêm một biến giả zi vào vế trái. Lập bài toán phụ với hàm mục tiêu: P  

z

i

 min(max) , trong đó dấu + với mục

tiêu min, dấu  với mục tiêu max. Ký hiệu bài toán gốc ban đầu là bài toán (G), bài toán phụ dạng chuẩn với các biến giả là bài toán (P). Bài toán gốc ban đầu (G): n

Bài toán phụ (P):

f x    c j x j  min (max)

P    z i  min (max)

 n a ij x j  b i (i  1, m)   j1  x  0 (j  1, n )   j

 n  a ij x j  z i  bi (i  1,m)  j1  x , z  0 (j  1,n; i = 1, m)  j i

j1

Đầu tiên ta giải BT phụ (P) sau đó BT gốc (G). Dễ thấy BT (P) luôn có PATƯ (tồn tại PACB xuất phát và bị chặn). Có các trường hợp xảy ra: i) Nếu PTƯ ≠ 0 thì (G) không có PA, do đó cũng không có PATƯ. ii) Nếu PTƯ = 0 và tất cả các biến giả đều bị loại khỏi cơ sở thì BT (P) dừng lại, pha 1 kết thúc, ta tiếp tục pha 2 giải BT (G) với PACB cuối cùng của BT (P). iii) Nếu PTƯ = 0 và tồn tại zi = 0 trong cơ sở thì ta loại các biến có ∆k < 0 với BT tìm min (∆k > 0 với BT tìm max) và tiếp tục giải BT (G) với các biến còn lại. Lưu ý khi giải BT phụ: Khi một biến giả bị loại ra khỏi cơ sở thì sẽ bị loại vĩnh viễn, có nghĩa là ta sẽ không tính các giá trị trên cột đó nữa. Chứng minh thuật toán: - 28 -

- Các biến giả là các biến ta tạm thời đưa vào để có dạng chuẩn xuất phát. Khi cải tiến PACB, các biến giả sẽ bị loại dần tới khi tất cả các biến giả bằng 0 (P = 0) thì hệ ràng buộc của BT (P) cũng chính là hệ ràng buộc của BT (G). Như vậy ta có PACB xuất phát với BT (G). - Vì sao khi PTƯ ≠ 0 (tức là vẫn tồn tại biến giả > 0) thì BT (G) không có PA? Ta chứng minh bằng phản chứng: Giá trị nhỏ nhất của hàm mục tiêu của Pmin có thể đạt được (nếu có thể) là bằng 0 khi tất cả các biến giả triệt tiêu. Giả sử BT (G) có PA thì BT (P) sẽ có PA mà tất cả các biến giả = 0 (xem hệ ràng buộc của 2 BT ở trên) suy ra Pmin = 0. Vì vậy nếu Pmin > 0 thì bài toán ban đầu (G) không có PA do đó cũng không có PATƯ. - Khi PTƯ = 0 và tồn tại zi = 0 trong cơ sở thì các biến có ước lượng thỏa mãn dấu hiệu tối ưu của BT (P) tức là ∆k < 0 với BT tìm min (∆k > 0 với BT tìm max) sẽ vĩnh viễn không được chọn làm biến cơ sở vì thế ta không cần tính các giá trị trên các cột tương ứng. Ví dụ 1.3.5: Giải bài toán sau bằng phương pháp đơn hình: f(x) = 3x1 + 4x2 + 2x3 + 2x4 → min 2x1 + 2x2 + x4 = 28 x1 + 5x2 + 3x3 − 2x4  31 2x1 – 2x2 + 2x3 + x4 = 16 xj ≥ 0 (j =1…4) Đưa bài toán về dạng chính tắc: f(x) = 3x1 + 4x2 + 2x3 + 2x4 → min 2x1 + 2x2 + x4 = 28 x1 + 5x2 + 3x3 − 2x4 + x5 = 31 2x1 – 2x2 + 2x3 + x4 = 16 xj ≥ 0 (j =1…5) Ta thấy bài toán không phải dạng chuẩn. Ở ràng buộc thứ nhất và thứ ba chưa có biến cơ sở ta thêm vào vế trái các biến giả z1 và z3. Ta lập bài toán phụ: P = z1 + z3 → min 2x1 + 2x2 + x4 + z1 = 28 x1 + 5x2 + 3x3 − 2x4 + x5 = 31 2x1 – 2x2 + 2x3 + x4 + z3 = 16 xj ≥ 0 (j =1…5); z1 và z3 ≥ 0 Ta có dạng chuẩn xuất phát, dùng phương pháp đơn hình để giải bài toán phụ.

- 29 -

Cơ Sở

Hệ Số

PA CB

x1

x2

x3

x4

x5

z1

z3

0 2

0 0

0 1

0 0

1 1

1 0

z1

1

28

0 2

x5

0

31

1

5

3

−2

1

0

0

z3

1

16

[2]

−2

2

1

0

0

1

B1

P

44

4

0

2

2

0

0

0

z1

1

12

0

[4]

−2

0

0

1

x5

0

23

0

6

2

−5/2

1

0

x1

0

8

1

−1

1

1/2

0

0

B2

P

12

0

4

−2

0

0

0

x2

0

3

0

1

−1/2

0

0

x5

0

5

0

0

5

−5/2

1

x1

0

11

1

0

1/2

1/2

0

B3

P

0

0

0

0

0

0

Ở bảng thứ 3 cả 2 biến giả đã bị loại, BT (P) kết thúc. Ta tiếp tục pha 2, giải BT (G) với PACB cuối cùng của BT (P). Cơ Sở

Hệ Số

PA CB

x1

x2

x3

x4

x5

4 1

2 −1/2

2 0

0 0

x2

4

3

3 0

x5

0

5

0

0

5

−5/2

1

x1

3

11

1

0

1/2

1/2

0

B5

f(x)

45

0

0

−5/2 −1/2

0

Sau khi tính lại các ước lượng theo hệ số của BT f(x) ta thấy mọi ước lượng của các biến tự do đều < 0 (nếu còn ước lượng dương thì tiếp tục thuật toán). Bài toán kết thúc với fmin = 45 và PATƯ duy nhất là X = (11, 3, 0, 0, 5). Lưu ý: Ta cũng có thể sử dụng bảng đơn hình cuối để giải bài toán với mục tiêu f max. - 30 -

Ví dụ 1.3.6: Giải BT QHTT sau: f(x) = 2x1 + 3x2 + 4x3 + x4 → max x1 + x2 + x3 + x4  5 2x1 + 2x2 + 3x3 = 18 2x1 + x2 + 2x4 ≥ 8 xj ≥ 0 (j =1…4) Đưa bài toán về dạng chính tắc: f(x) = 2x1 + 3x2 + 4x3 + x4  max x1 + x 2 + x 3 + x 4 + x 5 = 5 2x1 + 2x2 + 3x3 = 18 2x1 + x2 + 2x4 – x6 = 8 xj ≥ 0 (j =1…6) Ta thấy bài toán chưa phải là dạng chuẩn. Ở ràng buộc thứ hai và thứ ba chưa có biến cơ sở ta thêm vào vế trái các biến giả z2 và z3. Ta lập bài toán phụ (P): P = – z2 – z3 → max x1 + x2 + x3 + x4 + x5 = 5 2x1 + 2x2 + 3x3 + z2 = 18 2x1 + x2 + 2x4 – x6 + z3 = 8 xj ≥ 0 (j =1…6); z2 và z3 ≥ 0 Lập bảng đơn hình xuất phát cho bài toán (P). Cơ Hệ PA x1 x2 x3 x4 Sở Số CB 0 0 0 0 x5 0 5 1 1 1 1

x5

x6

z2

z3

0 1

0 0

–1 0

–1 0

z2

–1

18

2

2

3

0

0

0

1

0

z3

–1

8

[2]

1

0

2

0

–1

0

1

B1

P

– 26

–4

–3

–3

–2

0

1

0

0

x5

0

1

0

1/2

[1]

0

1

1/2

0

z2

–1

10

0

1

3

–2

0

1

1

x1

0

4

1

1/2

0

1

0

–1/2

0

B2

P

– 10

0

–1

–3

2

0

–1

0

x3

0

1

0

1/2

1

0

1

1/2

0 - 31 -

z2

–1

7

0

–1/2

0

–2

–3

–1/2

1

x1

0

4

1

1/2

0

1

0

–1/2

0

B3

P

–7

0

1/2

0

2

3

1/2

0

Ở bảng cuối ta thấy mọi ∆k ≥ 0, thỏa mãn dấu hiệu tối ưu, nhưng Pmax = – 7 ≠ 0 và trong PACB tương ứng vẫn còn tồn tại thành phần biến giả z2 = 7 > 0, nên BT ban đầu không có PA và như vậy cũng không có PATƯ. Ví dụ 1.3.7: Giải BT QHTT sau: f(x) = – 27x1 – 2x2 – 5x1 – 2x1 – 6x1 + x2 xj

+ x3 + 14x4 + 6x5 + 5x6 → max + 2x4 + x5 + x6 = 5 – x3 – 2x4 + x5 = 2 – 2x3 – x4 + 2x6 = 8 ≥ 0 (j =1…6)

BT trên có dạng chính tắc nhưng chưa phải là dạng chuẩn. Ràng buộc 1 và 2 chưa có biến cơ sở ta sẽ cộng vào vế trái các biến giả z1 và z2. Ta lập BT phụ (P): P = – z1 – z2 → max – 5x1 + 2x4 + x5 + x6 + z1 = 5 – 2x1 – x3 – 2x4 + x5 + z2 = 2 – 6x1 + x2 – 2x3 – x4 + 2x6 = 8 xj ≥ 0 (j =1…6); z1 và z2 ≥ 0 Ta có dạng chuẩn xuất phát: Cơ Hệ PA x1 Sở Số CB 0 z1 –1 5 –5

x2

x3

x4

x5

x6

z1

z2

0 0

0 0

0 2

0 1

0 1

–1 1

–1 0

z2

–1

2

–2

0

–1

–2

[1]

0

0

1

x2

0

8

–6

1

–2

–1

0

2

0

0

B1

P

–7

7

0

1

0

–2

–1

0

0

z1

–1

3

–3

0

1

[4]

0

1

1

x5

0

2

–2

0

–1

–2

1

0

0

x2

0

8

–6

1

–2

–1

0

2

0

B2

P

–3

3

0

–1

–4

0

–1

0 - 32 -

x4

0

3/4

–3/4

0

1/4

1

0

1/4

x5

0

7/2

–7/2

0

–1/2

0

1

1/2

x2

0

35/4 –27/4

1

–7/4

0

0

9/4

B3

P

0

0

0

0

0

0

0

Ở bảng 3 ta thấy cả 2 biến giả đã bị loại và BT (P) kết thúc. Ta tiếp tục pha 2, giải BT (G). Cơ Sở

Hệ Số

PA CB

x1

x2

x3

x4

x5

x6

–2 0

1 1/4

14 1

6 0

5 [1/4]

x4

14

3/4

–27 –3/4

x5

6

7/2

–7/2

0

–1/2

0

1

1/2

x2

–2

35/4 –27/4

1

–7/4

0

0

9/4

B4

f(x)

14

9

0

3

0

0

–3

x6

5

3

−3

0

1

4

0

1

x5

6

2

−2

0

−1

−2

1

0

x2

−2

2

0

1

−4

−9

0

0

B5

f(x)

23

0

0

6

12

0

0

Ở bảng cuối ta có  ∆k ≥ 0, BT kết thúc với fmax = 23 và PATƯ X1 = (0, 2, 0, 0, 2, 3). Nhưng đây không phải là PATƯ duy nhất, ta có x1 là biến phi cơ sở nhưng có ∆1 = 0, ngoài ra mọi ai1 ≤ 0 nên PATƯ tổng quát là nửa đường thẳng (xem đoạn cuối phần chứng minh trang 23). Cho x1 = t ≥ 0 tùy ý, các biến phi cơ sở khác (x3 và x4) bằng 0 và chuyển x1 sang vế phải ta được: x6 = 3 + 3t, x5 = 2 + 2t, x2 = 2 + 0.t = 2. Vậy PATƯ tổng quát là: X = (t, 2, 0, 0, 2 + 2t, 3 + 3t) = X1 + t.(1, 0, 0, 0, 2, 3) với mọi t ≥ 0. Ví dụ 1.3.8: Giải BT QHTT sau : f(x) = 2x1 + 4x2 + 1/2x3 − 3x4 → 2x1 + 2x2 + 3x3 + 3x4  4x1 + 8x2 + 2x3 + 3x4 = 4x1 + 4x2 + x3 + 2x4 = xj ≥ 0 (j =1…4)

min 50 80 40

Đưa BT về dạng chính tắc : - 33 -

f(x) = 2x1 + 4x2 + 1/2x3 − 3x4 → min 2x1 + 2x2 + 3x3 + 3x4 + x5 = 50 4x1 + 8x2 + 2x3 + 3x4 = 80 4x1 + 4x2 + x3 + 2x4 = 40 xj ≥ 0 (j =1…5) Cộng các biến giả z2 và z3 lần lượt vào ràng buộc 2 và 3. Ta lập BT phụ (P): P = z2 + z3 → min 2x1 + 2x2 + 3x3 + 3x4 + x5 = 50 4x1 + 8x2 + 2x3 + 3x4 + z2 = 80 4x1 + 4x2 + x3 + 2x4 + z3 = 40 xj ≥ 0 (j =1…5) ; z2 và z3 ≥ 0 Ta có dạng chuẩn xuất phát : Cơ Sở

Hệ Số

PA CB

x1

x2

x3

x4

x5

z2

z3

0 2

0 3

0 3

0 1

1 0

1 0

x5

0

50

0 2

z2

1

80

4

8

2

3

0

1

0

z3

1

40

4

[4]

1

2

0

0

1

B1

P

120

8

12

3

5

0

0

0

x5

0

30

0

0

5/2

2

1

0

z2

1

0

−4

0

0

−1

0

1

x2

0

10

1

1

1/4

1/2

0

0

B2

P

0

−4

0

0

−1

0

0

Ở bảng 2 ta có dấu hiệu tối ưu của BT (P) và P = 0, nhưng vẫn có z2 = 0 trong cơ sở. Ta loại các biến có ∆k < 0 của BT (P), đó là x1 và x4, tiếp tục giải BT (G) với các biến còn lại. Cơ Sở x5 z2

Hệ Số 0

PA CB

x1

x2

x3

x4

x5

30

2 \

4 0

1/2 [5/2]

−3 \

0 1

0

\

0

0

\

0 - 34 -

x2

4

10

\

1

1/4

\

0

B4

f(x)

40

\

0

1/2

\

0

x3

1/2

12

\

0

1

\

2/5

0

\

0

0

\

0

z2 x2

4

7

\

1

0

\

−1/10

B5

f(x)

34

\

0

0

\

−1/5

Ở bảng cuối ta có dấu hiệu tối ưu của BT (G), BT kết thúc với f(x)min = 34 và PATƯ duy nhất là X = (0, 7, 12, 0, 0).

1.4. Bài toán quy hoạch tuyến tính đối ngẫu 1.4.1. Khái niệm về bài toán đối ngẫu Ví dụ 1.4.1: Bài toán mặc cả mua bán nguyên vật liệu Ta quay lại bài toán lập kế hoạch sản xuất vải của xí nghiệp X. Mức tiêu hao nguyên liệu để sản xuất ra 1 mét vải A, B, C và giá bán một mét mỗi loại được cho trong bảng sau: Nguyên liệu

Hiện có

A

B

C

Cotton (kg)

5500 kg

0.5

0.8

0.6

Polyester (kg)

3800 kg

0.4

0.3

0.2

27

36

30

Giá bán (nghìn/ m)

Gọi x1, x2, x3 là số mét vải A, B, C cần sản xuất. Ta có bài toán: f(x) = 27x1 + 36x2 + 30x3 → max 0.5x1 + 0.8x2 + 0.6x3 ≤ 5500 0.4x1 + 0.3x2 + 0.2x3 ≤ 3800 x1, x2, x3  0 Giả sử có doanh nghiệp Y muốn mua toàn bộ nguyên vật liệu thì hai bên sẽ thỏa thuận giá cả như thế nào để hai bên cùng có lợi. Gọi y1 là giá bán 1 kg Cotton (nghìn/kg), y2 là giá bán 1 kg Polyester (nghìn/kg). Đối với người mua, tổng số tiền bỏ ra phải là ít nhất tức là: 5500y1 + 3800y2 → min. - 35 -

Đối với người bán, giá bán nguyên vật liệu cho 1 mét vải phải không ít hơn giá 1 mét vải thành phẩm có nghĩa là: 0.5y1 + 0.4y2 ≥ 27 0.8y1 + 0.3y2 ≥ 36 0.6y1 + 0.2y2 ≥ 30 Giá bán không thể âm nên y1 ≥ 0 và y2 ≥ 0. Như vậy để thuận mua vừa bán thì hai bên cần giải bài toán sau: f (y) = 5500y1 + 3800y2 → min

0.5y1 + 0.4y2 ≥ 27 0.8y1 + 0.3y2 ≥ 36 0.6y1 + 0.2y2 ≥ 30 yj ≥ 0 j = 1,2 Ta gọi bài toán trên là đối ngẫu của bài toán f(x). Ví dụ 1.4.2: Bài toán của người sản xuất chất dinh dưỡng Ta quay lại bài toán dinh dưỡng của người thợ mỏ. Để đảm bảo chất dinh dưỡng cho mỗi người thợ mỏ mỗi ngày, để có thể sinh hoạt và làm việc bình thường, cần tiêu thụ ít nhất 60g protit, 50g lipid và 70g glucid. Các thành phần dinh dưỡng này có trong 1g cá và 1g thịt như trong bảng dưới đây. Biết rằng giá 1g cá và 1g thịt là 40 và 90 VNĐ. Chất dinh dưỡng

Cá

Thịt

Protit (gam)

0.2

0.4

Lipid (gam)

0.25

0.1

Glucid (gam)

0.4

0.3

Vậy mỗi ngày ta cần mua bao nhiêu gam thịt, cá sao cho số tiền phải chi là ít nhất nhưng vẫn đảm bảo lượng dinh dưỡng cần thiết. Gọi x1 và x2 là số gam cá thịt cần mua trong ngày (x1, x2 ≥ 0). Ta cần giải bài toán sau: tìm x1, x2 sao cho: f(x) = 40x1 + 90x2 → min 0.2x1 + 0.4x2 ≥ 60 0.25x1 + 0.1x2 ≥ 50 0.4x1 + 0.3x2 ≥ 70 x1, x2 ≥ 0 - 36 -

Giả sử có Doanh nghiệp Y sản xuất các thành phần dinh dưỡng trên dưới dạng bột. Để xác định đơn giá của các chất dinh dưỡng trên thì người sản xuất và người tiêu dùng cùng thỏa thuận để 2 bên cùng có lợi. Gọi y1, y2, y3 lần lượt là giá 1 gam protit, lipid, glucid. Đối với nhà sản xuất, số tiền bán chất dinh dưỡng cho 1 người/ngày phải là lớn nhất, tức là: 60y1 + 50y2 + 70y3 → max. Đối với người mua, số tiền để mua chất dinh dưỡng tương đương với 1 gam cá, thịt phải không nhiều hơn giá 1 gam cá, thịt tươi. Tức là: 0.2y1 + 0.25y2 + 0.4y3 ≤ 40 0.4y1 + 0.1y2 + 0.3y3 ≤ 90 Giá bán không thể âm nên y1 ≥ 0, y2 ≥ 0 và y3 ≥ 0. Như vậy nhà sản xuất chất dinh dưỡng cần giải bài toán sau: f (y) = 60y1 + 50y2 + 70y3 → max

0.2y1 + 0.25y2 + 0.4y3 ≤ 40 0.4y1 + 0.1y2 + 0.3y3 ≤ 90 yj ≥ 0 j = 1...3 Ta cũng có bài toán f (y) là đối ngẫu của bài toán f(x). Từ 2 ví dụ trên, ta thành lập quy tắc đối ngẫu tổng quát như sau : 1.4.2. Quy tắc thành lập bài toán đối ngẫu - Nếu ở bài toán gốc f(x) → min thì ở bài toán đối ngẫu ta có f (y) → max và ngược lại. - Số ràng buộc chung trong bài toán này bằng số biến số trong bài toán kia, nghĩa là tương ứng với một ràng buộc chung của bài toán này là một biến số của bài toán kia. - Hệ số hàm mục tiêu của bài toán này là vế phải của ràng buộc chung trong bài toán kia. - Ma trận hệ số ràng buộc chung trong hai bài toán là chuyển vị của nhau. - Các ràng buộc của bài toán này và các biến tương ứng của bài toán kia phải thỏa mãn các điều kiện sau: Bài toán gốc (G)

Bài toán đối ngẫu (D) m

n

f (y)   bi yi  max

f(x)   c j x j  min j1

i=1

n

yi .( a i j x j  bi )  0; i  1,..., m j=1 m

x j .( a i j yi  c j )  0

và

j  1,..., n

i=1

- 37 -

n

a

Tức là nếu

ij

x j  bi thì yi ≥ 0, nếu xj ≥ 0 thì

nếu

a

ij

a

y  cj ,

ij i

i=1

j=1

n

m

m

a

x j  bi thì yi tùy ý, nếu xj tùy ý thì

j=1

y =c j .

ij i

i=1

Trường hợp ngược lại: Bài toán gốc (G)

Bài toán đối ngẫu (D)

n

f (x)   c j x j  max

m

f (y)   bi yi  min

j=1

n

i=1

yi .( a i j x j  bi )  0; i  1,..., m j=1

m

x j .( a i j yi  c j )  0

và

j  1,..., n

i 1

Nhận xét: Các quy tắc đối ngẫu trên có thể diễn tả một cách đơn giản như sau: -

Các ràng buộc chung của bài max trái dấu với biến tương ứng của bài toán min.

-

Các ràng buộc chung của bài min cùng dấu với biến tương ứng của bài toán max.

-

Các ràng buộc chặt của bài toán này tương ứng với biến tùy ý của bài toán kia. Các cặp ràng buộc trên được gọi là các cặp ràng buộc đối ngẫu. Lưu ý: Đối ngẫu của bài toán (D) lại chính là bài toán (G).

Ví dụ 1.4.3: Viết bài toán đối ngẫu của bài toán sau: f(x) = − 4x1 + x2 + 5x3 +

3x5 → min

3x1 − 6x2 − x3 + 2x4 + 4x5 ≥ –15 −2x1 + 3x2 + 4x3 − 5x4 + x5  8 − 6x2 + 3x3 + 8x4 − 4x5 =

9

− 3x4 + x5 ≥ 24

3x1 + 2x2

x1, x3, x5 ≥ 0 , x4 ≤ 0, x2 tuỳ ý. Bài toán đối ngẫu sẽ là:

f (y) = –15y1 + 8y2 + 9y3 + 24y4 → max 3y1 − 2y2

+ 3y4

 –4 (vì x1 ≥ 0)

−6y1 + 3y2 − 6y3 + 2y4

=

− y1

 5 (vì x3 ≥ 0)

+ 4y2 + 3y3

1 (vì x2 tùy ý)

- 38 -

2y1

− 5y2 + 8y3

4y1

+

y2

– 3y4

≥ 0 (vì x4 ≤ 0)

− 4y3 + y4

 3 (vì x5 ≥ 0)

y1 ≥ 0, y4 ≥ 0 (vì các ràng buộc 1và 4 của BT (G) có dấu ≥), y2 ≤ 0 (vì các ràng buộc 2 của BT (G) có dấu ≤), y3 tuỳ ý (vì các ràng buộc 3 của BT (G) là ràng buộc chặt). Ví dụ 1.4.4: Viết bài toán đối ngẫu của bài toán sau: f(x) = 14x1 + 12x2 + 17x3 → max 3x1 + 5x2 + 4x3 ≤ 35 2x1 + 3x2 + 6x3 = 30 5x1 + 2x2 + 3x3 ≥ 50 x1 ≥ 0, x2 ≤ 0, x3 tuỳ ý Tương tự, dựa vào lược đồ trên ta có bài toán đối ngẫu:

f (y) = 35y1 + 30y2 +50y3 → min 3y1 + 2y2 + 5y3 ≥ 14 5y1 + 3y2 + 2y3 ≤ 12 4y1 + 6y2 + 3y3 = 17 y1 ≥ 0, y2 tuỳ ý, y3 ≤ 0 Lưu ý: Nếu BT gốc ở dạng chính tắc thì BT đối ngẫu có dạng : Bài toán gốc (G)

Bài toán đối ngẫu (D)

n

f(x)   c j x j  min

f (y) =  bi yi  max

j=1

n

a

m

ij

x j  bi

i=1

yi tùy ý, với i = 1, m

j=1

m

a

xj ≥ 0 Ngược lại : Bài toán gốc (G) n

f(x)   c j x j  max

yi  c j , với j = 1, n

i=1

Bài toán đối ngẫu (D) m

f (y) =  bi yi  min i=1

j=1

n

a

ij

ij

x j  bi

yi tùy ý, với i = 1, m

j=1

m

xj ≥ 0

a

y  c j , với j = 1, n

ij i

i=1

- 39 -

Như vậy, để cho đơn giản khi viết BT đối ngẫu, trước hết ta đưa BT (G) về dạng chính tắc. Lưu ý: Bài toán (G) ở dạng tổng quát hay dạng chính tắc đều có chung một bài toán đối ngẫu (D). Ví dụ 1.4.5: Viết bài toán đối ngẫu của BT sau: f(x) = − x1 + 2x2 + 3x3 + 4x4 → max 2x1 − 3x2 + x3 − 2x4 ≥ − 5 − x1 + 4x2 + 2x3 − 5x4  7 − 6x2 + 3x3 + x4 = 8 xj ≥ 0, j = 1,...,4 Trước tiên ta đưa bài toán về dạng chính tắc: f(x) = − x1 + 2x2 + 3x3 + 4x4 → max 2x1 − 3x2 + x3 − 2x4 − x5

= −5

− x1 + 4x2 + 2x3 − 5x4

+ x6 = 7

− 6x2 + 3x3 + x4

= 8

xj ≥ 0, j = 1,...,6 Bài toán đối ngẫu có dạng:

f (y) = − 5y1 + 7y2 + 8y3 → min 2y1 − y2

≥−1

− 3y1 + 4y2 − 6y3 ≥ 2 y1 + 2y2 + 3y3 ≥ 3 − 2y1 − 5y2 + y3 ≥ 4 − y1

≥0 ≥0

y2

1.4.3. Các định lý đối ngẫu Trong các định lý dưới đây ta giả thiết bài toán (G) là f(x) → min. Định lý 1.4.1: Nếu X và Y là 2 PA bất kỳ của cặp bài toán đối ngẫu thì ta luôn có f(X) ≥

f (Y). Dấu bằng xảy ra khi và chỉ khi X và Y là các PATƯ, có nghĩa là f(x)min = f (y)max. Chứng minh: Để cho đơn giản, ta giả thiết f(x) có dạng chính tắc. Ta có: n

n

m

m

n

m

j=1

j=1

i=1

i=1

j=1

i=1

f(x)= c j x j   ( a ij yi ).x j = ( a ijx j ).yi =  bi yi =f (y) . Đpcm. - 40 -

Trong chứng minh trên ta sử dụng BĐT c j 

m

a y

ij i

là các ràng buộc của BT f (y)

i=1

(xem lược đồ trên). Giả sử f(X0) = f (Y0) = d. Ta có f(X) ≥ f (Y0) = d với mọi PA X suy ra d chính là giá trị nhỏ nhất của BT f(x). Tương tự d cũng chính là giá trị lớn nhất của BT

f (y). Do đó X0 và Y0 là các PATƯ của cặp BT đối ngẫu trên. Hệ quả 1.4.1: Nếu mỗi BT (G) và BT (D) đều có ít nhất 1 PA thì cả 2 BT cùng có PATƯ (vì hàm mục tiêu bị chặn). Định lý 1.4.2: Nếu bài toán này có PATƯ thì bài toán kia cũng có PATƯ và ngược lại nếu bài toán này không có PATƯ thì bài toán kia cũng không có PATƯ. Hệ quả 1.4.2: Nếu BT này có hàm mục tiêu không bị chặn thì BT đối ngẫu của nó không có PA và ngược lại. Định lý 1.4.3: Điều kiện cần và đủ để X0 và Y0 là các PATƯ khi và chỉ khi X0 và Y0 là các PA và thoả mãn: m   x j .( a i j yi  c j )  0; j  1, n  i=1  n  y .( a x  b )  0 i = 1,m i  i j1 i j j

Tức là nếu biến số của bài toán này là khác 0 thì ràng buộc chung tương ứng của bài toán kia phải là ràng buộc chặt, nếu ràng buộc chung của bài toán này là lỏng thì biến tương ứng của bài toán kia phải bằng 0. Chứng minh: Theo định lý 1 thì ta phải có f(X0) = f (Y0). Ta có: m

n

m

n

n

i=1

j=1

i=1

j=1

j=1

f (Y0 ) – f(X 0 )=  bi yi –  c j x j =  ( a ijx j ).yi –  c jx j = n

m

j=1

i=1

 ( a

ij

n

n

m

j=1

j=1

i=1

yi ).x j –  c j x j =  x j .( a ij yi – c j ) = 0

Ta thấy biểu thức cuối cùng là tổng của n số hạng ≤ 0 (xem quy tắc đối ngẫu ở trang 38, 39), nó bằng 0 khi và chỉ khi tất cả các số hạng đó bằng 0, có nghĩa là: m

x j .( a ij yi  c j )  0 , với mọi j = 1…n. Tương tự có thể chứng minh phần còn lại của i 1

định lý trên. Ví dụ 1.4.6: Giải BT QHTT sau bằng cách giải BT đối ngẫu của nó: f(x) = 8x1 + 10x2 + 5x3 → min - 41 -

≥ 6

2x1 + x2

+ 2x3 ≥ 4

x1

≥ 10

2x1 + 3x2

2x2 + x3 ≥ 7 x1, x2, x3 ≥ 0 Ta có BT đối ngẫu:

f (y) = 6y1 + 4y2 + 10y3 + 8y4 → max 2y1 +

 8

y2 + 2y3

+ 3y3 + 2y4  10

y1 2y2

+

y4  5

yi ≥ 0, i = 1...4. Dạng chính tắc của BT đối ngẫu :

f (y) = 6y1 + 4y2 + 10y3 + 7y4 → max 2y1 +

y2 + 2y3

y1

+ y5

+ 3y3 + 2y4 2y2

+

= 8 + y6

y4

= 10 + y7 = 5

yi ≥ 0, i = 1...7. Ta có dạng chuẩn xuất phát : Cơ Sở

Hệ Số

PA CB

y1

y2

y3

y4

y5

y6

y7

4 1

10 2

7 0

0 1

0 0

0 0

y5

0

8

6 2

y6

0

10

1

0

3

2

0

1

0

y7

0

5

0

2

0

[1]

0

0

1

B1

f (y)

0

–6

–4

– 10

–7

0

0

0

y5

0

8

2

1

2

0

1

0

0

y6

0

0

[1]

–4

3

0

0

1

–2

y4

7

5

0

2

0

1

0

0

1

B2

f (y)

35

–6

10

– 10

0

0

0

7 - 42 -

y5

0

8

0

[9]

–4

0

1

–2

4

y1

6

0

1

–4

3

0

0

1

–2

y4

7

5

0

2

0

1

0

0

1

B3

f (y)

35

0

– 14

8

0

0

6

–5

y2

4

8/9

0

1

–4/9

0

1/9

–2/9

4/9

y1

6

32/9

1

0

11/9

0

4/9

1/9

–2/9

y4

7

29/9

0

0

8/9

1

–2/9

4/9

1/9

f (y) 427/9

0

0

16/9

0

14/9 26/9

11/9

B4

Ở bảng cuối ta có dấu hiệu tối ưu, f (y)max = 427/9 và PATƯ Y0 = (32/9, 8/9, 0, 29/9, 0, 0). Theo định lý 1.4.1 thì f(x)min = f (y)max = 427/9, còn PATƯ của BT (G) được xác định dựa vào định lý 1.4.3, cụ thể là : y1 > 0 → 2x1 + x2 y2 > 0 → x1 y4 > 0 →

= 6 + 2x3 = 4

2x2 + x3 = 7

Giải hệ trên ta được X0 = (14/9, 26/9, 11/9). Thay X0 vào các ràng buộc của BT (G) ta thấy thỏa mãn nên X0 là PA của BT (G). Thay vào phần còn lại của định lý 1.4.3 cũng thỏa mãn. Vậy X0 = (14/9, 26/9, 11/9) là PATƯ của BT (G). Ví dụ 1.4.7: Cho BT QHTT : f(x) = 2x1 2x1 − 2x1 x1

− − + −

24x2 3x2 2x2 3x2 xj

+ 12x3 + 14x4 → max − 2x3 + 2x4 = 16 + 3x3 ≤ −2 + 2x4 = 20 ≥ 0 (j =1…4)

và vectơ X0 = (20, 0, 12, 0). Hãy viết BT đối ngẫu và chứng tỏ X0 là PATƯ của BT gốc. Giải : BT đối ngẫu (D) có dạng :

f (y) = 16y1 − 2y2 + 20y3 → min 2y1 − 2y2 +

y3 ≥

2

− 3y1 + 2y2 − 3y3 ≥ − 24 − 2y1 + 3y2 2y1

≥ 12 + 2y3 ≥ 14 - 43 -

y2 ≥ 0. Ta thấy X0 thỏa mãn tất cả các ràng buộc của BT (G) nên nó là PA của BT (G). Giả sử X0 là PATƯ của BT (G), theo định lý 1.4.3, ta có : x1 > 0 →

2y1 − 2y2 +

x3 > 0 → − 2y1 + 3y2

y3 = 2 = 12

ràng buộc 2 của BT (G) lỏng → y2 = 0. Giải hệ trên ta có nghiệm Y0 = (−6, 0, 14). Thay vào BT (D) ta thấy Y0 thỏa mãn mọi ràng buộc nên nó là PA của BT (D). Thay X0 và Y0 vào các hàm mục tiêu ta có : f(X0) = f (Y0) = 184. Theo định lý 1.4.1 thì X0 và Y0 là các PATƯ của cặp BT đối ngẫu trên. 1.4.4. Thuật toán của phương pháp đơn hình đối ngẫu Thuật toán đơn hình đối ngẫu được áp dụng cho BT QHTT dạng chuẩn tắc nhưng chưa phải là dạng chuẩn, tức là mỗi ràng buộc đều có một biến cơ sở nhưng tồn tại ràng buộc có vế phải âm. Như vậy ta chưa có PACB xuất phát. Nếu mọi ước lượng thỏa mãn điều kiện tối ưu, tức là mọi ∆k ≤ 0 với BT tìm min hoặc mọi ∆k ≥ 0 với BT tìm max, thì PA với thành phần âm đó được gọi là giả phương án (GPA), hoặc PA chấp nhận đối ngẫu, bởi vì ứng với giả PA đó ta có tương ứng 1 PACB của BT đối ngẫu. Thật vậy, nếu hệ biến cơ sở của m BT gốc là {x1, x2,.., xm} và với mọi Δk ≤ 0 trong BT f(x)min ↔ a c  c 0 m



a

ij

i

k

i=1

c  c k với mọi k, thỏa mãn mọi ràng buộc của BT (D) suy ra Y = (c1, c2,.., cm) là

ij i

i=1

PACB của BT đối ngẫu. a. Trường hợp có giả phương án xuất phát Thuật toán đơn hình đối ngẫu luôn đảm bảo các ước lượng thỏa mãn dấu hiệu tối ưu. Ta sẽ loại dần các giá trị bi âm tới khi bi ≥ 0 thì BT kết thúc. Thuật toán gồm các bước sau: Bước 1: Lập bảng đơn hình với giả PA xuất phát. Lưu ý: Vì là giả PA nên ∆0 không phải là giá trị thực của f(x), thực chất đó chính là giá trị f (y) của BT (D). Vì vậy, ở hàng đặc trưng ta viết f (y) thay cho f(x). Bước 2: Kiểm tra PACB - Nếu bi ≥ 0 thì thuật toán kết thúc, GPA trở thành PACB và cũng chính là PATƯ. - Nếu  bi < 0 mà tất cả các phần tử trên hàng đó đều không âm thì bài toán không có PA (vì phương trình thứ i có một vế âm, một vế không âm). - Nếu với  bi < 0 đều có ít nhất một phần tử âm trên hàng đó thì ta chuyển sang bước 3.

- 44 -

Bước 3: Trong các bi âm ta chọn bi có giá trị âm nhỏ nhất. Giả sử đó là br, ta chọn hàng r làm hàng xoay. Trên hàng xoay đó ta chọn phần tử trục là phần tử arj < 0 với tỷ số  j /a rj là nhỏ nhất. Giả sử đó là arv .Thực hiện phép khử Gauss-Jordan với phần tử trục arv sau đó quay lại bước 2. Lưu ý: - Lý do chọn phần tử trục arj < 0 là để khi chia hàng xoay cho arj, br sẽ trở về dương. - Điều kiện  j /a rj nhỏ nhất để đảm bảo khi thực hiện quy tắc hình chữ nhật, dấu hiệu tối ưu vẫn được giữ nguyên sang bảng sau. Ví dụ 1.4.8: Giải bài toán sau bằng phương pháp đơn hình đối ngẫu. Viết BT đối ngẫu và tìm PATƯ của nó. f(x) = x1 + 3x2 + 2x3 + 3x4 + 5x5 → min x1 + 2x2 − x3 + x4 −

x5 = −3

− x2 − x3 + 2x4 + 4x5 ≥ 18 + 2x5  10

− x2 − 3x3 xj ≥ 0 (j = 1…5) Đưa bài toán về dạng chính tắc:

f(x) = x1 + 3x2 + 2x3 + 3x4 + 5x5 → min x1 + 2x2 − x3 + x4 −

x5

= −3

− x2 − x3 + 2x4 + 4x5 – x6 − x2 − 3x3

+ 2x5

= 18 +x7 = 10

xj ≥ 0 (j = 1…7) Đổi dấu hai vế ràng buộc thứ 2 để được dạng chuẩn tắc. Lập bảng đơn hình tương ứng, tính các ước lượng ta thấy ∆k ≤ 0 nên ta có GPA xuất phát với các biến cơ sở là {x1, x6, x7}. Cơ Hệ GPA x1 x2 x3 x4 x5 x6 x7 sở số 1 3 2 3 5 0 0 x1 1 −3 1 2 −1 1 −1 0 0 x6

0

−18

0

1

1

[− 2]

−4

1

0

x7

0

10

0

−1

−3

0

2

0

1

B1

f (y)

−3

0

−1

−3

−2

−6

0

0

- 45 -

Ở bảng 1 ta chọn hàng 2 là hàng xoay vì có b2 = −18 âm nhỏ nhất. Trên hàng xoay ta chọn phần tử trục là a24 = − 2 vì thỏa mãn a24 < 0 và│∆4/a24│=│−2/−2│= 1 là nhỏ nhất. Thực hiện phép khử Gauss − Jordan với phần tử trục này ta có bảng sau: Cơ Sở

Hệ Số

GPA

x1

x2

x3

x4

x5

x6

x7

3 5/2

2 −1/2

3 0

5 [−3]

0 1/2

0 0

x1

1

−12

1 1

x4

3

9

0

−1/2

−1/2

1

2

−1/2

0

x7

0

10

0

−1

−3

0

2

0

1

B2

f (y)

15

0

−2

−4

0

−2

−1

0

x5

5

4

−1/3

−5/6

1/6

0

1

−1/6

0

x4

3

1

2/3

7/6

5/6

1

0

−1/6

0

x7

0

2

2/3

2/3

−10/3

0

0

1/3

1

B3

f (y)

23

−2/3

−11/3

−11/3

0

0

−4/3

0

Ở bảng cuối ta có bi ≥ 0 và Δk ≤ 0 nên ta có fmin = 23 và PATƯ duy nhất là X = (0, 0, 0, 1, 4, 0, 2). Để tìm PATƯ của bài toán đối ngẫu, trước tiên ta viết BT (D) dựa vào dạng chính tắc ban đầu của BT (G):

f (y) = − 3y1 + 18y2 + 10y3 → max ≤ 1

y1

2y1 − y2 − y3 ≤ 3 − y1 − y2 − 3y3 ≤ 2 y1 + 2y2

≤ 3

− y1 + 4y2 + 2y3 ≤ 5 − y2

≤ 0 y3 ≤ 0

- 46 -

m

Áp dụng định lý đối ngẫu 1.4.3: x j .(

a

ij

yi  c j ) = 0 , với mọi j. Tức là nếu xj > 0

i=1

m

thì: ( a i j yi  c j ) = 0 . Phần còn lại của định lý luôn đúng vì BT (G) ở dạng chính tắc. i=1

Trong PATƯ của BT (G) ta có x4, x5, x7 > 0. Tương ứng ta có : y1 + 2y2

=3

− y1 + 4y2 + 2y3 = 5

(Các ràng buộc tương ứng với x4, x5, x7 là ràng buộc chặt).

y3 = 0 Giải hệ trên ta có : y1 = 1/3, y2 = 4/3, y3 = 0 suy ra Y = (1/3, 4/3, 0). Thay vào các ràng buộc của BT (D) ta thấy thỏa mãn nên Y = (1/3, 4/3, 0) là PA và cũng là PATƯ của BT (D). Ví dụ 1.4.9: Giải BT QHTT sau bằng phương pháp đơn hình đối ngẫu. Tìm PATƯ của BT đối ngẫu của nó (nếu có). f(x) = 3x1 + 2x2 + 3x3 + 5x4 + 2x5 → max x1 + x2 + 2x3 + 2x4

≤ 18

2x1 + 2x2 + 3x3 + 4x4 + x5 = 12 x1 + 2x2 + 2x3 + 3x4

≥ 20

xj ≥ 0 (j = 1,…,5) Đưa BT về dạng chính tắc: f(x) = 3x1 + 2x2 + 3x3 + 5x4 + 2x5 → max x1 + x2 + 2x3 + 2x4

+ x6

2x1 + 2x2 + 3x3 + 4x4 + x5

= 18 = 12 − x7 = 20

x1 + 2x2 + 2x3 + 3x4 xj ≥ 0 (j = 1,…,7)

Đổi dấu 2 vế ràng buộc 3 ta sẽ có dạng chuẩn tắc với các biến cơ sở: x5, x6, x7. f(x) = 3x1 + 2x2 + 3x3 + 5x4 + 2x5 → max x1 + x2 + 2x3 + 2x4 2x1 + 2x2 + 3x3 + 4x4 + x5 − x1 − 2x2 − 2x3 − 3x4

+ x6

= 18 = 12 + x7 = −20

xj ≥ 0 (j = 1,…,7) Lập bảng đơn hình, tính các ước lượng ta thấy chúng thỏa mãn dấu hiệu tối ưu nên ta có GPA xuất phát.

- 47 -

Cơ sở

Hệ số

GPA

x1

x2

x3

x4

x5

x6

x7

2 1

3 2

5 2

2 0

0 1

0 0

x6

0

18

3 1

x5

2

12

2

2

3

4

1

0

0

x7

0

− 20

[− 1]

−2

−2

−3

0

0

1

B1

f (y)

24

1

2

3

3

0

0

0

x6

0

−2

0

−1

0

−1

0

1

1

x5

2

− 28

0

[− 2]

−1

−2

1

0

2

x1

3

20

1

2

2

3

0

0

−1

B2

f (y)

4

0

0

1

0

0

0

1

x6

0

12

0

0

1/2

0

− 1/2

1

0

x2

2

14

0

1

1/2

1

− 1/2

0

−1

x1

3

−8

1

0

1

1

1

0

1

B3

f (y)

4

0

0

1

0

0

0

1

Ở bảng cuối ta thấy hàng thứ 3 có b3 = − 8 < 0, nhưng mọi phần tử trên hàng đó đều không âm (a3j ≥ 0) suy ra phương trình đó không có nghiệm dương (một vế âm, một vế dương). Vì vậy bài toán trên không có PA do đó cũng không có PATƯ. Theo hệ quả 1.4.2 thì BT đối ngẫu của nó có hàm mục tiêu không bị chặn và cũng không có PATƯ. b. Trường hợp không có giả PA xuất phát Nếu tồn tại ước lượng không thỏa mãn dấu hiệu tối ưu thì ta thêm vào một ràng buộc giả: z + ∑ xk = M, với mọi xk có ước lượng không thỏa mãn điều kiện tối ưu và M là số dương đủ lớn. Như vậy trong hệ biến cơ sở có thêm biến z. Ở cột GPA ta tách ra thành 2 cột: cột đơn vị và cột hệ số M. Để có giả PACB xuất phát ta chọn trên ràng buộc giả phần tử trục ứng với ước lượng vi phạm nhiều nhất (∆k dương lớn nhất với BT tìm min, hoặc ∆k âm nhỏ nhất với BT tìm max). Thực hiện phép khử Gauss – Jordan với phần tử trục này ta sẽ có giả PACB xuất phát. Lưu ý : Khi xét dấu của bi ta để ý dấu trên cột hệ số M trước tiên. - 48 -

Ví dụ 1.4.10: GPA Đ/vị M –8 1 5 0 26 –3 30 2 Ta có b1 = M – 8 > 0, b2 = 5 > 0, b3 = – 3M + 26 < 0, ∆0 = 2M + 30. Ví dụ 1.4.11: Vẫn bài toán ở ví dụ 1.4.8 nhưng ta tìm giá trị max của hàm mục tiêu. Ta thấy chưa có giả PACB xuất phát (yêu cầu mọi ∆k ≥ 0). Các biến có ước lượng vi phạm là: x2, x3, x4, x5 nên ta thêm ràng buộc giả : z + x2 + x3 + x4 + x5 = M. Ta lập bảng đơn hình: Cơ sở

Hệ số

GPA

z

x1

x2

x3

x4

x5

x6

x7

Đ/vị

M

0

1

3

2

3

5

0

0

x1

1

−3

0

0

1

2

−1

1

−1

0

0

x6

0

−18

0

0

0

1

1

−2

−4

1

0

x7

0

10

0

0

0

−1

−3

0

2

0

1

z

0

0

1

1

0

1

1

1

[1]

0

0

B1

f (y)

−3

0

0

0

−1

−3

−2

−6

0

0

x1

1

−3

1

1

1

3

0

2

0

0

0

x6

0

−18

4

4

0

5

5

2

0

1

0

x7

0

10

−2

−2

0

−3

0

0

1

x5

5

0

1

1

0

1

1

1

1

0

0

B2

f (y)

−3

6

6

0

5

3

4

0

0

0

x1

1

−3

1

1

1

3

0

2

0

0

0

x6

0

−8

2

2

0

2

0

0

0

1

1

x3

2

−2

0,4

0,4

0

0,6

1

0,4

0

0

−0,2

x5

5

2

0,6

0,6

0

0,4

0

0,6

1

0

0,2

B3

f (y)

3

4,8

4,8

0

3,2

0

2,8

0

0

0,6

[−5] −2

- 49 -

Ở bảng 1 ta chọn hàng 4 (ràng buộc giả) là hàng xoay, cột xoay là cột x 5 vì có ước lượng ∆5 = − 6 âm nhỏ nhất. Sang bảng 2 ta có mọi ước lượng thỏa mãn dấu hiệu tối ưu nhưng trong GPA có b3 = − 2M + 10 < 0 nên hàng 3 là hàng xoay, trên hàng xoay phần tử trục là [−5] vì tỷ số |3/−5| là nhỏ nhất. Ở bảng 3 ta thấy với M đủ lớn thì mọi bi ≥ 0, bài toán kết thúc, nhưng f(x) = 4,8M + 3 sẽ có giới hạn + ∞ khi M tiến tới + ∞ nên hàm mục tiêu không bị chặn trên, có nghĩa là BT không có PATƯ. Ví dụ 1.4.12: Giải BT QHTT sau bằng phương pháp đơn hình đối ngẫu. f(x) = 2x1 + 3x2 + 2x3 + x4 + x5 → min 3x1 + x2 − 2x3 + 4x4 + x5

= 8

2x2 + x3 + 2x4

= 20

+ x6

−2x1 + 2x2 − x3 − 4x4

+ x7 = − 6

xj ≥ 0 (j = 1…7) Sau khi lập bảng đơn hình, tính các ước lượng ta có ∆1 = 1, ∆2 = 2, ∆3 = 4 và ∆4 = 3. Như vậy ∆1 và ∆4 không thỏa mãn dấu hiệu tối ưu. Vì vậy ta thêm ràng buộc giả: z + x1 + x4 = M, với M là số dương đủ lớn. Cơ sở

Hệ GPA số Đ/vị M

z

x1

x2

x3

x4

x5

x6

x7

0

2

3

2

1

1

0

0

x5

1

8

0

0

3

1

−2

4

1

0

0

x6

0

20

0

0

0

2

1

2

0

1

0

x7

0

−6

0

0

−2

2

−1

−4

0

0

1

z

0

0

1

1

1

0

0

[1]

0

0

0

B1

f (y)

8

0

0

1

−2

−4

3

0

0

0

x5

1

8

−4

[−4]

−1

1

−2

0

1

0

0

x6

0

20

−2

−2

−2

2

1

0

0

1

0

x7

0

−6

4

4

2

2

−1

0

0

0

1

x4

1

0

1

1

1

0

0

1

0

0

0

B2

f (y)

8

−3

−3

−2

−2

−4

0

0

0

0

z

0

−2

1

1

1/4 −1/4

1/2

0

−1/4

0

0

x6

0

16

0

0

−3/2

3/2

2

0

−1/2

1

0

0

2

0

0

1

3

−3

0

1

0

1

x7

- 50 -

x4

1

2

0

0

3/4

1/4 −1/2

1

1/4

0

0

B3

f (y)

2

0

0

−5/4 −11/4 −5/2

0

−3/4

0

0

Ở bảng 1 ta chọn trên ràng buộc giả phần tử trục có ước lượng dương lớn nhất (∆ 4 = 3). Sang bảng 2 ta có b1 = − 4M + 8 < 0 nhỏ nhất nên hàng 1 là hàng xoay, trên hàng xoay phần tử trục là [−4] vì tỷ số |−3/−4| là nhỏ nhất. Ở bảng 3 ta thấy mọi bi ≥ 0, BT kết thúc với f(x)min = 2 và PATƯ duy nhất: X = (0, 0, 0, 2, 0, 16, 2). Lưu ý: +) Các giá trị trên cột hệ số M và cột z luôn giống nhau nên khi tính toán ta chỉ cần tính 1 cột, cột còn lại chép sang; +) Khi kết thúc thuật toán: - Nếu z là biến cơ sở thì ta có PATƯ (ví dụ 1.4.12), - Nếu z là biến phi cơ sở và f(x) không chứa M thì ta có vô số PATƯ, - Nếu z là biến phi cơ sở và f(x) có chứa M thì không tồn tại PATƯ (ví dụ 1.4.11).

Câu hỏi thảo luận chương 1 1. BT QHTT là gì? Nêu các thành phần của nó. 2. Nêu đặc điểm cơ bản của tập PA của BT QHTT dạng chính tắc. 3. Trong BT QHTT có những loại biến gì? Phân biệt sự khác nhau giữa chúng. 4. Khi nào BT QHTT không có PATƯ? 5. Có phải tập PATƯ của BT QHTT là tập lồi? 6. Nếu BT (G) có PA và không bị chặn thì BT (D) có PA hay không?

- 51 -

BÀI TẬP CHƯƠNG I Hãy lập mô hình bài toán cho các bài tập dưới đây: Bài 1: Một xưởng gỗ dự định sản xuất bàn ghế, tủ, giường. Biết định mức tiêu hao các yếu tố sản xuất khi làm ra 1 sản phẩm được cho trong bảng sau: Yếu tố

Sản phẩm

sản xuất

Bàn ghế

Tủ

Giường

Lao động (ngày công)

3

8

5

Chi phí SX (triệu đồng)

1,5

6

2,2

Biết rằng giá bán 1 bộ bàn ghế là 2,5 triệu; 1 cái tủ là 9 triệu và 1 cái giường là 3,5 triệu. Xưởng hiện có số lao động là 150 ngày công và số vốn là 100 triệu. Giả sử số sản phẩm sản xuất ra được tiêu thụ hết. Hãy lập mô hình bài toán tìm kế hoạch sản xuất (KHSX) tối ưu. Bài 2: Từ ví dụ 1.2.1 và bài tập 1 hãy lập bài toán tìm kế hoạch sản xuất tối ưu tổng quát. Bài 3: Để nuôi một loại gia súc trong 24 giờ cần có khối lượng tối thiểu các chất dinh dưỡng là 80g protit, 120g gluxit và 6g chất khoáng. Tỷ lệ % theo khối lượng các chất trên có trong các loại thức ăn như sau: Thức ăn

Chất dinh dưỡng (%) Protit

Gluxit

Khoáng

A

10

30

2

B

20

45

1,5

C

25

20

3

Biết rằng giá của 1 kg thức ăn A, B và C tương ứng là 20, 30 và 25 (nghìn đồng). Hãy lập mô hình bài toán xác định khối lượng thức ăn tối ưu cần mua trong một ngày. Bài 4: Từ ví dụ 1.2.2 và bài tập 3 hãy lập bài toán xác định khẩu phần ăn tối ưu tổng quát. Bài 5: (Bài toán pha trộn) Một nhà máy lọc dầu hiện có 2 loại xăng cơ bản với các đặc tính sau: Xăng cơ bản

Chỉ số Octan

Lực hóa hơi

Số lượng hiện có (lít)

Loại 1

105

5

50.000

Loại 2

93

9

70.000 - 52 -

Từ 2 loại xăng trên, nhà máy dự định sản xuất 2 loại xăng máy bay và xăng ô tô với các đặc tính sau: Xăng thành

Chỉ số Octan

Lực hóa hơi

Giá bán

phẩm

tối thiểu

tối đa

(nghìn đ/l)

Xăng máy bay

103

6

35

Xăng ô tô

95

8

20

Biết rằng khi xăng được trộn với nhau, xăng thành phẩm có chỉ số octan và lực hóa hơi được tính trung bình theo tỷ lệ với dung tích của mỗi thành phần. Dung tích xăng thành phẩm thu được bằng tổng dung tích của các thành phần. Hãy lập mô hình bài toán xác định phương án pha trộn xăng tối ưu. Bài 6: (Bài toán lập tiến độ sản xuất) Một công ty sản xuất một loại máy biến áp (MBA) cỡ lớn để cung cấp cho ngành công nghiệp điện, có các đơn đặt hàng trong 4 tháng liên tiếp và chi phí sản xuất (CPSX) của mỗi MBA trong các tháng như sau: Dữ liệu

Tháng 1

2

3

4

Đơn đặt hàng (máy)

35

28

42

51

CPSX trong thời gian thường (tr/máy)

86

84

85

87

CPSX trong thời gian phụ trội (tr/máy)

91

88

89

90

Năng lực sản xuất của công ty là 30 máy/tháng trong thời gian thường (làm trong giờ) và 15 máy/tháng trong thời gian phụ trội (làm ngoài giờ). Chi phí lưu kho cho 1 máy là 1 triệu đồng/tháng. Công ty có sẵn trong kho 10 máy vào ngày 1/1 và mong muốn có ít nhất 5 máy lưu kho vào ngày 30/4. Hãy lập mô hình bài toán xác định tiến độ sản xuất tối ưu. Bài 7: (Bài toán mua sắm phương tiện) Một doanh nghiệp vận tải hàng tháng phải vận chuyển hàng hóa từ các nhà máy tới các kho với số lượng 300.000 T-km (1 T-km = chuyên chở 1 tấn hàng hóa đi quãng đường 1 km). Doanh nghiệp dự định mua các loại xe tải để vận chuyển với các dữ liệu ở dưới đây. Biết rằng Doanh nghiệp có số vốn để mua xe là 30 tỷ đồng và số chỗ để xe là 20 ô đậu. Mỗi xe loại lớn hay vừa chiếm 1 ô đậu, mỗi xe loại nhỏ chiếm 1/2 ô đậu. Doanh nghiệp có 35 lái xe và chỉ có 8 trong số đó điều khiển được xe loại lớn.

- 53 -

Dữ liệu

Loai xe Lớn

Vừa

Nhỏ

Giá mua (triệu/xe)

2.500

1.800

750

Chi phí vận hành (nghìn đồng/T-km)

6,2

7,4

8,5

Năng suất (1.000 T-km/tháng)

15

8

4,5

Hãy lập mô hình bài toán xác định số lượng xe các loại cần phải mua sao cho tổng chi phí vận chuyển mỗi tháng là ít nhất và chở hết hàng. Bài 8: (Bài toán chia cắt) Một xưởng cơ khí cần cắt những thanh sắt dài 2 m thành 200 đoạn dài 0,9 m; 300 đoạn dài 0,8 m và 150 đoạn dài 0,6 m. Hãy lập mô hình bài toán tìm phương án cắt sao cho số sắt thừa là ít nhất, biết rằng số lượng thanh sắt 2 m hiện có là rất lớn. Bài 9: (Bài toán cái túi) Một người đi du lịch có chiếc vali chứa được tối đa 20 kg. Có 8 đồ vật định mang theo. Có số liệu về khối lượng (kg) và giá trị (triệu đồng) các đồ trong bảng dưới đây: Loại đồ vật

1

2

3

4

5

6

7

8

Khối lượng (kg)

4,5

5,2

6,3

7,4

2,8

1,5

0,6

1,9

Giá trị (triệu đồng)

2,2

3,4

4,3

5,5

1,7

1,1

0,2

1,6

Hãy lập mô hình bài toán xác định các loại đồ vật cần mang theo sao cho tổng giá trị là lớn nhất. Bài 10: (Bài toán xếp hàng hóa lên tàu) Một tàu chở hàng có trọng tải 1.200 tấn và dung tích 1.000 m3. Tàu có thể chở 6 loại hàng hóa. Có số liệu về khối lượng (tấn/kiện), thể tích (m3/kiện) và giá trị (triệu đồng/kiện) các đồ trong bảng dưới đây: Loại hàng

1

2

3

4

5

6

Khối lượng (tấn/kiện)

2,5

3,2

4,3

5,4

5,8

6,1

Thể tích (m3/kiện)

1,3

2,2

2,6

3,0

3,4

4,5

Giá trị (triệu đ/kiện)

52

54

63

68

77

81

Hãy lập mô hình bài toán xác định số lượng kiện hàng các loại cần xếp lên tàu sao cho tổng giá trị là lớn nhất. Bài 11: (Bài toán quy hoạch đất trồng) Một nông trại dự định trồng 2 loại cây C1 và C2 trên 3 khu đất A, B, C. Diện tích các khu đất, chi phí sản xuất (CPSX) và năng suất (NS) của các loại cây có trong bảng sau: - 54 -

Khu

Diện

Loại cây

đất

Tích

C1

(ha)

CPSX (tr. đ/ha)

NS (tạ/ha)

CPSX (tr. đ/ha)

NS (tạ/ha)

A

60

5

12

8,5

20

B

80

5,5

15

9

22

C

50

4,8

10

7

19

C2

Yêu cầu sản lượng của các loại cây C1 và C2 tương ứng là 1.500 và 1.200 (tạ). Hãy lập mô hình bài toán xác định phương án phân phối đất trồng sao cho đảm bảo yêu cầu về sản lượng và chi phí sản xuất thấp nhất. Bài 12: (Bài toán phân bổ công nhân) Một phân xưởng có 30 công nhân và 30 máy gia công một loại sản phẩm. Biết rằng có 3 loại công nhân A, B, C và 4 loại máy M1, M2, M3, M4. Số lượng công nhân, số lượng máy các loại và năng suất lao động (sản phẩm/giờ) của công nhân được cho trong bảng sau: Loại CN

Loại máy (số lượng)

(số lượng)

M1 (6 máy) M2 (8 máy) M3 (9 máy) M4 (7 máy)

A (9 CN)

8

5

12

7

B (13 CN)

11

8

6

10

C (8 CN)

14

10

9

13

Biết rằng mỗi công nhân phụ trách một máy. Hãy lập mô hình bài toán sắp xếp số lượng công nhân các loại vào các loại máy sao cho tổng năng suất lao động của phân xưởng là lớn nhất. Từ bài tập 13 đến bài tập 16 hãy tìm nghiệm riêng cơ bản và nghiệm tổng quát của các hệ phương trình sau bằng phép khử Gauss – Jordan: Bài 13: x1 – 2x2 + 2x3 +

x4 = 8

2x1 – x2 + x3 –

x4

– x1 + x2 – 2x3 –

x4 = – 4

=2

Bài 14: – x1 + 3x2 + 2x3 = 6 x1 + 2x2 +

x3 = 10

x1 – x2 + x3 = 4 - 55 -

Bài 15: x1 + x2 – 2x3 + 2x4 = 2 + 2x3 – x4 = 3

2x1

– 2x1 + 2x2 + x3 + x4 = 4 Bài 16: + 4x4 – x5 = 5

x1 + 2x2

x1 – 2x2 – x3 – 2x4 + 3x5 = 2 – x1 + x2 + 2x3 + x4

= 4

+ 3x3 – x4 + x5 = 6

2x1

Giải các BT QHTT sau bằng phương pháp đơn hình với dạng chuẩn xuất phát: Bài 17: f(x) = 2x1 + 4x2 + 6x3 + 8x4 + x5 + 6x6 → min (max) x1

+ 2x3 + x4

= 6

2x1 + x2 + 3x3 4x1

+ 3x3

+ x6 = 10 + x5 + x6 = 36

xj ≥ 0 (j=1÷6) Bài 18: f(x) = 4x1 + 2x2 + 8x3 – x4 + x5 → min (max) 3x1 + x2 + 2x3 – 2x4

= 14

+ 2x3 + 3x4 + x5 ≤ 8

x1

x3 + 2x4 + 2x5 ≤ 6 (xj ≥ 0, j = 1..5) Bài 19: f(x) = – 4x1 + 3x2 + x3 → min (max) x1 – x2 + 3x3 ≤ 10 x1 – 2x2 + 2x3 ≥ – 60 – x1 + x 2

≤ 8

xj ≥ 0 (j=1÷3) Bài 20: f(x) = x1 – 4x2 + 3x3 + 3x4 + 11x5 – 6x6 → min (max) 2x1 + x2 x1

x3 – 2x4

– x6 = 2

+ x4

– 2x6 = 0

+ x4 + x5 – x6 = 1

xj ≥ 0 (j=1÷6) - 56 -

Bài 21: f(x) = 5x1 + 4x2 – 5x3 + 5x4 – 2x5 + 3x6 → min (max) x1 + 4x2

+ 2x4 + 2x5

= 12

2x2 + x3 + 4x4 + 3x5

= 24

3x4 + 2x5 + x6 = 18 xj ≥ 0 (j=1÷6) Bài 22: f(x) = 2x1 + 7x2 – 5x3 + 4x4 → min (max) x1 – x2 – x3 + 3x4 = 14 x2 – 4x3 + x4 ≤

8

x2 – 2x3 + 3x4 ≥ –20 xj ≥ 0 (j=1÷4) Bài 23: f(x) = – 4x1 + 2x2 + 3x3 + x4 – 2x5 → min (max) – 5x1 + x2 + 3x3 + 2x4

=5

– 2x1

+ x3 + x4 + x5 = 2

– 4x1

+ 2x3 + 2x4

≤ 10

xj ≥ 0 (j=1÷ 5) Giải các BT QHTT sau bằng phương pháp đơn hình với bài toán BT phụ (P): Bài 24: f(x) = x1 + 2x2 – 4x3 + 3x4 → min (max) 2x1 – x2 + x3 + x4 = 4 – 6x1 + 3x2 + 3x3 + 2x4 = 18 – x1 + x2 – x3 + x4 = 10 xj ≥ 0 (j=1÷4) Bài 25: f(x) = 6x1 + x2 – 2x3 → min (max) 9x1 + x2 + x3 ≤ 18 15x1 + x2 – 2x3 = 20 3x1

+ x3 = 3

xj ≥ 0 (j=1÷3) Bài 26: f(x) = 2x1 – 3x2 – 2x3 + x4 – x5 – 4x6 + 3x7 → min (max) x1 – 3x2 + x3 + 3x4 – x3 – 2x2 + 2x3 + x4

+ x6 – 4x7 = 20 + x5 + x6 + 5x7 = 10 – 4x7 = 16

xj ≥ 0 (j=1÷7) - 57 -

Bài 27: f(x) = 4x1 + 2x2 + 6x3 + 4x4 + 4x5 → min (max) 2x1

+ x4 + x5 = 20

– x1 + x2 + x3 + 3x4 x1

= 25

+ 3x5 ≤ 40

+ 2x3 xj ≥ 0 (j=1÷5)

Bài 28: f(x) = 2x1 + x2 – x3 – 4x4 → min (max) 2x2 – 2x3 + 3x4 ≤ 12 2x1 – 3x2 + x3

= 10

2x1 – 3x2 – 2x3 – 4x4 = 6 xj ≥ 0 (j=1÷4) Bài 29: f(x) = 2x1 – x2 – 2x3 – 2x4 + x5 – 4x6 + x7 → min (max) – x 2 + x3 + x4

+ x6 – 2x7 = 6

+ x3 + 3x4

+ x6 – 4x7 = 10

x1

2x2 – x3

+ x5 + x6 + 5x7 = 8

xj ≥ 0 (j=1÷7) Bài 30: f(x) = 2x1 + x2 + 2x3 – x4 → min (max) 5x1 + 3x2 + x3 – 2x4 ≤ 20 2x1

+ 2x3 + x4 = 18

– 2x1 + 2x2 + 2x3 + x4 = 10 xj ≥ 0 (j=1÷4) Bài 31: f(x) = – x1 + 2x2 – x3 + 8x4 – x5 – x6 → min (max) x1 + 4x2 – x3 – x4

+ x6 = 5

x3 – 2x4

= 6

– 2x2 + 3x3 + 6x4 – 2x5 – x6 = 12 xj ≥ 0 (j=1÷6) Sau khi giải các bài tập từ bài 17 đến bài 31 hãy viết bài toán đối ngẫu của các bài toán đó và tìm PATƯ của các bài toán đối ngẫu dựa vào các định lý đối ngẫu. Bài 32: Cho BT QHTT sau: f(x) = 4x1 – 2x2 – x3 – 3x4 → min x1

+ x3 + x4 + 3x5 = 16

2x1 – 3x2 – 2x3

+ 2x5 ≤ 52

x2 + x3 – 2x5 ≤ 24 - 58 -

xj ≥ 0 (j=1÷5) và véc tơ X0 = (0, 24, 0, 16, 0). Hãy viết bài toán đối ngẫu của bài toán trên và chứng tỏ X 0 là PATƯ của bài toán gốc. Bài 33: Cho BT QHTT sau: f(x) = – 2x1 + 3x2 + x3 → max 2x1 – x2 + x3 ≤ 18 3x1 + x2 – 2x3 ≤ 20 ≤ 12

x1 + 2x2

xj ≥ 0 (j=1÷3) và véc tơ X0 = (0, 6, 24). Hãy viết bài toán đối ngẫu của bài toán trên và chứng tỏ X0 là PATƯ của bài toán gốc. Giải các bài toán sau bằng phương pháp đơn hình đối ngẫu, viết BT đối ngẫu và tìm PATƯ của nó: Bài 34: f(x) = 2x1 + x2 + x3 + 4x4 → max 5x1 + x2 + x3 + 6x4 = 50 – 3x1

+ x3 + 2x4 ≥ 16

4x1

+ 3x3 + x4 ≤ 23

xj ≥ 0 (j=1÷4) Bài 35: f(x) = x1 + 3x2 + 4x3 + x4 → min x1 – 2x2

+ 2x4 ≥ 8

– 3x2 + x3 – 4x4 ≤ 18 – 3x1 + x2 + 2x3 – x4 ≥ 20 xj ≥ 0 (j=1÷4) Bài 36: f(x) = 4x1 + 2x2 + x3 + 1/2x4 → max x1 + 4x2

+ 3x4 ≤ 32

6x1 + 5x2 + x3 + x4 = 66 2x1 – 3x2

+ x4 ≥ 24

xj ≥ 0 (j=1÷4) Bài 37: f(x) = – 2x1 + 4x2 – 3x3 – x4 + 5x5 → min x1 + x2 + 3x3 + x4 – x5 = 6 – 2x2 + x3

– 4x5 ≤ 15 - 59 -

5x2 + 2x3 + x4 – x5 ≥ 18 xj ≥ 0 (j=1÷5) Bài 38: f(x) = 3x1 + 5x2 – 2x3 + 9x4 – x5 + 2x6 + 3x7 → min – 3x2

+ x4 – 2x5 + x6 – x7 = –15

– x2 + x3 – x4 + 5x5 x1 + x 2

+ x4 + 3x5

+ x7 = –10 + 2x7 = 10

xj ≥ 0 (j=1÷7) Bài 39: f(x) = 4x1 + 2x2 + 2x3 + 3x4 → min (max) + 2x3 + x4 ≥ 40

x1

x1 + 4x2 + x3 – 2x4 ≥ 32 – 2x1 + 3x2 – 3x3 – 2x4 ≤ 69 xj ≥ 0 (j=1÷4) Bài 40: f(x) = x1 + x2 – 7x3 + 5x4 – 2x5 + x6 → max (min) x1 – x2

– 2x4

= –12

x2 + x3 + 2x4 – x5 2x2 – 4x3 + 2x4

= 8 + x6 = 28

xj ≥ 0 (j=1÷6) Bài 41: f(x) = 3x1 – 2x2 – x3 – 4x4 – x5 → min (max) – 4x1 + x2 + 2x3 + 2x4 – 4x5 = 38 5x1

– 3x3 – x4 + 2x5 ≤ 4

4x1

– 2x3 – 3x4 + 4x5 ≥ 16

xj ≥ 0 (j=1÷5) Bài 42: f(x) = 2x1 + 3x2 + 2x3 + x4 + x5 → min (max) 3x1 + x2 – 2x3 + 4x4 + x5 = 2 2x2 + x3 + 2x4

≤ 20

2x1 + 2x2 + x3 – 2x4

≥ 12

xj ≥ 0 (j=1÷5)

- 60 -

Chương II: BÀI TOÁN VẬN TẢI Mục đích Mục đích của chương này là trang bị cho người học các kiến thức về bài toán chi phí vận tải, ý nghĩa của bài toán vận tải và bài toán đối ngẫu của nó. Kết thúc chương người học có thể giải được các dạng bài toán vận tải và ứng dụng bài toán vận tải để giải các dạng bài toán khác như bài toán phân bổ công nhân v.v.

2.1. Khái niệm về bài toán vận tải 2.1.1. Bài toán chi phí vận tải a) Ví dụ dẫn đến bài toán vận tải (BTVT) Ví dụ 2.1.1: Giả sử Doanh nghiệp (DN) X có 4 siêu thị ở 4 thành phố Hà Nội (HN), Hải Phòng (HP), Đà Nẵng (ĐN) và Tp. Hồ Chí Minh (HCM). DN cần vận chuyển gạo từ 3 kho ở 3 thành phố Hưng Yên (HY), Huế và Bình Thuận (BT) tới 4 siêu thị trên. Yêu cầu lượng gạo của các siêu thị (tấn), trữ lượng của các kho (tấn) và cước phí vận chuyển 1 tấn gạo từ thành phố A đến thành phố B (nghìn/tấn) được cho trong bảng sau: Thu Phát HY

HN

HP

ĐN

HCM

80

70

60

90

5 120

Huế

7 x11

8 85

BT

x12 9

x21 14

95

10 x13 4 x22

15 x31

17 13 x23

3 x32

x14 x24 6

x33

x34

Bài toán được đặt ra là ta phải vận chuyển từ kho này tới siêu thị kia bao nhiêu tấn gạo sao cho mọi yêu cầu của các siêu thị đều được đáp ứng, mọi kho đều phát hết và tổng chi phí vận chuyển phải ít nhất. Ta có mô hình bài toán: Gọi xij là số tấn gạo cần vận chuyển từ kho i tới siêu thị j. Tìm {xij} i = 1,…, 3; j = 1,…, 4 sao cho: f(x) = 5x11 + 7x12 + 10x13 + 17x14 + 8x21 + 9x22 + 4x23 + 13x24 + 14x31 + 15x32 + 3x33 + 6x34 → min x11 + x12 + x13 + x14 = 120 - 61 -

x21 + x22 + x23 + x24 = 85 x31 + x32 + x33 + x34 = 95 x11 + x21 + x31 = 80 x12 + x22 + x32 = 70 x12 + x23 + x33 = 60 x14 + x24 + x34 = 90 xij ≥ 0. Từ ví dụ này ta thành lập BTVT cổ điển như sau: b) BTVT tổng quát Giả sử ta cần vận chuyển hàng hoá từ m trạm phát tới n trạm thu. Ta có một số ký hiệu sau: Ai (i =1,…m): các trạm phát, Bj (j = 1,…n): các trạm thu, ai: lượng hàng hoá có (trữ lượng) ở trạm phát Ai , bj: lượng hàng hoá yêu cầu ở trạm thu Bj , cij: chi phí vận chuyển một đơn vị hàng hoá từ trạm phát Ai đến trạm thu Bj (cij>0), xij: lượng hàng hoá cần vận chuyển từ trạm phát Ai đến trạm thu Bj , xij ≥ 0 (i, j). Hãy thành lập một PA vận chuyển hàng hoá sao cho đáp ứng đầy đủ yêu cầu của các trạm thu bằng tất cả hàng hóa có ở các trạm phát với tổng chi phí vận chuyển là nhỏ nhất (hoặc lớn nhất). Mô tả bài toán dưới dạng bảng: Thu Phát A1

B1

B2

b1

b2

c11

Am

cm1 am

c2n

x22 ……

x2n …… ……

cm2 xm1

x1n ……

x21 …..

c1n

x12 c22

a2 …..

……

x11 c21

Bn bn

c12

a1 A2

……

xm2

…… cmn xmn

- 62 -

Giao của hàng i và cột j gọi là ô (i, j) đặc trưng cho sự vận chuyển từ trạm phát A i tới trạm thu Bj, ở ô này ta ghi cij ở góc trên bên trái và xij ở góc dưới bên phải. m

n

Ta có tổng phát =  a i ; tổng thu =

 b j . Nếu j=1

i=1

m

n

 a = b i

i=1

j

thì BTVT là bài

j=1

toán cân bằng thu – phát. Khi đó ta có BTVT cân bằng thu – phát tổng quát như sau: Tìm bộ giá trị X = [ xij ], i = 1…m; j = 1…n sao cho: m

n

f(X) =  cij x ij  min(max)

(1)

i=1 j=1

n

x j1

ij

=a i

ij

=b j

m

x i=1

x ij  0

i=1,m 

(2)

 j=1,n  i=1,m; j=1,n 

(3) (4)

Nhận xét: BTVT cũng chính là BT QHTT dạng chính tắc với m.n biến và m + n ràng buộc chung. 2.1.2. Một số khái niệm cơ bản Ô chọn (ô cơ sở): Là ô có xij > 0 (biến cơ sở). Ô loại (ô phi cơ sở): Là ô có xij = 0 (biến phi cơ sở). Dây chuyền: Là một dãy ô chọn liên tiếp nhau sao cho 2 ô cạnh nhau là cùng hàng hoặc cùng cột và sự cùng hàng, cùng cột đó phải xen kẽ nhau. Vòng (chu trình): Là một dây chuyền khép kín. Ví dụ 2.1.2: x

x

x x

x x

PACB của BTVT là tập hợp các ô có xij biến cơ sở. 2.1.3. Các tính chất của bài toán vận tải Định lý 2.1.1: BTVT cân bằng thu – phát luôn có PATƯ. Chứng minh: - 63 -

m

n

i=1

j=1

 a i = b j = d . Đặt: x ij =

i) Tồn tại PA: Giả sử

n

aib j

j=1

d

n

Khi đó ta có:

 x = ij

j=1

m

m

 x ij = i=1

[x ij =

i=1

aib j d

aib j d

=

bj d

aib j d

 0.

ai n a = . b j = i .d = a i và : d j=1 d

m

bj

i=1

d

. a i =

.d = b j . Thỏa mãn (2), (3) và (4) nên:

]m×n là 1 PA.

ii) Chứng tỏ hàm mục tiêu bị chặn: Giả sử giá trị nhỏ nhất của cij là C0 , giá trị lớn nhất của nó là C1. Vì mọi xij ≥ 0 nên ta có: m

n

m

n

f(X) =  cij .x ij  C0 . x ij = C0 .d . Suy hàm mục tiêu bị chặn dưới. i=1 j=1

i=1 j=1

Tương tự ta có: f(X) ≤ C1.d nên f(X) bị chặn trên. Do đó BTVT luôn có PATƯ đối với cả BTVT fmin và fmax . Định lý 2.1.2: Hạng của hệ ràng buộc chung của BTVT cân bằng thu phát là (m + n – 1). Chứng minh: Hệ ràng buộc chung của BTVT cân bằng thu phát có (m + n) phương trình, m

nhưng vì ta có điều kiện

n

 a = b i

i=1

j

, đồng thời tổng vế trái của các ràng buộc (2) đúng

j=1

bằng tổng vế trái của các ràng buộc (3) nên phải có 1 phương trình phụ thuộc tuyến tính, vì vậy hạng của hệ ràng buộc chung là (m + n – 1). Hệ quả 2.1.1: Số ô cơ sở trong 1 PACB của BTVT có tối đa là (m + n – 1) ô. PACB là không suy biến (KSB) nếu có đúng (m + n – 1) thành phần dương, ngược lại PACB là suy biến nếu có ít hơn (m + n – 1) thành phần dương. Định lý 2.1.3: Một PA là PACB khi và chỉ khi các ô chọn không tạo thành vòng. Chứng minh: Ta chứng minh bằng phương pháp phản chứng. Giả sử trong PACB X có 1 vòng:

 ...x rs ...x rj ...  X=   ...x ...x ...  ij  is  và q là giá trị nhỏ nhất trên vòng đó. Khi đó ta có:

 ...x rs + q...x rj – q...   ...x rs – q...x rj + q...  X1 =  , X =   2  ...x – q...x + q...  ...x + q...x – q ... is ij is ij     - 64 -

cũng là 2 PA. Ta thấy X = (X1 + X2)/2 nên X là trung điểm của cạnh [X1, X2] như vậy X không thể là 1 đỉnh của tập PA, cũng có nghĩa là X không phải là PACB. Hệ quả 2.1.2: Nếu PACB là không suy biến thì mọi ô phi cơ sở đều có thể tạo thành vòng với các ô chọn. Định lý 2.1.4: Nếu X1 và X2 là 2 PATƯ thì ta có: X = α.X1 + ( 1 – α ).X2 với 0 ≤ α ≤ 1 cũng là PATƯ. 2.1.4. Các phương pháp xây dựng phương án cực biên cho bài toán vận tải Khi tìm PACB xuất phát cho BTVT cân bằng thu – phát ta thực hiện theo nguyên tắc phân phối tối đa cho ô được chọn. Giả sử ô (i, j) là ô được chọn, lượng hàng tối đa có thể phân phối là xij = min{ai , bj}. Sau đó ta gạch các giá trị ai , bj và thay thế bằng các giá trị mới: ai’ = ai – xij ; bj’ = bj – xij Nếu ai’ = 0 thì ta loại các ô còn lại trên hàng i, đánh dấu x lên các ô đó. Nếu bj’ = 0 thì ta loại các ô còn lại trên cột j và đánh dấu x lên các ô đó. Tiếp tục phân phối cho các ô còn lại (trừ các ô đã chọn và các ô có dấu x) theo quy tắc trên cho tới khi mọi ai và bj đều bằng 0, có nghĩa là các trạm phát đã phát hết và các trạm thu đã thu đủ. Với cách xây dựng như vậy ta sẽ được một PACB. Chứng minh: Với quy tắc phân phát tối đa như trên ta sẽ có PA mà trong nó không tồn tại vòng. Thật vậy, giả sử ta có 1 vòng: [xrs]

[xis]

[xrj]

[xij]

và (r, s) là ô chọn đầu tiên trong vòng trên. Theo quy tắc phân phát tối đa thì sau khi phân phát cho ô (r, s) thì hoặc ar’ = 0, hoặc bs’ = 0 nên ta sẽ có hoặc xrj = 0, hoặc xis = 0 vì vậy không thể tồn tại vòng trong PA, do vậy ta có PACB xuất phát. a) Phương pháp cước phí nhỏ nhất Khi thực hiện theo phương pháp này ta sẽ ưu tiên phân phát tối đa cho ô có cước phí nhỏ nhất. Nếu có nhiều ô có cước phí nhỏ nhất bằng nhau thì chọn ô nào trong số đó trước cũng được. Ví dụ 2.1.3:

- 65 -

Thu Phát 115 55; 0 110 40; 5; 0 75 0

70 0

60 0

10

80 5; 0

2 x

3

9 [60]

11

6 x

8

[70] 12

90 35; 0

x 15

7 [5]

4

x

[55]

x

[35] 5

[75]

x

Ô có cước phi nhỏ nhất là ô (1, 2), tối đa có thể phân phát cho ô này là x 12 = min{60, 115} = 60. Tiếp theo ta điều chỉnh: a1 = 115 – 60 = 55, b2 = 60 – 60 = 0. Vì b2 = 0 nên ta loại các ô còn lại trên cột 2 và đánh dấu x lên các ô đó. Bây giờ ô có cước phí nhỏ nhất là ô (2, 1) tối đa có thể phân phát cho ô này là x21 = min{70, 110} = 70. Các bước tiếp theo ta làm tương tự cho tới khi mọi ai và bj bằng 0 và được PACB như trên. b) Phương pháp cước phí lớn nhất Ở phương pháp này ta sẽ ưu tiên phân phát tối đa cho ô có cước phí lớn nhất. Nếu có nhiều ô có cước phí lớn nhất bằng nhau thì chọn ô nào trong số đó trước cũng được. Ví dụ 2.1.4: Thu Phát 10 115 45; 0 3 110 95; 60; 0 12 75 0

70 0

90 15; 0

80 35; 0

2 [70]

9 x

11 x

6 [45]

8 [15]

15 x

x 7

[35] 4

[75]

60 0

[60] 5

x

x

Ô có cước phí lớn nhất là ô (3, 2), tối đa có thể phân phát cho ô này là x32 = min{90, 75} = 75. Tiếp theo ta điều chỉnh: a3 = 75 – 75 = 0, b2 = 90 – 75= 15. Vì a3 = 0 nên ta loại các ô còn lại trên hàng 3 và đánh dấu x lên các ô đó. Ô có cước phí lớn nhất trong các ô còn lại là ô (2, 2) tối đa có thể phân phát cho ô này là x22 = min{15, 110} = 15. Các bước tiếp theo ta làm tương tự cho tới khi mọi ai và bj bằng 0 và được PACB như trên. c) Phương pháp góc tây – bắc Ở phương pháp này ta luôn ưu tiên cho ô trên cùng bên trái (góc tây – bắc) của bảng. Ví dụ 2.1.5: - 66 -

Thu Phát 10 115 45; 0 13 110 95; 15; 0 12 75 0

70 0

60 15; 0

80 0

19 [70]

9 [45]

11 x

6 x

8 [15]

17 x

90 15; 0 x 7

[80] 10

x

[15] 5

x

[75]

Đầu tiên ta phân phát tối đa cho ô (1, 1) x11 = min{70, 115} = 70, tiếp theo ta điều chỉnh: a1 = 115 – 70 = 45, b1 = 70 – 70 = 0. Vì b1 = 0 nên ta loại các ô còn lại trên cột 1 và đánh dấu x lên các ô đó. Ô tiếp theo được chọn là ô (1, 2) các bước tiếp theo ta làm tương tự cho tới khi mọi ai và bj bằng 0 và được PACB như trên.

2.2. Phương pháp thế vị 2.2.1. Bài toán đối ngẫu của bài toán vận tải fmin Bài toán đối ngẫu có dạng: m

n

i=1

j=1

f =  a i u i +  b j v j  max ui + vj ≤ cij , với mọi i = 1, m; j = 1, n (2.1) Ý nghĩa kinh tế của bài toán đối ngẫu. Trong khi bài toán chi phí vận tải fmin là bài toán của DN đi thuê vận tải thì bài toán đối ngẫu của nó là bài toán của DN vận tải. DN vận tải sẽ thu phí vận chuyển một đơn vị hàng hóa (đvhh) từ trạm phát Ai với cước phí là ui và khi giao hàng tại Bj sẽ thu phí tại Bj là vj trên một đvhh. Đối với DN vận tải thì tổng doanh thu phải lớn nhất tức là: m

n

i=1

j=1

f =  a i u i +  b j v j  max Đối với DN đi thuê vận tải số tiền phải chi cho 1 đvhh để vận chuyển từ Ai tới Bj không được vượt quá cước phí niêm yết cho quãng đường (i, j) là cij, tức là: ui + vj ≤ cij. Theo định lý đối ngẫu 1.4.3 thì một PA [xij] là PATƯ khi và chỉ khi tồn tại {(ui , vj)} sao cho: xij( ui + vj – cij ) = 0 với mọi i = 1…m ; j = 1… n (2.2) Kết hợp (2.1) và (2.2) ta có:

  u i + v j  ci j , (i, j)  , nếu (i, j) là ô cơ sở   u i + v j = ci j

- 67 -

2.2.2. Thuật toán thế vị để giải bài toán vận tải cân bằng thu – phát fmin Bước 1: Tìm PACB xuất phát Khi tìm PACB xuất phát cho BTVT cân bằng thu – phát fmin ta sử dụng phương pháp phân phối tối đa cho ô có cước phí nhỏ nhất. Chú ý: Khi số ô cơ sở nhỏ hơn (m + n – 1) thì ta phải bổ sung thêm ô cơ sở với xij = 0 và không tạo thành vòng với các ô cơ sở khác (nếu có nhiều lựa chọn thì ta chọn ô có cij nhỏ nhất với BTVT fmin, với BTVT fmax thì chọn ô có cij lớn nhất). Khi có đủ (m + n – 1) ô cơ sở ta chuyển sang bước sau. Bước 2: Tìm hệ thống thế vị {( ui , vj )} Mỗi hàng, mỗi cột ta chọn tương ứng một thế vị (ui là thế vị hàng, vj là thế vị cột) sao cho với các ô cơ sở ta luôn có ui + vj = cij . Vì số ô cơ sở là m + n – 1 nên ta có hệ m + n – 1 phương trình với m + n ẩn suy ra có 1 ẩn được chọn tự do, để cho đơn giản ta chọn ẩn tự do = 0. Ta có thuật toán tìm hệ thống thế vị như sau: - Đầu tiên ta chọn hàng hoặc cột có nhiều ô chọn nhất có thế vị = 0. - Sau đó dựa vào các ô chọn có thể tính được các thế vị khác theo công thức sau: ui = cij – vj , nếu vj đã biết, hoặc vj = cij – ui , nếu ui đã biết. Khi tất cả các hàng và các cột đều có thế vị ta chuyển sang bước tiếp theo. Bước 3: Kiểm tra dấu hiệu tối ưu Ta tính các ước lượng của từng ô: Δij = ui + vj – cij . Lưu ý: Với các ô cơ sở ta luôn có Δij = 0. -

Nếu mọi Δij ≤ 0, ta có PACB tương ứng là PATƯ. Thuật toán kết thúc.

-

Nếu tồn tại Δij > 0, ta chưa có PATƯ và chuyển sang bước sau.

Bước 4: Tìm PACB tốt hơn Giả sử ô (i, j) có Δij > 0 lớn nhất, ô (i, j) sẽ là ô chọn trong bảng mới và được gọi là ô điều chỉnh (ô cơ sở mới). Đánh dấu ô điều chỉnh bằng dấu (*). Ta tìm vòng xoay tạo bởi ô điều chỉnh và các ô chọn khác. Sau đó trên vòng xoay ta đánh dấu liên tiếp +, – bắt đầu ô (*) với dấu + . Lưu ý: Vòng xoay luôn luôn tồn tại và duy nhất. Trên vòng xoay ta tìm lượng điều chỉnh: q = min{xij của các ô mang dấu –} Giả sử q = xrs, ô (r, s) sẽ bị loại ra khỏi cơ sở. - 68 -

Trên vòng xoay ta điều chỉnh như sau:

xij' = xij + q với ô có dấu “ + “ và

xij' = xij – q với ô có dấu “– “. Các ô khác không thuộc vòng xoay ta giữ nguyên giá trị xij . Lưu ý: Trên vòng xoay ta thêm 1 ô chọn (ô điều chỉnh) và chỉ loại đúng 1 ô ra khỏi cơ sở. Nếu có 2 ô mang dấu – và cùng có xij = q thì để tránh gặp phải PACB suy biến, ta sẽ chỉ loại 1 ô và giữ lại ô kia là ô cơ sở với xij = 0. Như vậy số ô cơ sở luôn luôn = m + n – 1. Như vậy ta có PACB mới và quay về bước 2. Sau một số hữu hạn bước ta sẽ có PATƯ. Chứng minh thuật toán: i) Dấu hiệu tối ưu: Vì mọi ∆ij ≤ 0 nên ta có: ui + vj ≤ cij , tức là {(ui, vj)} là PA của BT đối ngẫu. Ngoài ra với mọi ô cơ sở ta có ∆ij = 0 ↔ (ui + vj – cij) = 0 nên theo định lý đối ngẫu 1.4.3 thì PACB tương ứng là PATƯ của bài toán gốc. ii) Chứng minh bước cải thiện PACB: Giả sử ta có vòng xoay: crs

crj

+ (*)

– [xrj]

cis

cij

– [xis] vs

+ [xij]

ur

ui

vj

Trong đó Δrs = ur + vs – crs > 0, suy ra crs = ur + vs – Δrs . Sau khi điều chỉnh vòng xoay, giá trị của hàm mục tiêu thay đổi là : ∆f(X) = q.(crs – crj + cij – cis) = q.(ur + vs –Δrs –ur – vj + ui + vj – ui – vs) = – q.Δrs< 0. Có nghĩa là giá trị hàm mục tiêu giảm, tức là ta được PACB tốt hơn. Ví dụ 2.2.1: Giải bài toán vận tải sau: f(x) → min

- 69 -

Thu

76

62

88

45

40

Phát 79

10

19

9

6

8

102

13

11

8

7

4

70

12

17

10

5

3

60

12

18

18

7

9

Ta có tổng phát = tổng thu = 311. Đây là BTVT cân bằng thu – phát. Xây dựng PACB ban đầu theo nguyên tắc phân phối tối đa cho ô có chi phí nhỏ nhất: Thu

76

62

88

45

40

Phát 10

79

19

9

[64] 102

13

x

12

8 [14]

12

7

10

[12]

x

x 18

x 3

[30] 7

[48]

x 4

5

x 18

8 [15]

[88]

17 x

60

x

11 x

70

6

x

[40] 9

x

x

Số ô chọn là 8 đúng bằng 4 + 5 – 1 nên ta có PACB không suy biến (KSB) xuất phát. Lưu ý: Từ bảng sau ta có thể bỏ đi hàng thu, cột phát và các dấu x (vì không cần thiết nữa). Cho u4 = 0, dựa vào các ô chọn ta lần lượt tính được các thế vị hàng và cột khác. 10

19

9

6

[64] 13

–2

[15] 11

8 [14]

12

8

17

7

4

5

3

10

[30] 12

18 [12] 12

–7

[88]

18

7

[40] 9

0

[48] 18

15

8

–3

6

Tính ∆ịj = ui + vj – cij đối với các ô phi cơ sở và chỉ ghi các giá trị ≥ 0 vào bảng. - 70 -

10

19

9

+4 6

8

[64] 13

[15] 11

8 [14]

12

17

12

10

18

7

4

[88] +2 5

3

7

[30] +1 9

18

[12]

[40]

[48]

Ước lượng dương lớn nhất là ∆13 = 4 nên ô (1, 3) được đưa vào cơ sở. Đánh dấu ô điều chỉnh bằng dấu (*) sau đó tìm vòng xoay tạo bởi ô (*) và các ô chọn khác. 10 –

19

9 +

[64]

13

11 +

12

[14]

17

8 –

+4 (*)

6

8 [15]

7

4

[88]

10

+2

5

3 [30]

12 +

[12]

18 –

18

7

+1

[40] 9

[48]

Xác định q = min {88, 48, 64} = 48, ô (4,2) sẽ bị loại ra khỏi cơ sở. Thực hiện việc điều chỉnh lượng hàng hóa trên vòng xoay, ta được PACB mới: 10 +

19

9

[16]

13

[48] 11

8 [62]

12

17

6 –

8

0

[15]

7

4

5

3

–1

[40] 10

[30] 12 –

18

18

7 +

[60]

10

12

9

[40]

+1 9 (*)

6

–1 2

4

q = min {15, 60} = 15, ô bị loại là ô (1,4). Điều chỉnh trên vòng xoay ta được PACB mới: - 71 -

10

19

9

[31] 13

8

–2

7

4

–3

5

3

[48] 11

8 [62]

12

6

17

[40] 10

[30] 12

18

18

–2

[40]

7

9

[45]

[15]

12

14

11

0

7

5

Sau khi xây dựng hệ thống thế vị và kiểm tra tiêu chuẩn tối ưu ta thấy: ∆ij < 0 với mọi ô loại. PACB tương ứng là PATƯ duy nhất và giá trị nhỏ nhất của hàm mục tiêu là: fmin = 10 x 31 + 9 x 48 + 11 x 62 + 8 x 40 + 5 x 30 + 3 x 40 + 12 x 45 + 7 x 15 = 2659. PATƯ là:

 31 0  X =  0 62  0 0   45 0

48 40 0 0

0 0 30 15

0  0 40   0

Ví dụ 2.2.2: Giải BTVT sau: f(x) → min Thu

30

20

25

35

40

Phát 30

13

7 x

20

5

1 x

40

10

10

5

6

x

x

x

x

x 14

[5] 11

[25]

x 11

7

2 x

12 [30]

5

3

3 [30]

2 x

[20]

x 60

6 [0]

[35] 10

x

[5]

Ta có tổng thu = tổng phát = 150. Khi xây dựng PACB ban đầu ta tìm được số ô chọn là 7 nhỏ hơn 4 + 5 – 1 = 8 nên phải bổ sung thêm 1 ô chọn có xij = 0 và không tạo thành vòng với các ô chọn khác, đó là ô (1, 2). - 72 -

13

7 –

5

6

2 +

[0]

1

10

12

–1

[30]

5

11

+ 37 –

14

–7

[20] 10

05 +

+ 73 (*)

3

+ 52

6

[5]

11

[30] 8

2

4

[5]

0

10

[25]

6

[35]

3

10

Ở đây ta có q = min{0, 5} = 0, thuật toán vẫn được thực hiện, ô (1, 2) sẽ bị loại: 13

7

6

2

12 [30]

5

+1 1

–1

10

5

11

3 +

+3 7 (*)

14 –

[35]

10 +

[5]

0

[20] 10

0

5 [0]

6

3

2 –

[30] 6

1

[5]

11 [25] 2

3

4 0

10

q = min {25, 35} = 25. Ô (4,3) bị loại khỏi cơ sở, ô (3,3) sẽ là ô chọn mới. 13

7

6

2

12 [30]

5 +

+1 1 (*) –

10

0

6 –

10

5

11

[20]

5 +

–4 3

7

[0]

3

[25] 2

[5] 11

[30]

10

–5

5

3

7

14 –

[10]

10 +

[30]

0 –4

14 - 73 -

q = min {20, 10, 30} = 10. Ô (3,5) bị loại khỏi cơ sở, ô (2,1) sẽ là ô chọn mới. 13

7

6

2

12 [30]

5

1

10

[10]

–5

5

11

[10]

10

5

–4 3

7

[10] 6

3

14

[25] 2

[5]

0

11

10

[20]

[40]

9

5

3

7

–3

13

Ở bảng cuối ∆ij < 0 với mọi ô loại, ta có PATƯ duy nhất:

 0 0  10 10 X =  0 10   20 0

0 0 25 0

30 0 5 0

0  0 0  40 

và

fmin = 30 x 2 + 10 x 5 +10 x 1 + 10 x 5 + 25 x 3 + 5 x 7 + 20 x 6 + 40 x 10 = 800. Lưu ý: Khi  ∆ij ≤ 0 nhưng tồn tại ô loại có ước lượng = 0 thì PATƯ không phải là duy nhất. Ta có thể đưa ô loại đó vào cơ sở và được PATƯ mới. Ví dụ 2.2.3: Giải bài toán vận tải sau: Ta có tổng thu = tổng phát = 200. Đây là BTVT cân bằng thu – phát. f(x) → min Thu Phát 50

50

75

7

10 [50]

40

8

13

10

60

9

12

9

[40]

[15]

x 10

[10] 12

[60]

x 10

9

14 x

11 x

x

x

25

16 x

[0] 50

50

[25] 15

x

x

Sau khi xây dựng PACB xuất phát ta có số ô chọn là 6 < 4 + 4 – 1 nên phải bổ sung thêm ô chọn (2, 1) để được 7 ô cơ sở.

- 74 -

7

10

+1

16

11 –1

[50] 8 –

13 [0]

10

12 +

9 +

+1 (*)

[15]

14 –

8

9 +

10 [40]

9 –

[10]

0 10

12

[25]

0

15

2

[60] 12

9

10

q = min { 0, 10, 60 } = 0, ô (2,1) bị loại, ô (4,1) sẽ là ô chọn. 7 –

[50]

8

10 +

+2 (*)

13

16

11 0

9

10 [40]

10

12

9 [15]

9 +

[0]

14 –

7

0 10

[10] 12

[25] 15

2

[60] 12

9

0

10

q = min {50, 60} = 50, ô (1, 1) sẽ bị loại. 7

10

16

11

9 –

[40]

10 +

0 (*)

0

[10]

10 –

[25]

0

–2

[50] 8

13

10

12 [15]

9

14

12

[50] 7

9 +

15 2

[10] 12

9

10

Ở bảng trên ta thấy mọi ước lượng đều ≤ 0 nên ta có PATƯ: - 75 -

 0 50 0 0     0 0 40 0  X1 =  0 15 10 25     50 10 0 0  Và fmin = 10 x 50 + 9 x 40 + 12 x 15 + 9 x 10 + 10 x 25 + 9 x 50 + 14 x 10 = 1970. Nhưng PATƯ trên không phải là duy nhất vì ô (2, 4) là ô loại nhưng có ước lượng = 0 nên ta có thể đưa ô này vào cơ sở và được PATƯ khác. Lưu ý, ở bảng sau ta không cần xây dựng hệ thống thế vị và cũng không cần tính các ước lượng nữa. Lượng điều chỉnh là: q = min { 25, 40 } = 25, ô (3,4) bị loại ra khỏi cơ sở. 7

10

16

11

9

10

[50] 8

13

[15] 10

12

9 [15]

9

14 [50]

[25] 10

[35] 12

15

[10]

Như vậy ta có PATƯ mới:

 0 50 0 0     0 0 15 25  X2 =  0 15 35 0     50 10 0 0  Và PATƯ tổng quát là:

0 0   0 50    0 0 15+25α 25 – 25α  X = α.X1 + (1 – α).X2 =  0 15 35 – 25α 25α    0 0   50 10

với mọi α  [0, 1]

Ví dụ 2.2.4: Giải bài toán vận tải sau: f(x) → min

- 76 -

Thu

95

80

65

35

95

Phát 110

7

6

14

[35] 100

10

x

5

9

100

14

3

x 4

x

x 12

x 12

x

x 6

x

[75] 10

[20] 9

[60]

x 8

[80] 5

13

x

2 x

60

9

x 18

[45]

[35]

[20]

Ta có BTVT cân bằng thu – phát với tổng thu = tổng phát = 370. Số ô cơ sở là 8 đúng bằng hạng của bài toán là 4 + 5 – 1 nên ta có PACB KSB xuất phát. 7

6

14

9

–5

13

[35] 10

2

5

9 [80] – 9

5

8

[75] +5 (*)

10 + 12

[20] 6

–3 –7

[60] 14

3

12

+ 2 12 + 5

4

18 [35] –

[45] 12

4

[20]

0

18

Ở bảng trên ta có q = min{20, 20} = 20. Sang bảng sau x23 và x45 sẽ bằng 0 nhưng để tránh PACB suy biến ta chỉ loại một ô và vẫn giữ lại một ô làm ô cơ sở. Ta ưu tiên giữ lại ô có cước phí thấp hơn và loại ô cước phí cao hơn (với BTVT có mục tiêu là max thì ngược lại). Ở đây ta sẽ giữ lại ô (2, 3) và loại ô (4, 5). 7

6

14

9

13

3

[35] 10 5

[75] 2 – 5

9 [80] + 9

3 +

+ 2 12 (*) –

8

10

[0] +16

[20] 12

4

18

0 1

[60] 14

4

2

[65] 9

[35] 1

x

3

10

q = min{80, 65} = 65. Ô (4, 3) sẽ bị loại. - 77 -

7

6 +

14

9

13 –

[35]

10

2

9

8 [65]

10 + 12

+

+16 (*)

12

4

18

–

[15] 5

5 –

9

[60]

14

3 [65] 4

x

2

[75]

0 [20] 1 1

[35]

9

3

3

10

q = min{60, 75, 65} = 60 7

6

14

9

3

13

[95] 10

[15] 2

9

8

[15] 5

5

[5] 9

[80] 6

x 14

10 12

12

4

18

[65] 4

0

[60] 3

[35]

2

9

0

3

1 10

Ở bảng cuối ta thấy mọi ô phi cơ sở đều có ước lượng âm nên bài toán kết thúc với PATƯ duy nhất:

 95  0 X  0   0

0 15 0 65

0 5 60 0

0 0 0 35

15   80  0   0 

Và fmin = 7 x 95 + 13 x 15 + 2 x 15 + 9 x 5 + 10 x 80 + 9 x 60 + 3 x 65 + 4 x 35 = 2610. 2.2.3. Bài toán vận tải không cân bằng thu phát a) Trường hợp tổng phát lớn hơn tổng thu Ta lập thêm một trạm thu giả Bn+1 với yêu cầu: bn+1 = tổng phát – tổng thu. Cước phí từ các trạm phát tới trạm thu giả là = 0. b) Trường hợp tổng thu lớn hơn tổng phát - 78 -

Thì ngược lại, ta lập thêm một trạm phát giả Am+1 với trữ lượng hàng hóa: am+1 = tổng thu – tổng phát. Cước phí từ trạm phát giả tới các trạm thu là = 0. Lưu ý: Khi xây dựng PACB ban đầu với phương pháp chi phí nhỏ nhất, ta ưu tiên phân phát cho ô thực có cước phí nhỏ nhất trước, các ô giả để lại sau cùng. Ví dụ 2.2.4: Giải bài toán vận tải sau: f(x) → min Thu Phát

78

56

65

51

85

8

3

5

12

60

4

8

8

10

75

11

15

16

9

80

10

13

18

11

Tổng thu = 250, tổng phát = 300. Phát nhiều hơn thu, ta thêm trạm thu giả B5 với yêu cầu b5 = 300 – 250 = 50. Khi xây dựng PACB xuất phát ta ưu tiên cho ô thực có cước phí thấp nhất trước. Đó là ô (1, 2) có c12 = 3 là nhỏ nhất. Thu Phát 85

78

56

8

3 x

60

4

8

11

80

8

15

10 [18]

10

16

13

x

[24]

x 0

[51] 11

[12]

x 0

9

18 x

0 x

x

x

50

12 [29]

x

x

51

5 [56]

[60] 75

65

x 0

x

[50]

Xây dựng hệ thống thế vị, tính các ước lượng, tìm ô điều chỉnh và lập vòng xoay ta có:

- 79 -

8

3

4 –

12

0

[56]

5 [29]

+2 8 +

+ 4 10 (*)

0

8 [60]

11

15

16

–6

9

0

[24] 10 +

13

+ 3 18 –

[18] 10

16

– 13

[51] 11

–2

0 0

[12]

[50]

18

11

0

0

q = min {60 ; 12} = 12, ô (4,3) bị loại ra khỏi cơ sở. 8

3

5

12

[56] 4 –

8 [48]

11 10 +

[29]

+2 8 +

[12]

16 –

[24]

+ 1 15 13

0 5

10

0 8

9

18

0 [51] +

+2 (*)

0 0 –

[50]

11

[30] –4

–2

–7

0

16 14

– 14

q = min {50 ; 48 ; 24} = 24, ô (3,3) bị loại ra khỏi cơ sở. 8

3

5

12

[56] 4

8

8

–9 10

[24] 11

0

[29] 0

[36] 15

16

–6 9

0 [51]

10

13

18

11

[24] 0

[54] 10

[26] 12

14

0

9

0

0

Ở bảng cuối ta có ∆ij < 0 với mọi ô loại, PACB tương ứng là PATƯ duy nhất:

- 80 -

 0   24 X=  0   54

56 29 0 0   0 36 0 0  0 0 51 24   0 0 0 26 

Và fmin = 56 x 3 + 29 x 5 + 24 x 4 + 36 x 8 + 51 x 9 + 24 x 0 + 54 x 10 + 26 x 0 = 1696. Trong đó: x35 = 24 và x45 = 26 là lượng hàng còn tồn lại ở trạm phát A3 và A4 vì thực chất không có sự vận chuyển hàng hóa tới trạm thu giả. 2.2.4. Giải BTVT với hàm mục tiêu fmax a. Ý nghĩa của BTVT với hàm mục tiêu fmax Ở BTVT fmin hàm mục tiêu là hàm chi phí, các trạm thu trực thuộc một công ty và người cần giải BTVT fmin chính là công ty đó, vì vậy có mục tiêu cực tiểu chi phí. Ngược lại ở BTVT fmax hàm mục tiêu là hàm doanh thu, các trạm thu thuộc các công ty khác nhau và người cần giải BTVT fmax là công ty dịch vụ vận tải, vì vậy có mục tiêu tối đa doanh thu. Ngoài ra, BTVT còn được dùng để giải bài toán phân bổ công nhân (bài tập 12 chương 1). b. Thuật toán giải BTVT fmax Thuật toán giải BTVT fmax cũng tương tự như BTVT fmin . Có 3 điểm khác nhau: - Ở bước 1: Khi tìm PACB ta phân phát tối đa cho ô có cij lớn nhất. - Ở bước 3: Nếu mọi ∆ij ≥ 0 tacó PATƯ. - Ở bước 4: Ô điều chỉnh là ô có ước lượng âm nhỏ nhất. Ví dụ 2.2.5: Giải bài toán vận tải sau: f(x) → max Thu

95

80

65

35

95

110

7

6

14

9

13

100

10

2

9

8

10

60

5

5

9

6

12

100

14

3

12

4

18

Phát

Ta có tổng phát = tổng thu = 370. Đây là BTVT cân bằng thu – phát. Xây dựng PACB ban đầu theo qui tắc phân phát tối đa cho ô có cước phí lớn nhất. - 81 -

Thu Phát

95

80

7

110

6 x

10

100

2

5

9

5

14

x 6 x 4

x

x 12

x 12

x 10

x

[60]

[5]

13 [35]

8

9

3

95

9 [65]

[10]

x 100

35

14 [10]

[90] 60

65

x 18

x

x

[95]

Số ô chọn là 8 đúng bằng hạng của BTVT: 4 + 5 – 1, Ta có PACB không suy biến xuất phát. Xây dựng hệ thống thế vị, tính các ước lượng và chỉ ghi các ước lượng ≤ 0 vào bảng: 7

6 + 10

14 [10]

2 [90] –

5

9 [65] –

9

[35]

9

0

– 3 10 (*)

8 +

[10]

5

13

6

–4

12

[60] 14

3

–1 12

4

18

[5]

[95]

14

6

14

9

0

18

q = min {10, 35} = 10, ô (2,2) sẽ bị loại ra khỏi cơ sở. 7

6

14 [20]

10

2

9

13

[65] 9

[25] 8

10

[90] 5

0

[10] 5

9

6

–1 12

[60] 14

3

–1 12

4

18

[5] 11

[95] 6

14

9

3

15 - 82 -

Ở bảng cuối ta thấy mọi ước lượng của các ô loại đều > 0 nên ta có PATƯ duy nhất:

 0   90 X=  0  5

20 65 25 0   0 0 10 0  60 0 0 0   0 0 0 95 

Và fmax = 6 x 20 + 14 x 65 + 9 x 25 + 10 x 90 + 8 x 10 + 5 x 60 + 14 x 5 + 18 x 95 = 4315.

Câu hỏi thảo luận chương 2 1. BTVT có phải là BT QHTT hay không ? 2. Vì sao BTVT luôn luôn có PATƯ ? 3. Khi xây dựng hệ thống thế vị, bước đầu tiên ta cho một thế vị nào đó bằng 0, sự lựa chọn đó có ảnh hưởng tới giá trị của các ước lượng Δij hay không ?

- 83 -

BÀI TẬP CHƯƠNG II Tất cả các BTVT dưới đây đều có hàm mục tiêu f(x)  min(max). Giải các BTVT cân bằng thu – phát: Bài 1: Thu

30

40

30

50

Phát 60

1

2

4

3

70

2

3

2

7

20

3

5

6

4

Bài 2: Thu Phát 100

60

70

40

30

7

6

9

8

80

10

8

7

11

20

11

7

6

10

Bài 3: Thu

80

70

45

90

Phát 105

8

9

22

11

100

7

14

16

20

80

12

16

10

17

Bài 4: Thu

70

30

80

70

Phát 120

7

4

8

6

50

8

9

5

7

80

4

5

3

8 - 84 -

Bài 5: Thu

100

50

30

70

Phát 80

4

6

4

6

70

5

6

8

9

55

4

5

5

4

45

6

6

9

9

Bài 6: Thu

40

70

60

50

Phát 45

8

7

5

5

80

5

4

3

4

40

3

5

4

6

55

9

8

7

6

Bài 7: Thu Phát 42

35

30

45

65

5

16

16

7

60

17

9

13

6

28

8

8

12

4

45

10

19

19

8

Bài 8: Thu Phát 4 100

120

80

50

90

14

11

10

70

13

15

18

16

60

2

6

10

9

110

7

9

15

8 - 85 -

Bài 9: Thu

60

50

45

80

85

Phát 80

6

16

24

17

5

100

8

13

14

18

15

50

12

9

20

5

9

90

10

13

8

16

4

Bài 10: Thu 150 Phát 24 140

110

175

70

80

4

2

12

21

220

30

8

9

17

28

125

20

5

6

3

16

100

9

12

7

4

6

Bài 11: Thu Phát 6 100

320

180

360

130

170

2

16

3

6

420

7

15

9

10

28

230

11

5

13

14

18

410

16

22

17

14

33

Bài 12: Thu Phát 4 60

40

110

50

70

40

3

7

13

5

80

5

6

14

12

16

75

2

5

10

9

7

95

7

11

8

14

11 - 86 -

Giải các BTVT không cân bằng thu – phát: Bài 13: Thu 50 Phát 12 40

80

65

14

25

60

22

17

13

45

15

18

19

65

16

23

26

Bài 14: Thu Phát 5 50

20

40

50

35

8

6

7

30

6

7

11

5

45

8

8

12

10

Bài 15: Thu Phát 1 20

35

25

70

6

12

80

3

12

21

40

4

15

20

60

2

10

15

Bài 16: Thu 50 Phát 11 70

95

35

70

12

14

13

90

7

5

6

4

50

7

8

7

10

- 87 -

Bài 17: Thu 100 Phát 7 125

65

95

80

12

11

14

75

8

13

10

10

150

5

11

7

9

50

6

9

7

8

Bài 18: Thu 130 Phát 6 100

85

60

35

13

16

12

120

10

8

7

3

80

11

15

13

9

50

14

19

5

17

- 88 -

Chương III: MÔ HÌNH SƠ ĐỒ MẠNG - PERT Mục đích: Trang bị cho người học các khái niệm bản về Lý thuyết sơ đồ mạng (SĐM) và ứng dụng của SĐM trong việc quản trị dự án về mặt thời gian và nhân lực. Kết thúc chương người học có thể lập được SĐM, tính được các chỉ tiêu thời gian, xác định được đường găng của dự án và xác định được tình hình sử dụng nhân công và máy móc thiết bị cho dự án.

3.1. Khái niệm về sơ đồ mạng 3.1.1. Ví dụ dẫn đến sơ đồ mạng Ví dụ 3.1.1: Giả sử công trình xây dựng X gồm có 10 công việc Y1, Y2, …, Y10. Thời gian thực hiện và trình tự tiến hành của các công việc được cho trong bảng sau: Công việc Thời gian thực hiện (tháng) Trình tự tiến hành Y1 2 Bắt đầu ngay Y2 4 Bắt đầu ngay Y3 3 Bắt đầu ngay Y4 11 Sau khi Y3 hoàn thành Y5 5 Sau khi Y1 hoàn thành Y6 4 Sau khi Y1 hoàn thành Y7 6 Sau khi Y1 hoàn thành Y8 3 Sau khi Y2 , Y5 hoàn thành Y9 4 Sau khi Y7 , Y8 hoàn thành Y10 5 Sau khi Y6 hoàn thành Có một số vấn đề đặt ra với dự án trên là : - Sau bao lâu dự án trên hoàn thành (theo định mức) ? - Trong quá trình thực hiện những nhóm công việc nào quan trọng, chúng có vai trò gì tới tiến trình kết thúc dự án ? - Quan sát một thời điểm cụ thể trong tiến trình dự án thì công việc nào đã làm xong, công việc nào đang làm, công việc nào chưa làm, công việc nào bị làm chậm so với tiến độ...v.v ? Để trả lời những câu hỏi trên, nếu chỉ quan sát vào bảng số liệu đã có thì đó là một việc không dễ dàng. Điều đó dẫn tới, phải có phương pháp hoặc một cách thức để phân tích dự án một cách chi tiết, và PERT (Program Evaluation and Review Technique) là một trong số phương pháp đó. 3.1.2. Các khái niệm cơ bản PERT có thể được hiểu là phương pháp hoặc kỹ thuật theo dõi và đánh giá dự án với mục đích giúp cho bộ máy quản lí trả lời các câu hỏi sau đâu: - 89 -

- Dự án sẽ hoàn thành khi nào ? - Mỗi hoạt động của dự án được bắt đầu vào thời điểm nào và kết thúc vào thời điểm nào ? - Trong dự án thì những công việc nào đóng vai trò quan trọng về mặt thời gian ? Định nghĩa sơ đồ mạng lưới PERT một cách chặt chẽ theo lý thuyết đồ thị thì : Sơ đồ mạng là đồ thị đơn, hữu hạn, liên thông, không khuyên, không chu trình và phản xứng. Trong đó có 1 đỉnh đầu (chỉ có cung hướng ra), 1 đỉnh cuối (chỉ có cung hướng vào) và các cung luôn hướng từ đỉnh có số thấp tới đỉnh có số cao. Trên mỗi cung có ghi thời gian hoàn thành công việc tương ứng. - Đồ thị: là tập hợp các đỉnh và các cạnh (cung) nối chúng với nhau. - Đồ thị đơn : là đồ thị mà giữa 2 đỉnh bất kỳ chỉ có tối đa 1 cung nối chung với nhau. - Đồ thị hữu hạn : là tập hợp hữu hạn các đỉnh và cung. - Đồ thị liên thông : là đồ thị mà giữa 2 đỉnh bất kỳ luôn có 1 đường đi vô hướng nối chúng với nhau. - Đồ thị không khuyên: là đồ thị không có cung nào xuất phát từ 1 đỉnh rồi quay lại chính đỉnh đó. - Đồ thị không chu trình : là đồ thị không có đường đi có hướng khép kín. - Đồ thị phản xứng : là đồ thị mà mỗi cung chỉ có 1 chiều. Nhưng với khối lượng kiến thức toán mà sinh viên tích lũy được, chúng ta không đi sâu theo hướng chặt chẽ của định nghĩa trên mà tiếp cận sơ đồ mạng lưới-PERT theo quan điểm thực hành, cụ thể như sau : Sơ đồ mạng sử dụng 2 yếu tố lôgic là công việc và sự kiện. - Công việc: Là hoạt động sử dụng thời gian, nhân lực, vật lực, máy móc, nguyên vật liệu trong quá trình sản xuất thi công. Chúng được biểu thị bằng mũi tên nét liền, phía trên ghi tên công việc, phía dưới ghi thời gian hoàn thành. - Công việc giả: Là hoạt động không có thực, chúng được biểu thị bằng mũi tên nét đứt, dùng biểu thị trình tự của một công việc hoặc nhóm công việc (với tij = 0). - Sự kiện (biến cố) : Là mốc thời gian hoàn thành 1 số công việc và khởi đầu của một số công việc khác, chúng được biểu thị bằng hình tròn. Có mấy loại sự kiện sau: + Sự kiện khởi công: chỉ có mũi tên đi ra. + Sự kiện kết thúc : chỉ có mũi tên đi vào. + Sự kiện trung gian : vừa có mũi tên đi vào vừa có mũi tên đi ra. Trở lại ví dụ 3.1.1 về công trình xây dựng trên, ta có thể biểu diễn quá trình thực hiện bằng sơ đồ như sau : - 90 -

Hình 3.1 Lưu ý : Các cung (công việc) xuất phát từ đỉnh i và hướng tới đỉnh j được ký hiệu là (i, j). Thời gian hoàn thành công việc được ký hiệu là tij. Ví dụ công việc Y1 được ký hiệu là (0, 1) và t01 = 2. 3.1.3. Các quy tắc thực hành lập sơ đồ mạng lưới PERT Khi lập sơ đồ mạng lưới PERT theo quan điểm thực hành, để cho việc phân tích thời gian được chính xác và không vi phạm các yếu tố cơ bản về mạng lưới trong lý thuyết đồ thị, ta tuân thủ một số quy tắc sau. Quy tắc 1: Lập theo trình tự của dự án. Công việc nào dự án (đề bài) yêu cầu biểu thị trước thì vẽ trước, tiếp theo đến công việc nào biểu thị sau thì vẽ sau. Quy tắc 2 (Vẽ song song): Giữa hai sự kiện bất kì chỉ được vẽ tối đa một công việc (đồ thị đơn). Nếu có nhiều công việc cùng làm song song mà biểu diễn như hình 3.2a là sai quy tắc đồ thị đơn. Khi đó ta cần lập thêm các đỉnh giả và các cạnh giả với tij = 0 (Hình 3.2b).

t1

i1 t1

i

t2

tg1 0

j

t2

i

t3

t3

j

tg2 0

Hình 3.2a Hình 3.2b

i2

- 91 -

Quy tắc 3: - Nếu Z4 khởi công sau khi xong Z1, Z2 còn Z5 khởi công sau Z1, Z2, Z3 thì ta vẽ như hình 3.3a. Biểu diễn như hình 3.3b là sai. - Nếu Z4 khởi công sau khi xong Z1, Z2 còn Z5 khởi công sau Z2, Z3 thì vẽ như hình 3.3c. Z1

Z1

Z4

Z4 Z2

Z1

Z4

Z2

Z2 Z3

Z3

Z5

Z3

Z5

Hình 3.3a: Biểu diễn đúng Hình 3.3b: Biểu diễn sai

Z5

Hình 3.3c: Biểu diễn đúng

Quy tắc 4: Khi chia nhỏ công việc chẳng hạn công việc a, b, c bắt đầu khi hoàn thành 1/3; 2/3 và cả công việc X thì vẽ như hình 3.4a (chứ không phải hình 3.4b). a

b

c

a X

X/3

X/3

b c

X/3

Hình 3.4a: Biểu diễn đúng Hình 3.4b: Biểu diễn sai Quy tắc 5: Nếu có 1 nhóm công việc tạo thành 1 mạch con khi đưa ra mạch lớn thì ta có thể coi là 1 việc với thời gian bằng đường găng của mạch con (hình 3.5). 2

t2 t1 i

t5 t3

t7

1

j

4

t4

t6 3

T = tổng đường găng j

i Hình 3.5

- 92 -

Quy tắc 6 (Đánh chỉ số đỉnh): Các đỉnh trên sơ đồ mạng phải thỏa mãn điều kiện: Nếu (i, j) là một cung thì i < j, có nghĩa là mọi cung đều hướng từ đỉnh số thấp tới đỉnh số cao hơn. Để thỏa mãn điều kiện này, khi đánh số các đỉnh ta thực hiện các bước sau : Bước 1: Đỉnh đầu tiên (sự kiện đầu) được đánh số 0. Bước 2: Sau khi đánh số đỉnh i, ta đánh dấu gạch tất cả các cung xuất phát từ đỉnh đó. Đỉnh được đánh số tiếp theo (i + 1) là đỉnh trong phần sơ đồ còn lại (trừ các đỉnh đã đánh số và các cung đã gạch) chỉ có cung hướng ra, không có cung hướng vào, nếu có nhiều đỉnh như vậy thì ta chọn đỉnh nào trước cũng được. Tiếp tục quay lại bước 2 cho tới khi tất cả các đỉnh được đánh số. Ví dụ ở sơ đồ trên, sau khi đánh số đỉnh đầu tiên với số 0, ta gạch 3 cạnh đi ra từ đỉnh 0 đó là Y1, Y2, Y3 (có thể gạch bằng bút chì ở đầu cạnh), như vậy đỉnh số 1 có thể đánh ở phần đuôi công việc Y1 hoặc Y3 nhưng không thể ở phần đuôi công việc Y2 (vì vẫn có Y5 hướng vào). Ở sơ đồ trên, sau khi đánh số đỉnh 1, ta tiếp tục gạch 3 cạnh xuất phát từ đó là Y5, Y6 và Y7 sau đó tìm đỉnh không có cạnh hướng vào để đánh số 2 v.v.

3.2. Các chỉ tiêu thời gian trong Sơ đồ mạng 3.2.1. Các chỉ tiêu thời gian đối với sự kiện a. Thời điểm sớm nhất xuất hiện sự kiện Ký hiệu tj(s) là thời điểm sớm nhất xuất hiện sự kiện j. Thời gian thực hiện một quá trình sản xuất, thi công thường được tính từ thời điểm khởi công (sự kiện đầu) nên t0(s) = 0. Ở các sự kiện j ≠ 0, tj(s) là thời điểm sớm nhất mà tất cả các công việc hướng tới nó đều hoàn thành. Vì vậy: tj(s) = max{ ti(s) + tij , với mọi (i, j) hướng tới j }.

(3.1)

Quay lại ví dụ trên ta có: t0(s) = 0;

t1(s) = t0(s) + 2 = 2;

t2(s) = t0(s) + 3 = 3;

t3(s) = max{t0(s) + 4, t1(s) +5} = max{4;7} = 7; t4(s) = t1(s) + 4 = 2 + 4 = 6 ; t5(s) = max{t1(s) + 6; t3(s) + 3} = max{8;10} = 10; t6(s) = max{t4(s) + 5; t5(s) + 4); t2(s) + 11} = max{11;14;14} = 14. b. Thời điểm muộn nhất xuất hiện sự kiện Ký hiệu ti(m) là thời điểm muộn nhất xuất hiện sự kiện i. Khi sự kiện cuối (n) xuất hiện có nghĩa là toàn bộ quá trình sản xuất, thi công kết thúc. Vì vậy ta có tn(m) = tn(s). - 93 -

Ở các sự kiện i ≠ n, ti(m) là thời điểm muộn nhất có thể xảy ra mà không làm ảnh hưởng tới thời gian hoàn thành của tất cả các công việc diễn ra sau nó. Vì vậy: ti(m) = min{ tj(m) – tij , với mọi (i, j) xuất phát từ i }.

(3.2)

Ở ví dụ trên ta có: t6(m) = t6(s) = 14; t3(m) = t5(m) – 3 = 7;

t5(m) = t6(m) – 4 = 10; t4(m) = t6(m) – 5 = 9; t2(m) = t6(m) – 11 = 3;

t1(m) = min{t4(m) – 4; t5(m) – 6 ; t3(m) – 5} = min{5; 4; 2} = 2; t0(m) = min{t1(m) – 2; t2(m) – 3; t3(m) – 4} = min{0; 0; 3} = 0. c. Thời gian dự trữ của sự kiện Ký hiệu Di là thời gian dự trữ của sự kiện i, ta có như sau : Di = ti(m) – ti(s). Nếu Di = 0 thì sự kiện i được gọi là sự kiện găng. Sự kiện găng là sự kiện chỉ được xảy ra ở một thời điểm nhất định của quá trình thực hiện. Ở ví dụ trên ta có: D0 = 0, D1 = 0, D2 = 0, D3 = 0, D4 = 3, D5 = 0, D6 = 0. Đỉnh (4) không phải đỉnh găng. 3.2.2. Các chỉ tiêu thời gian đối với công việc a. Thời điểm sớm nhất khởi công và hoàn thành công việc Ký hiệu tkij(s) và thij(s) là thời điểm sớm nhất khởi công và hoàn thành công việc (i, j). Ta có: tkij(s) = ti(s) và thij(s) = ti(s) + tij . b.Thời điểm muộn nhất khởi công và hoàn thành công việc Ký hiệu tkij(m) và thij(m) là thời điểm muộn nhất khởi công và hoàn thành công việc (i,j). Ta có: thij(m) = tj(m) và tkij(m) = tj(m) – tij . c. Thời gian dự trữ chung (toàn phần) của công việc Dự trữ chung của mỗi công việc là hiệu số giữa thời gian hoàn thành muộn nhất và sớm nhất của công việc đó, ký hiệu là Dij(c): Dij(c) = thij(m) – thij(s) = tkij(m) – tkij(s) = tj(m) – ti(s) – tij . Nếu Dij(c) = 0 thì công việc đó là công việc găng. Công việc găng là công việc không có thời gian dự trữ, nó phải được thực hiện theo đúng tiến độ của quá trình. Trở lại ví dụ trên ta điền các chỉ tiêu thời gian đối với các công việc vào bảng sau:

- 94 -

Công việc

tij

tkịj(s) = ti(s)

thịj(s) = ti(s) + tij

thịj(m) = tj(m)

tkịj(m) = tj(m) − tij

Y1(0,1)

2

0

2

2

0

Dij(c) = thịj(m) – thịj(s) 0 (Găng)

Y2(0,3)

4

0

4

7

3

3

Y3(0,2)

3

0

3

3

0

0 (Găng)

Y4(2,6)

11

3

14

14

3

0 (Găng)

Y5(1,3)

5

2

7

7

2

0 (Găng)

Y6(1,4)

4

2

6

9

5

3

Y7(1,5)

6

2

8

10

4

2

Y8(3,5)

3

7

10

10

7

0 (Găng)

Y9(5,6)

4

10

14

14

10

0 (Găng)

Y10(4,6)

5

6

11

14

9

3

Bảng 3.1 Các chỉ tiêu thời gian đối với công việc 3.2.3. Đường găng trên sơ đồ mạng a. Định nghĩa Đường găng là đường nối các sự kiện găng bằng các công việc găng (tô đậm các công việc găng). Trên đường găng các sự kiện và các công việc không có thời gian dự trữ và phải được thực hiện theo đúng tiến độ của mình. Chính vì thế các sự kiện găng và các công việc găng là các sự kiện và các công việc quan trọng mà ta phải quan tâm nhiều hơn. Cụ thể là phải chuẩn bị đầy đủ nguyên vật liệu, nhân lực, máy móc thiết bị để tiến độ trên đường găng được đảm bảo trước. Lưu ý: - Trên SĐM có ít nhất 1 (có thể nhiều hơn 1) đường găng. - Đường găng là đường có tổng thời gian lớn nhất. - Đường găng là đường liên tục xuất phát từ đỉnh đầu và kết thúc ở đỉnh cuối. - Các chỉ tiêu thời gian luôn không âm. b. Tìm đường găng trên sơ đồ mạng Có 2 cách tìm đường găng trên SĐM. Cách 1: Dựa vào bảng chỉ tiêu thời gian đối với công việc (bảng 3.1) ta thấy những công việc nào là công việc găng (Dij(c) = 0) thì tô trên SĐM bằng nét đậm (hoặc nét đôi). Ví dụ ở bảng 3.1 ta thấy các công việc găng là Y1, Y3, Y4, Y5, Y8 và Y9. Tô đậm các công việc đó ta sẽ có 2 đường găng. - 95 -

Cách 2: Dùng để tìm nhanh đường găng trước khi tính các chỉ tiêu thời gian đối với công việc (tính bảng 3.1 sau). Ta vẽ lại SĐM bằng cách chia mỗi đỉnh thành 4 phần và ghi các giá trị như sau:

Chỉ số sự kiện j tj(s)

tj(m) k Hình 3.6

Trong đó k là chỉ số i được chọn trong công thức 3.1 (trang 93), tức là với chỉ số đó thì ti(s) + tij đạt max, nói cách khác kết quả tj(s) đến từ đỉnh k phía trước. Sau đó từ đỉnh cuối cùng ta tô đậm ngược lại đỉnh số k phía trước. Tiếp theo, từ đỉnh đó ta tô đậm về phía trước theo đỉnh k' được ghi ở góc phần tư phía dưới của đỉnh đó. Cứ như vậy tới khi về tới đỉnh đầu tiên. Trở lại ví dụ trên, ta tìm k: t0(s) = 0, k = 0; t1(s) = t0(s) + 2 = 2, k = 0; t2(s) = t0(s) + 3 = 3, k = 0; t3(s) = max{t0(s) + 4, t1(s) +5} = max{4;7} = 7, k = 1; (vì kết quả này đến từ đỉnh 1) t4(s) = t1(s) + 4 = 2 + 4 = 6, k = 1; t5(s) = max{t1(s) + 6; t3(s) + 3} = max{8;10} = 10, k = 3; (vì kết quả này đến từ đỉnh 3) t6(s) = max{t4(s) + 5; t5(s) + 4); t2(s) + 11} = max{11;14;14} = 14, k = 5; 2. Lưu ý: Các chỉ tiêu trên có thể tính trực tiếp trên SĐM (phần tính ở trên chỉ để minh họa cách tính, khi làm bài có thể bỏ phần trình bầy ở trên).

- 96 -

Hình 3.7 Cách tìm đường găng: Từ đỉnh số 6 ta tô đậm tới đỉnh 5 và đỉnh 2 (k = 5; 2). Tiếp theo từ đỉnh 5 ta tô ngược về đỉnh 3. Từ đỉnh 3 lại tô ngược về đỉnh 1 và từ đỉnh 1 về đỉnh 0. Tương tự, từ đỉnh 2 ta tô ngược về đỉnh 0. Như vậy ta có 2 đường Găng: - Đường Găng 1: (0) – (1) – (3) – (5) – (6); hoặc: y1 - y5 - y8 - y9. - Đường Găng 2: (0) – (2) – (6); hoặc: y3 - y4. Nhận xét: Cách thứ 2 giúp cho ta xác định các chỉ tiêu thời gian đối với sự kiện và đường găng một cách nhanh nhất và ít sai sót nhất, chính vì vậy ta nên dùng cách này. Các chỉ tiêu thời gian đối với công việc vẫn được tính như bảng 3.1.

3.3. Bài toán xác định nhân lực và tài nguyên trên sơ đồ mạng Để xác định số lượng nhân công, máy móc thiết bị, tài chính, nguyên vật liệu trong quá trình sản xuất thi công ta có thể sử dụng biểu đồ Gant. Trên mỗi công việc ta ghi số lượng công nhân, thiết bị, tài nguyên…, sau đó ở các giai đoạn ta cộng các số liệu đó lại. Ví dụ 3.3.1: Trở lại công trình xây dựng trên: Công việc Thời gian thực Trình tự tiến hành hiện (tháng) Y1 2 Bắt đầu ngay Y2 4 Bắt đầu ngay Y3 3 Bắt đầu ngay Y4 11 Sau khi Y3 hoàn thành Y5 5 Sau khi Y1 hoàn thành Y6 4 Sau khi Y1 hoàn thành

Số công nhân (CN) thi công 15 12 9 25 7 10 - 97 -

Y7 Y8 Y9 Y10

6 3 4 5

Sau khi Y1 hoàn thành Sau khi Y2 , Y5 hoàn thành Sau khi Y7 , Y8 hoàn thành Sau khi Y6 hoàn thành

14 8 11 6

Ta có biểu đồ sau : Công việc (số CN)

Thời gian thực hiện (tháng) 1

2

3

4

5

6

7

8

9

10

11

12

13

14

36

36

52

68

56

56

52

53

39

39

42

36

36

36

Y1 (15) Y2 (12) Y3 (9) Y4 (25) Y5 (7) Y6 (10) Y7 (14) Y8 (8) Y9 (11) Y10 (6) Tổng số CN

Bảng 3.2: Biểu đồ Gant Các công việc được biểu diễn bằng các đường đậm nét với điểm đầu dựa vào trình tự tiến hành của các công việc đó với độ dài chính bằng thời gian thực hiện của chúng. Nhìn vào biểu đồ trên ta thấy số công nhân (CN) cần huy động nhiều nhất là 68 CN vào tháng thứ 4 của quá trình thi công, số CN tối thiểu cần có là 36 người vào tháng thứ 1, 2, 12, 13 và 14 của quá trình. Để giảm bớt số CN cần huy động vào tháng thứ tư ta cần lùi tiến độ một số công việc nào đó. Nhìn vào bảng 3.1 ta thấy liên quan đến tháng thứ tư, các công việc có thời gian dự trữ là Y6 và Y7. Nhưng thích hợp nhất là lùi tiến độ công việc Y7 sau 2 tháng. Khi đó số CN tháng 3 và thứ 4 giảm 14 CN, số CN tháng thứ 9 và thứ 10 tăng 14 CN. Như vậy số CN cần huy động nhiều nhất sẽ là 56 CN vào tháng thứ 5 và tháng thứ 6.

3.4. Rút ngắn đường găng của sơ đồ mạng - 98 -

Quay lại ví dụ với công trình xây dựng trên. Giả sử ta cần đẩy nhanh tiến độ thi công để rút ngắn thời gian hoàn thành toàn bộ công trình xuống còn 10 tháng thì cần phải rút ngắn thời gian thực hiện của những công việc nào sao cho chi phí rút ngắn là ít nhất. Dưới đây là bảng về thời gian có thể rút ngắn được và chi phí rút ngắn tương ứng: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

Thời gian hoàn thành (tháng) Bình thường 2 4 3 11 5 4 6 3 4 5

Có thể rút được 1 2 2 4 2 2 2 1 2 2

Chi phí rút ngắn (triệu đồng/tháng) 3 2 4 5 1 3 6 2 5 4

Gọi yi là thời gian rút ngắn của công việc Yi ; xj = tj(s) là thời điểm sớm nhất xuất hiện sự kiện j. Ta có x0 = 0, x6 = 10. Áp dụng công thức (3.1): tj(s) = max{ti(s) + tij với mọi công việc hướng tới j} suy ra: xj ≥ ti(s) + tij = xi + tij với mọi công việc hướng tới j. Ta có mô hình bài toán: f(y) = 3y1 + 2y2 + 4y3 + 5y4 + y5 + 3y6 + 6y7 + 2y8 + 5x9 + 4y10 → min x1 = 2 – y1

y1 ≤ 1

x2 = 3 – y3

y2 ≤ 2

x3 ≥ x1 + 5 – y5

y3 ≤ 2

x3 ≥ 4 – y2

y4 ≤ 4

x4 = x1 + 4 – y6

y5 ≤ 2

x5 ≥ x1 + 6 – y7

y6 ≤ 2

x5 ≥ x3 + 3 – y8

y7 ≤ 2

10 ≥ x4 + 5 – y10

y8 ≤ 1

10 ≥ x5 + 4 – y9

y9 ≤ 2

10 ≥ x2 + 11 – y4

y10 ≤ 2

xj ≥ 0, j = 1,...,5 ; yi ≥ 0, i = 1,...,10. (Xem lại sơ đồ hình 3.1 tr 91).

- 99 -

Giải bài toán trên ta được PATƯ: y1 = 1, y2 = 0, y3 = 2, y4 = 2, y5 = 2, y6 = 0, y7 = 0, y8 = 0, y9 = 1, y10 = 0 ; x1 = 1, x2 = 1, x3 = 4, x4 = 5, x5 = 7 và f(y)min = 28 triệu đồng. Khi đó ta có sơ đồ mới:

Hình 3.8 Sau khi tính toán các chỉ tiêu thời gian ta thấy tất cả các công việc đều là găng và độ dài đường Găng là 10.

Câu hỏi thảo luận chương 3 1. Sơ đồ mạng (SĐM) là gì? 2. Trong SĐM, đỉnh có chỉ số lớn nhất là đỉnh nào? 3. Nếu trong một SĐM có n đỉnh thì số cạnh tối đa là bao nhiêu? 4. Có SĐM nào không có đường găng? 5. Độ dài đường găng có ý nghĩa gì?

- 100 -

BÀI TẬP CHƯƠNG III Trong các bảng công việc dưới đây, hãy lập sơ đồ mạng, tính các chỉ tiêu thời gian, tìm đường găng và thời gian hoàn thành toàn bộ công trình: Bài 1: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7

Thời gian thực hiện (ngày) 4 8 5 6 10 2 5

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y3 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y1 , Y6 hoàn thành

Thời gian thực hiện (tháng) 3 6 4 2 8 7 5 9

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Sau khi Y2 hoàn thành Sau khi Y3 hoàn thành Sau khi Y2 hoàn thành Sau khi Y4 hoàn thành Sau khi Y1 , Y6 hoàn thành Sau khi Y5 hoàn thành

Thời gian thực hiện (giờ) 5 12 10 7 6 8 9 4 15

Trình tự tiến hành Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y3 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y5 hoàn thành Sau khi Y5 hoàn thành Sau khi Y4, Y6 hoàn thành

Bài 2: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Bài 3: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9

- 101 -

Bài 4: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11

Thời gian thực hiện (giờ) 3 4 5 6 2 4 8 6 11 6 3

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y3 hoàn thành Sau khi Y7 hoàn thành Sau khi Y6 hoàn thành Sau khi Y4 , Y5 hoàn thành Sau khi Y8 , Y9 hoàn thành

Thời gian thực hiện (tháng) 13 11 15 16 13 18 14 16 17 19 13

Trình tự tiến hành Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y3 hoàn thành Sau khi Y4 hoàn thành Sau khi Y5 hoàn thành Sau khi Y6 hoàn thành Sau khi Y7 hoàn thành Sau khi Y8 , Y9 hoàn thành

Thời gian thực hiện (ngày) 2 3 5 7 4 4 10 6 2 6 4

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y3 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y1 hoàn thành Sau khi Y4 , Y5 hoàn thành Sau khi Y4 , Y5 hoàn thành Sau khi Y7 hoàn thành Sau khi Y6 , Y9 hoàn thành

Bài 5: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Bài 6: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11

- 102 -

Bài 7: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

Thời gian thực hiện (tuần) 4 7 5 8 12 9 8 15 4 7

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y2 , Y3 hoàn thành Sau khi Y2 , Y3 hoàn thành Sau khi Y4 hoàn thành Sau khi Y5 , Y6 hoàn thành Sau khi Y8 hoàn thành

Thời gian thực hiện (tháng) 1 3 5 4 6 3 5 6 7 2

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y4 , Y5 hoàn thành Sau khi Y6 hoàn thành Sau khi Y3 hoàn thành Sau khi xong Y7, Y8 và Y9

Thời gian thực hiện (tháng) 1 3 5 4 6 3 5 6 7 2

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y3 hoàn thành Sau khi Y5, Y7 hoàn thành Sau khi Y4, Y6 hoàn thành Sau khi Y8, Y9 hoàn thành

Bài 8: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Bài 9: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

- 103 -

Bài 10*: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9

Thời gian thực hiện (tháng) 3 4 3 4 2 1 4 2 4

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y2 , Y4 hoàn thành Sau khi Y3 , Y5 hoàn thành Sau khi xong Y2 , Y3, Y4 , Y5, Y6

Bài 11*: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

Thời gian thực hiện (giờ) 3 5 7 9 6 12 11 8 4 5

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y3 hoàn thành Sau khi Y3 hoàn thành Sau khi Y2 ,Y4 , Y5 ,Y6 hoàn thành Sau khi Y2 , Y5 ,Y6 hoàn thành Sau khi Y7 hoàn thành

Bài 12*: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

Thời gian thực hiện (tháng) 5 4 6 9 7 3 8 5 10 6

Trình tự tiến hành Bắt đầu ngay Bắt đầu ngay Sau khi Y2 hoàn thành Sau khi Y2 hoàn thành Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y1 hoàn thành Sau khi Y3 , Y5 hoàn thành Sau khi Y7 , Y8 hoàn thành Sau khi Y4 , Y6 hoàn thành

Ở các bài tập dưới đây yêu cầu: Lập sơ đồ mạng, tính các chỉ tiêu thời gian, xác định đường găng và tính số công nhân cần sử dụng ở từng thời điểm. - 104 -

Bài 13: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

Trình tự thực hiện Bắt đầu ngay Bắt đầu ngay Sau khi xong Y1 Sau khi xong Y2 và Y3 Sau khi xong Y1 Sau khi xong Y4 Sau khi xong Y5 và Y6 Sau khi xong Y4 Sau khi xong Y7 và Y8 Sau khi xong Y4

Thời hạn (tuần) 2 1 3 4 3 2 4 1 1 2

Số công nhân 11 8 15 9 7 10 6 18 13 14

Trình tự thực hiện Bắt đầu ngay Bắt đầu ngay Bắt đầu ngay Sau khi xong Y3 Sau khi xong Y2 và Y4 Sau khi xong Y3 Sau khi xong Y1 Sau khi xong Y1 Sau khi xong Y5 và Y7 Sau khi xong Y8 và Y9

Thời hạn (ngày) 2 3 1 4 3 10 4 8 5 3

Số công nhân 7 12 10 8 7 13 6 15 11 12

Trình tự thực hiện Bắt đầu ngay Bắt đầu ngay Sau khi xong Y2 Sau khi xong Y2 Sau khi xong Y2 Sau khi xong Y1 và Y3 Sau khi xong Y6 Sau khi xong Y4 và Y7 Sau khi xong Y6 Sau khi xong Y5

Thời hạn (tháng) 2 1 3 8 7 5 4 3 6 5

Số công nhân 15 11 9 8 10 18 7 14 6 12

Bài 14: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Bài 15: Công việc Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10

- 105 -

ĐÁP SỐ CỦA CÁC BÀI TẬP Bài tập chương I 13. X0 = (–4/3, –4, 2/3, 0); X = (–4/3 + x4, –4, 2/3 – x4, x4). 14. X0 = (4, 2, 2) nghiệm duy nhất. 15. X0 = (0, –10, 9, 15); X = (x1, –10 + 15x1, 9 – 10x1, 15 – 18x1). 16. X0 = (0, –16, 17/3, 26/3, –7/3); X = (x1, –16 + 28x1, 17/3 – 22x1/3, 26/3 – 37x1/3, –7/3 + 23x1/3). 17. f(x)min = 34, X = (5, 0, 0, 1, 16, 0) duy nhất; f(x)max = 134, X = (0, 0, 0, 6, 26, 10) duy nhất. 18. f(x)min = 56/3, X = (14/3, 0, 0, 0, 0, 10/3, 6) duy nhất; f(x)max = 44, X = (0, 6, 4, 0, 0, 0, 2) duy nhất. 19. f(x)min = –110, X = (80, 70, 0, 0, 0, 18) duy nhất; f(x)max = 30, X = (0, 8, 6, 0, 56, 0) duy nhất. 20. f(x) không bị chặn dưới và chặn trên. 21. f(x)min = –24, X1 = (0, 3, 18, 0, 0, 18) có vô số PATƯ; f(x)max = 30, X = (0, 0, 0, 6, 0, 0) duy nhất. 22. f(x)min = –106, X = (0, 0, 34, 16, 128, 0) duy nhất; f(x) không bị chặn trên. 23. f(x)min = 4, X1 = (0, 1, 0, 2, 0, 6) có vô số PATƯ; f(x) không bị chặn trên. 24. f(x)min = 32, X = (2, 6, 0, 6) duy nhất; f(x)max = 52, X = (14, 29, 5, 0) duy nhất. 25. f(x)min = 11, X = (1, 5, 0, 4) duy nhất; f(x)max = 67/5, X = (11/5, 53/5, 4/5, 0) duy nhất. 26. f(x) không bị chặn dưới; f(x)max = 26, X1 = (24, 0, 20, 0, 0, 0, 6) có vô số PATƯ. 27. f(x)min = 60, X = (5, 0, 0, 10, 0, 35) duy nhất; f(x)max = 170, X = (10, 20, 15, 0, 0, 0) duy nhất. 28. f(x)min = 6, X = (5, 0, 0, 1, 9) duy nhất; f(x)max = 110/3, X = (46/3, 22/3, 4/3, 0, 0) duy nhất. 29. f(x)min = –42, X = (0, 8, 18, 0, 0, 0, 2) duy nhất; - 106 -

f(x)max = 10, X = (4, 0, 6, 0, 14, 0, 0) duy nhất. 30. f(x)min = –10, X = (2, 0, 0, 14, 38) duy nhất; f(x)max = 93/5, X = (23/10, 3/5, 67/10, 0, 0) duy nhất. 31. f(x) không bị chặn dưới và chặn trên. 32. X0 = (0, 24, 0, 16, 0), Y0 = (–3, 0, –2), f(x)min = f (y)max  96. 33. X0 = (0, 6, 24), Y0 = (1, 0, 2), f(x)min = f (y)max  42. 34. X0 = (0, 14, 6, 5, 0, 0), Y0 = (1, –6/5, 2/5), f(x)min = f (y)max  40. 35. X0 = (0, 0, 12, 4, 0, 22, 0), Y0 = (3/2, 0, 2), f(x)min = f (y)max  52. 36. X0 = (8, 0, 10, 8, 0, 0), Y0 = (1/5, 1, –11/10), f(x)min = f (y)max  46. 37. X0 = (0, 3, 0, 3, 0, 21, 0), Y0 = (–9/4, 0, 5/4), f(x)min = f (y)max  9. 38. X0 = (0, 25/4, 0, 15/4, 0, 0, 0), Y0 = (1, y3 – 8, y3) với y3 ≤ 3 , f(x)min = f (y)max  65. 39. f(x)min = f (y)max  46, X0 = (0, 3, 20, 0, 0, 0, 120), Y0 = (4/3, 1/2, 0); f(x) không bị chặn trên, bài toán đối ngẫu không có PA. 40. f(x) không bị chặn dưới, bài toán đối ngẫu không có PA; f(x)max = f (y)min  46, X0 = (16, 0, 0, 14, 20, 0), Y0 = (1, 2, 1/3).

41. f(x) không bị chặn dưới và chặn trên, bài toán đối ngẫu không có PA. 42. f(x)min = f (y)max  116 / 7, X0 = (26/7, 0, 32/7, 0, 0, 108/7, 0), Y0 = (–2/7, 0, 10/7); f(x)max = f (y)min  82, X0 = (0, 0, 20, 0, 42, 0, 8), Y0 = (1, 4, 0).

Bài tập chương II 1. f(x)min = 380, có vô số PATƯ; f(x)max = 660, có vô số PATƯ. 2. f(x)min = 1460, có vô số PATƯ; f(x)max = 1750, PATƯ duy nhất. 3. f(x)min = 2940, PATƯ duy nhất; f(x)max = 1750, PATƯ duy nhất. 4. f(x)min = 1220, PATƯ duy nhất; f(x)max = 1950, có vô số PATƯ. 5. f(x)min = 1195, PATƯ duy nhất; f(x)max = 1630, có vô số PATƯ. 6. f(x)min = 990, có vô số PATƯ; f(x)max = 1295, có vô số PATƯ. 7. f(x)min = 1476, có vô số PATƯ; f(x)max = 2276, có vô số PATƯ. 8. f(x)min = 2780, có vô số PATƯ; f(x)max = 3970, PATƯ duy nhất. 9. f(x)min = 2580, PATƯ duy nhất; f(x)max = 5120, PATƯ duy nhất. 10. f(x)min = 5640, PATƯ duy nhất; f(x)max = 9660, PATƯ duy nhất. 11. f(x)min = 12440, PATƯ duy nhất; f(x)max = 19460, có vô số PATƯ. 12. f(x)min = 2115, có vô số PATƯ; f(x)max = 3370, PATƯ duy nhất. - 107 -

13. f(x)min = 2955, PATƯ duy nhất; f(x)max = 4390, PATƯ duy nhất. 14. f(x)min = 795, PATƯ duy nhất; f(x)max = 1210, có vô số PATƯ. 15. f(x)min = 1365, PATƯ duy nhất; f(x)max = 1955, PATƯ duy nhất. 16. f(x)min = 1535, có vô số PATƯ; f(x)max = 1980, PATƯ duy nhất. 17. f(x)min = 2690, có vô số PATƯ; f(x)max = 3455, có vô số PATƯ. 18. f(x)min = 2095, có vô số PATƯ; f(x)max = 4200, có vô số PATƯ. Bài tập chương III 1. Đường găng: Y2 – Y5, T = 18. 2. Đường găng: Y2 – Y3 – Y4 – Y6 – Y7, T = 24. 3. Đường găng: Y1 – Y2 – Y6 – Y9, T = 40. 4. Đường găng: Y2 – Y6 – Y9 – Y11 và Y3 – Y7 – Y8 – Y11, T = 22. 5. Đường găng: Y1 – Y3 – Y6 – Y9 – Y11, T = 76. 6. Đường găng: Y1 – Y7 – Y10, Y3 – Y4 – Y9 – Y11 và Y3 – Y4 – Y8, T = 18. 7. Đường găng: Y1 – Y4 – Y8 – Y10, T = 34. 8. Đường găng: Y2 – Y5 – Y7 – Y10, T = 16. 9. Đường găng: Y3 – Y7 – Y8 – Y10, T = 18. 10. Đường găng: Y1 – Y4 – Y7 và Y1 – Y4 – Y1g – Y9, T = 11. 11. Đường găng: Y3 – Y6 – Y1g – Y8, T = 27. 12. Đường găng: Y1 – Y5 – Y8 – Y9, T = 27. 13. Đường găng: Y1 – Y3 – Y4 – Y6 – Y7 – Y9, T = 16. 14. Đường găng: Y3 – Y4 – Y5 – Y9 – Y10, T = 16. 15. Đường găng: Y2 – Y3 – Y6 – Y7 – Y8, T = 16.

- 108 -

Tài liệu tham khảo [1]

Nguyễn Thành Cả, 2006, “Tối ưu hóa tuyến tính”, Trường Đại học Kinh tế Thành phố Hồ Chí Minh.

[2]

Nguyễn Quang Dong, Ngô Văn Thứ, Hoàng Đình Tuấn, “ Mô hình toán kinh tế”, 2006, Trường Đại học Kinh tế Quốc dân.

[3]

Võ Văn Tuấn Dũng, 2007, "Giáo trình Quy hoạch tuyến tính", NXB Thống kê.

[4]

Đặng Văn Thoan, 2003, "Hướng dẫn giải bài tập toán kinh tế", Trường Đại học Thương mại.

[5]

Hoàng Tụy, 1968, “Lý thuyết quy hoạch” - Tập I - Quy hoạch tuyến tính”, NXB Khoa học - Hà Nội.

[6]

Dantzig G. B., 1963, “Linear programming and Extensions”, Princeton University.

[7]

Frederick S. Hillier, Gerald J. Lieberman, 2010, “Introduction to operation research”, Stanford University.

- 109 -