Các dạng ký hiệu LPP khác nhau (tổng quát, chính tắc, đối xứng). Phương pháp Simplex để giải quyết vấn đề lập trình tuyến tính

Bất kỳ bài toán lập trình tuyến tính nào cũng có thể được rút gọn thành một bài toán lập trình tuyến tính ở dạng chuẩn. Để làm được điều này, trong trường hợp chung, bạn cần phải có khả năng giảm thiểu vấn đề tối đa hóa thành vấn đề tối thiểu hóa; đi từ ràng buộc bất bình đẳng sang ràng buộc bình đẳng và thay thế các biến không tuân theo điều kiện không phủ định. Cực đại của một số chức năng tương đương với cực tiểu của cùng một chức năng, lấy cùng dấu và ngược lại.

Quy tắc để giảm một bài toán lập trình tuyến tính về dạng chuẩn như sau:

Nếu trong bài toán ban đầu, yêu cầu xác định cực đại của một hàm tuyến tính, thì bạn nên đổi dấu và tìm điểm cực tiểu của hàm này;
nếu vế phải của các ràng buộc là số âm, thì ràng buộc này phải được nhân với -1;
nếu có sự bất bình đẳng giữa các ràng buộc, thì bằng cách đưa thêm các biến không âm, chúng được chuyển thành các giá trị bằng nhau;
nếu một số biến x j không có giới hạn về dấu hiệu, sau đó nó được thay thế (trong hàm mục tiêu và trong tất cả các hạn chế) bằng sự khác biệt giữa hai biến không âm mới:
x 3 = x 3 + - x 3 - , ở đâu x 3 +, x 3 - ≥ 0 .

ví dụ 1... Giảm bài toán lập trình tuyến tính về dạng chuẩn:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Chúng tôi giới thiệu vào mỗi phương trình của hệ thống ràng buộc các biến cấp x 4, x 5, x 6... Hệ thống sẽ được viết dưới dạng cân bằng, và trong phương trình thứ nhất và thứ ba của hệ thống giới hạn, các biến x 4, x 6được nhập ở phía bên trái bằng dấu "+" và trong phương trình thứ hai, biến x 5được nhập bằng dấu "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Các số hạng tự do ở dạng chính tắc phải là số dương, vì điều này, chúng tôi nhân hai phương trình cuối cùng với -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

Trong dạng chính tắc của bài toán lập trình tuyến tính, tất cả các biến có trong hệ thống các ràng buộc phải là số âm. Hãy để chúng tôi giả định rằng x 1 = x 1 "- x 7 , ở đâu x 1 "≥ 0, x 7 ≥ 0 .

Thay biểu thức này vào hệ thống các ràng buộc và hàm mục tiêu và viết các biến theo thứ tự tăng dần của chỉ số, chúng ta thu được một bài toán lập trình tuyến tính được trình bày dưới dạng chính tắc:

L min = 2x 1 ”+ x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 ”- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ”+ x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i = 2, 3, 4, 5, 6, 7.

Điều kiện tối ưu cho phương án cơ bản của bài toán LP chính tắc. Phương pháp Simplex và sự hội tụ của nó.

Phương pháp simplex là phổ quát, vì nó cho phép bạn giải quyết hầu hết mọi vấn đề lập trình tuyến tính được viết bằng hình thức kinh điển.

Ý tưởng của phương pháp simplex cải tiến nhất quán của kế hoạch, nằm ở chỗ, bắt đầu từ một số giải pháp hỗ trợ ban đầu, chuyển động được định hướng nhất quán bằng các giải pháp hỗ trợ của vấn đề một cách tối ưu nhất.

Giá trị của hàm mục tiêu không giảm theo chuyển động này đối với các nguyên công ở mức tối đa.

Vì số lượng giải pháp hỗ trợ là hữu hạn, nên sau một số bước hữu hạn, chúng ta sẽ có được giải pháp hỗ trợ tối ưu.

Một giải pháp cơ bản không âm được gọi là một giải pháp tham chiếu.

Thuật toán phương pháp Simplex

1. Mô hình toán học của bài toán nên kinh điển. Nếu nó không phải là canonical thì phải đưa nó về dạng canonical.

2. Tìm giải pháp hỗ trợ ban đầu và kiểm tra xem nó có tối ưu không.
Để làm điều này, hãy điền vào bảng simplex 1.
Chúng tôi điền vào tất cả các hàng của bảng của bước 1 theo dữ liệu của hệ thống các hạn chế và hàm mục tiêu.

Các trường hợp sau đây có thể xảy ra khi giải quyết vấn đề trên tối đa:

1. Nếu tất cả các hệ số của hàng cuối cùng của bảng đơn giản Dj ³ 0, sau đó được tìm thấy

dung dịch tối ưu.

2 Nếu ít nhất một hệ số Dj £ 0, nhưng đối với biến tương ứng không có một tỷ lệ đánh giá dương duy nhất, thì giải pháp chúng tôi dừng nhiệm vụ, vì F (X) ® ¥, tức là, hàm mục tiêu không bị giới hạn trong phạm vi các giải pháp khả thi.

Nếu ít nhất một hệ số của hàng cuối cùng là số âm và đối với biến tương ứng thì có ít nhất một mối quan hệ đánh giá tích cực, sau đó bạn cần phải sang một giải pháp tham khảo khác.

4.E nếu như có một số hệ số âm trong dòng cuối cùng, sau đó đến cột biến cơ sở(Bp) giới thiệu rằng Biến đổi tương ứng với hệ số âm lớn nhất về giá trị tuyệt đối.

5. Nếu ít nhất một hệ số Dk< 0 ,sau đó k - th cột chúng tôi chấp nhận cho người thuyết trình.

6. Đối với hàng đầu chúng tôi chấp nhận cái tương ứng với tối thiểu thái độ thành viên tự do bi thành hệ số dương dẫn đầu, k - đó cột.

7. Một phần tử nằm ở giao điểm của các hàng đầu và một cột được gọi là yếu tố hàng đầu.

Đang điền bảng simplex 2 :

· điền vào cột cơ sở bằng các số không và các số

· viết lại dòng đứng đầu bằng cách chia nó cho phần tử đứng đầu

Nếu hàng đầu có số 0, thì các cột tương ứng có thể được chuyển sang bảng đơn giản tiếp theo

· phần còn lại của các hệ số được tìm thấy bởi quy tắc "hình chữ nhật"

Chúng tôi nhận được một giải pháp hỗ trợ mới, mà chúng tôi kiểm tra vì sự tối ưu:

Nếu tất cả các hệ số của hàng cuối cùng Dj ³ 0, thì giải pháp được tìm thấy tối đa.

Nếu không, hãy điền vào bảng đơn giản bước thứ 8, v.v.

Nếu hàm mục tiêu F (X) yêu cầu tìm kiếm giá trị tối thiểu, sau đó là tiêu chí tính khả quan của vấn đề là một tỷ lệ cược không tích cực NS j với mọi j = 1,2, ... n.

Sự hội tụ của phương pháp đơn giản. Sự thoái hóa trong các vấn đề LP. Tính chất quan trọng nhất của bất kỳ thuật toán tính toán nào là sự hội tụ, nghĩa là khả năng thu được, trong quá trình áp dụng nó, các kết quả mong muốn (với độ chính xác nhất định) trong một số bước (lặp lại) hữu hạn.

Dễ dàng nhận thấy rằng các vấn đề với sự hội tụ của phương pháp đơn giản có thể tiềm ẩn phát sinh ở giai đoạn chọn giá trị của r (mục 2 ") trong trường hợp các giá trị nhỏ nhất của tỷ lệ giống nhau

sẽ đạt được cho một số hàng của bảng T (q) cùng một lúc. Khi đó, ở cột lặp tiếp theo b (β (q + 1)) sẽ không chứa phần tử nào.

Trang 1

Dạng chính tắc của bài toán được đặc trưng bởi ba đặc điểm sau: 1) một hệ thống các giới hạn thuần nhất ở dạng một hệ phương trình; 2) điều kiện thuần nhất của không phủ định, áp dụng cho tất cả các biến liên quan đến bài toán, và 3) cực đại của một hàm tuyến tính. Trong vấn đề này, cả ba tính năng này đều bị vi phạm.

Dạng chính tắc của bài toán lập trình tuyến tính thuận tiện ở chỗ có thể dễ dàng tìm được đỉnh ban đầu của vùng khả thi.

Xét dạng chính tắc của bài toán lập trình tuyến tính và phương pháp khử Jordan - Gauss.

Dạng chính tắc của một bài toán lập trình tuyến tính thường trở nên thuận tiện.

Khi biến đổi hệ thức về dạng chính tắc của bài toán lập trình tuyến tính, các bất đẳng thức (12) và (13) phải được thay thế bằng các đẳng thức. Đối với điều này, các biến không âm bổ sung được giới thiệu.

Chứng minh rằng các ma trận thực đi lại theo cặp đồng thời được rút gọn về dạng chính tắc của bài toán 1128 bằng một phép biến đổi tương tự sử dụng ma trận trực giao.

Về bản chất, (4) - (5) có thể được coi là dạng chính tắc của một bài toán lập trình phi tuyến, vì các phương pháp được trình bày trong Ch. Thông thường, trong các bài toán lập trình phi tuyến, yêu cầu về số nguyên của các biến không được đưa ra.

Các loại hạn chế và phương pháp biến đổi của chúng.

Dạng chính tắc của bài toán được đặc trưng bởi tính thuần nhất của hệ thống các ràng buộc dưới dạng một hệ phương trình; phát huy tối đa hàm mục tiêu; điều kiện không phủ định của tất cả các biến liên quan đến vấn đề.

Dạng bài toán chính tắc không thêm bất kỳ tính năng bổ sung nào vào sơ đồ tính toán được xem xét.

Đầu tiên chúng ta hãy xem xét dạng chính tắc thứ hai của bài toán tối thiểu.

Thuật toán simplex-meta có thể được chia thành hai giai đoạn. Ở giai đoạn đầu tiên, giải pháp cơ bản được tìm thấy bằng cách loại bỏ các biến. Nếu nó được tìm thấy, thì chúng ta có dạng chính tắc của bài toán cho quá trình chuyển đổi sang giai đoạn thứ hai. Ở giai đoạn thứ hai, nó được kiểm tra xem có giới hạn tối ưu hay không. Nếu nó tồn tại, thì các giải pháp cơ bản có thể chấp nhận được sẽ được xác định và trong đó giải pháp tối ưu được chọn.

Nếu bài toán được giải ở dạng chuẩn, thì chỉ một phần của các thao tác được giới thiệu trong đoạn thứ hai được sử dụng. Vì vậy, đối với bài toán tối thiểu chính tắc, chỉ trường hợp của Phần 3.4.1 được thực hiện và chỉ các phép toán hoán vị theo chu kỳ của các cột, quét một cột qua vùng giáp dọc, sửa lỗi vi phạm cấu trúc và một phần của phép toán cắt ngắn là cần thiết. Một cách đối xứng, khi giải quyết vấn đề chính tắc đến mức tối đa, chỉ trường hợp của đoạn 3.4.2 được thực hiện và các phép toán hoán vị hàng tuần hoàn, quét một hàng qua vùng biên ngang, sửa lỗi cấu trúc và các phần khác của phép toán cắt ngắn là cần thiết. . Nếu không, dạng chuẩn của vấn đề không thêm bất kỳ chi tiết cụ thể bổ sung nào.

Trong phần đầu tiên của phần giới thiệu, nó đã chỉ ra cách một bài toán lập trình tuyến tính tổng quát có thể được rút gọn thành một trong các dạng chính tắc. Về mặt kinh điển (mặt khác, việc mô tả phương pháp cải tiến tuần tự được đơn giản hóa một cách chính thức, vì không cần phải xem xét hai biến thể vi phạm điều kiện tối ưu và hai biến thể đi đến đỉnh tiếp theo. Tuy nhiên, trong nhiều trường hợp, Việc áp dụng phương pháp này cho các dạng chính tắc của bài toán hóa ra lại được ưa chuộng hơn, và trong phần này chúng ta sẽ tập trung vào các biến thể của phương pháp thu được đối với các bài toán lập trình tuyến tính cụ thể.

Số trang: 1

Trong cài đặt ban đầu, các LPP có thể thừa nhận nhiều hình thức ghi âm khác nhau. Vì vậy, trong một số nhiệm vụ, nó được yêu cầu để tối đa hóa chức năng mục tiêu, trong những nhiệm vụ khác - để giảm thiểu; một số ràng buộc tuyến tính có thể ở dạng bình đẳng, những ràng buộc khác ở dạng bất bình đẳng, v.v.

Đối với tính đồng nhất của bản ghi LPP, cái gọi là hình thức kinh điển Hồ sơ.

Họ nói rằng ZLP được viết ở dạng chuẩn nếu nó có dạng sau:

Lưu ý các đặc điểm sau của biểu mẫu chuẩn:

1) nó được yêu cầu để giảm thiểu hàm mục tiêu;

2) tất cả các ràng buộc tuyến tính, ngoại trừ yêu cầu về tính không phủ định của các biến, đều có dạng bằng nhau;

tất cả các biến đều tuân theo các yêu cầu không phủ định.

Hãy để chúng tôi chứng minh rằng bất kỳ LPP nào cũng có thể được rút gọn thành dạng chuẩn.

1) Nếu trong LPP bắt buộc phải đạt cực đại hàm mục tiêu f, thì chúng ta đặt g = - f và yêu cầu tối thiểu hóa hàm g. Chúng ta nhận được một LPP mới, tương đương với LPP ban đầu theo nghĩa là mỗi giải pháp tối ưu cho vấn đề ban đầu sẽ là giải pháp tối ưu cho vấn đề mới và ngược lại.

2) Giả sử rằng LPP có một ràng buộc tuyến tính có dạng

Chúng tôi thay thế ràng buộc này bằng hai ràng buộc sau:

ở đâu z - một biến mới được đưa vào hàm mục tiêu với hệ số bằng 0 (nói cách khác, biến z không được nhập vào hàm mục tiêu). Giá trị của biến z có thể được bỏ qua sau khi giải một bài toán mới.

Tương tự, ràng buộc khung nhìn được thay thế bằng hai ràng buộc:

3) Giả sử rằng trong LPP không phải tất cả các biến đều được yêu cầu là không âm. Sau đó, mỗi biến , trên đó yêu cầu về tính không âm không được áp đặt, có thể được biểu diễn dưới dạng hiệu số của hai biến không âm:

Mỗi lần xuất hiện một biến vào hàm mục tiêu hoặc các ràng buộc, chúng tôi thay thế sự khác biệt
... Sau khi giải quyết vấn đề mới với sự trợ giúp của (2.6), chúng ta quay trở lại các biến trước đó.

Với các kỹ thuật được chỉ định, bất kỳ LPP nào cũng được giảm xuống dạng chuẩn.

Thí dụ. Đưa về dạng chuẩn

Hãy thực hiện các hành động được mô tả.

Bây giờ chúng ta nhận được ZLP ở dạng chuẩn:

2.7. Khái niệm về phương án cơ bản zlp.

Hãy để ILP được đưa ra ở dạng chính tắc (2.3 - 2.5). Giả sử rằng hệ phương trình (2.4) được rút gọn thành dạng Jordan với các vế phải không âm:

(2.6)

ở đâu
.

Cân bằng các biến tự do bằng 0, chúng ta thu được nghiệm cơ bản của hệ thống (2.4)

Do điều kiện
tập giá trị của các biến (2.7) cũng thỏa mãn các ràng buộc (2.5). Do đó, (2,6) là quyết định có thể chấp nhận được của LPP.

Một giải pháp khả thi (2.7) được gọi là cơ bản có thể chấp nhận quyết định hoặc kế hoạch cơ bản của ZLP.Đồng thời, họ nói rằng các biến
tạo thành một cơ sở có thể chấp nhận được.

Nó chỉ ra rằng nếu ODR được mô tả bằng hình học, thì mỗi phương án hỗ trợ của ZLP tương ứng với đỉnh của đa diện. Do đó, định lý sau là đúng.

Nếu LPP có thể giải quyết được thì cần có phương án hỗ trợ tối ưu.

3. Phương pháp Simplex để giải zlp

3.1. Đặc điểm chung và các giai đoạn chính của phương pháp simplex

Người sáng lập ra phương pháp simplex là nhà toán học Liên Xô L.V. Kantorovich và nhà toán học người Mỹ J. Danzig.

Bất kỳ LPP nào cũng có thể được giải quyết bằng phương pháp simplex hoặc tính không xác định của nó có thể được phát hiện. Nhiều lớp đặc biệt của LPP có thể được giải quyết bằng các phương pháp khác hiệu quả hơn cho các lớp này. Tuy nhiên, ưu điểm của phương pháp simplex là tính linh hoạt của nó. Đối với hầu hết tất cả các máy tính, các chương trình tiêu chuẩn đã được phát triển để giải quyết LPP bằng phương pháp simplex.

Hãy để chúng tôi mô tả ý tưởng chung của phương pháp simplex.

Chúng tôi giả định rằng LPP được viết ở dạng chuẩn và hàm mục tiêu cần được giảm thiểu. Như chúng ta đã biết, phương án tối ưu cần được tìm kiếm trong số các phương án hỗ trợ của LPP. Phương pháp simplex không lặp lại tất cả các kế hoạch cơ sở (điều này thường là không thể do số lượng lớn của chúng), nhưng, bắt đầu từ một số kế hoạch cơ sở ban đầu, nó tuần tự chuyển sang các kế hoạch cơ sở khác với hàm mục tiêu giảm. Phương pháp simplex ngừng hoạt động khi tìm thấy phương án cơ sở tối ưu hoặc vấn đề được phát hiện là không thể giải quyết được.

Khi giải quyết LPP bằng phương pháp simplex, có thể phân biệt các giai đoạn sau:

1) đưa LPP về dạng chuẩn;

2) giảm hệ phương trình tuyến tính về dạng Jordan với vế phải không âm với việc kiểm tra đồng thời tính không xác định của LPP do sự không nhất quán của hệ thống các ràng buộc tuyến tính;

3) nghiên cứu kế hoạch cơ bản về tính tối ưu;

4) điều tra LPP về tính không xác thực do không có giới hạn từ bên dưới đối với ODR của hàm mục tiêu;

5) chuyển đổi sang một kế hoạch tham chiếu mới, "tốt hơn".

Dạng chuẩn của ZLP- Bài toán lập trình tuyến tính dạng ax = b trong đó a là ma trận các hệ số, b là vectơ ràng buộc.

Mục đích dịch vụ... Máy tính trực tuyến được thiết kế để chuyển đổi ZLP sang KZLP. Giảm vấn đề về dạng chính tắc có nghĩa là tất cả các ràng buộc sẽ có dạng bằng nhau bằng cách đưa thêm các biến bổ sung.
Nếu không có hạn chế nào được áp dụng cho bất kỳ biến x j nào, thì nó được thay thế bằng hiệu của các biến bổ sung, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Hướng dẫn. Chọn số lượng biến và số dòng (số lượng ràng buộc). Giải pháp kết quả được lưu trong tệp Word.

Cách đưa một bài toán lập trình tuyến tính về dạng chuẩn

Mô hình toán học của ZLP được gọi là căn bản nếu các ràng buộc trong nó được trình bày dưới dạng phương trình, với điều kiện là các biến không âm.

Mô hình toán học được gọi là kinh điển, nếu hệ thống các ràng buộc của nó được biểu diễn dưới dạng một hệ gồm m phương trình độc lập tuyến tính (hạng của hệ là r = m), cơ sở đơn vị, các biến tự do được xác định và hàm mục tiêu được biểu thị dưới dạng các biến tự do. Trong trường hợp này, các vế phải của phương trình là không âm (b i ≥ 0).

Các biến có trong một trong các phương trình của hệ với hệ số là một và không có trong các phương trình khác được gọi là ẩn số cơ bản và tất cả những người khác - miễn phí.

Giải pháp của hệ thống được gọi là căn bản nếu các biến tự do trong nó bằng 0 và nó có dạng:
X căn = (0, 0; b 1, ..., b m), f (X căn) = c 0

Giải pháp cơ bản là một điểm góc của tập hợp các giải pháp cho hệ thống, tức là xác định đỉnh của đa giác giải pháp mô hình. Trong số các giải pháp như vậy là giải pháp mà tại đó hàm mục tiêu có giá trị tối ưu.

Một giải pháp cơ bản được gọi là quan trọng nếu nó được chấp nhận, tức là tất cả các vế phải của các phương trình của hệ (hoặc bất phương trình) đều dương b i ≥ 0.

Dạng thu gọn của mô hình chuẩn là:
AX = b
X ≥ 0
Z = CX (tối đa)

Khái niệm về một giải pháp khả thi, một lĩnh vực của các giải pháp khả thi, một giải pháp tối ưu cho một bài toán lập trình tuyến tính.
Định nghĩa 1. Một vectơ X thỏa mãn hệ thống các ràng buộc LPP, bao gồm các điều kiện không phủ định, nếu có, được gọi là một nghiệm có thể chấp nhận được của LPP.
Định nghĩa 2. Tổng thể của tất cả các giải pháp khả thi tạo thành khu vực các giải pháp khả thi (ODS) của LPP.
Định nghĩa 3. Giải pháp khả thi mà hàm mục tiêu đạt cực đại (hoặc cực tiểu) được gọi là giải pháp tối ưu.

Ví dụ 1. Rút gọn bài toán LP tiếp theo về dạng chính tắc: F (X) = 5x 1 + 3x 2 → max theo các ràng buộc:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Mô hình được viết dưới dạng tiêu chuẩn. Chúng tôi giới thiệu các biến số dư không âm x 3, x 4, x 5, x 6, mà chúng tôi thêm vào bên trái của các ràng buộc bất đẳng thức. Trong hàm mục tiêu, chúng tôi giới thiệu tất cả các biến bổ sung có hệ số bằng 0:
Trong bất đẳng thức đầu tiên có nghĩa (≤), chúng tôi giới thiệu biến cơ bản x 3. Trong bất đẳng thức thứ hai có nghĩa (≤), chúng tôi giới thiệu biến cơ bản x 4. Trong bất đẳng thức thứ ba, chúng tôi giới thiệu biến cơ bản x 5. Ở bất đẳng thức 4 - biến cơ bản x 6. Hãy lấy dạng chuẩn của mô hình:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F (X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → tối đa

Ví dụ số 2. Tìm hai giải pháp hỗ trợ của hệ thống
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2