Tiểu luận về bài toán Quy Hoạch Tuyến Tính
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...
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
thực tiển của tối ưu hóa. Sự ra đời của quy hoạch tuyến tính nói riêng và quy hoạch
toán học nói chung có thể coi vào năm 1939.
Nội dung của môn học nhằm đáp ứng được yêu cầu cung cấp những kiến
thức và thuật toán cơ bản của quy hoạch tuyến tính. Phương pháp đơn hình và
thuật toán của nó, do Dantzig đề xuất năm 1947, cho đến ngày nay vẫn được coi là
phương pháp tổng quát và được sử dụng nhiều nhất để giải bài toán quy hoạch
tuyến tính.
Có những phương pháp khác nhau để giải bài toán vận tải, tuy nhiên thuật
toán của chúng có tên gọi là thuật toán thế vị.
Các kiến thức của chương I
- Trang 1 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
Dạng tổng quát của bài toán quy hoạch tuyến tính :
Tìm vectơ x* = ( x1, x2, …, xn ) sao cho tại đó
n
f ( x) = ∑ cj xj (1)
j =1
⎧ n
∑a ( 2) trong ñoù I ⊂ M= {1,2,...,m}
i∈I
x = ai ,
⎪ ij j
⎪ j =1
⎪ m
∑a ( 3)
j ∈ I' I' = M \ I
x = bj ,
⎨ ij j
⎪ i =1
( 4) J ⊂ N= {1,2,...,n}
⎪ xj ≥ 0 , j∈ J
⎪
⎩
f(x) là hàm mục tiêu; các ràng buộc (2) và (3) là ràng buộc cưỡng bức; ràng
buộc (4) là ràng buộc tự nhiên.
Mỗi vectơ x* = ( x1, x2, …, xn ) là một phương án.phương án mà tại đó hàm
mục tiêu đạt giá trị nhỏ nhất ( lớn nhất ) gọi là phương án tối ưu. Khi đó x* là giá
trị tối ưu của hàm mục tiêu trên tập hợp các phương án.
Đối với bài toán quy hoach tuyến tính đòi hỏi giá trị của hàm mục tiêu đạt
giá trị nhỏ nhất ( hoặc lớn nhất ) ta nói bài toán cực tiểu hay bài toán dạng min (
hoặc bài toán cực đại hay bài toán dạng max ). Phương án x* đượ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:
f ( x ) = max f ( x ) ⇔ - f ( x ) = min ⎡ - f ( x ) ⎤
x∈X ⎣ ⎦
x∈X
Viết dưới dạng gọn hơn
n
f ( x ) = ∑ c j x j ⎯⎯ Min
→
j =1
⎧ n
∑a x ≥ ai , i∈I
⎪ ij j
⎪ j =1
⎪ m
∑a j ∈ I'
x = bj ,
⎨ ij j
⎪ i =1
⎪ xj ≥ 0 , j∈ J
⎪
⎩
Đưa ra một số kí hiệu và quy ước:
+ A là ma trân cỡ (m,n) thì Ai = ( ai1,ai2, … , ain ) là vectơ dòng thứ i của A;
Aj = ( a1j,a2j, … , amj ) là vectơ cột thứ j của A.
- Trang 2 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
+ Nếu A = ( aij ) và B = ( bij ) là hai ma trận cùng kiểu thì A ≥ B hiểu là
aij ≥ bij ∀ i,j.
+ Nếu c = ( c1, c2, … , cn ) và x = ( x1, x2, … , xn )là hai vectơ nào đó
n
thì biểu thức: c, x = ∑ c j x j được gọi là tích vô hướng của hai vectơ c và x
j =1
⎛ ⎞
n
Xem c và x là hai ma trận cột thì t cx = ⎜ ∑ c j x j ⎟ là ma trận cấp 1,
⎝ ⎠
j =1
trong đó c là ma trận chuyển vị của c ( còn có thể kie hiệu là ct hay cT ) đẻ
t
n
gọn ta quy ước t cx = ∑ c j x j = c, x
j =1
Dạng chính tắc và chuẩn tắc của bài toán quy hoạch tuyến tính:
a./ Nếu I = ∅ và J = N thì ta có bài toán quy hoạch tuyến tính dạng chính
tắc. nó có dạng:
f ( x ) = t cx ⎯⎯⎯ Min
→
trong đó : b = ( b1,b2, …,bm )
⎧ Ax ≥ b A là ma trận ràng buộc
⎨
⎩ x≥0
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:
f ( x ) = t cx ⎯⎯⎯ Min
→
⎧ Ax ≥ b
⎨
⎩ x≥0
Bằng phép biến đổi ta có thể đưa bài toán quy hoạch tuyến tính bất kì về
dạng chính tắc hoặc chuẩn tắc cụ thể :
Mỗi phương trình Aix = bi được thay bởi bằng hệ hai bất phương trình
Aix ≥ bi và - Aix ≥ - bi
Mỗi bất phương trình Aix ≥ bi được thay bởi bằng hệ
Aix – xn+1 = bi và xn+1 ≥ 0 trong đó xn+1 ẩn bù
Mỗi bất phương trình Aix ≤ bi được thay bởi bằng hệ
Aix + xn+1 = bi và xn+1 ≥ 0 trong đó xn+1 ẩn bù
Mỗi ẩn xj không ràng buộc về dấu đều có thể viết thành hiệu hai hai ẩn mới
không âm: x j = x ,j - x ,,j ; x ,j ≥ 0 ; x ,,j ≥ 0 .
Nếu ẩn xj có điều kiện xj ≤ 0 thì đặt xj = -tj với tj ≥ 0
Giải bài toán quy hoạch tuyến tinh bằng phương pháp đồ thị:
Xét bài toán quy hoach tuyến tính :
- Trang 3 -
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
f (x ) = ∑ c j x j
2
∑a x j ≥ bi
với các ràng buộc
j =1 ij
j =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 f (x ) 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ô
hình toán học và tìm phương án cho bài toán kinh tế ta thực hiện giải các bài toán
sau:
Bài 1: ( bài 1 chương I trong giáo trình quy hoạch tuyến tính trang 22)
Giải
Nguyên liệu A Nguyên liệu B Danh thu
Hàng loại I 2 3 7 đơn vị tiền
Hàng loại II 1 4 5 đơn vị tiền
Tổng 6 8
Gọi x1 và x2 là số hàn loại I và II cần sản xuất theo kế hoạch trong 1 ngày,
khi đó danh thu trong 1 ngày là f(x) = 7x1 + 5x2 . do trữ lượng nguyên liệu có hạn
và lượng hàng sản xuất không vước quá nhu cầu thì trường ta có các ràng buộc
2x1+x2 ≤ 6 ; 3x1 + 4x2 ≤ 8 ; x1 ≤ 2 ; x1 – x2 ≤ 1 và x1, x2 ≥ 0 .
Từ đó ta có mô hình toán học của bài toán là
f(x) = 7x 1 + 5x ⎯ Max
⎯→
2
⎧2x 1 + x 2 ≤ 6
⎪
⎪3x 1 + 4x 2 ≤ 8
⎪
≤2
⎨ x1
⎪ x - x ≤1
⎪1 2
⎪ x1 , x 2 ≥ 0 .
⎩
Bài 2: ( bài 2 chương I trong giáo trình quy hoạch tuyến tính trang 22)
Giải
- Trang 4 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
Gọi xj ≥ 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
n
∑ x jα j ≤ M
về trọng lượng M nên và tổng giá thành là lớn nhất
j =1
n
f = ∑ x j β j ⎯ Max . Từ đó ta có mô hình toán học của bài toán vận tải.
⎯→
j =1
n
f = ∑ x j β j ⎯ Max
⎯→
j =1
⎧n
⎪ ∑ x jα j ≤ M
⎨ j =1
⎪x j ≥ 0
⎩
Bài 3: ( bài 3 chương I trong giáo trình quy hoạch tuyến tính trang 22)
Giải
Gọi S là tổng số máy sản xuất theo kế hoạch. xij là số đơn vị thời gian dành
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:
n
f = ∑ a ij xij = kS
j =1
⎧x ≥ 0
⎪ ij
⎨
⎪S ≥ 0
⎩
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./ f (x ) = 48x1 + x 3 ⎯ min
⎯→
⎧2x 1 + x + x ≥ 5
⎪ 2 3
⎪x 1 − x 2 + x 3 ≥ 1
⎪
⎨
− x 3 ≥ −3
⎪4x 1
⎪
x1 ≥ 0
⎪
⎩
x*=( 0,2,3 )
Giải
Tập X ≠ φ vì x*∈ X. với x*=( x1,x2,x3 ) 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ó 7x1 + x3 ≥ 3 .
Thay x*=( 0,2,3 ) vào thỏa mãn và thay vào hàm cơ bản ta có f(x*) = 3
nên 7x1 + x3 ≥ 3 = f(x*) với mọi phương án.
Vậy x*=( 0,2,3 ) là phương án tối ưu
- Trang 5 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
f (x ) = x 2 + x 4 ⎯ min
b./ ⎯→
⎧− x 1 + 2x 2 + x 3 + x 4 = 1
⎪
⎪− 2x 1 + x 2 + x 3 + x 4 = 2
⎨
+ 2x 4 = 3
3x 2
⎪
⎪x ≥ 0
⎩1
x* = ( 0,-1,0,3 )
Giải
Tập X ≠ φ vì x*∈ X. với x*=( x1,x2,x3,x4 ) 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ó : -3x1 + 6x2 + 2x3 + 4x4 =6 .
Thay x*=( 0,-1,0,3 ) vào thỏa mãn và thay vào hàm cơ bản ta có f(x*) = 6
nên -3x1 + 6x2 + 2x3 + 4x4 = 6 = f(x*) với mọi phương án
vậy x* = ( 0,-1,0,3 ) là phương án tối ưu.
Bài 5: ( bài 5 chương I trong giáo trình quy hoạch tuyến tính trang 23)
f (x ) = 3x 1 - x 2 ⎯ max
a./ ⎯→
(1)
⎧ x1 + x 2 ≥ 2
⎪
(2)
⎪− x 1 + x 2 ≤ 2
⎨
(3)
⎪ x 1 − 2x 2 ≤ 2
⎪x ≥ 0 , x ≥ 0
⎩1 2
Giải
Nhân (-1) vào 2 vế của (1) và cộng các vế của các ràng buộc
Ta có: -x1 – 2x2 ≤ 2 có vô số nghiệm.
Suy ra hệ ràng buộc có vô số nghiệm.
Vậy hàm mục tiêu không bị chặn.
f (x ) = x 1 - x 2 ⎯ min
b./ ⎯→
(1)
⎧ 2x 1 − x 2 ≥ 2
⎪
(2)
⎪ 2x 1 + x 2 ≥ 2
⎨
(3)
⎪ x 1 − 3x 2 ≤ 3
⎪ x ≥ 0, x ≥ 0
⎩1 2
Giải
Nhân (-1) vào 2 vế của (1) , (2) và cộng các vế của các ràng buộc
Ta có: -3x1 – 3x2 ≤ 3 có vô số nghiệm
Suy ra hệ ràng buộc có vô số nghiệm.
- Trang 6 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
Vậy hàm mục tiêu không bị chặn.
Bài 8: ( bài 8 chương I trong giáo trình quy hoạch tuyến tính trang 24)
a./ -x1 + x2 ⎯ → min
⎯ C
B
(1)
D
⎧ - 2x 1 + x 2 ≤ 2 A E
⎪
(2)
⎪ x1 - x 2 ≤ 2
⎨
(3)
⎪ x1 + x 2 ≤ 5
⎪ x ≥0,x ≥0
⎩1 2
biểu diễn đồ thị các bất đẳng thức lên hệ trục tọa độ ta được miền các
phương án là hình ngũ giác ABCDE. Các điểm coa tọa độ như sau A(0,0); B(0,2);
C(1,4); D(4,1); E(2,0) là các cực biện. lầm lược thay các cực biện vào hàm mục
tiêu ta có f(A) = 0; f(B) = 2; f(C) = 3; f(D) = -3; f(E) = -2.
Vậy phương án tối ưu x*=(4,1) tại đó hàm mục tiêu đạt giá trị Min
Bài 9: ( bài 9 chương I trong giáo trình quy hoạch tuyến tính trang 24)
Giải : x1+ x2 ⎯ → Max
⎯
⎧ 2x 1 + x 2 − x =1
⎪ 3
⎪
+ x4 = 0
⎨ x1 - x 2
⎪
⎪ x1 ≥ 0 , x 2 ≥ 0
⎩
PHẦN III: KẾT LUẬN
Qua các kiên thức về quy hoạch tuyến tính và trên cơ sở những bài tập về
vận dụng kiến thức tôi nhận thấy rằng đây là một môn học vận dụng nhiều kiến
thức. đối với môn học này, nhằm giúp đỡ người nghiêm cứu biết tìm ra phương án
tối uư cho một kế hoạch cần thực hiện.
Qua tiểu luận này, nếu có thời gian nghiêm cứu tôi sẽ thực hiện một cách cụ
thể hơn và kiếm thức tìm hiểu sẽ rộng hơn. Tuy nhiện trong quá trình nghiệm cứu
vẫn còn những vấn đề sai xót xin được sự góp ý. Chân thành cảm ơn.
- Trang 7 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
1./ KẾT LUẬN.
2./ KIẾN NGHỊ.
Quy hoạch tuyến tính là một bộ phận cơ bản và có nhiều ứng dụng trong
thực tiển của tối ưu hóa. Sự ra đời của quy hoạch tuyến tính nói riêng và quy hoạch
toán học nói chung có thể coi vào năm 1939.
Nội dung của môn học nhằm đáp ứng được yêu cầu cung cấp những kiến
thức và thuật toán cơ bản của quy hoạch tuyến tính. Phương pháp đơn hình và
thuật toán của nó, do Dantzig đề xuất năm 1947, cho đến ngày nay vẫn được coi là
phương pháp tổng quát và được sử dụng nhiều nhất để giải bài toán quy hoạch
tuyến tính.
Có những phương pháp khác nhau để giải bài toán vận tải, tuy nhiên thuật
toán của chúng có tên gọi là thuật toán thế vị.
Cơ sở lí luận của thuật toán thế vị là trường hợp riêng của thuật toán đơn
hình. Lí thuyết đối ngẫu là một vấn đề rất quan trọng của quy hoạch tuyến tính.
Để giải quyết một cách có hiệu quả bài toán, 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 sát và sự liên quan cần phỉa tôn trọng giữa chúng; ngoài ra, đương
nhiên cần chỉ rõ mục tiêu 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ệ các phương trình và bất phương trình, cói đó 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 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.
Tư tưởng tối ưu hóa đã có từ xa xưa,
con người đã tìm đến cách sản xuất và trao đổi làm sao để cho lợi nhậm cao
mà tốn ích chi phí sản xuất cũng như vận chuyển.
2./ MỤC ĐÍCH NGHIÊN CỨU.
- Trang 8 -
Tiểu luận về bài toán Quy Hoạch Tuyến Tính Người viết: Tô Thanh Hiền
3./ ĐỐI TƯỢNG NGHIÊN CỨU.
4./ KHÁCH THỂ NGHIÊN CỨU.
5./ PHẠM VỊ ĐỀ TÀI.
4./ THỰC TIỂN.
5./ BIỆN PHÁP.
- Trang 9 -