Vận Trù Học

By Phong Nguyễn Như

Vận trù học là khoa học bắt đầu từ thế chiến II, ở nước Anh với ý nghĩa ban đầu là nghiên cứu cho các hoạt động quân sự (To do "Research" on military "Operations": Operations Research). Hiện nay, ngoài lĩnh vực quốc phòng, Vận trù học là một khoa học phổ biến và ứng dụng trong nhiều lĩnh vực khác như công nghiệp, thương mãi, dịch vụ, công cộng, ... Vận trù học là khoa học quản lý, vận dụng các phương pháp của khoa học hiện đại trong các vấn đề ra quyết định trong các hệ thống quản lý lớn và phức tạp, bao gồm con người, máy móc, nguyên vật liệu, tiền bạc, với các ràng buộc nhất định, với mục tiêu giúp nhà quản lý ra quyết định tốt hơn, giải quyết vấn đề hiệu quả hơn.
Vận Trù Học được biên soạn với nội dung bao gồm 4 phần, 25 chương. PHẦN A - Vận Trù Xác Định bao gồm các chương Quy hoạch tuyến tính, Quy hoạch vận tải, Quy hoạch mạng, Quy hoạch mục tiêu, Quy hoạch nguyên, Quy hoạch động, Quy hoạch phi tuyến. PHẦN B - Vận Trù Ngẫu Nhiên bao gồm các chương Ra quyết định ngẫu nhiên, Lý thuyết trò chơi, Ra quyết định tái sinh, Ra quyết định Markov, Ra quyết định sắp hàng. PHẦN C - Vận Trù Mờ bao gồm các chương Lý thuyết tập mờ, Quan hệ mờ, Số học mờ, Lý thuyết khả năng. PHẦN D - Vận Trù Mềm bao gồm các chương Logic mờ, Mạng thần kinh, Giải thuật di truyền. PHẨN E - Ứng Dụng Vận Trù bao gồm các chương Dự báo nhu cầu, Ra quyết định, Phân tích kinh tế, Điều độ dự án, Kiểm soát chất lượng, Hoạch định tồn kho.

• Language: Tiếng việt
• Publisher: Phong Nguyễn Như
• Release date: Nov 1, 2020
• ISBN: 9781005596491

Phong Nguyễn Như

Nguyen Nhu Phong is a Senior Lecturer at the Industrial Systems Engineering Department, HCM City University of Technology (HCMUT), Vietnam. He is also an IEEE member, and a SAP ERP specialist.He received his Master of Engineering at Asian Institute of Technology (1997), and his Bachelor of Engineering at HCMUT, Vietnam (1987).He was a member of the Project of building ISE program (1999) and the leader of the Project of improving the program (2007-2012). He was the deputy dean of the Faculty of Mechanical Engineering in period of 2002-2007, and the former head of the ISE department in period of 2007-2012.He is the authors of 24 books in Statistics, Operations Research, Scientific Research Methodology, Design of Experiment, Engineering Economy, Production Management, Inventory Management, Quality Management, Lean Production, Lean Six Sigma, MRPII, ERP, Fuzzy Theories & Applications.He is also the authors of 49 papers including 38 conference papers, 7 international conference papers, 4 journal papers, and 120 web papers. His research topics include Soft Computing; Lean Six Sigma; Resource Planning MRPII - ERP.

Book preview

Nguyễn Như Phong

VẬN TRÙ HỌC

2020

NỘI DUNG

MỤC LỤC

LỜI NÓI ĐẦU

PHẦN A: VẬN TRÙ XÁC ĐỊNH

Chương 1: Quy hoạch tuyến tính

Chương 2: Quy hoạch vận tải

Chương 3: Quy hoạch mạng

Chương 4: Quy hoạch mục tiêu

Chương 5: Quy hoạch nguyên

Chương 6: Quy hoạch động

Chương 7: Quy hoạch phi tuyến

PHẦN B: VẬN TRÙ NGẪU NHIÊN

Chương 8: Ra quyết định ngẫu nhiên

Chương 9: Lý thuyết trò chơi

Chương 10: Ra quyết định tái sinh

Chương 11: Ra quyết định Markov

Chương 12: Ra quyết định sắp hàng

PHẦN C: VẬN TRÙ MỜ

Chương 13: Lý thuyết tập mờ

Chương 14: Quan hệ mờ

Chương 15: Số học mờ

Chương 16: Lý thuyết khả năng

PHẦN D: VẬN TRÙ MỀM

Chương 17: Logic mờ

Chương 18: Mạng thần kinh

Chương 19: Giải thuật di truyền

PHẨN E: ỨNG DỤNG VẬN TRÙ

Chương 20: Dự báo nhu cầu

Chương 21: Ra quyết định

Chương 22: Phân tích kinh tế

Chương 23: Điều độ dự án

Chương 24: Kiểm soát chất lượng

Chương 25: Hoạch định tồn kho

TÀI LIỆU THAM KHẢO

MỤC LỤC

NỘI DUNG

LỜI NÓI ĐẦU

PHẦN A: VẬN TRÙ XÁC ĐỊNH

1. Vận trù học

2. Mô hình vận trù

3. Giải mô hình vận trù

4 Mô hình hóa

5. Quy trình vận trù

6. Vận trù xác định

Chương 1: Quy hoạch tuyến tính

1. Mô hình quy họach tuyến tính

2. Phương pháp đồ thị

3. Giải thuật đơn hình

4. Phân tích độ nhạy

Chương 2: Quy hoạch vận tải

1. Mô hình vận tải

2. Cân bằng mô hình vận tải

3. Giải thuật vận tải

4. Mô hình giao việc

Chương 3: Quy hoạch mạng

1. Mô hình mạng

2. Mô hình cây cực tiểu

3. Mô hình đường đi ngắn nhất

4. Mô hình lưu lượng cực đại

5. Mô hình điều độ dự án

Chương 4: Quy hoạch mục tiêu

1. Quy hoạch mục tiêu

2. Mô hình hóa quy hoạch mục tiêu

3. Giải thuật quy hoạch mục tiêu

Chương 5: Quy hoạch nguyên

1. Quy hoạch nguyên

2. Mô hình quy hoạch nguyên

3. Giải thuật quy hoạch nguyên

4. Phương pháp rẻ nhánh và chận

Chương 6: Quy hoạch động

1. Quy hoạch động

2. Phương trình đệ quy

3. Mô hình quy hoạch động

Chương 7: Quy hoạch phi tuyến

1. Quy hoạch phi tuyến

2. Bài toán tối ưu không ràng buộc

3. Bài toán tối ưu có ràng buộc dạng phương trìnhEC

4. Bài toán tối ưu với ràng buộc bất phương trìnhEC

5. Giải thuật quy hoạch phi tuyếnEC

6. Ứng dụng quy hoạch phi tuyến

PHẦN B: VẬN TRÙ NGẪU NHIÊN

1. Dữ kiện vận trù

2. Thông tin vận trù

3. Lý thuyết bất định

4. Vận trù ngẫu nhiên

Chương 8: Ra quyết định ngẫu nhiên

1. Ra quyết định trong khi biết phân bố xác suất

2. Ra quyết định khi không biết phân bố xác suất

Chương 9: Lý thuyết trò chơi

1. Mô hình trò chơi

2. Chiến lược đơn

3. Chiến lược hỗn hợp

Chương 10: Ra quyết định tái sinh

1. Quá trình đếm

2. Quá trình Poisson

3. Quá trình tái sinh

4. Quá trình hồi phục

5. Ra quyết định tái sinh

Chương 11: Ra quyết định Markov

1. Chuỗi Markov rời rạc

2. Mô hình quyết định Markov

Chương 12: Ra quyết định sắp hàng

1. Chuỗi Markov liên tục

2. Quá trình sắp hàng

3. Mô hình quyết định sắp hàng

PHẦN C: VẬN TRÙ MỜ

1. Lý thuyết mờ

2. Vận trù mờ

Chương 13: Lý thuyết tập mờ

1. Lý thuyết tập hợp

2. Tập mờ

3. Toán tử tập mờ

4. Xây dựng tập mờ

5. Giải mờ

Chương 14: Quan hệ mờ

1. Quan hệ

2. Quan hệ mờ

3. Liên kết mờ

4. Hợp thành mờ

5. Nguyên lý mở rộng

6. Chuyển đổi mờ

Chương 15: Số học mờ

1. Số mờ

2. Biến ngôn ngữ

3. Toán tử số học mờ

4. Cực trị mờ

5. So sánh mờ

6. Xếp hạng mờ

Chương 16: Lý thuyết khả năng

1. Sự kiện

2. Lý thuyết độ đo mờ

3. Lý thuyết bằng chứng

4. Lý thuyết xác suất

5. Lý thuyết khả năng

6. Lý thuyết khả năng và lý thuyết tập mờ

7. Lý thuyết khả năng và lý thuyết xác suất

PHẦN D: VẬN TRÙ MỀM

1. Lý thuyết bất định

2. Tính toán mềm

3. Vận trù mềm

Chương 17: Logic mờ

1. Logic học

2. Mệnh đề mờ

3. Hàm kéo theo mờ

4. Mệnh đề điều kiện mờ

5. Suy diễn mờ

6. Lập luận xấp xỉ đa điều kiện

Chương 18: Mạng thần kinh

1. Mạng thần kinh thiên tạo

2. Mạng thần kinh nhân tạo

3. Huấn luyện mạng thần kinh

4. Xây dựng hàm thành viên dùng mạng thần kinh

5. Công nghệ Neurofuzzy

6. Mạng thần kinh mờ

Chương 19: Giải thuật di truyền

1. Giải thuật di truyền

2. Các bước của giải thuật di truyền

3. Tạo hàm thành viên bằng giải thuật di truyền

4. Giải thuật di truyền mờ

PHẨN E: ỨNG DỤNG VẬN TRÙ

1. Khoa học quản lý

2. Ứng dụng vận trù

Chương 20: Dự báo nhu cầu

1. Dự báo

2. Dự báo nhu cầu

3. Sai số dự báo

4. Phân tích chuỗi thời gian

5. Mô hình tương quan

6. Dự báo định tính

7. Dự báo mềm

Chương 21: Ra quyết định

1. Xếp hạng mềm

2. Đánh giá tổng hợp mềm

3. Ra quyết định mềm đơn

4. Ra quyết định mềm nhóm

5. Ra quyết định mềm đa tiêu chuẩn

6. Ra quyết định mềm theo mục tiêu

7. Ra quyết định mềm Bayes

Chương 22: Phân tích kinh tế

1. Dòng tiền tệ mềm

2. Phân tích tương đương dòng tiền tệ mờ

3. Phân tích khả thi dự án

4. So sánh dự án

5. Phân tích lãi suất nội tại mờ

Chương 23: Điều độ dự án

1. Quản lý dự án

2. Điều độ dự án

3. Điều độ dự án mềm

4. Bài toán thời gian hoàn thành dự án

5. Mô hình mạng

6. Mô hình CPM

7. Mô hình pCPM

8. Ra quyết định khả năng hoàn thành dự án

Chương 24: Kiểm soát chất lượng

1. Kiểm soát chất lượng

2. Kiểm soát chất lượng mềm

3. Kiểm đồ biến ngôn ngữ

4. Kiểm đồ Raz - Wang

5. Kiểm đồ Kanagawa - Tamaki - Ohta

6. Mô hình pLCC

Chương 25: Hoạch định tồn kho

1. Hoạch định vật tư tồn kho

2. Hoạch định vật tư tồn kho mềm

3. Ước lượng tham số mô hình

4. Hoạch định tồn kho nhu cầu độc lập

5. Hoạch định tồn kho nhu cầu phụ thuộc

TÀI LIỆU THAM KHẢO

LỜI NÓI ĐẦU

Vận trù học là khoa học bắt đầu từ thế chiến II, ở nước Anh với ý nghĩa ban đầu là nghiên cứu cho các hoạt động quân sự (To do Research on military Operations: Operations Research). Hiện nay, ngoài lĩnh vực quốc phòng, Vận trù học là một khoa học phổ biến và ứng dụng trong nhiều lĩnh vực khác như công nghiệp, thương mãi, dịch vụ, công cộng...

Vận trù học là khoa học quản lý, vận dụng các phương pháp của khoa học hiện đại trong các vấn đề ra quyết định trong các hệ thống quản lý lớn và phức tạp, bao gồm con người, máy móc, nguyên vật liệu, tiền bạc, với các ràng buộc nhất định, với mục tiêu giúp nhà quản lý ra quyết định tốt hơn, giải quyết vấn đề hiệu quả hơn.

VẬN TRÙ HỌC được biên soạn với nội dung bao gồm 4 phần, 25 chương.

PHẦN A - VẬN TRÙ XÁC ĐỊNH bao gồm các chương Quy hoạch tuyến tính, Quy hoạch vận tải, Quy hoạch mạng, Quy hoạch mục tiêu, Quy hoạch nguyên, Quy hoạch động, Quy hoạch phi tuyến.

PHẦN B - VẬN TRÙ NGẪU NHIÊN bao gồm các chương Ra quyết định ngẫu nhiên, Lý thuyết trò chơi, Ra quyết định tái sinh, Ra quyết định Markov, Ra quyết định sắp hàng.

PHẦN C - VẬN TRÙ MỜ bao gồm các chương Lý thuyết tập mờ, Quan hệ mờ, Số học mờ, Lý thuyết khả năng.

PHẦN D - VẬN TRÙ MỀM bao gồm các chương Logic mờ, Mạng thần kinh, Giải thuật di truyền.

PHẨN E - ỨNG DỤNG VẬN TRÙ bao gồm các chương Dự báo nhu cầu, Ra quyết định, Phân tích kinh tế, Điều độ dự án, Kiểm soát chất lượng, Hoạch định tồn kho.

Dù đã bỏ ra nhiều thời gian và công sức nhưng lần đầu tiên xuất bản nên chắc chắn không tránh khỏi nhiều sai sót, tác giả rất mong nhận được nhiều ý kiến đóng góp của các đồng nghiệp và quý độc giả để sách được hoàn thiện hơn trong lần tái bản. Mọi ý kiến đóng góp xin gởi về:

Nguyễn Như Phong.

Trường Đại Học Bách Khoa - Đại Học Quốc Gia TPHCM.

Tel: [phone].

Email: [e-mail], [e-mail]

Xin thành thật biết ơn.

Phần A

VẬN TRÙ XÁC ĐỊNH

Vận trù học

Mô hình vận trù

Giải mô hình vận trù

Mô hình hóa

Quy trình vận trù

Vận trù xác định

1. Vận trù học

Vận trù học, một công cụ quan trọng trong kỹ thuật hệ thống Công nghiệp, là khoa học bắt đầu từ thế chiến II, ở nước Anh với ý nghĩa ban đầu là nghiên cứu cho các hoạt động quân sự (To do Research on military Operations: Operations Research). Hiện nay, ngoài lĩnh vực quốc phòng, vận trù học là một khoa học phổ biến và ứng dụng trong nhiều lĩnh vực khác như công nghiệp, thương mại, dịch vụ, công cộng... Trong quản lý sản xuất, Vận trù học ứng dụng trong các lĩnh vực như quản lý tồn kho, hoạch định và điều độ sản xuất, quản lý chất lượng, quản lý dự án, quản lý bảo trì…

Vận trù học là khoa học quản lý, vận dụng các phương pháp của khoa học hiện đại trong các vấn đề ra quyết định trong các hệ thống quản lý lớn và phức tạp, bao gồm con người, máy móc, nguyên vật liệu, tiền bạc, với các ràng buộc nhất định, với mục tiêu giúp nhà quản lý ra quyết định tốt hơn, giải quyết vấn đề hiệu quả hơn. Dựa vào tính bất định của dữ hiện hệ thống, Vận trù học bao gồm:

Vận trù xác định

Vận trù bất định.

Vận trù xác định ứng dụng với dữ kiện xác định, Vận trù bất định ứng dụng với dữ kiện bất định. Vận trù xác định được trình bày ở phần này.

2. Mô hình vận trù

Nghiên cứu vận trù đầu tiên là ở nước Anh thời Đệ nhị thế chiến, khi ấy các nhà khoa học người Anh, dựa trên cơ sở khoa học, ra quyết định về việc sử dụng vật tư nguyên liệu sao cho tốt nhất. Sau chiến tranh, các ý tưởng vận trù khoa học đã áp dụng trong lĩnh vực quân sự được áp dụng trong việc nâng cao hiệu quả và năng suất của các hệ thống sản xuất trong lĩnh vực dân dụng.

Vận trù học dựa vào các mô hình toán học để giải các bài toán thực tế qua việc tìm lời giải tối ưu trong các lời giải khả thi bằng các tính toán lặp lại. Việc xác định chính xác vấn đề là rất quan trọng trong nghiên cứu vận trù, tuy nghiên cứu vận trù dựa vào toán học nhưng ảnh hưởng của các yếu tố định tính cũng rất quan trọng và cần được cân nhắc trước khi ra quyết định cuối cùng. Mô hình vận trù bao gồm ba thành phần cơ bản:

Phương án

Mục tiêu

Ràng buộc

Số phương án quyết định phụ thuộc vào bài toán, có thể là hữu hạn mà cũng có thể là vô hạn. Mục tiêu là tiêu chuẩn để đánh giá tính tối ưu phương án. Ràng buộc là tiêu chuẩn để đánh giá tính khả thi của phương án. Dạng thức tổng quát của mô hình vận trù là:

Cực đại / Cực tiểu - Hàm mục tiêu

Thỏa mãn - Ràng buộc

Hay theo ngôn ngữ mô hình toán học:

Max / Min - Hàm mục tiêu

St. - Ràng buộc

Lời giải mô hình là khả thi khi nó thỏa tất cả các ràng buộc. Trong các lời giải khả thi sẽ có lời giải tối ưu khi nó tạo ra giá trị tốt nhất thỏa hàm mục tiêu. Mô hình vận trù được sử dụng để tối ưu hóa một hàm mục tiêu, đồng thời thỏa các ràng bụôc. Tuy nhiên chất lượng lời giải phụ thuộc vào việc mô hình hóa. Với các mô hình có số phương án hữu hạn, lời giải tìm được là lời giải tốt nhất trong các phương án đề ra, không hẳn là lời giải tối ưu.

3. Giải mô hình vận trù

Không có kỹ thuật nào giải được mọi mô hình toán trong vận trù. Tùy thuộc lọai và mức độ phức tạp của mô hình toán mà có những kỹ thuật giải khác nhau, từ đơn giản như xếp hạng các phương án theo một tiêu chuẩn nào đó đến phức tạp hơn như sử dụng các phép tính vi phân trong tối ưu kinh điển. Một kỹ thuật giải mô hình vận trù nổi bật là quy hoạch tuyến tính các kỹ thuật khác như quy hoạch mục tiêu, quy hoạch nguyên, quy hoạch động, quy hoạch phi tuyến...

Một đặc điểm của các kỹ thuật giải mô hình vận trù là lời giải thường không từ các công thức toán học mà từ các giải thuật. Giải thuật là tập các quy tắc tính toán được áp dụng lập đi lập lại cho bài toán, với mỗi bước lặp, kết quả sẽ tiến gần đến lời giải tối ưu. Một số mô hình toán quá phức tạp đến nỗi không thể tìm được lời giải tối ưu từ những giải thuật sẵn có. Trong trường hợp này, ta thường không tìm lời giải tối ưu, mà tìm lời giải tốt và chấp nhận được từ các giải thuật trực quan, kinh nghiệm.

4. Mô hình hóa

Mô hình là một biểu diễn của thế giới thực nhằm giúp tìm ra lời giải giải quyết vấn đề của thế giới thực. Thế giới thực thường là rất phức tạp, mô hình vận trù không thể biểu diễn chính xác tuyệt đối thế giới thực. Mô hình thường chỉ biểu diễn gần đúng thế giới thực, qua việc đơn giản hóa thế giới thực, chỉ giữ lại các yếu tố quan trọng khi xây dựng mô hình. Hãy xem bài toán vận trù trong sản xuất. Khi khách hàng đặt hàng và đơn hàng đến bộ phận sản xuất, nguyên vật liệu được lấy từ kho hay mua từ nhà cung cấp. Khi lô hàng đã được sản xuất xong, bộ phận bán hàng sẽ phân phối sản phẩm đến khách hàng. Vấn đề là sản xuất với cỡ lô là bao nhiêu và mô hình nào sẽ được sử dụng.

Có rất nhiều biến trong hệ thống ảnh hưởng đến việc sản xuất bao nhiêu. Các biến ở bộ phận sản xuất bao gồm hay liên quan đến năng lực sản xuất của phân xưởng, tồn kho bán phẩm trên chuyền, chuẩn chất lượng. Các biến ở bộ phận vật tư bao gồm hay liên quan đến nguyên vật liệu sẵn có trong kho, nguyên vật liệu đã đặt từ nhà cung cấp, giới hạn lưu trữ thành phẩm trong kho. Các biến ở bộ phận bán hàng bao gồm hay liên quan đến nhu cầu dự báo, năng lực phân phối, hiệu quả quảng cáo, đối thủ cạnh tranh. Việc thiết lập quan hệ toán tường minh giữa biến ra là cỡ lô sản xuất và mọi biến vào có ảnh hưởng nêu trên là rất khó khăn.

Việc đơn giản hóa hệ thống bằng cách đưa về hai biến cơ bản là tốc độ sản xuất và tốc độ nhu cầu. Tốc độ sản xuất định bởi các biến năng lực sản xuất, chuẩn chất lượng và nguyên liệu sẵn có. Tốc độ nhu cầu định bởi nhu cầu dự báo, năng lực phân phối, hiệu quả quảng cáo, đối thủ cạnh tranh. Việc đơn giản hóa còn được thực hiện bởi loại bỏ các biến không quan trọng hay kết hợp các biến thành một biến để giảm thiểu số biến vào.

Từ hệ thống sản xuất đã được đơn giản hóa, mô hình sẽ được xây dựng đơn giản hơn. Với tốc độ sản xuất và tiêu thụ, ta dễ dàng đo lường tồn kho thành phẩm khi cung vượt cầu hay sản xuất thặng dư và ngược lại cầu vượt cung khi sản xuất thiếu hàng. Mô hình được xây dựng để cân bằng chi phí khi sản xuất quá mức và khi sản xuất thiếu. Một mô hình hay sử dụng để xác định cỡ lô là cực tiểu chi phí tồn kho qua việc cân bằng chi phí tồn trữ và chi phí hết hàng.

Nghiên cứu vận trù dựa trên các mô hình toán học, tuy nhiên trước khi sử dụng các mô hình phức tạp cần cân nhắc các yếu tố phi toán học như tâm lý, văn hóa... đồng thời cần cân nhắc phương pháp đơn giản trước. Trong một số trường hợp, vấn đề có thể giải quyết một cách đơn giản và không tốn kém, với sự hỗ trợ của các chuyên gia trong các lĩnh vực khác, không phải là các nhà toán học, chẳng hạn như các nhà tâm lý học và với các quan sát thực tế, các giải pháp đơn giản có thể sử dụng để giải quyết vấn đề mà không cần phải sử dụng các mô hình toán phức tạp.

Một số trường hợp, ‎yếu tố văn hóa là rất quan trọng. Ứng dụng giải pháp cho vấn đề là con người nên cần cân nhắc yếu tố con người với tập quán, thói quen, niềm tin thì mới có thể áp dụng thành công. Nhóm nghiên cứu vận trù cần am hiểu văn hóa của những người có liên quan đến vấn đề cần giải quyết. Nghiên cứu vận trù không nên có định kiến khi chọn lựa mô hình. Vấn đề là mô hình nào là phù hợp nhất để giải quyết vấn đề, chứ không phải là mô hình phức tạp sẽ giải quyết vấn đề tốt hơn mô hình đơn giản. Nghiên cứu vận trù nên bắt đầu bằng việc phân tích các dữ kiện sẵn có với các công cụ đơn giản để xác định nguyên nhân gốc rễ của vấn đề. Khi vấn đề đã được xác định, công cụ phù hợp nhất sẽ được sử dụng để tìm ra giải pháp.

5. Quy trình vận trù

Nhóm nghiên cứu vận trù gồm các nhà phân tích vận trù và khách hàng. Nhà phân tích vận trù sẽ có trách nhiệm mô hình hóa hệ thống, còn khách hàng sẽ hỗ trợ nhà phân tích vận trù qua kinh nghiệm về hệ thống của mình. Vận trù học mang cả tính khoa học và nghệ thuật. Tính khoa học thể hiện ở các kỹ thuật toán học sử dụng. Tính nghệ thuật thể hiện ở chỗ sự thành công của các bước vận trù dẫn đến lời giải của mô hình toán phụ thuộc phần lớn vào tính sáng tạo và kinh nghiệm của nhóm vận trù. Theo Willemain (1994) vận trù hiệu quả đòi hỏi không chỉ năng lực phân tích mà còn đòi hỏi năng lực phán đoán các công cụ kỹ thuật, nghĩa là khi nào sẽ sử dụng công cụ và sử dụng như thế nào cũng như các kỹ năng giao tiếp, truyền thông, tổ chức...

Các bước trong nghiên cứu vận trù bao gồm:

Xác định vấn đề

Xây dựng mô hình

Giải mô hình

Kiểm chứng mô hình

Vận dụng kết quả

Xác dịnh vấn đề là xác định phạm vi nghiên cứu của vấn đề, được thực hiện bởi nhóm vận trù. Xác định vấn đề bao gồm

Xác định mục tiêu nghiên cứu,

Xây dựng các phương án,

Xác định các giới hạn, ràng buộc và các yêu cầu của hệ thống.

Xây dựng mô hình hay mô hình hóa, chọn mô hình phù hợp nhất cho vấn đề nghiên cứu. Việc chọn mô hình phải dựa vào bản chất hệ thống. Mô hình hóa diễn dịch vấn đề thành các quan hệ toán học. Nếu các quan hệ toán học này đơn giản và phù hợp với một mô hình toán chuẩn thì lời giải sẽ tìm được qua các giải thuật có sẳn. Ngược lại, nếu quan hệ toán học là quá phức tạp, có thể đơn giản hóa mô hình và sử dụng các giải pháp trực quan kinh nghiệm để xác định lời giải hay sử dụng kỹ thuật mô phỏng. Ở vài trường hợp cần dùng phối hợp giữa mô hình toán tiêu chuẩn, mô hình mô phỏng và mô hình trực quan.

Giải mô hình là bước đơn giản nhất trong các bước nghiên cứu vận trù vì thường chỉ dựa vào các giải thuật có sẵn. Với các mô hình toán tiêu chuẩn, các giải thuật được sử dụng để tìm nghiệm tối ưu. Với mô hình mô phỏng hay mô hình trực quan không thể xác định lời giải tối ưu, chỉ dùng để đánh giá giải pháp và tìm lời giải tốt hơn hay chấp nhận được.

Ngoài việc tìm lời giải, còn cần phân tích độ nhạy của lời giải theo sự thay đổi của các tham số hệ thống. Phân tích độ nhạy là rất quan trọng khi không thể ước lượng chính xác các tham số đầu vào của mô hình. Khi ấy cần phân tích để tìm hiểu thay đổi của lời giải khi tham số đầu vào thay đổi trong vùng lân cận giá trị ước lượng. Phân tích độ nhạy còn giúp xác định tham số đầu vào quan trọng để chọn kỹ thuật ước lượng tốt hơn.

Kiểm chứng mô hình là kiểm tra xem mô hình có giá trị khi thực hiện đúng các chức năng, dự báo hợp lý đặc tính hệ thống, cho kết quả có nghĩa và chấp nhận được. Để kiểm chứng mô hình ta thường so sánh kết quả của mô hình với kết quả quá khứ của hệ thống. Mô hình là có giá trị nếu như với cùng các điều kiện đầu vào, mô hình sẽ cho kết quả không sai khác nhiều với kết quả hệ thống thực. Nếu hệ thống là mới và không có số liệu quá khứ thì mô hình mô phỏng thường được dùng như một mô hình độc lập để kiểm chứng mô hình sử dụng. Tuy nhiên cần lưu ý rằng mô hình có giá trị ở quá khứ không có nghĩa là sẽ có giá trị ở tượng lai, nên việc kiểm chứng mô hình nên thực hiện thường xuyên sử dụng mô hình để ra quyết định.

Vận dụng kết quả là diễn dịch các kết quả mô hình đã được kiểm chứng thành các chỉ dẫn dễ hiểu cho các người quản lý vận hành hệ thống. Trong 5 bước nghiên cứu vận trù, chỉ có bước giải mô hình là mang tính khoa học, các bước còn lại còn mang tính nghệ thuật.

6. Vận trù xác định

Như trên đã nêu, vận trù xác định vận dụng các phương pháp khoa học giúp các nhà quản lý ra quyết định trong các hệ thống có dữ kiện xác định. Vận trù xác định bao gồm các quy hoạch toán học sau:

Quy hoạch tuyến tính

Quy hoạch vận tải

Quy hoạch mạng

Quy hoạch mục tiêu

Quy hoạch nguyên

Quy hoạch động

Quy hoạch phi tuyến.

Các nội dung này sẽ được tuần tự trình bày ở các chương sau.

Chương 1

QUY HOẠCH TUYẾN TÍNH

Mô hình quy hoạch tuyến tính

Phương pháp đồ thị

Giải thuật đơn hình

Phân tích độ nhạy

1. Mô hình quy hoạch tuyến tính

1.1 Mô hình hóa

Mô hình quy hoạch tuyến tính được minh họa qua ví dụ là bài toán sản xuất sau.

Ví dụ: Một công ty sản xuất ra hai sản phẩm P1 và P2 sử dụng hai nguyên liệu M1 và M2. Đơn vị tính của sản phẩm và nguyên liệu là tấn (T). Lượng nguyên liệu cần cho mỗi tấn của mỗi loại sản phẩm MR (T/T), lượng nguyên liệu sẵn có hàng ngày A (T/ng) của từng nguyên liệu và lợi nhuận đơn vị của từng sản phẩm P (triệu đồng /T) như ở bảng sau:

Nghiên cứu thị trường cho thấy nhu cầu hàng ngày của P2 không quá 2 T và không vượt quá nhu cầu hàng ngày của P1 quá 1T. Vấn đề đặt ra là sản xuất P1 và P2 như thế nào để cực đại tổng lợi nhuận. Mô hình vận trù có ba thành phần:

Biến quyết định

Hàm mục tiêu

Các ràng buộc

Bước đầu tiên của việc lập mô hình là xác định biến quyết định. Biến quyết định thể hiện phương án. Khi biến quyết định đã được xác định, hàm mục tiêu và các ràng buộc sẽ được thiết lập. Với bài toán hoạch định sản xuất ở trên, cần xác định sản lượng hàng ngày của các sản phẩm P1 và P2 nên các biến quyết định được xác định như sau:

x1 là sản lượng hàng ngày của các sản phẩm P1

x2 là sản lượng hàng ngày của các sản phẩm P2

Nhằm xây dựng hàm mục tiêu, thấy rằng công ty muốn cực đại tổng lợi nhuận hàng ngày của các sản phẩm. Với lợi nhuận hàng ngày cho mỗi tấn sản phẩm các loại đã nêu, lợi nhuận hàng ngày của P1 và P2 lần lượt là 5x1 và 4x2. Tổng lợi nhuận hàng ngày của công ty là:

Z = 5x1 + 4x2

Mục tiêu cực đại lợi nhuận được mô hình bởi

Max Z = 5x1 + 4x2

Các ràng buộc của mô hình được thiết lập dựa vào các biến như sau. Đầu tiên là ràng buộc về lượng giới hạn nguyên liệu hàng ngày cho mỗi loại nguyên liệu. Lượng nguyên liệu M1 sử dụng hàng ngày cho sản phẩm P1 và P2 lần lượt là 6x1 và 4x2. Tổng lượng nguyên liệu M1 sử dụng hàng ngày cho cả hai sản phẩm là:

U1 = 6x1 + 4x2

Với giới hạn nguyên liệu đã cho ở trên ta có được ràng buộc về lượng nguyên liệu hàng ngày của M1.

6x1 + 4x2 24

Tương tự, tổng lượng nguyên liệu M2 sử dụng hàng ngày cho cả hai sản phẩm là:

U2 = x1 + 2x2

Với giới hạn nguyên liệu đã cho ở trên ta có được ràng buộc về lượng nguyên liệu hàng ngày của M2.

x1 + 2x2 6

Các ràng buộc định bởi nghiên cứu thị trường sản lượng hàng ngày của P2 không quá 2T và không vượt quá sản lượng hàng ngày của P1 quá 1T, được thể hiện như sau:

x2 2

x2 – x1 1

Ràng buộc không âm của các biến:

x1 0

x2 0

Tích hợp mục tiêu và các ràng bụôc ta được mô hình vận trù:

Max Z = 5x1 + 4x2

St.

6x1 + 4x2 24

x1 + 2x2 6

x2 2

x2 – x1  1

x1 0

x2 0

Mô hình vận trù trên được gọi là mô hình QHTT vì hàm mục tiêu và tất cả các ràng buộc bao gồm những biểu thức tuyến tính theo các biến của mô hình. Trên đây khảo sát bài toán cực đại hàm mục tiêu với bài toán cực tiểu hàm mục tiêu ta xem một ví dụ là bài toán pha trộn sau.

Ví dụ: Môt công ty pha trộn một hợp chất với hai nguyên liệu A và B với nhu cầu hàng ngày của sản phẩm là 800kg. Lượng chất C và D trong hai nguyên liệu A và B và giá nguyên liệu như ở bảng sau.

Yêu cầu của hợp chất này là ít nhất 30% lượng chất C và nhiều nhất 5% lượng chất D. Lượng nguyên liệu hàng ngày cần là bao nhiêu để thỏa nhu cầu hàng ngày và cực tiểu chi phí nguyên liệu cho hợp chất này. Nhằm mô hình hóa bài toán, chọn biến là lượng nguyên liệu hàng ngày:

x1: lượng nguyên liệu A sử dụng hàng ngày (kg)

x2: lượng nguyên liệu B sử dụng hàng ngày (kg)

Chi phí nguyên liệu hàng ngày:

z = 30x1 + 90x2 (ngàn)

Mục tiêu cực tiểu chi phí nguyên liệu hàng ngày:

Min z = 30x1 + 90x2

Ràng buộc về nhu cầu hàng ngày của hợp chất:

x1 + x2³ 800 (kg)

Ràng buộc về ít nhất 30% chất C trong hợp chất:

0,09 x1 + 0,6x2³ 0,3(x1 + x2)

Hay:

0,21 x1 – 0,3x2£ 0

Ràng buộc về nhiều nhất 5% chất D trong hợp chất:

0,02 x1 + 0,06 x2£ 0,05(x1 + x2)

Hay:

0,03 x1 – 0,01 x2³ 0

Ràng buộc biến không âm:

x1, x2³ 0

Mô hình bài toán pha trộn

Minz = 3x1 + 9x2

St.

x1 + x2³ 800

0,21 x1 – 0,3x2£ 0

0,03 x1 – 0,01 x2³ 0

x1³ 0

x2³ 0

Mô hình trên là mô hình QHTT với mục tiêu cực tiểu hàm mục tiêu.

1.2 Lời giải khả thi và lời giải tối ưu

Lời giải khả thi là lời giải không vi phạm các ràng buộc, ngược lại lời giải không khả thi là lời giải vi phạm các ràng buộc của bài toán. Chẳng hạn như ở bài toán hoạch định sản xuất trên thì (x1 = 3, x2 = 1) là một lời giải khả thi, còn (x1 = 4, x2 = 1) là một lời giải không khả thi. Lời giải tối ưu là lời giải khả thi tốt nhất. Để tìm lời giải tối ưu đầu tiên ta phải tìm tất cả các lời giải khả thi rồi sử dụng hàm mục tiêu để đánh giá tất cả các lời giải khả thi, xem lời giải nào tốt nhất thì đó là lời giải tối ưu. Thực tế cho thấy số lời giải khả thi của 1 bài toán thường là vô hạn nên không thể sử dụng phương pháp đơn giản trên để xác định lời giải tối ưu.

Để tìm lời giải tối ưu ta có thể dùng phương pháp hình học với một số bước hữu hạn có hệ thống. Phương pháp hình học tuy đơn giản và trực quan nhưng chỉ có thể giải các bài toán hai biến với bài toán nhiều biến tổng quát ta có thể dùng phương pháp đại số là phương pháp suy diễn và khái quát hóa từ phương pháp hình học. Tuy nhiên trước khi đi vào các phương pháp này, ta hãy tìm hiểu một số tính chất của mô hình QHTT

1.3 Tính chất mô hình quy hoạch tuyến tính

Mô hình QHTT có mục tiêu và ràng buộc là những hàm tuyến tính với các tính chất sau:

Tuyến tính

Cộng tính

Xác định.

Thuộc tính tuyến tính thể hiện ở chỗ đóng góp của mỗi biến vào hàm mục tiêu và các ràng bụôc là tỷ lệ thuận với giá trị biến. Thuộc tính cộng tính thể hiện ở chỗ đóng góp của mọi biến vào hàm mục tiêu và các ràng buộc là tổng của các đóng góp thành phần của các biến. Thuộc tính xác định thể hiện ở chỗ mọi hệ số trong hàm mục tiêu và các ràng buộc đều là các hằng số xác định. Điều này có thể không thực tế vì thực tế các hệ số này thường là biến thiên. Tuy nhiên nếu biến thiên nhỏ ta có thể sử dụng các giá trị kỳ vọng, còn với biến thiên lớn thì có thể phân tích độ nhạy của lời giải theo biến thiên của các tham số đầu vào.

2. Phương pháp đồ thị

Phương pháp đồ thị gồm hai bước:

Xác định vùng lời giải khả thi

Xác đinh lời giải tối ưu từ các lời giải trong vùng lời giải khả thi.

Để xác định vùng khả thi, ta sử dụng các đường thẳng mà ta gọi là đường khả thi tạo bởi các ràng buộc của bài toán. Từ vùng khả thi, ta xác định lời giải tối ưu theo phương tăng hay giảm của đường thẳng mà ta gọi là đường mục tiêu xác định bởi hàm mục tiêu tùy thuộc vào bài toán là cực đại hay cực tiểu.

2.1 Bài toán cực đại

Xem bài toán hoạch định sản xuất

Max z = 5x1 + 4x2

St.

6x1 + 4x2 24

x1 + 2x2 6

x2 2

x2 – x1 1

x1 0

x2 0

a. Xác định vùng khả thi

Vùng lời giải khả thi định bởi sáu ràng buộc:

6x1 + 4x2£ 24

x1 + 2x2£ 6

x2 – x1£ 1

x2£ 2

x1³ 0,

x2³ 0,

Các ràng buộc trên xác định các đường khả thi sau:

C1: 6x1 + 4x2 = 24

C2: x1 + 2x2 = 6

C3: x2 – x1 =1

C4: x2 = 2

C5: x1 = 0

C6: x2 = 0

Trong mặt phẳng (x1, x2), mỗi đường khả thi sẽ chia mặt phẳng thành hai nửa mặt phẳng. Vùng khả thi của mỗi ràng buộc sẽ tương ứng với một nửa mặt phẳng, thỏa ràng buộc tương ứng. Vùng khả thi của bài toán sẽ là phần giao của 6 nửa mặt phẳng tương ứng với 6 ràng buộc. Với b bài toán trên, vùng khả thi là vùng tô đậm nằm trong đa giác ABCDEF như ở hình vẽ sau.

Tất cả các điểm nằm trong vùng khả thi ABCDEF đều tương ứng với lời giải khả thi và đều là ứng viên của lời giải tối ưu. Lời giải tối ưu là một trong các lời giải khả thi này với giá trị hàm mục tiêu cực đại. Vì số lời giải khả thi là vô hạn nên không thể thử từng lời giải để tìm lời giải tối ưu, mà phải tìm một giải pháp mang tính hệ thống.

b. Xác định lời giải tối ưu

Đường mục tiêu của bài toán, tương ứng với hàm mục tiêu của bài toán:

O: 5x1 + 4x2 = z

Với những giá trị khác nhau của z, ta có những đường mục tiêu khác nhau.

z=10  O1: 5x1 + 4x2 = 10

z=15  O2: 5x1 + 4x2 = 15

Với mục tiêu cực đại hàm z, để tìm lời giải tối ưu, trong mặt phẳng (x1, x2) ta tìm phương tăng hàm mục tiêu của đường mục tiêu. Để tìm phương tăng hàm mục tiêu, ta tùy chọn hai giá trị của z, chẳng hạn như 10 và 15. Các giá trị này trên mặt phẳng x1, x2) tương ứng với hai đường mục tiêu:

O1: 5x1 + 4x2 = 10

O2: 5x1 + 4x2 = 15

Từ hai đường mục tiêu này ta xác định được phương tăng của z như ở hình sau:

Ta thấy khi z tăng, các đường mục tiêu sẽ di chuyển song song nhau theo phương tăng của z như hình vẽ trên. Các đường mục tiêu này phải cắt vùng khả thi nếu muốn có lời giải khả thi. Khi các đường mục tiêu này không cắt vùng khả thi thì sẽ không có lời giải khả thi tương ứng. Vậy giá trị giới hạn của z để vẫn còn có lời giải khả thi là tương ứng với đường mục tiêu cắt vùng khả thi ở điểm C và điểm C cũng chính là điểm tối ưu. Điểm tối ưu C là giao điểm của hai đường ràng buộc tương ứng với hai ràng bụôc 1 và 2 của bài toán:

C1: 6x1 + 4x2 = 24

C2: x1 + 2x2 = 6

Suy ra:

x1 = 3

x2 = 1,5

Và giá trị hàm mục tiêu:

z = 5  3 + 4  1,5 = 21

Vậy lời giải tối ưu là công ty sẽ sản xuất 3 tấn / ngày cho sản phẩm P1 và 1,5 tấn / ngày cho sản phẩm P2, với kế hoạch sản xuất này, lợi nhuận hàng sẽ cực đại ở giá trị là 21 triệu đồng.

2.2 Bài toán cực tiểu

Phương pháp hình học được ứng dụng tương tư cho bài toán cực tiểu hàm mục tiêu. Xem bài toán pha trộn với mô hình:

Min z = 3x1 + 9x2

St.

x1 + x2³ 800

0,21 x1 – 0,3x2£ 0

0,03 x1 – 0,01 x2³ 0

x1³ 0

x2³ 0

a. Xác định vùng khả thi

Vùng khả thi xác định bởi các ràng buộc:

x1 + x2³ 800

0,21 x1 – 0,3x2£ 0

0,03 x1 – 0,01 x2³ 0

x1³ 0

x2³ 0

Tương ứng với các đường ràng buộc:

C1: x1 + x2 = 800

C2: 0,21 x1 – 0,3x2 = 0

C3: 0,03 x1 – 0,01 x2 = 0

C4: x1 = 0

C5: x2 = 0

Vùng khả thi là vùng tô đậm như ở hình sau:

b. Xác định lời giải tối ưu

Với bài toán cực tiểu hàm mục tiêu, thay vì tìm phương tăng hàm mục tiêu như ở bài toán cực đại hàm mục tiêu, ta tìm phương giảm hàm mục tiêu qua đường mục tiêu. Các đường mục tiêu của bài toán:

O: 3x1 + 9x2 = z

Dựa vào đường mục tiêu ta xác định được phương giảm hàm mục tiêu như ở hình vẽ trên, từ phương giảm ta thấy điểm tối ưu là giao điểm của hai đường ràng buộc:

C1: x1 + x2 = 800

C2: 0,21x1 – 0,3x2 = 0

Suy ra:

x1 = 470,6

x2 = 329,4

Từ đó tính được:

Z = 437,64

Vậy lời giải tối ưu là công ty sẽ sử dụng lượng nguyên liệu hàng ngày là 470,6 kg A và 329,4kg nguyên liệu B. Chi phí nguyên liệu hàng ngày là 437,64 đồng và là chi phí cực tiểu.

2.3 Tính chất lời giải tối ưu

Từ lời giải cho các bài toán QHTT trên, trực quan thấy một tính chất quan trọng của lời giải tối ưu của mô hình QHTT là lời giải tối ưu luôn xác định một trong các điểm góc của vùng khả thi, điểm góc này là giao điểm của hai đường thẳng tương ứng với hai ràng buộc của bài toán. Điều này vẫn nghiệm đúng khi đường thẳng tương ứng với phương trình hàm mục tiêu song song với đường thẳng tương ứng với một ràng buộc của bài toán, khi này lời giải tối ưu không còn tương ứng với một điểm góc nữa mà là tương ứng với đoạn thẳng tương ứng với ràng buộc đặc biệt trên. Bài toán tối ưu bây giờ là bài toán đa nghiệm.

3. Giải thuật đơn hình

3.1 Mô hình quy họach tuyến tính chuẩn

3.1.1 Mô hình chuẩn

Giải thuật đơn hình là một phương pháp giải bài toán QHTT bằng phương pháp đại số. Nhằm thuận tiện trong tính toán, các yêu cầu của giải thuật là: Mọi ràng buộc, ngoại trừ ràng buộc biến không âm, ở dạng phương trình với vế phải không âm. Mọi biến đều không âm.

Bài toán thực tế thường không có dạng chuẩn thỏa các yêu cầu nêu trên. Trong trường hợp này phải chuyển về dạng chuẩn trước khi áp dụng giải thuật. Nếu vế phải của ràng buộc là số âm, ta có thể chuyển thành số không âm bằng cách nhân cả hai vế của ràng buộc bởi hằng số –1.

3.1.2 Biến thừa, biến thiếu

Thực tế các ràng buộc thường có dạng  hay . Với ràng buộc thường có dạng  vế phải là nguồn lực giới hạn còn vế trái là nguồn lực được sử dụng, sai biệt giữa hai vế là nguồn lực dư hay không sử dụng. Để biến đổi sang dạng phương trình ta cộng vào vế trái một biến không âm, biến này có tên gọi là biến thiếu. Với ràng buộc thường có dạng  vế phải là giới hạn dưới của các hoạt động định bởi các biến ở vế trái. Để biến đổi sang dạng phương trình ta trừ vào vế trái một biến không âm, biến này có tên gọi là biến thừa.

3.1.3 Biến lệch

Thực tế có thể có biến không ràng buộc âm dương phải đổi về dạng chuẩn là biến không âm. Xem một biến không ràng buộc x, biến x có thể chuyển thành hai biến không âm x– và x+ như sau:

x = x+ – x-

x- < x+ x > 0

x- > x+ x < 0

Các biến x– và x+ tuần tự là các biến lệch âm và lệch dương. Thực tế, các biến lệch này không đồng thời dương. Biến ban đầu x lệch dương khi:

x+ > 0, x– = 0  x > 0

Và x lệch âm khi:

x- > 0, x+ = 0  x < 0

3.2 Phương pháp đại số

3.2.1 Biến cơ bản và lời giải cơ bản

Giải bài toán QHTT bằng phương pháp hình học có ưu điểm trực quan và đơn giản nhưng chỉ giải được với bài toán hai biến, với bài toán nhiều biến phải dùng phương pháp đại số được suy diễn từ phương pháp hình học với các bước như ở sau.

Bước 1: Xác định vùng lời giải.

Phương pháp hình học: Vẽ hình biễu diễn các đường ràng buộc.

Phương pháp đại số: Hệ m phương trình chuẩn với n biến không âm (m < n).

Bước 2: Xác định các lời giải khả thi quan trọng ứng viên lời giải tối ưu.

Phương pháp hình học: Xác định các điểm góc khả thi.

Phương pháp đại số: Xác định lời giải khả thi cơ bản của hệ phương trình.

Bước 3: Dùng hàm mục tiêu xác định lời giải tối ưu trong các ứng viên.

Phương pháp hình học: Điểm góc tối ưu

Phương pháp đại số: Lời giải khả thi cơ bản tối ưu

Quan hệ các đại lượng cơ bản giữa hai phương pháp như sau:

a- Biểu diễn