Bài giảng Qui hoạch tuyến tính - Chương 2: Phương pháp đơn hình - Lê Anh Vũ
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
Chương 2 :
PHƯƠNG PHÁP ĐƠN HÌNH
Phương pháp đơn hình do G.B. Dantzig đề xuất năm 1947 cho đến hiện nay vẫn là
phương pháp được sử dụng nhiều nhất trong việc giải các bài toán qui hoạch tuyến tính.
Đối với các bài toán cỡ lớn (có thể đến hàng nghìn biến và hàng trăm ràng buộc)
phải dùng đến máy tính, phương pháp đơn hình cũng đã được kiểm nghiệm qua mấy
chục năm áp dụng là rất hiệu quả, với thời gian tính toán khá ngắn.
§1. CƠ SỞ CỦA PHƯƠNG PHÁP ĐƠN HÌNH
Phương pha
́
̀
̉
̣
́
́
̣
sau đây cua bai toá
̉
̀
a) Nêu bài toán qui hoa
phương an cưc biên tôi ưu, nghi
i giai cua bai toan.
b) Môi điêm cưc tiê
t tâp hơp lôi) la môt điê
Tinh chât a) cho phep ti
a bai toan (sô nay la hưu ha
môt phương an cưc biên (đinh) chi
la đu
Vi
cua ba
phương an hiê
tri ham muc tiêu ta
đung thi dưng qua
phương an cưc biên mơ
đinh kê vơi đinh trươc đo.
an tôi ưu hoăc phat hiên ba
Như vây, phương phap đơn hi
buôc đê tim ra đinh tôi ưu. Măc dù sô
trên thưc tê phương phap nay
đinh. Chinh điêu đo thê hiên hiê
́
̣
́
́
́
́
́
phương a
́
́
̀
cu
̣
̃
co
lơ
́
́
̣
́
̃
̀
́
í
t mô
̣
̉
̉
̀
̀
̀
̀
̉
̉
̀
́
̃
̉
̣
̉
̣
̉
̀
tuyê
́
́nh trên miền ràng buộc D
(mô
̣
̣
̣
̀
̀
̣
̉
̣
̉
̣
́
́
́
́
̀
́
́
́
cac
́
phương a
n cưc
̣
biên
i vơ
nh kê
cu
̉
̀
́
́
̀
̀
̃
̣
́
́
́
̉
́
́
̣
́
̣
̉
̉
̀
́
́
́
́
̉
n (đi
̉
̀
̉.
̀
thê
i toa
n co
́
́
nh bă
t đâ
̀
̀
mô
̣
́
̣
̀
́ (tuỳ
y)́
̉
̀
́
̣
̉
̉
̀
̀
̣
́
́
kiể
́
̣
́
̃
̉
̀
́
́
̀
́
́
́
̣
̀
̣
̣
̉
́
́
́
̣
̀
̣
̣
́
̉
̀
́
́
́
̀
̀
́
̀
́
́
́
̣
́
̃
̀
́
̣
́
́
́
́
̣
̀
̣
̉
̀
́
̀
̉
̀
́
̉
́
́
́
̀
̀
́
̀
́
̀
̣
́
́
̣
́
̣
̀
́
̃
́
̀
̉
̣
́
̀
́
̀
̉
́
́
đi
̉
̉
̀n ràng
̣
̉
̀
̉
́
̣
́
̉
̉
̀
́
́
́
́
̣
́
́
̀
chi
̉
đo
̉
̀
̉
̉
̣
̀
́
̉
̉
́
̀
́
̉
̣
u qua
̣
́
̉
phương pha
́
̀
§2. THUẬT TOÁN ĐƠN HÌNH
Để giải bìa toán QHTT (G) bằng phương pháp đơn hình ta thực hiện các bước
dưới đây.
25
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
• Bước chuẩn bị: Đưa (G) về dạng chính tắc chuẩn (N) nếu cần.
• Bước 1: Xác định PACB xo xuất phát, chỉ ra các biến và các hệ số cơ sở.
(Nếu bài toán dạng (N) thì một PACB được tìm dễ dàng từ ma trận con sơ
cấp của A – trong bảng đơn hình ở bước 2, ma trận con sơ cấp được giả
định là ma trận đơn vị cấp m tạo thành từ m dòng và m cột đầu tiên, khi đó
PACB xuất phát chính là x0 = (b1, b2, …, bm, 0, …, 0)).
• Bước 2: Lập bảng đơn hình, tính giá trị của hàm mục tiêu và các số ước
lượng ∆j.
Hệ số
cơ sở
Biến
cơ sở
x1
x2
.
.
.
xm
PA
CB
b1
b2
.
.
.
bm
x1
c1
1
0
.
.
.
0
x2 …… xm
c2 …… cm
xm+1 …… xn
cm+1 …… cn
a1,m+1 …… a1n
a2,m+1 …… a2n
λi
c1
c2
.
.
.
0
1
.
……
……
……
……
……
……
0
0
.
.
.
.
……
……
……
.
.
.
.
.
.
.
cm
0
1
am,m+1 …… amn
Bảng 1
Ở đây
f (x0)
0
0
……
0
∆
…… ∆n
m+1
f(x0) = c1b1 + c2b2 + … + cmbm;
m
c a −c ; m +1≤ j ≤ n
∆j = 0 (j=1,…, m); ∆j =
.
∑
i
ij
j
i=1
• Bước 3: Kiểm tra điều kiện tối ưu (Đối với bài toán MIN)
∆ ≤ 0
a) Nếu mọi
phương án đang xét tối ưu → STOP.
j
∆ j > 0
aij ≤ 0
b) Nếu tồn tại
mà mọi
thì hàm mục tiêu không bị chặn, do
đó bài toán đã cho vô nghiệm → STOP.
∆ j > 0
∆ j > 0
aij > 0
c) Nếu tồn tại
và với mỗi
đều có ít nhất một
thì
phương án đang xét chưa tối ưu → Làm tiếp bước 4.
• Bước 4: Cải tiến PACB đang xét để được PACB tốt hơn (Đối với bài toán
MIN)
∆ = max{∆ > 0}
xv
a) Chọn biến cơ bản mới
sao cho
để đưa vào.
v
j
26
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
b
i
λ = min{λ =
/ a > 0}
iv
xr
b) Chọn biến cơ bản cũ
sao cho
để đưa ra.
r
i
aiv
c) Tiếp theo chọn dòng thứ r làm dòng xoay, cột thứ v làm cột xoay, phần
arv
tử
làm phần tử xoay rồi biến đổi sơ cấp để được bảng đơn hình mới
với PACB mới tốt hơn.
Cách biến đổi bảng đơn hình để nhận được bảng mới và PACB mới tốt hơn
•
Đô
̉
̣
́
: biê
́
̉
mơ
́
̀
xv thay cho biê
́n cơ sở cũ là xr ở
do
̀
•
•
Đô
̉
̣
̣
sô
ng xoay:
Dong mơ
chia môi phân tư
́
cơ sở: hê
̣
́
̣
sô cr ơ dong r.
́
̉
̀
Biê
́
̉
̀
̀
́
̀
̃
/ phâ
n tư
̉
xoay,
n tư
vi tri
t:
t xoay × do
Nghia
̃
la
̀
̃
̀
̉
ơ
̉
̀
̀
̉
xoay (arv > 0). Kê
cua arv cu).
́t
qua nhâ
̉
̣
̣
̣
̀
̀
́
́
́
̣
̉
̣
́
̉
̃
•
Biê
́
̉
́
̀
́
́
̀
̃
̣
Do
ng mơ
́
̀
̃
́
̀
̉
̉
́
̣
̀ng chính,
nghi
̃
̀
Cô
̣
̣
Cột xoay (cột v)
Do
̀
̀
b
×
a’ = a – b c
Dòng chính (dòng r mới) : c
1
Sau đó lặp lại các bước 2, 3, 4 cho đến khi được P.A.C.B tối ưu thì dừng
và kết luận về đáp số của bài toán đã cho
Chú ý
• Ở bước 3 khi kiểm tra điều kiện tối ưu đối với bài toán MAX, ta làm như
sau:
∆ ≥ 0
a) Nếu mọi
phương án đang xét tối ưu → STOP.
j
∆ j < 0
aij ≤ 0
b)
Nếu tồn tại
mà mọi
thì hàm mục tiêu không
bị chặn, do đó bài toán đã cho vô nghiệm → STOP.
∆ j < 0
∆ j < 0
c)
Nếu tồn tại
mà với mỗi
đều có ít nhất một
aij > 0
thì phương án đang xét chưa tối ưu → Làm tiếp bước 4.
27
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
• Còn ở bước 4 khi cải tiến PACB đối với bài toán MAX, ta làm như sau:
∆ = min{∆ < 0}
xv
a) Chọn biến cơ bản mới
sao cho
để đưa vào.
v
j
b
i
λ = min{λ =
/ a > 0}
iv
xr
b) Chọn biến cơ bản cũ
sao cho
để đưa ra.
r
i
aiv
arv
c) Tiếp theo chọn dòng thứ r làm dòng xoay, phần tử
làm phần tử
xoay rồi biến đổi sơ cấp để được bảng đơn hình mới.
• Cũng có thể quy bài toán MAX về bài toán MIN hoặc ngược lại bằng cách
đối dấu hàm mục tiêu.
• Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu ở bước 3,
∆ j ≤ 0
∆ j ≥ 0
nếu mọi
(đối với bài toán MIN) hoặc
(đối với bài toán
∆ j = 0
xj
MAX) đồng thời tồn tại một
có vô số nghiệm.
ứng với biến phi cơ sở
thì bài toán
• Cách tìm hết tất cả các PATU của bài toán QHTT: Giả sử đã tìm ra một
f (x) = f (x0 )
x0
PATU . Khi đó giải hệ gồm phương trình
và các ràng buộc
ta sẽ được tất cả các PATU của bài toán đã cho.
Vi
́
du
̣
1. Gia
̉
̀
́
̣ h tuyến tính (N) sau đây
vơ
́
́
điêu kiê
̀
̣
x1
+ x4 + x5 - x6 = 2,
+ x4 + x6 = 12,
x2
x3 + 2x4 + 4x5 + 3x6 = 9,
xj ≥ 0, j = 1, 2, ... , 6.
Cho x4 = x5 = x6 = 0 ta đươc
muc tiêu f0 = -10. Cơ sơ cua
x0 la
x1, x2, x3. Cac biên phi cơ sơ la x4, x5, x6. Cac
̣
phương an
́
cưc
̣
biên ban đâu
̀
x0 = (2; 12; 9; 0; 0; 0) vơi
biên cơ sơ
hệ số cơ sở c1= 1, c2 = – 1, c3 = 0.
́
tri
̣
̣
̉
̉
̀
{A1, A2, A3}, tức là J0 = {1, 2, 3}. Cac
́
́
̉
la
̀
́
́
̉
̀
́
Bang đơn hinh đầ
̉
̀
x1
x2
-1
x3
0
x4
x5
2
x6
Biê
n
Hệ số
cơ sở
λi
PACB
1
cơ sơ
̉
-2
-3
1
x1
x2
2
1
0
0
1
0
0
1
1
1
0
–1
1
2
12
12
–1
28
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
0
x3
ng 1
9
0
0
0
0
1
0
2
4
3
1
9/2
Ba
̉
-10
2
–1
∆
Trong do
chứa mỗi số ước lượn dương đó đều có những hệ số dương nên phương an
bang nay chưa tôi ưu. Ta cần biến đổi bảng để dược PACB mới tốt hơn.
̀
̣
̀
i) co
̀
4 = 2 > 0, 6 = 1> 0 và trên mỗi cột
́
x0 ơ
̉
̉
̀
• Biê
• Biê
́
̉
mới cần đưa va
̀
́
́
4 = 2 lơ
́n nhất).
́
̣
̉
̉
̀
• Phâ
̀
̉
̀
a14 = 1 (trong ô đươ
̣
́ng mờ
Biê
́
̉
̉
́
qui tăc đa nêu ta nhâ
́
̃
̣
̣
̉
x1
1
x2
x3
x4
x5
2
x6
Hê
cơ sơ
̣
sô
̉
́
Biến
cơ sở
λi
PACB
0
–1
–2
–3
x4
x2
x3
2
10
5
1
0
1
0
0
0
1
1
0
0
1
–1
2
–2
–1
0
–1
2
5
–1
–2
5
1
Ba
̉
0
0
0
–14
–2
–3
3
Trong do
hai hệ số dương nên phương a
để dược PACB mới tốt hơn.
̀
́
̉
ba
̉
̀
co
̉
̀
̀
̉
∆6 = 3 > 0 và trên cột chứa nó có
i ưu. Ta cần biến đổi bảng
́
̉
́
• Biê
• Biê
́
̉
mới cần đưa va
̀
́
́
6 = 3 lơ
́
́
λ
n loa
i cơ sơ
̉
la
̀
x3 (ư
nho
̉
nhâ
t
29
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
• Phâ
̀
̉
xoay la
̀
a36 = 5.
n đươc ba
Biê
́
̉
̉
̣
̣
̉ng 3 dưới đây.
x1
1
x2
x3
0
x4
x5
2
x6
Hệ số Biến
λi
PACB
cơ sơ
̉
cơ sở
–1
–2
–3
x4
x2
x6
3
8
1
3/5
0
1
0
1/5
–2/5
1/5
1
0
0
7/5
–9/5
2/5
0
0
1
–2
–1
–3
–1/5
–2/5
Bảng 3
0
0
0
–17
–4/5
–3/5
–21/5
Trong ba
̉
̀
̣
≤ 0, nên phương an
́
x* = (0; 8; 0; 3; 0; 1) la
̀
PATU
k
vơ
Vi
́i fmin = f(x*) = – 17.
́
du 2. Vi du sau cho thâ
̣
́
̣
́
i toa
́
́
phương an
́
tô
́
f = x2 – 3x3
+ 2x5
+ x5
→ min,
= 7,
x1 + x2 – x3
– 4x2 + 4x3 + x4
–5x2 + 3x3
= 12,
+ x5 + x6 = 10,
xj ≥ 0, j = 1, 2, ... , 6.
Ta gia
̉
̀
́
̀
́
̀
́
t tư
̀
phương a
́
̣c
biên x0 = (7, 0, 0, 12, 0, 10) vơ
́
̉
̀
̣
́
= {1, 4, 6}. Lâ
̣
̉
̀
đơn hình ta được:
x1
0
x2
1
x3
-3
x4
0
x5
2
x6
0
Biê
cơ sơ
́
Hê
CB
̣
sô
́
Phương
λi
̉
án
x1
x4
x6
0
0
0
7
1
0
0
0
1
1
-4
-5
-1
0
-1
4
0
1
1
0
0
0
1
0
0
12
10
0
3
3
0
1
10/3
Ba
ng 1
0
-2
1
3
0
x1
0
10
1/4
30
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
x3
x6
-3
0
3
1
0
0
0
-1
-2
2
1
0
0
1/4
-3/4
-3/4
0
1
0
1
0
Ba
ng 2
-9
-2
Trong ba
n trên không co
ng buôc cua no). Nói cách khác, bài toán QHTT đã cho không có lời giải.
̉
́
2 = 2 > 0 nhưng mo
̣
̀
̉
ai2 ≤ 0 (i = 1, 2, 3) nên ba
̀i
toa
ra
́
̀
ham muc tiêu cua
̀
̣
̉
̀
́
̉
̣
̀
̣
Chú ý: Bai toan tìm g → max đươc thay băng bai toan tim f = – g → min.
̀
́
̣
̀
̀
́
̀
Ví dụ 3. Giải bài toán qui hoac̣ h tuyến tính sau.
f = 3x1 – x2 – 2x3
–x1 + 3x2 + x3 + x4
→ max,
= 7,
= 10,
= 12,
3x1 – 4x2 + 8x3
4x1 – 2x2
+ x5
+ x6
xj ≥ 0, j = 1, 2, ... , 6.
Ta thay f bă
trên.
̀
́
̀
́
̀
̣
Xuâ
phương pha
0) vơi gmin = –11. Tư
́
́
̀
phương a
́
̣
̉
̀
́
̀ng
́
̀
́
̉
̀
̉
̣
̀
́
̀
đo
́
fmax = 11.
x1
-3
x2
1
x3
2
x4
0
x5
0
x6
0
Biê
cơ sơ
́
Hệ số Phương
λi
̉
CB
án
x4
x5
x6
0
0
0
7
-1
3
3
1
8
0
1
0
0
0
1
0
0
0
1
10
12
-4
-2
10/3
4
3
Ba
̉
0
-1
-2
0
0
0
3
0
0
1
0
x4
x5
x1
10
1
5/2
-5/2
-1/2
1
8
1
0
0
0
0
1
0
0
1/4
-3/4
1/4
4
3
0
Ba
̉
-9
-2
-3/4
1/2
1
x2
x5
4
0
0
2/5
9
2/5
1
0
1
1/10
-1/2
11
0
31
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
x1
-3
ng 3
5
1
0
0
0
1/5
1/5
0
0
3/10
-4/5
Ba
̉
-11
-11/5 -1/5
32
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
Vi
́
du
̣
4. Giả bài toán (C) : f(x) = 3x1 – 3x2 + x3 – x4 → min,
–x1 + x2 + 2x3 + x4 = 2,
x1 + x2 – x3 – x4 = 6,
3x1 + 2x2 – 6x3 + 3x4 = 9,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
Đưa va
̀
́
̉
x5, x6, x7 ≥ 0 với hệ số giả M > 0 (đủ lớn) ta được ba
̀
́
–x1 + x2 + 2x3 + x4 + x5
x1 + x2 – x3 – x4
= 2,
= 6,
+ x7 = 9,
+ x6
3x1 + 2x2 – 6x3 + 3x4
xj ≥ 0 (j = 1, 2, 3, 4, 5, 6, 7).
Ta gia
̉
̀
́
̀
p đơn hi
̀
́
́
̀
phương án cự
= (0, 0, 0, 0, 2, 6, 9).
Qua
́
tri
̀
̉
̀
n (N) đươ
̣
́
́
́
̉
̉
x1
3
x2
-3
x3
1
x4
-1
x5
x6
x7
Biê
cơ sơ
́n
θ
CB
̉
án
M
M
M
x5
x6
x7
M
M
M
2
6
9
-1
1
3
1
1
2
2
-1
-6
1
-1
3
1
0
0
0
1
0
0
0
1
2
6
4.5
4M
+3
1
0
0
3M-
3
3M+
1
Ba
̉
17M
< 0
0
0
0
x2
x6
x7
2
4
5
-1
2
5
2
-3
-10
1
-2
1
0
1
0
0
0
1
2
1
Ba
̉
9M-6
0
< 0
< 0
0
0
7M
x2
x6
x1
-3
M
3
3
2
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
1
-2
M-7
0
6/5
-12/5
1/5
< 0
6/5
0
1
0
0
2
Ba
ng 3
2M-6
x2
x3
x1
-3
1
3
3
2
5
1
0
-12/5
-23/5
Ba
̉
8
0
0
0
-94/5
33
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
Ở Ba
(5, 3, 2, 0, 0, 0, 0) la
n tôi ưu cua bai toan ban đâ
̉
́
y ∆k ≤ 0 vơ
phương an tô
u vơi fmin = 8.
́
̣
́
̉
ba
̉
̀
̀
́
́
̉
̀
́
̣
á
́
́
̀
́
§4. VÍ DỤ GIẢI BÀI TOÁN QHTT DẠNG TỎNG QUÁT (G)
Vi du 1. Giai bai toán sau bằng phương pháp đơn hình.
́
̣
̉
̀
f = 5x1 + 8x2 → max,
x1 + 2x2 ≤ 1,
x1 + x2 ≤ 2,
x1 ≥ 0, x2 ≥ 0.
Trươ
́
́
̉
n ba
̀
́
̀ bài toán tìm min và có dạng (N) bằng cách đưa
va
̀
́
́
̣
̀
́n
g = – 5x1 – 8x2
→ min,
= 1,
x1 + 2x2 + x3
x1 + x2
+ x4 = 2,
xj ≥ 0, j = 1, 2, 3, 4.
ng phương phap đơn hinh, xuâ
nh giai như sau (Ba
x1
Ta gia
= (0, 0, 1, 2). Cơ sơ
̉
̀
́
̀
̀
́
̀
́t phát từ phương án cự
c biên x0
̀
{A3, A4}. Qua
́
tri
̀
̉
̉
x2
-8
x3
0
x4
0
Phương
λi
án
-5
x3
x4
Ba
0
0
1
2
0
1
1
5
2
1
8
1
0
0
0
1
0
½
2
̉
x2
x4
Bảng 2
1/2
3/2
-4
1/2
1/2
1
1
0
0
1
0
0
1/2
-1/2
-4
0
1
0
1
3
0
x1
x4
Ba
-5
0
ng 3
1
1
-5
2
-1
-2
1
-1
-5
0
1
0
̉
ỞBa
i gmin = – 5. Tư
du 2. Giai bai toa
̉
̣
̀
phương a
́
́
̉a bài toán chính tắc
vơ
́
̀
́
̀
̉
̀
́
̀
̀
́
Vi
́
̣
́
2x1 + 4x2 – x3 ≤ 10,
3x1 + x2 + x3 ≥ 4,
x1 – x2 + x3 = 2,
xj ≥ 0, j = 1, 2, 3.
34
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
Trươ
́
́
̀
́
̉
đưa bài toán về dạng chính tắc (C).
Tiê
́
́
̀
́
̉
̉
̀
́
fM = - 3x1 + x2 - 2x3
2x1 + 4x2 - x3 + x4
+ M(x6 + x7) → min,
= 10,
3x1 + x2 + x3
x1 - x2 + x3
- x5 + x6
= 4,
+ x7 = 2,
xj ≥ 0, j = 1, 2, ... , 7.
Ta gia
̉
̀
́
̀
́
̀nh với M > 0 (đủ lớn). Quá trình giải
ghi ơ cac ba
̉
́
̉
̉
qua hai cô
̣
́
̉
x1
-3
x2
1
x3
-2
x4
0
x5
0
Biê
cơ sơ
́
Phương
λi
CB
̉
án
x4
x6
x7
0
M
M
10
4
2
2
3
1
4
1
-1
-1
1
1
1
0
0
0
-1
0
5
4/3
2
4M+
2M
+2
Ba
̉
60
– 1
0
– M
3
0
1
0
x4
x1
x7
22/3
4/3
2/3
10/3
1/3
-4/3
-5/3
1/3
2/3
1
0
0
2/3
-1/3
1/3
4
1
2M/3
+1
M/3+
1
Ba
̉
2M/3- 4
0
< 0
0
x4
x1
x3
0
-3
-2
9
1
1
0
1
0
0
1
-2
0
0
1
1
0
0
3/2
-1/2
1/2
6
2
Ba
̉
-5
0
0
0
0
1/2
x4
x1
x5
0
-3
0
6
2
2
0
1
0
0
6
-1
-4
2
1
0
0
0
-3
1
2
1
0
0
0
0
0
1
0
1
Ba
ng 4
-6
-1
x2
x1
x5
1
-3
0
1
3
6
0
1
0
0
-1/2
1/2
0
1/6
1/6
2/3
-1/3
0
0
1
0
Ba
ng 5 mo
đo suy ra lơ
ng 5
-8
0
ỞBa
̉
i ∆k ≤ 0 nên x* = (3, 1, 0, 0, 6, 0, 0) la
̀
phương a
́n tối ưu của bài toán
N
(N). Tư
̀
́
i gia
̉
i toa
́
̀
̀
x* = (3, 1, 0) vơi fmin = – 8.
́
35
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
BÀI TẬP
1. Dùng phương pháp đơn hình giải các bài toán dưới đây
a) f = – 50x1 – 60x2 → min,
x1 + 2x2 ≤ 8,
x1 + x2 ≤ 5,
9x1 + 4x2 ≤ 36,
x1 ≥ 0, x2 ≥ 0.
b) f = 2x1 + 5x2 + 4x3 + x4 – 5x5 → min,
x1 + 2x2 + 4x3 – 3x5 = 152,
4x2 + 2x3 + x4 + 3x5 = 60,
3x2
+ x5 ≤ 36,
xj ≥ 0 (j = 1,2,...,5).
c) f = 6x1 + x2 + x3 + 3x4 + x5 – 7x6 + 6x7 → min,
–x1 + x2
2x1
– x4
+ x6 + x7 = 15,
+ 2x6 + x7 = –9,
– x3
4x1
+ 2x4 + x5 – 3x6
= 2,
xj ≥ 0 (j = 1,...,7).
d)
f = x1 – x2 → min,
x1 – x2 ≥ –1,
3x1 + 2x2 ≤ 6,
–3x1 – x2 ≥ –9,
x1≥ 0, x2 ≥ 0.
e) f = 2x1 + x2 + x3 → min,
x1 + x2 + x3 + x4 + x5 = 5,
x1 + x2 + 2x3 + 2x4 + 2x5 = 8,
x1 + x2
= 2,
= 3,
x3 + x4 + x5
xj ≥ 0 (j = 1,...,4).
36
Bài giảng Qui hoạch tuyến tính
PGS-TS Lê Anh Vũ
f)) f = – x1 – 2x2 – 3x3 + x4 → min,
x1 + 2x2 + 3x3
2x1 + x2 + 5x3
= 15,
= 20,
x1 + 2x2 + x3 + x4 = 10,
xj ≥ 0 (j = 1,...,4).
g) f = x1 + 2x2 – x3→ max,
– x1 + 4x2 – 2x3 ≤ 6,
x1 + x2 + 2x3 ≥ 6,
2x1 – x2 + 2x3 = 4,
x1≥ 0, x2 ≥ 0, x3 ≥ 0.
.
h) f = – x1 –x2 + 1 → max,
x1 – x2 ≥ –1,
3x1 + 2x2 ≥ 6,
–3x1 – x2 ≥ –9,
x1≥ 0, x2 ≥ 0.
2. Giải các bài toán thực tế cho ở bài tập 1), 2) và 5) Chương 1.
37
13 trang
27200
Free
Bạn đang xem tài liệu "Bài giảng Qui hoạch tuyến tính - Chương 2: Phương pháp đơn hình - Lê Anh Vũ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_qui_hoach_tuyen_tinh_chuong_2_phuong_phap_don_hinh.pdf
