16/04/2017
1
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
QUY HOẠCH TUYẾN TÍNH
HAI BIẾN
CHƯƠNG 5b
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 1
•Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh,
bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường,
đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền
lãi cho một bánh mỗi loại được cho trong bảng sau:
•Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần
sản xuất sao cho không bị động về nguyên liệu mà lãi đạt
được cao nhất.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 1
•Gọi x
1
,x
2
,x
3
lần lượt là số bánh đậu xanh, bánh thập
cẩm, bánh dẻo cần phải sản xuất.
•Điều kiện: x
j
≥ 0 = 1,2,3
•Tiền lãi thu được (ngàn đồng)
•Lượng đường sử dụng và điều kiện:
•Lượng đậu sử dụng và điều kiện:
1 2 3 1 2 3
, , 3 2 2,5f x f x x x x x x
123
0,04 0, 06 0,05 500
x x x

1 3
0,07 0,02 300
x x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 1
•Vậy ta có mô hình bài toán:
•Đây là bài toán quy hoạch tuyến tính 3 biến, tìm
giá trị lớn nhất của hàm mục tiêu.
1 2 3 1 2 3
1 2 3
1 3
, , 3 2 2,5 max
0,04 0,06 0,05 500
0,07 0,02 300
0 1,2,3
j
f x f x x x x x x
x x x
x x
x j
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 2
•Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng
đạm, đường, khoáng cho một loại gia súc tương ứng là
90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng
trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi
loại được cho trong bảng sau:
•Hãy lập mô hình toán học của bài toán xác định khối lượng
thức ăn mỗi loại phải mua để tổng số tiền chi cho mua
thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng
mỗi ngày.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 3
•Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là
bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và
giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau:
•Hãy lập mô hình toán học của bài toán xác định số sản phẩm
mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất
và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao
động tương đương với 500 ngày công, số tiền dành cho chi phí
sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.
16/04/2017
2
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 4
•Bài toán lập kế hoạch sản xuất
•Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại
ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả
sử, đối với:
•Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m
ván
•Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván
•Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm
việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván
thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m
ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa
phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Bài toán QHTT tổng quát
(1) Hàm f(x) gọi là hàm mục tiêu
(2) là hệ ràng buộc chính
(3) là hệ ràng buộc dấu
(2) Và (3) gọi chung là hệ ràng buộc của bài toán
1 1 2 2
1 1 2 2
1 ...
2 ... 1, 2,..,
0
3 0 1, 2,...,
min (max)
n n
i i in n i
j
f x c x c x c x
a x a x a x b i m
x j n
tuy y
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Bài toán dạng chính tắc
n
j j
j 1
n
ij j
j 1
j
f x c x min (max)
a x b (i 1,m)
x 0 (j 1,n)
i
Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài
toán dạng chính tắc tương đương theo nghĩa trị tối ưu
của hàm mục tiêu trong hai bài toán là trùng nhau và từ
phương án tối ưu của bài toán này suy ra phương án tối
ưu của bài toán kia
•Các ràng buộc
chính đều là
phương trình
•Các ẩn đều
không âm
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 4
•Bài toán sau có dạng chính tắc:
1 2 3
1 2 3
1 2 3
1 2
1 2 3
260 120 600 max
2 3 500
100 40 250 40000
6
, , 0
x x x
x x x
x x x
x x
x x x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Dạng ma trận của bài toán QHTT
•Xét bài toán QHTT dạng:
1 1 2 2
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
...
...
...
..........................................
...
0
min (max)
n n
n n
n n
m m mn n m
j
f x c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Dạng ma trận của bài toán QHTT
•Đặt:
•Ta có dạng ma trận của bài toán QHTT:
11 12 1
1 2
...
...
....................
...
n
n
m m mn
a a a
A b x c
a a a
min max
0
T
f c x
Ax b
x
16/04/2017
3
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Các loại phương án
•Định nghĩa. Vec tơ ∈
thỏa tất cả các ràng
buộc của bài toán quy hoạch tuyến tính được
gọi là phương án chấp nhận được.
•Định nghĩa. Phương án chấp nhận được làm
cho hàm mục tiêu có giá trị lớn nhất (nếu là bài
toán max) hay nhỏ nhất (nếu là bài toán min)
thì được gọi là phương án tối ưu (PATU).
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ
•Cho bài toán QHTT:
•Trong các phương án sau phương án nào là
phương án chấp nhận được.
1 2
1 2
1 2
1 2
120 100 max
2 3 8
5 3 15
0, 0
f x x x
x x
x x
x x
1 2 3 4
1 2 1 2
2 2 3 1
u u u u
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Đưa bài toán về dạng chính tắc
•Bước 1. Kiểm tra ràng buộc chính
1 1 2 2
...
i i in n i
a x a x a x b
•Ràng buộc dạng nhỏ hơn:
•
•Ta cộng thêm ẩn phụ:
•Ràng buộc dạng lớn hơn:
•Ta trừ đi ẩn phụ:
1 1 2 2
...
i i in n n k i
a x a x a x x b
1 1 2 2
...
i i in n i
a x a x a x b
1 1 2 2
...
i i in n n k i
a x a x a x x b
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Đưa bài toán về dạng chính tắc
•Bước 2. Kiểm tra điều kiện dấu các ẩn số
•Nếu có ẩn dạng: ta đổi biến:
•Nếu ẩn xi có dấu tùy ý ta đổi biến:
•Chú ý:
•Các ẩn mới và các ẩn phụ đều không âm.
•Hệ số của các ẩn phụ trong hàm mục tiêu là 0.
•Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần
tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ
được PATU của bài toán dạng tổng quát đã cho.
0
i
x
i i i
x x x
i i
x x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ
•Đưa bài toán sau về dạng chính tắc:
1 2 3
123
1 3
1 2 3
1 2
2 4 min
4 6 3 12
7 3
2 3 5 6
0, 0
f x x x x
x x x
x x
x x x
x x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Tính chất của tập phương án
•Định nghĩa. Đoạn thẳng nối hai điểm x1 và x2 được
định nghĩa:
•Nhận xét
•Nếu = 0 chúng ta có x2, = 1 chúng ta có x1.
•Những điểm thuộc đoạn thẳng với 0 < < 1 gọi là
các điểm trong của đoạn thẳng
•x1, x2 gọi là các điểm biên của đoạn thẳng.
1 2
1 , 0 1
n
x R x x x
16/04/2017
4
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Tính chất của tập phương án
•Định lý. Cho x
1
và x
2
là hai phương án chấp nhận được
của bài toán QHTT. Điểm = 
1
+ 1 −
2
với
0 ≤ ≤ 1 thuộc đoạn thẳng nối hai điểm x
1
và x
2
.
•Khi đó:
•i) x cũng là phương án chấp nhận được
•ii) Nếu các f(x
1
)=f(x
2
) thì f(x)=f(x
1
)=f(x
2
)
•iii) Nếu f(x
1
)<f(x
2
) thì f(x)<f(x
2
)
•Nhận xét: Đối với tập các phương án chấp nhận được
là đoạn thẳng nối hai điểm x
1
, x
2
thì một điểm biên có
giá trị hàm mục tiêu lớn nhất và điểm biên còn lại có
giá trị hàm mục tiêu nhỏ nhất.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ
•Xét bài toán QHTT
•Có tập phương án được biểu
diễn như hình bên
, 4 3 max
4
5 3 15
, 0
f x y x y
x y
x y
x y
•Ta thấy x
1
=(0,5; 2) và x
2
=(2;0,5) là các phương án chấp
nhận được.
•Điểm = 
1
+ 1 −
2
với =2/3 cũng là phương
án chấp nhận được.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ
•Hai phương án chấp nhận
được x
1
=(0,5; 7/3) và
x
2
=(2;1/3) có cùng giá trị
hàm mục tiêu là 9.
•Khi đó phương án x định
bởi:
•Cũng có giá trị hàm mục tiêu
là 9.
1 2
2
1
3
x x x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Tập lồi và tính chất
•Tập S gọi là tập lồi nếu với hai điểm phân biệt
bất kỳ x
1
và x
2
thuộc S thì đoạn nối hai điểm x
1
và x
2
cũng nằm trong tập S.
Tập lồi
Không phải
Tập lồi
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Định lý
•Tập S tất cả các phương án chấp nhận được của
bài toán quy hoạch tuyến tính dạng chính tắc là
một tập lồi.
, 0
S x Ax b x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Điểm cực biên của tập hợp lồi
•Điểm x trong tập lồi S được gọi là điểm cực biên
nếu không thể biểu diễn được dưới dạng tổ
hợp lồi thật sự của hai điểm phân biệt của S.
16/04/2017
5
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Điểm cực biên của tập hợp lồi
•Định lý. Điểm x của tập lồi S được gọi là điểm cực biên
của S nếu x không là tổ hợp lồi của hai điểm của S khác
x.
•Nhận xét:
•Nếu có x1, x2 thuộc S sao cho
•Thì:
1 2
1 , 0
x x x
1 2
x x x
A, B, C, D, E là các điểm cực biên
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Tính chất tập phương án
•Tập hợp các phương án của một bài toán quy
hoạch tuyến tính là một tập lồi đa diện.
•Nếu tập hợp lồi đa diện này không rỗng và bị
chặn thì đó là một đa diện lồi. Số điểm cực biên
của nó là hữu hạn.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Phương án cực biên
•Định nghĩa. Điểm cực biên của tập các phương
án S trong bài toán QHTT gọi là phương án cực
biên.
•Tính chất.
•Số phương án cực biên của tập phương án S
trong bài toán QHTT là hữu hạn
•Nếu bài toán QHTT dạng chính tắc có phương
án tối ưu thì nó sẽ có một phương án cực biên
là phương án tối ưu.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Phương pháp đồ thị
•Dùng cho bài toán quy hoạch tuyến tính 2 biến
•Xét bài toán quy hoach tuyến tính :
2
1
2
1
min max
0
j j
j
ij j i
j
j
f x c x
a x b
x
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Phương pháp đồ thị
•Biểu diễn các ràng buộc lên đồ thị Oxy.
•Xác định phần được giới hạn bởi các ràng buộc là tập
phương án.
•Xác định các điểm cực biên (đỉnh) của tập phương án
thỏa mãn các ràng buộc.
•Xác định giá trị của hàm mục tiêu tại các điểm cực
biên.
•So sánh và suy ra phương án tối ưu
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 1
•Giải bài toán QHTT sau:
1 2 1 2
1 2
1 2
1 2
1 2
, min
2 2 1
2 2
5 3
0, 0
f x x x x
x x
x x
x x
x x
