Bài 3. Vận dụng hệ bất phương trình bậc nhất hai ẩn để giải quyết một số bài toán quy hoạch tuyến tính

Chuyên đề 2. Ứng dụng toán học để giải quyết một số bài toán tối ưu

1. Giới thiệu bài toán quy hoạch tuyến tính hai biến

Bài toán quy hoạch tuyến tính hai biến Tìm giá trị lớn nhất (hoặc nhỏ nhất) của biểu thức

F (x; y) = A x + B y

(hàm mục tiêu,

A, B

không đồng thời bằng 0) trên miền nghiệm $S$ của một hệ bất phương trình bậc nhất hai ẩn

$a_{1} x + b_{1} y \leq c_{1}; \dots; a_{n} x + b_{n} y \leq c_{n}$ (các ràng buộc; có thể có “ $\geq$ ”)

Viết gọn:

F (x; y) = A x + B y \to max (min)

Thuật ngữ

Cặp $(x_{0}; y_{0})$ là nghiệm của hệ gọi là phương án chấp nhận được (khả thi); tập các phương án chấp nhận được là miền chấp nhận được (miền nghiệm $S$ ).
Phương án chấp nhận được làm $F$ lớn nhất (nhỏ nhất) gọi là phương án tối ưu; giá trị đó gọi là giá trị tối ưu.
Đỉnh của miền nghiệm gọi là điểm cực biên (phương án cực biên).

Ví dụ 1 – xí nghiệp sản xuất (tình huống mở đầu) Sản phẩm loại I: 2 kg nguyên liệu, 30 giờ, lãi 40 nghìn/kg; loại II: 4 kg, 15 giờ, lãi 30 nghìn/kg. Có 200 kg nguyên liệu và tối đa 1 200 giờ. Gọi

x, y

(kg) là số kg loại I, II:

F = 40 x + 30 y \to max

với

2 x + 4 y \leq 200

(hay

x + 2 y \leq 100); 30 x + 15 y \leq 1200

(hay

2 x + y \leq 80); x \geq 0, y \geq 0

. Miền nghiệm là tứ giác với đỉnh

O (0; 0), (0; 50), (20; 40), (40; 0) . F

tại các đỉnh: 0; 1 500; 2 000;

1600 \Rightarrow

phương án tối ưu

(20; 40)

: sản xuất 20 kg loại I và 40 kg loại II, lãi 2 000 nghìn đồng.

Ví dụ – thực phẩm X,

Y

(doanh thu lớn nhất) 1 tấn X: 0,5 tấn bột, 0,5 đường, 0,2 dầu; 1 tấn

Y : 0, 6; 0, 3; 0, 5

; dự trữ 15; 12; 10 tấn. Giá bán 100 và 112 triệu/tấn:

F = 100 x + 112 y \to max

với

0, 5 x + 0, 6 y \leq 15; 0, 5 x + 0, 3 y \leq 12; 0, 2 x + 0, 5 y \leq 10; x, y \geq 0

. Đỉnh:

O; A (0; 20); B (\frac{150}{13}; \frac{200}{13}); C (18; 10); D (24; 0) . F : 0; 2240; 2876, 9

; 2 920;

2400 \Rightarrow

sản xuất 18 tấn X, 10 tấn

Y

, doanh thu 2 920 triệu.

Miền phương án chấp nhận được của bài toán xí nghiệp (ví dụ 1)

2. Miền chấp nhận được là miền đa giác

Nhận xét

Nếu $S = \emptyset$ thì bài toán không có phương án tối ưu.
Nếu $S \neq = \emptyset$ và là miền đa giác thì bài toán luôn có phương án tối ưu, và phương án tối ưu là một trong các phương án cực biên (đỉnh).

5 bước giải

Đặt biến ( $x, y$ , kèm đơn vị).
Xác định hàm mục tiêu $F (x; y)$ .
Lập hệ bất phương trình ràng buộc (nhớ $x \geq 0, y \geq 0$ nếu là số lượng).
Biểu diễn miền nghiệm, tìm các đỉnh.
Tính $F$ tại mọi đỉnh, chọn lớn nhất / nhỏ nhất, kết luận.

Ví dụ 3 – bài toán vitamin (chi phí nhỏ nhất) Cần 400–1 000 đơn vị vitamin A và

B

(cả hai),

A \leq 600, B \leq 500, B \geq \frac{1}{2} A, B \leq 3

A; giá A 90 đồng,

B 75

đồng.

F = 90 x + 75 y \to min

; miền nghiệm là lục giác

MNPQRS

với

M (100; 300), N (\frac{500}{3}; 500), P (500; 500), Q (600; 400), R (600; 300), S (\frac{800}{3}; \frac{400}{3}) . F : 31500; 52500; 82500; 84000; 76500; 34000 \Rightarrow

nhỏ nhất 31 500 đồng tại

M (100; 300)

Miền lục giác MNPQRS của bài toán vitamin (ví dụ 3)

Ví dụ 4 – nhiều phương án tối ưu Sơn nội thất (

x

tấn) và ngoài trời (

y

tấn),

X \leq 6

tấn,

Y \leq 8

tấn:

2 x + y \leq 6; x + 2 y \leq 8; x \leq y + 1; 0 \leq x \leq 2; y \geq 0. F = 60 x + 30 y = 30 (2 x + y) \Rightarrow

khi

2 x + y = 6

thì

F = 180

(lớn nhất) tại mọi điểm của đoạn $C D$

(C (2; 2), D (\frac{4}{3}; \frac{10}{3}))

: có vô số phương án tối ưu.

Lưu ý Khi đường mức

F =

hằng số song song với một cạnh của miền thì phương án tối ưu đạt tại cả cạnh đó. Số lượng phải nguyên (xe, máy…) thì kiểm tra lại các điểm nguyên gần đỉnh.

3. Miền chấp nhận được không phải là miền đa giác

Nhận xét

Nếu bài toán có phương án tối ưu thì nó là một trong các phương án cực biên.
Nếu $F = A x + B y$ có $A > 0, B > 0$ , ràng buộc gồm $x \geq 0, y \geq 0$ và miền không là đa giác (không bị chặn) thì $F$ có giá trị nhỏ nhất, không có giá trị lớn nhất.

Ví dụ 5 – khẩu phần ăn 100 g X: 2 chất béo, 1 carbohydrate, 4 protein; 100 g

Y : 3; 3; 3

. Cần

\geq 18; \geq 12; \geq 24

. Giá 20 và 25 nghìn/100 g.

F = 20 x + 25 y \to min; 2 x + 3 y \geq 18; x + 3 y \geq 12; 4 x + 3 y \geq 24; x, y \geq 0

. Đỉnh

A (0; 8), B (3; 4), C (6; 2), D (12; 0) : F = 200

; 160;

170; 240 \Rightarrow min 160

tại

B

: mua 300 g X, 400 g Y.

Ví dụ 6 Hệ

x + y \geq 3; 2 x - y \geq 1; x - 2 y \geq - 4; y \geq 0

: miền không bị chặn, đỉnh

A (2; 3), B (\frac{4}{3}; \frac{5}{3}), C (3; 0) . F = 2 x + 3 y

có

min = 6

tại

C

và không có

max

. Với

G = - x + 0, 5 y

thì

max = - \frac{1}{2}

tại mọi điểm đoạn

A B

(vì

G = - \frac{1}{2} (2 x - y) = - \frac{1}{2}

Tổng kết bài 3 Quy hoạch tuyến tính: lập hàm mục tiêu và ràng buộc

\to

vẽ miền nghiệm

\to

chỉ cần tính tại các đỉnh. Miền đa giác: có cả

max, min

; miền không bị chặn: kiểm tra từng trường hợp.

Bài 3. Vận dụng hệ bất phương trình bậc nhất hai ẩn để giải quyết một số bài toán quy hoạch tuyến tính

1. Giới thiệu bài toán quy hoạch tuyến tính hai biến

2. Miền chấp nhận được là miền đa giác

3. Miền chấp nhận được không phải là miền đa giác

Sơ đồ tư duy