Ktl-icon-tai-lieu

ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH

Được đăng lên bởi Antony Hoangtan
Số trang: 9 trang   |   Lượt xem: 5089 lần   |   Lượt tải: 16 lần
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HCM
Khoa Khoa Học Cơ Bản

ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH
Lớp: DHKT5BTLT

Ngày thi: 11/7/2012

Thời gian: 60 phút

Đề 2

Câu 1 (2đ). Cho bài toán quy hoạch tuyến tính mà ta gọi là bài toán (P)
Z=2

(*)

1

+2

2

+

3

+

4

1

+4

2

+

3

2

1

+5

2

+

3

1

+4

2

+

max

4

+

4

4

3

4

= 11

= 13

= 11

j

T

Chứng minh rằng phương án

= (1;1;1;0) là phương án cực biên, tối ưu của

bài toán (P).
GIẢI:
Det (A1,A2,A3) =

4

T

=9

1

+4

2

+

= (1;1;1;0) là PACB.

3

= 11

4

(*)

2

1

1

1

3

+

3

= 13

4

= 11

4

4

4

,

T

=1

=1

2

Z = 2(1

Vậy,

2

+

4

2

3

2

+4

=1

1

Thế

+5

,

4

3

vào z ta được:

) + 2(1

4

) + (1

4

)+

4

=5

4

= (1;1;1;0) là phương án cực biên, tối ưu của bài toán (P).

Câu 2 (2đ). Xây dựng bài toán đối ngẫu của bài toán quy hoạch tuyến tính sau.
Z=6

1

1

+4

10

2

+3

2

2

1

2

3

+

+6

4

3

+

5

5

5

+ 10

4

+ 18

3

+

3

+

6

6

6

6

+

max

5

,

2

;

3

1

,

6

GIẢI:
Z=6

+3

1

2

3

Z = 16y1 + 12y2 + 3y3

1

+4

10

2

2

2

4

+

3

+

+ 10

4

+ 18

3

5

+

max

6

min

3

+

1

+6

5

5

+

y

6

y

6

y

6

1

0

y1

+

2

0

4y1 + 10y2

2y3

0

3

2y1

y2 + 8y3

y1

4

18y2 + y3

5

0

6

10y1 + 2y2

Câu 3 (3đ). Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình.
Z=2

1

+6

2

5

(*)

1

1

+

+2

+5

max

3

2

2

+

+

3

3

12

10

y3

1

+

2

+

10

3

j

G

5

1

(*)

Cho

1

=

+2

1

+5

1

+

2

4

= 12

5

= 10

6

= 10

2

2

2

=

+

3

+

3

+

3

3

12

4

10

5

10

6

=0, suy ra:

Bảng đơn hình:
1

6

2

3

4

5

4

5

2

3

1

0

0

12

5

1

5

2

0

1

0

10

6

2

1

2

0

0

1

10

-2

-6

-7

0

0

0

0

1

2

3

4

5

6

3

1

0

0

5

0

1

0

6

0

0

1

0

28

0

0

4

2

1

2

3

4

5

6

3

0

1

0

2

1

0

0

6

0

0

1

0

Vậy,

T

= (0;

0

;0;0;

0

), z =

Câu 4 (3đ). Cho bài toán vận tải cân bằng thu phát và một phương án ban đầu, với
các số liệu cho ở bảng sau:
j

80

70

150

7

10

i
100 4
80

20

60

3

10

11
50

140 1

9

10
12
140

a)

Chứng tỏ rằng phương án trên là một phương án cực biên không suy biến,
tính cước phí của phương án trên. Phương án cực biên trên được xây dựng
bằng phương pháp nào?

b)

Chứng tỏ rằng phương án trên chưa tối ưu.

c)

Xuất phát từ phương án trên hãy xây dựng phương án cực biên mới tốt hơn,
tính cước phí của phương án đó.
GIẢI:

a) Ta thấy tập các ô chọn không tạo thành chu trình con nên nó là PACB và số ô
chọn bằng m+n-1=5 nên nó là PACB không su...
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HCM
Khoa Khoa Học Cơ Bản
ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH
Lớp: DHKT5BTLT Ngày thi: 11/7/2012
Thời gian: 60 phút Đề 2
Câu 1 (2đ). Cho bài toán quy hoạch tuyến tính mà ta gọi là bài toán (P)
Z = 2
1
+ 2
2
+
3
+
4
max
4
1
+ 4
2
+
3
+
4
= 11
(*) 2
1
+ 5
2
+
3
4
= 13
1
+ 4
2
+
3
4
= 11
j
Chứng minh rằng phương án
T
= (1;1;1;0) là phương án cực biên, tối ưu của
bài toán (P).
GIẢI:
Det (A
1
,A
2
,A
3
) = = 9
T
= (1;1;1;0) là PACB.
4
1
+ 4
2
+
3
= 11
4
ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH - Người đăng: Antony Hoangtan
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
9 Vietnamese
ĐỀ THI CUỐI KỲ MÔN QUY HOẠCH TUYẾN TÍNH 9 10 233