Tối ưu hóa giúp bạn tìm ra kết quả tốt nhất mang lại lợi nhuận, giảm chi phí hoặc đặt một thông số gây ra lỗi trong quy trình kinh doanh.
Quá trình này còn được gọi là lập trình toán học. Nó giải quyết vấn đề xác định phân phối các nguồn lực hạn chế cần thiết để đạt được mục tiêu do người đứng đầu bài toán tối ưu hóa đề ra. Trong tất cả các phương án có thể, bạn nên tìm phương án tối đa hóa (hoặc giảm) thông số kiểm soát, ví dụ, lợi nhuận hoặc chi phí. Các mô hình tối ưu hóa còn được gọi là mô hình quy định hoặc quy chuẩn bởi vì chúng tìm kiếm một chiến lược khả thi cho doanh nghiệp.
Lịch sử phát triển
Lập trình tuyến tính (LP) hoạt động với một lớp các bài toán tối ưu hóa trong đó tất cả các ràng buộc đều là tuyến tính.
Trình bày sơ lược về lịch sử phát triển của LP:
- Năm 1762, Lagrange đã giải quyết các vấn đề tối ưu hóa đơn giản với các ràng buộc bình đẳng.
- Năm 1820, Gauss quyết địnhhệ phương trình tuyến tính sử dụng loại bỏ.
- Năm 1866, Wilhelm Jordan đã hoàn thiện phương pháp tìm sai số bình phương nhỏ nhất như một tiêu chí phù hợp. Phương pháp này hiện được gọi là phương pháp Gauss-Jordan.
- Máy tính kỹ thuật số xuất hiện vào năm 1945.
- Danzig đã phát minh ra phương pháp simplex vào năm 1947.
- Năm 1968, Fiacco và McCormick giới thiệu phương pháp Inside Point.
- Năm 1984, Karmarkar áp dụng phương pháp nội thất để giải các chương trình tuyến tính, bổ sung thêm phân tích sáng tạo của mình.
LP đã được chứng minh là một công cụ cực kỳ mạnh mẽ cho cả việc mô hình hóa các vấn đề trong thế giới thực và như một lý thuyết toán học được áp dụng rộng rãi. Tuy nhiên, nhiều vấn đề tối ưu hóa thú vị là phi tuyến tính.
Làm gì trong trường hợp này? Việc nghiên cứu các vấn đề như vậy liên quan đến một hỗn hợp đa dạng của đại số tuyến tính, phép tính đa biến, phân tích số và các phương pháp tính toán. Các nhà khoa học đang phát triển các thuật toán tính toán, bao gồm các phương pháp điểm bên trong để lập trình tuyến tính, hình học, phân tích các tập hợp và hàm lồi cũng như nghiên cứu các vấn đề có cấu trúc đặc biệt như lập trình bậc hai.
Tối ưu hóa phi tuyến cung cấp hiểu biết cơ bản về phân tích toán học và được sử dụng rộng rãi trong các lĩnh vực khác nhau như kỹ thuật, phân tích hồi quy, quản lý tài nguyên, thăm dò địa vật lý và kinh tế.
Phân loại các bài toán tối ưu hóa
Một bước quan trọng trongQuá trình tối ưu hóa là phân loại các mô hình, vì các thuật toán giải pháp của chúng được điều chỉnh cho phù hợp với một loại cụ thể.
1. Các vấn đề với tối ưu hóa rời rạc và liên tục. Một số mô hình chỉ có ý nghĩa nếu các biến nhận giá trị từ một tập con rời rạc của các số nguyên. Những người khác chứa dữ liệu có thể nhận bất kỳ giá trị thực nào. Chúng thường dễ giải quyết hơn. Những cải tiến trong thuật toán, kết hợp với những tiến bộ trong công nghệ máy tính, đã làm tăng đáng kể quy mô và độ phức tạp của một bài toán tối ưu hóa lập trình tuyến tính.
2. Tối ưu hóa không giới hạn và có giới hạn. Một sự khác biệt quan trọng khác là các nhiệm vụ không có ràng buộc về các biến. Nó có thể bao gồm rộng rãi từ các công cụ ước lượng đơn giản đến các hệ thống bình đẳng và bất bình đẳng mô hình hóa các mối quan hệ phức tạp giữa các dữ liệu. Các bài toán tối ưu hóa như vậy có thể được phân loại thêm theo bản chất của các hàm (tuyến tính và phi tuyến tính, lồi và mịn, có thể phân biệt và không phân biệt được).
3. Nhiệm vụ khả thi. Mục tiêu của họ là tìm các giá trị biến đáp ứng các ràng buộc của mô hình mà không có bất kỳ mục tiêu tối ưu hóa cụ thể nào.
4. Nhiệm vụ bổ sung. Chúng được sử dụng rộng rãi trong công nghệ và kinh tế. Mục đích là tìm một giải pháp thỏa mãn các điều kiện bổ sung. Trong thực tế, các nhiệm vụ có một số mục tiêu thường được định dạng lại thành các mục tiêu duy nhất.
5. Tối ưu hóa xác định so với ngẫu nhiên. Tối ưu hóa xác định giả định rằng dữ liệu chobài tập hoàn toàn chính xác. Tuy nhiên, trong nhiều vấn đề thời sự, chúng không thể được biết đến vì một số lý do.
Đầu tiên phải làm với một lỗi đo lường đơn giản. Lý do thứ hai là cơ bản hơn. Nó nằm ở chỗ một số dữ liệu đại diện cho thông tin về tương lai, ví dụ, nhu cầu đối với một sản phẩm hoặc giá cả trong một khoảng thời gian trong tương lai. Khi tối ưu hóa trong các điều kiện tối ưu ngẫu nhiên, mô hình không chắc chắn sẽ được đưa vào.
Thành phần chính
Hàm mục tiêu là hàm được thu nhỏ hoặc tối đa. Hầu hết các dạng bài toán tối ưu hóa đều có một hàm mục tiêu. Nếu không, chúng thường có thể được định dạng lại để hoạt động.
Hai ngoại lệ đối với quy tắc này:
1. Nhiệm vụ tìm kiếm mục tiêu. Trong hầu hết các ứng dụng kinh doanh, người quản lý muốn đạt được một mục tiêu cụ thể trong khi thỏa mãn các ràng buộc của mô hình. Người dùng đặc biệt không muốn tối ưu hóa thứ gì đó, vì vậy việc xác định một hàm mục tiêu là vô nghĩa. Loại này thường được gọi là vấn đề thỏa mãn.
2. Rất nhiều tính năng khách quan. Thông thường, người dùng muốn tối ưu hóa nhiều mục tiêu khác nhau cùng một lúc. Chúng thường không tương thích. Các biến tối ưu hóa cho một mục tiêu có thể không tốt nhất cho các mục tiêu khác.
Loại thành phần:
- Đầu vào được kiểm soát là một tập hợp các biến quyết định ảnh hưởng đến giá trị của một hàm mục tiêu. Trong một nhiệm vụ sản xuất, các biến số có thể bao gồm việc phân phối các nguồn lực sẵn có khác nhau hoặc lao động cần thiết đểmỗi hành động.
- Ràng buộc là mối quan hệ giữa các biến quyết định và tham số. Đối với vấn đề sản xuất, việc dành nhiều thời gian cho bất kỳ hoạt động nào là không hợp lý, vì vậy hãy hạn chế tất cả các biến "tạm thời".
- Giải pháp khả thi và tối ưu. Giá trị của quyết định đối với các biến, theo đó tất cả các ràng buộc đều được thỏa mãn, được gọi là thỏa mãn. Hầu hết các thuật toán đầu tiên tìm thấy nó, sau đó cố gắng cải thiện nó. Cuối cùng, họ thay đổi các biến để chuyển từ giải pháp khả thi này sang giải pháp khả thi khác. Quá trình này được lặp lại cho đến khi hàm mục tiêu đạt cực đại hoặc cực tiểu. Kết quả này được gọi là giải pháp tối ưu.
Các thuật toán của các bài toán tối ưu hóa được phát triển cho các chương trình toán học sau được sử dụng rộng rãi:
- Lồi.
- Tách biệt.
- Bậc hai.
- Hình học.
Google Linear Solvers
Tối ưu hóa hoặc lập trình tuyến tính là tên được đặt cho quá trình tính toán để giải quyết một vấn đề một cách tối ưu. Nó được mô hình hóa như một tập hợp các mối quan hệ tuyến tính nảy sinh trong nhiều ngành khoa học và kỹ thuật.
Google đưa ra ba cách để giải quyết các vấn đề về tối ưu hóa tuyến tính:
- Thư viện mã nguồn mở Glop.
- Tiện ích bổ sung Tối ưu hóa Tuyến tính cho Google Trang tính.
- Dịch vụ Tối ưu hóa Tuyến tính trong Google Apps Script.
Glop được tích hợp vào Googlebộ giải tuyến tính. Nó có sẵn trong mã nguồn mở. Bạn có thể truy cập Glop thông qua trình bao bọc trình giải tuyến tính OR-Tools, là trình bao bọc cho Glop.
Mô-đun tối ưu hóa tuyến tính cho Google Trang tính cho phép bạn thực hiện một tuyên bố tuyến tính của vấn đề tối ưu hóa bằng cách nhập dữ liệu vào bảng tính.
Lập trình bậc hai
Nền tảng Bộ giải cao cấp sử dụng phiên bản LP / bậc hai mở rộng của phương pháp Simplex với giới hạn xử lý vấn đề LP và QP lên đến 2000 biến quyết định.
SQP Solver cho các bài toán quy mô lớn sử dụng phương pháp tập hợp tích cực hiện đại với độ thưa thớt để giải các bài toán lập trình bậc hai (QP). Công cụ XPRESS Solver sử dụng phần mở rộng tự nhiên của "Điểm bên trong" hoặc phương pháp Rào cản Newton để giải các bài toán QP.
MOSEK Solver áp dụng phương pháp "Inside Point" được nhúng và phương pháp tự động kép. Điều này đặc biệt hiệu quả đối với các vấn đề QP được ghép nối lỏng lẻo. Nó cũng có thể giải quyết các vấn đề Ràng buộc quy mô bậc hai (QCP) và Lập trình hình nón bậc hai (SOCP).
Tính toán nhiều phép tính
Chúng được sử dụng khá thành công với việc sử dụng các tính năng của Microsoft Office, chẳng hạn như giải quyết các vấn đề tối ưu hóa trong Excel.
Trong bảng trên, các ký hiệu là:
- K1 - K6 - khách có nhu cầu cung cấp hàng.
- S1 - S6 là các địa điểm sản xuất tiềm năng có thể được xây dựng cho việc này. Có thể được tạo1, 2, 3, 4, 5 hoặc tất cả 6 vị trí.
Có chi phí cố định cho mỗi cơ sở được liệt kê trong cột I (Khắc phục).
Nếu địa điểm không thay đổi gì thì sẽ không được tính. Sau đó, sẽ không có chi phí cố định.
Xác định các vị trí tiềm năng để có chi phí thấp nhất.
Trong những điều kiện này, địa điểm có được thành lập hoặc không. Hai trạng thái này là: "TRUE - FALSE" hoặc "1 - 0". Có sáu trạng thái cho sáu vị trí, ví dụ: 000001 chỉ được đặt thành vị trí thứ sáu, 111111 được đặt thành tất cả.
Trong hệ thống số nhị phân, có chính xác 63 tùy chọn khác nhau từ 000001 (1) đến 111111 (63).
L2-L64 bây giờ sẽ đọc {=MULTIPLE OPERATION (K1)}, đây là kết quả của tất cả các giải pháp thay thế. Khi đó giá trị nhỏ nhất là=Min (L) và giá trị thay thế tương ứng là INDEX (K).
Lập trình số nguyên CPLEX
Đôi khi một mối quan hệ tuyến tính không đủ để đi đến trọng tâm của một vấn đề kinh doanh. Điều này đặc biệt đúng khi các quyết định liên quan đến các lựa chọn rời rạc, chẳng hạn như có mở một nhà kho ở một địa điểm nhất định hay không. Trong những trường hợp này, lập trình số nguyên phải được sử dụng.
Nếu vấn đề liên quan đến cả lựa chọn rời rạc và liên tục, thì đó là một chương trình số nguyên hỗn hợp. Nó có thể có các bài toán tuyến tính, bậc hai lồi và các ràng buộc bậc hai giống nhau.
Các chương trình số nguyên phức tạp hơn nhiều so với các chương trình tuyến tính, nhưng chúng có các ứng dụng kinh doanh quan trọng. Phần mềmPhần mềm CPLEX sử dụng các phương pháp toán học phức tạp để giải các bài toán số nguyên. Các phương pháp của ông liên quan đến việc tìm kiếm một cách có hệ thống các kết hợp có thể có của các biến rời rạc bằng cách sử dụng phần mềm tuyến tính hoặc phần mềm bậc hai để tính toán giới hạn về giá trị của giải pháp tối ưu.
Họ cũng sử dụng LP và các phương pháp giải quyết vấn đề tối ưu hóa khác để tính toán các ràng buộc.
Trình giải quyết Microsoft Excel tiêu chuẩn
Công nghệ này sử dụng cách triển khai cơ bản của phương pháp Simplex chính để giải quyết các vấn đề LP. Nó được giới hạn ở 200 biến. "Bộ giải đặc biệt" sử dụng phương pháp đơn giản chính được cải tiến với các giới hạn hai mặt cho các biến. Nền tảng Bộ giải cao cấp sử dụng phiên bản mở rộng của Bộ giải đơn giản LP / bậc hai để giải quyết vấn đề tối ưu hóa với tối đa 2000 biến quyết định.
LP quy mô lớn cho nền tảng Bộ giải cao cấp áp dụng cách triển khai hiện đại của phương pháp đơn giản kép và đơn giản kép, sử dụng độ thưa thớt trong mô hình LP để tiết kiệm thời gian và bộ nhớ, các chiến lược nâng cao để cập nhật và tái cấu trúc ma trận, định giá nhiều và từng phần và phép quay, và để khắc phục sự thoái hóa. Động cơ này có sẵn trong ba phiên bản (có khả năng xử lý tới 8.000, 32.000 hoặc không giới hạn các biến và giới hạn).
MOSEK Solver bao gồm đơn giản chính và đơn giản kép, một phương pháp cũng khai thác độ thưa thớt và sử dụng các chiến lược nâng cao để cập nhật ma trận và "tái cấu trúc hóa". Nó giải quyết các vấn đề về kích thước không giới hạn, đãđã thử nghiệm trên các bài toán lập trình tuyến tính với hàng triệu biến quyết định.
Ví dụ từng bước trong EXCEL
Để xác định mô hình vấn đề tối ưu hóa trong Excel, hãy thực hiện các bước sau:
- Sắp xếp dữ liệu cho vấn đề trong bảng tính ở dạng logic.
- Chọn một ô để lưu trữ từng biến.
- Tạo trong ô một công thức để tính toán mô hình toán học mục tiêu của bài toán tối ưu hóa.
- Tạo công thức để tính vế trái của mỗi ràng buộc.
- Sử dụng hộp thoại trong Excel để thông báo cho Bộ giải quyết về các biến quyết định, mục tiêu, ràng buộc và giới hạn mong muốn trên các tham số đó.
- Chạy "Solver" để tìm ra giải pháp tối ưu.
- Tạo trang tính Excel.
- Sắp xếp dữ liệu cho bài toán trong Excel nơi tính công thức cho hàm mục tiêu và ràng buộc.
Trong bảng trên, các ô B4, C4, D4 và E4 được dành riêng để đại diện cho các biến quyết định X 1, X 2, X 3 và X 4. Ví dụ về quyết định:
- Mô hình kết hợp sản phẩm ($ 450, $ 1150, $ 800 và $ 400 lợi nhuận trên mỗi sản phẩm) được nhập lần lượt vào các ô B5, C5, D5 và E5. Điều này cho phép tính mục tiêu trong F5=B5B4 + C5C4 + D5D4 + E5E4 hoặc F5:=SUMPRODUCT (B5: E5, B4: E4).
- Trong B8, nhập số lượng tài nguyên cần thiết để sản xuất từng loại sản phẩm.
- Công thức cho F8:=SUMPRODUCT (B8: E8, $ B $ 4: $ E $ 4).
- Sao chép cái nàycông thức trong F9. Ký hiệu đô la trong $ B $ 4: $ E $ 4 cho biết rằng phạm vi ô này không đổi.
- Trong G8, nhập số lượng tài nguyên hiện có của mỗi loại, tương ứng với các giá trị của các giới hạn ở bên phải. Điều này cho phép bạn diễn đạt chúng như thế này: F11<=G8: G11.
- Điều này tương đương với bốn giới hạn F8<=G8, F9 <=G9, F10 <=G10 và F11=0
Lĩnh vực ứng dụng thực tế của phương pháp
Tối ưu hóa tuyến tính có nhiều ứng dụng thực tế như một ví dụ về bài toán tối ưu hóa:
Một công ty có thể tạo ra một số sản phẩm với mức đóng góp đã biết. Việc sản xuất một đơn vị của mỗi mặt hàng đòi hỏi một lượng tài nguyên giới hạn đã biết. Nhiệm vụ là tạo ra một chương trình sản xuất để xác định số lượng mỗi sản phẩm nên được sản xuất để lợi nhuận của công ty là tối đa mà không vi phạm các hạn chế về nguồn lực.
Bài toán trộn là giải pháp cho các bài toán tối ưu hóa liên quan đến việc kết hợp các thành phần thành sản phẩm cuối cùng. Một ví dụ cho điều này là vấn đề về chế độ ăn uống được nghiên cứu bởi George Danzig vào năm 1947. Một số nguyên liệu thô được đưa ra như yến mạch, thịt lợn và dầu hướng dương cùng với hàm lượng dinh dưỡng của chúng như protein, chất béo, vitamin A và giá của chúng trên một kg. Thách thức là pha trộn một hoặc nhiều sản phẩm cuối cùng từ các nguyên liệu thô với chi phí thấp nhất có thể trong khi vẫn tôn trọng các giới hạn tối thiểu và tối đa cho giá trị dinh dưỡng của chúng.
Một ứng dụng cổ điển của bài toán tối ưu hóa tuyến tính là xác định định tuyến cho các nhu cầulưu lượng trong mạng viễn thông hoặc mạng giao thông. Đồng thời, các luồng phải được định tuyến qua mạng theo cách đáp ứng tất cả các yêu cầu về lưu lượng mà không vi phạm các điều kiện về băng thông.
Trong lý thuyết toán học, tối ưu hóa tuyến tính có thể được sử dụng để tính toán các chiến lược tối ưu trong trò chơi có tổng bằng không cho hai người. Trong trường hợp này, phân phối xác suất cho mỗi người tham gia được tính toán, là hệ số kết hợp ngẫu nhiên các chiến lược của họ.
Không có quy trình kinh doanh thành công nào trên thế giới có thể thực hiện được nếu không có sự tối ưu hóa. Có nhiều thuật toán tối ưu hóa có sẵn. Một số phương pháp chỉ phù hợp với một số dạng bài toán nhất định. Điều quan trọng là có thể nhận ra đặc điểm của chúng và lựa chọn phương pháp giải thích hợp.
