Hàm mục tiêu ở dạng chính tắc có dạng. Dạng chính tắc của một bài toán quy hoạch tuyến tính

Bất kỳ nhiệm vụ lập trình tuyến tính có thể được rút gọn thành bài toán quy hoạch tuyến tính ở dạng chính tắc. Với mục đích này trong trường hợp chung bạn cần có khả năng quy bài toán cực đại hóa thành bài toán cực tiểu hóa; chuyển từ ràng buộc bất đẳng thức sang ràng buộc đẳng thức và thay thế các biến không tuân theo điều kiện không âm. Tối đa hóa một hàm nhất định tương đương với việc giảm thiểu hàm tương tự được lấy với dấu ngược lại và ngược lại.

Quy tắc đưa một bài toán quy hoạch tuyến tính về dạng chính tắc như sau:

• nếu ở vấn đề ban đầu cần xác định mức tối đa hàm tuyến tính, thì bạn nên đổi dấu và tìm giá trị nhỏ nhất của hàm này;
• nếu có những hạn chế phần bên phải là âm thì giới hạn này phải được nhân với -1;
• nếu có sự bất bình đẳng giữa các hạn chế, thì bằng cách đưa vào các biến không âm bổ sung, chúng sẽ được chuyển thành các đẳng thức;
• nếu một số biến xj không có hạn chế về dấu thì nó được thay thế (trong hàm mục tiêu và trong tất cả các hạn chế) bằng hiệu 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. Rút gọn bài toán quy hoạch tuyến tính về dạng chính tắc:

phút L = 2x 1 + x 2 - x 3 ;
2x2 - x3 5;
x 1 + x 2 - x 3 ≥ -1;
2x1 - x2 ≤ -3;
x 1 0; x 2 ≥ 0; x 3 ≥ 0.

Hãy đưa các biến san bằng vào từng phương trình của hệ ràng buộc x 4 , x 5 , x 6. Hệ sẽ được viết dưới dạng đẳng thức, còn phương trình thứ nhất và thứ ba của hệ ràng buộc các biến x 4 , x 6được nhập vào bên trái với dấu "+" và trong phương trình thứ hai, biến x 5được nhập bằng dấu "-".

2x2 - 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 dương; để làm điều này, nhân hai phương trình cuối với -1:

2x2 - 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 việc viết các bài toán quy hoạch tuyến tính, tất cả các biến có trong hệ thống ràng buộc phải âm. Hãy giả sử 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ệ ràng buộc và hàm mục tiêu rồi viết các biến theo thứ tự chỉ số tăng dần, chúng ta thu được bài toán quy hoạch 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 ;
2x2 - 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 vấn đề kinh điển LP. Phương pháp đơn giản và sự hội tụ của nó.

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

Ý tưởng của phương pháp đơn giản cải tiến nhất quán kế hoạch,đó là, bắt đầu từ một giải pháp tham chiếu ban đầu nào đó, chuyển động có hướng tuần tự từ lời giải tham khảo của bài toán đến lời giải tối ưu.

Giá trị của hàm mục tiêu không giảm trong quá trình di chuyển các bài toán đến mức tối đa.

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

Nghiệm tham chiếu là nghiệm cơ bản không âm.

Thuật toán phương pháp đơn giản

1. Mô hình toán học nhiệm vụ nên được kinh điển. Nếu nó không chính tắc thì nó phải được đưa về dạng kinh điển.

2. Tìm giải pháp tham chiếu ban đầu và kiểm tra tính tối ưu của nó.
Để làm điều này, hãy điền vào bảng đơn 1.
Chúng ta điền vào tất cả các hàng của bảng bước 1 theo dữ liệu của hệ hạn chế và hàm mục tiêu.

Khả thi trường hợp sau khi giải quyết các vấn đề trên tối đa:

1. Nếu mọi hệ số dòng cuối cùng bảng đơn giản Dj³ 0, sau đó tìm thấy

giải pháp tối ưu.

2 Nếu có ít nhất một hệ số DJ £ 0, nhưng đối với biến tương ứng không có một mối quan hệ đánh giá tích cực duy nhất, thì nghiệm 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 âm và đối với biến tương ứng thì có ít nhất một thái độ đánh giá tích cực thì bạn cần phải chuyển sang sang giải pháp tham khảo khác.

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

5. Nếu có ít nhất một hệ số Dk< 0 ,Cái đó k - thứ cột chấp nhận cho người dẫn chương trình.

6. Đối với đường dẫn đầu chúng tôi chấp nhận cái tương ứng tối thiểu tỷ lệ thành viên miễn phí biđến hệ số dương dẫn đầu, k – cái đó cột.

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

Điền vào bảng đơn 2 :

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

· viết lại dòng đầu bằng cách chia nó cho phần tử đầ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 tiếp theo

· chúng ta tìm các hệ số còn lại bằng quy tắc “hình chữ nhật”

Chúng tôi thu được một giải pháp tham chiếu mới mà chúng tôi kiểm tra cho sự tối ưu:

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

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

Nếu hàm mục tiêu F(X)đòi hỏi phải tìm giá trị tối thiểu, thì tiêu chí sự tối ưu của vấn đề là hệ số không dương D j với mọi j = 1,2,...n.

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

Dễ dàng nhận thấy các vấn đề về sự hội tụ của phương pháp đơn hình có thể nảy sinh ở khâu chọn giá trị r (phần 2”) trong trường hợp giống nhau. giá trị tối thiểu mối quan hệ

sẽ đạt được đồng thời cho nhiều hàng của bảng T (q). Sau đó, ở lần lặp tiếp theo, cột 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) hệ thống các ràng buộc đồng nhất ở dạng hệ phương trình; 2) các điều kiện không âm đồng nhất áp dụng cho tất cả các biến liên quan đến bài toán và 3) cực đại hóa 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 được đặc trưng bởi ba đặc điểm sau: 1) hệ thống các ràng buộc đồng nhất ở dạng hệ phương trình; 2) các điều kiện không âm đồng nhất áp dụng cho tất cả các biến liên quan đến bài toán và 3) cực đại hóa 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 quy hoạch tuyến tính thuận tiện ở chỗ dễ dàng tìm được đỉnh ban đầu của vùng khả thi.

Chúng ta hãy xem xét dạng chính tắc của bài toán quy hoạch tuyến tính và phương pháp loại bỏ Jordan-Gauss.

Dạng chính tắc của một bài toán quy hoạch tuyến tính thường thuận tiện.

Khi chuyển đổi một hệ thống các ràng buộc sang dạng chính tắc của một bài toán quy hoạch 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. Để làm điều này, các biến không âm bổ sung được đưa vào.

Chứng minh rằng các ma trận thực giao hoán 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 phép biến đổi tương tự sử dụng ma trận trực giao.

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

Dạng chính tắc của bài toán có đặc điểm là tính đồng nhất của hệ ràng buộc dưới dạng hệ phương trình; tối đa hóa hàm mục tiêu; điều kiện không âm của tất cả các biến liên quan đến bài toán.

Không có Tính năng bổ sung dạng chính tắc của các bài toán không bổ sung vào sơ đồ tính toán đang được xem xét.

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

Thuật toán đơn giản-mete có thể được chia thành hai giai đoạn. Ở giai đoạn đầu tiên, một giải pháp cơ bản được tìm ra bằng cách loại bỏ các biến số. 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 để chuyển sang giai đoạn thứ hai. Bước thứ hai là kiểm tra xem có tối ưu bị chặn hay không. Nếu tồn tại thì xác định các giải pháp cơ bản có thể chấp nhận được và từ đó lựa chọn giải pháp tối ưu.

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

Đoạn đầu tiên của phần giới thiệu cho thấy làm thế nào một bài toán quy hoạch 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. Đối với các bài toán kinh điển, việc mô tả phương pháp cải tiến tuần tự được đơn giản hóa về mặt hình thức, vì không cần phải xem xét hai phương án vi phạm điều kiện tối ưu và hai phương án để đạt đến đỉnh tiếp theo. Tuy nhiên, điều này làm tăng kích thước ma trận cơ sở A [ /, J ], chủ yếu xác định độ phức tạp của một sha. 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 lại tỏ ra thích hợp 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 cho các bài toán quy hoạch tuyến tính cụ thể.

Trang:      1

Bài toán quy hoạch tuyến tính có dạng ax = b trong đó a là ma trận hệ số, b là vectơ ràng buộc.
Ví dụ:

Trong mỗi bài toán LP, giá trị của biến được tìm với điều kiện:

• những giá trị này thỏa mãn một số hệ thống Các phương trình tuyến tính hoặc sự bất bình đẳng;
• tại các giá trị này, hàm mục tiêu sẽ chuyển sang mức tối thiểu hoặc tối đa.

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

Một trong phương pháp phổ quát LP là phương pháp đơn giản, tuy nhiên, có thể được sử dụng nếu bài toán LP có dạng chính tắc.

Sự định nghĩa. Bài toán LP có dạng chính tắc nếu tất cả các ràng buộc của hệ thống chỉ bao gồm các phương trình (ngoại trừ các bất đẳng thức biểu thị tính không âm của các biến) và hàm mục tiêu phải được cực tiểu hóa.
Một ví dụ về bài toán LP như vậy ở dạng chính tắc là Bài toán 1 – bài toán vận chuyển cân bằng với hệ các ràng buộc (1) và hàm mục tiêu (2).
Tuy nhiên, trong hầu hết nhiệm vụ kinh tế Thông thường, hệ thống ràng buộc ban đầu không chỉ bao gồm các phương trình mà còn bao gồm các bất đẳng thức.

Tuyên bố. Bất kỳ bài toán LP tổng quát nào cũng có thể được quy về dạng chính tắc.
Đưa nhiệm vụ chung LP sang dạng chuẩn đạt được bằng cách đưa vào các biến mới (chúng được gọi là các biến bổ sung).
Hệ ràng buộc (3) của bài toán này gồm 4 bất đẳng thức. Bằng cách giới thiệu các biến bổ sung y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, ta có thể đi đến hệ điều kiện:

Các biến bổ sung này y tôi có một ý nghĩa kinh tế hoàn toàn rõ ràng, cụ thể là, chúng có nghĩa là lượng thời gian làm việc không được sử dụng (thời gian ngừng hoạt động của máy Tôi-loại thứ).
Ví dụ: nếu máy thuộc loại thứ nhất làm việc suốt 18 giờ thì x + y = 18, do đó y 1 = 0. Nhưng chúng tôi cho phép khả năng sử dụng không đầy đủ thời gian hoạt động của máy thứ nhất x + y<18. В этом случае y 1 mang giá trị dương và có thể được coi là giới hạn thời gian chưa sử dụng. Ví dụ: biết giải pháp cho vấn đề này từ đoạn 3.3.2, x = 12, y= 6, từ hệ hạn chế (3.9) ta có thể kết luận rằng y 1 = y 2 = y 3 = 0, và y 4 = 12 – 6 = 6. Tức là các máy loại một, loại hai, loại ba sử dụng hoàn toàn thời gian làm việc. Nhưng máy thứ tư chỉ hoạt động được một nửa, trong 6 giờ và ở trạng thái không hoạt động, theo phương án tối ưu. Có lẽ, sau những kết luận như vậy, người đứng đầu doanh nghiệp sẽ muốn gánh công việc khác, cho thuê lại thời gian này, v.v.
Vì vậy, bằng cách đưa vào các biến bổ sung, chúng ta có thể giảm bất kỳ ràng buộc loại bất đẳng thức nào đối với một phương trình.

Hãy xem xét vấn đề hỗn hợp. Hệ điều kiện hạn chế có dạng:
Các bất đẳng thức hướng về phía “nhiều hơn”, do đó khi đưa thêm các biến y 1, y 2, y 3 ≥ 0 thì phải trừ vế trái để cân bằng với vế phải. Chúng tôi thu được một hệ thống hạn chế ở dạng chính tắc:
Các biến y i cũng sẽ có ý nghĩa kinh tế. Nếu nhớ lại nội dung thực tế của bài toán thì biến y 1 sẽ là lượng chất dư A có trong hỗn hợp, y 2 là lượng chất dư TRONG trong hỗn hợp y 3 – thặng dư VỚI trong hỗn hợp.
Nhiệm vụ tìm giá trị lớn nhất của hàm mục tiêu có thể được rút gọn thành việc tìm giá trị nhỏ nhất của hàm - F do tính hiển nhiên của phát biểu max F = –min (- F). Nhìn vào bức tranh: nếu tại một thời điểm nào đó x= x 0 chức năng y= F(x) đạt cực đại thì hàm số y= –F(x), đối xứng với nó so với trục CON BÒ ĐỰC, tại cùng một điểm x 0 sẽ đạt mức tối thiểu và F tối đa = – (– F phút) tại x = x 0 .

Phần kết luận.Để biểu diễn bài toán LP ở dạng chính tắc cần thiết:

• chuyển các bất đẳng thức có trong hệ ràng buộc của bài toán thành phương trình bằng cách đưa thêm các biến;
• nếu hàm mục tiêu F→max (tối đa hóa), nó được thay thế bằng hàm – F→ phút (được giảm thiểu).

Mục đích của dịch vụ. Công cụ tính toán trực tuyến được thiết kế để chuyển đổi PPP sang KZLP. Đưa 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 đẳng thức bằng cách đưa vào các biến bổ sung.
Nếu một ràng buộc không được áp đặt lên 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ố lượng hàng (số lượng ràng buộc). Giải pháp thu được được lưu trong tệp Word.

Mô hình toán học của ZLP được gọi là nền tảng, 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ệ ràng buộc của nó được biểu diễn dưới dạng hệ gồm m phương trình độc lập tuyến tính (thứ hạng hệ r=m) thì hệ đó được phân bổ 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, vế phải của phương trình không âm (b i ≥ 0).

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

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

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

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

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

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

Ví dụ số 1. Chuyển bài toán LP sau về dạng chính tắc: F(X) = 5x 1 + 3x 2 → max theo giới hạn:
2x1 + 3x2 20
3x1 + x2 15
4x1 16
3x2 12
Mô hình được viết ở dạng chuẩn. Hãy để 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 vế trái của ràng buộc bất đẳng thức. Chúng tôi đưa tất cả các biến bổ sung vào hàm mục tiêu với các hệ số bằng 0:
Trong bất đẳng thức thứ nhất về ý nghĩa (≤), ta đưa vào biến cơ bản x 3 . Trong bất đẳng thức ý nghĩa thứ 2 (≤) ta đưa vào 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 . Trong bất đẳng thức thứ 4 - biến cơ bản x 6. Chúng ta thu được dạng chính tắc 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 tham chiếu của hệ thống
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2