Chương 4 Quy
Ch
Q hoạch
h
h
tuyến tính số nguyên

Tin học trong quản lý


Chương 4Quy hoạch
tuyến
ế tính số
ố nguyên
• Quy hoạch tuyến tính thuần nguyên
• Quy hoạch tuyến tính số nguyên hỗn
hợp
ợp
• Quy hoạch tuyến tính nhị nguyên
• Bài toán pha cắt vật tư
• Bài toán rút ngắn thời gian đường găng
có xét
ét đến
đế yếu tố chi
c p
phí

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


Chương 4 Quy hoạch tuyến tính số

nguyên

MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN
Ví dụ
d 4.1:
41
Để phát triển sản xuất,chủ cơ cở gia công
cốp
pp
pha dự
ự định
ị mua thêm một
ộ số máyy
dập và máy tiện.Ước tính mỗi máy dập
mỗi ngày cho 70USD tiền lời và máy tiện
là 60USD tiền lời.Ông chỉ có 30.000USD
và diện tích xưởng có 12 m2.
Biết :
+ Máy
Má dập
dậ chiếm
hiế 2m
2 2 , giá
iá 6.000

6 000 USD
+ Máy tiện chiếm 3m2, giá 5.000 USD
Vậy số lượng máy mỗi loại nên mua bao
nhiêu thì tiền lời nhất.
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN
 Tóm tắt bài toán :
Khả năng
đáp ứng

Tài nguyên

Máy dập(x1)

Máy tiện (x2)

Tiề lời
Tiền

70USD
0USD

60USD

Diện tích

2


3

12

Giá

6.000USD

5.000USD

30.000

x1

x2

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN
Mô hình toán:
Hàm mục tiêu:
Z = 70x1 +60x2 USD

max

Các ràng buộc:
6x1 + 5x2 ≤ 30 (1

(1.000USD)
000USD)
2x1 + 3x2 ≤ 12 (m2 )
Điều kiện biên: x1 ≥ 0, x2 ≥ 0
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


X2

Giải bài ttoán
á quy h
hoạch
h ttuyến
ế
tính số nguyên bằng phương
pháp
p
p đồ thịị

6

6X1 + 5X2 =30

Máy tiệnn

5
4

Lời giải tối ưu
X1 =3

3.75
75 ,X
X2 =1
1.5
5
lợi nhuận = 352.5 USD

3
D(4,2)
2
1

Z=340

1

2

2X1 + 3X
+ 3X2 =12

E(4,1)

3

4

B(5,0)
5
6


Máy dập
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.

Z=350

X1


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN
Mô hình toán:
Hàm mục tiêu:
Z = 70x1 +60x2 USD

max

Các ràng buộc:
6x1 + 5x2 ≤ 30 (1.000USD)
(1 000USD)
2x1 + 3x2 ≤ 12 (m2 )
Điều kiện biên:

x1 ≥ 0, x2 ≥ 0
bổ sung x1 , x2 nguyên
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH THUẦN NGUYÊN

+ Lợi nhuận =350 Lời giải tối
ưu của bài toán quy hoạch
tuyến
ế tính
í h sốố nguyên
ê
+ Lợi nhuận =340 Lời giải
khi làm tròn nghiệm tối
ố ưu
của bài toán quy hoạch
tuyến
y tính

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


Chương 4 Quy hoạch tuyến tính số
nguyên

MÔ HÌNH QUY HOẠCH
TUYẾN TÍNH NHỊ NGUYÊN
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH NHỊ NGUYÊN
Bài toán :
Chính quyền thị trấn Tương Lai đang xem
xét sẽ xây dựng những công trình thể thao
trong

g bốn công
g trình được
ợ đề nghị
g ị sau đây
y:
Công trình thể
thao

Số người kỳ
vọng sử dụng
hàng ngày

Kinh phí xây
dựng (triệu
đồng )

Diện tích mặt
bằng cần thiết
(1000m2 )

Hồ bơi

300

3500

4

Sân quần vợt


90

1000

2

Sân điền kinh

400

2500

7

Nhà thi đấu mini

150

9000

3

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH NHỊ NGUYÊN
Tổng mặt bằng dành cho các công trình
không được vượt quá 12000 m2.Tổng
Tổng kinh

phí để xây dựng chỉ có 12 tỷ đồng. Thị trấn
chỉ có một
ộ khu đất có địa
ị thế thích hợp
ợp để
có thể để xây dựng hoặc hồ bơi hoặc sân
quần vợt. Nên xây dựng công trình nào để
người dân trong thị trấn
ấ có thể
ể sử dụng
được nhiều nhất?

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


Gọi :
x1 là chọn
h phương
h
án
á xây
â d
dựng hồ
bơi .
x2 là chọn
h phương
h ơ án
á xây
â d
dựng sân

â
quần vợt .
x3 là chọn phương án xây dựng sân
điền kinh .
x4 là chọn phương án xây dựng nhà
thi đấu
– Nếu xi = 0 thì phương án i không
được chọn ngược lại xi = 1 thì
phương
p
g án i được chọn .
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH NHỊ NGUYÊN
Mô hình bài toán :
* Hàm mục tiêu :
Z = 300 x1 + 90x2 + 400x3 + 150x4  max
* Các ràng
g buộc
ộ :
- Ràng buộc về kinh phí :
3500x1 + 1000x2 + 2500x3 + 9000x4 ≤
12000
- Ràng buộc về địa điểm xây dựng :
x1 + x2 ≤ 1
- Ràng buộc về diện tích đất :
4x1 + 2x2 + 7x3 + 3x4 ≤ 12
* Điều kiện biên : x1 , x2 , x3 , x4  0,1

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH NHỊ NGUYÊN
Lời giải tối ưu của bài toán là :
x1 = 1 ( xây dựng hồ bơi)
x2 = 0 ( không xây dựng sân quần vợt )
x3 = 1 ( xây dựng sân điền kinh )
x4 = 0 ( không xây dựng nhà thi đấu
mini)
Z = 700 người .

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


Chương 4 Quy hoạch tuyến tính số
nguyên

MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH SỐ NGUYÊN HỖN HỢP
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH SỐ NGUYÊN HỖN HỢP

 Ví dụ 4.2:
Ông
g Giàu có tiền vốn là 250.000USD định

ị đầu tư
theo 3 phương án sau:
1.Mua xe ô tô chở khách, mỗi xe giá
50 000USD cuối năm cho tiền lời 5.000USD.
50.000USD,
5 000USD
2.Mua đất vườn, mỗi ha đất giá 12.000USD,
cuối năm cho tiền lời 1.500USD.
3M
3.Mua
tí phiếu
tín
hiế kho
kh bạc,
b
mỗi
ỗi tín
tí phiếu
hiế giá
iá
8.000USD,cuối năm lãnh tiền lời 1.000USD.
Vậy
ậy ông
g Giàu nên đầu tư vào dự
ự án như thế nào
để tiền lời nhiều nhất? Biết rằng ông Giàu chỉ nên
mua tối đa 4 xe ô tô để đảm bảo có kế hoạch sử
dụng
ụ g thường
g xuyên

y
và khu đất ông
g Giàu định
ị
mua chỉ còn 30ha.
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH SỐ NGUYÊN HỖN HỢP
• Gọi : x1 là số xe ô tô sẽ mua
x2 là số
ố ha
h đất sẽ
ẽ mua
x3 là số tín phiếu sẽ mua
• Mô hình toán:
– Hàm mục tiêu: (để có tiền lời mỗi năm nhiều nhất)
Z = 5.000x1 + 1.500x2 + 1000x3 ((USD))  max
– Các ràng buộc :
50.000x1 + 12.000x2 + 8.000x3 ≤ 250.000 (USD)
x1 ≤ 4
x2 ≤ 30
– Điều
ề kiện biên:
x1 ≥ 0 , nguyên; ©2010 của Đỗ
x2 ≥ 0 ;ThịxXuân Lan , GVC. Ths.
3 ≥ 0 , nguyên



MÔ HÌNH QUY HOẠCH TUYẾN
TÍNH SỐ NGUYÊN HỖN HỢP

Lời giải tối ưu của bài toán là:
– x1 = 0 xe ô tô sẽ mua
– x2 = 7,5 ha đất sẽ mua
– x3 = 20 tín phiếu sẽ mua
– Tiền lời thu được hàng năm
Z = 31.250 USD
Lời giải tối ưu thứ hai của bài toán là:
– x1 = 0 xe ô tô sẽ mua
– x2 = 20,83 ha đất sẽ mua
– x3 = 0 tín phiếu sẽ mua
– Tiền lời thu được hàng năm
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Z = 31.250
USD


Chương 4 Quy hoạch tuyến tính số
nguyên

BÀI TOÁN PHA CẮT VẬT
TƯ
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


BÀI TOÁN PHA CẮT VẬT TƯ
Ví dụ
ụ 4.4 :

Có một số thanh cốt thép Ø16 dài 11,7m. Để
thi công
g lắp
p đặt cốt thép
p dầm, cột cho một
tầng của một tòa nhà bê tông cốt thép thì
cần phải có 210 đoạn Ø 16 dài 2,1m;
161 đoạn
đ
Ø 16 dài 2
2,9m;
9 176 đoạn
đ
Ø 16 dài
3,2m; 48 đoạn Ø 16 dài 4,2m. Vậy nên cắt
cốt thép như thế nào để tốn ít thanh nguyên
nhất

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


BÀI TOÁN PHA CẮT VẬT TƯ
 Đặt
ặ tên biến:
Gọi x1 là số thanh nguyên pha cắt theo PA 1
Gọi xi là số thanh nguyên pha cắt theo PA i
Các phương án pha cắt từ thanh nguyên 11,7m
được trình bày trong bảng sau :

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.



Các phương án

Số lượng các đoạn

Mẫu thừa (m)

2.1m

2.9m

3.2m

4.2m

x1

0

0

1

2

0.1

x2


0

1

0

2

04
0.4

x3

1

0

0

2

1.2

x4

0

0

2


1

1.1

x5

0

1

1

1

14
1.4

x6

0

2

0

1

1.7


x7

2

1

0

1

0.4

x8

3

0

0

1

1.2

x9

1

0


3

0

0

x10

1

1

2

0

0.3

x11

2

0

2

0

1.1


x12

1

2

1

0

0.6

x13

2

1

1

0

1.4

x14

4

0


1

0

0.1

x15

0

4

0

0

0.1

x16

1

3

0

0

0.9


x17

2

2

0

0

1.7

x18

4

1

0

0

0.4

x19

5

0


0

0

1.2


BÀI TOÁN PHA CẮT VẬT TƯ
 Đặt
ặ tên biến:
Gọi x1 là số thanh nguyên pha cắt theo phương án 1
Gọi xi là số thanh nguyên pha cắt theo phương án i
 Mô hình toán :
Hàm mục
ụ tiêu

Z



i 119

Điề kiệ
Điều
kiện biê
biên:

xi  min

xi ≥ 0

0, nguyên
ê

©2010 của Đỗ Thị Xuân Lan , GVC. Ths.


BÀI TOÁN PHA CẮT VẬT TƯ
Điều kiện ràng buộc:
Có đủ 210
đoạn dài
2.1m
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 2x7 + 3x8 +
1x9 + 1x10 + 2x11 + 1x12 + 2x13 + 4x14 + 0x15 +
Có đủ 161
1x16 + 2x17 + 4x18 + 5x19 ≥ 210
đoạn dài
2.9m
0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 2x6 + 1x7 + 0x8 + 0x9
Có đủ 176
+ 1x
1 10 + 0
0x11 + 2x
2 12 + 1x
1 13 + 0x
0 14 + 4x
4 15 + 3x
3 16 +
2x17 + 1x18 + 0x19 ≥ 161
đoạn dài
3.2m

Có đủ 48
đoạn
ạ dài
4.2m

1x1 + 0x2 + 0x3 + 2x4 + 1x5 + 0x6 + 0x7 + 0x8 + 3x9 + 2x10 +
2x11 + 1x12 + 1x13 + 1x14 + 0x15 + 0x16 + 0x17 + 0x18 + 0x19
≥ 176
2x1 + 2x2 + 2x3 + 1x4 + 1x5 + 1x6 + 1x7 + 1x8 + 0x9 + 0x10 + 0x11 +
0x12 + 0x13 + 0x14
+ 0x15 +Thị0x
16 + 0x17 + 0x18 + 0x19 ≥ 48
©2010 của Đỗ
Xuân Lan , GVC. Ths.