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

Giải Hoạt động 3 trang 30 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 \to \min$
với các ràng buộc
$\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 $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 \cap S \ne \varnothing$.
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.

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

Hình 2.6: Hệ trục toạ độ Oxy. Miền $S$ (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 $d_{10}: x + 2y = 4$ cắt trục Oy tại điểm $(0; 2)$ (ghi $\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)$. Đường thẳng $d_{12}: x + y = 3$ cắt Oy tại $(0; 3)$ và Ox tại $(3; 0)$; trên trục y có đánh dấu $\frac{m}{4}$ ở phía trên. Hai đường ràng buộc cắt nhau tại điểm $(2; 1)$ — được chỉ là 'Phương án tối ưu'. Đường $d_m: 3x + 4y = m$ (nét đậm) song song, cắt Ox tại $\frac{m}{3}$ và Oy tại $\frac{m}{4}$. Trên trục x đánh dấu các điểm 1, 2, $\frac{10}{3}$, 4, $\frac{m}{3}$.

Lời giải

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

Miền chấp nhận được là tập các điểm $(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 \ge 0$: nửa mặt phẳng bên phải trục $Oy$;
- $y \ge 0$: nửa mặt phẳng phía trên trục $Ox$;
- $x + 2y \ge 4$: nửa mặt phẳng chứa các điểm phía trên đường $x + 2y = 4$ (đường này qua $(4;0)$ và $(0;2)$);
- $x + y \ge 3$: nửa mặt phẳng chứa các điểm phía trên đường $x + y = 3$ (đường này qua $(3;0)$ và $(0;3)$).

Lấy một điểm thử nằm trong miền tô màu, chẳng hạn $(5;5)$:
$$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)$ 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 = 3$ cắt $Oy$ tại $(0;3)$ (thoả $x+2y=6\ge4$);
- $x + 2y = 4$ và $x + y = 3$ cắt nhau: trừ vế theo vế được $y = 1$, suy ra $x = 2$, tức điểm $(2;1)$;
- $x + 2y = 4$ cắt $Ox$ tại $(4;0)$ (thoả $x+y=4\ge3$).

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

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

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

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

## c) Điều kiện của $m$ để $d_m \cap S \ne \varnothing$

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

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

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

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

Với điểm $(x;y)$ bất kỳ thuộc $S$, đặt $m = F(x;y) = 3x + 4y$; khi đó $(x;y) \in d_m \cap S$, nên $d_m \cap S \ne \varnothing$, do đó theo phần c) ta có $m \ge 10$. Suy ra
$$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) \in S$, vì $F(2;1) = 3\cdot 2 + 4\cdot 1 = 10$.

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

Điểm $(2;1)$ chính là giao của hai đường biên $x + 2y = 4$ và $x + 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 $F$ đạ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) = 12$, $F(4;0) = 12$, đều lớn hơn $10$ — phù hợp.)

Đáp số

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