Ôn thi cao học Toán kinh tế: Bài giảng Quy hoạch tuyến tính (chuẩn nhất)

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

2. Một trại chăn nuôi sử dụng 3 loại thực phẩm I, II, III. Lượng chất dinh dưỡng Albumin, chất béo, chất đạm cho gia súc trong 1 ngày cũng như tỉ lệ các chất này trong 3 loại thức ăn được cho trong bảng sau:

Chất

Lượng cần

Tỉ lệ có trong thực phẩm

dinh dưỡng

trong ngày

III

Albumin

Ít nhất 20kg

20%

10%

Chất béo

Đúng 10kg

30%

40%

20%

Chất đạm

Không quá 15kg

30%

Giá 1kg của từng loại thực phẩm I, II, III lần lượt là 80, 120, 90 (ngàn). Cần lập kế hoạch mua các loại thực phẩm theo đúng yêu cầu trong ngày sao cho tổng chi phí thấp nhất.

a) Lập mô hình bài toán.

b) Mô hình bài toán thay đổi thế nào nếu có yêu cầu lượng Albumin không vượt quá hai

lần lượng chất đạm?

ÔN THI CAO HỌC MÔN TOÁN KINH TẾ (GV: Trần Ngọc Hội - 2011) BÀI GIẢI PHẦN I: QUI HOẠCH TUYẾN TÍNH 1. Một xí nghiệp sản xuất đồ gỗ sản xuất 4 loại bàn A, B, C, D. Xí nghiệp có hai phân xưởng: Phân xưởng mộc và phân xưởng trang trí. Số giờ công có thể huy động được cho hai phân xưởng tương ứng lần lượt là 1000 và 2500. Số gỗ quý có thể mua được là 350m3. Suất tiêu hao gỗ và lao động đối với mỗi loại bàn và mỗi lọai công việc, cũng như lãi cho 1 bàn mỗi loại được cho trong bảng sau:

Giải. Gọi x1, x2, x3 (kg) lần lượt là lượng thực phẩm loại I, II, III cần mua. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó

Bàn

Công việc

Mộc

0,08m3/4h

0,12m3/6h

0,3m3/9h

0,21m3/12h

Trang trí

Lãi

250000đ

350000đ

380000đ

850000đ

Lập mô hình bài toán tìm kế họach sản xuất để tổng số lãi thu được lớn nhất.

min

1) Chi phí mua thực phẩm là: f(x) = 80x1 + 120x2 + 90x3 (đv: ngàn). 2) Lượng Albumin có được là: 0,2x1 + 0,1x2 + 0,1x3 (kg). Ta phải có 0,2x1 + 0,1x2 + 0,1x3 ≥ 20. 3) Lượng chất béo có được là: 0,3x1 + 0,4x2 + 0,2x3 (kg). Ta phải có 0,3x1 + 0,4x2 + 0,2x3 = 10. 4) Lượng chất đạm có được là: 0,05x1 + 0,3x2 + 0,3x3 (kg). Ta phải có 0,05x1 + 0,3x2 + 0,3x3 ≤ 15. a) Ta có mô hình bài toán: (1)

≥

0,1x

2 0, 4x

0, 2x

(2)

≤

3 0, 3x

2 0, 3x

0, 3x 1 0, 05x 1

f(x) = 80x1 + 120x2 + 90x3 0,1x 0, 2x ⎧ ⎪ ⎨ ⎪ ⎩

Giải. Gọi x1, x2, x3, x4 lần lượt là số bàn loại A, B, C D cần sản xuất. Điều kiện: xj ≥ 0 (j= 1, 2, 3, 4). Khi đó 1) Tiền lãi thu được là: f(x) = 25x1 + 35x2 + 38x3 + 85x4 (đv: mười ngàn). 2) Lượng gỗ được sử dụng là: 0,08x1 + 0,12x2 + 0,3x3+ 0,21x4 (m3). Ta phải có 0,08x1 + 0,12x2 + 0,3x3+ 0,21x4 ≤ 350. 3) Số giờ công lao động được sử dụng ở phân xưởng mộc là: 4x1 + 6x2+ 9x3+ 12x4 (h)

≥

(j 1, 3)

(3) b) Nếu có thêm yêu cầu lượng Albumin không vượt quá hai lần lượng chất đạm thì ta phải có:

Ta phải có 4x1 + 6x2+ 9x3+ 12x4 ≤ 1000. 4) Số giờ công lao động được sử dụng ở phân xưởng trang trí là:

0,2x1 + 0,1x2 + 0,1x3 ≤ 2(0,05x1 + 0,3x2 + 0,3x3) ⇔ 0,1x1 – 0,5x2 – 0,5x3 ≤ 0.

x1 + 2x2+ 3x3+ 4x4 (h)

min

Do đó ta có mô hình bài toán: (1)

0,1x

Ta phải có x1 + 2x2+ 3x3+ 4x4 ≤ 2500. Vậy ta có mô hình bài toán: (1)

0, 4x

0, 2x

≤

0,12x

0, 3x

max 350

0, 21x

(2)

≤

3 0, 3x

2 0, 3x

2 +

3 ≤

1000

12x

(2)

0, 3x 1 0, 05x 1 −

3 ≤

2 −

0, 5x

4x 1 +

4 ≤

2 +

3 +

2500

0,1x 1

f(x) = 80x1 + 120x2 + 90x3 ≥ 0,1x 0, 2x ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

x 1

f(x) = 25x1 + 35x2 + 38x3 + 85x4 0, 08x ⎧ 1 ⎪ 6x ⎨ ⎪ ⎩

≥

(j 1, 3)

≥

( j 1, 4)

(3)

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

≤

25000

≥

10000

3. Để sản xuất 3 loại sản phẩm A, B, C cần dùng 4 loại nguyên liệu I, II, III, IV. Lượng dự trữ nguyên liệu, định mức tiêu hao nguyên liệu, tiền lãi cho 1 đơn vị sản phẩm được cho trong bảng sau:

≤

1 2x

2 3x

30000

Nguyên liệu

Lượng

Định mức tiêu hao nguyên liệu(kg) cho 1đv

(2)

2 ≤

1 4x

3 35000

dự trữ (tấn)

≥

15000

1 +

≤

3 4x

40000

III

≥

⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪⎩ x

(3)

(j 1, 3)

Tiền lãi cho 1đv

Cần lập kế hoạch sản xuất để không bị động về nguyên liệu và tổng lãi đạt cao nhất.

a) Lập mô hình bài toán.

4. Hai kho I và II có nhiệm vụ cung cấp sắt cho hai công trường xây dựng A và B. Kho I có khả năng cung cấp 60 tấn, kho II có khả năng cung cấp 40 tấn. Công trường A cần ít nhất 50 tấn, công trường B cần ít nhất 30 tấn. Cước phí vận chuyển (đv: ngàn đồng) 1tấn sắt từ các kho đến các công trường được cho trong bảng sau:

b) Mô hình bài toán thay đổi thế nào nếu trong lượng nguyên liệu dự trữ có 10 tấn loại I và

A B

15 tấn loại III sắp hết hạn sử dụng?

I 40 10

II 20 30

Lập mô hình bài tóan tìm kế hoạch vận chuyển sao cho đảm bảo được nhu cầu xây dựng mà chi phí vận chuyển đạt thấp nhất.

Giải. Gọi

• x1, x2 (tấn) lần lượt là lượng sắt cần chuyển từ kho I đến hai công trường A, B. • x3, x4 (tấn) lần lượt là lượng sắt cần chuyển từ kho II đến hai công trường A, B.

max

Giải. Gọi x1, x2, x3 lần lượt là số đơn vị sản phẩm loại A, B, C cần sản xuất. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó 1) Tiền lãi thu được là: f(x) = 6x1 + 7x2 + 8x3. 2) Lượng nguyên liệu I cần sử dụng là: x1 + 2x2 (kg). Ta phải có x1 + 2x2 ≤ 25000 (25000kg = 25tấn). 3) Lượng nguyên liệu II cần sử dụng là: 2x1 + 3x2+ 7x3 (kg). Ta phải có 2x1 + 3x2+ 7x3 ≤ 30000 (30000kg = 30tấn). 4) Lượng nguyên liệu III cần sử dụng là: 4x1 + x3 (kg). Ta phải có 4x1 + x3 ≤ 35000 (35000kg = 35tấn). 5) Lượng nguyên liệu IV cần sử dụng là: x2 + 4x3 (kg). Ta phải có x2 + 4x3 ≤ 40000 (40000kg = 40tấn). a) Ta có mô hình bài toán: (1)

25000

≤

1 2x

2 3x

30000

(2)

2 ≤

3 35000

1 4x

1 +

≤

3 4x

40000

f(x) = 6x1 + 7x2 + 8x3 ≤ x ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

≥

(j 1, 3)

min

Điều kiện: xj ≥ 0 (j= 1, ..., 4). Khi đó 1) Chi phí vận chuyển là: f(x) = 40x1 + 10x2 + 20x3 + 30x4 (ngàn đồng). 2) Lượng sắt kho I xuất ra là: x1 + x2 (tấn). Ta phải có x1 + x2 ≤ 60. 3) Lượng sắt kho II xuất ra là: x3 + x4 (tấn). Ta phải có x3 + x4 ≤ 40. 4) Lượng sắt công trường A nhận được là: x1 + x3 (tấn). Ta phải có x1 + x3 ≥ 50. 5) Lượng sắt công trường B nhận được là: x2 + x4 (tấn). Ta phải có x2 + x4 ≥ 30. Ta có mô hình bài toán: (1)

(3) b) Nếu trong lượng nguyên liệu dự trữ có 10 tấn loại I và 15 tấn loại III sắp hết hạn sử dụng thì ta nhất thiết phải sử dụng hết lượng này, nghĩa là ta cần thêm điều kiện:

≤

x1 + 2x2 ≥ 10000 và 4x1 + x3 ≥ 15000.

≤

(2)

≥

max

Ta có mô hình bài toán: (1)

f(x) = 6x1 + 7x2 + 8x3

≥

3 x

f(x) = 40x1 + 10x2 + 20x3 + 30x4 x ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

≥

(3)

(j 1, 4)

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

(Trong mỗi ô, số liệu ở góc trái là chi phí sản xuất, ở góc phải là năng suất). Yêu cầu sản lượng tối thiểu của Tiêu và Điều lần lượt là 6 tấn và 5 tấn. Lập mô hình bài toán xác định diện tích trồng các loại cây trên sao cho chi phí sản xuất đạt thấp nhất. Giải. Gọi

5. Có hai khu vườn A và B với diện tích lần lượt là 30ha và 40ha. Người ta dự định trồng ba loại cây I, II và III sao cho tỉ lệ sản lượng khi thu hoạch ba loại cây đó là I:II:III = 2:1:4. Biết rằng năng suất (tấn/ha) mỗi loại cây trên hai khu vườn được cho trong bảng sau:

• x1, x2 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất I. • x3, x4 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất II. • x5, x6 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất III.

II III A 1 3 1 B 1 2 2 a) Lập mô hình bài toán xác định diện tích trồng các loại cây trên hai khu vườn trên để sản

lượng đạt được cao nhất.

b) Mô hình bài toán sẽ thay đổi thế nào nếu có yêu cầu sản lượng cây loại I ít nhất 10 tấn?

Giải. Gọi

Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 1) Chi phí sản xuất là f(x) = 1,4x1 + 2,1x2 + 1,3x3 + 2,4x4 + 1,6x5 + 1,8x6. 2) Diện tích trồng trên khu đất I là x1 + x2 (ha).

Ta phải có x1 + x2 ≤ 30.

3) Diện tích trồng trên khu đất II là x3 + x4 (ha).

• x1, x2, x3 (ha) lần lượt là diện tích trồng cây loại I, II, III trên khu vườn A. • x4, x5, x6 (ha) lần lượt là diện tích trồng cây loại I, II, III trên khu vườn B.

Ta phải có x3 + x4 ≤ 40.

4) Diện tích trồng trên khu đất III là x5 + x6 (ha).

Ta phải có x5 + x6 ≤ 50.

Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 1) Diện tích trồng cây trên khu vườn A là x1 + x2 + x3 (ha).

Ta phải có x1 + x2 + x3 ≤ 30.

2) Diện tích trồng cây trên khu vườn B là x4 + x5 + x6 (ha).

Ta phải có x4 + x5 + x6 ≤ 40.

5) Sản lượng Tiêu thu được là 8x1 + 7x3 + 10x5 (tạ). Ta phải có 8x1 + 7x3 + 10x5 ≥ 60 (6tấn = 60tạ). 6) Sản lượng Điều thu được là 7x2 + 11x4 + 6x6 (tạ). Ta phải có 7x2 + 11x4 + 6x6 ≥ 50 (5tấn = 50tạ).

max

Ta có mô hình bài toán: (1)

≤

3) Sản lượng cây loại I thu được là x1 + x4 (tấn). 4) Sản lượng cây loại II thu được là 3x2 + 2x5 (tấn). 5) Sản lượng cây loại III thu được là x3 + 2x6 (tấn). Theo yêu cầu, tỉ lệ sản lượng ba loại cây là I:II:III = 2:1:4 nên ta phải có −

−

≤

−

4 2x

5 2x

x + 2x 4

x + x 2

x 1 2x 1

⎧ ⇔ ⎨ ⎩

≤

(2)

≥

6 7x

5 8x

10x

≥

3 11x

5 6x

max

3x + 2x + 1 3 và sản lượng đạt max khi và chỉ khi sản lượng cây loại I đạt max. Ta có mô hình bài toán: (1)

f(x) = 1,4x1 + 2,1x2 + 1,3x3 + 2,4x4 + 1,6x5 + 1,8x6 x ⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎪ 7x ⎩

≥

(j 1, 6)

(3)

≤

2 x

3 x

(2)

−

5 6x

6 x

−

1 2x

4 2x

5 2x

f(x) = x1 + x4 ≤ x x ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

7. Công ty Y dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần lượt là 50, 60, 70 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng sau:

≥

(j 1, 6)

Tiêu

Khu đất I

(3) 6. Công ty X dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần lượt là 30, 40, 50 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng sau:

III

Điều 2,2 2,3 2

1,2 1,4 1,8

Tiêu

Khu đất I

(Trong mỗi ô, số liệu ở góc trái là chi phí sản xuất, ở góc phải là năng suất). Tiền vốn huy động được cho sản xuất là 180 (triệu đồng). Tiền lãi mỗi tạ Tiêu, Điều lần lượt là 2 và 2,5 (triệu đồng). Lập mô hình bài toán xác định diện tích trồng các loại cây trên sao cho tiền lãi đạt cao nhất.

III

Điều 2,1 2,4 1,8

1,4 1,3 1,6

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

Giải. Gọi

−

→

f (x)

max

2x 1

−

≤ −

12;

4x + x 2

−

≤

2x + 1

x + x 3

−

x + x

20.

2x + 1

1 2 3 2

≥

(j 1, 3)

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪⎩ x

Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 1) Chi phí sản xuất là 1,2x1 + 2,2x2 + 1,4x3 + 2,3x4 + 1,8x5 + 2x6. Ta phải có 1,2x1 + 2,2x2 + 1,4x3 + 2,3x4 + 1,8x5 + 2x6 ≤ 180.

2) Diện tích trồng trên khu đất I là x1 + x2 (ha).

Ta phải có x1 + x2 ≤ 50.

3) Diện tích trồng trên khu đất II là x3 + x4 (ha).

= −

−

ĐS: VN vì PATU của bài toán mở rộng là: (0,2,7,0,0,10) c)

min

f (x)

+ → x 4

Ta phải có x3 + x4 ≤ 60.

2 =

22;

4) Diện tích trồng trên khu đất III là x5 + x6 (ha).

Ta phải có x5 + x6 ≤ 70.

25;

5) Sản lượng Tiêu thu được là 9x1 + 7x3 + 10x5 (tạ).

20.

x + 2x + 3x 2 3 2x + x + 5x 2 3 x + 2x + x + x 2

⎧ ⎪ ⎨ ⎪ ⎩

Tiền lãi thu được từ Tiêu là 2(9x1 + 7x3 + 10x5) (triệu đồng).

6) Sản lượng Điều thu được là 8x2 + 11x4 + 6x6 (tạ).

≥

(j 1, 4)

Tiền lãi thu được từ Điều là 2,5(8x2 + 11x4 + 6x6) (triệu đồng).

= −

ĐS: x0 = (7,6,1,0); f(x0) = −22. d)

f (x)

min

− → x 4

max

7) Tổng tiền lãi thu được là 2(9x1 + 7x3 + 10x5) + 2,5(8x2 + 11x4 + 6x6) (triệu đồng). Ta có mô hình bài toán: (1)

≤

2, 2x

1, 4x

2, 3x

1, 8x

180

3x 1 −

2 +

3 =

≤

−

4 +

x + 2x 2 6x + 3x 2

(2)

≤

−

x + x

3 x

4 6.

1 2x 1 x 1

⎧ ⎪ ⎨ ⎪ ⎩

≤

f(x) = 18x1 + 20x2 + 14x3 + 27,5x4 + 20x5 + 15x6 1, 2x ⎧ 1 ⎪ x ⎪ ⎨ ⎪ ⎪ ⎩

≥

(j 1, 6)

−

→

(j 1, 4) ĐS: x0 = (3,2,5,0); f(x0) = 8 e)

f (x)

min

−

≤

2x 1 2x + 2x 2

→

−

(3) 8. Giải các bài toán QHTT sau bằng phương pháp đơn hình: a)

min

f (x)

−

≥

1 x 1

−

≤

16;

2x + x 1

≥

⎧ ⎪ ⎨ ⎪⎩ x

(j 1, 3)

−

3 ≤

2 4x + 2x 3 −

≤

12.

1 x + 2x 2

⎧ ⎪ ⎨ ⎪ ⎩

≥

(j 1, 3)

ĐS: VN vì PATU của bài toán mở rộng là: (1/2,0,0,0,0,1/2) f )

max

f (x)

x 1

− → x 3 ≤

−

2 2x

x + 4x 2

j ĐS: Vô nghiệm

≥

3 6;

−

x + x + 2x 2 x + 2x

1 2x 1

⎧− ⎪ ⎨ ⎪ ⎩

≥

(j 1, 3)

= ĐS: x0 = (14/5, 12/5, 2/5); f(x0) = 36/5

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

f (x)

max

x 1

−

− → x 3 ≥ −

2 4x + 2x

4x 1

= −

→

−

min

g(x)

A chứa vectơ cột đơn vị e1 (cột 4), không chứa các vectơ cột đơn vị e2, e3 nên bài toán chưa có dạng chuẩn. Ta đưa vào các ẩn giả xj ≥ 0 (j = 6, 7) và lần lượt cộng x6, x7 vào vế trái của các phương trình ràng buộc thứ 2, thứ 3 để xây dựng bài toán mở rộng dạng chuẩn: x Mx Mx (1 '') 6

x 1

3 ≥

−

4x + 4x

2x + x = 6;

−

x + x + 2x 2 x + 2x

1 2x 1

⎧ ⎪ ⎨ ⎪ ⎩

−

(2 '') x + x + 2x

3 4 x + x

≥

(j 1, 3)

−

2 3 5 x + 2x + x

6 4.

1 2x 1

⎧− ⎪ ⎨ ⎪ ⎩

≥

(3 '') x

(j 1, 7)

j Khi đó bài toán có

= −

−

Giải. Chuyển về bài toán min bằng cách đặt g(x) = −f(x) = − x1 − 2x2 + x3 Ta có bài toán: (1)

min

g(x)

2 ≥ −

−

+ → x 3 6;

1 4x + 2x

- Ẩn cơ bản thứ 1 là x4; - Ẩn cơ bản thứ 2 là x6; - Ẩn cơ bản thứ 3 là x7.

3 ≥

1 (2) x + x + 2x

Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: Hệ

−1

−2

−

2 x + 2x

1 2x 1

⎧ ⎪ ⎨ ⎪ ⎩

An Cbản Phương 0 1 0 An3 An số

BảngI

≥

(3) x

(j 1, 3)

−4 1

−2 2

Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 ≥ 0, x5 ≥ 0:

−1 0

−1

−

= −

g(x)

min

+ → x 3

−1

g(x)

2 −

−

x 1 4x + 2x

x = 6;

−M

λi X1 X2 x3 x5 x4 6 0 4 0 1 x4 6 1 M 0 x6 λ2 = 6/2 =3 4 2 M 0 x7 λ3 = 4/2 =2* 0 0 0 1 2 10M 3M 0 4M* 0

BảngII

−

3 x

4 6;

−2

−1

−

5 =

x + x + 2x 2 x + 2x

1 2x 1

⎧ ⎪ ⎨ ⎪ ⎩

−1/2

≥

(j 1, 5)

g(x)

−M

−1/2

10 0 3 0 0 1 x4 λ1 = 10/3 2 M 0 0 x6 λ2 = 2/2 = 1* 2 1 1 1 0 0 x3 0 2 2 3/2 0 0 2M 2M* 0 0 7 0 0 0 3/2 1 x4

BảngIII

−1/2

−2

−1/2

= −

−

Vế phải của phương trình ràng buộc thứ 1 âm nên ta đổi dấu hai vế phương trình này và được bài toán sau: (1 ')

min

g(x)

+ → x 3

−1/4

3 / 4

−

4x + 4x

2x + x = 6;

g(x)

−

1 (2 ') x + x + 2x

3 x

4 = 6;

1 1 0 0 x2 5/2 1 0 1 0 x3 3/4 ½ 11/4* 0 0 0

4 / 3

−

5 =

2 x + 2x

1 2x 1

⎧− ⎪ ⎨ ⎪ ⎩

−2

−2/3

26/3 0 0 2/3 0 1 x4 8/3 0 1 2/3 0 x2

BảngIV

≥

(3 ') x

(j 1, 5)

−1

−1/3

−26/3

−11/3

Ma trận hệ số ràng buộc là:

g(x)

−

10/3 1 0 4/3 0 x1 5/3* 0 0 0

2 1

0 0

−2

−

2 0

1 0

13/2 0 0 1/2 0 1 3/4 7 0 1 1 0 1/2 x5 x2

BảngV

−1

−

2 0

0 1

⎛ ⎜ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎟ ⎠

−39/2

−9/2

−5/4

11/2 1 0 3/2 0 1/4 x1 0 0 0

g(x)

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

−

→

(1 ')

f (x)

10x

7x Mx Mx

max

5x 1

3 =

30;

x + 2x + 2x + x

Trong Bảng V ta thấy Δj ≤ 0 với mọi j = 1, 2,..., 5, nên bài toán mở rộng min có một phương án tối ưu là phương án cơ bản ban đầu

4 =

(2 ')

25;

13 / 2;

2 x + 2x + x + x 2

−

3 2x + x + x

6 x + x

40.

⎧ ⎪ ⎨ ⎪ ⎩

11 / 2;

≥

(3 ')

(j 1, 7)

x 1 x

0x định bởi: = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

Khi đó bài toán có

với

= −

0g(x )

39 / 2.

- Ẩn cơ bản thứ 1 là x4; - Ẩn cơ bản thứ 2 là x6; - Ẩn cơ bản thứ 3 là x7.

0x = (11/2, 7, 0, 0, 13/2, 0, 0), trong đó có phương án tối ưu là x0 = (11/2, 7, 0)

Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: An Hệ

Phương

→

Bài toán mở rộng g(x) min→ có phương án tối ưu là các ẩn giả x6, x7 đều bằng 0 nên bài toán g(x) min→ với g(x0) = −39/2 (ta bỏ đi các ẩn phụ x4 = 0, x5 = 13/2). Kết luận: Bài toán max đã cho có phương án tối ưu là x0 = (11/2, 7, 0) với f(x0) = − g(x0) = 39/2. h)

max

f (x)

10x

5x 1

2 ≤

30;

x + 2x + 2x 2

10 5 7 0 0 cơ án số λi x1 X2 x3 x4 x5 bản 30 1 2 2 1 0 0 x4 λ1 = 30/2

BảngI

3 =

x + 2x + x

25;

≥

3 2x + x + x

40.

⎧ ⎪ ⎨ ⎪ ⎩

f(x)

≥

(j 1, 3)

25 1 1 0 0 −M x6 λ2= 25/2* 40 2 1 1 0 −1 −M x7 λ3 = 40/1 0 0 0 −10 −7 −5 M 0 −65M −3M* −2M −3M

BảngII

3 / 2

→

5 0 0 1 1 0 0 25/2 1/2 1 1/2 0 0 10 x4 x2 λ2= (25/2)/(1/2) =25 55/2 0 1/2 0 −1 −M x7 λ3= (55/2)/(3/2) =55/3*

Giải. Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 ≥ 0, x5 ≥ 0: (1)

max

f (x)

10x

5x 1

3 =

30;

x + 2x + 2x + x

f(x)

3 =

(2)

4 25;

x + 2x + x

0 125 0 0 0 −2 M 0 0 −55M/2 −3M/2* −M/2 5 0 0 0 1 0 x4 λ1 = 5/1=5*

BảngIII

−

3 2x + x + x

40.

⎧ ⎪ ⎨ ⎪ ⎩

≥

(3)

(j 1, 5)

f(x)

10/3 0 1 1/3 0 1/3 10 x2 λ2= (10/3)/(1/3)=10 55/3 1 0 1/3 0 5 −2/3 x1 λ3 = (55/3)/(1/3)=55 0 0 125 0 0 −2*

Các vế phải của phương trình ràng buộc trong (2) đều không âm. Ma trận hệ số ràng buộc là:

5 0 0 1 1 0 7 1/3 5/3 0 1 0 10 −1/3 x3 x2

BảngIV

1 2 2 1

0 0

1 2 1 0

1 0

f(x)

2 1 1 0

0 1

⎛ ⎜ = ⎜ ⎜ ⎝

⎞ ⎟ 0 ⎟ ⎟− 1 ⎠

Trong Bảng IV ta thấy Δj ≥ 0 với mọi j = 1, 2,..., 5, nên bài toán mở rộng max có một phương án tối ưu là phương án cơ bản ban đầu

0x định bởi:

50/3 1 0 0 5 −1/3 −2/3 x1 0 135 0 0 0 2

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

5 / 3;

50 / 3;

x 1 x

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

max

2) Lượng nguyên liệu N1 cần sử dụng là: 0,5x1 + 0,2x2 + 0,3x3+ 0,6x4 (kg). Ta phải có 0,5x1 + 0,2x2 + 0,3x3+ 0,6x4 ≤ 600. 3) Lượng nguyên liệu N2 cần sử dụng là: 0,1x1 + 0,4x2 + 0,2x3+ 0,5x4 (kg). Ta phải có 0,1x1 + 0,4x2 + 0,2x3+ 0,5x4 ≤ 800. Ta có mô hình bài toán: (1)

600

với

= f (x ) 135.

(2)

≤

0,1x + 0,4x + 0,2x + 0,5x

800

f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 ≤ 0,5x + 0,2x + 0,3x + 0,6x ⎧ ⎨ ⎩

có phương án tối ưu là

≥

( j 1, 4)

(3)

→

Biến đổi bài toán trên về dạng chính tắc bằng cách đưa vào 2 ẩn phụ x5 ≥ 0, x6 ≥ 0: (1 ')

0, 38x

0, 4x

0, 3x

max

f (x)

0, 8x 1

= −

0x = (50/3, 5/3, 5, 0, 0, 0, 0), trong đó Bài toán mở rộng f (x) max→ các ẩn giả x6, x7 đều bằng 0 nên bài toán đã cho có phương án tối ưu là x0 = (50/3, 5/3, 5) với f(x0) = 135 (ta bỏ đi các ẩn phụ x4 = 0, x5 = 0). i)

min

f (x)

− → x 4

3x 1

4 =

2 0,5x + 0,2x + 0,3x + 0,6x + x

600;

(2 ')

−

0,1x + 0,4x + 0,2x + 0,5x + x

800.

⎧ ⎨ ⎩

−

3 3x

4 3x

≥

(j 1, 6)

x 1 2x 1 −

2 +

−

4 6.

3 x

(3 ') Các vế phải của phương trình ràng buộc trong (2’) đều không âm. Ma trận hệ số ràng buộc là:

x 1

x 2

⎧ ⎪ ⎨ ⎪ ⎩

0, 5 0, 2 0, 3 0, 6 1 0

≥

0,1 0, 4 0, 2 0, 5 0 1

⎛ = ⎜ ⎝

⎞ ⎟ ⎠

A chứa đủ 2 vectơ cột đơn vị e1 (cột 5), e2 (cột 6) nên bài toán đã có dạng chuẩn, trong đó:

(j 1, 4) ĐS: x0 = (3,2,5,0); f(x0) = 8

−

f (x)

max

- Ẩn cơ bản thứ 1 là x5; - Ẩn cơ bản thứ 2 là x6.

−

2 4x

+ → x 4 10;

3 x

Ta giải bài toán bằng phương pháp đơn hình.

1 x 2 +

−

3 x

4 2x

−

2x 1 3x 1 −

2 2x

3 4.

4x 1

⎧ ⎪ ⎨ ⎪ ⎩

0, 5

≥

(j 1, 4)

Hệ An Phương 0,8 0,3 0,38 0,4 0 0 số cơ bản án λi x1 x2 x3 x4 x5 x6 600 0 0,2 0,3 0,6 1 x5 0 λ1 = 600/0,5* 800 0,1 0,4 0,2 0,5 0 1 0 x6 λ2 = 800/0,1 Bảng I 0 0 f(x) 0 − 0,8* − 0,3 − 0,38 − 0,4 1200 1 0,4 0,6 1,2 2 0 0,8 680 0 0,36 0,14 0 0,38 −0,2 1 x1 x6

Bảng II

f(x) 960 0 0,02 0,1 0,56 1,6 0

ĐS: x0 = (28,108,0,62,); f(x0) = 38. 9. Một xí nghiệp sản xuất 4 mặt hàng: H1, H2, H3, H4. Nguyên liệu cần dùng là N1, N2, mà lượng tối đa xí nghiệp có thể huy động được lần lượt là 600kg và 800kg. Định mức tiêu hao mỗi loại nguyên liệu đối với mỗi mặt hàng cũng như tiền lãi cho 1 đơn vị hàng hóa mỗi loại được cho trong bảng sau:

Trong Bảng II ta thấy Δj ≥ 0 với mọi j = 1, 2,.., 6, nên bài tóan max đang xét có một phương án tối ưu là phương án cơ bản ban đầu x1 định bởi:

H1 H2 H3

1200;

Suất tiêu hao(kg) Hàng Nguyên liệu

680;

x 1 x

⎧ ⎪ ⎨ ⎪ ⎩

N1: 600kg N2: 800kg Tiền lãi (ngàn)

0,6 0,5 0,2 0,3 0,1 0,4 0,2 0,5 0,8 0,3 0,38 0,4

Hãy tìm phương án sản xuất mỗi mặt hàng bao nhiêu đơn vị để tổng tiền lãi thu được cao nhất. Giải. Gọi x1, x2, x3, x4 lần lượt là số đơn vị mặt hàng H1, H2, H3, H4 cần sản xuất. Điều kiện: xj ≥ 0 (j = 1, ..., 4). Khi đó

x 4 với f(x1) = 960. Bỏ đi các ẩn phụ, ta được phương án tối ưu của bài toán max ban đầu là x0 = (x1, x2, x3, x4) = (1200, 0, 0, 0) với f(x0) = 960. Kết luận: Để tiền lãi đạt cao nhất cần sản xuất 1200 đơn vị mặt hàng H1, không sản xuất các mặt hàng khác. Khi đó tổng tiền lãi thu được là 960 ngàn.

1) Tiền lãi thu được là: f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 (ngàn).

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình:

max

Hệ An Phương 0,8 0 0 0,3 0,5 0,4 0 Số cơ bản án λi x5 x6 x2 x1 x3 x4 x7 0,2 0,5 0,3 600 0,6 1 0 0 0 x5 λ1 = 600/0,5 Bảng I 0,4 0,1 0,2 800 0,5 0 1 0 0 x6 λ2= 800/0,1 1000 1 0 0 0 0 1 −M x8 λ3 = 1000/1*

10. Giải bài toán tương tự như trong bài 9 với một số bổ sung sau: - Tổng số sản phẩm mặt hàng H1 và H2 không ít hơn 1000. - Tiền lãi cho 1 đơn vị mặt hàng H3 không phải là 0,38 mà là 0,5. Giải. Tương tự như bài 9, trong đó yêu cầu tổng số sản phẩm mặt hàng H1 và H2 không ít hơn 1000 được thể hiện bởi điều kiện: x1 + x2 ≥ 1000. Ta có bài toán: (1)

f(x)

≤

600

≤

(2)

0,1x + 0,4x + 0,2x + 0,5x

800

0, 5

≥

2 1000

x + x

f(x) = 0,8x1 + 0,3x2 + 0,5x3+ 0,4x4 0,5x + 0,2x + 0,3x + 0,6x ⎧ ⎪ ⎨ ⎪ ⎩

≥

( j 1, 4)

f(x)

0, 6

→

(3) Biến đổi bài toán trên về dạng chính tắc bằng cách đưa vào 3 ẩn phụ x5 ≥ 0, x6 ≥ 0, x7 ≥ 0: (1 ')

0, 4x

0, 5x

0, 3x

max

f (x)

0, 8x 1

2 0,5x + 0,2x + 0,3x + 0,6x + x

600;

f(x)

(2 ')

0,1x + 0,4x + 0,2x + 0,5x + x

800;

−

x + x

x = 1000.

⎧ ⎪ ⎨ ⎪ ⎩

≥

(j 1, 7)

f(x)

(3 ') Các vế phải của phương trình ràng buộc trong (2’) đều không âm. Ma trận hệ số ràng buộc là:

1x định bởi:

Trong Bảng IV ta thấy Δj ≥ 0 với mọi j = 1, 2,..., 7, nên bài toán mở rộng max có một phương án tối ưu là phương án cơ bản ban đầu

0, 5 0, 2 0, 3 0, 6 1 0

1000 / 3;

0,1 0, 4 0, 2 0, 5 0 1

1900 / 3;

0 0 0

⎛ ⎜ = ⎜ ⎜ ⎝

⎞ ⎟ 0 ⎟ ⎟− 1 ⎠

1000;

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

với

1 f (x )

2900 / 3.

→

−

0 A chứa 2 vectơ cột đơn vị e1 (cột 5), e2 (cột 6), còn thiếu vectơ cột đơn vị e3 nên bài toán chưa có dạng chuẩn. Ta đưa vào ẩn giả x8 ≥ 0 và cộng x8 vào vế trái của các phương trình ràng buộc thứ 3, để xây dựng bài toán mở rộng dạng chuẩn: (1 '')

0, 5x

0, 3x

max

f (x)

0, 8x 1

có phương án tối ưu là

0, 4x Mx 4 =

0,5x +0,2x + 0,3x + 0,6x + x

600;

(2 '')

0,1x +0,4x + 0,2x + 0,5x + x

800;

2 x +x - x + x =1000. 7

⎧ ⎪ ⎨ ⎪ ⎩

≥

(j 1, 8)

(3 '') x Khi đó bài toán có

- Ẩn cơ bản thứ 1 là x5; - Ẩn cơ bản thứ 2 là x6; - Ẩn cơ bản thứ 3 là x8.

0 0 0 0 − 0,5 − 0,4 −0,8 − 0,3 0 0 0 M 0 −1000M −M* −M 0,33 0,6 1 0 0 100 0 −0,3 x5 λ1 = 100/0,5* Bảng II 0 0,3 0,2 700 0,5 0 1 0,1 0 x6 λ2= 700/0,1 1 1 0 1000 0 0 0 0,8 −1 x1 0 0 0,5 800 − 0,4 0 − 0,8* − 0,5 0 200 1,2 2 0 1 0 −0,6 x7 λ1 = 200/0,6 1 0 0 0,36 0,14 680 0 0,38 −0,2 x6 1 0,4 0,6 1200 1,2 2 0 0 0,8 x1 λ2= 680/0,14 Bảng III λ3= 1200/0,6 0 960 1,6 0 0 0,02 − 0,02* 0,56 1 2 0 10/3 10/6 0 1000/3 0,5 −1 x3 1 Bảng IV 0 0,5 0 1900/3 0,1 0 −2/3 −7/30 x6 1 1 0 1000 0 0 0 0,8 −1 X1 0 0 0 2900/3 0 0,6 5/3 1/30

1x = (1000, 0, 1000/3, 0, 0, 1900/3, 0, 0) Bài toán mở rộng f (x) max→ trong đó ẩn giả x8 = 0 nên bài toán max ban đầu có phương án tối ưu là x1 = (1000, 0, 1000/3, 0) với f(x1) = 2900/3 (ta bỏ đi các ẩn phụ x5, x6 và x7). Kết luận: Để tiền lãi đạt cao nhất cần sản xuất 1000 đơn vị mặt hàng H1, 1000/3 đơn vị mặt hàng H3, không sản xuất các mặt hàng khác. Khi đó tổng tiền lãi thu được là 2900/3 ngàn. 11. Xí nghiệp dùng các tấm kim loại kích thước 60cm×100cm để sản xuất 3 loại bán thành phẩm là các tấm kim loại T1, T2, T3. Có 4 phương thức cắt P1, P2, P3, P4. Số lượng bán thành phẩm cần trong sản xuất; số lượng bán thành phẩm có được cũng như lượng thừa sau khi cắt một tấm theo mỗi cách được cho trong bảng sau:

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

Bán thành phẩm

Luợng bán thành phẩm cần có

T1 T2 T3

420 6 6 7 10 -1 -1 -1

Lượng thừa (cm2)

Phương thức cắt P4 P3 P2 P1 10 5 4 3 0 1 0 2 0 1 2 1 200 400 200 0

240 100 80

Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá lớn nhỏ nhất ứng với x4 vậy biến đưa vào là : x4 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1

Ci 0 M M Xi X4 X9 X10 F(x) Yi 24 100 80 0 180 X1 3/10 2 1 -200 3 X2 2/5 0 2 -400 2 X3 1/2 1 1 -200 2 X4 1 0 0 0 0 X5 -1/10 0 0 0 0 X6 0 -1 0 0 -1 X7 0 0 -1 0 -1 Lamda 80 50 80

Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá lớn nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2

min

Ci 0 200 M Xi X4 X1 X10 F(x) Yi 9 50 30 10000 30 X1 0 1 0 0 0 X2 2/5 0 2 -400 2 X3 7/20 1/2 1/2 -100 1/2 X4 1 0 0 0 0 X5 -1/10 0 0 0 0 X6 3/20 -1/2 1/2 -100 1/2 X7 0 0 -1 0 -1 Lamda 45/2 - 15

Hãy tìm phương án cắt sao cho lượng bán thành phẩm cần trong sản xuất đuợc đảm bảo mà tổng số lượng thừa là ít nhất. Giải. Gọi x1, x2, x3, x4 lần lượt là số tấm kim loại được cắt theo phương thức P1, P2, P3, P4. Điều kiện: xj ≥ 0 (j= 1, ..., 4). Khi đó 1) Tổng lượng thừa: f(x) = 200x1 + 400x2 + 200x3 (cm2). 2) Lượng bán thành phẩm T1 thu được: 3x1 + 4x2 + 5x3+ 10x4. Ta phải có 3x1 + 4x2 + 5x3+ 10x4 ≥ 240. 3) Lượng bán thành phẩm T2 thu được: 2x1 + x3. Ta phải có 2x1 + x3 ≥ 100. 4) Lượng bán thành phẩm T3 thu được: x1 + 2x2 + x3. Ta phải có x1 + 2x2 + x3 ≥ 80. Ta có bài toán: (1)

240

2 ≥

(2)

100

1 2x + x 1

≥

x + 2x + x

f(x) = 200x1 + 400x2 + 200x3 ≥ 3x + 4x + 5x + 10x ⎧ ⎪ ⎨ ⎪ ⎩

≥

(j 1, 4)

Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá lớn nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 3

Ci 0 200 400 Xi X4 X1 X2 F(x) Yi 3 50 15 16000 0 X1 0 1 0 0 0 X2 0 0 1 0 0 X3 1/4 1/2 1/4 0 0 X4 1 0 0 0 0 X5 -1/10 0 0 0 0 X6 1/20 -1/2 1/4 0 0 X7 1/5 0 -1/2 -200 0 Lamda - - -

Chất

Lượng yêu cầu trong 1 ngày đêm Ít nhất 200g

Phương án tối ưu của bài toán mở rộng là : (50,15,0,3,0,0,0,0,0,0) Giá trị hàm mục tiêu đạt được là : F(x) = 16000 12. Có ba loại thức ăn I, II, III dùng trong chăn nuôi. Mức yêu cầu cần phải có đủ các chất cho gia súc trong một ngày đêm và giá mỗi đơn vị thức ăn mỗi loại được cho trong bảng sau: 200x1 + 400x2 + 200x3 + Mx8 + Mx9 + Mx10 => MIN

Albumin Chất béo Không quá 100g Chất đạm Đúng 150g Giá 1đv thức ăn (ngàn đồng)

Lượng chất (đv: g) có trong 1đv thức ăn mỗi loại II 0,8 0 10 1,5

III 2 0,4 0 3

I 0,3 3 1 0,8

= 240

= 80 3x1 + 4x2 + 5x3 + 10x4 - x5 2x1 + x3 - x6 x1 + 2x2 + x3 = 100 - x7

Hãy xác định lượng thức ăn cần dùng mỗi loại sao cho tổng chi phí thấp nhất mà vẫn đảm bảo được mức yêu cầu cho gia súc về các chất trong 1 ngày đêm. Giải. Gọi x1, x2, x3 lần lượt là số đơn vị thực phẩm loại I, II, III cần mua. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó

x5, x6, x7 là biến phụ x8, x9, x10 là biến giả x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0

(3) Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (50, 15, 0, 3); f(x0) = 16000. Do đó để tổng số lượng thừa là ít nhất, số tấm kim loại được cắt theo phương thức P1, P2, P3, P4 lần lượt là 50, 15, 0, 3. Khi đó tổng số lượng thừa là 1600cm2. Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: F(x) = Các ràng buộc: Trong đó:

1) Chi phí mua thực phẩm: f(x) = 0,8x1 + 1,5x2 + 3x3 (ngàn đồng). 2) Lượng Albumin có được: 0,3x1 + 0,8x2 + 2x3 (g). Ta phải có 0,3x1 + 0,8x2 + 2x3 ≥ 200. 3) Lượng chất béo có được: 3x1 + 0,4x3 (g). Ta phải có 3x1 + 0,4x3 ≤ 100.

Xi X8 X9 X10 F(x) Yi 240 100 80 0 X1 3 2 1 -200 X2 4 0 2 -400 X3 5 1 1 -200 Ci M M M X5 -1 0 0 0 X6 0 -1 0 0 X7 0 0 -1 0 Lamda 24 - - X4 10 0 0 0

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

min

4) Lượng chất đạm có được: x1 + 10x2 (g). Ta phải có x1 + 10x2 = 150. Ta có bài toán: (1)

200

2 ≤

1 +

3 100

0, 4x

(2)

3x 1 +

3 =

150

10x

x 1

f(x) = 0,8x1 + 1,5x2 + 3x3 ≥ 0,3x + 0,8x + 2x ⎧ ⎪ ⎨ ⎪ ⎩

0 1 0 0 0 3 0 15/10 X3 X5 X2 F(x) 94 312/5 15 609/2 0 11/100 739/250 1/10 -8/25 0 0 0 1 0 0 1 0 0 0 0 -1/2 1/5 0 -3/2 0 - - -

≥

(j 1, 3)

Chi phí sản xuất cho 1ha

Nông sản A B C

Vốn (ngàn đồng) 300 350 400

Lao động (ngàn đồng) 500 400 450

Giá trị sản lượng thu được trên 1ha (ngàn đồng) 2.000 1.500 2.500

(3) Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (0, 15, 94); f(x0) = 609/2. Do đó để tổng chi phí thấp nhất, số đơn vị thực phẩm loại I, II, III cần mua lần lượt là 0, 15, 94. Khi đó tổng chi phí là 609/2 (ngàn đồng).

Phương án tối ưu của bài toán mở rộng là : (0,15,94,0,312/5,0,0) Giá trị hàm mục tiêu đạt được là : F(x) = 609/2 13. Một nông trường sử dụng 3000ha để trồng 3 loại nông sản A, B, C có thông số sau:

Khả năng của nông trường về vốn là 1200 triệu đồng, về lao động là 1600triệu đồng. Ngoài ra, để đảm bảo hợp đồng đã ký kết, cần trồng ít nhất 600ha nông sản A. Hãy xác định diện tích trồng mỗi loại nông sản để tổng giá trị sản lượng thu được là cao nhất. Giải. Gọi x1, x2, x3 (ha) lần lượt là diện tích trồng các loại nông sản A, B, C. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó

8/10x1 + 15/10x2 + 3x3 + Mx6 + Mx7 => MIN

= 200 + 2x3 - x4 + 8/10x2 + x5 = 100 3/10x1 3x1 + 4/10x3 x1 + 10x2 = 150

x4, x5 là biến phụ x6, x7 là biến giả x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0

Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: F(x) = Các ràng buộc: Trong đó:

1) Tổng giá trị sản lượng thu được: f(x) = 2x1 + 1,5x2 + 2,5x3 (triệu). 2) Tổng diện tích trồng: x1 + x2 + x3 (ha). Ta phải có x1 + x2 + x3 ≤ 3000. 3) Diện tích trồng nông sản A: x1 (ha). Ta phải có x1 ≥ 600. 4) Chi phí về vốn: 300x1 + 350x2 + 400x3 (ngàn). Ta phải có 300x1 + 350x2 + 400x3 ≤ 1200000 (1200triệu = 1200000ngàn). 5) Chi phí về lao động: 500x1 + 400x2 + 450x3 (ngàn). Ta phải có 500x1 + 400x2 + 450x3 ≤ 1600000 (1600triệu = 1600000ngàn). Ta có bài toán: (1)

max

≤

3000

≥

x + x + x 2 600

⇔

(2)

≤

1 300x

350x

400x

1200000

3, 5x

12000

≤

2 +

≤

400x

450x

1600000

3 4, 5x

16000

f(x) = 2x1 + 1,5x2 + 2,5x3 x + x + x ⎧ 2 ⎪ 600 ⎪ ⎨ ⎪ ⎪ 500x ⎩ 1

⎧ ⎪ ⎪ 1 ⎨ 3x ⎪ 1 ⎪ 5x ⎩ 1

≥

(j 1, 3)

Xi X6 X5 X7 F(x) Yi 200 100 150 0 350 X1 3/10 3 1 -4/5 13/10 X2 8/10 0 10 -3/2 54/5 X3 2 4/10 0 -3 2 X4 -1 0 0 0 -1 X5 0 1 0 0 0 Lamda 250 - 15 Ci M 0 M

Xi X6 X5 X2 F(x) Yi 188 100 15 45/2 188 X1 11/50 3 1/10 -13/20 11/50 X2 0 0 1 0 0 X3 2 2/5 0 -3 2 X4 -1 0 0 0 -1 X5 0 1 0 0 0 Lamda 94 250 - Ci M 0 15/10

2x1 + 3/2x2 + 5/2x3 - Mx8 => MAX Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá lớn nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1

(3) Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (600,0,2400); f(x0) = 7200. Do đó để tổng giá trị sản lượng thu được là cao nhất, diện tích trồng các loại nông sản A, B, C lần lượt là 600, 0, 2400 (ha). Khi đó tổng giá trị sản lượng thu được là 7200 (triệu đồng). Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: F(x) = Các ràng buộc:

Lamda Xi Yi X1 X2 X3 X4 X5 Ci

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

= 600 + x2 + x3 + x4 = 3000 - x5

x1 x1 3x1 + 7/2x2 5x1 + 4x2 + 9/2x3 + 4x3 + x6 = 12000 + x7 = 16000

Do chiến lược tiếp thị, công ty phải có ít nhất 30 lần quảng cáo trên truyền hình trong 1 tháng. Hãy xác định số lần quảng cáo trên mỗi phương tiện sao cho số người dự kiến tiếp nhận quảng cáo là cao nhất. Giải. Gọi x1, x2, x3 lần lượt là số lần quảng cáo trên truyền hình, phát thanh và báo. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó

1) Dư kiến tổng số người tiếp nhận quảng cáo:

f(x) = 15x1 + 9x2 + 30x3 (ngàn người). 2) Số lần quảng cáo tối đa trên truyền hình là 60, tối thiểu là 30 nên

x1 ≤ 60 và x1 ≥ 30.

x4, x5, x6, x7 là biến phụ x8 là biến giả x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0 Trong đó:

max

3) Số lần quảng cáo tối đa trên phát thanh là 90 nên x2 ≤ 90. 4) Số lần quảng cáo tối đa trên báo là 26 nên x3 ≤ 26. 5) Chi phí quảng cáo: 1,5x1 + 0,5x2 + x3 (triệu đồng). Ta phải có 1,5x1 + 0,5x2 + x3 ≤ 100. Ta có bài toán: (1)

≤

≥

Ci 0 -M 0 0 Xi X4 X8 X6 X7 F(x) Yi 3000 600 12000 16000 0 -600 X1 1 1 3 5 -2 -1 X2 1 0 7/2 4 -3/2 0 X4 1 0 0 0 0 0 X5 0 -1 0 0 0 1 X6 0 0 1 0 0 0 X7 0 0 0 1 0 0 Lamda 3000 600 4000 3200 X3 1 0 4 9/2 -5/2 0

≤

(2)

1 x

≤

0,5x

100

Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2

≥

f(x) = 15x1 + 9x2 + 30x3 x ⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ 3 ⎪⎩ 1,5x 1 x

(j 1, 3)

Ci 0 2 0 0 Xi X4 X1 X6 X7 F(x) Yi 2400 600 10200 13000 1200 0 X1 0 1 0 0 0 0 X2 1 0 7/2 4 -3/2 0 X4 1 0 0 0 0 0 X5 1 -1 3 5 -2 0 X6 0 0 1 0 0 0 X7 0 0 0 1 0 0 Lamda 2400 - 2550 26000/9 X3 1 0 4 9/2 -5/2 0

Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1

15x1 + 9x2 + 30x3 - Mx9 => MAX Ci 5/2 2 0 0 Xi X3 X1 X6 X7 F(x) Yi 2400 600 600 2200 7200 0 X1 0 1 0 0 0 0 X2 1 0 -1/2 -1/2 1 0 X4 1 0 -4 -9/2 5/2 0 X5 1 -1 -1 1/2 1/2 0 X6 0 0 1 0 0 0 X7 0 0 0 1 0 0 Lamda - - - - X3 1 0 0 0 0 0

+ x4 = 60 - x5 = 30 + x6 = 90 + x7 = 26 x1 x1 x2 x3 3/2x1 + 1/2x2 + x3 + x8 = 100

Chi phí mỗi lần quảng cáo (triệu đồng)

Số lần quảng cáo tối đa trong 1 tháng

1,5

15.000

Phương án tối ưu của bài toán mở rộng là : (600,0,2400,0,0,600,2200,0) Giá trị hàm mục tiêu đạt được là : F(x) = 7200 14. Một công ty muốn quảng cáo một loại sản phẩm trong 1 tháng với tổng chi phí 100triệu đồng. Các phương tiện được chọn để quảng cáo là: Truyền hình, Phát thanh và Báo với các số liệu sau: Dự kiến số người tiếp nhận trong 1 Phương tiện lần quảng cáo

x4, x5, x6, x7, x8 là biến phụ x9 là biến giả x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0, x8 >=0

(3) Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (30, 58, 26); f(x0) = 1752. Do đó để số người dự kiến tiếp nhận quảng cáo là cao nhất, số lần quảng cáo trên truyền hình, phát thanh và báo lần lượt là 30, 58, 26. Khi đó số người dự kiến tiếp nhận quảng cáo là 1752000 người. Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: F(x) = Các ràng buộc: Trong đó:

0,5

9.000

30.000

Truyền hình (1phút/lần) Phát thanh (1 phút/lần) Báo (1/2trang/lần)

Ci 0 -M 0 0 0 Yi 60 30 90 26 100 X1 1 1 0 0 3/2 X2 0 0 1 0 1/2 X4 1 0 0 0 0 X5 0 -1 0 0 0 X6 0 0 1 0 0 X7 0 0 0 1 0 X8 0 0 0 0 1 X3 0 0 0 1 1 Xi X4 X9 X6 X7 X8

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

−

→

f (x)

max

−

≤ −

4x + x 1

F(x) 0 -30 -15 -1 -9 0 -30 0 0 0 0 1 0 0 0 0 0 0

−

≤

x + x

2x + 1

−

x + x

2x + 1

1 2 3 2 ≤

≥

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪⎩ x 1

→

= −

20y

min

Xi X4 X1 X6 X7 X8 F(x) Yi 30 30 90 26 55 450 0 X1 0 1 0 0 0 0 0 X2 0 0 1 0 1/2 -9 0 X3 0 0 0 1 1 -30 0 X4 1 0 0 0 0 0 0 X5 1 -1 0 0 3/2 -15 0 X6 0 0 1 0 0 0 0 X7 0 0 0 1 0 0 0 X8 0 0 0 0 1 0 0 Ci 0 15 0 0 0

0, x Giải. Bài toán đối ngẫu: + 12y g(y)

1 −

2 ≥

−

≤

y 3

1 2 +

= −

−

3 2 y

≥

0, y

⎧ ⎪ ⎪ ⎨ ⎪ ⎪⎩ y Các cặp ràng buộc đối ngẫu như sau:

≤ −

4x + x 2x 2

0≥ 0≥

1y 2y

−

≤ 8

2x + 1

x + x 2

Xi X4 X1 X6 X3 X8 F(x) Yi 30 30 90 26 29 1230 0 X1 0 1 0 0 0 0 0 X2 0 0 1 0 1/2 -9 0 X3 0 0 0 1 0 0 0 X4 1 0 0 0 0 0 0 X5 1 -1 0 0 3/2 -15 0 X6 0 0 1 0 0 0 0 X7 0 0 0 1 -1 30 0 X8 0 0 0 0 1 0 0 Ci 0 15 0 30 0

y3 tuỳ ý

−

x + x

2x + 1

− 1 2 3 2

−

≥ 2

0≥ 0≤

1x 2x

≤

y 3

Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x5 vậy biến đưa vào là : x5 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5

x3 tuỳ ý

−

− 1 2 +

= − 5

2y 3 2 y

= −

f (x)

min

− → x 4

Xi X4 X1 X6 X3 X5 F(x) Yi 32/3 148/3 90 26 58/3 1520 0 X1 0 1 0 0 0 0 0 X2 -1/3 1/3 1 0 1/3 -4 0 X3 0 0 0 1 0 0 0 X4 1 0 0 0 0 0 0 X5 0 0 0 0 1 0 0 X6 0 0 1 0 0 0 0 X7 2/3 -2/3 0 1 -2/3 20 0 X8 -2/3 2/3 0 0 2/3 10 0 Ci 0 15 0 30 0

1 −

2 +

3 2

−

≤

4 +

3 3x

1 2x

2 6x

1 −

2 +

−

≥

4 6

3 x

1 ≥

≤

4 0

⎧ ⎪ ⎨ ⎪ ⎩ x 1

Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5

Xi X4 X1 X6 X3 X2 F(x) Yi 30 30 32 26 58 1752 0 X1 0 1 0 0 0 0 0 X2 0 0 0 0 1 0 0 X3 0 0 0 1 0 0 0 X4 1 0 0 0 0 0 0 X5 1 -1 -3 0 3 12 0 X6 0 0 1 0 0 0 0 X7 0 0 2 1 -2 12 0 X8 0 0 -2 0 2 18 0 Ci 0 15 0 30 9

x 3 2 0, x 0, x 4 Giải. Bài toán đối ngẫu:

Phương án tối ưu của bài toán mở rộng là : (30,58,26,30,0,32,0,0,0) Giá trị hàm mục tiêu đạt được là : F(x) = 1752 15. Lập các bài toán đối ngẫu của các bài toán QHTT sau và xác định các cặp ràng buộc đối ngẫu:

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

→

g(y)

max

= −

f (x)

min

− → x 4

≤ −

3x 1 −

2 +

3 ≥

−

≥

−

3 y

2 6y

1 2y

≤

−

3 3x

4 3x

−

1 y

2 +

−

x 1 2x 1 −

3 x

x 2

3 ≥ −

2 −

1 +

≥

x 1 ≤

≥

0, x

⎧ ⎪ ⎨ ⎪ ⎩ x 1

1 ≤

≥

0, y

→

0, x 4 Giải. Bài toán đối ngẫu: g(y)

max

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ y Các cặp ràng buộc đối ngẫu như sau:

y1 tuỳ ý

−

x + 2x

= 2

≥ −

−

4 +

1 2x

≤

−

3 y

1 2y

2 6y

≤ y2 ≤ 0 y3 ≥ 0

−

2 6x + 3x 2 x + x

3 x

4 ≥ 6

−

1 y

3 ≤ −

2 −

1 +

1 ≥

≤

0, y

2 6y 3y

1 +

2 −

y 1 2y 1 − y y

2y − + 3y

y 3 − y 3 + y y

≤ − 3 ≥ 1 = 3 3 ≥ − 1

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ y Các cặp ràng buộc đối ngẫu như sau:

1 − x 2 1 0≥ 1x 0≤ 2x x3 tuỳ ý 0≤ 4x

y1 ≥ 0

−

≥ 2

x + 2x

f (x)

max

y2 ≤ 0

≤

−

x + x 3 6x + 3x + 3x

−

≤

−

x 1 x + 4x

− → x 3 6

2 2x

y3 tuỳ ý

2 +

3 −

4 = 6

3 ≥

−

x + x + 2x 2 3 x + 2x

1 2x 1 ≥

≤

⎧ ⎪ ⎨ ⎪ ⎩ x

2 6y 3y

1 +

2 −

y 1 2y 1 − y y

2y − + 3y

y 3 − y 3 + y y

≥ − 3 ≤ 1 = 3 3 ≤ − 1

1 2x 1 − x x 2 1 0≤ 1x 0≥ 2x x3 tuỳ ý 0≥ 4x

→

0, x Giải. Bài toán đối ngẫu: g(y)

min

−

y + 2y

−

3 ≥

−

16. Với bài toán QHTT đã cho và phương án tối ưu tương ứng hãy lập bài toán đối ngẫu và tìm PATU của bài toán đối ngẫu (không giải trực tiếp bằng phương pháp đơn hình): a)

max vôùi phöông aùn toái öu x = (3, 3, 1 ,0)

f (x)

− → x 4

≤ −

3 +

2 2y

1 2y

2 −

−

3 =

1 x + 2x

x 1

≤

1 0, y

2 0

4 +

−

3 3x

2 +

2 2x + x 1 x + x

4 7.

3 x + x 3

⎧ ⎪ ⎨ ⎪ ⎩

⎧ ⎪ 4y ⎨ ⎪− ⎩ ≥ y Các cặp ràng buộc đối ngẫu như sau:

x + 4x

0≥

≤ 6

≥

( j 1, 4)

1y y2 ≤ 0

Giải. Bài toán đối ngẫu của bài toán trên là:

3 6≥ 4

+ +

= y3 tuỳ ý − y 4y −

≤ −

1 2y

y + 2y − y y 2 3 + + 2y

= 1 3 ≥ 2 2y

− − x + x + 2x 2 1 3 − x + 2x 2x 1 2 x1 tuỳ ý 0≥ 2x 0≤ 3x

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

→

(1 ')

g(y)

min

→

f (x)

min vôùi phöông aùn toái öu x = (0, 5, 11, 3)

≥

3 2;

2x 1 +

2 −

3 =

−

≥

1 y + y + y

(2 ')

2 +

3 ≥

x 1 +

4 22

−

≥ −

2 3y + y 2

≥

3 ≥ −

y + y + y

1 2 y + 2y + y ⎧ ⎪− ⎪ 1 ⎨ 2y ⎪ 1 ⎪− ⎩

≤

(3 ')

y (j 1, 3) tuøy yù.

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

≥

(j 1, 4)

0x = (3, 3, 1 ,0) .

Theo giả thiết, bài toán đã cho có PATU là Bây giờ ta tìm PATU

0 0 (y , y , y ) 2 3

0 1

Giải. Bài toán đối ngẫu của bài toán trên là:

0 1

→

(1 ')

g(y)

24y

22y

20y

max

y + 2y + y

0 1

0 2

0 3

≤

−

1 2;

nên ta có

0 x 1 x

0 2

−

= ⇔ 1

0 y + y + y 2

0 1

0 3

0 2

1 +

≤

= > 1

0 3

(2 ')

⎧ ⎪ ⎨ ⎪ ⎩

−

= −

0 1

0 3y + y 2

0 3

⎧ ⎪ ⎨ ⎪ ⎩

≤

2 y

3 y

4 2;

0 3

của bài toán đối ngẫu. 2 11 7 11 6 11

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪⎩

4 +

≤

2 2y

⎧ ⎪ ⎪ 1 ⎨ 2y ⎪ ⎪− ⎩ ≥

≥

≤

1 y 1 0, y

(3 ')

3 0.

Vậy PATU của bài toán đối ngẫu là y0 = (2/11, 7/11, 6/11) với g(y0) = 8.

= −

−

f (x)

min vôùi phöông aùn toái öu x = (

,0,0)

+ → x 5

3 5 1 2 2 2

2 0, y 0x = (0, 5, 11, 3) . của bài toán đối ngẫu.

0 0 (y , y , y , y ) 2 4

0 1

0 3

−

ta thấy không xảy ra

≤

−

x 1 2x

2 3x

3 5x

4 2x

5 7x

Theo giả thiết, bài toán đã cho có PATU là Bây giờ ta tìm PATU 1) Thế phương án x0 vào bất phương trình ràng buộc thứ 4: dấu đẳng thức (5 + 11 < 20) nên ta có

0.=

2 −

3 +

4 +

5 =

⎧ ⎪ ⎨ ⎪ ⎩

0 1

0 2

0 1

0 2

0 3

0 4

0 1

0 2

0 3

≥

(j 1, 5)

nên ta có

2) Do

0 3

⇔

1 2 1

0 2

Giải. Bài toán đối ngẫu của bài toán trên là:

0 4

⎧ ⎪ ⎨ ⎪ ⎩

−

0 1 y

0 2 2y

0 4 y

0 1 y

0 2 2y

0 1

0 2

0 3

0 1

0 2

0 3

⎧ ⎪ ⎨ ⎪ ⎩

0 3

→

(1 ')

g(y)

max

3 2

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

≤ −

2 +

1 +

3 ≤ −

2 3y

y 1 2y

≤ −

−

3 2y

2 5y

1 3y

(2 ')

→

−

Vậy PATU của bài toán đối ngẫu là y0 = (1/2, 1, 3/2, 0) với g(y0) = 46. d)

f (x)

max vôùi phöông aùn toái öu x = (0, 15, 6, 2, 0)

3x 1

1 +

≤ −

−

≥

−

4 8x

−

≤

2 7y

y 1 5y

⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎪− ⎩

−

≥

20x

x 1

(3 ')

y (j 1, 3) tuøy yù.

3 2

Theo giả thiết, bài toán đã cho có PATU là

0 x = (

,0,0)

−

≤

−

x 1

15 2

3 4

3 2

5x 1 23 2 17 4

Bây giờ ta tìm PATU

3 5 1 2 2 2 của bài toán đối ngẫu.

0 0 (y , y , y ) 2 3

0 1

≤

x 1

3 / 2

1 2

= −

0 y 1

0 2

0 1

nên ta có

5 / 2

0 x 1 x

3 2 ≥

⎧ ⎪ ⎪− ⎪⎪ ⎨ ⎪ ⎪ ⎪ ⎪⎩ x

(j 1, 5)

0 2

0 3 = − ⇔ 4

0 3

0 1

0 2

1 / 2

0 3

= −

−

⎧ ⎪ ⎨ ⎪ ⎩

0 3

0 1

0 3

0 2

⎧ ⎪ ⎨ ⎪ ⎩

Giải. Bài toán đối ngẫu của bài toán trên là:

− Vậy PATU của bài toán đối ngẫu là y0 = (−27, 18, −4) với g(y0) = −15.

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

−

→

c) f (x)

max

= −

−

d) f (x)

max

2x 1

− → x 5

→

(1 ')

g(y)

20y

min

≥

−

3 12

4x 1 +

2 ≥

−

2 3x 5

3x 5

−

4 4x

1 2x

−

4 4x

x 1 2x 1

−

≥

3 2

23 2

1 −

2 +

3 −

4 ≤ −

5 16

−

≥

4 x

3x 1

⎧ ⎪ ⎨ ⎪ ⎩

≥

15 2 17 4 1;

≥

= 0 ( j 1, 5)

= 0 (j 1, 5)

−

≥

(2 ')

3 2

1 2

3 3 4

−

≥ −

2y 1

≥ −

3 2 6y

20y

8y 1

Giải. Trước hết, ta dùng phương pháp đơn hình để giải các bài toán đã cho tìm phương án tối ưu x0. Sau đó, dùng phương pháp như trong Bài 16 để tìm phương án tối ưu y0 của bài toán đối ngẫu. Kết quả như sau: a) x0 = (0, 0, 12, 4), y0 = (3/2, 0, 2), f(x0) = g(y0) = 52. b) x0 = (0, 6, 5, 0), y0 = (−3, 4, 0), f(x0) = g(y0) = 45

⎧ ⎪ ⎪ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪⎩ ≤

≤

≥

(3 ')

0, y

0, y 0x = (0, 15, 6, 2, 0) .

c) Bài toán đã cho vô nghiệm nên bài toán đối ngẫu cũng vô nghiệm. d) x0 = (0, 3, 9, 0, 2), y0 = (−1, 2, −2), f(x0) = g(y0) = 28.

của bài toán đối ngẫu.

0 0 (y , y , y , y ) 2 4

0 1

0 3

Theo giả thiết, bài toán đã cho có PATU là Bây giờ ta tìm PATU 1) Thế phương án x0 vào bất phương trình ràng buộc thứ 2 của bài toán đã cho:

−

≥

20x

x 1

23 2

3 2

0.=

ta thấy không xảy ra dấu đẳng thức (3.15 −(3/2).6 – 6.2 > 20) nên ta có

→

18. Lập các bài toán đối ngẫu và giải các bài toán đối ngẫu bằng phương pháp đơn hình. Dùng kết quả trên để suy ra nghiệm của các bài toán đã cho (không giải trực tiếp bằng phương pháp đơn hình): Giải. Trước hết ta lập các bài toán đối ngẫu: 50x a) f (x)

max

18x

27x 1

0 2

≤

x + 2x + x

2 2;

2) Do

nên ta có

0 3

−

3 −

≤

0 4

⎧ ⎪ ⎨ ⎪ ⎩

2 −

3 ≤ −

1 2x + x 1 x + 2x

≤

⎧ ⎪ ⎨ ⎪ ⎩ x ; x tuøy yù; x

0 2

0 1

= −

0 1

−

= ⇔ −

= ⇔ 2

0 3

0 2

0 4

0 3

0 4

0 1

−

→

2 3 có bài toán đối ngẫu là 2y g(y)

min

1 2

3 2

1 2

0 3 3 4

0 4

⎧ ⎪ ⎨ ⎪ ⎩

1 −

3 27;

2 2y + y 2

−

= −

−

0 3

0 2

0 2y 1

0 1

0 3

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩

3 2

50;

3 2y + y + 2y 2 −

1 −

3 ≤

18.

⎧ ⎪ ⎨ ⎪ ⎩

≥

→

b) f (x)

= 0(j 1, 3). = 2x

min

≥

4x 1 2x

3 40

−

≥

3 4x

2 x 4 x

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ Vậy PATU của bài toán đối ngẫu là y0 = (–1, 0, 2, 5) với g(y0) = 25. 17. Giải các bài toán QHTT sau bằng phương pháp đơn hình. Lập các bài toán đối ngẫu và dùng kết quả trên để suy ra nghiệm của bài toán đối ngẫu (không giải trực tiếp bằng phương pháp đơn hình): a)

min

f (x)

→

b) f (x)

min

−

≤

+ → x 4

2 3x

3 3x

4 2x

⎧ 1 ⎪ x ⎨ 1 ⎪− 2x ⎩

≥

−

≤

4x 1 x

3 21

−

≤

2 x

x 1 3x

−

≥

2 2x

2 3x 3 3x

4 4x 4

= ≥ 0 ( j 1, 4) có bài toán đối ngẫu là

−

≥

4 2x

3x 1

⎧ ⎪ − ⎨ ⎪− ⎩

2x ⎧ 1 ⎪ x ⎨ 1 ⎪− x ⎩

≥

(j 1, 4)

= 0 ( j 1, 4)

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

→

g(y)

40y

32y

69y

max

−

→

g(y)

min

2 3

13 3

−

≤

1 + y

2 2y

≤

3 2;

−

≥

3 −

≤

4y + 3y 2 2y + y 1 −

−

≤

2 2y

3 2y

−

≥ −

2 3 3y

−

2 ≥ −

1 y

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ y 1 =

0, y +

≤ +

→

≥ 2 2x

3 0, y 3 + 3x

0. 4x

min

c) f (x)

−

≥ −

y + 3y

1 ≥ 5x 1 +

2 −

3 ≥

≥

−

2 2x

4x 4 3x

−

≥ −

y + 7y

2 ≥

⎧ ⎪ 2 ⎪ 3 ⎪ 5y ⎪ ⎪ ⎨ ⎪ ⎪− ⎪ ⎪ ⎪ ⎩

2 5 3 4 3

5 3 13 3

2 +

3 +

−

≥

x 1

≥

= 0 (j 1, 3)

2x ⎧ 1 ⎪− x ⎪ 1 ⎨ − x ⎪ ⎪ ⎩

≥

= 0 (j 1, 4)

→

có bài toán đối ngẫu là + = g(y) 14y

13y

10y

max

1 −

≤

2 y + y

≤

−

1 y + 2y

4 y + y

4 ≤

1 3y

Ta dùng phương pháp đơn hình để giải các bài toán đối ngẫu tìm phương án tối ưu y0. Sau đó, dùng phương pháp như trong Bài 16 để tìm phương án tối ưu x0 của bài toán đã cho (chú ý rằng bài toán đã cho chính là bài toán đối ngẫu của bài toán đối ngẫu). Kết quả như sau: a) Bài toán đối ngẫu vô nghiệm nên bài toán đã cho cũng vô nghiệm. b) y0 = (3/4, 1/2, 0), x0 = (0, 3, 20, 0), g(y0) = f(x0) = 46. c) y0 = (1/2, 6, 21/2, 0), x0 =(0, 21, 11, 2), g(y0) = f(x0) = 85. d) y0 = (1, 5, 3), x0 =(6, 0, 5, 2, 0), g(y0) = f(x0) = − 6.

2 2y + y 3 −

≤

2 4y

4 3y

⎧ ⎪ ⎪ ⎨ − ⎪ ⎪− ⎩

≥

= 0 (j 1, 4)

--------------------------------------------

MỘT SỐ ĐỀ THI CAO HỌC THAM KHẢO (TRƯỜNG ĐH KINH TẾ - LUẬT TP HCM)

−

→

f (x)

max

x 1

−

≤

Bài 1 (2005). Giải bài toán: +

≤

2 5 3

3 4 3

f(x) = – 4x1 – 3x2 → min x 2 2 ≤

x 1 +

−

≤ −

13 3

x 2 16

≤

−

≤

2 3 2 3 −

5 3 3x

2 3 13 3 7x

⎧ ⎪ ⎨ ⎪ ⎩ x

1, 2

x 1 x 4 1 ≥

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩

f x

max

( ) 3 =

−

x 1

x 2

x 3

x 4

x − → 5

≥

( j 1, 5)

Bài 2 (2007). a) Giải bài toán: =

(

)

có bài toán đối ngẫu là

x 1 x 2 4 x 3

x 3 x 3 x 4

x 4 x 5

⎧ ⎪ ⎨ ⎪ ⎩

1,5

≥

b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D).

Printed with FinePrint trial version - purchase at www.fineprint.com

Trần Ngọc Hội

Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính

f x ( )

min

Bài 3 (2008). Giải bài toán:

x 2

x + → 3

x = − − 1 ≤

−

x 3 6 ≥

x − + 1 +

x 2 2 +

−

⎧ ⎪ ⎨ ⎪ ⎩ x

x 3 x 2 3 1, 2,3.

x 1 x 2 1 ≥

x 2 x 2 j =

f x

min

( ) 12 =

→

Bài 4 (2009). a) Giải bài toán:

x 1

x 2

x 3

≥

(

)

≥

x 3 x 2 3 2 x 3 1, 2,3.

x ⎧ 1 ⎪ x + ⎨ 1 ⎪ + x ⎩ 1 0, x ≥

x 2 x 2 2 x 2 j =

f x ( )

= −

b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D). Bài 5 (2010 – Đợt 1). a) Giải bài toán:

+ → min

x 1

x 2

x 4

≤

−

(

)

4 18

x 2 x 2 x

≤

−

x 3 x 3 x 3

1, 2, 3, 4.

⎧ ⎪ ⎨ ⎪ ⎩ x

x 1 x 1 2 x 1 ≥

2 j =

b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm dạng chuẩn của bài toán (D).

f x ( )

max

−

Bài 6 (2010 – Đợt 2). a) Giải bài toán:

2 x = − 1

x 2

x 3

x − → 5

−

(

)

−

2 x

x 3 x 4 x

−

4 x 5 =

4 5 1, 2, 3, 4,5.

⎧ ⎪ ⎨ ⎪ ⎩ x

x 1 x 1 x 1 ≥

2 =

b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D).

Ôn thi cao học môn: Toán kinh tế - Bài giảng Quy hoạch tuyến tính

Chủ đề:

2. Một trại chăn nuôi sử dụng 3 loại thực phẩm I, II, III. Lượng chất dinh dưỡng Albumin, chất béo, chất đạm cho gia súc trong 1 ngày cũng như tỉ lệ các chất này trong 3 loại thức ăn được cho trong bảng sau:

Giải. Gọi x1, x2, x3 (kg) lần lượt là lượng thực phẩm loại I, II, III cần mua. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó

Printed with FinePrint trial version - purchase at www.fineprint.com

3. Để sản xuất 3 loại sản phẩm A, B, C cần dùng 4 loại nguyên liệu I, II, III, IV. Lượng dự trữ nguyên liệu, định mức tiêu hao nguyên liệu, tiền lãi cho 1 đơn vị sản phẩm được cho trong bảng sau:

Giải. Gọi

Printed with FinePrint trial version - purchase at www.fineprint.com

Giải. Gọi

7. Công ty Y dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần lượt là 50, 60, 70 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng sau:

Tiêu

Khu đất I

(3) 6. Công ty X dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần lượt là 30, 40, 50 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng sau:

Điều 2,2 2,3 2

Tiêu

Khu đất I

Điều 2,1 2,4 1,8

Printed with FinePrint trial version - purchase at www.fineprint.com

Giải. Gọi

ĐS: VN vì PATU của bài toán mở rộng là: (0,2,7,0,0,10) c)

(3) 8. Giải các bài toán QHTT sau bằng phương pháp đơn hình: a)

Printed with FinePrint trial version - purchase at www.fineprint.com

Giải. Chuyển về bài toán min bằng cách đặt g(x) = −f(x) = − x1 − 2x2 + x3 Ta có bài toán: (1)

Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: Hệ

BảngI

BảngII

BảngIII

BảngIV

BảngV

g(x)

Printed with FinePrint trial version - purchase at www.fineprint.com

Trong Bảng V ta thấy Δj ≤ 0 với mọi j = 1, 2,..., 5, nên bài toán mở rộng min có một phương án tối ưu là phương án cơ bản ban đầu

= −

39 / 2.

Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: An Hệ

Phương

BảngI

BảngII

Giải. Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 ≥ 0, x5 ≥ 0: (1)

BảngIII

BảngIV

Printed with FinePrint trial version - purchase at www.fineprint.com

Bảng II

Hãy tìm phương án sản xuất mỗi mặt hàng bao nhiêu đơn vị để tổng tiền lãi thu được cao nhất. Giải. Gọi x1, x2, x3, x4 lần lượt là số đơn vị mặt hàng H1, H2, H3, H4 cần sản xuất. Điều kiện: xj ≥ 0 (j = 1, ..., 4). Khi đó

Printed with FinePrint trial version - purchase at www.fineprint.com

Printed with FinePrint trial version - purchase at www.fineprint.com

Printed with FinePrint trial version - purchase at www.fineprint.com

Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: F(x) = Các ràng buộc: Trong đó:

Printed with FinePrint trial version - purchase at www.fineprint.com

Printed with FinePrint trial version - purchase at www.fineprint.com

0, x Giải. Bài toán đối ngẫu: + 12y g(y)

x 3 2 0, x 0, x 4 Giải. Bài toán đối ngẫu:

Printed with FinePrint trial version - purchase at www.fineprint.com

0, x 4 Giải. Bài toán đối ngẫu: g(y)

0, x Giải. Bài toán đối ngẫu: g(y)

16. Với bài toán QHTT đã cho và phương án tối ưu tương ứng hãy lập bài toán đối ngẫu và tìm PATU của bài toán đối ngẫu (không giải trực tiếp bằng phương pháp đơn hình): a)

Giải. Bài toán đối ngẫu của bài toán trên là:

Printed with FinePrint trial version - purchase at www.fineprint.com

Giải. Bài toán đối ngẫu của bài toán trên là:

Giải. Bài toán đối ngẫu của bài toán trên là:

Giải. Bài toán đối ngẫu của bài toán trên là:

Printed with FinePrint trial version - purchase at www.fineprint.com

Printed with FinePrint trial version - purchase at www.fineprint.com

MỘT SỐ ĐỀ THI CAO HỌC THAM KHẢO (TRƯỜNG ĐH KINH TẾ - LUẬT TP HCM)

Bài 1 (2005). Giải bài toán: +

Bài 2 (2007). a) Giải bài toán: =

Printed with FinePrint trial version - purchase at www.fineprint.com

Bài 3 (2008). Giải bài toán:

Bài 4 (2009). a) Giải bài toán:

b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D). Bài 5 (2010 – Đợt 1). a) Giải bài toán:

Bài 6 (2010 – Đợt 2). a) Giải bài toán:

2 x = − 1

------------------------------------

Printed with FinePrint trial version - purchase at www.fineprint.com

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính