Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
MỞ ĐẦU

PHẦN I: LÝ DO.
Loài người xuất hiện trên trái đất cách đây hàng triệu năm, nhưng chỉ cách
đây khoảng 5 hoặc 6 nghìn năm con người mới bắt đầu có những hoạt động trí óc.
Từ khi ngôn ngữ ra đời con người đã biết đến những khái niệm cơ bản ban đầu về
toán học. Cùng với sự tiến bộ về kinh tế - xã hội của loài người, đã thút đẩy toán
học từng bước phát triển nhảy vọt. Nhất là khi con người biết tạo ra sản phẩm cần
thiết để phục vụ cho nhu cầu của đời sống xã hội thì việc trao đổi hàng hóa cần có
sự tính toán.
Không những thế, ngay từ khi con người biết suy nghĩ để tìm cách hành
động sao cho có lợi nhất cho mình theo những mục đích xác định. Những yêu cầu
cấp bách của sự phát triển nền kinh tế và quốc phòng lại càng làm nảy sinh những
ý tưởng tương tự. Do đó đã xuất hiện một bài toán cần phải giải quyết, đó là bài
toán về tìm phương án tối ưu.
Để giải quyết một cách có hiệu quả bài toán ấy, trước hết cần phải xây dựng
một mô hình toán học cho nó, trên đó thể hiện được bản chất của mỗi đối tượng đã
được khảo xác và sự liện quan cần phải tôn trọng giữa chúng; ngoài ra, dường như
cần phải chỉ rõ mục tiêu mong muốn đạt được. Bài toán tìm quyết định tối ưu với
mô hình toán học đã được xây dựng được gọi là bài toán quy hoạch toán học hay
bài toán tối ưu. Sự liên quan giữa các đối tượng đã được khảo sát trong quá trình
xây dựng mô hình toán học thường được thể hiện dưới dạng một hệ phương trình
và bất phương trình, coi đó như là những điều kiện ( hay ràng buộc ) không thể bỏ
qua. Nếu tất cả các hàm số có mặt trong bài toán ấy là các hàm tuyến tính thì ta có
bài toán quy hoạch tuyến tính.
ở phần quy hoạch tuyến tính này chỉ nghiên cứu về kiến thức ban đầu của
phần quy hạch tuyến tính. Đó chính là nội dung của chương I
PHẦN II: NỘI DUNG
1./ CƠ SỞ LÝ LUẬN.
Quy hoạch tuyến tính là một bộ phận cơ bản và có nhiều ứng dụng trong

ij j j
1
1
1
a = a , i I 2 trong I M= 1,2,...,m
a = b , j I 3 I = M \ In
j
m
i
n
jj
j
x
x
fx cx
=
=
=
∈⊂
∈
=
∑
∑
∑
ñoù
() { }
j

*
được gọi là phương
án tốt hơn phương án x nếu: f(x
*
) < f(x) đối với bài toán cực tiểu ( f(x
*
) > f(x) đối
với bài toán cực đại )
Giải bài toán quy hoạch tuyến tính được hiểu là tìm được dù chỉ một phương
án tối ưu; hoặc là chứng tỏ trên tập phương án hàm mục tiêu không bị chặn, tức là
hàm mục tiêu có thể nhận giá trị nhỏ tùy ý đối với bài toán dạng min ( hoặc lớn tùy
ý đối với bài toán dạng max )
Ta có thể thấy rằng:
()
()
( )
( )
xX
xX
x=max x -x=min-xfff f
∈
∈
⎡ ⎤
⎣ ⎦
⇔

Viết dưới dạng gọn hơn
()

ij j i

∈
⎨
⎪
⎪
≥∈
⎪
⎩
=
∑
∑
∑

Đưa ra một số kí hiệu và quy ước:
+ A là ma trân cỡ (m,n) thì A
i
= ( a
i1
,a
i2
, … , a
in
) là vectơ dòng thứ i của A;
A
j
= ( a
1j
,a
2j
, … , a
mj

n
)là hai vectơ nào đó
thì biểu thức:
1
,
n
j j
j
cx cx
=
=
∑
được gọi là tích vô hướng của hai vectơ c và x
¾Xem c và x là hai ma trận cột thì
1
t
n
j j
j
cx c x
=
⎛
⎜
⎝⎠
=
∑
⎞
⎟
là ma trận cấp 1,
trong đó

x 0
⎯⎯⎯→
⎧
⎨
⎩
≥
≥ trong đó : b = ( b
1
,b
2
, …,b
m
)
A là ma trận ràng buộc
b./ Nếu I
’
= ∅ và J = N thì ta có bài toán quy hoạch tuyến tính dạng
chuẩn
tắc
. nó có dạng:
()
t
fx = cx Min

Ax b

x 0

b
i
được thay bởi bằng hệ
A
i
x – x
n+1
= b
i
và x
n+1

≥
0 trong đó x
n+1
ẩn bù
Mỗi bất phương trình A
i
x
≤
b
i
được thay bởi bằng hệ
A
i
x + x
n+1
= b
i
và x

Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
()
∑
=
=
2
1
j
jj
xcxf
với các ràng buộc
i
j
jij
bxa ≥
∑
=
2
1
- 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 của tập phương án thỏa mãn các ràng buộc.
- Xác định giá trị của
( )
xf
tại các điểm cực biên.
- Suy ra phương án tối ưu
2./ THỰC TIỂN.
Trên cơ sở các kiến thức cơ bản của chương I của bài toán Quy Hoạch
Tuyến Tính nhằm vận dụng tốt các kiến thức trên vào giải các bài toán về tập mô

8 ; x
1

≤
2 ; x
1
– x
2

≤
1 và x
1
, x
2

0 .
≥
Từ đó ta có mô hình toán học của bài toán là
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
⎯→⎯
≥
≤

Gọi x
j
≥
0 là số đơn vị hàng loại j cần xếp lên máy bay. Do đề bài ràng buộc
về trọng lượng M nên và tổng giá thành là lớn nhất
. Từ đó ta có mô hình toán học của bài toán vận tải.
M
n
j
≤
∑
=1
jj
x
α
Max
n
j
∑
=
=
⎯→⎯
⎪
⎩
⎪
⎨
⎧
≥
⎯→⎯
≤

cho phân xưởng i làm chi tiết j. Theo đề bài ta có được mô hình toán học của bài
toán như sau:

⎪
⎩
⎪
⎨
⎧
≥
≥
∑
==
=
0 S

0
af
1
ij
ij
ij
x
kSx
n
j
Bài 4:
( bài 4 chương I trong giáo trình quy hoạch tuyến tính trang 22;23)
a./
()
minx 48xxf

x
*
=( 0,2,3 )
Giải
Tập X≠
φ
vì x
*
∈
X. với x
*
=( x
1
,x
2
,x
3
) là một phương án bất kì.
Cộng hai vế các bất đẳng thức ràng buộc cưỡng bức ta có 7x
1
+ x
3
3 .
c

≥
Thay x
*
=( 0,2,3 ) vào
c