Giáo trình Tin học trong quản lý xây dựng

áo hay một tập danh mục đầu tư sẽ bị giới hạn bởi tổng số tiền sẵn có để đầu tư. + Trong bài toán vận tải, việc cực tiểu hóa chi phí vận tải sẽ bị ràng buộc bởi khả năng cung cấp của các nhà máy cũng như nhu cầu tại các nơi tiêu thụ. Vì vậy, chúng ta thường muốn cực đại hóa hay cực tiểu hóa các đại lượng (hàm mục tiêu) trong điều kiện giới hạn về tài nguyên (các điều kiện ràng buộc). 2.3. Phải có các phương án để lựa chọn (There must be alternatives available). Có một công ty sản xuất 3 loại sản phẩm khác nhau. Có thể công ty tập trung sản xuất chủ yếu một trong 3 sản phẩm hay sản xuất đều 3 loại sản phẩm, hoặc phân bổ ở một tỷ lệ bất kỳ nào đó? Nhà quản lý Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 243 có thể sử dụng QHTT để xác định tỷ lệ phân bổ của chúng trong điều kiện giới hạn về tài nguyên sản xuất (máy móc, công nhân,…) để cực đại lợi nhuận. Nếu chỉ có một phương án, chúng ta không cần QHTT. 2.4. Hàm mục tiêu và các ràng buộc đều là hàm tuyến tính. Dạng ràng buộc có thể là: + Bất phương trình có dạng “£” hoặc “³”; + Phương trình “=”. Hàm tuyến tính có nghĩa là số mũ của các biến quyết định phải ở dạng bậc nhất (không được là bậc 2, bậc 3 hay các bậc khác 1). Ví dụ: + Phương trình 2a+ 5b = 10 là phương trình tuyến tính, trong khi đó 2a2 + 5b3 + 3ab = 10 không phải là phương trình tuyến tính bởi vì biến a có bậc là 2, biến b có bậc là 3 và tích a.b cũng không khả thi . + Hàm mục tiêu Z = 10x1 + 9x2 là hàm tuyến tính, trong khi đó 2 1 2Z 10x 9 x= + không phải là hàm tuyến tính. Chúng ta thường gặp các dạng ràng buộc bất phương trình khi giải các bài toán QHTT. Điều này có nghĩa là các ràng buộc không phải lúc nào cũng có dạng phương trình A + B = C. Các nhà khoa học quản lý đã nghiên cứu và tìm ra lời giải của rất nhiều các mô hình toán học bao gồm một hàm mục tiêu và một tập các ràng buộc. Các mô hình này được gọi là các mô hình quy hoạch toán học (mathematical programming models). Mô hình QHTT là một dạng đặc biệt của các mô hình quy hoạch toán học, trong đó hàm mục tiêu và các ràng buộc đều là hàm tuyến. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 244 3. CÁC GIẢ THIẾT CƠ BẢN CỦA QUY HOẠCH TUYẾN TÍNH Thông thường các mô hình toán ứng dụng trong kinh tế đều có các giả thiết đi kèm. Vậy tại sao phái sử dụng các giả thiết? Câu trả lời là vì rất khó để có mô hình toán học nào mô tả một cách hoàn toàn chính xác đến chi tiết trong các tình huống thực tế và nếu có thì mô hình đó sẽ rất phức tạp. Vì vậy, để mô hình được đơn giản hóa (nhưng vẫn phải đảm bảo không mất đi tính thực tế của bài toán), chúng ta cần có các giả thiết đi kèm. Có 5 giả thiết/yêu cầu cơ bản cần nắm khi giải các bài toán QHTT: 1. Tính chắc chắn (Certainty): Các con số trong hàm mục tiêu và các điều kiện ràng buộc được biết chắc chắn và không thay đổi trong suốt quá trình nghiên cứu. 2. Tính tỷ lệ (Proportionality): Chúng ta phải giả thiết có tính tỷ lệ tồn tại trong hàm mục tiêu và các ràng buộc. Nghĩa là sự đóng góp đối với hàm mục tiêu và giá trị tài nguyên trong mỗi ràng buộc phải tỷ lệ với giá trị của các biến quyết định. Ví dụ như nếu sản xuất một sản phẩm mất 3 giờ thì sản xuất 10 sản phẩm sẽ mất 30 giờ. 3. Tính cộng dồn (Additivity): Giá trị của hàm mục tiêu và tổng tài nguyên sử dụng được tính toán bằng cách lấy tổng hàm mục tiêu đóng góp và tài nguyên sử dụng của tất cả các biến quyết định. Nghĩa là tổng các hoạt động sẽ bằng kết quả cộng dồn của từng hoạt động riêng rẽ. Ví dụ: Nếu có mục tiêu là cực đại hóa lợi nhuận bằng 8 USD của sản phẩm 1 + 3 USD của sản phẩm 2 thì khi một sản phẩm được sản xuất, lợi nhuận tổng cộng sẽ là 8 + 3 = 11 USD. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 245 4. Tính chia được (Divisibility): Biến quyết định là biến liên tục. Giả thiết này chấp nhận các nghiệm số ở dạng thập phân (Lời giải không nhất thiết phải là số nguyên). Nghĩa là có thể chấp nhận giá trị như 1/3 cái bàn được sản xuất. 5. Tính không âm (Nonnegative): Tất cả các biến phải không âm. Sử dụng các con số âm để đếm là không thể. Bạn không thể sản xuất một số âm cái bàn, cái ghế, cái đèn, hay máy tính… được. Bảng 4.1 sau đây trình bày tóm tắt các đặc điểm và giả thiết cơ bàn của bài toán QHTT: Bảng 4.1. Các đặc điểm và giả thiết cơ bản của bài toán QHTT 4 đặc điểm của QHTT 5 giả thiết của bài toán QHTT 1. Hàm mục tiêu; 2. Các ràng buộc; 3. Các phương án lựa chọn; 4. Hàm mục tiêu và các ràng buộc là hàm tuyến tính. 1. Tính chắc chắn 2. Tính tỷ lệ 3. Tính cộng dồn 4. Tính chia được 5. Tính không âm 4. THÀNH LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Thành lập một bài toán QHTT liên quan đến việc xây dựng một mô hình toán (mathematical model) để diễn tả vấn đề quản lý. Vì vậy, để thành lập một bài toán QHTT, chúng ta cần phải hiểu một cách sâu sắc vấn đề quản lý đang phải đối mặt. Khi đã nắm rõ, chúng ta có thể bắt đầu xây dựng mô hình toán cho vấn đề. Việc thành lập một bài toán QHTT bao gồm các bước sau đây: 1. Hiểu rõ vấn đề quản lý đang phải đối mặt. 2. Xác định hàm mục tiêu và các ràng buộc. 3. Định nghĩa các biến ra quyết định. 4. Sử dụng các biến ra quyết định để viết các mô hình toán cho hàm mục tiêu và các ràng buộc. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 246 Một trong những ứng dụng phổ biến của QHTT là bài toán kế hoạch sản xuất nhiều sản phẩm (Product mix problem). Hai hay nhiều sản phẩm được sản xuất trong điều kiện giới hạn về tài nguyên như lao động, máy móc, nguyên vật liệu…Lợi nhuận mà công ty muốn cực đại được dựa trên lợi nhuận đóng góp của mỗi đơn vị sản phẩm. Công ty sẽ phải quyết định sản xuất bao nhiêu sản phẩm mỗi loại để cực đại hóa tổng lợi nhuận trong phạm vi cho phép về tài nguyên. Ví dụ về cách thành lập 1 bài toán QHTT: Công ty sản xuất nội thất Phương Nam Công ty Phương Nam sản xuất các loại bàn và ghế gỗ rẻ tiền. Quy trình sản xuất của mỗi sản phẩm đều có điểm chung là cùng trải qua công đoạn đóng mộc (carpentry work) và sơn, đánh bóng (painting and varnishing): - Mỗi cái bàn cần 4 giờ đóng mộc, 2 giờ sơn và đánh bóng. - Mỗi cái ghế cần 3 giờ đóng mộc, 1 giờ sơn và đánh bóng. Trong giai đoạn sản xuất hiện tại, chu kỳ 1 tuần, với lực lượng công nhân lao động hiện có, công ty Phương Nam có tổng cộng 240 giờ đóng mộc và 100 giờ sơn, đánh bóng (Số công nhân * Giờ công mỗi ngày). Mỗi cái bàn và ghế khi công ty đem bán sẽ đem lại lợi nhuận tương ứng là 70 USD và 50 USD. Vấn đề đặt ra cho công ty này là trong giới hạn về giờ đóng mộc và giờ sơn như trên, công ty cần sản xuất bao nhiêu cái bàn và bao nhiêu cái ghế là tối ưu dể đem lại lợi nhuận cao nhất. Giải: Thời gian thực hiện từng công đoạn, thời gian có sẵn và lợi nhuận đem lại cho từng sản phẩm (bàn và ghế) được tóm tắt trong bảng sau đây: Bảng 4.2. Dữ liệu của công ty Phương Nam Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 247 Thời gian (giờ) Số giờ cần thiết để sản xuất một cái Tổng thời gian có được trong 1 tuần Công đoạn Bàn Ghế 1. Đóng mộc 4 3 240 2. Sơn và đánh bóng 2 1 100 Lợi nhuận (USD) 70 50 Số lượng cần sản xuất x1 x2 Gọi: + x1 = Số lượng bàn sẽ sản xuất trong 1 tuần; + x2 = Số lượng ghế sẽ sản xuất trong 1 tuần. x1 và x2 được gọi là các biến quyết định (decision variables). 1. Hàm mục tiêu (Objective function): Maximize Lợi nhuận Z = 70 x1 + 50 x2 (USD) Giải thích: 1 cái bàn thu được 70 USD lợi nhuận nên x1 cái bàn sẽ thu được 70x1 USD lợi nhuận; tương tự, 1 cái ghế thu được 50 USD lợi nhuận nên x2 cái ghế sẽ thu được 50x2 USD lợi nhuận® Tổng lợi nhuận Z = 70x1 + 50x2 (USD) 2. Ràng buộc (Constraints): Tổng quát, tại mỗi công đoạn ta có: Tổng số tài nguyên (số giờ) sử dụng £ Tổng số tài nguyên (số giờ) sẵn có: + Giờ đóng mộc: 4x1 + 3x2 £ 240 (1) + Giờ sơn và đánh bóng: 2x1 + 1x2 £ 100 (2) Cả 2 điều kiện ràng buộc này thể hiện giới hạn của khả năng sản xuất của công ty, và tất nhiên, tác động đến tổng lợi nhuận. Ví dụ: + Công ty Phương Nam không thể sản xuất 70 cái bàn vì nếu như thế x1 = 70, khi đó cả 2 điều kiện ràng buộc đều không thỏa. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 248 + Tương tự, công ty cũng không thể sản xuất 50 cái bàn (x1 = 50) và 10 cái ghế (x2 =10) vì nếu thế thì ràng buộc thứ 2 sẽ không thỏa mãn. Chú ý: Chúng ta có thể nhận thấy một đặc điểm quan trọng của QHTT, đó là tồn tại mối quan hệ tương tác giữa các biến. Nếu công ty sản xuất nhiều sản phẩm này thì buộc phải sản xuất ít đi sản phẩm còn lại. Cụ thể hơn, khả năng của doanh nghiệp bị giới hạn. 3. Điều kiện biên (Ràng buộc mặc định): Để bài toán có ý nghĩa thì giá trị x1 và x2 phải là số không âm (ràng buộc không âm), nghĩa là: x1³ 0 (Số lượng bàn sản xuất trong 1 tuần ³ 0) x2 ³ 0 (Số lượng ghế sản xuất trong 1 tuần ³ 0) * Tóm lại, ta có mô hình toán của vấn đề lập kế hoạch sản xuất của công ty Phương Nam như sau: - Hàm mục tiêu: Max Lợi nhuận Z = 70 x1 + 50 x2 (USD) - Ràng buộc: 4x1 + 3x2 £ 240 (1) 2x1 + 1x2 £ 100 (2) x1³ 0, x2 ³ 0 Như vậy: Bài toán có 2 biến và 4 ràng buộc, trong đó có 2 ràng buộc mặc định là: x1³ 0, x2 ³ 0 5. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH CỰC ĐẠI HÓA BẰNG PHƯƠNG PHÁP ĐỒ THỊ Một trong những phương pháp để giải quyết các bài toán QHTT đơn giản là dùng phương pháp đồ thị. Phương pháp đồ thị chỉ sử dụng đối với bài toán QHTT đơn giản có 2 biến quyết định. Ví dụ: Chẳng hạn như số lượng bàn sẽ sản xuất x1 và số lượng ghế sẽ sản xuất x2 trong vấn đề lập kế hoạch sản xuất của công ty Phương Nam. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 249 Khi bài toán QHTT có nhiều hơn 2 biến, chúng ta không thể biểu diễn lời giải bằng đồ thị trong hệ tọa độ phẳng 2 chiều mà phải sử dụng các phương pháp giải khác (phương pháp đơn hình). Tuy nhiên, phương pháp đồ thị sẽ giúp chúng ta hiểu rõ được bản chất của bài toán QHTT và trên cơ sở đó nghiên cứu các phương pháp giải khác. Các bước giải bài toán QHTT bằng phương pháp đồ thị: + Bước 1: Biểu diễn các ràng buộc lên đồ thị + Bước 2: Tìm nghiệm tối ưu, áp dụng 1 trong 2 phương pháp sau: § Phương pháp đường đẳng trị § Phương pháp các điểm gốc. 5.1. Bước 1: Biểu diễn các ràng buộc lên đồ thị Để tìm lời giải tối ưu cho một bài toán QHTT, trước tiên chúng ta phải xác định miền nghiệm khả thi (Feasible Solution Region), còn gọi là miền thỏa mãn các điều kiện ràng buộc (miền ràng buộc). Để thực hiện điều này, bước đầu tiên ta biểu diễn từng điều kiện ràng buộc lên đồ thị. Trong ví dụ này, biến x1 (số lượng bàn sản xuất trong 1 tuần) được thể hiện trên trục hoành của đồ thị và biến x2 (số lượng ghế sản xuất trong 1 tuần) được thể hiện trên trục tung của đồ thị (tuy nhiên không nhất thiết lúc nào cũng như vậy, ta vẫn có thể biễu diễn ngược lại, nghĩa là biến x1 nằm trên trục tung và biến x2 nằm trên trục hoành). Để bài toán có ý nghĩa thì giá trị x1 và x2 phải là số không âm, nghĩa là: x1³ 0 (Số lượng bàn sản xuất sản xuất trong 1 tuần ³ 0) x2 ³ 0 (Số lượng ghế sản xuất sản xuất trong 1 tuần ³ 0) Khi đó, chúng ta chỉ làm việc trong góc phần tư thứ I của đồ thị (xem hình 4.1) Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 250 Hình 4.1. Góc phần tư I chỉ gồm các giá trị không âm 1. Ràng buộc thứ nhất: 4x1 + 3x2 £ 240 (1) * Cách biểu diễn: - Chuyển ràng buộc bất phương trình thành dạng phương trình: 4x1 + 3x2 = 240 (1’) - Tìm 2 điểm A và B thỏa mãn phương trình (1’) và vẽ đường thẳng nối 2 điểm đó: + Cho x1 = 0 ® 4*(0) + 3*x2 = 240® x2 = 80® A (x1 = 0, x2 = 80) + Cho x2 = 0 ® 4* x1 + 3*(0) = 240® x1 = 60® B (x1 = 60, x2 = 0) - Xác định miền nghiệm của ràng buộc thứ nhất: Vùng phía dưới AB, phần tô đậm của hình 4.2. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 251 Hình 4.2. Biểu diễn đồ thị cho ràng buộc thứ nhất (Giới hạn về Giờ đóng mộc) 2. Ràng buộc thứ hai: 2x1 + 1x2 £ 100 (2) * Cách biểu diễn: - Chuyển ràng buộc bất phương trình thành dạng phương trình: 2x1 + 1x2 = 100 (2’) - Tìm 2 điểm C và D thỏa mãn phương trình (2’) và vẽ đường thẳng nối 2 điểm đó: + Cho x1 = 0 ® 2*(0) + 1*x2 = 100® x2 = 100® C (x1 = 0, x2 = 100) + Cho x2 = 0 ® 2* x1 + 1*(0) = 100® x1 = 50® D (x1 = 50, x2 = 0) - Xác định miền nghiệm của ràng buộc thứ hai: Vùng phía dưới CD, phần tô đậm của hình 4.3. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 252 Hình 4.3: Biểu diễn đồ thị cho ràng buộc 2 (Giới hạn về Giờ sơn và đánh bóng) 3. Xác định miền nghiệm khả thi thỏa mãn cả 2 ràng buộc: Phần tô đậm Chúng ta biết rằng để sản xuất ra bàn hoặc ghế thì đều phải trải qua 2 công đoạn đóng mộc và sơn, đánh bóng. Với bài toán QHTT, chúng ta cần phải tìm tập hợp các điểm lời giải đồng thời thỏa mãn tất cả các ràng buộc cùng một lúc (simultaneously). Vì vậy. 2 đường giới hạn phải vẽ trên cùng một đồ thị (xem hình 4.4). Vùng tô đậm thể hiện các sự kết hợp của lượng bàn và ghế sản xuất đồng thời thỏa mãn cả 2 điều kiện ràng buộc về thời gian đóng mộc và sơn, đánh bóng. Ta gọi đó là miền nghiệm khả thi (Feasible Solution Region), gọi tắt là miền khả thi. Miền khả thi của một bài toán QHTT là tập hợp các điểm thỏa mãn tất cả các điều kiện ràng buộc của bài toán, vì vậy nó cũng chính là phần trùng lắp (che phủ/chồng lên nhau) của tất cả các điều kiện ràng buộc. + Bất cứ điểm nào nằm bên trong miền khả thi sẽ cho ta một nghiệm khả thi (feasible solution). Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 253 + Bất cứ điểm nào nằm ngoài miền khả thi sẽ cho ta một nghiệm không khả thi (infeasible solution). Hình 4.4. Miền nghiệm khả thi cho vấn đề của công ty Phương Nam - Ta xét 3 điểm sau đây để minh họa. + Điểm M (x1 = 30, x2 = 20), nghĩa là sản xuất 30 cái bàn và 20 cái ghế trong 1 tuần. Ta có: § Thời gian đóng mộc là: 4*30 + 3*20 = 180 giờ < 240 giờ nên thỏa mãn điều kiện ràng buộc thứ nhất: 4x1 + 3x2 £ 240. § Thời gian sơn và đánh bóng là: 2*30 + 1*20 = 80 giờ < 100 giờ nên thỏa mãn điều kiện ràng buộc thứ hai: 2x1 + 1x2 £ 100. + Điểm N (x1 = 70, x2 = 40), nghĩa là sản xuất 70 cái bàn và 40 cái ghế trong 1 tuần.. Ta có: Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 254 § Thời gian đóng mộc là: 4*70 + 3*40 = 400 giờ > 240 giờ nên không thỏa mãn điều kiện ràng buộc thứ nhất: 4x1 + 3x2 £ 240. § Thời gian sơn và đánh bóng là: 2*70 + 1*40 = 180 giờ > 100 giờ nên không thỏa mãn điều kiện ràng buộc thứ hai: 2x1 + 1x2 £ 100. + Điểm P (x1 = 50, x2 = 5), nghĩa là sản xuất 50 cái bàn và 5 cái ghế trong 1 tuần.. Ta có: § Thời gian đóng mộc là: 4*50 + 3*5 = 215 giờ < 240 giờ nên thỏa mãn điều kiện ràng buộc thứ nhất: 4x1 + 3x2 £ 240. § Thời gian sơn và đánh bóng là: 2*50 + 1*5 = 105 giờ > 100 giờ nên không thỏa mãn điều kiện ràng buộc thứ hai: 2x1 + 1x2 £ 100. Chú ý: Điểm nào đó chỉ cần không thỏa mãn một trong các điều kiện ràng buộc thì điểm ấy cũng nằm ngoài miền khả thi . Chẳng hạn như điểm P(x1 = 50, x2 = 5) nằm trong giới hạn về thời gian đóng mộc nhưng lại vượt quá về thời gian sơn, đánh bóng cho phép nên điểm P cũng không nằm trong miền khả thi . 5.2. Bước 2: Tìm nghiệm tối ưu 5.2.1. Cách 1: Phương pháp đường đẳng trị Sau khi đã vẽ miền khả thi, chúng ta sẽ tiến hành tìm nghiệm tối ưu của bài toán. Nghiệm tối ưu là điểm nằm trong miền khả thi cho chúng ta giá trị hàm mục tiêu tốt nhất (lợi nhuận cao nhất). Nhưng có rất nhiều điểm trong miền khả thi, vậy chúng ta phải làm như thế nào để tìm ra điểm tốt nhất, điểm cho ta lợi nhuận cao nhất? Bởi vì có vô số điểm nằm trong miền khả thi của bài toán, nên chúng ta không thể dùng phương pháp thử và sai (trial-and-error) để đánh giá hàm mục tiêu của tất cả các nghiệm khả thi để xác định nghiệm tối ưu. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 255 Có rất nhiều cách khác nhau để tìm được nghiệm tối ưu sau khi miền khả thi đã được vẽ trên đồ thị. Trong đó, một trong những cách nhanh nhất để tìm nghiệm tối ưu là ứng dụng phương pháp đường đẳng trị (đường đẳng lợi nhuận-isoprofit line method). Chúng ta bắt đầu phương pháp bằng cách cho lợi nhuận bằng 1 số bất kỳ nào đó (một số tiền lợi nhuận nhỏ), nghĩa là ta gán một trị bất kỳ cho vế phải của phương trình lợi nhuận: giả sử là 2100 USD. Đây là mức lợi nhuận có thể dễ dàng đạt được mà vẫn thỏa mãn các điều kiện ràng buộc. Khi đó ta có hàm mục tiêu: 2.100 = 70x1 + 50x2. Phương trình đường thẳng này được gọi là đường đẳng lợi nhuận (isoprofit line), vì nó thể hiện tất cả các sự kết hợp của (x1, x2) cho ra lợi nhuận tổng cộng là 2.100 USD. Để vẽ đường đẳng lợi nhuận 2100 = 70x1 + 50x2, ta tìm 2 điểm thỏa mãn phương trình và vẽ đường thẳng nối 2 điểm đó (giống như đã thực hiện cho các ràng buộc ở bước 1). Tìm x1 và x2: + Cho x1 = 0® 2100 = 70*(0) + 50*x2 ® x2 = 42; và + Cho x2 = 0® 210= 70*x1 + 50*(0) ® x1 = 30 Sau đó, chúng ta nối 2 điểm này bằng một đường thẳng. Tất cả mọi điểm nằm trên đường này có lợi nhuận là 2.100 USD. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 256 Hình 4.5. Đường đẳng lợi nhuận ở mức 2.100 USD Dễ dàng nhận thấy đường đẳng lợi nhuận ở mức 2.100 USD không phải là đường cho ra lợi nhuận cao nhất của công ty. Ở hình 4.6, ta cố gắng vẽ thêm 3 đường đẳng lợi nhuận ở mức cao hơn. Trước tiên ta vẽ đường đồng lợi nhuận ở mức 2.800 USD có phương trình: 2.800 = 70x1 + 50x2 bằng cách: + Cho x1 = 0® 2800 = 70*(0) + 50*x2 ® x2 = 56; và + Cho x2 = 0® 2800= 70*x1 + 50*(0) ® x1 = 40 Như vậy, tất cả các sự kết hợp của (x1, x2) nằm trên đường đẳng lợi nhuận 2800 = 70x1 + 50x2 đều cho ra lợi nhuận tổng cộng là 2.800 USD. Bây giờ, chúng ta tiếp tục vẽ đường đẳng lợi nhuận thứ ba ở mức 3.500 USD. Chúng ta nhận thấy rằng càng xa gốc tọa độ thì thu được lợi nhuận càng cao. Một đặc điểm quan trọng nữa là các đường đẳng lợi nhuận đều song song (parallel) với nhau. Điều này giúp chúng ta có thể tìm được nghiệm tối ưu cho bài toán. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 257 Giải thích: Ta có: Z = 70x1 + 50x2 Þ x2 = 1 7 1x Z 5 50 - + = -1,4x1 + 0,02Z (3) Phương trình (3) này thể hiện độ dốc (hệ số góc) của hàm mục tiêu thông qua x1 và x2. Trong đó, hệ số của biến x1 = -1,4 là độ dốc (slope) của đường thẳng hàm mục tiêu; còn hệ số của biến x2 là 0,02 là giá trị chắn (intercept) của x2, tức là giá trị của biến x2 khi đường thẳng hàm mục tiêu ứng có phương trình (3) đi qua trục x2. Thay thế các giá trị lợi nhuận Z tương ứng là 2100, 2800, 3500 USD, ta được: + Khi Z = 2100 USD: x2 = -1,4x1 + 42Z (3a) + Khi Z = 2800 USD: x2 = -1,4x1 + 56Z (3b) + Khi Z = 3500 USD: x2 = -1,4x1 + 70Z (3c) Các đường đẳng lợi nhuận ở trên đều có cùng độ dốc là -1,4 nên chúng song song với nhau. Và đường thẳng nào cho chúng ta giá trị chắn của x2 càng lớn thu được lợi nhuận càng cao, nghĩa là các đường xa dần gốc tọa độ. Chúng ta vẽ một chuỗi các đường thẳng song song bằng cách di chuyển cẩn thận cây thước vẽ song song với phương của đường đẳng lợi nhuận ban đầu và dần xa gốc tọa độ. Đường lợi nhuận cao nhất là đường cách xa gốc tọa độ nhất và vẫn có điểm chung với miền khả thi (đến khi tiếp xúc với các điểm biên, ta có lời giải tốt nhất). Chúng ta nhận thấy đường đẳng lợi nhuận 4.200 USD thì quá cao (không có điểm chung với miền khả thi) nên không xét. Đường đẳng lợi nhuận cao nhất được trình bày trong hình 4.7. Đường này tiếp xúc với điểm góc của miền nghiệm tại điểm I(x1 = 30, x2= 40) và đạt lợi nhuận cao nhất là Z = 70*30 + 50*40 = 4.100 USD. Trong đó điểm I (x1 = 30, x2= 40) chính là giao điểm của 2 đường ràng buộc nên tọa độ cảu nó chính là nghiệm của hệ phương trình: 1 2 1 2 4x 3x 240 2x 1x 100 + =ì í + =î . Như vậy, mỗi Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 258 tuần công ty Phương Nam nên sản xuất 30 cái bàn và 40 cái ghế thì sẽ đạt cực đại lợi nhuận Z = 4.100 USD. Hình 4.6. Bốn đường đẳng lợi nhuận Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 259 Hình 4.7. Nghiệm tối ưu của công ty Phương Nam 5.2.2. Cách 2: Phương pháp điểm góc (Corner Point Method) Phương pháp thứ hai được sử dụng để giải quyết các bài toán QHTT là phương pháp điểm góc (Corner/Extreme Point Method). Phương pháp này về mặt khái niệm đơn giản hơn phương pháp đường đẳng trị, nhưng nó yêu cầu phải xác định được lợi nhuận tại mọi điểm góc của miền khả thi. Lý thuyết toán học về QHTT đã chứng minh được rằng điểm tối ưu chỉ đạt được trên các điểm cực biên (các điểm góc) của miền khả thi. Chú ý: Đối với 2 trường hợp đặc biệt của bài toán QHTT là không khả thi (infeasibility) và không bị chặn (Unboundedness) thì phát biểu trên không áp dụng được. Do đó, chúng ta chỉ cần thể xác định tọa độ các điểm góc và kiểm tra xem điểm nào đạt giá trị tối ưu về lợi nhuận bằng cách tính toán và so sánh các giá trị hàm mục tiêu tại từng điểm góc. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 260 Hình 4.8. Phương pháp điểm góc Quan sát miền khả thi của bài toán, chúng ta thấy miền khả thi là 1 đa giác lồi có 4 góc (4 đỉnh) OAID. Ta tìm tọa độ từng điểm góc và tính mức lợi nhuận tại các điểm đó như sau: + Điểm O (0,0): Z = 70*0 + 50*0 = 0 USD + Điểm D(50,0): Z = 70*50 + 50*0 = 3500 USD + Điểm A(0,80): Z = 70*0 + 50*80 = 4000 USD + Điểm I(30,40): Z = 7*30 + 5*40 = 4100 USD (Max) Trong đó, để tìm tọa độ của điểm I, chúng ta cần giải hệ phương trình sau: 1 2 1 2 4x 3x 240 2x 1x 100 + =ì í + =î Như vậy, điểm tối ưu là I (x1 = 30 bàn, x2 = 40 ghế) vì nó cho công ty mức lợi nhuận cao nhất Z = 4.100 USD. Kết quả này hoàn Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 261 toàn giống như khi chúng ta dùng phương pháp đường đẳng lợi nhuận ở trên. Tóm lại, để giải bài toán QHTT đơn giản chỉ có 2 biến theo phương pháp đồ thị, chúng ta có thể dùng phương pháp đường đẳng trị hoặc phương pháp điểm góc. Các bước thực hiện hai phương pháp này được tóm tắt trong bảng 4.3 sau đây: Bảng 4.3. Tóm tắt cách giải bài toán QHTT bằng phương pháp đồ thị Phương pháp đồ thị (giải bài toán QHTT có 2 biến) Phương pháp đường đẳng trị Phương pháp điểm góc 1. Biểu diễn các ràng buộc lên đồ thị và tìm miền nghiệm khả thi. 2. Vẽ một đường đẳng lợi nhuận (hoặc đường đẳng chi phí). 3. Di chuyển cây thước vẽ song song với phương của đư