Bài tập quy hoạch tuyến tính

Chia sẻ: hoanghe

Một dạng bài toán đăch biệt của bài toán QHTT có nhiều ứng dụng trong thực tế là bài toán vận tải, sẽ được nghiên cứu trong chương này. Về mặt lý thuyết bài toán vận tải cũng là một bài toán QHTT nên chúng ta có thể dùng phương pháp đơn hình để giải, Tuy nhiên nếu dùng thuật toán đơn hình như trong chương 2 khối lượng tính toán sẽ rất lớn và phức tạp vì ẩn số quá nhiều....

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Bài tập quy hoạch tuyến tính

NHÓM I
BÀI TOÁN VẬN TẢI
THÀNH LẬP BÀI TOÁN
ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ
PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ
XÂY DỰNG PACB ĐẦU TIÊN
PHƯƠNG PHÁP THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT
BÀI TOÁN VẬN TẢI CÓ Ô CẤM

TRƯỜNG HỢP SUY BIẾN
BÀI TOÁN VẬN TẢI
Một dạng đặc biệt của bài toán QHTT có nhiều ứng dụng
trong thực tế là Bài toán vận tải, sẽ được nghiên cứu
trong chương này. Về mặt lý thuyết, bài toán vận tải (đã
được giới thiệu khái niệm trong đoạn 1.2) cũng là một bài
toán QHTT, nên chúng ta cũng có thể dùng phương pháp
đơn hình để giải. Tuy nhiên, nếu dùng thuật toán đơn hình
như trong chương 2, khối lượng tính toán sẽ rất lớn và
phức tạp vì số ẩn quá nhiều. Do có một số đặc điểm
riêng, nên người ta xây dựng các phương pháp giải riêng
đơn giản hơn, nhanh hơn cho bài toán vận tải. Chương
này vẫn dùng ký hiệu: I = {1, 2, …, m} và J = {1, 2, …, n}.
BÀI TOÁN VẬN TẢI
4.1. THÀNH LẬP BÀI TOÁN
BÀI TOÁN VẬN TẢI
4.1.1 Bài toán vận tải cân bằng thu phát
m n

Ta có ∑ pi = ∑ tj
i =1 j =1
(4.1.1)
BÀI TOÁN VẬN TẢI
m n
z = f ( X ) = ∑∑ cij xij → min
i =1 j =1

 n
∑ xij = pi i ∈I
 j =1
m
∑ xij = t j j∈J
 i =1
 xij ≥ 0, i ∈I , j ∈ J


BÀI TOÁN VẬN TẢI
4.1.2 Bài toán không cân bằng thu phát
gọi là bài toán dạng mở:
m n m n

∑ pi < ∑ tj, và ∑ pi > ∑ tj
i =1 j =1 i =1 j =1
m n
4.1.2.1 Trường hợp 1: ∑ pi < ∑ tj
i =1 j =1
BÀI TOÁN VẬN TẢI

m n
z = f ( X ) = ∑∑ cij xij → min
i =1 j =1


 n

∑ xij = pi i = 1, m
 j =1
m
∑ xij ≤ t j j = 1, n
 i =1
 x ≥ 0, i = 1, m, j = 1, n
 ij

BÀI TOÁN VẬN TẢI
4.1.3 Định lý tồn tại:

4.2 ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ
m n
z = f ( X ) = ∑∑ cij xij → min
i =1 j =1
 n

∑ xij = pi i ∈I
 j =1
m
∑ xij = t j j∈J
 i =1
 xij ≥ 0, i ∈I , j ∈ J


BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI

1 1 ... 1 0 0 ... 0 ... 0 0 ... 0 
0 0 ... 0 1 1 ... 1 ... 0 0 ... 0 ÷
 ÷
 ... ... ... ... ... ... ... ... ... ... ... ... ... ÷
 ÷
A = 1 1 ... 1 0 0 ... 0 ... 1 1 ... 1 ÷
1 0 ... 0 1 0 ... 0 ... 1 0 ... 0 ÷
 ÷
0 1 ... 0 0 1 ... 0 ... 0 1 ... 0 ÷
0 0 ... 1 0 0 ... 1 ... 0 0 ... 1 ÷
 
BÀI TOÁN VẬN TẢI
4.2.1 Định lý :
BÀI TOÁN VẬN TẢI



Thật vậy, với các số thực 2 ,..., α m , λ1 ,..., λn thỏa:
α
α 2 H 2 + α 3 H 3 + ... + α m H m + λ1H m +1 + λ2 H m+ 2 +
+... + λn H m+ n = 0mn
chúng ta có ngay λ1 = λ2 = ... = λn = 0
và α 2 + λ1 = 0, α 3 + λ1 = 0,..., α m + λ1 = 0
từ đó,α 2 = α 3 = ... = α m = 0
Do đó, r(A) = m + n - 1.
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
4.3 PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN
VTCĐ
4.3.1 Mô tả bài toán VTCĐ dưới dạng bảng :
BÀI TOÁN VẬN TẢI
Thu
ti … tj …
tn
phát

p1 c11 c1j c1n

… …
ci1 cij cin
pi
(x )
ij

… …
cm1 cmj cmn
pm … …
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
4.3.2 Định nghĩa :
BÀI TOÁN VẬN TẢI




4.3.3 Bổ đề :
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI




( i , j )∈U
λij Aij = Om + n




Ai1 j1 − Ai 2 j1 + Ai 2 j 2 − ... + Aikjk − Ai1 jk +
+ ∑
( i , j )∈U
λij Aij = Om+ n
BÀI TOÁN VẬN TẢI




4.3.4 Định lý :
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI


4.3.5 Định nghĩa :




4.3.6 Định lý :
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI


Giả sử: V1 = {(i ', j '),(i ', j1 ),(i1 , j1 ),(i1 , j2 ),...,(ik , jk ),(ik , j ')}
V2 = {(i ', j '),(i ', l1 ),...,(i p , l p ),(i p , j ')}
từ đây ta lại có một vòng
V3 = {(i ', j1 ),(i1 , j1 ),(i1 , j2 ),...,(ik , jk ),(ik , j '),(i p , j '),(i p , l p ),..., (i ', l1 )}
BÀI TOÁN VẬN TẢI
4.4 XÂY DỰNG PACB ĐẦU TIÊN:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
XÂY DỰNG PHƯƠNG ÁN ĐẦU TIÊN

1. Phương pháp góc Tây Bắc

2. Phương pháp phần tử nhỏ nhất

3. Phương pháp Fogels
BÀI TOÁN VẬN TẢI
4.4.1 PHƯƠNG PHÁP GÓC TÂY BẮC
Điền dần phương án vận chuyển vào
ma trận vận chuyển, bắt đầu từ ô
bên trái phía trên.
Đặt x11 = min (t1; p1)
Nếu t1 > p1 : ta đặt x12 = min (t1 – p1; p2)
Nếu t1 < p1 : ta đặt x21 = min (p1 – t1; t2)
Theo cách trên ta tiếp tục điền vào các
ô của ma trận vận chuyển cho đến
khi không còn hàng ở các điểm phát
hàng và thoả mãn nhu cầu ở các
điểm nhận hàng.
BÀI TOÁN VẬN TẢI
4.4.1.1 Thí dụ:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI




4.4.2 PHƯƠNG PHÁP PHẦN TỬ NHỎ NHẤT
BÀI TOÁN VẬN TẢI
Chọn ô cij có giá trị nhỏ nhất trong bảngchi
phí vận chuyển.
Tính và điền vào ô đó giá trị xij = min (ti,pj).
Sau đó, ta không xét hàng hoặc cột có dự
trữ đã hết hay nhu cầu đã thoả mãn.
Nếu ti = pj thì không xét đồng thời cả cột Bj
lẫn hàng Ai.
Từ phần còn lại của bảng ta lại chọn ô có
giá trị nhỏ nhất và quá trình phân phối tiếp
tục cho đến khi thoả mãn nhu cầu ở các
BÀI TOÁN VẬN TẢI
4.4.2.1 Thí dụ:



Giải : Ưu tỉên phân phối hàng vào ô có cij nhỏ nhất
trong mỗi hàng.
Lần lượt phân phối hàng, theo thứ tự, vào các ô:
(1,3); (2,1); (1,2); (3,2) và (3,1):
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
4.4.3 PHƯƠNG PHÁP FOGELS

B1: Tính độ lệch của các hàng và cột.
Độ lệch của mỗi hàng (cột) = chi phí thấp thứ
nhì trong hàng (cột) – chi phí thấp nhất trong hàng
(cột) ấy.
B2: Chọn hàng (cột) có độ lệch lớn nhất để ưu tiên
phân phối trước. Trong hàng (cột) ấy ưu tiên phân phối
tối đa cho ô nào có chi phí nhỏ nhất.
BÀI TOÁN VẬN TẢI
B3: Nếu có nhiều hàng (cột) có cùng độ lệch lớn nhất
thì ta xác định ô trũng.

Ô trũng là ô có chi phí nhỏ nhất nằm giữa giao
của một hàng và một cột đang xét để ưu tiên phân phối
cho ô nào có chi phí nhỏ nhất trong tất cả các hàng và
cột đang xét.

B4: Sau mỗi lần phân phối ta xoá hàng (cột) tương
ứng với nó. Ta có một bảng mới, tính lại độ lệch của
các cột trong bảng này, sửa lại lượng hàng.

B5: Với bảng còn lại tiếp tục các bước 2 và 3 cho tới
khi kết thúc.
BÀI TOÁN VẬN TẢI
4.4.3.1 Thí dụ:



Hiệu số lớn nhất là 5 ở hàng 3, nên đầu tiên phân phối
x33 = 50
cho ô (3,3) với lượng hàng là
Không kể đến hàng 3, tính lại các hiệu số chi phí, rồi
tiếp tục tìm hiểu số lớn nhất,…
Lần lượt phân phối hàng, theo thứ tự, vào các ô:
(3,3); (1,3);(2,1 ,2);(1
);(1 ,1)
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI

 25 60 15 
X =  50 0 0 ÷
 0 0 50÷
 
Giá trị mục tiêu tương ứng là:

f (x ) = 5× 25+ 4× 60 + 1× 15+ 2× 50 + 2× 50 = 580
BÀI TOÁN VẬN TẢI

4.5 PHƯƠNG PHÁP THẾ VỊ

THUẬT GIẢI
Bước 1: Xác định hệ thế vị (ui,vj)
Bước 2: Kiểm tra tiêu chuẩn tối ưu
Bước 3: Điều chỉnh phương án
BÀI TOÁN VẬN TẢI


Bước 1: Xác định hệ thế vị (ui,vj)

Từ phương án tựa ban đầu, xác định hệ số thế vị (u i,
vj). Hệ thế vị được tính từ các ô cơ sở:
ui + vj = cij

* Ô cơ sở là những ô có điền giá trị của biến số
khác 0.
* Ô tự do là những ô còn lại.
* Chọn một ẩn cho giá trị bằng 0, sau đó xác định
các ẩn còn lại.
BÀI TOÁN VẬN TẢI

Bước 2: Kiểm tra tiêu chuẩn tối ưu
Dùng Định lý 4.5.1. Hiển nhiên điều kiện (b) được
thoả mãn tại các ô cơ sở, nên chúng ta chỉ cần
kiểm tra điều kiện (a) tại các ô phi cơ sở.
Với mọi ô (i, j) S, tính đại lượng: ( gọi là ước
lượng của ô (i, j) )
ij = ui + vj - cij
· Nếu ij 0, với mọi (i, j) S, thì X là một PATƯ. Thuật
toán kết thúc.
· Nếu có một (i, j) S sao cho ij > 0, thì X không là
một PATƯ. Ô (i, j) đó được gọi là ô vi phạm.
Chuyển sang bước 3.
BÀI TOÁN VẬN TẢI


Giả sử:∆ rs = ma x∆ij
∆ ij > 0




Xác địnhq = min {x ij / ( i, j) ∈ V − }, gọi là lượng điều chỉnh
BÀI TOÁN VẬN TẢI


 xij


xij =  xij + q vôù (i, j ) ∈ V +
i


 xij − q vôù (i, j ) ∈ V −
i


f (X ' ) − f (X ) = ∑
(i , j )∈V
cij x 'ij − ∑
(i , j )∈V
cij xij = −q∆ rs
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI

4.5.3 Thí dụ:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI

4.6. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT:




m n

4.6.1.TRƯỜNG HỢP: ∑ p < ∑t
i =1
i
i =1
j
BÀI TOÁN VẬN TẢI
n m
pm +1 = ∑ t j − ∑ pi > 0
j =1 i =1
BÀI TOÁN VẬN TẢI
m n n

∑∑ c x +∑ 0.x
i =1 j =1
ij ij
j =1
m +1, j
→ min

 n

∑ xij = pi (i = 1 m + 1)
,...,
 j =1
m
∑ xij = t j ( j ∈ J )
 i =1
 xij ≥ 0 (i = 1 m + 1 j ∈ J )
,..., ;


BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI




Giải.
Đây là một bài toán không cân bằng thu phát, với
BÀI TOÁN VẬN TẢI




n m

∑t − ∑ p
j =1
j
i =1
i
= 300 − 262 = 38
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI

Kiểm tra tiêu chuẩn tối
ưu:
Vì max ∆ 45 = 3 , nên chọn ô (4,5) làm ô điều chỉnh
∆ij > 0
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
m n
4.6.2. Trường hợp ∑ p < ∑t
i =1
i
i =1
j

Đưa vào một điểm thu ảo Tn +1, với yêu cầu lượng
thu tương ứng làm n
tn+1 = ∑ pi − ∑ t j > 0 và đặt c = 0, với mọi i ∈ I
i,n +1
i =1 j =1
Chúng ta có bài toán VTCĐ tương ứng gồm có
m điểm phát và n + 1 điểm thu như sau:
BÀI TOÁN VẬN TẢI
m n m

∑∑ c x +∑ 0.x
i =1 j =1
ij ij
i =1
i ,n +1
→ min
 n

∑ xij = pi (i ∈ I )
 j =1
m
∑ xij = t j ( j = 1 n + 1)
,...,
 i =1
 xij ≥ 0 (j =1 n +1i ∈ I)
,..., ;


Dùng thuật toán thế vị để giải bài toán này.
Từ một PATƯ của nó, loại bỏ các thành phần
xi,n+1,
chúng ta có được một PATƯ của bài toán đã cho.
BÀI TOÁN VẬN TẢI

4.7 BÀI TOÁN VẬN TẢI CÓ Ô CẤM.
Trong trường hợp, vì một lý do nào đó, không thể vận
chuyển hàng từ điểm phát i đến điểm thu j thì ô (i, j)
trên bảng tương ứng được gọilà một ô cấm. Không
được phân phối hàng vào ô cấm. Để giải quyếttrường
hợp này, người ta gán chi phí vận chuyển ở ô cấm
bằng M > 0lớn tuỳ ý, chúng ta có một bài toán khác gọi
là bài toán (VM).Dùng thuật toán thế vị để giải bài toán
này.
Nếu trong PATƯ của bài toán (VM), tất cả các thành phầ
ứng với ô cấm đều bằng 0 thì PATƯ đó cũng chính là mộ
PATƯ của bài toán ban đầu.
BÀI TOÁN VẬN TẢI
Nếu trong PATƯ của bài toán (VM) có một thành
phần ứng với ô cấm khác 0,thì bài toán ban đầu
không có phương án.

4.8 TRƯỜNG HỢP SUY BIẾN
Trường hợp một PACB X có /G(X)/ < m + n - 1 thì
X là suy biến.Khi đó, chúng ta phải bố sung một ô
nào đó vào G(X) để có tập ô cơ sở S.Ô bổ sung đó
phải thoả mãn các yêu cầu sau:
Không được tạo thành vòng với các ô cơ sở đã có,
giúp chúng ta tính đủ hệ thống thế vị {ui, vj}, và đặt
xij = 0 vào ô đó.
BÀI TOÁN VẬN TẢI

Thí dụ: Một công ty cần vận chuyển một loại hàng từ
4 kho chứa hàng đến 3 cửa hàng của công ty đó. Số
lượng hàng hiện có ở các kho, yêu cầu của các cửa
hàng và chi phí vận chuyển từ mỗi kho đến mỗi cửa
hàng được cho trong bảng sau:
BÀI TOÁN VẬN TẢI

Bài toán đặt ra là: Lập kế hoạch vận chuyển hàng sao
cho các cửa hàng được thu đủ theo yêu cầu và tổng
chi phí vận chuyển là thấp nhất.
1) Hãy tìm một PATƯ cho bài toán và cho biết chi phí
thấp nhất.
2) Giải lại câu (a), nếu có thêm điều kiện “ kho hàng
thứ tư phải phát hết hàng ”.
Giải. (a) Đây là một bài toán không cân bằng thu phát, vớ
m n

∑ p − ∑t
i =1
i
j =1
j
= 495− 470 = 25
BÀI TOÁN VẬN TẢI

Đưa vào một điểm thu ảo, với yêu cầu lượng thu
tương ứng là 25, chúng ta có bài toán VTCĐ tương ứng.
Xây dựng PACB đầu tiên bằng phương pháp đường
gần và tính hệ thống thế vị. PACB thu được là suy biến,
nên chúng ta bổ sung thêm ô (1,1) để có tập ô cơ sở
tương ứng. Kết quả được trình bày trong bảng 4.15:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI


và lượng điều chỉnh là q = min {100,35} = 35 = x43. Sau khi
điều chỉnh, chúng ta có bảng sau:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI




Ô điều chỉnh là ô (3,4), lượng điều chỉnh là q = 25 =
x44.
Sau khi điều chỉnh, chúng ta có bảng sau:
BÀI TOÁN VẬN TẢI
BÀI TOÁN VẬN TẢI
Xin cảm ơn các bạn đã theo dõi.
Hoàng em- Lớp DH7A2- Su phạm toán
Đại học An Giang
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản