BỐ CỤC BÀI GIẢNG
1.Các ví dụ dẫn đến bài toán Quy hoạch tuyến
tính:
1.1 Lập kế hoạch sản xuất:
1.2 Phân bổ vốn đầu tư:
2. Định nghĩa:

1. Các ví dụ dẫn đến bài toán Quy hoạch tuyến
tính (QHTT):
1.1 Lập kế hoạch sản xuất:
sản phẩm
Chi phí
S
1
S
2
S
3

Số lượng nguyên
liệu hiện có
Nguyên liệu 1 (N1)
Nguyên liệu 2 (N2)
Nguyên liệu 3 (N3)
Lao động
4
2
3
10

≥ 0, j = 1, 2, 3.)
1 2 3
4 5 3 15000x x x
+ + ≤
Theo kế hoạch sản xuất phải tìm lượng nguyên liệu tiêu
hao là:
N
1
:
1 2 3
2 4 3 12000x x x
+ + ≤
N
2
:
1 2 3
3 6 4 10000x x x
+ + ≤
N
3
:
Số phút cần sử dụng:
1 2 3
10 7 6 500.000x x x+ + ≤
Tổng lợi nhuận theo kế hoạch sản xuất là:
1 2 3
5000 10000 7000x x x
+ +
Yêu cầu tối ưu là:
5000 10000 7000 max












= + + →
+ + ≤
+ + ≤
+ + ≤
+ + ≤
≥ =

Tổng quát: ta có bài toán lập kế hoạch sản xuất
dưới dạng bảng số liệu sau đây:
Yếu tố
sản xuất
Số lượng
hiện có
Sản phẩm
S
1
S
2
…

a
m1
a
m2
…
a
mn
Lợi nhuận đơn vị
c
1
c
2
…
c
n

Mô hình:
Tìm x = (x
1
, x
2
,…, x
n
) sao cho:
max
1
n
f c x
j j
j

kiệm ít nhất 25% tổng vốn đầu tư; gửi tiết kiệm ít
nhất 300 triệu đồng. Hãy xác định kế hoạch phân bổ
vốn đầu tư sao cho tổng thu nhập hàng năm là lớn
nhất.

•
Do tổng số tiền đầu tư không được vượt quá số tiền
hiện có nên: x
1
+ x
2
+ x
3
+ x
4
≤ 4000 (triệu đồng)

•
Điều kiện về số tiền đầu tư vào chứng khoán:
0,3( ) 0,7 0,3 0,3 0,3 0
1 1 2 3 4 1 2 3 4
x x x x x x x x x
≤ + + + ⇔ − + + + ≥
Gọi x
1
, x
2
, x
3
, x

Mô hình:
Tìm x = ( x
1
, x
2
, x
3
, x
4
) sao cho:
1 2 3 4
( ) 0, 2 0,12 0,15 0,18 maxf x x x x x
= + + + →
1 2 3 4
0, 25 0,75 0,75 0, 25 0x x x x+ + − ≥
3
300
x
≥
0, 1, , 4
j
x j
≥ =
0,7 0,3 0,3 0,3 0
1 2 3 4
x x x x
− + + + ≥
1 2 3 4
4000x x x x+ + + ≤


 
 
= =
 
 
≥
 
∑
0
0 , 1, 2, ,
tuy y
j
x j n
≥
 
 
≤ =
 
 
 
hàm mục tiêu
ràng buộc biến
(ràng buộc chính)
ràng buộc dấu


Vectơ x=( x
1
, x
2

Khi đó hoặc là bài toán không có phương án hoặc có
phương án nhưng hàm mục tiêu không bị chặn
( đối với bài toán max (min)).
( ) ( )
f x
→ +∞ −∞

Nếu phương án x thỏa mãn ràng buộc nào đó với
dấu “=” thì ta nói x thỏa mãn chặt ràng buộc đó. Ngược
lại nếu thỏa dấu “>” hoặc “<” thì ta nói thỏa mãn lỏng
rạng buộc đó.

Một số khái niệm:

- Ứng với ràng buộc thứ i ta có vectơ A
i
* = (a
i1
, a
i2
, …,a
i3
).
- Ký hiệu:
1
2
3
.
j
j

án thỏa mãn chặt n ràng buộc độc lập tuyến tính.
+ Phương án cực biên (PACB) thỏa mãn chặt đúng n
ràng buộc gọi là PACB không suy biến, PACB thỏa mãn
chặt hơn n ràng buộc gọi là PACB suy biến.

Một số khái niệm:

( )
1 2 3
1 2 3
1 2 3
1 2 3
10 12 9 max
12 5 0
8 4 6 52
0, 0,
f x x x x
x x x
x x x
x x x
= + + →
− + ≥


+ − =


≥ ≤

Ví dụ 1:

1 2 3
10 7 6 500000
1 2 3
0, 1,2,3
f x x x x
x x x
x x x
x x x
x x x
x j
j











= + + →
+ + ≤
+ + ≤
+ + ≤
+ + ≤
≥ =
Hàm mục
tiêu

≥ =
Định lý: Phương án x của bài toán QHTT dạng chính tắc
là phương án cực biên khi và chỉ khi hệ thống các vectơ
{Aj} tương ứng với các thành phần dương của phương
án là độc lập tuyến tính.

Ví dụ 2: Cho bài toán QHTT có hệ ràng buộc:
1 2 4
2 3 4
2 4
3 2 3
0; 1, , 4
j
x x x
x x x
x j
+ + =
+ + =
≥ =
Các phương án
x
1
= (4; 0; 3; 0); x
2
= (2; 1; 0; 0); x
3
= (0; 1/2; 0; 3/4)
là các PACB theo định lý trên.

* Cách biến đổi bài toán QHTT dạng tổng quát về dạng

j
a x b
=
≥
 
 ÷
≤
 
∑
( )
1
n
p
ij j i i
j
a x x b
=
+ − =
∑
0
p
i
x
≥
với
Ví dụ 3: đưa bài toán QHTT ở ví dụ 1 về dạng chính tắc.

Ví dụ 4: Đưa bài toán QHTT sau về dạng chính tắc.
( )
1 2 3

5
1 2 3 4 6
6 2 9 30
5
1 2 4
4 3 40
5
2 3 4
3 26
5
2 6
0 1, ,6
f x x x x x x x
x x x x
x x x x
x x x
x j
j
= + + + − − →
− − − ≥
+ + + =
+ + ≤
≥ =

* Bài toán QHTT dạng chuẩn là:
+ Bài toán QHTT dạng chính tắc.
+
+ Ma trận hệ số chứa ma trận đơn vị.
( )
0 1, ,



Bằng cách sắp xếp lại bài toán QHTT dạng chuẩn
có dạng.
( ) ( )
(
)
(
)
(
)
( ) ( )
max min
1
a
1 1 1 1
1 m+1
a
2 1 2 2
1 m+1
a
1
m+1
0 1, , ; 0 1, ,
n
f x c x
j j
j
x x a x b
n