12/09/2017
Ví dụ 1
CHƯƠNG 5b
• Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền lãi cho một bánh mỗi loại được cho trong bảng sau:
QUY HOẠCH TUYẾN TÍNH HAI BIẾN
• Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động về nguyên liệu mà lãi đạt được cao nhất.
Ví dụ 1
Ví dụ 1
• Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập
cẩm, bánh dẻo cần phải sản xuất.
3
,
2
2,5
max
f x
• Vậy ta có mô hình bài toán: f x x x , 1 3
x 1
2
x 2
x 3
• Điều kiện: xj ≥ 0 = 1,2,3 • Tiền lãi thu được (ngàn đồng)
0,04
0,06
0,05
500
x 3
0,07
0,02
300
,
3
2
2,5
f x
f x x x , 1 3
2
x 1
x 2
x 3
x 1 x 1 0
x 2 x 3 1, 2,3
x
j
j
0,04
0,06
x
500
2
• Đây là bài toán quy hoạch tuyến tính 3 biến, tìm
giá trị lớn nhất của hàm mục tiêu.
• Lượng đường sử dụng và điều kiện: x x 0,05 1 3 • Lượng đậu sử dụng và điều kiện: 0,07
0,02
300
x 3
x 1
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Ví dụ 2
Ví dụ 2 – Đ/S
4
x
5
min
,
3
x 1
2
x 3
2
• Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được cho trong bảng sau:
x
90
0, 4
0, 2
0,3
130
• Ta có mô hình sau: f x x x , 1 3 x 0,3 0, 2 3 x 3 0,03
10
x 3
f x x 0,1 1 x 1 x 0,02 1 0
2 x 2 x 0,01 2 1, 2,3
x
j
j
• Hãy lập mô hình toán học của bài toán xác định khối lượng thức ăn mỗi loại phải mua để tổng số tiền chi cho mua thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi ngày.
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
1
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
12/09/2017
Ví dụ 3
Ví dụ 3 – Đ/S
• Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau:
260
120
600
max
,
x 1
x 2
x 3
3
500
f x x x , 1 3
x 3
x 2
250
40
40.000
x 2
x 3
x 1
6
x 1
1, 2,3
0
x
x 2 j
2
• Ta có mô hình sau: f x x 2 1 100
• Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.
j
Ví dụ 4
Bài toán QHTT tổng quát ... 1 min (max)
f x
c x 2 2
c x 1 1
...
1, 2,..,
m
2
a x 1 1 i
a x 2 2 i
a x in n
b i i
• Bài toán lập kế hoạch sản xuất • Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với:
c x n n
• Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m
0
ván
x
j
1, 2,...,
n
0
3
j
tuy y
• Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván • Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất.
(1) Hàm f(x) gọi là hàm mục tiêu (2) là hệ ràng buộc chính (3) là hệ ràng buộc dấu (2) và (3) gọi chung là hệ ràng buộc của bài toán
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Dạng ma trận của bài toán QHTT
Dạng ma trận của bài toán QHTT
...
n
a 1
min (max)
• Xét bài toán QHTT dạng: c x ... 1 1
c x 2 2
c x n n
...
A
b
x
c
...
a 12 a a 2 22 n ....................
b 1 b 2 ...
x 1 x 2 ...
c 1 c 2 ...
...
a m 1
a m
2
a mn
b m
x n
c n
• Đặt: a 11 a 21
...
f x a x 11 1 a x 21 1
b 1 b 2
a x 12 2 a x 22 2
a x 1 n n a x 2 n n
• Ta có dạng ma trận của bài toán QHTT:
f
T c x
min max
...
a x 2 2 m
a x mn n
b m
.......................................... x
a x 1 1 m 0
j
0
Ax b x
• Dạng này còn gọi là dạng chuẩn của bài toán
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
QHTT
2
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
12/09/2017
Ví dụ
Bài toán QHTT - Kinh tế
n
• Viết bài toán QHTT sau dạng ma trận:
max
f x
c x j
j
T c x
min (max)
j 1
f x
n
A x B i (
.
1,
m
)
b (i 1,m)
i
a x ij
j
j 1
x
0 (
j
n 1, )
0 (j 1,n)
j
x
...
c 1 c
x 1 x
...
a 11 a 21
a 1 n a 2
c
x
B
A
2 ...
2 ...
b 1 b 2 ...
a 12 a 22 n .......................
c
x
...
n
n
b n
a m 1
a m
2
a mn
Bài toán dạng chính tắc
Bài toán QHTT - Kinh tế
n
n
min
min (max)
f x
c x j
j
f x
c x j
j
T c x
min (max)
j 1
f x
j 1
n
n
A x B i (
.
1,
m
)
b (i 1,m)
i
a x ij
j
j 1
b (i 1,m)
i
a x ij
j
x
0 (
j
n 1, )
j 1
0 (j 1,n)
j
x
• Các ràng buộc chính đều là phương trình • Các ẩn đều không âm
0 (j 1,n)
j
x
...
...
a 11 a 21
a 1 n a 2
c
x
B
A
c 1 c 2 ...
x 1 x 2 ...
b 1 b 2 ...
a 12 a 22 n .......................
...
c n
x n
b n
a m 1
a m
2
a mn
Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Bài toán dạng chính tắc
Ví dụ 4
• Dạng như sau:
• Bài toán sau có dạng chính tắc:
260
120
600
max
x 3
3
500
x 1
2
x 2 x 3
40
250
40000
x 2
x 2
x 3
6
x 1
,
0
x x 1 2 x x x , 1 2 3
x 1 100
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
3
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
12/09/2017
Giải bài toán QHTT
Giải bài toán QHTT
• B4. Kiểm tra tập phương án để xem xét điều
• B1. Nhận dạng các biến và hàm mục tiêu • B2. Diễn tả hàm mục tiêu và ràng buộc theo các
kiện có nghiệm của bài toán.
biến
• B3. Kiểm tra các quan hệ trong hàm mục tiêu và trong các ràng buộc có phải tuyến tính không. Nếu không ta tìm mô hình khác
• Không có tập phương án (tập p.án rỗng) • Tập phương án vô hạn và không có p.án tối ưu • Tập phương án vô hạn và có p.án tối ưu • Tập phương án hữu hạn
• B4. Kiểm tra tập phương án để xem xét điều
kiện có nghiệm của bài toán.
• B5. Tìm p. án tối ưu nếu có. Phương pháp: đơn
hình hoặc đồ thị
Các loại phương án
Ví dụ
• Cho bài toán QHTT:
120
100
max
x 1
x 2
• Định nghĩa. Vec tơ ∈ thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được.
3
8
x 2
3
15
0,
0
x 2 x 2
f x x 2 1 5 x 1 x 1
• Trong các phương án sau phương án nào là
phương án chấp nhận được.
• Định nghĩa. Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là bài toán min) thì được gọi là phương án tối ưu (PATU).
u
u
u
u 1
2
3
4
1 2
2 2
1 3
2 1
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
Tính chất của tập phương án
Tính chất của tập phương án • Định nghĩa. Đoạn thẳng nối hai điểm x1 và x2 được
• Định lý. Cho x1 và x2 là hai phương án chấp nhận được của bài toán QHTT. Điểm = 1 + 1 − 2 với 0 ≤ ≤ 1 thuộc đoạn thẳng nối hai điểm x1 và x2 .
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến
x R x
, 0
1
x 1
x 2
định nghĩa:
n
1
• Nhận xét • Nếu = 0 chúng ta có x2, = 1 chúng ta có x1. • Những điểm thuộc đoạn thẳng với 0 < < 1 gọi là
các điểm trong của đoạn thẳng
• x1, x2 gọi là các điểm biên của đoạn thẳng.
• Khi đó:
• i) x cũng là phương án chấp nhận được
• ii) Nếu các f(x1)=f(x2) thì f(x)=f(x1)=f(x2)
• iii) Nếu f(x1) 4 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Ví dụ Ví dụ 7/3) 4 x
y 3 max • Xét bài toán QHTT
y
f x y
,
x 4 • Hai phương án chấp nhận
được
và
x1=(0,5;
x2=(2;1/3) có cùng giá trị
hàm mục tiêu là 9. 5 x 3 y 15 • Khi đó phương án x định x y
, 0
bởi: • Có tập phương án được biểu diễn như hình bên x
1
x
1 x
2 2
3
• Ta thấy x1=(0,5; 2) và x2=(2;0,5) là các phương án chấp nhận được.
• Cũng có giá trị hàm mục tiêu • Điểm = 1 + 1 − 2 với =2/3 cũng là phương là 9. án chấp nhận được. Tập lồi và tính chất Định lý • Tập S tất cả các phương án chấp nhận được của
bài toán quy hoạch tuyến tính dạng chính tắc là
một tập lồi. • Tập S gọi là tập lồi nếu với hai điểm phân biệt
bất kỳ x1 và x2 thuộc S thì đoạn nối hai điểm x1
và x2 cũng nằm trong tập S. S
x Ax b x ,
0 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Điểm cực biên của tập hợp lồi Điểm cực biên của tập hợp lồi • Định lý. Điểm x của tập lồi S được gọi là điểm cực biên
của S nếu x không là tổ hợp lồi của hai điểm của S khác
x. • Điểm x trong tập lồi S được gọi là điểm cực biên
nếu không thể biểu diễn được dưới dạng tổ
hợp lồi thật sự của hai điểm phân biệt của S. • Nhận xét:
• Nếu có x1, x2 thuộc S sao cho x 0
1
x
1
x
,
2 • Thì: x x
1 x
2 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 5 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Tính chất tập phương án Phương án cực biên • Tập hợp các phương án của một bài toán quy hoạch tuyến tính là một tập lồi đa diện. • Định nghĩa. Điểm cực biên của tập các phương
án S trong bài toán QHTT gọi là phương án cực
biên. • Nếu tập hợp lồi đa diện này không rỗng và bị
chặn thì đó là một đa diện lồi. Số điểm cực biên
của nó là hữu hạn. • Tính chất.
• Số phương án cực biên của tập phương án S trong bài toán QHTT là hữu hạn • Nếu bài toán QHTT dạng chính tắc có phương
án tối ưu thì nó sẽ có một phương án cực biên
là phương án tối ưu. Phương pháp đồ thị Phương pháp đồ thị • Ví dụ. Giải bài toán QHTT 4 x
y 3 max • Dùng cho bài toán quy hoạch tuyến tính 2 biến
• Xét bài toán quy hoach tuyến tính :
2
f x y
,
x
y 4
f x
min max c x
j j j
1 5 x 3 y 15 2
x 0, y 0 a x
ij j b
i
1
j
x 0 j
Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Tập phương án Nhận xét • Miền OABC chứa tất cả các điểm thỏa mãn ràng buộc của bài toán. Đây là tập phương án • Vấn đề: tìm một điểm thuộc miền này sao cho hàm mục tiêu đạt cực đại. • Chú ý: Miền OABC bị chặn nên bài toán chắc chắn có nghiệm. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 6 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Phương pháp đồ thị Phương pháp đồ thị 4 x 3 y z • Xét hàm mục tiêu:
f x y
, • Mục tiêu: tìm đường đẳng lợi sao cho giá trị
hàm mục tiêu lớn nhất đồng thời vẫn cắt tập
phương án. • Với mỗi giá trị z thì đường thẳng có phương • Có nghĩa là tìm z lớn nhất sao cho đường thẳng trình f(x,y)=z gọi là đường đẳng lợi (d) vẫn cắt tập phương án. 4 x z 3 y y z x
f x y
, 4
3 z
3 : y d x z
3 • Tất cả các đường đẳng lợi đều song song với 4
3
• Ta vẽ các đường song song với Δ. Đường nào
cách xa gốc tọa độ mà còn cắt thì lấy đường đó. nhau và song song với
y x 4
3 Phương pháp đồ thị Phương pháp đồ thị • Ta thấy z/3 max khi và chỉ khi (d) đi qua điểm • Tịnh tiến d theo phương ∆ sao cho vẫn cắt tập B(3/2; 5/2). phương án. • Vậy phương án tối ưu là (x,y)=(3/2;5/2)
• Giá trị hàm mục tiêu f(x,y)=27/2 • Chú ý.
• Đường thẳng f(x,y)=z trong bài toán min ta gọi Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến • Ta chọn đường đẳng phí gần gốc tọa độ nhất. Phương pháp đồ thị Tập phương án 2 x
y 5 max • Ví dụ. Giải bài toán QHTT
f x y
,
3
2 6 x y x 2 y 2
x 0, y 0 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 7 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Phương pháp điểm cực biên • Biểu diễn các ràng buộc lên đồ thị Oxy.
• Xác định phần được giới hạn bởi các ràng buộc là tập • Bài toán không có
án tối phương án. phương
ưu. • Xác định các điểm cực biên (đỉnh) của tập phương án thỏa mãn các ràng buộc. • Xác định giá trị của hàm mục tiêu tại các điểm cực biên. • So sánh và suy ra phương án tối ưu
• Chú ý. Phải chứng minh được bài toán có nghiệm thì mới dùng phương pháp so sánh này. Ví dụ 1 Ví dụ 1 • Giải bài toán QHTT sau: C , x
2 x
1 B 2
x
2 x
1 D A E 2 x
2 x
1 5 min
1
2
3 x
2
0, 0 x
2
f x x
1
2
2
x
1
x
1 • Biểu diễn đồ thị các bất đẳng
thức lên hệ trục tọa độ ta
được miền các phương án là
hình ngũ giác ABCDE.
Các
điểm có tọa độ như sau A(0,0);
B(0,2); C(1,4); D(4,1); E(2,0) là
các điểm cực biên.
lần lượt
thay các cực biên vào hàm
mục tiêu ta có f(A) = 0; f(B) = 2;
f(C) = 3; f(D) = -3; f(E) = -2. • Vậy phương án tối ưu x*=(4,1)
tại đó hàm mục tiêu đạt giá trị
Min Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ 2 Ví dụ 2 • Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng • Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2 max • Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu
100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ
chính quyết định sản lượng kế hoạch. Thợ rèn có 2000
công, thợ sắt có 3000 công, thợ mộc có 1500 công.
Định mức lao động của mỗi loại tàu được cho trong
bản: Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến x x70 3000 1 2 x x50 2000 1
x40 1500 2
• Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt x 1
2
0
x,0 1 2 • Điều kiện:
150
120
x80
tổng số mã lực cao nhất? 8 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Ví dụ 3 Tìm PACB bằng pp Đại số • Xét bài toán QHTT dạng chính tắc: Tc
x min (max) b
f x
A
.
x
x 0 • A là ma trận cấp m.n (giả sử m≤n)
• Ma trận A có hạng là m (có m dòng độc lập tuyến tính) • Một xí nghiệp có thể sử dụng tối đa 510 giờ máy
cán, 360 giờ máy tiện, 150 giờ máy mài để chế tạo
3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản
phẩm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ
máy mài; 1 đơn vị sản phẩm B cần 3 giờ máy cán, 4
giờ máy tiện; 1 đơn vị sản phẩm C cần 5 giờ máy
cán. 3 giờ máy tiện, 2 giờ máy mài. Mỗi sản phẩm
A trị giá 48 ngàn đồng, mỗi sản phẩm B trị giá 16
ngàn đồng, mỗi sản phẩm C trị giá 27 ngàn đồng.
• Vấn đề đặt ra là xí nghiệp cần chế tạo bao nhiêu
đơn vị sản phẩm mỗi loại để tổng giá trị sản phẩm
xí nghiệp thu được là lớn nhất, với điều kiện không
dùng quá số giờ hiện có của mỗi loại máy. Nghiệm cơ bản Ví dụ • Phương trình A.x=b được viết lại dạng: • Cho hệ phương trình tuyến tính 4 ẩn như sau: 4
... 0 x
2
x A x A
1 1
2 2 x A
n
n 3 x
3
15 x
1
x
1 x
2 x
4
5
• Chọn m cột của ma trận A độc lập tuyến tính
• Giả sử ta có các cột A1, A2, …, Am
• Cho các biến tương ứng với các cột còn lại bằng 0
• Giải phương trình ràng buộc với các biến còn lại
• Nghiệm tìm được kết hợp với các biến đã cho bằng 0 tạo thành nghiệm cơ bản của bài toán. Có bao nhiêu pt
tìm nghiệm cơ bản • Tìm tất cả các nghiệm cơ bản
• Chú ý:
• - Ma trận có hạng là 2
• - Có 4 ẩn Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Phương án cơ bản Ví dụ • Xét bài toán QHTT dạng chính tắc có tập các • Tìm tất cả các phương án cơ bản của bài toán ràng buộc: QHTT: f 4 3 max S
x Ax b x , x
1
x
2 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến • Với các điều kiện: • Nghiệm cơ bản của hệ phương trình tuyến tính
A.x=b thỏa mãn điều kiện về dấu x≥0 được gọi
là phương án cơ bản của bài toán QHTT. 9 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 12/09/2017 Phương án cực biên Kiểm tra phương án cực biên • Chứng minh nó là phương án
• Đặt T={Aj|xj>0} trong đó Aj là các vectơ cột của • Nghiệm cơ bản thỏa mãn điều kiện các thành phần
đều không âm gọi là phương án cực biên của bài toán.
• PACB có đúng m thành phần dương gọi là PACB không ma trận hệ số A. suy biến • Chứng minh các vectơ của T tạo thành hệ vectơ • PACB có ít hơn m thành phần dương gọi là PACB suy độc lập tuyến tính biến. • Định lý. Nếu x=(x1,x2,…,xn) là PACB của tập các phương
án S= {A.x=b, x≥0} thì các cột của A tương ứng với xj>0
là độc lập tuyến tính. Ví dụ Ví dụ • Chứng minh rằng x=(1,2,3,0) là PACB của bài • Tìm tất cả các phương án cực biên của bài toán toán QHTT sau: QHTT: f 4 3 max x
1
x
2 • Với các điều kiện: Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến X1=(3/2; 5/2;0;0)
X2=(3;0;1;0)
X3=4;0;0;-5)
X4=(0;5;-1;0)
X5=(0;4;0;3)
X6=(0;0;4;15) 10 Bài giảng Toán Cao cấp 1 Nguyễn Văn TiếnTập lồi
Không phải
Tập lồi
A, B, C, D, E là các điểm cực biên
là đường đẳng phí.
100 mã lực
50 mã lực
Thợ sắt (3000)
150
70
Thợ rèn (2000)
120
50
Thợ mộc (1500)
80
40
0
Nghiệm cơ bản
Phương án cực biên
Giá trị hàm
mục tiêu
