Bài giảng Quy hoạch toán học Trang 21
________________________________________________________________________
2.3.5. Tìm ẩn loại ra
r=1; while (a[i][j]<=0)r++;
for (i=r+1; i<=m; i++)
if (a[i][j]>0)
if (a[i][0]/a[i][j]< a[r][0]/a[r][j])r=i;
2.3.6. Biến đổi bảng
abc[r]:=s; cb[s]=1;
ars = a[r][s]; // Biến trung gian
// Biến đổi riêng hàng r
for (j=0; j<=n; j++) a[r][j]/=ars;
for (i=1; i<=m+1; i++)
if (i!=r){
ais=a[i][s]; // Biến trung gian
a[i][j]-= a[r,j]* ais/ars;
}
---oOo---
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 22
________________________________________________________________________
2.4. Bài tập
Giải các bài toán sau bằng phương pháp đơn hình
1. f(x) = 7x1 - 5x2 - 3x3 → max
4x + x - 3x 15
4x + 3x + 5x 12
x + 2x + 3x 10
x 0 (j = 1..3)
12 3
123
12 3
j
=
=
=
≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
2. f(x) = -5x1 - 4x2 + 5x3 - 3x4 → max
2x + 4x + 3x x 42
4x - 2x + 3x 24
3x + x 15
x 0 (j = 1..4)
1234
12 3
13
j
+
=
≤
≤
≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
3. f(x) = 7x1 +15x2 + 5x3 → min
3x - 2x - 4x
-x + 4x + 3x -3
2x +x + 8x 2
x 0 (j = 1..3)
123
123
12 3
j
≥
≥
≥
≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
1
4. f(x) = 2x1 +17x2 +18x3 → max
6x + 4x + 7x
8x + 4x 30
x 0 (j = 1..3)
123
13
j
≤
≤
≥
⎧
⎨
⎪
⎩
⎪
50
5. f(x) = 3x1 -x2 +2x3 x4 +5x5 → max
2x -x +x +2x +x
4x - 2x + x
x - x + 2x + x
x + x +2x +x
x 0 (j = 1..5)
12 3 4 5
123
12 3 5
12 34
j
≤
=
≥−
≤
≥
⎧
⎨
⎪
⎪
⎪
⎩
⎪
⎪
⎪
17
20
18
100
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 23
________________________________________________________________________
6. f(x) = -5x1 - 4x2 + 5x3 - 3x4 → max
2x + 4x + 3x x 42
4x - 2x + 3x 24
3x + x 15
x 0 (j = 1..4)
1234
12 3
13
j
+
=
≤
≤
≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
7. f(x) = 8x1 + 7x2 + 9x3 ----> min
45 3
36 4
248
013
123
12 3
123
xxx
xx x
xxx
xj
j
−+=
+−≤
++=
≥∀=
⎧
⎨
⎪
⎪
⎩
⎪
⎪,..
6
9
7
6
3
2
8. f(x) = 2x1 - x2 + 3x3 ----> min
7x + 3x + 9x 5
2x - x - 8x
6x + 4x + 2x
123
12 3
123
≤
=−
=
≥∀=
⎧
⎨
⎪
⎪
⎩
⎪
⎪
18
20
013xj
j,..
9. f(x) = 3x1 + 2x2 - 4x3 ----> min
568
434
272
013
123
12 3
123
xxx
xx x
xxx
xj
j
−+=
++=
−−≤
≥∀=
⎧
⎨
⎪
⎪
⎩
⎪
⎪,..
10. f(x) = 3x1 - x2 + 5x3 ----> min
2x + 3x + 7x 5
5x - 2 x - x
6x + 2x + x
123
123
123
≤
=−
=
≥∀=
⎧
⎨
⎪
⎪
⎩
⎪
⎪
41
10
013xj
j,..
11. f(x) = x1 + 2x2 + x3 → max
x -4 x + 2x -6
x +x + 2x 5
2x - x + 2x 3
x 0 (j = 1..3)
12 3
12 3
12 3
j
≥
=
=
≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
***********************
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 24
________________________________________________________________________
Chương 3. BÀI TOÁN ĐỐI NGẪU
3.1. Các bài toán thực tế
3.1.1. Bài toán lập kế hoạch sản xuất
Một nhà máy sản xuất hai loại sản phẩm A, B gồm hai phân xưởng với năng suất như
sau:
Phân xưởng I : 1 nghìn sản phẩm A + 4 nghìn sản phẩm B trong 1 năm. và
Chi phí 16 triệu đồng.
Phân xưởng II : 3 nghìn sản phẩm A + 1 nghìn sản phẩm B trong 1 năm. và
Chi phí 15 triệu đồng.
Kế hoạch Nhà nước giao cho nhà máy là: 1 nghìn sản phẩm A + 2 nghìn sản phẩm B.
Hãy lập kế hoạch sản xuất sao cho tổng chi phí thấp nhất đồng thời đảm bảo kế hoạch
nhà nước giao cho nhà máy.
Gọi x1 là thời gian phân xưởng I sản xuất ( đơn vị năm),
x
2 là thời gian phân xưởng II sản xuất ( đơn vị năm)
Tổng chi phí của kế hoach sản xuất x=(x1, x2) là
f(x) = 16x1 + 15x2 (triệu đồng)
Mô hình toán học:
f(x) = 16x1 + 15x2 → min
(d)
⎪
⎩
⎪
⎨
⎧
≥
≥+
≥+
0
24
13
2,1
21
21
xx
xx
xx
3.1.2. Bài toán đánh giá sản phẩm
Với năng suất hai phân xưởng của nhà máy như bài toán trên . Nhà máy sản xuất được 1
nghìn sản phẩm A và 2 nghìn sản phẩm B. Hãy định giá trị cho 1 sản phẩm A và 1 sản
phẩm B sao cho tổng giá trị của sản phẩm: phân xưởng I không vượt quá chi phí là 16
triệu đồng/năm và phân xưởng II không vượt quá chi phí là 15 triệu đồng/năm, và tổng
giá trị sản phẩm của nhà máy lớn nhất.
Gọi y1(nghìn đồng) là giá trị đơn vị sản phẩm A,
y2(nghìn đồng) là giá trị đơn vị sản phẩm B
Tổng giá trị sản phẩm theo kế hoạch đánh giá y=( y1, y2) là
g(y) = y1+2y2(nghìn đồng)
Mô hình toán học:
g(y) = y1+2y2 → max
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 25
________________________________________________________________________
(d
~
)
⎪
⎩
⎪
⎨
⎧
≥
≤+
≤+
0
153
164
2,1
21
21
yy
yy
yy
x
2
(4,3)
d
(5/11, 2/11)
O
O x
1
fmin=f(5/11, 2/11)= 10 (triệu đồng) gmax=g(4, 3)= 10 (triệu đồng)
Nhận xét: fmin= gmax
3.2. Bài toán đối ngẫu
3.2.1. Đối ngẫu không đối xứng
Cho bài toán (d,f) dạng chính tắc
(1) f(x) = c
∑
=
n
j1
jxj → min
(d)
⎪
⎩
⎪
⎨
⎧
=≥
==
∑
=
)..1(0
)..1(
1
njx
mibxa
j
ij
n
j
ij
Cùng với bài toán (I), xét bài toán ( d
~
, g) như sau:
(1
~
) g(y) = b
∑
=
m
i1
iyi → max
(d
~
)
⎪
⎩
⎪
⎨
⎧
=
=≤
∑
=
)..1(dotu
)..1(
1
miy
njcya
i
ji
n
j
ji
(1
~
) gọi là bài toán đối ngẫu của bài toán (1).
________________________________________________________________________
GV: Phan Thanh Tao