Giáo án điện tử chuyên đề Toán 12 chân trời Bài 1: Bài toán quy hoạch tuyến tính

KHỞI ĐỘNG

Một thương nhân sử dụng 120 triệu đồng tiền vốn để mua tối đa 8 tấn trái cây. Thương nhân đó thu mua hai loại trái cây là A với giá 12 triệu đồng/tấn và B với giá 20 triệu đồng/tấn. Lợi nhuận thương nhân đó thu được sau khi bán mỗi tấn hàng đối với loại A là 1,1 triệu đồng, đối với loại B là 1,5 triệu đồng. Thương nhân đó nên mua khối lượng bao nhiêu mỗi loại để thu được lợi nhuận cao nhất khi bán hết hàng đã thu mua?

CHUYÊN ĐỀ I: ỨNG DỤNG TOÁN HỌC GIẢI CÁC BÀI TOÁN TỐI ƯU

BÀI 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

NỘI DUNG BÀI HỌC

1. Bài toán quy hoạch tuyến tính

2. Ứng dụng vào các bài toán thực tế

1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

HĐKP1. Xét bài toán: Tìm giá trị lớn nhất và giá trị nhỏ nhất của biểu thức với là nghiệm của hệ bất phương trình

Miền nghiệm của hệ là miền tứ giác (được tô màu) trên Hình 1. Với giá trị cho trước, xét đường thẳng :

Trả lời các câu hỏi sau để giải bài toán trên.

a) Với giá trị nào của thì đường thẳng đi qua điểm , điểm ?

b) Khi giá trị của tăng (hoặc giảm) thì tung độ giao điểm của với trục thay đổi như thế nào? Khi đó, phương của đường thẳng có thay đổi không?

c) Với điều kiện nào của thì đường thẳng và miền nghiệm có điểm chung?

d) Từ đó, chỉ ra giá trị lớn nhất và giá trị nhỏ nhất của biểu thức trên miền nghiệm . Biểu thức đạt được các giá trị đó tại điểm nào?

Giải:

a) Thay vào ta có: , suy ra

Thay vào ta có: , suy ra

Vậy thì đường thẳng đi qua điểm , thì đường thẳng đi qua điểm .

Vậy khi giá trị của tăng (hoặc giảm) thì tung độ giao điểm của với trục thay đổi cũng tăng (hoặc giảm) tương ứng.

Khi đó, đường thẳng có phương không đổi, luôn nhận vectơ làm vectơ pháp tuyến.

Giải:

Vậy đường thẳng và miền nghiệm có điểm chung khi và chỉ khi

d) Từ đó, đạt được tại điểm ;

đạt được tại điểm .

Bài toán quy hoạch tuyến tính (hai biến) là bài toán tìm giá trị lớn nhất, giá trị nhỏ nhất của biểu thức dạng ( và là các số thực không đồng thời bằng ) trên miền nghiệm của một hệ bất phương trình bậc nhất hai ẩn ( và ).

Biểu thức gọi là hàm mục tiêu, hệ bất phương trình bậc nhất gọi là ràng buộc, miền nghiệm gọi là tập phương án của bài toán quy hoạch tuyến tính đó.

Khái niệm

Các bước giải bài toán quy hoạch tuyến tính trong trường hợp tập phương án là miền đa giác.

Bước 1: Biểu diễn tập phương án của bài toán trên mặt phẳng tọa độ .

Bước 2: Tính giá trị của biểu thức tại các đỉnh của

Giá trị lớn nhất (nhỏ nhất) trong các giá trị này là giá trị lớn nhất (nhỏ nhất) của trên .

Chú ý

a) Trong bài toán quy hoạch tuyến tính, ta viết

(hoặc )

để thể hiện tìm giá trị lớn nhất (hoặc giá trị nhỏ nhất) của . Nếu tìm cả giá trị lớn nhất và giá trị nhỏ nhất của thì ta viết

.

b) Giá trị lớn nhất, giá trị nhỏ nhất của trên được kí hiệu lần lượt là và . Với hai số thực cho trước, ta viết để chỉ giá trị của hàm mục tiêu khi .

Ví dụ 1. Giải bài toán quy hoạch tuyến tính:

với ràng buộc

Giải:

Tập phương án là miền tứ giác trên Hình 2.

Toạ độ giao điểm của hai đường thằng và là nghiệm của hệ phương trình:

Giải:

Giá trị của biểu thức tại các đỉnh của :

HĐKP2. Xét bài toán quy hoạch tuyến tính:

Với ràng buộc

Tập phương án của bài toán là phần được tô màu trên Hình 3. Hai điểm và gọi là các đỉnh của .

Với giá trị cho trước, xét đường thẳng : hay .

Trả lời các câu hỏi sau để giải bài toán trên.

a) Tìm giá trị của để đường thẳng đi qua điểm . Gọi giá trị tìm được là

b) Khi giá trị của tăng (hoặc giảm) thì tung độ giao điểm của với trục thay đổi như thế nào? Khi đó, phương của đường thẳng có thay đổi không?

c) Nếu thì và có điểm chung không? Từ đó, chỉ ra giá trị nhỏ nhất của hàm mục tiêu trên .

d) Với giá trị nào của thì và có điểm chung? Hàm mục tiêu đạt giá trị lớn nhất trên hay không?

Giải:

a) Thay vào phương trình đường thẳng ta có:

Vậy đường thẳng đi qua điểm khi .

b) Giao điểm của đường thẳng với trục là . Khi tăng (hoặc giảm) thì tung độ giao điểm của với trục tăng (hoặc giảm).

Khi đó, đường thẳng có phương không đổi, luôn nhận vectơ làm vectơ pháp tuyến.

c) Khi thì và không có điểm chung. Từ dó, .

d) và có điểm chung khi .

Suy ra, hàm mục tiêu không đạt giá trị lớn nhất trên .

Chú ý

Nhiều bài toán quy hoạch tuyến tính xuất phát từ tình huống thực tế có tập phương án (không là miền đa giác) nằm trong góc phần tư thứ nhất (của mặt phẳng tọa độ ) và hàm mục tiêu có các hệ số không âm. Khi đó, người ta chứng minh được rằng luôn đạt giá trị nhỏ nhất trên tại đỉnh nào đó của .

Từ đó, đối với bài toán quy hoạch tuyến tính

min

với tập phương án không là miền đa giác nằm trong góc phần tư thứ nhất và các hệ số và không âm, ta có thể giải bằng cách thực hiện các bước như sau:

Bước 1: Biểu diễn tập phương án của bài toán trên mặt phẳng tọa độ .

Bước 2: Tính giá trị của biểu thức tại các đỉnh của .

Giá trị nhỏ nhất trong các giá trị này là giá trị nhỏ nhất của trên .

Ví dụ 2. Giải bài toán quy hoạch tuyến tính:

với ràng buộc

Giải:

Viết lại ràng buộc của bài toán thành

Giải:

Tập phương án của bài toán là miền không gạch chéo trên Hình 4 (không là miền đa giác).

Toạ độ điểm là nghiệm của hệ

Tương tự, tìm được điểm

Miền có hai đỉnh là và

Do nằm trong góc phần tư thứ nhất và các hệ số của biểu thức đều dương nên đạt giá trị nhỏ nhất tại một đỉnh của .

Ta có

Vậy đạt giá trị nhỏ nhất tại đỉnh và

Thực hành 1

Giải bài toán quy hoạch tuyến tính:

với ràng buộc

Giải:

Tọa độ giao điểm của đường thẳng và trục là .

Tọa độ giao điểm của hai đường thẳng và là nghiệm

của hệ phương trình

Vậy .

Giải:

Tương tự, ta tìm được .

Tập phương án là miền tứ giác với .

Giá trị của biểu thức tại các đỉnh của :

Từ đó,

.

Thực hành 2

Giải bài toán quy hoạch tuyến tính:

với ràng buộc

Giải:

Viết lại ràng buộc của bài toán thành

Tương tự, tìm .

Giải:

Tập phương án là miền không đa giác có hai

Do nằm trong góc phần tư thứ nhất, các hệ số của hàm mục tiêu đều dương nên hàm mục tiêu đạt giá trị nhỏ nhất tại đỉnh của .

Từ đó, .

Vận dụng

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

có tập phương án là miền tứ giác (được tô màu như Hình 5) với các đỉnh là và

a) Giải bài toán quy hoạch tuyến tính đã cho.

b) Hàm mục tiêu đạt giá trị lớn nhất trên tại bao nhiêu điểm? Giải thích.

Giải:

a) Tập phương án của bài toán là miền tứ giác với các đỉnh là , và .

Giá trị của tại các đỉnh của là: .

Suy ra đạt được tại các đỉnh hoặc đạt được tại đỉnh .

b) Tại mọi điểm ( trên cạnh của miền , ta đều có

hay

do đó, .

Vậy đạt giá trị lớn nhất trên tại mọi điểm thuộc cạnh .

2. ỨNG DỤNG VÀO CÁC BÀI TOÁN THỰC TẾ

HĐKP3. Xét tình huống thương nhân thu mua trái cây ở Bài toán mở đầu (trang 6).

a) Nếu gọi (tính theo tấn) lần lượt là khối lượng trái cây loại và được thương nhân thu mua thì và phải thỏa mãn hệ bất phương trình bậc nhất hai ẩn nào?

b) Từ đó, phát biểu bài toán quy hoạch tuyến tính tìm khối lượng thu mua mỗi loại trái cây để thu được lợi nhuận cao nhất. Giải bài toán đó.

Giải:

a) Ta có: .

Do tiền thu mua không vượt quá 120 triệu đồng nên

hay .

Do tổng khối lượng trái cây không vượt quá 8 tấn nên hay .

Lợi nhuận đạt được là .

Tập phương án của bài toán là miền tứ giác trên hình, trong đó

, .

Giá trị của tại các đỉnh:

Từ đó, .

Giải:

b) Từ đó, ta nhận được bài toán quy hoạch tuyến tính:

Với ràng buộc

Các bước thực hiện giải bài toán tối ưu trong thực tế:

--------------- Còn tiếp ---------------