Chuyên đề học tập Toán 12

Giải Hoạt động 3 trang 29 Chuyên đề Toán 12

3. Bài toán quy hoạch tuyến tính với miền chấp nhận được không là miền đa giác   Đã kiểm chéo

Đề bài

Xét bài toán quy hoạch tuyến tính
F(x;y)=3x+4y→min⁡F(x;y) = 3x + 4y \to \min
với các ràng buộc
{x≥0,y≥0x+2y≥4x+y≥3.\begin{cases} x \ge 0, y \ge 0 \\ x + 2y \ge 4 \\ x + y \ge 3. \end{cases}
a) Kiểm tra lại rằng miền SS 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)M(x;y) thoả mãn F(x;y)=3x+4y=12F(x;y) = 3x + 4y = 12.

c) Với mỗi số thực mm, xét đường thẳng dm:3x+4y=md_m : 3x + 4y = m. Từ hình vẽ, tìm điều kiện của mm để dm∩S≠∅d_m \cap S \ne \varnothing.

d) Từ phần c suy ra giá trị nhỏ nhất của F(x;y)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)F(x;y) tại một điểm cực biên của miền chấp nhận được.

Bài có hình vẽ / bảng trong sách — xem ở trang 29 · mở sách.
Hình trong bài (mô tả bằng lời):

Hình 2.6: Hệ trục toạ độ Oxy. Miền SS (tô màu hồng) là miền chấp nhận được, không bị chặn, nằm phía trên các đường ràng buộc. Đường thẳng d10:x+2y=4d_{10}: x + 2y = 4 cắt trục Oy tại điểm (0;2)(0; 2) (ghi 52\frac{5}{2} tại vị trí 2 trên trục y, thực chất đường cắt Oy tại y=2) và cắt trục Ox tại (4;0)(4; 0). Đường thẳng d12:x+y=3d_{12}: x + y = 3 cắt Oy tại (0;3)(0; 3) và Ox tại (3;0)(3; 0); trên trục y có đánh dấu m4\frac{m}{4} ở phía trên. Hai đường ràng buộc cắt nhau tại điểm (2;1)(2; 1) — được chỉ là 'Phương án tối ưu'. Đường dm:3x+4y=md_m: 3x + 4y = m (nét đậm) song song, cắt Ox tại m3\frac{m}{3} và Oy tại m4\frac{m}{4}. Trên trục x đánh dấu các điểm 1, 2, 103\frac{10}{3}, 4, m3\frac{m}{3}.

Lời giải

## a) Kiểm tra miền chấp nhận được SS

Miền chấp nhận được là tập các điểm (x;y)(x;y) thoả mãn đồng thời tất cả các ràng buộc, tức là giao của các nửa mặt phẳng:

- x≥0x \ge 0: nửa mặt phẳng bên phải trục OyOy;
- y≥0y \ge 0: nửa mặt phẳng phía trên trục OxOx;
- x+2y≥4x + 2y \ge 4: nửa mặt phẳng chứa các điểm phía trên đường x+2y=4x + 2y = 4 (đường này qua (4;0)(4;0) và (0;2)(0;2));
- x+y≥3x + y \ge 3: nửa mặt phẳng chứa các điểm phía trên đường x+y=3x + y = 3 (đường này qua (3;0)(3;0) và (0;3)(0;3)).

Lấy một điểm thử nằm trong miền tô màu, chẳng hạn (5;5)(5;5):
x=5≥0, y=5≥0, x+2y=15≥4, x+y=10≥3.x=5\ge0,\ y=5\ge0,\ x+2y=15\ge4,\ x+y=10\ge3.
Tất cả các ràng buộc đều thoả mãn, nên (5;5)(5;5) thuộc miền chấp nhận được.

Biên của miền gồm các đoạn/tia nằm trên các đường ràng buộc; các đỉnh (điểm cực biên) là giao của các đường biên kề nhau:
- x+y=3x + y = 3 cắt OyOy tại (0;3)(0;3) (thoả x+2y=6≥4x+2y=6\ge4);
- x+2y=4x + 2y = 4 và x+y=3x + y = 3 cắt nhau: trừ vế theo vế được y=1y = 1, suy ra x=2x = 2, tức điểm (2;1)(2;1);
- x+2y=4x + 2y = 4 cắt OxOx tại (4;0)(4;0) (thoả x+y=4≥3x+y=4\ge3).

Miền SS đúng là phần không bị chặn, giới hạn bởi trục OyOy (từ (0;3)(0;3) trở lên), đoạn nối (0;3)(0;3)–(2;1)(2;1) trên đường x+y=3x+y=3, đoạn nối (2;1)(2;1)–(4;0)(4;0) trên đường x+2y=4x+2y=4, và trục OxOx (từ (4;0)(4;0) trở đi). Đây chính là miền SS tô màu trong Hình 2.6. (đpcm)

##

b) Tập hợp các điểm M(x;y)M(x;y) thoả 3x+4y=123x + 4y = 12

Tập hợp các điểm M(x;y)M(x;y) thoả mãn F(x;y)=3x+4y=12F(x;y) = 3x + 4y = 12 là đường thẳng d12:3x+4y=12d_{12}: 3x + 4y = 12.

Đường thẳng này cắt trục OxOx tại (123;0)=(4;0)\left(\dfrac{12}{3};0\right) = (4;0) và cắt trục OyOy tại (0;124)=(0;3)\left(0;\dfrac{12}{4}\right) = (0;3).

##

c) Điều kiện của mm để dm∩S≠∅d_m \cap S \ne \varnothing

Các đường thẳng dm:3x+4y=md_m : 3x + 4y = m (với các giá trị mm khác nhau) là những đường thẳng song song với nhau (cùng vectơ pháp tuyến (3;4)(3;4)). Khi mm tăng, đường dmd_m tịnh tiến ra xa gốc toạ độ về phía miền SS.

Từ hình vẽ, khi mm nhỏ thì dmd_m nằm hẳn phía dưới miền SS (không có điểm chung). Tăng dần mm, đường dmd_m tiến lại gần SS; đường dmd_m bắt đầu chạm miền SS tại điểm (2;1)(2;1) (đỉnh gần gốc toạ độ nhất), ứng với
m=3⋅2+4⋅1=10.m = 3\cdot 2 + 4\cdot 1 = 10.
Với mọi m≥10m \ge 10, đường dmd_m luôn cắt miền SS (miền SS không bị chặn về phía mm lớn). Với m<10m < 10, đường dmd_m nằm ngoài SS.

Vậy điều kiện là:
m≥10.\boxed{m \ge 10}.

##

d) Giá trị nhỏ nhất của FF trên miền chấp nhận được

Với điểm (x;y)(x;y) bất kỳ thuộc SS, đặt m=F(x;y)=3x+4ym = F(x;y) = 3x + 4y; khi đó (x;y)∈dm∩S(x;y) \in d_m \cap S, nên dm∩S≠∅d_m \cap S \ne \varnothing, do đó theo phần

c) ta có m≥10m \ge 10. Suy ra
F(x;y)=3x+4y≥10với mọi (x;y)∈S.F(x;y) = 3x + 4y \ge 10 \quad \text{với mọi } (x;y) \in S.

Dấu bằng xảy ra tại điểm (2;1)∈S(2;1) \in S, vì F(2;1)=3⋅2+4⋅1=10F(2;1) = 3\cdot 2 + 4\cdot 1 = 10.

Vậy giá trị nhỏ nhất của FF trên miền chấp nhận được là
min⁡SF=10, đạt tại (2;1).\min_{S} F = 10, \text{ đạt tại } (2;1).

Điểm (2;1)(2;1) chính là giao của hai đường biên x+2y=4x + 2y = 4 và x+y=3x + y = 3, tức là một điểm cực biên (đỉnh) của miền chấp nhận được. Do đó giá trị nhỏ nhất của FF đạt được tại một điểm cực biên của miền chấp nhận được. (đpcm)

(Kiểm tra thêm tại hai đỉnh còn lại: F(0;3)=12F(0;3) = 12, F(4;0)=12F(4;0) = 12, đều lớn hơn 1010 — phù hợp.)

Đáp số

đpcm (miền SS là giao các nửa mặt phẳng ràng buộc, có các đỉnh (0;3),(2;1),(4;0)(0;3),(2;1),(4;0), không bị chặn)Đường thẳng d12:3x+4y=12d_{12}: 3x+4y=12 (qua (4;0)(4;0) và (0;3)(0;3))m≥10m \ge 10min⁡F=10\min F = 10 tại điểm cực biên (2;1)(2;1)

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.