Phương pháp đơn hình để giải LLP. Ý tưởng chung của phương pháp đơn giản. Phương pháp đơn giản giải bài toán quy hoạch tuyến tính

GIỚI THIỆU

Chủ đề công việc của tôi liên quan đến việc giải quyết các vấn đề phát sinh trong kinh tế. Điều này đặt ra câu hỏi về việc lựa chọn giải pháp tốt nhất, theo một nghĩa nào đó. Và để tìm kiếm tùy chọn có thể Thường bị ảnh hưởng bởi nhiều yếu tố khác nhau làm thu hẹp phạm vi lựa chọn. Nói cách khác, cần phải giải quyết vấn đề tối ưu hóa, trong đó cần phải chọn sự lựa chọn tốt nhất quyết định trong số một tập hợp nhất định, thường có giới hạn các lựa chọn khả thi.

Bài toán tối ưu có thể được biểu diễn bằng ngôn ngữ toán học nếu tập hợp Tùy chọn có sẵn có thể được mô tả bằng các mối quan hệ toán học (bình đẳng, bất đẳng thức, phương trình) và mỗi giải pháp có thể được đánh giá định lượng bằng cách sử dụng một số chỉ số gọi là tiêu chí tối ưu hoặc hàm mục tiêu. Sau đó giải pháp tốt nhất sẽ là người mang lại hàm mục tiêu giá trị lớn nhất hoặc nhỏ nhất tùy theo ý nghĩa của bài toán. Ví dụ, khi đầu tư một lượng vốn hạn chế vào một số dự án, nhiệm vụ đương nhiên là chọn những dự án có thể mang lại lợi nhuận lớn nhất trong tương lai. Khi giao sản phẩm từ nhiều nhà cung cấp khác nhau đến cửa hàng, nhiệm vụ giảm thiểu chi phí vận chuyển phát sinh.

Quá trình hình thức hóa một bài toán được gọi là xây dựng mô hình toán học của nó. Nó bao gồm ba giai đoạn.

1. Lựa chọn các tham số của bài toán mà lời giải phụ thuộc vào. Các tham số này được gọi là biến điều khiển và được biểu thị bằng cách tạo thành một vectơ từ chúng . Đưa ra quyết định có nghĩa là thiết lập các giá trị cụ thể cho các biến.

2. Xây dựng tiêu chí bằng số để có thể so sánh Các tùy chọn khác nhau các quyết định. Tiêu chí như vậy thường được gọi là hàm mục tiêu và được ký hiệu là .

3. Mô tả trọn bộ X giá trị cho phép của các biến - hạn chế liên quan đến sự hiện diện nguồn nguyên liệu nguồn lực tài chính, năng lực công nghệ, v.v.

Bài toán tối ưu hóa là tìm ra lời giải khả thi như vậy , mang lại cho hàm mục tiêu giá trị lớn nhất hoặc nhỏ nhất trong số tất cả các nghiệm có thể.

1. Phương pháp hình học giải bài toán LP

Phương pháp này thường được sử dụng để giải các bài toán chỉ có hai đại lượng chưa biết. Hãy xem xét nó bằng các ví dụ sau:

Ví dụ 1.1. (Vấn đề về sản xuất sơn).

Một nhà máy nhỏ sản xuất hai loại sơn: INT- Vì công việc nội thất Và EXT- cho công việc ngoài trời. Trong sản xuất sơn người ta sử dụng hai sản phẩm ban đầu MỘT Và TRONG. Do diện tích kho nhỏ nên lượng dự trữ tối đa hàng ngày của các sản phẩm này lần lượt là 6 tấn và 8 tấn. Để sản xuất được 1 tấn sơn INT tiêu thụ hết 1 tấn sản phẩm MỘT và 2 tấn sản phẩm TRONG và để sản xuất 1 tấn sơn EXT có 2 tấn sản phẩm MỘT và 1 tấn sản phẩm TRONG. Nhà máy bán sơn với giá 3 nghìn. đô la mỗi tấn sơn INT và 2 nghìn đô la một tấn sơn EXT. Thật thuận tiện để tóm tắt dữ liệu ban đầu trong một bảng:

Nghiên cứu thị trường tiêu thụ cho thấy nhu cầu sơn hàng ngày EXT không bao giờ vượt quá nhu cầu về sơn INT, hơn 1 tấn. Nhà máy nên sản xuất bao nhiêu loại sơn mỗi ngày để tối đa hóa thu nhập từ việc bán sản phẩm?

Nào cùng xây mô hình toán học nhiệm vụ. Để làm được điều này cần xác định các biến bài toán, hàm mục tiêu và các ràng buộc mà các biến đó thỏa mãn. Hãy ký hiệu bằng x 1- khối lượng sản xuất sơn INT hàng ngày theo kế hoạch và sau đó x 2- khối lượng sản xuất sơn EXT hàng ngày. Hàm mục tiêu f(x) sẽ thể hiện thu nhập hàng ngày từ việc bán sơn bằng 3x1 + 2x2(nghìn đô la). Thu nhập này phải được tối đa hóa

f( x)= 3 x 1 + 2 x 2 ® tối đa.

Chúng ta hãy xây dựng các ràng buộc của bài toán liên quan đến nguồn cung sản phẩm hạn chế MỘT Và TRONG. Dùng cho sản xuất sơn INT về số lượng x 1(t) sẽ được sử dụng 1x1(t) của sản phẩm MỘT và sản xuất sơn EXT về khối lượng x 2(t) sẽ được chi tiêu 2x2(t) của sản phẩm MỘT. Vì việc cung cấp sản phẩm hàng ngày MỘT là 6 tấn thì lượng tiêu thụ sản phẩm MỘTđể sản xuất hai loại sơn không được vượt quá số lượng này mỗi ngày: 1x1 + 2x2 £6. Tương tự, chúng ta thu được ràng buộc liên quan đến tồn kho sản phẩm TRONG : 2x1 +1x2 £8. Sự ràng buộc về tỷ lệ nhu cầu về sơn có thể được mô tả bằng sự bất bình đẳng: x 2 - x 1 £1. Xét đến các điều kiện tự nhiên để khối lượng sản xuất không âm, cuối cùng chúng ta thu được bài toán sau lập trình tuyến tính

f(x) = 3 x 1 + 2 x 2 ® tối đa (1.1)

1 x 1 + 2 x 2 £ 6 , (1.2)

2x1 + 1x2 £ 8 , (1.3)

- x 1 + x 2 £1 , (1.4)

x 1 ³ 0, x 2 ³ 0 . (1.5)

Chúng ta hãy xây dựng một tập hợp các phương án bài toán được mô tả bằng các ràng buộc (1.2)-(1.5). Hãy xem xét bất đẳng thức đầu tiên. Nó chỉ định một nửa mặt phẳng nhất định nằm ở một phía của đường ranh giới

trang 1 : 1x1 +2x2 =6

Hãy dựng đường thẳng này trên mặt phẳng có trục tọa độ x 1 Và x 2. Để vẽ một đường thẳng, chỉ cần biết hai điểm của nó là đủ. Cách dễ nhất là tìm giao điểm của một đường thẳng với các trục tọa độ. tin tưởng x 1 = 0, từ phương trình đường thẳng ta thu được x 2 = 3, và khi x 2 = 0 chúng ta sẽ tìm thấy x 1 = 6. Như vậy thẳng trang 1 sẽ đi qua các điểm (0,3) Và ( 6,0) . Để xác định nửa mặt phẳng mong muốn nằm ở phía nào của đường thẳng, chỉ cần thay tọa độ của bất kỳ điểm nào trên mặt phẳng vào bất đẳng thức (1.2) là đủ. Nếu đường thẳng không đi qua gốc tọa độ thì lấy điểm là thuận lợi nhất (0, 0) . Rõ ràng tại điểm này bất đẳng thức (1.2) được thỏa mãn nghiêm ngặt (1* 0 + 2* 0 < 6) , có nghĩa là nửa mặt phẳng xác định bởi bất đẳng thức này nằm bên dưới đường thẳng p1, kể cả nguồn gốc. Chúng tôi đánh dấu nửa mặt phẳng mong muốn bằng bóng ( Hình.1.1).

Tương tự, ta dựng nửa mặt phẳng xác định bởi bất đẳng thức (1.3) . Để làm điều này, hãy vẽ một đường ranh giới trên mặt phẳng tọa độ

p2 : 2x1 +x2 =8 ,

tìm giao điểm của nó với trục tọa độ: (0,8) Và (4,0) .

Tọa độ điểm thay thế (0,0) vào bất đẳng thức (2.3), ta thấy gốc tọa độ nằm trong nửa mặt phẳng mong muốn (2* 0 + 1* 0 < 8) , nghĩa là mọi điểm thỏa mãn bất đẳng thức (2.3) đều nằm bên trái đường thẳng p2. Hãy đánh dấu khu vực này bằng bóng ( Hình.1.1).

Các điểm được xác định bởi ràng buộc ( 4 ), nằm dưới đường thẳng

trang 3 : -x 1 +x 2 =1,

đi qua các điểm (0, 1) Và (-1, 0) .

Cuối cùng, điều kiện không âm: x 1 ³ 0, x 2³0 đặt tất cả các điểm của quý đầu tiên mà chúng tôi cũng đánh dấu bằng tô bóng.

Bây giờ, chọn các điểm của mặt phẳng thỏa mãn mọi ràng buộc của bài toán (1.1)-(1.5), nghĩa là nằm đồng thời trên tất cả các nửa mặt phẳng được tô bóng, chúng ta thu được một tập hợp các mặt phẳng X. Nó là một đa giác (trong bài toán này là một hình ngũ giác). Các cạnh của nó nằm trên những đường thẳng và phương trình của nó thu được từ hệ thống gốc bất đẳng thức (1.2)-(1.5) bằng cách thay dấu bất đẳng thức bằng đẳng thức chặt chẽ.

Vì biểu diễn đồ họa của hàm mục tiêu, chúng tôi giới thiệu khái niệm đường mức (hàm isoline).

Sự định nghĩa.Đường mức chức năng (isoline) f(x)được gọi là tập hợp điểm x = (x 1, x2), trong đó nó nhận cùng một giá trị không đổi f(x) = h, Ở đâu h- một số nào đó. Vì hàm tuyến tính hai biến f(x) = c 1 x 1 + c 2 x 2 vạch mức tương ứng với số h, sẽ biểu diễn một đường thẳng với phương trình

c 1 x 1 + c 2 x 2 = h (1.6)

Khi số thay đổi h chúng ta sẽ thu được một họ các đường đồng mức (các đường thẳng song song) có cùng vectơ chỉ phương c = =(c 1 , c 2), vuông góc với mọi đường thẳng. Được biết, vectơ c = (c 1 , c 2) cho hàm tuyến tính f(x) = c 1 x 1 +c 2 x 2 cho biết hướng tăng của nó. Về mặt hình học, điều này có nghĩa là khi chuyển động song song của đường thẳng (1.6) theo hướng của vectơ đích c giá trị của hàm mục tiêu tăng lên.

Hãy xây dựng các đường mức của hàm mục tiêu f(x) = 3x 1 + 2 x 2 trong nhiệm vụ của chúng tôi. Phương trình của chúng sẽ giống như 3x1 + 2x2 = h. Chúng xác định một họ các đường thẳng song song tùy thuộc vào tham số h. Tất cả các đường thẳng đều vuông góc với vectơ mục tiêu c = (3, 2), bao gồm các hệ số của hàm mục tiêu, do đó, để xây dựng một họ các đường cùng mức của hàm mục tiêu, chỉ cần xây dựng vectơ mục tiêu của nó và vẽ một số đường thẳng vuông góc với vectơ này là đủ. Chúng ta sẽ vẽ các đường mức trên nhiều phương án X, hãy nhớ rằng khi di chuyển các đường thẳng song song theo hướng của vectơ mục tiêu c = (3, 2) giá trị hàm f(x)= 3x 1 + 2x 2 sẽ tăng. Vì trong bài toán, phương án tối ưu phải mang lại giá trị lớn nhất có thể cho hàm mục tiêu, nên để giải bài toán bằng đồ thị cần phải có tất cả các điểm. x = (x 1, x2) nhiều kế hoạch X tìm một điểm như vậy x* = (x 1 * , x 2 *), qua đó đường mức cuối cùng sẽ đi theo hướng của vectơ mục tiêu c = (3,2). Từ Hình 1.2, rõ ràng điểm cần tìm sẽ là điểm nằm trên cùng của tập hợp X, được hình thành bởi giao điểm của các đường trang 1 Và p2. Giải hệ phương trình mô tả các đường thẳng ta tìm được phương án tối ưu x 1 * = 3 1/3, x 2 * = 1 1/3. Trong trường hợp này, giá trị cực đại của hàm mục tiêu sẽ bằng f(x*) = 12 2 / 3 . Vì vậy, hàng ngày nhà máy phải sản xuất 3 1 / 3 tấn sơn INT Và 1 1 / 3 tấn sơn EXT khi nhận được thu nhập 12 2 / 3 nghìn đô la.

x 1 + 2 x 2 = 6,

2 x 1 + x 2 = 8,

Ví dụ 1.2. Doanh nghiệp y tế mua hai loại phức hợp vitamin tổng hợp “Sức khỏe” và “Tuổi thọ” chứa ba loại vitamin. Số lượng đơn vị của các loại vitamin này trong một gam phức hợp đa phức, định mức cần thiết của chúng để sử dụng phòng ngừa và giá thành của một gam phức hợp “Sức khỏe” và “Tuổi thọ” được phản ánh trong bảng

Cần bao nhiêu gam phức hợp vitamin tổng hợp của mỗi loại cho một liều phòng ngừa để nhận được tất cả các vitamin ít nhất theo yêu cầu, đồng thời tổng chi phí của chúng là tối thiểu.

Hãy tạo một mô hình toán học của vấn đề. Để làm điều này, chúng tôi giới thiệu các biến: x 1– số lượng phức hợp “Sức khỏe” (gr.) , x 2– số lượng phức hợp “Tuổi thọ” (gr.) cần thiết cho việc sử dụng dự phòng. Hàm mục tiêu biểu thị tổng chi phí của phức hợp vitamin, nên càng thấp càng tốt

f( x)= 5 x 1 + 4 x 2 ® phút (1.7)

Các hạn chế mô tả việc tuân thủ các tiêu chuẩn về vitamin như sau:

Bằng vitamin V 1 : 3x1 + x2 ³ 9 , (1.8)

Bằng vitamin V 2 : x 1 + 2x 2 ³ 8, (1.9)

Bằng vitamin V 3 : x 1 + 6x 2 ³ 12 . (1.10)

Trong trường hợp này, các biến phải không âm: x j ³ 0, j = 1, 2.

Hãy bắt đầu lại giải pháp bằng cách xây dựng nhiều phương án X, trong đó chúng ta vẽ các đường thẳng biên, các phương trình của chúng thu được bằng cách thay thế các dấu bất đẳng thức trong các giới hạn bằng các đẳng thức

trang 1 : 3 x 1 + x 2 = 9,

p2 : x 1 + 2 x 2 = 8,

trang 3 : x 1 + 6 x 2 = 12.

Tọa độ điểm thay thế (0,0) trong bất đẳng thức (1.8)-(1.10) ta thấy gốc tọa độ không thỏa mãn chúng nên không nằm trong tập phương án X. Vì vậy, các cửa sập được hướng lên phía trên và bên phải của đường ranh giới. Bằng cách xác định các điểm thỏa mãn mọi bất đẳng thức và điều kiện không âm, chúng ta thu được tập hợp các kế hoạch như trong Hình 2. 1.2. TRONG trong ví dụ này nó không bị giới hạn.

Chúng ta hãy mô tả hàm mục tiêu (1.7) bằng cách sử dụng các đường mức. Để làm được điều này, chỉ cần xây dựng vectơ mục tiêu là đủ c = (5, 4) và vẽ một số đường thẳng vuông góc với nó trên tập hợp X. Vì vectơ mục tiêu chỉ ra hướng tăng của hàm mục tiêu và trong bài toán ăn kiêng cần phải tìm giá trị cực tiểu của nó, sau đó tìm giải pháp tối ưu chúng ta sẽ di chuyển đường mức song song với chính nó dọc theo tập hợp X theo hướng ngược lại với vectơ mục tiêu.

Điểm cuối cùng của tập hợp quy hoạch mà đường đồng mức vẫn đi qua sẽ là giao điểm của các đường trang 1 Và p2. Giải hệ uranium (Hình 1.3).

3 x 1 + x 2 = 9

x 1 + 2 x 2 = 8

chúng tôi có được kế hoạch tối ưu x 1 * = 2, x 2 * = 3. Giá trị tối thiểu của hàm mục tiêu sẽ bằng

f(x*) = 5∙2 + 4∙3 = 22.

Vì vậy, bộ dụng cụ dự phòng rẻ nhất bao gồm 2 g. phức hợp A và 3 g. tổ hợp TRONG, và giá của nó là 22 chà xát.

Bây giờ thật dễ dàng để xây dựng một giải pháp hình học nhiệm vụ tiêu chuẩn LP với hai biến:

· một đa giác chấp nhận được được mô tả - giao điểm của các nửa mặt phẳng là nghiệm của các bất đẳng thức tương ứng;

· vectơ mục tiêu được mô tả;

· Đường vuông góc với vectơ mục tiêu được vẽ thông qua tập hợp chấp nhận được - đây là đường mức của hàm mục tiêu;

· bằng cách di chuyển đường mức song song với chính nó theo hướng của vectơ mục tiêu cho đến khi nó nằm về một phía của đường thẳng di chuyển, điểm (hoặc các điểm) cực đại được xác định bằng trực quan;

· Tính tọa độ của điểm cực đại (bằng cách giải hệ phương trình tương ứng xác định đường thẳng, giao điểm của nó là điểm mong muốn) và giá trị cực đại của hàm mục tiêu.

Bình luận.Để xác định điểm tối thiểu, hãy di chuyển đường cô lập ngược hướng của vectơ mục tiêu.

Trong các ví dụ được phân tích, phương án tối ưu nằm ở đỉnh duy nhất của đa giác của các phương án khả thi. Tuy nhiên, khi giải bài toán LP, các trường hợp khác cũng có thể phát sinh.

Vô số phương án tối ưu. TRÊN Hình.1.4 hàm mục tiêu có cùng giá trị lớn nhất tại bất kỳ điểm nào trên đoạn AB nối hai đỉnh của một tập hợp các mặt bằng X. Tình huống này xảy ra nếu các đường mức song song với đường biên.

Không có giải pháp hạn chế. TRÊN Hình.1.5 Trường hợp được mô tả khi hàm mục tiêu không bị giới hạn ở trên trong tập kế hoạch và không tồn tại nghiệm của bài toán cực đại. Trong trường hợp này, có thể tồn tại một giải pháp cho vấn đề tối thiểu (như trong vấn đề vitamin).

Thiếu các kế hoạch hợp lệ. TRÊN Hình.1.6 Các khu vực được phép theo từng hạn chế không có điểm chung. Trong trường hợp này, họ nói rằng các ràng buộc không nhất quán, tập kế hoạch trống và bài toán LP không có lời giải.

Cơm. 1.4 Hình. 1.5 Hình. 1.6

2. Phương pháp đơn giản

2.1 Ý tưởng của phương pháp đơn hình

Hãy xem xét một phương pháp phổ quát để giải bài toán quy hoạch tuyến tính chuẩn

, , ,

Với N biến và tôi các ràng buộc đẳng thức, được gọi là phương pháp đơn hình.

Tập các mặt phẳng của một bài toán chính tắc là một tập đa diện lồi với số hữu hạn các điểm góc. Và nếu bài toán này có lời giải tối ưu thì nó đạt được ít nhất ở một điểm góc.

Bất kỳ điểm góc nào cũng được liên kết với một mặt phẳng cơ bản của bài toán, trong đó các biến bằng 0 và các biến còn lại tương ứng với các cột độc lập tuyến tính của ma trận điều kiện. Các cột độc lập tuyến tính này tạo thành một ma trận cơ sở không đơn lẻ.

Việc lặp lại tất cả các điểm góc tốn kém về mặt tính toán và do đó không hiệu quả. Năm 1947, J. Danzig đề xuất một quy trình có trật tự để liệt kê các điểm góc, trong đó chỉ cần kiểm tra một phần nhỏ trong số đó là đủ để tìm ra giải pháp tối ưu. Thủ tục này được gọi là phương pháp đơn giản .

J. Danzig đề xuất chỉ thay thế một vectơ trong ma trận cơ sở khi chuyển từ điểm cực trị này sang điểm cực trị khác. Điều này có nghĩa là trong quá trình chuyển đổi như vậy, chúng ta phải loại trừ một trong các biến cơ bản - làm cho nó không cơ bản ( bằng 0) và thay vào đó là một biến mới trong số các biến không cơ bản (không) - biến nó thành cơ bản (dương).

Nó chỉ ra rằng về mặt hình học, sự thay thế như vậy dẫn đến sự chuyển đổi từ điểm góc này sang điểm liền kề, được kết nối với điểm trước đó bằng một cạnh chung.

Trong số tất cả các điểm lân cận, điểm mà hàm mục tiêu tăng nhiều nhất sẽ được chọn. Vì số lượng điểm góc là hữu hạn nên qua một số hữu hạn bước chuyển tiếp, đỉnh có giá trị cao nhất hàm mục tiêu, hoặc tính không giới hạn của hàm mục tiêu sẽ được thiết lập trên một tập kế hoạch không giới hạn.

Sơ đồ chung của phương pháp đơn hình bao gồm các bước chính sau.

· bước 0. Xác định cơ sở ban đầu và điểm góc ban đầu tương ứng (đường cơ sở).

· bước 1. Kiểm tra đường cơ sở hiện tại để tối ưu . Nếu tiêu chí tối ưu được đáp ứng thì phương án là tối ưu và giải pháp là hoàn chỉnh. Nếu không thì chuyển sang bước 2.

· bước 2. Tìm biến được đưa vào biến cơ bản. (Từ điều kiện tăng hàm mục tiêu).

· bước 3. Tìm một biến bị loại trừ khỏi các biến cơ bản (Từ điều kiện bảo toàn các ràng buộc của bài toán).

· bước chân 4 . Tìm tọa độ của đường cơ sở mới (điểm góc liền kề). Đi tới bước 1.

Các bước lặp lại từ 1–4 tạo thành một lần lặp của phương pháp đơn hình.

Từ sơ đồ này, trước tiên, để bắt đầu phương pháp đơn hình, bạn cần phải có một số loại điểm góc - một sơ đồ cơ bản ban đầu, và thứ hai, bạn cần có khả năng kiểm tra điểm góc hiện tại để tìm mức tối ưu mà không cần tính toán tất cả các điểm liền kề đỉnh. Những vấn đề này có thể giải quyết dễ dàng nếu bài toán LP chuẩn có dạng đặc biệt nào đó.

Sự định nghĩa. Chúng ta sẽ nói rằng bài toán LP chuẩn có “dạng ưa thích” nếu

1. vế phải của các phương trình , .

2. ma trận điều kiện chứa ma trận con đơn vị có kích thước

.

Nói cách khác, trong bất kỳ phương trình nào cũng có một biến có hệ số bằng một, bị thiếu trong các phương trình khác. Điều kiện đầu tiên không nặng nề, vì trong trường hợp vế phải âm của một phương trình nào đó, chỉ cần nhân nó với (–1). Trong bài toán loại ưu tiên, việc tìm đường cơ sở ban đầu rất đơn giản.

Ví dụ 2.1.

Ma trận điều kiện MỘT và vectơ vế phải của các ràng buộc b trông giống như

, ,

và vectơ mục tiêu c = (1, -3, 0, 4, 2).

Một ma trận cơ sở là rõ ràng ngay lập tức: với vectơ đơn vị của điều kiện.

Vì vậy, việc chọn làm biến cơ bản x 1 , x 3 ,x 5 và đưa vào hệ phương trình x 2 = x 4 = 0 (biến không cơ bản) , chúng tôi tìm thấy nó ngay lập tức x 1 = 10,x 3 = 20,x 5 = 8, vậy đường cơ sở ban đầu x 0= (10, 0, 20, 0, 8) Ta thấy giá trị của các biến cơ bản bằng vế phải của ràng buộc. Từ đó rõ ràng là vế phải phải dương b tôi.

Trong tương lai chúng ta sẽ kết hợp các biến cơ bản thành một vector xB.

Như vậy, trong bài toán chính tắc dạng ưu tiên, ma trận con đẳng thức được lấy làm ma trận cơ sở ban đầu A B = E và các biến cơ sở tương ứng bằng vế phải của các ràng buộc:

x B = b .

Đối với kế hoạch cơ bản thuộc loại này, tiêu chí tối ưu có thể được xây dựng đủ đơn giản để kiểm tra. Hãy giới thiệu số lượng

∆j =< с Б, A j >– c j , j = 1,...,n, (2.1)

Ở đâu với B– vectơ hệ số của hàm mục tiêu cho các biến cơ bản x B , Aj – j- cột của ma trận điều kiện, cj – j- hệ số thứ của hàm mục tiêu. Sự khác biệt ∆jđược gọi là sai phân đơn giản hoặc ước lượng đơn giản.

Tiêu chí tối ưu cho phương án cơ bản. Nếu đối với một kế hoạch cơ bản có ma trận cơ sở đơn vị, tất cả các ước lượng đơn đều không âm thì kế hoạch này là tối ưu.

Chúng ta hãy áp dụng tiêu chí này để kiểm tra tính tối ưu của phương án cơ bản x 0= (10, 0, 20, 0, 8) từ ví dụ 2.1.

Vì về vấn đề này, vectơ của các biến cơ bản x B =(x 1 , x 3 ,x 5), Cái đó với B = (c 1 , c 3 ,c 5) = (1, 0, 2).

.

Kể từ đây,

∆ 1 = < с Б, A 1 >- từ 1 =1∙1 + 0∙0 + 2∙0 – 1= 0,

∆ 2 = < с Б, A 2 >– c 2 =1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆ 3 = < с Б, A 3 >– c 3 =1∙0 + 0∙1 + 2∙0 – 0= 0,

∆ 4 = < с Б, A 4 >– c 4 =1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆ 5 = < с Б, A 5 >– từ 5 =1∙0 + 0∙0 + 2∙1 – 2= 0.

Kể từ khi đánh giá ∆ 4 < 0, то базисный план x 0 không tối ưu. Lưu ý rằng các ước lượng đơn tương ứng với các biến cơ bản luôn bằng 0, do đó chỉ cần kiểm tra các ước lượng không cơ bản là đủ.

2.2 Thực hiện phương pháp đơn hình bằng ví dụ

Hãy để chúng tôi chứng minh việc sử dụng phương pháp đơn giản bằng một ví dụ. Hãy xem xét vấn đề kinh điển LP

f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 → tối đa	(2.2)
–x 1 + 2x 2 +x 3 = 4,	(2.3)
3x 1 + 2x 2 +x 4 = 12,	(2.4)
x j ≥ 0, j = 1,2,3,4.	(2.5)

Ma trận điều kiện MỘT = (MỘT 1 , MỘT 2 , MỘT 3 , MỘT 4), ở đâu

Vectơ mục tiêu c =(c 1, c2, c 3, c 4) = (1, 2, 0, 0); vector phần bên phải b =(b 1 , b 2) = (4, 12).

Bước 0. Tìm điểm góc bắt đầu (đường cơ sở).

Bài toán có dạng thích hợp hơn, vì vế phải của phương trình là dương và các cột của ma trận điều kiện MỘT 3, MỘT 4 tạo thành một ma trận con đơn vị. Điều này có nghĩa là ma trận cơ sở ban đầu = (MỘT 3 ,A 4); x 3 và x 4 – biến cơ bản x 1 và x 2 - các biến không cơ bản, c B = (c 3, c 4) = = (0, 0).

Đường cơ sở ban đầu trông giống như x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f( x o)= 0.

Bước 1. Kiểm tra kế hoạch cơ bản để tối ưu.

Hãy tính ước lượng đơn giản cho các biến không cơ bản bằng công thức (5.1)

 1 = < c B, MỘT 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

 2 = < c B, MỘT 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Vì các ước tính là âm nên kế hoạch x – không tối ưu. Chúng ta sẽ tìm một đường cơ sở mới (điểm góc liền kề) với giá trị lớn hơn của hàm mục tiêu.

Bước 2. Tìm biến được đưa vào cơ sở.

Hàm mục tiêu có thể được tăng lên bằng cách đưa một trong các biến không cơ bản vào các biến cơ bản (làm cho nó dương) x 1 hoặc x 2, vì cả hai ước tính j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x 2.

Bước 3.Định nghĩa của một biến xuất phát từ cơ sở.

Sau khi nhập biến vào cơ sở x 2 kế hoạch mới sẽ như thế nào

x" = (0, x 2, x 3 , x 4).

Kế hoạch này không phải là kế hoạch cơ bản, vì nó chỉ chứa một tọa độ 0, có nghĩa là cần phải tạo một trong các biến bằng 0 (loại trừ khỏi cơ sở) x 3 hoặc x 4 . Hãy thay thế tọa độ của kế hoạch x" = (0, x 2, x 3 ,x 4) trong các ràng buộc của vấn đề. Chúng tôi nhận được

2x 2 + x 3 = 4,

2x 2 + x 4 = 12.

Hãy để chúng tôi thể hiện các biến cơ bản từ đây x 3 và x 4 thông qua biến x 2 , được đưa vào cơ sở.

Làm sao nhiều giá trị hơn x 2 , hàm mục tiêu càng tăng. Hãy tìm giá trị lớn nhất của biến cơ sở mới không vi phạm ràng buộc của bài toán, tức là thỏa mãn điều kiện (2.8), (2.9).

Hãy viết lại các bất đẳng thức cuối cùng dưới dạng

2x 2 ≤ 4,

2x 2 ≤ 12,

giá trị tối đa đến từ đâu? x 2 = min ( 4/2, 12/2 ) = 2. Thay giá trị này vào các biểu thức (2.6), (2.7) cho x 3 và x 4, chúng tôi nhận được x 3 = 0. Do đó x 3 xuất phát từ cơ sở .

Bước 4. Xác định tọa độ của đường cơ sở mới.

Đường cơ sở mới (điểm góc liền kề) là:

x" = (0, x 2, 0, x 4)

Cơ sở của điểm này bao gồm các cột MỘT 2 và MỘT 4 , vậy =( MỘT 2, MỘT 4). Cơ sở này không đơn nhất, vì vectơ MỘT 2 = (2,2), và do đó bài toán (2.2)–(2.5) không có dạng ưu tiên đối với cơ sở mới. Ta biến đổi điều kiện của bài toán (2.3), (2.4) sao cho nó có dạng ưu tiên đối với các biến cơ bản mới x 2, x 4, nghĩa là, sao cho biến x 2 được đưa vào phương trình thứ nhất với hệ số bằng 1 và không có trong phương trình thứ hai. Hãy viết lại các phương trình của bài toán

– x 1 + 2 x 2 + x 3 = 4, (P 1)

3x 1 +2 x 2 + x 4 = 12. (P 2)

Hãy chia phương trình đầu tiên cho hệ số tại x 2. Hãy tìm một phương trình mới = p 1/2 tương đương với bản gốc

– 1/2 x 1 + x 2 + 1/2 x 3 = 2. ( )

Chúng tôi sử dụng phương trình này, mà chúng tôi gọi là giải quyết, để loại bỏ biến x 2 từ phương trình thứ hai. Để làm được điều này chúng ta cần phương trình nhân với 2 và trừ từ P 2 . Chúng tôi nhận được = p 2 – 2= p 2 -P 1:

4 x 1 – x 3 + x 4 = 8. ( )

Kết quả là chúng ta thu được một cách biểu diễn “ưu tiên” mới của bài toán ban đầu đối với các biến cơ bản mới. x 2 , x 4:

f (x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4  tối đa

– 1/2 x 1 + x 2 + 1/2 x 3 = 2 ( )

4 x 1 – x 3 + x 4 = 8 ( )

x j 0, j = 1,2,3,4

Thay thế ở đây bằng cách thể hiện đường cơ sở mới x 1 = (0, x 2, 0, x 4), chúng ta sẽ tìm ngay tọa độ của nó, vì giá trị của các biến cơ bản bằng vế phải của phương trình

x" = (0, 2, 0, 8); f (x 1)=4.

Điều này hoàn thành lần lặp đầu tiên phương pháp đơn giản. Tiếp theo, quá trình giải quyết vấn đề tiếp tục từ bước 1, bao gồm việc kiểm tra phương án tìm được ở mức tối ưu. Giải pháp kết thúc khi tất cả các ước tính đơn giản của kế hoạch cơ bản hiện tại hóa ra không âm.

Chúng tôi sẽ không thực hiện lần lặp thứ hai theo sơ đồ của lần lặp đầu tiên, vì sẽ thuận tiện hơn khi thực hiện tất cả các phép tính của phương pháp đơn hình ở dạng bảng.

2.3 Triển khai dạng bảng của một phương pháp đơn giản

Chúng ta sẽ chứng minh cách triển khai dạng bảng bằng cách sử dụng cùng một ví dụ (2.2)–(2.5).

Bước 0. Giải pháp bắt đầu bằng cách xây dựng một bảng đơn giản ban đầu. Điền vào đầu tiên phần bên phải bảng từ cột thứ ba. Tên được viết ở hai dòng trên cùng biến vấn đề (x 1, ...,x 4) và các hệ số của hàm mục tiêu cho các biến này. Dưới đây là các hệ số của phương trình - phần tử của ma trận điều kiện MỘT, do đó dưới biến x 1 là cột định vị MỘT 1, dưới biến x 2 – cột MỘT 2, v.v. Vế phải của các ràng buộc (số) được nhập vào cột bên phải tôi > 0).

Sau đó, chúng ta tìm các cột của ma trận điều kiện tạo thành cơ sở đơn vị - trong ví dụ của chúng ta đây là MỘT 3 và MỘT 4 và các biến cơ bản tương ứng x 3, x 4 được viết ở cột thứ hai. Cuối cùng, ở cột đầu tiên chúng ta viết các hệ số của hàm mục tiêu cho các biến cơ bản.

Bảng 1 - Bảng đơn giản ban đầu

S B	Biến cơ bản	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản ( x B = b)
		x 1	x 2	x 3	x 4
c 3 = 0	x 3	một 11 =-1	một 12 = 2	một 13 = 1	một 14 = 0	b 1 = 4
c 4 = 0	x 4	21 = 3	một 22 = 2	một 23 = 0	một 24 = 1	b 2 =12
Dòng đánh giá j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

Vì bài toán có dạng ưu tiên nên giá trị của các biến cơ bản bằng vế phải của các phương trình nằm ở cột cuối cùng. Vì các biến phi cơ sở bằng 0 nên đường cơ sở ban đầu là

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Bước 1.Để kiểm tra kế hoạch x o để tối ưu, chúng tôi tính toán ước tính đơn giản cho các biến không cơ bản x 1 và x 2 theo công thức

 j =< c Б , A j > – c j .

 1 = < c Б , MỘT 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

Với cách triển khai dạng bảng để tính điểm  1 chúng ta cần tìm tổng tích của các phần tử ở cột đầu tiên ( c B)đến các phần tử cột tương ứng MỘT 1 cho biến không cơ bản x 1 . Điểm được tính tương tự  2 , là tích vô hướng của cột đầu tiên ( c B) mỗi cột tại biến x 2 .

 2 = < c B, MỘT 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Các ước lượng đơn giản được viết ở hàng cuối cùng của bảng đơn giản, được gọi là hàng delta. Trong trường hợp này, không chỉ các ô cho các biến không cơ bản được điền mà còn cả các ô cơ bản. Dễ dàng kiểm tra xem đối với các cột đơn vị cơ bản của ma trận điều kiện, các ước lượng đơn giản có bằng 0 hay không. Trong ô cuối cùng của dòng đánh giá, chúng ta viết giá trị của hàm mục tiêu tại điểm xo. Lưu ý rằng vì tọa độ không cơ bản của sơ đồ cơ bản bằng 0 nên việc tính hàm mục tiêu bằng công thức sẽ rất thuận tiện

f (x)= < c B ,x B >,

nhân vô hướng các cột đầu tiên và cuối cùng của bảng.

Vì trong số các ước tính j có tiêu cực , sau đó kế hoạch x o không tối ưu và cần phải tìm ra một phương án cơ bản mới bằng cách thay thế một trong các biến cơ bản bằng một biến mới trong số các biến không cơ bản.

Bước 2. Vì cả hai ước tính  1 và  2 < 0,то в базис можно включить любую из переменных x 1, x 2 . Hãy để chúng tôi đưa vào cơ sở biến có ước tính âm tuyệt đối lớn nhất, đó là x 2 .

Cột của bảng đơn chứa biến được nhập vào cơ sở được gọi là cột dẫn đầu .

Trong ví dụ, cột đầu tiên sẽ ở x2 .

Bước 3. Nếu tất cả các phần tử ở cột đầu đều âm thì không có giải pháp nào cho vấn đề và giá trị tối đa f (x) . Trong ví dụ, tất cả các phần tử của cột đầu đều dương, do đó, chúng ta có thể tìm thấy giá trị lớn nhất x 2 , tại đó một trong các biến cơ bản cũ sẽ bằng 0. Hãy nhớ rằng giá trị tối đa x 2 = phút(4/2, 12/2)=2.

Theo bảng, giá trị này được tính như sau tỷ lệ nhỏ nhất của các thành phần của đường cơ sở (từ cột cuối cùng) với thành phần tương ứng tích cực các phần tử của cột đầu.

Tỷ lệ nhỏ nhất nằm ở hàng có biến cơ sở x3. Vì vậy biến x 3 loại trừ khỏi các biến cơ bản ( x 3 = 0).

Dòng chứa biến bị loại khỏi cơ sở được gọi là dòng dẫn đầu.

Trong ví dụ, dòng dẫn đầu sẽ là dòng đầu tiên.

Phần tử nằm ở giao điểm của hàng đầu và cột đầu được gọi là phần tử đầu.

Trong trường hợp của chúng tôi, phần tử hàng đầu Một 12 = 2.

Bàn 2 - Bảng đơn giản ban đầu có hàng và cột ở đầu

c B	Những thay đổi cơ bản.	với 1 = 1	với 2 = 2	với 3 = 0	C 4 = 0	Giá trị biến cơ bản	phương trình
		x 1	x 2	x 3	x 4
c 3 = 0	x 3	–1	2	1	0	4	trang 1
c 4 = 0	x 4	3	2	0	1	12	p2
Dòng đánh giá j		 1 = –1	 2 = –2	 3 = 0	 4 = 0	f(x)= 0

Bước 4. Để có được một kế hoạch cơ bản mới, chúng ta quy bài toán về một dạng ưu tiên mới đối với các biến cơ bản mới.

Để làm điều này, chúng ta sẽ xây dựng một bảng đơn giản mới, trong cột thứ hai thay vì biến bị loại trừ x 3 hãy viết một biến cơ bản mới x 2, và trong cột đầu tiên ( với B) thay vì từ 3 Hãy viết hệ số của hàm mục tiêu tại x 2 : c 2 =2. Trong bảng đơn giản mới, cột tại x 2 phải trở thành một (phần tử đứng đầu phải bằng 1 và tất cả các phần tử khác phải bằng 0). Điều này đạt được bằng các phép biến đổi hàng trong bảng sau.

Một. Chúng ta chia tất cả các phần tử của hàng đầu cho phần tử đầu và viết chúng vào cùng một hàng của bảng đơn giản mới.

Chuỗi kết quả p 1" Hãy gọi nó là sự cho phép.

b. Đối với dòng thứ hai còn lại, chúng ta thêm dòng phân giải, nhân với một số sao cho phần tử ở cột đầu bằng 0.

p 2 "= p 2 + (- 2) p 1 "= p 2 - p 1.

c. Hãy điền vào dòng cuối cùng bằng cách tính toán các ước tính  j " =< c Б ", A j " >- - cj,Ở đâu c B", A j " - các cột tương ứng của bảng đơn giản mới và giá trị của hàm mục tiêu f(x)=< c Б ", x Б " >.

Chúng ta thu được bảng đơn thứ hai với cơ sở mới.

Bảng 3 - Kết quả của lần lặp đầu tiên

c B"	Những thay đổi cơ bản.	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản	phương trình
		x 1	x 2	x 3	x 4
c 2 =2	x 2	–1/2	1	1/2	0	2	p 1" =p 1/2
c 4 = 0	x 4	4	0	-1	1	8	p 2 " =p 2 - p 1
ước tính j"		–2	0	1	0	f(x")=4

Đường cơ sở mới x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ).

Kể từ khi đánh giá  1 = -2 < 0, sau đó kế hoạch x " không tối ưu. Để chuyển sang một sơ đồ cơ bản mới (của điểm góc lân cận), chúng ta sẽ thực hiện một phép lặp khác của phương pháp đơn hình.

Bởi vì  1 < 0, sau đó một biến được đưa vào cơ sở x 1 . Cột đầu tiên chứa x 1 - dẫn đầu.

Chúng tôi tìm thấy mối quan hệ giữa các thành phần của kế hoạch cơ bản và tương ứng tích cực phần tử của cột đầu tiên và lấy hàng có tỷ lệ nhỏ nhất làm hàng đầu. Trong Bảng 2, ở cột đầu tiên chỉ có phần tử thứ hai lớn hơn 0 (= 4), do đó dòng thứ hai sẽ là dòng dẫn đầu, và cơ sở nằm trong đó Biến đổi x 4 bị loại khỏi cơ sở .

Chúng tôi chọn cột đầu tiên và hàng đầu tiên và tại giao điểm của chúng, chúng tôi tìm thấy phần tử dẫn đầu (= 4) .

Chúng tôi xây dựng một bảng đơn giản (thứ ba) mới, thay thế biến cơ bản trong đó x 4 TRÊN x 1 , đồng thời biến đổi lại các hàng của bảng sao cho phần tử đứng đầu bằng 1 và các phần tử còn lại của cột dẫn đầu trở thành 0. Để thực hiện việc này, hãy chia dòng đầu tiên (thứ hai) cho 4 và thêm dòng thứ hai chia cho 2 vào dòng đầu tiên. Dòng cuối cùng tính toán bằng cách sử dụng các công thức ước tính đơn giản j "" = < c Б "", Aj ""> - cj,Ở đâu c B "", Aj "" - các cột tương ứng của bảng đơn giản mới. Giá trị của hàm mục tiêu trên đường cơ sở mới được tìm thấy bằng công thức f(x "")= < c Б "", x B "" >.

Bảng 4 - Kết quả của lần lặp thứ hai

c B ""	Nền tảng thay đổi.	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản	phương trình
		x 1	x 2	x 3	x 4
c 2 =2	x 2	0	1	3/8	1/8	3	trang 1 "" = p 1 "+p 2 ""/2
c 1 = 1	x 1	1	0	-1/4	1/4	2	p 2 "" = p 2 "/4
ước tính  j ""		0	0	1/2	1/2	f(x "")= 8

Đường cơ sở mới x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Vì tất cả các ước lượng đều không âm nên kế hoạch x ""- phương án tối ưu.

Như vậy, x* = (2, 3, 0, 0 ), f(x*) = 8.

PHẦN KẾT LUẬN

Các phương pháp được xem xét để giải các bài toán quy hoạch tuyến tính được sử dụng rộng rãi trong thực tế. Tuy nhiên, cần lưu ý rằng mô hình toán học luôn kém hơn mô hình thực tế hệ thống kinh tế. Nó chỉ mô tả hệ thống này một cách gần đúng, làm nổi bật một số thuộc tính và bỏ qua những thuộc tính khác. Để bù đắp cho sự thiếu sót này trong kinh tế toán học, một số loại mô hình đang được phát triển, mỗi loại được thiết kế để phản ánh một khía cạnh cụ thể của thực tế kinh tế để khi giải quyết một vấn đề cụ thể vấn đề kinh tế có thể chọn một mô hình phù hợp nhất với nó.

DANH MỤC TÀI LIỆU THAM KHẢO ĐƯỢC SỬ DỤNG

1. Ashmanov S.A. Lập trình tuyến tính. – M.: Nauka, 1981.

2. Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Lập trình toán học. – M.: trường sau đại học, 1980.

3. Kalikhman I.L. Đại số tuyến tính và lập trình. – M.: Trường Cao Đẳng, 1967.

4. Nit I.V. Lập trình tuyến tính. – M.: Nhà xuất bản Đại học Tổng hợp Matxcova, 1978.

5. Yudin D.B., Golshtein E.G. Lập trình tuyến tính. Lý thuyết và phương pháp cuối cùng. – M.: Fizmatiz, 1963.

6. Tarasenko N.V. Toán-2. Lập trình tuyến tính: Giáo trình. – Irkutsk: nhà xuất bản BGUEP, 2003.

7. Lập trình toán học trong các ví dụ và bài toán: Proc. trợ cấp. – tái bản lần thứ 2, tái bản. và bổ sung – M.: Cao hơn. trường học, 1993. – 336 tr.

8. www.yandex.ru

9. www.mathematica.ru

Một phương pháp phổ biến để giải các bài toán LP được gọi là phương pháp đơn hình. Chúng tôi sẽ giải thích việc sử dụng phương pháp này và phương pháp sửa đổi phổ biến nhất của nó, phương pháp đơn công hai pha, kèm theo các ví dụ.
Ví dụ. Giải bài toán LP sau đây trong hình thức kinh điển phương pháp đơn giản. (5.5) (5.6)
x i ≥ 0, i = 1,…,6 (5,7)
Một bài toán LP được cho là có dạng chính tắc nếu mọi ràng buộc (ngoại trừ các điều kiện không âm của các biến) có dạng đẳng thức, và mọi số hạng tự do đều không âm. Vì vậy, chúng tôi có vấn đề ở dạng chính tắc.
Ý tưởng của phương pháp đơn giản như sau. Trước tiên, bạn cần tìm một số đỉnh (ban đầu) của khối đa diện có nghiệm chấp nhận được (có thể chấp nhận ban đầu). giải pháp cơ bản). Sau đó, bạn cần kiểm tra giải pháp này cho tối ưu. Nếu nó tối ưu thì đã tìm được giải pháp; nếu không thì đi đến một đỉnh khác của khối đa diện và kiểm tra lại xem có tối ưu không. Do tính hữu hạn của các đỉnh của khối đa diện (hệ quả của tính hữu hạn của các ràng buộc của bài toán LP), trong một số hữu hạn các “bước” chúng ta sẽ tìm được điểm yêu cầu là cực tiểu hoặc cực đại. Cần lưu ý rằng khi di chuyển từ đỉnh này sang đỉnh khác, giá trị của hàm mục tiêu giảm (trong bài toán cực tiểu) hoặc tăng (trong bài toán cực đại).
Như vậy, ý tưởng của phương pháp đơn hình dựa trên ba tính chất của bài toán LP.
Giải pháp.Để tìm giải pháp cơ sở khả thi ban đầu, tức là để xác định các biến cơ sở, hệ thống (5.6) phải được rút gọn về dạng “đường chéo”. Sử dụng phương pháp Gaussian (phương pháp loại bỏ tuần tự các ẩn số), ta thu được từ (5.6): (5.8)
Do đó, các biến cơ bản là x 2 , x 4 , x 5 , x 6 , Chúng tôi cung cấp cho chúng các giá trị bằng với các thành viên miễn phí của chuỗi tương ứng: x 2 =40, x 4 =20, x 5 =10, x 6 =30,. Biến x 1 Và x 3 là không cơ bản: x 1 = 0, x 3 = 0.
Hãy xây dựng giải pháp cơ bản khả thi ban đầu
x 0 = (0,40,0,20,10,30) (5,9)
Kiểm tra tính tối ưu của giải pháp tìm được x 0 cần loại trừ các biến cơ bản khỏi hàm mục tiêu (sử dụng hệ thống (5.8)) và xây dựng một bảng đơn giản đặc biệt.
Sau khi loại bỏ các biến, sẽ thuận tiện khi viết hàm mục tiêu dưới dạng:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Bây giờ, bằng cách sử dụng (5.8)–(5.10), chúng ta soạn bảng đơn giản ban đầu:

Đường 0 chứa các hệ số có dấu ngược lại với các biến tương ứng của hàm mục tiêu. Tiêu chí tối ưu (đối với bài toán tìm kiếm tối thiểu): giải pháp cơ bản có thể chấp nhận được ( x 0) là tối ưu nếu không có một số dương hoàn toàn nào trên dòng 0 (không tính giá trị của hàm mục tiêu (880)). Quy tắc này cũng áp dụng cho các lần lặp tiếp theo (bảng). Các phần tử của hàng thứ 0 sẽ được gọi là ước tính cột.
Vì vậy nghiệm cơ sở khả thi ban đầu (5.9) là dưới mức tối ưu: 7>0, 14>0 .
Cột 0 chứa giá trị của các biến cơ bản. Chúng phải không âm (xem phương trình (5.7)). Các hệ số của các biến trong hệ (5.8) được viết từ dòng đầu tiên đến dòng thứ tư.
Bởi vì x 0 không tối ưu thì chúng ta cần chuyển sang một đỉnh khác của khối đa diện có nghiệm chấp nhận được (xây dựng một d.b.r. mới). Để làm điều này, bạn cần tìm phần tử hàng đầu và thực hiện một phép biến đổi nhất định (biến đổi đơn giản).
Đầu tiên ta tìm phần tử đầu bảng, đứng ở giao điểm của cột đầu (cột có số điểm dương cao nhất) và hàng đầu (dòng tương ứng với tỷ lệ tối thiểu của các phần tử cột 0 so với các phần tử tương ứng (hoàn toàn dương) của cột đầu).
Trong Bảng 1, cột đầu tiên là cột thứ ba và hàng đầu tiên là hàng thứ tư. (phút(40/1,30/1)=30/1)được biểu thị bằng các mũi tên và phần tử dẫn đầu được biểu thị bằng một vòng tròn. Phần tử hàng đầu chỉ ra rằng biến cơ bản x 6 cần phải được thay thế bằng một cái không cơ bản x 3. Khi đó các biến cơ bản mới sẽ là x 2 , x 3 , x 4 , x 5 , và không cơ bản - x1, x6,. Điều này có nghĩa là sự chuyển đổi sang một đỉnh mới của khối đa diện có nghiệm có thể chấp nhận được. Để tìm các giá trị tọa độ của một giải pháp cơ sở khả thi mới x00 bạn cần xây dựng một bảng đơn giản mới và thực hiện các phép biến đổi cơ bản trong đó:
MỘT) chia tất cả các phần tử của dòng dẫn đầu cho phần tử dẫn đầu, từ đó biến phần tử dẫn đầu thành 1 (để dễ tính toán);
b) dùng phần tử đầu (bằng 1), biến tất cả các phần tử ở cột đầu thành số 0 (tương tự như phương pháp loại bỏ ẩn số);
Kết quả là giá trị của các biến cơ bản mới thu được ở cột 0 x 2 , x 3 , x 4 , x 5 ,(xem bảng 2) - các thành phần cơ bản của đỉnh mới x00(thành phần không cơ bản x 1 = 0, x 6 = 0,).

Như Bảng 2 cho thấy, giải pháp cơ bản mới x 00 =(0,10,30,20,40,0) dưới mức tối ưu (dòng 0 chứa điểm không âm là 7). Do đó, với phần tử dẫn đầu 1 (xem Bảng 2), chúng ta xây dựng một bảng đơn giản mới, tức là. xây dựng một giải pháp cơ bản khả thi mới

Bảng 3 tương ứng với giải pháp cơ bản chấp nhận được x 000 =(10,0,30,10,50,0) và nó là tối ưu, bởi vì không ở dòng số 0 xếp hạng tích cực. Đó là lý do tại sao f(x 000)=390 Có giá trị tối thiểu chức năng mục tiêu.
Trả lời: x 000 =(10, 0, 30, 10, 50, 0)- điểm tối thiểu, f(x 000)=390.

Tìm phương án tối ưu. Phương pháp này là phổ quát; nó cho phép giải các bài toán quy hoạch tuyến tính ở bất kỳ chiều nào trong một công thức tổng quát. Tuy nhiên, phương pháp này yêu cầu giảm bài toán ban đầu thành hình thức kinh điển.

Ý tưởng chính của phương pháp đơn hình là di chuyển từ đỉnh này sang đỉnh khác của ODR sao cho mỗi lần chuyển đổi giá trị của CF sẽ giảm đi. Đây là cách bạn có thể đi từ bất kỳ đỉnh nào đến đỉnh tối ưu và có được phương án tối ưu.

Ví dụ: Cho phương án tham chiếu X =(x1,x2,…,xm,0,0,…,0) và hệ liên kết các vectơ độc lập tuyến tính: A1,A2,…,Am được biết thì đối với phương án tham chiếu này bạn có thể tính giá trị CF Z=(c1x1+c2x2+…+cmxm) và viết ra các điều kiện giới hạn trong mẫu sau x1A1+x2A2+…+xmAm=b

Vì các vectơ A1, A2,…, Am độc lập tuyến tính nên bất kỳ vectơ Aj nào cũng có thể được mở rộng thành các vectơ sau: Aj=x1jA1+x2jA2+…+xmjAm (*) Hãy để chúng tôi giới thiệu các giá trị Zj Zj=x1jc1+x2jc2+…+ xmjcm, trong đó xij là hệ số tương ứng với Ai trong vectơ khai triển Aj theo vectơ cơ sở

Định lý 1: Cải thiện kế hoạch tham khảo

Nếu đối với một số chỉ số j điều kiện Zj-Cj>0 được thỏa mãn thì giá trị của CF có thể giảm đi và:

· nếu CF bị giới hạn từ bên dưới thì có thể xây dựng sơ đồ tham chiếu với giá trị CF nhỏ hơn, giống như trước đó

· Nếu TF không bị giới hạn từ bên dưới thì có thể xây dựng phương án tương ứng với giá trị TF nhỏ tùy ý

Định lý 2: tiêu chí tối ưu cho phương án tham chiếu

Nếu với một số chỉ số j trong sơ đồ tham chiếu có bất đẳng thức Zj-Cj0. Để đạt được mức tối thiểu này đối với vectơ Ak, thì vectơ này phải được suy ra từ cơ sở. Đường thẳng tương ứng với vectơ này được gọi là hướng dẫn và được ký hiệu là “à”.

4. Sau khi xác định các hướng dẫn cột và hàng, hãy điền vào một bảng đơn giản mới. Trong bảng như vậy, Ai sẽ xuất hiện ở vị trí của đường dẫn. đổ đầy bảng mới bắt đầu bằng một dòng hướng dẫn. Là một thành phần của sơ đồ tham chiếu, giá trị Ҩ0 X'l=Ҩ0=Xk/Xkl được viết ở đó, các phần tử còn lại của dòng này được xác định theo công thức X'lj X'lj=Xkj/Xkl trong đó Xkl là phần tử nằm ở giao điểm của các hướng dẫn hàng và cột, cụ thể trên đó tất cả các phần tử cũ của đường hướng dẫn đều được phân chia và một đơn vị tự động xuất hiện ở vị trí của phần tử Xkl trước đây. Nguyên tắc chungđể tính lại đường dẫn bạn có thể viết như sau: Ak (phần tử mới của đường dẫn) = (phần tử cũ của đường dẫn)/(phần tử đứng tại giao điểm của cột và hàng dẫn hướng)

5. Tất cả các phần tử của các hàng còn lại của bảng đều được tính toán lại, bao gồm cả hàng bổ sung dưới cùng. Việc tính toán lại được thực hiện theo công thức

· đối với các thành phần của phương án tham chiếu X'i=Xi-Ҩ0Xil=Xi-(Xk/Xkl)*Xil

· cho các thành phần được mở rộng trên cơ sở X'ij=Xij-(Xkj/Xkl)*Xil

· Vì dòng bổ sung Z'j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Tất cả các công thức này được xây dựng theo một quy tắc:

(email mới)=(email cũ)-(email hướng hàng mới)*(email hướng cột ở hàng tương ứng)

Sau khi điền vào bảng đơn giản mới, quá trình chuyển sang giai đoạn thứ hai của thuật toán sẽ diễn ra.

Phương pháp tự nhiên và cơ sở nhân tạo. Các khái niệm, thuật toán cơ bản của phương pháp.

Đối với hầu hết các bài toán quy hoạch tuyến tính, khó khăn nảy sinh khi giải chúng liên quan đến việc xác định sơ đồ tham chiếu ban đầu và bảng đơn ban đầu mà từ đó tất cả các phép lặp bắt đầu. Điều này là do trong các bài toán thực tế giữa các vectơ Ai không có vectơ nào chỉ chứa một thành phần khác 0, tức là các vectơ có dạng (0,0,0,…,0,1,0,…,0) hoặc số lượng của chúng không đủ để làm cơ sở. Tức là không thể hình thành cơ sở tự nhiên được.

Phương pháp cơ sở nhân tạo dựa trên giới thiệu giả tạo thành mô hình toán học của bài toán các vectơ đó.

Cho một ZLP có dạng chính tắc

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Sau đó nó được chuyển về dạng

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+…+anmxn+xn+m=bm

Trong đó M là vô hạn số lượng lớn. Trong bài toán tìm được, cơ sở ban đầu được nhìn thấy ngay lập tức; các vectơ với các biến được đưa vào một cách giả tạo xn+1, xn+2,…, xn+m nên được coi là nó. Vì các vectơ này sẽ có dạng: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Sau đó, bài toán đã biến đổi sẽ được giải bằng thuật toán phương pháp đơn hình. Sơ đồ tham chiếu ban đầu của bài toán được chuyển đổi có dạng (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Bảng đơn giản ban đầu trông như thế này:

Nền tảng	hệ số CF	Kế hoạch	C1	C2	…	Cn	M	M	…	M
			A1	A2	…	MỘT	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Chúng tôi xác định các phần tử của dòng bổ sung bằng cách sử dụng các công thức Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Để xác định sự khác biệt Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

Sau khi nhận được bảng đơn ban đầu, nó được biến đổi, cố gắng rút ra từ các vectơ cơ sở tương ứng với các biến bổ sung được đưa vào.

Vì M rất con số lớn, thì trong số các hiệu Zj-Cj sẽ có nhiều số dương. Nghĩa là sẽ có nhiều ứng cử viên để đưa vào cơ sở trong số các vectơ A1,A2,…,An

Nếu vectơ nào đó tương ứng với các biến được đưa vào giả tạo xn+1,xn+2,…,xn+m thì vectơ tương ứng được dẫn xuất từ ​​cơ sở và cột đơn của bảng có vectơ này bị gạch bỏ và không được trả về đến nó một lần nữa. Khi kết thúc quá trình chuyển đổi bảng đơn giản, có thể có hai tùy chọn:

· Tất cả các vectơ tương ứng với các biến nhân tạo đã được suy ra từ cơ sở, trong trường hợp này tất cả các cột của bảng đơn tương ứng với các biến bổ sung sẽ biến mất, và nghiệm sẽ là vấn đề ban đầu

· Phương án tối ưu thu được vẫn sẽ chứa một số biến bổ sung, điều này có nghĩa là ODD của bài toán ban đầu rỗng, tức là các ràng buộc của nó mâu thuẫn nhau, do đó bài toán ban đầu không có nghiệm nào cả.

Các bài toán quy hoạch tuyến tính kép. Tuyên bố các vấn đề, tính chất của họ.

Bài toán đối xứng kép:

Mẫu chuẩn đầu tiên

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

…………………………………………..

a1mx1+a2mx2+…+anmxn>=bm

Vấn đề kép

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Cặp bài toán kép không phân chia

Vấn đề ban đầu ở dạng chính tắc

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

…………………………..

Phương pháp đơn hình bao gồm việc tìm và kiểm tra một đỉnh (góc) là lời giải cho bài toán LP. Ở mỗi giai đoạn, phương pháp chọn một đỉnh và các biến tương ứng của nó, đảm bảo chuyển động đến mức tối thiểu (tối đa) với tốc độ cao nhất. Biến được chọn sẽ thay thế biến khác, hạn chế nhất. Phương pháp đơn hình cũng cho phép bạn xác định liệu có tồn tại nghiệm hay không. Thuật toán thực hiện phương pháp đơn hình có thể được viết là:

Bước 1. Một đỉnh nhất định trong ODR được xác định, tương ứng với các nghiệm (biến) cơ bản được chấp nhận được tìm thấy bằng cách trích xuất từ ​​ma trận T- các cột độc lập tuyến tính và bằng 0 tất cả các biến khác tương ứng với các cột khác của ma trận.

Bước 2.Được chọn từ tất cả những gì có thể còn lại p - t các cạnh tương ứng với các biến không cơ bản, một cạnh (biến) mà khi di chuyển dọc theo nó sẽ dẫn đến hàm mục tiêu giảm nhanh nhất.

Bước 3. Nó giống như một chuyển động được thực hiện từ đỉnh ban đầu dọc theo cạnh đã chọn tới một đỉnh khác, điều này mang lại một giải pháp mới có giá trị CF thấp hơn. Một đỉnh mới được hình thành bằng cách thay thế biến cơ sở (cạnh) bằng biến cơ sở mới (cạnh).

Các cột và phần tử của vectơ thường được sắp xếp và viết dưới dạng bảng đơn giản, cách hình thành bảng này sẽ được trình bày dưới đây.

Phương pháp đơn hình giải bài toán LP ở dạng chuẩn.

Cực tiểu hóa (cực đại hóa) hàm số với điều kiện x > 0; Rìu = b.

Ma trận A là thực và có chiều T x" và xếp hạng T.

Bài toán LP đã được xây dựng cũng có thể được viết dưới dạng

Dựa vào cách ghi bài toán LP dưới dạng (8Л), ta có thể nói rằng ma trận mở rộng

kích thước (t + 1) (n + 2) tương ứng với nghiệm[x/] t.

Hãy biểu diễn ma trận A dưới dạng tập hợp các cột

Vì ma trận A có hạng T, sau đó sẽ có T các cột độc lập tuyến tính của ma trận A, ví dụ (a V1 ,...,a V/i Xét một vectơ x° > 0, sao cho tất cả các cột đó p - t các phần tử là 0 và Ax° = b. Đặt đây là những phần tử có số..., tôi n _ tôi . Chúng ta cũng giả sử rằng vị trí aw của các cột độc lập tuyến tính của ma trận A tương ứng với vị trí của các phần tử khác 0 trong vectơ 0. Về mặt hình học, theo Tuyên bố 3 của § 7.6, điều này có nghĩa là x° là đỉnh (góc) của ODR và ​​ngoài ra, còn thỏa mãn các điều kiện đã cho. Giải pháp này được gọi là giải pháp cơ bản có thể chấp nhận được. Các góc của tập hợp chấp nhận được là giải pháp cơ bản có thể chấp nhận được.

Hãy nhớ lại rằng tập hợp các giải pháp cơ bản chứa tất cả thông tin cần thiết cho giải pháp tối ưu của bài toán LP. Đối với trường hợp hai chiều được xem xét trong § 7.6, các giải pháp cơ bản đều là 6 điểm và các giải pháp cơ bản được chấp nhận là các điểm L, V, Sĩ 0.

Do đó, bất kỳ vectơ x nào tương tự x° đều có thể được viết là

Ở đâu x vào- một vectơ có các phần tử tương ứng với các cột độc lập tuyến tính của ma trận A; xF - vectơ không có phần tử.

Chúng ta hãy định nghĩa tương tự các vectơ

Các biến là phần tử của vectơ x vào,được gọi là biến cơ bản và các biến là phần tử của vectơ x Fđược gọi là miễn phí (các biến không cơ bản).

Bởi vì x°F=0 thì giá trị của hàm mục tiêu đối với vectơ x° ban đầu sẽ bằng

trong đó /° là giá trị của / tại điểm x°.

Nghiệm (8.1) có dạng [x°/°]t cho x > 0 được gọi là giải pháp rõ ràng (rõ ràng). Vì vậy, nếu chúng ta đặt các biến không cơ bản bằng 0, chúng ta sẽ có được nghiệm hiển nhiên.

Để thuận tiện, hãy sắp xếp lại T các cột độc lập tuyến tính của ma trận A trong bên trái và viết ma trận dưới dạng

Ở đây ma trận B tương ứng T cột độc lập tuyến tính có kích thước tx t và xếp hạng T, và ma trận F

là tx (p - t) ma trận. Vì ma trận B bao gồm các cột độc lập tuyến tính nên nó có nghịch đảo B -1 và detB φ 0. Lưu ý rằng để lập ma trận B bạn có thể chọn bất kỳ T cột độc lập tuyến tính của ma trận A.

Chúng ta hãy biểu diễn bài toán (8.1) có xét đến ký hiệu đã giới thiệu

Biểu diễn này tương ứng với ma trận mở rộng. Giả sử rằng

từ đâu theo sau

Nếu vectơ x V. sẽ là nghiệm của hệ Bx d = b thì nó sẽ là nghiệm cơ bản. Nếu bất đẳng thức giữ V.= B -1 b > O thì x vào sẽ là một giải pháp có thể chấp nhận được.

Như vậy nghiệm hiện tại thỏa mãn phương trình sau:

Hãy xem xét ma trận (8.4). Các biến cơ bản sẽ được biểu diễn dưới dạng tường minh nếu thay ma trận B bằng ma trận đẳng thức I. Nhân dòng đầu tiên của ma trận (8.4) bên trái với B~ 1, ta được

trong đó B_1 b > O, tức là T Các phần tử trên cùng ở cột bên phải không âm và biểu thị giá trị hiện tại của các biến.

Ở bên trái dòng trên cùng Kết quả là ma trận đơn vị: B -1 B = I. Bài trình bày này rất thuận tiện, vì khi nhân với một vectơ x vào mỗi biến sẽ nằm trên một dòng riêng biệt.

Do đó, nghiệm cơ bản, mà chúng ta sẽ coi là có thể chấp nhận được và tương ứng với cơ sở B, là x m = [x trong 0], trong đó x trong == B_1 b. Giải pháp cơ bản xuất phát từ giả định rằng x F = 0. Tuy nhiên, nếu xF* 0 thì x^ có thể được tính là x 5 = = B~"b - B^"Fx/r. Thay biểu thức này vào hàm mục tiêu (hàm chi phí), chúng ta thu được

Vì cần xác định sự phụ thuộc của chi phí vào các biến không cơ bản, một trong số đó sau đó được đưa vào các biến cơ bản, nên điểm mấu chốt của ma trận I sẽ bằng 0. Để làm điều này, trong (8.7) chúng ta nhân hàng đầu tiên (của ma trận) với từ đến và thêm nó với cái thứ hai

đâu là giá trị của hàm mục tiêu cho thế kỷ đầu tiên

hình xuyến x 0 từ (8.3).

Ma trận (8.8) được gọi là bảng đơn giản.Đưa cô ấy đến loài này là giai đoạn đầu của thuật toán đơn giản. Trong quá trình thực hiện thuật toán, quá trình chuyển đổi được thực hiện từ bảng này sang bảng khác cho đến khi phần tử phía dưới bên phải của bảng trở thành giá trị tối đa hoặc tối thiểu.

Sử dụng bảng đơn giản, bạn có thể dễ dàng nhận thấy lời giải hợp lệ. Biến x F tương ứng với ma trận con 0, các biến x vào- ma trận đơn vị:

Giả sử rằng bài toán LP đã được rút gọn về dạng chuẩn, bảng đơn đã được tính toán và nghiệm cơ bản ban đầu tương ứng với đỉnh của đa diện nghiệm đã được chọn.

Sau đó - giải pháp cho vấn đề (8.1). Vì thế

như b > Ồ, đây là một giải pháp cơ bản có thể chấp nhận được.

Chúng ta hãy trình bày ma trận (8.9) ở dạng thuận tiện hơn, giữ nguyên ký hiệu cơ bản:

Chúng ta hãy xem xét riêng biệt các vấn đề tối đa hóa và tối thiểu hóa.

Một trong phương pháp phổ quát là một phương pháp đơn giản. Trong phương pháp đơn hình, việc tìm kiếm có hướng các sơ đồ tham chiếu được thực hiện, theo nghĩa là khi di chuyển từ sơ đồ tham chiếu này sang sơ đồ tham chiếu khác, hàm mục tiêu sẽ tăng lên. Giả sử bài toán được viết dưới dạng chính tắc:

f=(n; j=1)ΣCj*Xj (tối đa)

(n;j=1)Σaij*xj=aio (i=1,m)

Xj>=0 (j=1,n)

Nếu bài toán có thể giải được thì phương án tối ưu của nó trùng khớp với ít nhất một trong các nghiệm hỗ trợ cho phương trình. Sơ đồ tham chiếu này được tìm thấy bằng phương pháp đơn hình nhờ tìm kiếm theo thứ tự các sơ đồ tham chiếu. Thứ tự được hiểu theo nghĩa là khi chuyển từ phương án tham chiếu này sang phương án tham chiếu khác thì các giá trị tương ứng của hàm mục tiêu đều tăng lên. Vì vậy, phương pháp đơn giản được gọi là kế hoạch cải tiến nhất quán của m-house.

Ý tưởng chung của phương pháp đơn giảnđiều đó có đơn giản không? m-d được chia thành 2 giai đoạn:

1. tìm kế hoạch tham khảo ban đầu;

2. Cải tiến nhất quán cho đến khi tìm ra phương án tối ưu, trong đó hàm mục tiêu đạt giá trị cực đại.

8. Dấu hiệu tối ưu của phương án hỗ trợ ZLP.

Thuộc tính gói hỗ trợ là độ không âm của các phần tử thuộc cột số hạng tự do, không tính các phần tử của hàng f. Dấu hiệu của phương án tối ưu- nếu ở bảng đơn chứa một kế hoạch hỗ trợ, tất cả các phần tử của chuỗi f không âm (không tính thuật ngữ miễn phí booo), thì kế hoạch hỗ trợ này là tối ưu. Nếu trong quan hệ f=boo-(n-m;j=1)Σboj*Xj+m giá trị của tất cả các biến tự do bằng 0, thì hàm mục tiêu sẽ bằng số hạng tự do f(vectorXo)=boo. Với giá trị miễn phí ngày càng tăng hàm biến sẽ bắt đầu giảm, do đó, với kế hoạch Ho, hàm số sẽ đạt giá trị cực trị.

9. Tìm kế hoạch tham chiếu ban đầu của ZLP.

Để tìm kế hoạch tham khảo ban đầu, chúng tôi có thể đề xuất như sau thuật toán:

1. Viết bài toán dưới dạng bảng Jordan sao cho tất cả các phần tử của cột số hạng tự do đều không âm, tức là. bất đẳng thức aio>=0 (i=1,m) được thỏa mãn. Những phương trình trong đó số hạng tự do âm trước tiên được nhân với -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	tình yêu	am1…..amn
f=		-c1…. -cn

Chuyển đổi bảng bằng các bước loại bỏ Jordan, thay thế các số 0 ở cột bên trái bằng x tương ứng. Đồng thời, tại mỗi bước cho phép có thể được lựa chọn bất kỳ cột nào chứa ít nhất một phần tử dương. Hàng phân giải được xác định bằng tỷ lệ nhỏ nhất của các số hạng tự do với các phần tử dương tương ứng của cột phân giải. Nếu trong quá trình loại bỏ, gặp một hàng 0, tất cả các phần tử của nó đều bằng 0 và số hạng tự do khác 0 thì hệ phương trình ràng buộc không có nghiệm. Nếu chúng ta gặp một hàng 0 trong đó, ngoài số hạng tự do, không có phần tử dương nào khác, thì tập phương trình giới hạn không có nghiệm không âm. chung, thì sau một số bước nhất định, tất cả các số 0 ở cột bên trái sẽ được thay thế bằng x và từ đó có được một cơ sở nhất định và do đó, một sơ đồ tham chiếu tương ứng.

10. Tìm phương án tham chiếu tối ưu cho ZLP.

Kế hoạch hỗ trợ ban đầu của Hồ được kiểm tra tính tối ưu.

Nếu không có phần tử âm nào trong hàng f (không tính số hạng tự do) thì -plan là tối ưu. Nếu cũng không có phần tử 0 nào trong hàng f thì chỉ có một phương án tối ưu; nếu trong số các phần tử có ít nhất một phần tử bằng 0 thì có vô số phương án tối ưu. Nếu có ít nhất một phần tử âm trong hàng f và không có phần tử dương nào trong cột tương ứng thì hàm mục tiêu không bị giới hạn trong vùng khả thi. Vấn đề không thể giải quyết được. Nếu có ít nhất một phần tử âm trong hàng f và trong mỗi cột có phần tử như vậy có ít nhất một phần tử dương, thì bạn có thể chuyển sang sơ đồ tham chiếu mới gần với sơ đồ tối ưu hơn. Để làm điều này, cột có phần tử âm trong hàng f được lấy là dễ dãi; Họ xác định chuỗi phân giải từ quan hệ đơn hình tối thiểu và thực hiện bước loại trừ Jordan. Kế hoạch tham chiếu thu được một lần nữa được kiểm tra để tìm mức tối ưu. Điều này được lặp lại cho đến khi tìm được phương án tham chiếu tối ưu hoặc tính không thể giải quyết được của vấn đề được xác lập.

11. Dấu hiệu không giới hạn của hàm mục tiêu trên tập mặt bằng và hình minh họa hình học.

Một dấu hiệu của tính không giới hạn của hàm mục tiêu là trong quá trình tìm kiếm phương án tối ưu, người ta thu được một cột có phần tử âm trong hàng f không chứa một phần tử dương nào.

12. Dấu vô cực của tập phương án tối ưu và minh hoạ hình học.

Dấu hiệu của sự vô hạn của một tập hợp phương án là sự có mặt trong hàng f của một điểm đơn hình chứa phương án tối ưu của ít nhất một phần tử 0, không tính số hạng tự do. Hãy tìm một phương án tối ưu X1*, với một phần tử 0 ở hàng f. Một phương án tối ưu X2* khác có thể được tìm thấy bằng cách chọn một cột có phần tử 0 ở hàng f làm độ phân giải. Phần còn lại được tối ưu hóa. kế hoạch có thể được định nghĩa là một sự kết hợp tuyến tính:

Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ