Bài giảng Tính toán khoa học - Chương 8: Quy hoạch tuyến tính

Chương 8

QUY HOẠCH TUYẾN TÍNH

Linear Programming

Tính toán khoa học

Bài toán quy hoạch toán học

• Rất nhiều bài toán thực tế có thể phát biểu dưới dạng bài toán cực trị sau:

• Bài toán (1)-(4) được gọi là bài toán quy hoạch toán học

f(x) là hàm mục tiêu, gi,hj là các hàm ràng buộc. Tập

Gọi là tập ràng buộc, hay miền chấp nhận được. Mỗi vectơ x thuộc D được

gọi là lời giải chấp nhận được hay là phương án chấp nhận được

Tính toán khoa học

Bài toán quy hoạch toán học

• Phương án chấp nhận được x^*thỏa mãn

• Được gọi là pa tối ưu hay lời giải của bài toán, khi đó giá trị

• Được gọi là giá trị tối ưu của bài toán

Tính toán khoa học

Một số mô hình thực tế

 Bài toán lập kế hoạch sản xuất cho một nhà máy

 Bài toán khẩu phần ăn

 Bài toán vận tải

Tính toán khoa học

Bài toán lập kế hoạch sản xuất

• Một nhà máy có khả năng sản xuất n loại sản phẩm. Để sản

xuất các sản phẩm này cần phải sử dụng m loại nguyên liệu.

• Biết :

a_ijl-îng nguyªn liÖu lo¹i i cÇn thiÕt ®Ó s¶n xuÊt ra mét ®¬n vÞ s¶n phÈm lo¹i j;

b dù tr÷ nguyªn liÖu lo¹i i

i

c_j tiÒn l·i tõ viÖc b¸n mét ®¬n vÞ s¶n phÈm lo¹i ®¬n vÞ s¶n phÈm lo¹i j

(i=1,m ; j=1,n)

• Hãy xây dựng một chiến lược sản xuất mang lại nhiều lợi nhuận nhất.

x  0

x  (x , x₂,..., x_n)

– Gọi

là số sản phẩm loại j, kế hoạch sản xuất là

n

j

1

n

a * x

–

_jlà tổng chi phí nguyên liệu i do đó



ij

a * x  b



ij

j

i

j1

n

c x

_{– Tổng lợi nhuận thu được là}

j

j1

– Khi đó mô hình toán học của bài toán kế hoạch sản xuất được phát biểu

dưới dạng như ở sau.

Tính toán khoa học

Bài toán lập kế hoạch sản xuất

 Bài toán lập kế hoạch sản xuất cho một nhà máy

Tìm cực đại của

n

f(x ,x ,...,x )= c x



1

2

n

j j

j=1

víi ®iÒu kiÖn

n

a  b ,i=1,m



ij

i

j=1

x_j 0, j=1,n

Tính toán khoa học

Nội dung

I. Thuật toán đơn hình

3.1.1. Bài toán QHTT dạng chính tắc và dạng chuẩn

3.1.2. Phương án cơ sở chấp nhận được

3.1.3. Công thức số gia hàm mục tiêu. Tiêu chuẩn tối ưu

3.1.4. Thuật toán đơn hình dạng ma trận nghịch đảo

3.1.5. Thuật toán đơn hình dạng bảng

3.1.6. Tính hữu hạn của thuật toán đơn hình

3.1.7. Thuật toán đơn hình hai pha

II. Lý thuyết đối ngẫu

3.2.1. Xây dựng bài toán đối ngẫu

3.2.2. Các định lý đối ngẫu

3.2.3. Một số ứng dụng của lý thuyết đối ngẫu

Tính toán khoa học

I. THUẬT TOÁN ĐƠN HÌNH

Tính toán khoa học

Nội dung

1. Bài toán QHTT dạng chính tắc và dạng chuẩn

2. Phương án cơ sở chấp nhận được

3. Công thức số gia hàm mục tiêu. Tiêu chuẩn tối ưu

4. Thuật toán đơn hình dạng ma trận nghịch đảo

5. Thuật toán đơn hình dạng bảng

6. Tính hữu hạn của thuật toán đơn hình

7. Thuật toán đơn hình hai pha

Tính toán khoa học

1. Bài toán QHTT dạng chính tắc và dạng

chuẩn

Tính toán khoa học

Bài toán QHTT tổng quát

• Bài toán QHTT tổng quát là bài toán tối ưu hoá mà trong đó chúng ta phải

tìm cực đại (cực tiểu) của hàm mục tiêu tuyến tính với điều kiện biến số

phải thoả mãn hệ thống phương trình và bất phương trình tuyến tính. Mô

hình toán học của bài toán có thể phát biểu như sau

n

f (x , x ,..., x )  c x  min(max),

(1)

(2)

(3)



1

2

n

j

j1

với điều kiện

n

a x  b ,i 1,2,..., p ( p  m)



ij

j

i

j1

n

a x  b ,i  p 1, p  2,...,m



ij

j

i

j1

x_j 0, j 1,2,...,q (q  n)

x_j 0, j  q 1,q  2,...,n

(4)

(5)

• Ký hiệu x_j<> 0 để chỉ ra rằng biến x_jkhông có đòi hỏi trực tiếp về dấu.

Tính toán khoa học

Bài toán QHTT tổng quát

• Ràng buộc:

n

a x  b ,i 1,..., p



ij j

i

j1

được gọi là ràng buộc cơ bản dạng đẳng thức.

• Ràng buộc:

n

a x  b ,i  p 1,...,m



ij j

i

j1

được gọi là ràng buộc cơ bản dạng bất đẳng thức.

• Ràng buộc:

x_j 0, j 1,...,q

được gọi là ràng buộc về dấu của biến số.

Tính toán khoa học

Bài toán QHTT dạng chính tắc

• Ta gọi bài toán QHTT dạng chính tắc là bài toán sau:

n

f (x , x ,..., x )  c x  min,



1

2

n

j j

j1

n

a x  b ,i 1,2,...,m



ij j

i

j1

x_j 0, j 1,2,...,n

Tính toán khoa học

Bài toán QHTT dạng chuẩn

• Ta gọi bài toán QHTT dạng chuẩn là bài toán sau:

n

f (x , x ,..., x )  c x  min,



1

2

n

j j

j1

n

a x  b ,i 1,2,...,m



ij j

i

j1

x_j 0, j 1,2,...,n

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

• Rõ ràng Bài toán QHTT dạng chính tắc là trường hợp riêng của

QHTT tổng quát.

n

f (x , x ,..., x )  c x  min(max),

(1)

(2)

(3)



1

2

n

j

n

j1

n

f (x , x ,..., x )  c x  min,



1

2

n

j

a x  b ,i 1,2,..., p ( p  m)

j1



ij

j

i

j1

n

a x  b ,i 1,2,...,m



ij

j

i

a x  b ,i  p 1, p  2,...,m



ij

j

i

j1

x_j 0, j 1,2,...,n

x_j 0, j 1,2,...,q (q  n)

x_j 0, j  q 1,q  2,...,n

(4)

(5)

• Mặt khác, một bài toán QHTT bất kỳ luôn có thể đưa về dạng

chính tắc nhờ các phép biến đổi sau:

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

a) Đưa ràng buộc bất đẳng thức dạng “” về dạng “”.

Bất phương trình tuyến tính

n

a x  b



ij j

i

j1

là tương đương với bất phương trình tuyến tính sau

n

 a x  b



ij j

i

j1

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

b) Đưa ràng buộc dạng “=” về dạng “”.

Phương trình tuyến tính

n

a x  b



ij j

i

j1

là tương đương với hệ gồm 2 bất phương trình tuyến

tính sau

n

a x  b



ij j

i

j1

n

 a x  b



ij j

i

j1

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

c) Đưa ràng buộc dạng “” về dạng “=”.

Bất phương trình tuyến tính

n

a x  b



ij j

i

j1

là “tương đương” với hệ gồm 1 phương trình tuyến tính và một

điều kiện không âm đối với biến số sau đây

n

a x  y  b



ij j

i

j1

y  0

• Tương đương hiểu theⁱo nghĩa: Nếu (x₁, x₂, ..., x_n, y_i) là nghiệm

của hệ thì (x₁, x₂, ..., x_n) là nghiệm của bất phương trình.

• Biến y_iđược gọi là biến bù (hay biến phụ).

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

d) Thay mỗi biến không có điều kiện dấu x_jbởi hiệu hai biến có điều kiện về

dấu:

x_j x^_j x^_j,

x^_j 0, x^_j 0.

e) Đưa bài toán tìm cực đại về bài toán tìm cực tiểu. Bài toán tối ưu hoá

max { f(x): x  D}

là tương đương với bài toán tối ưu hoá

min {- f(x): x  D}

theo nghĩa: Lời giải của bài toán này cũng là lời giải của bài toán kia và

ngược lại, đồng thời ta có đẳng thức:

max { f(x): x  D} = - min {- f(x): x  D}

Tính toán khoa học

Đưa BT QHTT tổng quát về dạng chính tắc

f) Đưa ràng buộc dạng “” về dạng “=”. Bất phương trình tuyến

tính

n

a x  b



ij j

i

j1

là “tương đương” với hệ gồm 1 phương trình tuyến tính và một

điều kiện không âm đối với biến số sau đây

n

a x  y  b



ij j

i

j1

y_i 0

• Tương đương hiểu theo nghĩa: Nếu (x₁, x₂, ..., x_n, y_i) là nghiệm

của hệ thì (x₁, x₂, ..., x_n) là nghiệm của bất phương trình.

• Biến y_iđược gọi là biến bù (hay biến phụ).

Tính toán khoa học