TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HỒ CHÍ MINH
KHOA CƠ BẢN


Bài tiểu luận
Môn:
QUI HOẠCH TUYẾN TÍNH
Đề tài: ĐỀ SỐ 1

GVHD: ThS Nguyễn Đình Tùng
Lớp học phần : 211301204
Nhóm : I
Năm học :2008-2009
TP.Hồ Chí Minh, ngày 22 tháng 5 năm 2009


TIỂU LUẬN MÔN TOÁN CHUYÊN ĐỀ
QUY HOẠCH TUYẾN TÍNH
Đề tài 1
1.Bài toán khẩu phần ăn:
1.1.Phát biểu và lập mô hình bài toán:
1.1.1.Phát biểu:
Có n loại thực phẩm TP
1
,TP
2
,…,TPn.Gía tiền của một đơn vị
khối lượng các loại thực phẩm này lần lượt là c
1
,c
2

n
x
n
.
Lượng chất dinh dưỡng loại I có trong khẩu phần này là:
∑
=
n
j
j
j
i
xa
1
.
Từ đây ta có bài toán:Tìm giá trị nhỏ nhất của hàm
f = c
1
x
1
+ c
2
x
2
+…+ c
n
x
n
Với điều kiện:
∑

Trong một tháng một con gà cần tối thiểu 90g thành phần A,48g thành
phần B và 1,5g thành phần C.
Hãy tìm số lượng mỗi loại thức ăn cần mua để có thể đảm bảo đủ nhu
cầu tối thiểu về dinh dưỡng cho một con gà với giá rẻ nhất.
Lập mô hình bài toán:
Gọi x1,x2 lần lượt là số lượng đơn vị thực phẩm loại 1 và loại 2 cần
cho một con gà trong một tháng.
Hàm mục tiêu của bài toán này là hàm cực tiểu giá mua
Min f = 2x
1
+ 3x
2
Thành phần A: 5x
1
+ 10x
2
≥ 90
Thành phần B: 4x
1
+ 3x
2
≥ 48
Thành phần C: 0,5x
1
≥1,5
x
1
,x
2
≥ 0

1
+ 10x
2
= 90
(D2): 4x
1
+ 3x
2
= 48
(D3): 0,5x
1
= 1,5
(D4): x
1
= 0
(D5): x
2
= 0
Dùng đường thẳng đề xác định fmin.Đường thẳng chi phí càng gần gốc
O,f càng nhỏ.
Đường thẳng phí qua điểm B cho ta fmin.Tọa độ điểm B là nghiệm của
hệ phương trình




=+
=+
4834
90105

-Các điểm đỉnh là giao điểm của các ràng buộc nằm trong không gian lời giải
gọi là các đỉnh của không gian lời giải.
-Một kết quả quan trọng trong lý thuyết qui hoạch tuyến tính là: Nếu bài toán
QHTT có lời giải tối ưu thì lời giải sẽ nằm trên các đỉnh của không gian lời
giải.
-Áp dụng kết quả này điểm tìm giá trị của hàm mục tiêu bằng cách so sánh giá
trị của các đỉnh của không gian lời giải.
Bài giải :
So sánh giá trị tại 3 đỉnh A,B,C:
Đỉnh A (18;0)
⇒
fminA = 2 × 18 + 3 × 0 = 36
Đỉnh B (8,4;4,8)
⇒
fminB = 2 × 8,4 + 3 × 4,8 = 31,2
Đỉnh C (3;12)
⇒
fminC = 2 × 3 + 3 × 12 = 42
⇒
fmin=fC=31,2
⇒



=
=
8,42
4,81
x
x

1
21
21
x
xx
xx
⇒



≤++
≤++
30310
25.045
321
321
yyy
yyy
x
1
, x
2

0
≥
y
1
, y
2


2

0
≥
Ta có bảng đơn hình:

90 48 2 0 0
Cơ
sở
Hệ số P.án y
1
y
2
Y
3
y
4
y
5
A
4
0 2 5 4
2
1
1 0
A
5
0 3 10 3 0 0 1
-90 -48 -
2

0 9
A
2
48
5
1
0 1
5
1

5
2
-
5
1
A
1
90
25
6
1 0 -
50
3
-
25
3

25
4
0 0







310
45
^-1
= ( 90, 48 ) ×
25
1
−
×






−
−
510
43

= ( 90, 48 ) ×





giá trị tối ưu của bài toán gốc: f(x) = 2 ×
5
42
+ 3 ×
5
24
=
5
156

Kết quả này phù hợp với kết quả của cách giải bài toán bằng phương pháp
giải trên.
2.Bài toán vận tải không cân bằng thu phát(cung lớn hơn cầu)
Trong toán học, Bài toán vận tải (tiếng Anh: transportation problem) là một
dạng của bài toán quy hoạch tuyến tính. Bài toán vận tải có thể biểu diễn như
một đồ thị hai phía, có hướng. Nó có thể ứng dụng vào nhiều vấn đề khác
nhau. Giải thuật đơn hình trên bài toán vận tải cũng đơn giản hơn.
Biểu diễn đồ thị của bài toán vận tải
2.1.Phát biểu và lập mô hình bài toán:
Có m kho hàng với lượng hàng dự trữ tương ứng là a
1
,a
2
, ,a
m
và n nơi tiêu thụ
với yêu cầu tương ứng là b
1
,b
2

1
, i=1…m.
Lượng hàng nhận về nơi tiêu thụ j:
∑
=
m
i
ij
x
1
, j=1…n.
Như vậy ,bài toán vận tải được phát biểu như sau:
Tìm các số x
ij
(i=1…m, j=1…n) sao cho f=
∑
=
m
i 1
∑
=
n
j
ijij
xc
1
→
min
Trong đó


(1-1)
Bài toán vận tải là bài toán Qui hoạch tuyến tính dạng chính tắc có m × n ẩn
số, m + n phương trình ràng buộc trong đó mỗi ẩn số xuất hiện đúng hai lần
với hệ số bằng 1.Sự khai triển chi tiết của hệ phương trình rang buộc trong (1-
2) cho rõ điều này.
i = 1: x
11
+x
12
+…+x
1n
= a
1
i = 2: x
21
+x
22
+…+x
2n
= a
2
… …
i = m: x
m1
+x
m2
+…+x
mn
= a
m (1-

trong hệ
phương trình ràng buộc ta có:
Cột A
11
A
1n
A
21
A
2n
A
m1
A
m+n

↑

↑

↑

↑

↑

↑
A=




0 00 0 001 11
nmdòng
mdòng
mdòng
dòng
+→
+→
→
→
1
1
(1-
3)
Ngoài ra, đặt A
ij
là cột hệ số của ẩn x
ij
(i=1…m,j=1…n) thì các thành phần của
A
ij
hầu hết bằng 0, trừ hai số 1 ở dòng thứ I và dòng thứ m+j:
Là các vecto trong không gian R
m+n
A
ij =







0
0

1

0
nmdòng
jmdòng
mdòng
mdòng
idòng
dòng
+→
+→
+→
→
→
→
1
1
(1- 4)
Là các vecto trong không gian R
m+n
Mỗi phương án của bài toán vận tải là một ma trận cấp m×n : X =
[ ]
j
i
x
2.1.3. Cân bằng cung cầu

j
b
1

thu 85 75 70 60 45
phát
80 8 2 5 4 12
110 7 5 6 8 10
90 4 11 10 9 6
120 6 3 12 7 5
2.3.Gỉai ví dụ trên.Trong khi giải ví dụ này hãy lập nhiều phương án ban
đầu khác nhau
Bài tâp:
Cho bài toán vận tải không cân bằng thu phát.Đây là bài toán không
cân bằng thu phát, nên khi giải bài toán này ta thêm vào môt trạm thu giả.
Ta có bảng như sau;
Bảng 1:
85 75 70 60 45 65
80 8 2 5 4

12 0
110 7 5 6 8 10 0

90 4 11 10 9 6 0
120 6 3 12 7 5 0
Ta xây dựng phương án ban đầu như sau;
Bảng 2:
85 75 70 60 45 65
80 8 2
75

x
11 10 9 6
x
0 R3=-4
6 3 12 7
x
5
x
0
x
R4=-3
S1=0 S2=-2 S3=-3 S4=-4 S5=-2 S6=3
Bảng 4:
8 0
X
(4)
2

0

(3)x
10 3
4
0
0
x
1 5 0
x
0
x

=75-55= 20
X’
14
= 5+55= 60
X’
42
= 0+55=55
X’
44
= 55-55=0
Bảng 5:
85 75 70 60 45 65
80 8 2
20
5 4
60
12 0
110 7 5 6
70
8 10 0
40
90 4
85
11 10 9 6
5
0
120 6 3
55
12 7 5
40

x
8 1
4 2 0
x
3 5 0
x
0
x
7 3 3 0
x
(2)
-1

(1)*
3 0
x
2 2
0
X(3)

0

(4)x
Ta có:
V
c
= { 5;25 }
V
l
= {0;40 }

12 7 5
45
0
20
Bảng 9:
8 2
x
5 4
x
12 0 R1=0
7 5 6
x
8 10 0
x
R2=-1
4
x
11 10 9 6 0
x
R3=-1
6 3
x
12 7 5
x
0
x
R4=-1
S1=-3 S2=-2 S3=-5 S4=-4 S5=-4 S6=1
Bảng 10:
5 0