Bài toán quy hoạch tuyến tính và ý nghĩa hình học

§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ Ý NGHĨA HÌNH HỌC Dạng tổng quát của bài toán Quy hoạch tuyến tính. Bài toán Quy hoạch tuyến tính tổng quát có dạng sau đây Tìm giá trị lớn nhất hay nhỏ nhất của hàm
với các ràng buộc:
Trong đó
rời nhau và
,
rời nhau và
. Có thể viết lại bài toán tổng quát trên như sau:
Ví dụ: Xét bài toán

Đây là bài toán Quy hoạch tuyến tính dạng tổng quát, trong đó
. 2. Một số khái niệm của bài toán Quy hoạch tuyến tính: 2.1. Hàm mục tiêu: Hàm
được gọi là hàm mục tiêu. 2.2. Phương án: Véctơ
thỏa tất cả các ràng buôc (1), (2), (3), (4), (5), (6) gọi là một phương án. Tập hợp tất cả các véctơ x thỏa tất cả các ràng buộc (1), (2), (3), (4), (5), (6) gọi là tập phương án. 2.3. Phương án tối ưu: Phương án x làm cho hàm mục tiêu đạt giá trị lớn nhất (nếu là bài toán max) hoặc giá trị nhỏ nhất (nếu là bài toán min) được gọi là phương án tối ưu. 3. Dạng chính tắc của bài toán Quy hoạch tuyến tính: Bài toán Quy hoạch tuyến tính có dạng sau đây, gọi là dạng chính tắc
Hay có thể viết lại
Trong đó
là một ma trận cấp
,
. Viết
, nghĩa là
Quy ước thêm

là véctơ cột thứ j của ma trận A. Chú ý: Nếu là véctơ, trong giáo trình này không phân biệt véctơ dòng hay véctơ cột. Tuy nhiên trong từng điều kiện cụ thể ta không thể nhầm lẩn. Điều này không có gì khó khăn. Nhận xét: Mọi bài toán Quy hoạch tuyến tính đều có thể đưa về dạng chính tắc. Thật vậy, nếu gặp bất đẳng thức
, ta viết lại

Nếu gặp bất đẳng thức
, ta viết lại

Nếu
, ta thay
. Nếu
, ta thay
. 4. Ý nghĩa hình học và phương pháp đồ thị: Xét bài toán Quy hoạch tuyến tính
Ta biểu diễn tập phương án trên mặt phẳng x0y, đó chính là tứ giác OABC. Hàm mục tiêu
, với mỗi một giá trị
cố định, ta có
là một đường thẳng (d) có véctơ pháp tuyến
.
 Khi cho f thay đổi ta có họ đường thẳng song song. Vẽ đường thẳng (d) đi qua một điểm nào đó của tập phương án, chẳng hạn O(0;0), đường thẳng (d) lúc đó là
. Tịnh tiến đường thằng (d) theo một hướng nào đó sẽ làm cho giá trị hàm mục tiêu tăng, ngược lại sẽ làm hàm mục tiêu giảm. Ở bài toán này ta cần làm cho hàm mục tiêu tăng. Rõ ràng đi theo hướng mũi tên sẽ làm cho hàm mục tiêu tăng. Nhận thấy:

. Hàm mục tiêu đạt giá trị max là 20 tại điểm C(5;0). Trong trường hợp tập phương án không rỗng, và không bị chặn, hàm mục tiêu có thể nhận những giá trị nhỏ, hay lớn tùy ý. Lúc đó bài toán không có phương án tối ưu. Bài tập. 1. Đưa các bài toán sau đây về dạng chính tắc a)

b)

c)

2. Biểu diễn trên mặt phẳng x0y tập phương án của các bài toán sau a)

b)

3. Biểu diễn trong không gian 0xyz tập phương án của các bài toán sau a)

b)

4. Cho bài toán Quy hoạch tuyến tính dạng chính tắc

a) Hãy chỉ một phương án của bài toán. b) Rõ ràng tập phương án là tập các nghiệm của hệ phương trình tuyến tính (I). Hãy chỉ ra tập phương án của bài toán. 5. Bằng phương pháp hình học, giải các bài toán sau a)

b)

c)

Lời giải hoặc hướng dẫn 1) a)

b)

2) a) T ương tự như ví dụ. Tập phương án là phần trong của tam giác ABC.
 b) T ương tự như ví dụ. Tập phương án là phần trong của ngũ giác ABCDE, phần gạch chéo. Với A(1,0); B(0,1); C(0,9/4); D(3/4, 15/8); E(2,0).
 3) a) Tập phương án là phần trong hình chóp OABC, trong đó O(0;0;0), A(4;0;0), B(0;5;0), C(0;0;6).
 b) Tập phương án là hình hộp xiên. 4. a) Dùng phép biến đổi sơ cấp ta giải hệ phương trình tuyến tính đã cho.
. Ta có hệ phương trình tương đương
Ta có thể chọn một nghiệm như sau x=(2,0,2,0). Đây là một phương án của bài toán. b) Tập phương án của bài toán là:
Vì theo giả thiết
cho nên
. 5. a) Tập phương án là phần trong của ngũ giác ABCD, phần gạch chéo. Với A(12/5,2/5); B(0,2); C(0,6); D(4, 2).
 Vẽ đường thẳng
đi qua một điểm của tập phương án. Khi cho f thay đổi sẽ làm cho giá trị hàm mục tiêu tăng hay giảm.Ở bài toán này ta cần làm cho hàm mục tiêu giảm. Từ đó giá trị min của f là: f(A)=-42/5.