1

BÀI TẬP MÔN QUY HOẠCH TUYẾN TÍNH

Câu 1. Cho bài tóan Quy họach tuyến tính mà ta gọi là bài tóan (P)
= − − + →
1 2 3 4
( ) 3 4 5 6 min
f x x x x x
+ + + =


+ + =


+ + =

≥ =
1 2 3 4
1 2 4
2 3 4
13 14
2 14 11
3 14 16
0, 1,4.
j
x x x x
x x x
x x x
x j


ư
u c
ủ
a bài tóan (P). Hãy xây d
ự
ng m
ộ
t ph
ươ
ng án c
ự
c biên m
ớ
i t
ố
t h
ơ
n
x
′
.

Câu 2. Cho bài tóan Quy h
ọ
ach tuy
ế
n tính mà ta g
ọ
i là bài tóan (P)
= − − + →

ự
c biên t
ố
i
ư
u c
ủ
a bài tóan (P).
2)

Vi
ế
t bài tóan
ñố
i ng
ẫ
u c
ủ
a bài tóan (P) và tìm ph
ươ
ng án t
ố
i
ư
u c
ủ
a bài tóan
ñố
i ng
ẫ

1)

Li
ệ
t kê t
ấ
t c
ả
các ph
ươ
ng án c
ự
c biên c
ủ
a bài toán (P).
2)

Ch
ứ
ng t
ỏ
bài toán có ph
ươ
ng án t
ố
i
ư
u. T
ừ


a bài toán
ñố
i
ng
ẫ
u.
Câu 4.
M
ộ
t xí nghi
ệ
p d
ự

ñị
nh s
ả
n xu
ấ
t ba lo
ạ
i s
ả
n ph
ẩ
m A, B và C. Các s
ả
n ph
ẩ
m này

ệ
u c
ầ
n
ñể
s
ả
n xu
ấ
t m
ộ
t
ñơ
n v
ị
s
ả
n ph
ẩ
m A, B, C
ñượ
c cho
ở
b
ả
ng
sau
ñ
ây


f(x) x 2x 3x min
6x 3x 2x 20
2x 6x 3x 25
x 0; j 1,3.
= + +
+ +


+ +

=

1)

Phỏt bi

u bi toỏn
ủ
i ng

u c

a bi toỏn trờn .
2)

Hóy gi

i m

t trong hai bi toỏn r

n ngoi tr

i. Nguyờn li

u
ủ
s

n xu

t g

m hai
lo

i A, B v

i tr

l

ng l 6 t

n v 8 t

n t

ng

ng.

n xu

t m

t t

n s

n ngoi tr

i c

n 1 t

n nguyờn li

u A v
2 t

n nguyờn li

u B. Qua
ủ
i

u tra th

tr

ng cụng ty bi

t l 2000 USD, giỏ bỏn m

t t

n s

n ngoi tr

i l
3000 USD.
H

i c

n s

n xu

t m

i lo

i s

n bao nhiờu t

n
ủ
cú doanh thu l



c)

30

40 50 60
80

1

30
5

40
7

10
2
45

5 7 4

40
9
5
55

12 2 3 6

55

u.
3

2) Xuất phát từ phương án trên hãy xây dựng một phương án mới tốt hơn (chỉ cần một
phương án mới tốt hơn).

Câu 9. Cho bài tóan vận tải cân bằng thu phát hàm mục tiêu cước phí max và phương án (phương án
ñược xây dựng bằng phương pháp góc Tây – Bắc)

60

40 50 60
50

10
50
5

17

2
75

5
10
7
40
4
25



100 200 30 60
10

50

40
30
50
Câu 11. Cho bài tóan vận tải:

80

20 60
50

5 4 2

40

3 6
70

7 9 Trong ñó ô(2,1) và ô(3,3) là ô cấm, tức là tuyến ñường từ nơi phát hàng thứ 2 ñến nơi nhận hàng thứ
1 và tuyến ñường từ nơi phát hàng thứ 3 ñến nơi nhận hàng thứ 3 không thể ñi qua ñược.
4



70 20
80

10
20

9
60

2

30

4

3
10
1
20
20

2
20
6 2 2
1) Hỏi các phương án này có phải là các phương án cực biên không suy biến?
2) Hỏi phương án nào là phương án tốt hơn?
3) Kiểm tra tính tối ưu của các phương án.
Câu 14. Một nhà máy chế biến thịt, sản xuất ba loại thịt: bò, lợn, cừu, với tổng lượng mỗi ngày là
480 tấn bò; 400 tấn lợn; 230 tấn cừu. Mỗi loại ñều có thể bán ñược ở dạng tươi hoặc nấu chín. Tổng
lượng các loại thịt nấu chín ñể bán trong giờ làm việc là 420 tấn. Ngoài ra nấu thêm ngoài giờ 250
tấn (với giá cao hơn). Lợi nhuận thu ñược trên một tấn ñược cho bằng bảng sau: (với ñơn vị là triệu
ñồng)
5 Tươi Nấu chín

Nấu chín
ngoài giờ
Bò 8 11 14
Lợn 4 7 12
Cừu 4 9 13

Mục ñích của nhà máy là tìm phương án chế biến ñể làm cực ñại lợi nhuận. Hãy tìm phương án
chế biến ñó.

Đề thi tham khảo (Thời gian làm bài 60 phút)


1,2,0,3
x = là phương án cực biên, tối ưu của bài tóan (P).
b) Viết bài tóan ñối ngẫu của bài tóan (P) và tìm phương án tối ưu của bài tóan ñối ngẫu.

Câu II: (4
ñ
i
ể
m)
Một gia ñình cần ít nhất 1800 ñơn vị prôtêin và 1500 ñơn vị lipit trong thức ăn
mỗi ngày. Một kilôgam thịt bò chứa 600 ñơn vị prôtêin và 600 ñơn vị lipit, một kilôgam thịt heo
chứa 600 ñơn vị prôtêin và 300 ñơn vị lipit, một kilôgam thịt gà chứa 600 ñơn vị prôtêin và 600
ñơn vị lipit. Giá một kilôgam thịt bò là 80 ngàn ñồng, giá một kilôgam thịt heo là 75 ngàn ñồng,
giá một kilôgam thịt gà là 90 ngàn ñồng.
Hỏi một gia ñình nên mua bao nhiêu kilôgam thịt mỗi loại ñể: bảo ñảm tốt khẩu phần ăn
trong một ngày và tổng số tiền phải mua là nhỏ nhất?

Câu III: (3
ñ
i
ể
m)
Giải bài tóan vận tải cân bằng thu phát sau:

j
i
40

45 60 65
90