Tối ưu hóa lồi - Lập trình tuyến tính
Phương pháp luận
Lập trình tuyến tính còn được gọi là Tối ưu hóa tuyến tính, là một kỹ thuật được sử dụng để giải quyết các vấn đề toán học trong đó các mối quan hệ là tuyến tính. bản chất cơ bản của Lập trình tuyến tính là tối đa hóa hoặc giảm thiểuobjective function với chủ đề của một số constraints. Hàm mục tiêu là một hàm tuyến tính nhận được từ mô hình toán học của bài toán. Các ràng buộc là các điều kiện được áp dụng cho mô hình và cũng là tuyến tính.
- Từ câu hỏi đã cho, hãy tìm hàm mục tiêu.
- tìm các ràng buộc.
- Vẽ các ràng buộc trên đồ thị.
- tìm vùng khả thi, vùng này được hình thành bởi giao điểm của tất cả các ràng buộc.
- tìm các đỉnh của vùng khả thi.
- tìm giá trị của hàm mục tiêu tại các đỉnh này.
- Câu trả lời là cực đại hoặc cực tiểu của hàm mục tiêu (theo câu hỏi).
Ví dụ
Step 1 - Tối đa hóa $ 5x + 3y $ tùy theo
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: và \: y \ geq 0 $
Solution -
Bước đầu tiên là tìm vùng khả thi trên đồ thị.
Rõ ràng từ biểu đồ, các đỉnh của vùng khả thi là
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $
Cho $ f \ left (x, y \ right) = 5x + 3y $
Đặt các giá trị này vào hàm mục tiêu, chúng ta nhận được -
$ f \ left (0, 0 \ right) $ = 0
$ f \ left (0, 2 \ right) $ = 6
$ f \ left (1, 0 \ right) $ = 5
$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7
Do đó, hàm đạt cực đại tại $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Step 2- Một công ty đồng hồ sản xuất đồng hồ kỹ thuật số và đồng hồ cơ. Các dự báo dài hạn cho thấy nhu cầu dự kiến ít nhất 100 đồng hồ kỹ thuật số và 80 đồng hồ cơ mỗi ngày. Do hạn chế về năng lực sản xuất, không quá 200 đồng hồ kỹ thuật số và 170 đồng hồ cơ có thể được sản xuất hàng ngày. Để đáp ứng hợp đồng vận chuyển, tổng cộng ít nhất 200 chiếc đồng hồ được vận chuyển mỗi ngày.
Nếu mỗi chiếc đồng hồ kỹ thuật số được bán dẫn đến lỗ $ \ $ 2 $, nhưng mỗi chiếc đồng hồ cơ khí lại tạo ra lợi nhuận $ \ $ 5 $, thì nên sản xuất bao nhiêu loại mỗi loại hàng ngày để tối đa hóa lợi nhuận ròng?
Solution -
Gọi $ x $ là số lượng đồng hồ kỹ thuật số được sản xuất
$ y $ là số lượng đồng hồ cơ được sản xuất
Theo câu hỏi, ít nhất 100 đồng hồ kỹ thuật số sẽ được sản xuất hàng ngày và tối đa 200 đồng hồ kỹ thuật số có thể được sản xuất.
$ \ Rightarrow 100 \ leq \: x \ leq 200 $
Tương tự, ít nhất 80 đồng hồ cơ phải được sản xuất hàng ngày và tối đa 170 đồng hồ cơ có thể được sản xuất.
$ \ Rightarrow 80 \ leq \: y \ leq 170 $
Vì có ít nhất 200 chiếc đồng hồ được sản xuất mỗi ngày.
$ \ Mũi tên phải x + y \ leq 200 $
Vì mỗi chiếc đồng hồ kỹ thuật số được bán dẫn đến khoản lỗ $ \ $ 2 $, nhưng mỗi chiếc đồng hồ cơ khí lại tạo ra lợi nhuận $ \ $ 5 $,
Tổng lợi nhuận có thể được tính là
$ Lợi nhuận = -2x + 5y $
Và chúng tôi phải tối đa hóa lợi nhuận, Do đó, câu hỏi có thể được hình thành như:
Tối đa hóa $ -2x + 5y $ tùy theo
$ 100 \: \ leq x \: \ leq 200 $
$ 80 \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
Vẽ các phương trình trên dưới dạng đồ thị, chúng ta nhận được,
Các đỉnh của vùng khả thi là
$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) và \ left (100, 100 \ right) $
Giá trị lớn nhất của hàm mục tiêu nhận được là $ \ left (100, 170 \ right) $ Do đó, để tối đa hóa lợi nhuận ròng, cần sản xuất 100 đơn vị đồng hồ kỹ thuật số và 170 đơn vị đồng hồ cơ.