Các Phương Pháp Tối Ưu Quyển 1 - GS. Trần Vũ Thiệu

Chuyên khảo phân tích Các phương pháp tối ưu quyển 1, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo., phục vụ nghiên cứu và ứng dụng thực tiễn

• Đề tài: Các Phương Pháp Tối Ưu Trong Kinh Tế và Kỹ Thuật

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: QUI HOẠCH TUYẾN TÍNH DẠNG ĐẶC BIỆT
• 1.1. Qui hoạch tuyến tính với biến bị chặn trên
• 1.2. Qui hoạch tuyến tính tham số
• 1.3. Phân rã qui hoạch tuyến tính
• 1.4. Qui hoạch tuyến tính có cấu trúc khối
• 1.5. Thuật toán điểm trong Karmarkar
• 1.6. Qui hoạch tuyến tính nhiều mục tiêu
• 2. CHƯƠNG 2: PHƯƠNG PHÁP GIẢI QUI HOẠCH NGUYÊN
• 3. CHƯƠNG 3: PHƯƠNG PHÁP TỐI ƯU TRÊN MẠNG VÀ ĐỒ THỊ
• 4. CHƯƠNG 4: PHƯƠNG PHÁP QUI HOẠCH PHI TUYẾN

Tóm tắt

I. Khám phá các phương pháp tối ưu trong kinh tế và kỹ thuật

Các phương pháp tối ưu hóa là nền tảng toán học cho phép tìm kiếm giải pháp tốt nhất cho một vấn đề trong một tập hợp các lựa chọn khả thi. Như GS. Trần Vũ Thiều đã nhấn mạnh trong lời nói đầu của cuốn sách “Các phương pháp tối ưu”, các bài toán này xuất hiện rất phổ biến trong cả lĩnh vực kinh tế và kỹ thuật, với phạm vi ứng dụng rộng rãi và đa dạng. Về bản chất, đây là một nhánh quan trọng của nghiên cứu vận hành (Operations Research), tập trung vào việc sử dụng các mô hình toán học, thống kê và thuật toán để hỗ trợ quá trình ra quyết định. Mục tiêu không chỉ là tìm ra một giải pháp, mà là tìm ra giải pháp cực đại hóa (lợi nhuận, hiệu suất) hoặc cực tiểu hóa (chi phí, rủi ro, thời gian) một hàm mục tiêu cụ thể. Mọi bài toán tối ưu đều được cấu thành từ ba thành phần chính: các biến quyết định (decision variables) là những yếu tố có thể kiểm soát; hàm mục tiêu (objective function) là biểu thức toán học cần tối ưu; và các điều kiện ràng buộc (constraints) là những giới hạn về nguồn lực, thời gian, hoặc các quy định kỹ thuật. Việc áp dụng thành công các phương pháp tối ưu trong kinh tế và kỹ thuật đòi hỏi sự hiểu biết sâu sắc về cách mô hình hóa toán học một vấn đề thực tế, chuyển các mục tiêu kinh doanh hoặc yêu cầu kỹ thuật thành một cấu trúc toán học có thể giải được. Từ việc phân bổ nguồn lực trong một doanh nghiệp, quy hoạch sản xuất trong một nhà máy, đến thiết kế kỹ thuật tối ưu cho một công trình, tất cả đều có thể được hưởng lợi từ việc áp dụng các kỹ thuật này.

1.1. Định nghĩa tối ưu hóa và vai trò trong nghiên cứu vận hành

Tối ưu hóa (Optimization) là quá trình tìm kiếm điểm cực trị (cực đại hoặc cực tiểu) của một hàm số trên một miền xác định, tuân theo các điều kiện ràng buộc cho trước. Đây là công cụ cốt lõi của lĩnh vực nghiên cứu vận hành, giúp chuyển các bài toán quản lý phức tạp thành các mô hình có thể phân tích và giải quyết một cách có hệ thống. Vai trò của nó là cung cấp một cơ sở định lượng để đưa ra các quyết định hiệu quả nhất, thay vì dựa trên kinh nghiệm hoặc phỏng đoán.

1.2. Các thành phần cốt lõi hàm mục tiêu và điều kiện ràng buộc

Một bài toán tối ưu hóa được xác định rõ ràng thông qua ba yếu tố. Thứ nhất là biến quyết định, đại diện cho các lựa chọn cần đưa ra (ví dụ: số lượng sản phẩm cần sản xuất). Thứ hai là hàm mục tiêu, một phương trình toán học biểu diễn mục tiêu cần đạt được (ví dụ: hàm lợi nhuận cần tối đa hóa). Cuối cùng là điều kiện ràng buộc, các bất đẳng thức hoặc phương trình thể hiện giới hạn của hệ thống (ví dụ: nguồn vốn, nhân lực, công suất máy móc).

II. Bài toán tối ưu hóa Từ mô hình hóa đến các thách thức

Thách thức lớn nhất khi áp dụng các phương pháp tối ưu trong kinh tế và kỹ thuật không nằm ở việc giải thuật toán, mà là ở giai đoạn mô hình hóa toán học vấn đề. Việc chuyển một tình huống thực tế, với nhiều yếu tố phức tạp và bất định, thành một mô hình toán học chính xác là bước quyết định sự thành công. Mô hình cần phải đủ đơn giản để có thể giải được trong thời gian hợp lý nhưng cũng phải đủ chi tiết để phản ánh đúng bản chất của vấn đề. Một trong những quyết định quan trọng nhất trong quá trình này là phân loại bài toán. Các bài toán có thể được chia thành quy hoạch tuyến tính (Linear Programming), khi cả hàm mục tiêu và các ràng buộc đều là hàm tuyến tính, và quy hoạch phi tuyến (Nonlinear Programming), khi có ít nhất một trong số chúng không phải là tuyến tính. Ngoài ra còn có quy hoạch nguyên (Integer Programming) khi các biến quyết định phải nhận giá trị nguyên. Theo tài liệu của GS. Trần Vũ Thiều, kinh nghiệm tính toán cho thấy thời gian giải bài toán quy hoạch tuyến tính phụ thuộc chủ yếu vào số lượng ràng buộc. Do đó, việc xác định đúng cấu trúc bài toán và lựa chọn phương pháp giải phù hợp là cực kỳ quan trọng. Các vấn đề như bài toán vận tải hay quy hoạch sản xuất thường thuộc dạng tuyến tính, trong khi các bài toán liên quan đến động lực học hệ thống hay tối ưu hóa danh mục đầu tư với các mô hình rủi ro phức tạp thường là phi tuyến. Thách thức khác là việc thu thập dữ liệu chính xác để xác định các tham số trong mô hình.

2.1. Quy trình xây dựng một mô hình hóa toán học hiệu quả

Quy trình này bao gồm các bước: (1) Xác định rõ ràng vấn đề và mục tiêu cần đạt được. (2) Nhận diện các biến quyết định và các tham số không đổi. (3) Xây dựng hàm mục tiêu dưới dạng một biểu thức toán học. (4) Liệt kê và công thức hóa tất cả các điều kiện ràng buộc của hệ thống. (5) Kiểm tra và xác thực mô hình để đảm bảo nó phản ánh chính xác thực tế.

2.2. Phân loại bài toán Tuyến tính phi tuyến và quy hoạch nguyên

Việc phân loại bài toán quyết định phương pháp giải sẽ được sử dụng. Quy hoạch tuyến tính (Linear Programming) là dạng phổ biến và có thuật toán giải hiệu quả nhất. Quy hoạch phi tuyến (Nonlinear Programming) phức tạp hơn, thường yêu cầu các phương pháp lặp và không đảm bảo tìm được nghiệm tối ưu toàn cục. Quy hoạch nguyên xử lý các biến rời rạc, thường gặp trong các bài toán lập lịch hoặc lựa chọn dự án.

III. Quy hoạch tuyến tính Nền tảng của các phương pháp tối ưu

Quy hoạch tuyến tính (Linear Programming) là một trong những công cụ mạnh mẽ và được sử dụng rộng rãi nhất trong nghiên cứu vận hành. Nó giải quyết các bài toán mà ở đó mục tiêu là tối đa hóa hoặc tối tiểu hóa một hàm mục tiêu tuyến tính, trong khi phải tuân thủ một tập hợp các ràng buộc cũng ở dạng tuyến tính. Phương pháp đơn hình (Simplex Method), do George Dantzig phát triển, là thuật toán kinh điển và hiệu quả để giải quyết hầu hết các bài toán quy hoạch tuyến tính. Sức mạnh của nó nằm ở khả năng duyệt qua các đỉnh của miền khả thi một cách có hệ thống để tìm ra nghiệm tối ưu. Tài liệu của GS. Trần Vũ Thiều trình bày chi tiết về các dạng đặc biệt của quy hoạch tuyến tính, chẳng hạn như "quy hoạch tuyến tính với biến bị chặn trên", một vấn đề thường gặp trong thực tế khi các biến số có giới hạn tối đa. Phương pháp xử lý các ràng buộc này một cách riêng biệt giúp giảm đáng kể thời gian tính toán so với việc thêm chúng vào hệ ràng buộc chính. Các ứng dụng kinh điển của quy hoạch tuyến tính bao gồm bài toán vận tải (tìm cách vận chuyển hàng hóa từ nhiều nguồn đến nhiều đích với chi phí thấp nhất) và bài toán phân bổ nguồn lực (phân chia các nguồn lực có hạn như vốn, nhân công, nguyên vật liệu cho các hoạt động khác nhau để đạt lợi nhuận cao nhất).

3.1. Lý thuyết cơ bản và phương pháp đơn hình Simplex method

Phương pháp đơn hình hoạt động trên nguyên tắc di chuyển từ một đỉnh (phương án cực biên) của miền ràng buộc đến một đỉnh kề cận tốt hơn, lặp lại quá trình này cho đến khi không thể cải thiện thêm hàm mục tiêu. Quá trình này được thực hiện thông qua các phép biến đổi trên một bảng gọi là bảng đơn hình, đảm bảo tìm ra lời giải tối ưu sau một số hữu hạn bước.

3.2. Phân tích bài toán vận tải và phân bổ nguồn lực

Bài toán vận tải là một ví dụ điển hình của quy hoạch tuyến tính, với mục tiêu tối thiểu hóa chi phí logistics. Tương tự, bài toán phân bổ nguồn lực giúp các nhà quản lý ra quyết định phân chia ngân sách, nhân sự, hoặc thời gian một cách tối ưu để tối đa hóa hiệu quả hoạt động, đây là ứng dụng trực tiếp và quan trọng trong tối ưu hóa vận hành.

IV. Top phương pháp tối ưu phi tuyến và thuật toán heuristic

Khi các mối quan hệ trong bài toán không còn tuyến tính, chúng ta bước vào lĩnh vực quy hoạch phi tuyến (Nonlinear Programming). Các bài toán này phức tạp hơn đáng kể vì miền khả thi có thể không lồi và hàm mục tiêu có thể có nhiều điểm cực trị địa phương. Việc tìm kiếm nghiệm tối ưu toàn cục trở thành một thách thức lớn. Các phương pháp giải cho quy hoạch phi tuyến thường mang tính lặp, chẳng hạn như phương pháp Gradient Descent, phương pháp Newton, hay các phương pháp dựa trên điều kiện Karush-Kuhn-Tucker (KKT). Tuy nhiên, đối với các bài toán có độ phức tạp cực lớn hoặc cấu trúc không rõ ràng, các thuật toán heuristic và metaheuristic lại tỏ ra vô cùng hiệu quả. Những thuật toán này không đảm bảo tìm ra nghiệm tối ưu tuyệt đối nhưng thường cho kết quả đủ tốt trong thời gian tính toán hợp lý. Thuật toán di truyền (Genetic Algorithm) là một ví dụ nổi bật, mô phỏng quá trình tiến hóa tự nhiên thông qua các cơ chế lựa chọn, lai ghép và đột biến để tìm kiếm giải pháp. Một kỹ thuật khác là mô phỏng Monte Carlo, sử dụng các mẫu ngẫu nhiên để ước tính và tối ưu hóa các hệ thống phức tạp, đặc biệt hữu ích trong phân tích rủi ro và tối ưu hóa danh mục đầu tư. Các thuật toán này là công cụ không thể thiếu khi đối mặt với các bài toán tối ưu hóa tổ hợp hoặc các không gian tìm kiếm khổng lồ.

4.1. Giải quyết bài toán quy hoạch phi tuyến Nonlinear Programming

Giải quyết bài toán quy hoạch phi tuyến đòi hỏi các công cụ toán học cao cấp hơn. Các thuật toán thường bắt đầu từ một điểm ban đầu và lặp đi lặp lại việc tìm kiếm một hướng đi cải thiện và một độ dài bước phù hợp để tiến tới một điểm tốt hơn. Thách thức chính là tránh bị mắc kẹt tại các điểm tối ưu địa phương thay vì tìm ra điểm tối ưu toàn cục.

4.2. Khám phá thuật toán di truyền và mô phỏng Monte Carlo

Thuật toán di truyền thuộc lớp metaheuristic, rất mạnh trong việc giải các bài toán tối ưu hóa tổ hợp như bài toán người bán hàng (Traveling Salesman Problem). Trong khi đó, mô phỏng Monte Carlo thường được áp dụng trong tài chính để mô hình hóa sự biến động của giá tài sản, từ đó giúp xây dựng các chiến lược tối ưu hóa danh mục đầu tư nhằm cân bằng giữa lợi nhuận và rủi ro.

V. Ứng dụng các phương pháp tối ưu trong kinh tế kỹ thuật

Tính ứng dụng thực tiễn là minh chứng rõ ràng nhất cho sức mạnh của các phương pháp tối ưu trong kinh tế và kỹ thuật. Trong lĩnh vực kinh tế và quản trị kinh doanh, quản lý chuỗi cung ứng (Supply Chain Optimization) là một trong những lĩnh vực hưởng lợi nhiều nhất. Các doanh nghiệp sử dụng các mô hình tối ưu để quyết định vị trí đặt nhà kho, lộ trình vận chuyển, mức tồn kho an toàn và chiến lược quy hoạch sản xuất nhằm giảm thiểu chi phí và nâng cao khả năng đáp ứng khách hàng. Trong lĩnh vực tài chính, các mô hình tối ưu hóa danh mục đầu tư giúp các nhà đầu tư xây dựng danh mục tài sản mang lại lợi nhuận kỳ vọng cao nhất với một mức rủi ro chấp nhận được. Trong kỹ thuật, các ứng dụng còn đa dạng hơn. Thiết kế kỹ thuật tối ưu sử dụng các thuật toán để tìm ra hình dạng, kích thước và vật liệu tốt nhất cho các kết cấu (như dầm cầu, cánh máy bay) để chúng vừa nhẹ, vừa bền, vừa tiết kiệm chi phí. Lĩnh vực điều khiển tối ưu (Optimal Control) nghiên cứu cách điều khiển một hệ thống động (ví dụ: robot, tên lửa, quy trình hóa học) theo thời gian để đạt được một mục tiêu nhất định. Để giải quyết các bài toán này, các kỹ sư và nhà kinh tế học thường sử dụng các phần mềm tối ưu hóa chuyên dụng như MATLAB, LINGO, GAMS hoặc các thư viện mạnh mẽ trong các ngôn ngữ lập trình như Python Scipy.

5.1. Tối ưu hóa chuỗi cung ứng và quy hoạch sản xuất

Đây là ứng dụng cốt lõi của tối ưu hóa vận hành. Các mô hình toán học giúp giải quyết các bài toán phức tạp như bài toán vận tải, lập lịch sản xuất, và quản lý tồn kho. Mục tiêu là tạo ra một chuỗi cung ứng linh hoạt, hiệu quả về chi phí và đáp ứng nhanh chóng với sự thay đổi của thị trường, trực tiếp nâng cao năng lực cạnh tranh của doanh nghiệp.

5.2. Các phần mềm tối ưu hóa MATLAB Python Scipy và LINGO

Việc giải các bài toán tối ưu phức tạp trong thực tế không thể thực hiện bằng tay. Các công cụ như MATLAB với Optimization Toolbox, các thư viện mã nguồn mở như Python Scipy (scipy.optimize), hay các phần mềm chuyên dụng như LINGO và GAMS cung cấp các bộ giải (solver) mạnh mẽ, cho phép các chuyên gia tập trung vào việc mô hình hóa toán học vấn đề thay vì lập trình thuật toán từ đầu.

VI. Hướng phát triển mới của các phương pháp tối ưu hiện đại

Lĩnh vực tối ưu hóa không ngừng phát triển, đặc biệt với sự trỗi dậy của khoa học dữ liệu và trí tuệ nhân tạo. Một trong những bước đột phá quan trọng trong lịch sử quy hoạch tuyến tính là sự ra đời của thuật toán điểm trong (Interior-Point Methods), tiêu biểu là thuật toán của Karmarkar vào những năm 1980. Như được đề cập trong tài liệu tham khảo, khác với phương pháp đơn hình di chuyển dọc theo các cạnh của miền ràng buộc, thuật toán điểm trong đi xuyên qua phần bên trong của miền đó. Đối với các bài toán quy mô cực lớn (hàng chục ngàn ràng buộc), thuật toán điểm trong thường tỏ ra nhanh hơn đáng kể so với phương pháp đơn hình. Hướng phát triển tương lai của các phương pháp tối ưu trong kinh tế và kỹ thuật tập trung vào việc kết hợp tối ưu hóa với học máy (Machine Learning). Các mô hình học máy có thể được sử dụng để dự báo các tham số đầu vào cho bài toán tối ưu (ví dụ: dự báo nhu cầu khách hàng), sau đó mô hình tối ưu sẽ đưa ra quyết định dựa trên các dự báo đó. Ngược lại, các kỹ thuật tối ưu cũng được dùng để huấn luyện các mô hình học máy phức tạp. Tương lai của ngành nghiên cứu vận hành sẽ chứng kiến sự tích hợp ngày càng sâu sắc giữa tối ưu hóa xác định (deterministic), tối ưu hóa ngẫu nhiên (stochastic) và các kỹ thuật xử lý dữ liệu lớn để giải quyết các bài toán ngày càng phức tạp và δυναμικ trong thế giới thực.

6.1. Thuật toán điểm trong Karmarkar và hiệu suất tính toán

Thuật toán Karmarkar là một cột mốc, chứng minh rằng quy hoạch tuyến tính có thể được giải trong thời gian đa thức. Mặc dù mỗi bước lặp của nó phức tạp hơn phương pháp đơn hình, số bước lặp cần thiết cho các bài toán lớn lại ít hơn nhiều. Điều này mở đường cho việc giải quyết các bài toán tối ưu hóa với quy mô chưa từng có, đặc biệt trong các lĩnh vực như viễn thông và logistics.

6.2. Tương lai của ngành nghiên cứu vận hành Operations Research

Ngành nghiên cứu vận hành đang dịch chuyển sang việc xử lý các hệ thống quy mô lớn, bất định và có dữ liệu thời gian thực. Sự kết hợp giữa tối ưu hóa, mô phỏng, và phân tích dữ liệu sẽ là chìa khóa để giải quyết các thách thức toàn cầu như quản lý chuỗi cung ứng bền vững, tối ưu hóa mạng lưới năng lượng thông minh và phát triển các hệ thống giao thông tự hành.

Trích đoạn nội dung tài liệu

Chương 1. Qui hoạch tuyến tính dạng đặc biệt. Qui hoạch tuyến tính với biến bị chặn trên. Nội đung vấn đề.

Phương pháp xử lý biến bị chặn trên. Ví dụ minh họa. Qui hoạch tuyến tính tham số. Nội dung bài toán .- -:sc Sc St ssikeirrrerrsrrke 17 2.

Phương pháp giải. Ví dụ minh họa. Về phải phụ thuộc tham số. Phân rã qui hoạch tuyến tính.

Tư tưởng cơ bản của phương pháp phân rã. Phân rã khi miền G không bị chặn. Xác định phương án tựa xuất phát. Qui hoạch tuyến tính có cau trúc khối §4.

Thuật toán điểm trong Karmarkar. Vài nét lịch sử phát triỂn. Nội dung phương pháp Karmarkar. So sánh với phương pháp đơn hình.

Qui hoạch tuyến tính nhiều mục tiêu. Qui hoạch nhiều mục tiêu không ưu tiên. Qui hoạch nhiều mục tiêu có ưu tiên.--------- 65 Đài LẬP sázt19006160160601E0G19E0E1E14A4153535363143838SIX411EEES14G1S1348813388 71 Chương1 QUI HOẠCH TUYỂN TÍNH DANG DAC BIET §1. QUI HOACH TUYEN TiNH VOI BIEN BI CHAN TREN 1.

Nội dung vấn đề Xét bài toán qui hoạch tuyến tính dạng bất kỳ (chính tắc, chuẩn tắc, tổng quát), trong đó một số biến hay tất cả các biến số có thêm ràng buộc dạng sau đây, gọi là rằng buộc cận trên: ø S Mị,J€ư/ € {1\2,:::¡n}; (1.1) trong đó +; là hằng số dương cho trước biểu thị giá trị tối đa mà biến z; có thể nhận. Kinh nghiệm tính toán giải các bài toán qui hoạch tuyến tính bằng phương pháp đơn hình cho thấy thời gian giai phụ thuộc chủ yếu vào số ràng buộc chính m, còn các ràng buộc không âm (ràng buộc về dấu) có ảnh hưởng không đáng kể. Vì thế, nếu ghép thêm các ràng buộc cận trên (1.1) vào các ràng buộc chính sẽ làm tăng đáng kể thời gian tính toán. Để khắc phục nhược điểm này, ta hãy tạm gác bỏ các ràng buộc cận trên khỏi các ràng buộc chính và sẽ xử lý chúng một cách riêng biệt, tương tự như đã làm đối với các ràng buộc về dấu.

Việc tạm bỏ qua các ràng buộc cận trên như thế sẽ không anh hưởng tới kết qua giải, nếu như không có biến số nào tăng vượt quá cận trên của nó. Chi khi đưa một biến mới vào cơ sở (tăng giá trị của nó) để chuyển sang phương án cực biên mới, thì phương pháp đơn hình có thể sẽ làm tăng một số biến cơ sở. Vì thế, cần có biện pháp xử lý đảm bảo cho các biến cơ sở không tăng vượt quá cận trên của chúng. Phương pháp xử lý biến bị chặn trên Xét bài toán qui hoạch tuyến tính với các biến bị chặn trên có dạng như sau: n j= Sot —> mịn, (1.2) j=l với các điều kiện So airy = bi, i=1,2,.5) trong đó u; là các hằng số dương hữu hạn, cho trước.

Khi mị < n thì chỉ một số biến có cận trên, còn nếu mị = n thì mọi biến đều bị chặn trên. Ký hiệu 4; = (a1j;,42j,---;@mj)? là véctơ cột thứ7 cua ma trận ràng buộc (1. Cũng như trước đây, vécto 2? = (21, 22,.,2n) thoa man các điều kiện (1.5) được gọi là một phương án. Một phương án đạt cực tiểu của hàm mục tiêu (1.2) gọi là một phương án tối ưu hay lời giải của bài toán (1.

Về đại thể phương pháp giải bài toán (1.5) tương tự như phương pháp đơn hình giải qui hoạch tuyến tính, nghĩa là ta sẽ xuất phát từ một phương án cực biên nào đó, mỗi phương án cực biên sẽ tương ứng với một cơ sở, dựa vào cơ sở này ta sẽ tính ước lượng cho các biến phi cơ sở, nếu các ước lượng thoả mãn tiêu chuẩn tối ưu thì dừng thuật toán. Trái lại, ta sẽ tìm cách thay đổi cơ sở để chuyển sang một phương án cực biên mới tốt hơn. Quá trình này được tiếp tục cho đến khi nhận được phương án tối ưu. Các khái niệm phương án cực biên, cơ sở, tiêu chuẩn tối uu.

về cơ bản vẫn tương tự như cũ, tuy nhiên cần có đôi chút sửa đổi cho phù hợp với bài toán mới (1. Phương án z được gọi là phương án cực biên nếu hệ véctơ {Aj:0<2; <u;, j7 Sn1}U{A; tT7 >Ũ, 7 >m}. là độc lập tuyến tính. Cơ sở cuả một phương án cực biên ở đây được hiểu là tập chỉ số J C {1,2,.,n} thoa mãn |J| = m, {A;;j € J} độc lap tuyén tinh va dD {7 20 = a < ty, f Sy} Us op 30, 2 Soni fe Cac bién x;,j € J goi la biến cơ sở, còn biến z;,7 ¢ J gọi là biến phi cơ sở.

Khác với phương pháp đơn hình thông thường, biến phi cơ sở ở đây có thể nhận giá trị dương: z; = Uj. Biến thể sau đây của phương pháp đơn hình cho phép giải bài toán (1.5) sau một số hữu hạn bước lặp. Bước 0: Xây dựng phương án cực biên ban đầu z1 (chẳng hạn theo phương pháp phạt hay đánh thuế như trong qui hoạch tuyến tính). Ký hiệu cơ sở của phương an a! là J).

Tìm các hệ số khai triển z;¿ (7 € J, k # 7¡) của véctơ 4¿ từ hệ phương trình: Ax = »` #/kÂ;, k ¢ Jy. JEN và tính các ước lượng (Cũng như trước đấy, A; = 0 với mọi j € Jy nén khong can tính). Giá trị biến cơ sơ còn được tính từ hệ phương trình sau: b— ». = ÀmJẢ,, J¢ J JEN trong đó b = (b,b;,.,b„)” là véctơ các hệ số ở vế phải ràng buộc (1.

Bang don hình tương ứng với phương án cực biên z 1 có dạng như sau: T10 T11 #12 tee Zin #20 T21 T22 tee Z2n #m0 #Ÿm1 #m2 tae Tmmn #m+10 |ŸØm+1l Lm4+12 --- Tm+ln trong đó z;, là giá trị biến thứ ¿ trong cơ sơ (biến s;), #m+1,0 là giá trị hàm mục tiêu, zm+¡,; là các ước lượng A¡. Đặt k = 1 và tiến hành Bước 1 của vòng lặp thứ È. Bước 1: kiểm tra tối ưu. Phương án hiện có zẺ là tối ưu nếu điều kiện sau đây được thoa mãn A¿ < 0 với mọi j ý J¿ và z‡ =0, ges Š 3 Ñ k A; > 0 với mọi j ý J¿ và z; = u¿, 10 Nếu tiêu chuẩn tối ưu trên không thoa mãn, ta chuyển sang Bước 2.

Bước 2: tìm cột quay. Chọn biến phi cơ sở z¿ đưa vào cơ sở (nếu cần) theo qui tắc: A = max(AT,A~) với AT = max {A;:j ¢ Jz, xf = 0}, A™~ = max {-A;:j ¢ Jk, +} =u;}, (Theo qui ước chung, max trên tập rỗng bằng —os). Ký hiệu s ý 7; là chỉ số sao cho A = A,. Có hai trường hợp xay ra: a) A, > 0: giá trị biến phi cơ sở z; với z‡ = 0 sẽ tăng và biến này sẽ trở thành biến cơ sở nếu giá trị mới cuả nó chưa đạt tới cận trên u;.

b) A, <0: gid trị biến phi cơ sở z, với z‡ = u¿ sẽ giảm và biến này sé trở thành biến cơ sở nếu giá trị mới cuả nó vẫn dương. Bước 3: tìm dòng quay. Ký hiệu Ø = min (41, 42, 93) với (1.6) +oœ_ nếu s >7, Øy —= ty nếu s < mm, e Truong hop A, >0: 6, = min ce : Lis > OF, Tis 11 e Truong hop A, <0: T¡0 6, = min{ tis < O}, Tis š tạ; — T¡0 6; = min {— tis > 0,5; <r} Lis (Nếu s;¿ > mị với mọi ? = 1,2,.,m, nghĩa là mọi biến cơ sở đều không bị chặn trên thì đặt 0; = +oo. Điều này phù hợp với qui ước chung là min trên tập rỗng bằng +œ).

Nếu Ø < Ø¡, thì biến tương ứng với dòng đạt min cua 6 trong (1.6) sẽ bị loại khỏi cơ sở. Bước 4: biến đổi cơ sở. Nếu 0 = 0, thi co so khong thay đổi, chỉ có phương án và giá trị mục tiêu cuả bài toán biến đổi. Trái lại, ký hiệu r là dòng cuả bảng đơn hình đạt min cua Ø trong (1.6), khi đó biến ¿„ sẽ bị loại khỏi cơ sở và biến s sẽ trở thành biến cơ sở.

Cơ sở mới sẽ là: Tei = (Je \ {ir}) U {5}. Bước 5: biến đổi phương án và giá trị mục tiêu. e Trường hợp A, >0: Giá trị các biến cơ sơ: tig = #¡o — Ö2¡¿, ¡ = 1,2,. Giá trị biến cơ sở mới khi Ø < đị : z; = Ø.

Giá trị biến phi cơ sở: nếu Ø = Ø¡ thì: z¡ t8 = u¿, còn nếu 0 <0) thì: z; = tro —Ô7y;. Giá trị mục tiêu: #„ tp = #m+1o — Ô¡. e Truong hop A, <0: Giá trị các biến cơ sơ: Tịp = #;o +Ôz¡;, ¿ = 1,2,. Giá trị biến cơ sở mới khi Ø < Ổi : vig = tu; — Ô.

12 Giá trị biến phi cơ sở: nếu Ø = Ø; thì: x! = 0, con néu 8 <0) thì: zi, = #rọ +Ôz;;. Giá trị mục tiêu: #„¡ọ = #m+lo +ÓÁ,. Biến đổi dòng quay (dòng P)¿ fj = Laz / Prey J Hy Qyevegns Biến đổi các dòng khác cua bang don hình: ! — ae. 1 — Tịj — Tis, = ¡j — #r7Tis; ¿ =1,2,.

Như vậy, n cột cuối cuả bảng được biến đổi hoàn toàn giống như trong phương pháp đơn hình thông thường, chỉ có điều khác là ở đây phần tử chính (phần tử quay) có thể là số âm. Quay lại Bước 1 cuả vòng lặp k + 1. Vi du minh hoa Giải bài toán qui hoạch tuyến tính sau: f = zy +22. +23 —> min, với các điều kiện 47 + T2 = 8, —271 + z3 =4, 0<z¡<4,0<z;<10,0<z <6.

Trong bài toán này cả 3 biến đều bị chặn trên (uị = 4,uạ = 10, us = 6). Phương án cực biên ban dau: c! = (0 8 4) (không cần thêm biến gia). z;,+; là biến cơ sở : Jy = {2,3}. z¡ là biến phi cơ sở.

(4 - 2) là các hệ số khai triển cua véctơ điều kiện 4i theo các vếctơ cơ so Aj, A3. Bang don hình ban đầu có dạng: cq = 1 = #7 cy x! Ty = 0 |z;=8 „=4 zs |cạ=2 |zio= 8 | = 4|Zi¿=Ll|ziz¿=0 T3 ca = Ì #20 —= 4 T21 =—2 +23 — 23 = l 30 = 20 03, = 5 +32 —= +33 — 0 Bước 1. Kiểm tra tối ưu: phương án z! hiện có chưa phải là tối ưu, vì biến phi cơ sở z¡ có z = 0 và A¡ =5 >Ũ. Tìm cột quay: biến z¡ được chọn đưa vào cơ sở.

Chọn dòng quay: 6¡ = uị = 4, 0 = 8/4 = 2, 63 = (6—4)/2 = 1. Bién x3 tuong ứng bị loại khỏi cơ sở (r = 2). Phần tử quay là zại = —2. Đổi cơ sở: Do Ø = 1 < 6¡ = 4 nên biến z¡ vào cơ sở thay cho biến cơ sở ở dòng 2 (biến z¿): J; = {2,1}.