Bài Toán Tối Ưu: Khái Niệm và Ứng Dụng trong Kỹ Thuật và Kinh Tế

Tối ưu hóa giáo trình giúp nâng cao hiệu quả giảng dạy, cải thiện trải nghiệm học tập và đáp ứng nhu cầu của người học trong môi trường hiện đại.

• Đề tài: Bài Toán Tối Ưu và Ứng Dụng trong Kỹ Thuật và Kinh Tế

Mục lục chi tiết

• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. §1. Đối tượng nghiên cứu
• 1.1.1. Vài nét khái quát
• 1.1.2. Bài toán tối ưu tổng quát
• 1.1.3. Phân loại các bài toán tối ưu
• 1.1.4. Nội dung nghiên cứu
• 1.2. §2. Cơ sở giải tích lồi
• 1.2.1. Không gian tuyến tính n chiều Rⁿ
• 1.2.2. Đường thẳng, đoạn thẳng và siêu phẳng
• 1.2.2.1. Đường thẳng, đoạn thẳng
• 1.2.2.2. Siêu phẳng
• 1.2.3. Tập hợp lồi
• 1.2.3.1. Điểm cực biên
• 1.2.3.2. Bao lồi
• 1.2.3.3. Tập hợp lồi đa diện hay khúc lồi
• 1.2.4. Hàm tuyến tính và hàm tuyến tính afin
• 1.2.5. Hàm lồi và hàm lõm
• 1.3. Bài tập
• 2. CHƯƠNG 2: QUI HOẠCH TUYẾN TÍNH
• 2.1. §1. Một số ví dụ về bài toán qui hoạch tuyến tính
• 2.1.1. Bài toán lập kế hoạch sản xuất
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC

Tóm tắt

I. Bài Toán Tối Ưu Là Gì Tổng Quan Toàn Diện Cho Người Mới

Bài toán tối ưu là một nhánh cốt lõi của toán học ứng dụng, tập trung vào việc tìm kiếm giá trị tốt nhất (cực tiểu hoặc cực đại) của một hàm số trong một tập hợp các lựa chọn khả thi. Theo định nghĩa trong giáo trình "Tối Ưu Hóa" của GS. Trần Vũ Thiệu, đây là "bài toán tìm giá trị cực tiểu (hay cực đại) của một hàm số phụ thuộc nhiều biến số trên tập hợp các biến số thỏa mãn những điều kiện nhất định". Quá trình này bắt đầu bằng việc mô hình hóa toán học, chuyển đổi một vấn đề thực tế thành một cấu trúc toán học chặt chẽ. Mô hình này bao gồm ba thành phần chính: hàm mục tiêu đại diện cho đại lượng cần tối ưu (ví dụ: lợi nhuận, chi phí), các biến quyết định là những yếu tố có thể kiểm soát, và các điều kiện ràng buộc thể hiện những giới hạn về nguồn lực, kỹ thuật hoặc chính sách. Tầm quan trọng của tối ưu hóa không chỉ giới hạn trong lý thuyết mà còn có ứng dụng sâu rộng trong kỹ thuật, kinh tế, và quản lý, giúp đưa ra các quyết định hiệu quả nhất dựa trên dữ liệu và các giới hạn cho trước. Việc hiểu rõ bản chất và các thành phần của bài toán tối ưu là bước đầu tiên và quan trọng nhất để áp dụng thành công các phương pháp giải quyết trong thực tiễn.

1.1. Khám phá mô hình hóa toán học trong tối ưu hóa

Mô hình hóa toán học là quá trình biểu diễn một vấn đề thực tế dưới dạng các phương trình và bất phương trình. Mục tiêu là xây dựng một mô hình trừu tượng nhưng vẫn phản ánh chính xác các yếu tố quan trọng của hệ thống. Một mô hình tối ưu hóa điển hình có dạng tổng quát: Tìm x = (x₁, x₂, ..., xₙ) để tối ưu hàm f(x) với các điều kiện gᵢ(x) ≤ 0 và hⱼ(x) = 0. Việc xây dựng mô hình đòi hỏi phải xác định rõ ràng các yếu tố đầu vào, các quyết định cần đưa ra và mục tiêu cần đạt được. Chẳng hạn, trong phân bổ nguồn lực, mô hình phải thể hiện được lượng tài nguyên có hạn và cách chúng được sử dụng để tối đa hóa lợi nhuận hoặc sản lượng. Độ chính xác của mô hình quyết định trực tiếp đến chất lượng của lời giải, do đó, đây là giai đoạn đòi hỏi sự kết hợp giữa kiến thức chuyên môn và kỹ năng toán học.

1.2. Các thành phần cốt lõi hàm mục tiêu và biến quyết định

Mọi bài toán tối ưu đều xoay quanh ba thành phần cơ bản. Thứ nhất là hàm mục tiêu (f(x)), một hàm toán học biểu thị đại lượng cần tối ưu. Ví dụ, trong kinh doanh, hàm mục tiêu có thể là tổng lợi nhuận cần tối đa hóa hoặc tổng chi phí sản xuất cần tối thiểu hóa chi phí. Thứ hai là các biến quyết định (x₁, x₂, ..., xₙ), đại diện cho các lựa chọn hoặc quyết định cần được đưa ra. Trong bài toán sản xuất, biến quyết định có thể là số lượng sản phẩm mỗi loại cần sản xuất. Cuối cùng là các điều kiện ràng buộc, là các phương trình hoặc bất phương trình mô tả các giới hạn của bài toán, chẳng hạn như ngân sách, nguồn nhân lực, hay công suất máy móc. Các ràng buộc này xác định một không gian các giải pháp khả thi, được gọi là miền chấp nhận được. Lời giải tối ưu chính là điểm trong miền này làm cho hàm mục tiêu đạt giá trị tốt nhất.

1.3. Phân loại các bài toán tối ưu hóa phổ biến nhất hiện nay

Các bài toán tối ưu được phân loại dựa trên đặc tính của hàm mục tiêu và các hàm ràng buộc. Loại phổ biến và được nghiên cứu kỹ lưỡng nhất là Quy hoạch tuyến tính, trong đó cả hàm mục tiêu và các ràng buộc đều là hàm tuyến tính. Ngược lại, nếu có ít nhất một trong các hàm này không phải tuyến tính, ta có bài toán Quy hoạch phi tuyến. Các lớp bài toán quan trọng khác bao gồm Quy hoạch lồi (hàm mục tiêu lồi và miền ràng buộc lồi), Quy hoạch rời rạc (biến quyết định chỉ nhận giá trị rời rạc, ví dụ như số nguyên), và lập trình động (áp dụng cho các bài toán có cấu trúc đa giai đoạn). Mỗi loại bài toán đòi hỏi một phương pháp giải quyết riêng, từ thuật toán Simplex cho quy hoạch tuyến tính đến các phương pháp lặp số hay thuật toán heuristic như thuật toán di truyền cho các bài toán phức tạp hơn (Trần Vũ Thiệu & Võ Văn Tuấn Dũng, 2003).

II. Top các phương pháp giải bài toán tối ưu hiệu quả nhất

Việc lựa chọn phương pháp giải quyết phụ thuộc hoàn toàn vào cấu trúc của bài toán tối ưu. Đối với lớp bài toán quy hoạch tuyến tính, thuật toán Simplex (hay phương pháp đơn hình) do George Dantzig phát triển năm 1947 vẫn là công cụ nền tảng và hiệu quả nhất. Thuật toán này hoạt động bằng cách di chuyển dọc theo các đỉnh của miền ràng buộc đa diện để tìm ra đỉnh tối ưu. Ưu điểm của nó là đảm bảo tìm được lời giải tối ưu toàn cục nếu tồn tại. Tuy nhiên, khi đối mặt với các bài toán tối ưu có hàm mục tiêu hoặc ràng buộc phi tuyến, các phương pháp phức tạp hơn là cần thiết. Các phương pháp dựa trên gradient (như Gradient Descent) được sử dụng để tìm cực tiểu địa phương trong quy hoạch phi tuyến. Đối với các bài toán có không gian tìm kiếm phức tạp, rời rạc hoặc đa cực trị, các thuật toán heuristic và metaheuristic như thuật toán di truyền và lập trình động lại tỏ ra vượt trội. Những thuật toán này không đảm bảo tìm ra lời giải tối ưu tuyệt đối nhưng có khả năng đưa ra các giải pháp đủ tốt trong thời gian hợp lý, đặc biệt cho các bài toán tối ưu hóa tổ hợp quy mô lớn.

2.1. Hướng dẫn giải bài toán tối ưu với thuật toán Simplex

Thuật toán Simplex là phương pháp lặp kinh điển để giải bài toán quy hoạch tuyến tính. Ý tưởng cơ bản của nó là bắt đầu từ một phương án cực biên (một đỉnh của miền ràng buộc) và lặp đi lặp lại việc di chuyển đến một đỉnh kề cận có giá trị hàm mục tiêu tốt hơn. Quá trình này tiếp diễn cho đến khi không thể cải thiện thêm giá trị hàm mục tiêu, lúc đó phương án cực biên hiện tại chính là lời giải tối ưu. Mỗi bước lặp bao gồm việc xác định biến nào sẽ được đưa vào cơ sở (cột quay) và biến nào sẽ bị loại ra khỏi cơ sở (dòng quay) thông qua bảng đơn hình. Các công cụ phần mềm hiện đại như các thư viện Python cho tối ưu hóa (PuLP, SciPy) hay MATLAB optimization toolbox đã tự động hóa hoàn toàn quá trình này, cho phép giải quyết các bài toán quy mô hàng nghìn biến và ràng buộc một cách nhanh chóng.

2.2. Khám phá quy hoạch phi tuyến và các thuật toán liên quan

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. Các bài toán này thường khó giải hơn đáng kể vì lời giải tối ưu có thể nằm ở bất kỳ đâu trong miền ràng buộc, không nhất thiết phải ở các đỉnh. Các phương pháp giải thường dựa trên giải tích, sử dụng thông tin về đạo hàm (gradient) và ma trận Hessian để tìm hướng di chuyển nhằm cải thiện hàm mục tiêu. Các thuật toán phổ biến bao gồm Gradient Descent, phương pháp Newton, và các phương pháp vùng tin cậy (Trust-Region methods). Tuy nhiên, các thuật toán này thường chỉ hội tụ về một cực tiểu địa phương. Để tìm kiếm tối ưu toàn cục trong các bài toán quy hoạch phi tuyến phức tạp, người ta thường phải kết hợp chúng với các kỹ thuật tìm kiếm toàn cục hoặc các phương pháp heuristic.

2.3. Lập trình động và thuật toán di truyền cho vấn đề phức tạp

Đối với những bài toán tối ưu có thể chia thành các bài toán con gối nhau và có cấu trúc tối ưu con, lập trình động là một kỹ thuật cực kỳ mạnh mẽ. Nguyên lý của nó là giải các bài toán con một lần và lưu trữ kết quả để tái sử dụng, tránh tính toán lại. Kỹ thuật này đặc biệt hiệu quả cho các bài toán chuỗi, bài toán cái túi, hay quy hoạch sản xuất đa giai đoạn. Mặt khác, thuật toán di truyền là một phương pháp heuristic lấy cảm hứng từ quá trình tiến hóa tự nhiên. Nó hoạt động trên một quần thể các giải pháp, áp dụng các toán tử lai ghép và đột biến để tạo ra các thế hệ giải pháp mới ngày càng tốt hơn. Thuật toán di truyền không yêu cầu thông tin về đạo hàm và có khả năng thoát khỏi các cực tiểu địa phương, làm cho nó trở thành một công cụ linh hoạt để giải quyết các bài toán tối ưu hóa tổ hợp và phi tuyến khó khăn.

III. Ứng dụng bài toán tối ưu hóa trong kỹ thuật và kinh tế

Ứng dụng của bài toán tối ưu trải rộng trên nhiều lĩnh vực, đặc biệt là trong kỹ thuật và kinh tế, nơi việc sử dụng hiệu quả nguồn lực là yếu tố sống còn. Trong kinh tế, các doanh nghiệp sử dụng tối ưu hóa để giải quyết các bài toán kinh điển như tối đa hóa lợi nhuận và tối thiểu hóa chi phí. Ví dụ, một công ty có thể xây dựng một mô hình quy hoạch tuyến tính để xác định kế hoạch sản xuất tối ưu, quyết định số lượng mỗi sản phẩm cần sản xuất để đạt lợi nhuận cao nhất dưới các ràng buộc về nguyên vật liệu và giờ công lao động. Trong lĩnh vực tài chính, tối ưu hóa danh mục đầu tư là một ứng dụng quan trọng, giúp các nhà đầu tư lựa chọn cách phân bổ vốn vào các tài sản khác nhau để tối đa hóa lợi nhuận kỳ vọng trong khi kiểm soát rủi ro ở một mức độ chấp nhận được. Tương tự, trong lĩnh vực kỹ thuật, điều khiển tối ưu được sử dụng để thiết kế các hệ thống điều khiển tự động, từ quỹ đạo của tàu vũ trụ đến quy trình vận hành của một nhà máy hóa chất, nhằm đạt được hiệu suất cao nhất với chi phí năng lượng thấp nhất. Các mô hình này đều dựa trên việc xác định một hàm mục tiêu rõ ràng và các điều kiện ràng buộc chính xác.

3.1. Tối ưu hóa chuỗi cung ứng và logistics hiệu quả

Quản lý chuỗi cung ứng và logistics là một trong những lĩnh vực ứng dụng tối ưu hóa thành công nhất. Các công ty phải đối mặt với các quyết định phức tạp như xác định vị trí nhà kho, quản lý mức tồn kho, và lập kế hoạch tuyến đường vận chuyển. 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, nhằm tìm ra kế hoạch vận chuyển hàng hóa từ nhiều nguồn đến nhiều đích sao cho tổng chi phí là thấp nhất. Các mô hình tối ưu hóa logistics còn có thể giải quyết các vấn đề phức tạp hơn như bài toán người giao hàng (Traveling Salesperson Problem), giúp giảm thiểu quãng đường di chuyển và tiết kiệm thời gian, nhiên liệu. Việc áp dụng các thuật toán tối ưu hóa giúp các doanh nghiệp cắt giảm chi phí vận hành, cải thiện tốc độ giao hàng và nâng cao sự hài lòng của khách hàng.

3.2. Cách tối đa hóa lợi nhuận qua phân bổ nguồn lực

Mọi tổ chức đều hoạt động với nguồn lực hữu hạn, bao gồm vốn, nhân sự, máy móc và thời gian. Bài toán phân bổ nguồn lực là việc quyết định cách sử dụng các nguồn lực này một cách hiệu quả nhất để đạt được mục tiêu đề ra. Mục tiêu này thường là tối đa hóa lợi nhuận hoặc giá trị sản phẩm. Ví dụ, một nhà máy cần quyết định phân bổ giờ máy cho các dây chuyền sản xuất khác nhau, hay một công ty marketing cần phân bổ ngân sách quảng cáo cho các kênh truyền thông khác nhau. Bằng cách sử dụng các mô hình tối ưu hóa, các nhà quản lý có thể đưa ra quyết định dựa trên dữ liệu thay vì trực giác, đảm bảo rằng mỗi đơn vị tài nguyên được sử dụng ở nơi nó tạo ra giá trị lớn nhất, từ đó cải thiện đáng kể hiệu quả hoạt động và khả năng cạnh tranh của doanh nghiệp.

3.3. Tối ưu hóa danh mục đầu tư và quản lý rủi ro tài chính

Trong tài chính, lý thuyết danh mục đầu tư hiện đại của Markowitz là một ứng dụng kinh điển của quy hoạch phi tuyến (cụ thể là quy hoạch toàn phương). Bài toán tối ưu hóa danh mục đầu tư tìm cách xác định tỷ trọng phân bổ vốn vào các loại tài sản khác nhau (cổ phiếu, trái phiếu, v.v.) sao cho đạt được một mức lợi nhuận kỳ vọng nhất định với mức độ rủi ro (thường đo bằng phương sai) là thấp nhất. Mô hình này giúp các nhà đầu tư xây dựng các danh mục đa dạng hóa, tránh việc đặt tất cả trứng vào một giỏ. Các mô hình kinh tế lượng và tối ưu hóa cũng được sử dụng trong quản lý rủi ro, định giá các công cụ tài chính phái sinh, và lập kế hoạch tài chính dài hạn, đóng vai trò trung tâm trong hoạt động của các ngân hàng và quỹ đầu tư hiện đại.

IV. Tương lai của bài toán tối ưu Xu hướng và thách thức mới

Lĩnh vực tối ưu hóa đang liên tục phát triển, được thúc đẩy bởi sự gia tăng của dữ liệu lớn (Big Data) và sức mạnh tính toán. Một trong những xu hướng nổi bật nhất là sự hội tụ giữa tối ưu hóa và học máy (Machine Learning). Nhiều thuật toán học máy, chẳng hạn như mạng nơ-ron và máy vector hỗ trợ (SVM), về bản chất là các bài toán tối ưu nhằm tìm ra các tham số mô hình để tối thiểu hóa chi phí lỗi dự đoán. Ngược lại, các kỹ thuật tối ưu hóa cũng được sử dụng để cải thiện hiệu suất của các mô hình học máy. Một hướng đi khác là giải quyết các bài toán tối ưu hóa tổ hợp quy mô cực lớn, vốn là thách thức lớn đối với các thuật toán truyền thống. Sự phát triển của máy tính lượng tử cũng hứa hẹn mang lại những đột phá trong việc giải quyết một số lớp bài toán tối ưu nhất định, mở ra những khả năng ứng dụng chưa từng có. Tuy nhiên, các thách thức vẫn còn đó, bao gồm việc xử lý sự không chắc chắn trong dữ liệu (tối ưu hóa ngẫu nhiên và bền vững) và phát triển các thuật toán có thể đưa ra quyết định tối ưu trong thời gian thực.

4.1. Sự kết hợp mạnh mẽ giữa tối ưu hóa và học máy

Sự giao thoa giữa tối ưu hóa và học máy đang tạo ra một lĩnh vực nghiên cứu năng động. Các thuật toán tối ưu hóa, đặc biệt là các biến thể của Gradient Descent, là xương sống của việc huấn luyện các mô hình học sâu (Deep Learning). Đồng thời, 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 các bài toán tối ưu. Ví dụ, một mô hình dự báo nhu cầu có thể cung cấp dữ liệu cho một mô hình tối ưu hóa chuỗi cung ứng để lập kế hoạch sản xuất và tồn kho. Sự kết hợp này cho phép tạo ra các hệ thống ra quyết định thông minh hơn, có khả năng học hỏi từ dữ liệu và tự động điều chỉnh để thích ứng với các điều kiện thay đổi, vượt qua giới hạn của các mô hình vận trù học truyền thống.

4.2. Thách thức tính toán trong tối ưu hóa tổ hợp quy mô lớn

Tối ưu hóa tổ hợp liên quan đến việc tìm kiếm một đối tượng tối ưu từ một tập hợp các đối tượng hữu hạn nhưng rất lớn, ví dụ như tìm đường đi ngắn nhất qua tất cả các thành phố. Khi quy mô bài toán tăng lên, số lượng giải pháp khả thi bùng nổ theo cấp số nhân, khiến việc tìm kiếm lời giải tối ưu tuyệt đối trở nên bất khả thi về mặt tính toán (NP-hard). Thách thức hiện nay là phát triển các thuật toán xấp xỉ và heuristic hiệu quả hơn, có thể tìm ra các giải pháp gần tối ưu trong thời gian hợp lý. Việc tận dụng kiến trúc tính toán song song và điện toán đám mây là chìa khóa để giải quyết các bài toán tối ưu hóa tổ hợp trong thực tế, từ lập lịch trình cho hãng hàng không đến thiết kế vi mạch.

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

Mở đầu 3. Chứng minh rằng các tập hợp sau đây là các tập hợp lôi: a) A={(Xi,X¿) € R? : xp > ax; +b, abeR} b) B= { (x1, x2) € R?: x2 2ax)? (a>0)} c) C={(xi,x;)€ R?: x? +x’ < 1} | 4. Chứng tỏ K = { (x1, x2) € R?: x2 <ax;? (a> 0) } không phải là tập hợp lỗi. Biểu diễn trọng tâm của tam giác ABC dưới dạng tổ hợp lỗi của các đỉnh A, B, C.

wn Xét trường hợp các dinh cé toa dé: A = (-1, -1), B= q, 3),C = ,]). Vẽ miền thoả mãn các bắt phương trình tuyến tính (bậc nhất) sau: - 2x, + 5x2 $ 10, -Xi†3x¿<3, 2xi†xạ< 6, x) +2x222. Chỉ rõ các điểm cực biên (đỉnh) của miền nảy. Chứng minh rằng một tổ hợp tuyến tính không â âm bất kỳ của các hàm lỗi là một hàm lồi.

Hãy xác định xem các hàm sau đây có phải là ham lồi ‘hay không? a) |x| với mọi x e R. e) log x voi 0 <x <+too. Cho f(x) là một hàm lỗi trên một tập hợp lồi C khác rỗng trong R". Chứng minh rằng tập hợp các điểm (x,t) e R"xR sao cho x e C vàt> f(x) là một tập hợp lôi: 10.

Cho A là ma trân mxn, b e R”. Chứng minh rằng tập hop sau đây là lỗi: D={xeR":Ax=b,x20} | : (D là tập hợp các phương án của bài toán qui hoạch tuyến tính dạng chính tắc)., m, la cdc ham 14i, h;i(X), j =1,., p, là các hàm tuyến tính afn, x € R", Chimg minh ring tập hợp sau đây là lôi: M={xeR': g(x) <0,1=1,. Chương 2 -- Qui hoach tuyén tinh Chương2 : QUI HOẠCH TUYỂN TÍNH. Qui hoạch tuyến tính (Linear Programming) khai sinh lịch sử phát triển của mình từ năm 1939, khi nhà toán học Nga nổi tiếng, Viện sĩ L.

Kantorovich dé xuất những thuật toán đầu tiên để giải nó trong một loạt công trình nghiên cứu về kế hoạch hoá sản xuất, và nó thực sự phát triển mạnh mẽ kể từ khi nhà toán học Mỹ G. Dantzig để xuất phương pháp đơn hình (simplex method) gidi qui hoạch tuyến tinh vào năm 1947 dễ giải các bài toán xuất phát từ việc lập kế hoạch cho không quân Mỹ. Vậy có thể nói là, cũng như phép tính vi tích phân hình thành vào thế kỷ 17 từ việc giải các bài toán cơ học, qui hoạch lu tính hình thành vào giữa thế kỷ 20 do nhụ câu của các bài toán quản lý. Qui hoạch tuyến | tính ngay từ khi ra dời đã chiếm một vị trí hết sức quan trọng trong tối ưu hoa.

Trude hết mô hình tuyến tính là mô hình rất phổ biến trong thục tế, vì tính đơn giản dễ hiểu của no. Mặt khác, về mặt ly thuyết, có thể xếp xỉ với độ chính xác cao các bài toán tối ưu phi tuyến bởi dãy các bài toán qui hoạch tuyến tính. MỘT SÓ VÍ DỤ VỀ BÀI TOÁN QUI HOẠCH TUYẾN TÍNH Ö1,1. Bài toán lập kế hoạch sản xuất ! _ Một xi nghiệp dự định sản xuất hai loại sản phẩm là S¡ và S;.

Để làm được một đơn vị S¡ cần 4 đơn vị vật liệu Vị, 5 đơn vị vật liệu Vạ. Để làm được 1 đơn vị S; cần 3 đơn vị Vị, 2 đơn vị V+„. Giá bán một đơn vị 5¡ là 50 ngàn đồng, một đơn vị 5; là 30 ngàn đồng. Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm S¡ và §; dé tông thu nhập là lớn nhất, biết rằng xí nghiệp chỉ có 1.200 đơn vị vật liệu Vị và 1.080 đơn vị vật liéu V2.

Chi phi San pham. vật liệu S, S; Vật liệu Vị : 1.080 - 5 2 Giá bán 1 đơn vị SP 50.000 d Mô hình toán học. Gọi x1, x2 lần lượt là số đơn vị sản phẩm S¡, S; cần sản xuất. Số đơn vị vật liệu Vì cần có là 4xị + 3x;.

Do xí nghiệp chỉ có 1.200 đcn vị vật liệu Vị nên xị và xạ phải thỏa mãn 4x, + 3x2 $ 1. _— Tương tự, số đơn vị vật liệu Vạ cân có là 5x;+ 2x¿, vì thể xị và xạ phải thoả mãn 5x, + 2x2 S$ 1. Tắt nhiên ta còn phải có x; 2 0 va x2 2 0. Chương 2 - Qui hoạch tuyển tính Tổng thu nhập của xí nghiệp (cần làm cực đại) sẽ là f= 50xị + 30x; (ngàn đồng).

Vậy bài toán đặt ra được phát biểu thành: Tìm các biến số x; va x2 sao cho f = 50x; + 30x. —> max, với các điều kiện 4x, + 3x¿< “1. Bài toán xác định khẩu phần thức ăn Một xí nghiệp chăn nuôi cần mua hai loại thức ăn tông hợp Tì, Ta cho gia súc với ti lệ chế biến: 1 kg T¡ chứa 3 đơn vị đinh dưỡng Dị (chất béo), ! đơn vị dinh dưỡng D; (Hydrat cacbon) va | don vị dinh dưỡng D; (Protein); ! kg T› chứa 1 đơn vị Dị, 1 don vị D2 va 2 don vi D3. Méi bữa ăn cho gia súc cần tối thiểu 60 đơn vị Dị, 40 đơn vị Dạ và 60 đơn vị Dạ.

Hỏi xí nghiệp cần mua bao nhiêu kg T1,:T2 cho mỗi bữa ăn, sao cho vừa đảm bảo tốt đinh dưỡng cho bữa ăn của gia súc, vừa để tổng số tiền chỉ mua thức ăn là nhỏ nhất. Cho biết kg T¡ giá 20 ngàn đồng, 1 kg T; giá 15 ngàn đồng. , £ Mức Các loại thức ăn Các chả Í tái tập T | T; Dị 60 `3 l D2 40 1 1 Da 60 I 2 Gia 1 kg 20 ngan | 15 ngan thức ăn Mô hình toán học. Gọi xị, X2 lần lượt là số kg thức ăn Tì\, Tạ cần mua cho mỗi 'bữa ăn.

Số đơn vị chất Dị có trong mỗi bữa ăn là 3xị + xạ, vì thế XỊ Và X¿ cần thỏa mãn 3x, + x2 2 60, Tương tự, dé dap tmg nhu cầu về chất D; và Dạ cho mỗi bữa ăn, xị và xạ cần thỏa mãn xị † x2 2 40, „ X, + 2x2 2 60, Tât nhiên, ta cũng đòi hỏi X, 20 va x22 0. Số tiên chỉ mua thức ăn (cần làm cực tiểu) bằng f = 20x + 15x; (ngàn đồng). Vậy bài toán nêu trên được phát biểu thành: Tìm các biến số xị và xạ sao chỏ f=20x; + 15x. — min, Chương 2 - Qui hoạch tuyển tính với các điều kiện -34xị +.

Bài toán vận ti Cần vận chuyển xi măng từ 3 kho Ki, Kạ, K¿ tới 4 công trường xây dung Ti, To, Ts, Tạ. Cho biết lượng xi măng có ở mỗi kho, lượng xi măng cần ỏ mỗi công trường và giá. cước vận chuyên (ngàn đồng) một tắn xi măng từ mỗi kho tới mỗi công trường như sau : Công trường xây dựng Kho xi măng T¡ : 130 tấn T¿ : 160 tấn Tạ : 120 tấn Ta : 140 tấn Kị : 170 tấn 20 18 22 25 K¿ : 200 tấn 15 25 30 l5. Ky: 180 tan 45 30 40 35 Vấn đẻ Tà tìm kế hoạch vận chuyển xi măng từ các kho tới các công trường sao cho mọi kho phát hết lượng xỉ măng có, mọi công trường nhận đủ lượng xi măng cần và tổng chỉ phí vận chuyển là nhỏ nhất? Vân đề nêu trên có thể mô hình hoá như sau: Dat x; 1a luong xi mang can van chuyén tir kho K; (i = 1, 2, 3) tới công trường T; ( = 1, 2, 3, 4).

| Các biến số cần thoả mãn các điều kiện sau: Xyp + X12 + X13 + X14 = 170 (kho Ky giao hét lượng xi măng có), X21 + X92 + X23 + X24 = 200 (kho K2 giao hết lượng xi măng có), X31 + X32 + X33 + X34 = 180 (kho Kạ giao hết lượng xỉ măng có), "XI + Xại † Xại = 130 (công trường Tì nhận đủ số xỈ măng cần),. cho hàm Vậy bài toán trở thành : Tìm các biến số xị thỏa mãn các điều kiện (1.3) sao f đạt cực tiêu (f —> min). Chương 2 — Qui hoạch tuyển tính 1. Bài toán pha cắt vật liệu Trong thực tế ta thường phải cắt những vật liệu dài (thanh thép,ôống nước, băng giấy .) có độ dài cho trước thành những đoạn ngăn hơn với số lượng nhất định để sử dụng.

Nên cắt như rhế nào cho tốn ít vật liệu nhất ? Ví dụ: một phân xưởng cốt thép có những thanh thép nguyên dài 3,8 mét,-cần cắt thành ba loại đoạn ngắn hơn T¡, Tạ, T; với độ dài tương ứng 1,8 mét, 1,4 mét và 1,0 mét. Có tắt cả 5 mẫu cắt khác nhau (xem bảng dưới đây). Hỏi cần phải cắt theo mỗi mẫu bao nhiêu thanh thép nguyên để vừa có đủ số lượng các đoạn Tì, Tạ, T› zaà phân xưởng cần, vừa sao cho tổngphan thép thừa là nhỏ nhất? Loại đoạn cần _Mẫu cắt Số đoạn cần có I I II IV Vv T¡ dài 1,8™ 2 0 1 | 1 400 T; dài 1,4" 0 2 0 +0 ¬ 400 T: dài 1,0” 0 1 2 3 01 1.300 Phan thừa 0,2" | 0 0 | 0,8" | 0,6™ Mô hình toán học., 5) la sé thanh thép nguyén cần cắt theo mẫu j. Số đoạn Tị¡ thu được 1a 2x, + x3 + xs.

Phan xưởng cần có 400 đoạn Tị. Vì thể, các biến số phải thỏa mãn " 2x; + x3 †+ x; = 400. Tương tự, để thu được số đoạn T; và T› phân xưởng cần, các biến số phải thoả mãn 2x2 + xs = 400, X2 + 2x3 + 3xq = 1. Tổng số thép thừa bằng f = 0,2 x; + 0,8 x4 + 0,6 x; (mét).

Bài toán trên sẽ được phat biểu thành: Tìm các biến số XỊ, Xa, X3, X4, Xs sao cho f=0,2xị + 0,8x¿ + 0,6x; —> min, với các điều kiện { 2x, + Xã +x5= 400,. Chương 2 ~ Qui hoạch tuyến tính §2. CÁC DẠNG BÀI TOÁN QUI HOẠCH TUYÉN TÍNH Qui hoạch tuyển tính là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính f(x) trên một khúc lỗi D c R” được xác định bởi một hệ các phương trình và/hoặc bất phương trình tuyến tính cho trước. Bài toán tong quat ` ` ` ,.

Bài toán này có dạng: Tìm các biên số xị, Xạ,., Xa sao cho: f(x) = 5 "c,x, — min (hay max) : (2.1) /= - : thỏa mãn điều kiện 7 Đ;a,x, < b,i=],.2) jal ya, xx,> b,i=mị + I. nị, xị <0, j = nị + l„.5) ° Trong bài toán trên, f gọi là hàm mục tiêu, mỗi hệ thức ở (2. 5) gọi là một rằng buộc. Mỗi ràng buộc (2.4) gọi là một ràng buộc chính (dạng đẳng thức hay bắt đẳng thức), mỗi rằng buộc x¡ > 0 hay xị < 0 gọi là một ràng buộc về dấu., Xa) € R" thỏa mãn mọi ràng buộc gọi là một điểm chấp nhận được, hay một phương án.