QUY HOẠCH TUYẾN TÍNH - BÀI TOÁN VẬN TẢI

Chia sẻ: ytuongsangtao

Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình thường nhưng cước phí vận chuyển là M rất lớn rồi giải như trường hợp không có ô cấm.

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

Nội dung Text: QUY HOẠCH TUYẾN TÍNH - BÀI TOÁN VẬN TẢI

1) Giải bài toán vận tải cho bởi bảng
vận tải sau:
j 40 50 80 30
i
90 2 4 4 2

40 5 7 1 1

70 4 8 3 6
Bước 1: Thành lập một phương án ban
đầu. j 40 50 80 30
i
90 2 4 4 2
40 20 30
40 5 7 1 1
40
70 4 8 3 6
30 40
2 4 4 2
0
R1=
x x x

5 7 1 1
-2
x R2=
4 8 3 6
-4
R3=
x x

0 0 5 0
s1= s2= s3= s4=
x x x
-2 -4 1 -2
1 1 0 -3
x

-2 0 0 0
x x
0 0 5 0
x x x


1 1 0 -3
x *
0 0 5 0
x x x
(3) (2)
-2 0 0 0
x x
1 1 0 -3
(6) x *
(1)

-2 0 0 0
x x
(4) (5)
0 0 5 0
� 4); (1, 2); �
(2,
x x x
V =�
L
,
(3) (2)

(3,3)

1 1 0 -3
(6) x *
� 4); (3, 2);�
(1,
(1)
V =�
C

(2,3)

-2 0 0 0
x x
(4) (5)
0 0 5 0
� 4); (1, 2); �
(2,
40 20 30
V =�
L
,
(3) (2)

(3,3)

1 1 0 -3
(6) *
� 4); (3, 2);�
(1,
40 (1)
V =� C

(2,3)

-2 0 0 0
30 40
(4) (5)


xi* j* = min { xij : (i, j ) � } = min { 30,30, 40}
C
V
= 30
0 0 5 0
xi* j* = 30
40 20 30
(3) (2)

0 0 5 0
1 1 0 -3
40 50
(6) *
40 (1)

1 1 0 -3
-2 0 0 0
*
30 40
10 30
(4) (5)

-2 0 0 0
70
2 4 4 2
40 50



5 7 1 1

10 30

4 8 3 6
70
2 4 4 2
0
R1=
x x
5 7 1 1
x x
0
R2=
4 8 3 6
-2
R3=
X* x

0 0 3 1
s1= s2= s3= s4=
x x x
-2 -4 -1 -1
3 3 0 0
x

0 2 0 3
x x
2) Giải bài toán vận tải có ô cấm cho
bởi bảng vận tải sau:
j 65 75 100
i
80 4 2 1

90 3 5

70 6 7 8
Để giải bài toán vận tải có ô cấm ta
sẽ xem ô cấm như ô bình thường nhưng
cước phí vận chuyển là M rất lớn rồi giải
như trường hợp không có ô cấm.
j 65 75 100
i
80 4 2 1

M
90 3 5

70 6 7 8
j 65 75 100 j 65 75 100
i i
80 4 2 1 80 4 2 1
80
M
90 3 5
90 3 5
M
65 20
5

70 6 7 8
70 6 7 8
70


Đây là phương án cực biên ban đầu.
4 2 1
r1= 4
x

3 5
M
r2= 0
x x
x

6 7 8
r3= M-7
x


s1 s2 s3 5 -M+6 0
x

-M -5
-3 0
0 0
x x
x

M-4 0 M-4
x
5 -M+6 0
x

0
0 0
x x
x

M-4 0 M-4 5 -M+6 0
x * x


0
0 0
x x
x

M-4 0 M-4
x
5 -M+6 0
(1) * x (4)

0
0 0
x x
(2) x
(3)
M-4 0 M-4 5 -M+6 0
x * 80
x
0
0 0

xi* j* = min { xij : (i, j ) �V }=
x x
x
C
5

min { 5,80} = 5
M-4 0 M-4
x
80
(1) * x (4)

x
65 x (3)
(2) x
5
20
x
75
5
70


65 25



70
5 0 0
4 2 1
x x
r1= 4
x x
0 0
M-6
3 5
M
r2= 0 x x
x x

6 7 8 2 0 2
r3= -1
x x

s1 s2 s3
Vì M là số dương rất
-6 -5 lớn nên ma trận cước phí
-3
mới này không âm. Vậy
phương án vừa có là tối
ưu.
3) Giải bài toán vận tải không cân bằng
thu phát cho bởi bảng vận tải sau:
j 40 50 80
i
90 6 1 1

40 5 7 4

70 4 11 3
Để giải quyết vấn đề này ta thêm vào một
trạm thu giả mà cước phí vận chuyển đến
đều bằng 0.
j 40 50 80 30
i

90 6 1 1 0

40 5 7 4 0

70 4 11 3 0
j 40 50 80 30
j 40 50 80 30
i
i
90 6 1 1 0
90 6 1 1 0 60 30

40 5 7 4 0
40 5 7 4 0
40
70 4 11 3 0
70 4 11 3 0
40 10 20
6 1 1 0
r1= 0
x x

5 7 4 0
r2= 2
x
4 11 3 0
r3= -2
x x x


s1 s2 s3 s4
4 -8 0 0
-2 -9 -1 0 x x

5 0 5 2
x
0 0 0 -2
x x x
6 1 1 0
r1= 0
x x

5 7 4 2
r2= 2
x
4 11 3 -2
r3= -2
x x x


s1 s2 s3 s4
4 -8 0 0
-2 -9 -1 0 * x x

5 0 5 2
x
0 0 0 -2
x x x
4 -8 0 0
* x x
(1) (2)
5 0 5 0
x
0 0 (4) 0(3) 0
x x x



xi* j* = min { xij : (i, j ) � C } =
V 4 -8 0 60 0
* x x
min { 10, 60} = 10
5 0 5 2
x
0 0 10 0 20 -2
x x x
60 30
* x x
(1) (2)
40
x

(4) (3)
x x x
40 10 20

10 50 30

40

40 30
6 1 1 0
r1= 0
x x x

5 7 4 0
r2= -6
x
4 11 3 0
r3= -2
x x


s1 s2 s3 s4
4 0 0 0
-2 -1 -1 0 x x x

-3 0 -3 -6
x
0 8 0 -2
x x
6 1 1 0
r1= 0
x x x

5 7 4 -6
r2= -6
x
4 11 3 -2
r3= -2
x x


s1 s2 s3 s4
4 0 0 0
-2 -1 -1 0 x x x

-3 0 -3 -6
x *

0 8 0 -2
4 0 (3) 0 0
x x x
(2)
-3 0 -3 -6
x *
(4) (1)
0 8 0 -2
x x
4 0 10 0 0 30
x x x

-3 0 -3 -6
xi* j* = min { xij : (i, j ) �V }= x *
C
40

min { 40,30} = 30 0 8 0 -2
x x
10 50 30
x x x
(3) (2)
40
x *
(4)
(1)
40 30
x x
40 50

10 30

40 30
6 1 1 0
r1= 0
x x
5 7 4 0
x x
r2= -6
4 11 3 0
r3= -2
x x


s1 s2 s3 s4
4 0 0 6
-2 -1 -1 6 x x
-3 0 -3 0
x
0 8 0 4
x x
6 1 1 0
r1= 0
x x
5 7 4 0
x x
r2= -6
4 11 3 0
r3= -2
x x


s1 s2 s3 s4
4 0 0 6
-2 -1 -1 6 x x
-3 0 -3 0
x *
0 8 0 4
x x
4 0 0 6
x x

-3 0 -3 0
x *

0 8 0 4 4 0 0 6
x x x x


-3 0 -3 0
x *


0 8 0 4
x x
Đề 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