Bai 2 Chuong 1

Bài 2. Bài toán quy hoạch tuyến tính 2.1 Các khái niệm cơ bản 2.2 Bài toán QHTT dạng chính tắc và dạng chuẩn tắc 2.3 Giải bài toán QHTT trong mặt phẳng

1

2.1 Các khái niệm cơ bản 2.1.a Phát biểu bài toán 2.1.b Hàm mục tiêu 2.1.c Phương án

2

2.1.a Phát biểu bài toán Tìm các biến số x1 , x2 ,..., xn   sao cho hàm tuyến tính f ( x1 ,..., xn )  c1x1  c2 x2  ...  cn xn  min(max)

với các điều kiện  n   a ij x j  bi j  1   n   a ij x j  bi D :  j  1  n   a x b ij j i  j  1  x  0 , j  1, k  j

i  1, p i  p  1, q i  q  1, m x j  free , j  k  1, n 3

Cho một số ví dụ Chú ý: + Hàm mục tiêu f(x) là tuyến tính + Các điều kiện trong miền ràng buộc D là - phương trình - bất phương trình - dấu của các biến: ≤, ≥, =, tự do

4

2.1.b Hàm mục tiêu Tính chất

max  f ( x)  min  f ( x) xD

xD

Ta chỉ nghiên cứu bài toán cực tiểu hoá hàm f(x) trên D f ( x1 ,..., xn )  c1x1  c2 x2  ...  cn xn  min

viết ngắn gọn

min f ( x) xD

5

2.1.c Phương án

min f ( x) xD

 Véc tơ x   x1 , x2 ,..., xn  D được gọi là một phương án x là phương án  x thoả mãn D Tập D được gọi là tập các phương án  Phương án x*D được gọi là phương án tối ưu nếu f (x*)  f (x) x  D

Cho ví dụ?

6

Ví dụ Hàm mục tiêu f ( x , y)  3x  5 y  min

miền ràng buộc 2 x  y  6y  D :  4 x  x  0,

 

 12 y 0

Phương án tối ưu x* = (2,4) 7

8 24

2.2 Bài toán quy hoạch tuyến tính 2.2.a Dạng chính tắc 2.2.b Dạng chuẩn tắc 2.2.c Mối quan hệ giữa chúng

8

Viết dưới hình thức ma trận   A   

a11 a12 ... a1n   c1   x1   b1  c  x  b  a21 a21 ... a2n  2 2 2    c x b  :  : : : :   :  :        am1 am2 ... amn   cn   xn   bn 

Kí hiệu x  y nếu x j  y j , j  1, n .

Biểu diễn bài toán QHTT ở ví dụ trên qua ma trận?

9

2.2.a Dạng chính tắc Viết tường minh f ( x1 ,..., xn )  c1x1  c2 x2  ...  cn xn  min

n  aij x j  bi  j 1   x j  0



i  1, n j  1, n

Biểu diễn qua ma trận f ( x )  c t x  min

 Ax  b   x0 10

2.2.b Dạng chuẩn tắc Viết tường minh f ( x1 ,..., xn )  c1x1  c2 x2  ...  cn xn  min

n  aij x j  bi  j 1   x j  0



i  1, n j  1, n

Biểu diễn qua ma trận f ( x)  ct x  min  Ax  b   x0 11

Câu hỏi: i) Cho 2 ví dụ tương ứng với 2 dạng trên? ii) Sự khác nhau của dạng chính tắc và dạng chuẩn tắc? iii) Mối quan hệ của 2 dạng này?

12

2.2.c Mối quan hệ Quan hệ 1. Đưa bất đẳng thức dấu ≤ về dấu ≥, ngược lại n

n

j 1

j 1

 aij x j  bi   aij x j  bi Ví dụ i) Đưa dấu ≤ về dấu ≥ 2x1  x2  x3  4

ii) Đưa dấu ≥ về dấu ≤ x1  2x2  x3  x4  3 13

2.2.c Mối quan hệ (tiếp) Quan hệ 2. Đưa dấu đẳng thức = về dấu ≥  n aij x j  bi  n  j 1 aij x j  bi   n  j 1   aij x j   bi  j 1







Ví dụ Đưa dấu = về dấu ≥ 2x1  x2  x3  4 14

2.2.c Mối quan hệ (tiếp) Quan hệ 3. Đưa dấu bất đẳng thức ≥ về dấu =  n n  aij x j  yi  bi aij x j  bi   j 1  j 1 yi  0 





Trong đó yi là một biến phụ, biến giả Câu hỏi Hãy đưa dấu ≤ về dấu = ?

15

2.2.c Mối quan hệ (tiếp) x Quan hệ 4. Thay biến j không có ràng buộc về dấu bằng

2 biến phụ có ràng buộc về dấu   xj  xj  xj

Trong đó

xj  0, xj  0

16

Ví dụ i) Đưa dấu ≥ về dấu = 2x1  x2  x3  4

ii) Đưa dấu ≤ về dấu = x1  2x2  x3  x4  3

iii) Đưa miền ràng buộc với biến có dấu âm, tự do về miền ràng buộc với biến có dấu dương. 2 x1  x2  x3  4  x1  free   x2  0   x3  0 17

Nhận xét i) Mọi bài toán QHTT luôn có thể đưa về dạng chính tắc hay chuẩn tắc ii) Từ nay ta chỉ nghiên cứu bài toán QHTT có dạng chính tắc hoặc chuẩn tắc

18

Đưa bài toán QHTT tổng quát về dạng chính tắc Bước 1. Chuyển max -> min Bước 2. Đưa các dấu ≥, ≤ về dấu = Bước 3. Xử lý dấu của các biến Bước 4. Lập hàm mục tiêu mới, chú ý: + Dấu của hệ số thay đổi do Bước 1 + Hệ số của các biến phụ do Bước 2 và Bước 3

19

Ví dụ Đưa bài toán sau về dạng chính tắc f (x)  2x1  x2  3x3  5x4  max

Với miền ràng buộc  x1 3x2 5x3 x4  16 2 x x2 2x3 2x4  4 1  4x1 3x2  x3  x4  9  x2 0  x1  0 x3  x4 free  20

Mục 2.3 Giải bài toán QHTT trong mặt phẳng Xem trang 10-11/[7]-Hiếu Bài tập Bài 1-3. Trần Vũ Thiệu Bài 4-5. Trần Vũ Thiệu Bài 10. a,b,c P.Q.Khánh 21