, B
ộ
CÔNG THƯƠNG
B
ộ
M
Ô
N QUY HO
Ạ
CH TUY
É
N T
Í
NH
TI
Ẻ
U LU
Ậ
N
Ĩ
HU
Í
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HÒ CHÍ MINH
HO CHI UNH UMVBBITY Cf INDLSTSY
KHOA KHOA HỌC cơ BẢN
■d
\
Viện Công nghệ Sinh học - Thực phẩm
TP. HCM, ngày 25
tháng 4 năm 2009
Lớ
p
: 211301202
GVHD : TS. Võ Văn Tu
ấ
n Dũng
1. Nguy
ễ
n Trung Nhân 0771637
2. Mai Hạnh Nguyên 0770613
3. Huvnh Thành Trung 0771757
4. H
Thị Thanh Hi
u0771725
5. Dưong Thị Hà Như0771496
6. Cao Thị Ngọc Tuv
ề
n0770834
7. Mai Nguy
ễ
n Thục Hi
ề
n0770770
8. Vũ Kim H
ư
ờng 0771102
Æ
LỜI MỞ ĐẦU
1. Lv do chọn đề tài
Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những
quyết định quan trọng đê đưa ra những phương án hoặc chiến lược tốt nhất trong sản xuất
kinh doanh hay trong một trò chơi mà đối thủ là một kẻ thông minh và nguy hiêm...Khi đó
ta cần phải lập mô hình toán học quy hoạch tuyến tính đê có được phương án tối ưu cần
thiết.
Trong đó phương pháp đơn hình được George Bemanrd Dantzig đưa ra năm 1947
cùng lúc với việc khai sinh ra quy hoạch tuyến tính, phương pháp này thực sự có hiệu quả
đê giải những bài toán quy hoạch tuyến tính cỡ lớn trong thực tế mà ta thường gặp, như đế
vận chuyển hàng hóa đầy đủ nhưng có tong chi phí là nhở nhất
- đây chính là bài toán vận tải. Hoặc trong kinh doanh phải lập kế hoạch sản xuất đối với
các nguyên liệu và sản phẩm đê thu được tổng lợi nhuận là lớn nhất...
Kiến thức sau khi học quy hoạch tuyến tính rất cần thiết, đây là những kiến thức rất
quan trọng đê xây dựng một mô hình toán học cho bất kỳ bài toán phức tạp nào trong thực
tế, chỉ cần xây dựng các thuật toán đã mô hình hóa ngôn ngữ nhờ việc lập trình trên máy
tính ta có thê giải quy hoạch tuyến tính một cách dê dàng nhanh chóng và chính xác. Như
vậy việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn
nếu biết lập các mô hình và tính toán đúng quy cách.
2. Đối tượng nghiên cứu và phương pháp nghiên cứu.
Quy hoạch tuyến tính là lĩnh vực nghiên cứu các bài toán tối ưu mà hàm mục tiêu là
vấn đề được quan tâm nhất và các ràng buộc là các yêu cầu ,điều kiện của kế hoạch đặt ra,
đều là hàm và các phương trình, bất phương trình tiiyến tính. Các bước đê nghiên cứu và
ứng dụng một bài toán quy hoạch tuyến tính điên hình là:
■ Xác định vấn đề cần giải quyết, thu thập dữ liệu .
ịy,
7=1
Với hệ ràn
g
buộc:
(3)
m
■ Xây dựng các thuật toán đê giải bài toán trên các lập trình máy tính.
■ Tính toán thử và điều chỉnh mô hình nếu cần .
■ Áp dụng đê giải các bài toán thực tế .
CHƯƠNG 1:
BÀI TOÁN QUY HOẠCH TUYỂN TÍNH
A. LÝ THUYẾT
1. ĐỊNH NGHĨA
Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng:
Tìm Xj, j=l,2,...,n sao cho: f=Vớjc. -»min(max) (1)
7=1
bị, i=l,2,...,m (2)
>0
<0
tùyỷ
(1) được gọi là hàm mục tiêu, nó có thể là cực tiểu (min) hay cực đại (max).
(2) được gọi là các ràng buộc chung hay ràng buộc hàm, nó có thế có dạng bất đẳng
thức (< hay >) hoặc có dạng đang thức (=).
(3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (>0), không dương
(<0) hay tùy ý.
Như vậy, bài toán QHTT là bài toán có các biêu thức xác định hàm mục tiêu và các
ràng buộc chung đều ở dạng tuyến tính.
Véctơ x=(Xị, x2,...,xn) được gọi là phưong án (pa) hay lời giải chấp nhận được của
bài toán QHTT nếu nó thoa mãn hệ ràng buộc của bài toán.
Phương án x*=(x,\j^,...,j^)rđược gọi là phương án tối ưu (patir) hay lời giải tối ưu,
nghiêm tối ưu của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất.
■ Lập mô hình toán học thật chính xác.
Æ
Tức là: f(x*)=XC,*; f(x) = ỴJCJXJ là giá trị hàm mục tiêu tại phương án
7=1 L-J
j
=1
x=(xl5x2,...,xn)T bất kỳ. (Dấu < ứng với bài toán cực tiểu. Dấu > ứng với bài toán cực đại).
Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nêu có).
Hai bài toán QHTT được gọi là tương đương với nhau riếu chúng có chung tập hợp
các phương án tối ưu.
Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu)
f(x)—»maxíg(x)=‐f(x)—>•min
0)0 v (2)
X G X [xeX
(Trong đó: X là tập hợp các phương án)
Tức là: nếu đồi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài toán tương
đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta chỉ xét bài toán có loại
hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm mục tiêu là cực đại)
2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH TUYÉN TÍNH
2 BIÉN
Bài toán có dạng: tìm x=(xi,x2)t sao cho f(x)=cix1+c2x2“^ min (max)
Với hệ ràng buộc: ailx1+ai2x2>bi, i=l,2,...,m Chú ý:
- Ràng buộc chung có dạng: a<b, ta đưa về dạng tương đương là: -a>-b.
- Ràng buộc chung có dạng: a = b thì tương đương với: a>b và -a>-b.
- Còn các ràng buộc biến có thê xem là các trường hợp riêng của các ràng buộc
chung.
Như vậy, hệ ràng buộc của bài toán QHTT có 2 biến luôn luôn có thê giả thiết là có
dạng: a¡iXi+ai2X2>b¡; i=l, 2..., m
2.1. Xác định miền phương án
Đưa các điểm (xi,x2) lên hệ trục tọa độ vuông góc. Ta xác định được các điểm thỏa
mãn phương trình: a¡1x1+ai2x2=b, hình thành nên một đường thẳng chia mặt phang tọa độ thành
2 nửa mặt phăng (mp). Một nửa mp bao gồm các điêm (xi, X-)) thỏa mãn bất phương trình:
a¡1x1+a¡2x2>bi, và nửa kia bao gồm các điêm (X], x2) thỏamãnbấtphươngtrình:aj|Xi+a¡2X2<bj.
4
n
Với hệ ràn
g
buộc: ^a.ịXị = bị,i=l,2,...,
m
Trong thực hành, đê xác định nửa mp nào ứng với bất phương trình: aj|Xi+ai2X2>bị. Ta
thường lấy một điêm đặc biệt như (0,0); (0,1); (1,0);... thay vào bất phương tình, nếu nó thỏa mãn
thì nửa mp chứa điểm đặc biệt đó là nửa mp phải tìm; còn nếu nó không thỏa mãn thì nửa mp
phải tìm là nửa mp không chứa điêm đặc biệt đó.
Các điêm thỏa mãn hệ ràng buộc của bài toán là các điêm thuộc miền giao của các nửa
mp xác định các bất phương trình tương ứng, nó tạo nên một hình đa giác lồi có the bị giới nội
hay không bị giới nội; hoặc miền giao là rồng ứng với trường hợp hệ ràng buộc không tương
thích. Trường hợp miễn phương án X không rỗng ta thực hiện tiếp bước sau.
2.2. Xác định phưong án tối ưu Một điểm X=(X|,X2)T bất kỳ nằm trong mp tọa độ
sẽ cho ta giá trị hàm mục tiêu là: C|X1+C2X2 =f.
Tập hợp tất cả các điếm có cùng giá trị hàm mục tiêu là f hình thành nên một
đường thẳng vuông góc với véctơ oc với C=(ci,c2)t. Đường thẳng này được gọi là đường thẳng
mục tiêu có mức là f.
Đặc điểm của các đường thẳng mục tiêu là: nếu tịnh tiến đường thăng mục tiêu theo
cùng hưởng vectơ oc thì giá trị hàm mục tiêu sẽ tăng lên. cỏn nếu tịnh tiến theo hưởng ngược
với vectơ oc thì giả trị hàm mục tiêu sẽ giảm đi.
3. CÁCH ĐƯA BÀI TOÁN QHTT BÁT KỲ VÈ DẠNG CHÍNH TÁC Bài toán
qhtt dạng chỉnh tăc là bài toán qhtt cỏ tất cả các ràng buộc chung đều ở dạng đăng thức và tất
cả các biến đều không âm.
n
Tức là bài toán có dạng: f=^c
-Xj
-» min (max)