Đề bài

Xét bài toán quy hoạch tuyến tính

F(x; y) = 3x + 4y → min

với các ràng buộc

\(\left\{ \begin{array}{l}x \ge 0,y \ge 0\\x + 2y \ge 4\\x + y \ge 3\end{array} \right.\)

a) Kiểm tra lại rằng miền S tô màu trong Hình 2.6 là miền chấp nhận được của bài toán.

b) Tìm tập hợp các điểm M(x; y) thoả mãn

F(x; y) = 3x + 4y = 12.

c) Với mỗi số thực m, xét đường thẳng

d_m: 3x + 4y = m.

Từ hình vẽ, tìm điều kiện của m để d_m ∩ S ≠ ∅.

d) Từ phần c suy ra giá trị nhỏ nhất của F(x; y) trên miền chấp nhận được. Chứng tỏ rằng, giá trị nhỏ nhất này chính là giá trị của F(x; y) tại một điểm cực biên của miền chấp nhận được.

Phương pháp giải

Bài toán yêu cầu tìm giá trị nhỏ nhất của F(x; y) trên miền nghiệm của hệ bất phương trình trên. Vì miền chấp nhận được không là miền đa giác và có x ≥ 0, y ≥ 0 nên F(x; y) có giá trị nhỏ nhất trên S và đạt được tại một trong các điểm cực biên của miền chấp nhận được.

Lời giải của GV Loigiaihay.com

a) Ta thấy rằng miền S tô màu trong Hình 2.6 là miền chấp nhận được của bài toán.

b) Theo bài, F(x; y) = 3x + 4y = 12.

Vậy tập hợp điểm M(x; y) thỏa mãn yêu cầu đề bài là tập hợp các điểm nằm trên đường thẳng d: 3x + 4y = 12 nằm trong miền S.

b) Vì đường thẳng d_m song song với đường thẳng (d) nên đường thẳng d_m: 3x + 4y = m luôn cắt trục tung tại điểm có tung độ \(y = \frac{m}{4}\).

Để d_m ∩ S ≠ ∅ thì \(\frac{m}{4} \ge \frac{5}{2}\) hay m ≥ 10.

Vậy m ≥ 10.

c) Ta có: F(x; y) = 3x + 4y = m, mà theo kết quả của câu b, ta có m ≥ 10 nên F(x; y) ≥ 10.

Vậy giá trị nhỏ nhất của F(x; y) trên miền S là 10.

Ta có các điểm cực biên của miền S là: (0; 3), (2; 1), (4; 0).

⦁ F(0; 3) = 3.0 + 4.3 = 12;

⦁ F(2; 1) = 3.2 + 4.1 = 10;

⦁ F(4; 0) = 3.4 + 4.0 = 12.

Vậy giá trị nhỏ nhất của F(x; y) trên miền S chính là giá trị của F(x; y) tại điểm cực biên có tọa độ (2; 1) của miền chấp nhận được.