Phương pháp đơn hình cải tiến để giải các bài toán quy hoạch mục tiêu. Phương pháp đơn giản sửa đổi

Ý tưởng cơ bản của phương pháp đơn hình sửa đổi là sử dụng ma trận nghịch đảo hiện tại (và dữ liệu gốc của bài toán) để thực hiện các phép tính cần thiết nhằm xác định các biến cần bao gồm và loại trừ. Việc biểu diễn ma trận nghịch đảo ở dạng nhân cho phép bạn tính toán một chuỗi ma trận nghịch đảo trực tiếp từ dữ liệu nguồn mà không cần sử dụng nhiều phép toán nghịch đảo cho mỗi cơ sở. Như trong phương pháp đơn hình thông thường, trong trường hợp này cơ sở ban đầu luôn là ma trận đơn vị I, nghịch đảo của chính ma trận này. Vì vậy, nếu
- Chuỗi ma trận nghịch đảo tương ứng với các lần lặp 1, 2,…,i, và
là dãy ma trận tương ứng với chúng thì

Trình tự thay thế dẫn đến công thức sau:

(2.23)

Cần nhấn mạnh rằng cách biểu diễn nhân của ma trận nghịch đảo là không thủ tục cần thiết thực hiện mạch tính toán phương pháp đơn giản sửa đổi và tại mỗi lần lặp, bạn có thể sử dụng bất kỳ phương pháp nào để đảo ngược cơ sở hiện tại. Khi sử dụng phương pháp đơn hình đã sửa đổi, điều quan trọng là ma trận nghịch đảo được tính toán theo cách làm giảm tác động của lỗi làm tròn máy.

Các bước của thuật toán phương pháp đơn giản sửa đổi về cơ bản giống như các bước của thuật toán phương pháp đơn giản thông thường. Sau khi tìm được cơ sở I ban đầu xác định được vectơ hệ số tương ứng hàm mục tiêu, các phần tử của chúng được hình thành tùy thuộc vào việc các biến cơ bản ban đầu là dư thừa (dư thừa) hay nhân tạo.

1. 2.7.2. Biểu diễn nhân của ma trận nghịch đảo

Trong biểu diễn nhân của ma trận nghịch đảo, phép toán đại số ma trận được sử dụng để tính các phần tử của ma trận nghịch đảo đối với ma trận mới của các vectơ cơ sở từ ma trận nghịch đảo đã biết của cơ sở trước đó, với điều kiện hai cơ sở đang xét chỉ khác nhau ở điểm vectơ một cột Phương pháp biểu diễn ma trận nghịch đảo này rất thuận tiện khi sử dụng trong sơ đồ tính toán của phương pháp đơn hình, vì các cơ số tương ứng với mỗi hai lần lặp liên tiếp chỉ khác nhau ở một cột (do thay thế vectơ cột bị loại bỏ của cơ sở hiện tại). với một vectơ cột mới). Nói cách khác, ma trận cơ sở hiện tại và một ma trận cơ sở mới
, tương ứng với lần lặp tiếp theo, chỉ khác nhau ở một cột. Với cách biểu diễn nhân của ma trận nghịch đảo
tương ứng với cơ sở mới, nó được tính bằng cách nhân nghịch đảo của ma trận hiện tại ở bên trái
thành một ma trận được hình thành theo những quy tắc nhất định .

Hãy xác định ma trận nhận dạng theo cách sau:

(2.24)

Ở đâu - vectơ cột đơn vị với phần tử thứ i, bằng một, và các phần tử khác, bằng 0. Giả sử các ma trận đã biết Và
và vectơ ma trận được thay thế bằng một vectơ mới ; như thông lệ khi mô tả phương pháp đơn hình, vectơ được định nghĩa là được bao gồm trong cơ sở và vectơ - như bị loại trừ khỏi cơ sở. Để đơn giản hóa việc viết các mối quan hệ toán học, chúng ta sử dụng định nghĩa sau
,trong đó sẽ đại diện cho phần tử thứ k
. Sau đó một cái mới ma trận nghịch đảo
có thể được tính bằng công thức sau:

(2.25)

miễn là
. Nếu như
, ma trận
không tồn tại. Lưu ý rằng ma trận thu được từ ma trận bằng cách thay thế vectơ cột thứ r của nó cột .

1.5.1. Sơ đồ tính toán dựa trên phép biến đổi ma trận nghịch đảo. Phân tích quy trình tính toán của phương pháp đơn hình từ góc độ ước lượng cường độ lao động, dễ dàng nhận thấy mấu chốt nhất trong vấn đề này là khâu tính toán lại các giá trị. MỘT Và b khi chuyển từ phương án cơ bản này sang phương án cơ bản khác (mục 3 của thuật toán). Tuy nhiên, trong trường hợp khi số lượng ràng buộc của bài toán tôi rõ ràng có ít biến hơn N, bạn có thể đạt được “tiết kiệm” đáng kể bằng cách thực hiện ở lần lặp tiếp theo q Biến đổi Jordan-Gauss không qua ma trận MỘT(β ( q)) và trên ma trận Δ -1 (β ( q)). Điều này cũng tính đến thực tế là, nếu cần, sử dụng công thức (1.26), người ta luôn có thể thu được MỘT(β ( q)) bởi Δ -1 (β ( q)). Hơn nữa, để thực hiện các hành động của thủ tục đơn hình được mô tả ở trên, chúng ta thực sự không cần một ma trận MỘT(β ( q)) toàn bộ. Trong thực tế, chỉ có dòng xếp hạng được sử dụng trong đó Một 0 (β ( q)) và cột đầu một tôi(β ( q)). Những xem xét này tạo thành cơ sở của sơ đồ tính toán của phương pháp đơn hình, dựa trên phép biến đổi ma trận nghịch đảo, còn được gọi là phương pháp đơn giản sửa đổi. Đầu tiên thuật toán nàyđược đề xuất vào năm 1951 trong tác phẩm của L. V. Kantorovich.

Sơ đồ tính toán của phương pháp đơn hình cải tiến tương ứng với hệ thống bảng T 1 và T 2 (q) . Bàn T 1 (cơm. 1.7) là chung cho tất cả các lần lặp và phục vụ để có được dòng ước tính cho đường cơ sở hiện tại Một 0 (β ( q)). Nếu chúng ta biểu thị bằng δ Tôi(β ( q)) (TôiÎ 0: tôi) các hàng của ma trận Δ -1 (β ( q)), thì từ (1.26), cụ thể suy ra rằng

Như có thể thấy từ cơm. 1.7, T 1 gồm 3 khối:

Ø Ø tâm chứa ma trận A;

Ø Ø trong khối bên trái của bảng tại mỗi lần lặp không có hàng nào của ma trận được thêm vàoΔ -1 (β ( q))cho cơ sở hiện tại;

Ø Ø khối dưới nằm dưới ma trận A, ở mỗi lần lặp lại, nó được bổ sung một dòng ước tính của kế hoạch hiện tại, được tính bằng công thức (1.42).

Bảng đơn giản T 2 (q) được thể hiện ở cơm. 1.8, tương ứng với cơ sở KZLP được chấp nhận β ( q) nhận được tại q lần lặp thứ. Cột N(β ( q)) chứa số cột cơ sở (theo thứ tự xuất hiện trong cơ sở); cột b(β ( q)) - các thành phần của vectơ ràng buộc so với cơ sở hiện tại β ( q) ; Δ -1 (β ( q)) - ma trận nghịch đảo của ma trận cột mở rộng của cơ sở hiện hành β ( q) ; đồ thị một tôi chứa một vectơ mở rộng các điều kiện được đưa vào cơ sở ở lần lặp hiện tại và biểu đồ tiếp theo chứa tọa độ một tôi(β ( q)) của cùng một cột trong cơ sở hiện tại β ( q) .

Bằng cách tương tự với đoạn 1.4.1, chúng tôi sẽ mô tả sơ đồ chính thức của thuật toán của phương pháp đơn giản được sửa đổi.

0 giai đoạn. Tìm một đường cơ sở khả thi.

1. Để tìm cơ sở có thể chấp nhận được, có thể áp dụng phương pháp giảm thiểu dư lượng được thảo luận ở đoạn 1.4.5. Trong trường hợp này, để giải bài toán phụ, người ta sử dụng quy trình của phương pháp đơn hình sửa đổi. Nhờ giai đoạn 0, chúng ta có được đường cơ sở khả thi x(β (1)) và ma trận tương ứng Δ -1 (β (1)) và vectơ b(β(1)).

2. Điền vào phần giữa bảng T 1 chứa ma trận MỘT.

3. Nội dung của ma trận Δ -1(β(1)) và vectơ b(β (1)), thu được ở giai đoạn tìm kiếm phương án cơ bản được chấp nhận, được chuyển vào bảng T 2 (1) .

4. Đặt số lần lặp hiện tại q bằng 1 và chuyển sang giai đoạn I.

Giai đoạn 1. Lặp lại tiêu chuẩn của thuật toán- thực hiện cho kế hoạch cơ bản tiếp theo x(β ( q)).

1°. Kiểm tra tính tối ưu của kế hoạch cơ sở hiện tại. Nội dung hàng 0 của bảng T 2 (q) - δ 0 (β ( q)) được viết lại vào cột tương ứng của bảng T 1 . Sử dụng công thức (1.42) ta tính toán và điền vào dòng Một 0 (β ( q)). Chúng tôi xem dòng đánh giá Một 0 (β ( q)). Có hai lựa chọn:

1. Một 0 (β ( q)) ≥0 -kế hoạch tương ứng với cơ sở hiện tại của bài toán, tối ưu. Quá trình tính toán được hoàn thành. Theo công thức (1.33) và (1.32), phương án tối ưu của bài toán được viết ra X* = x(β ( q)) Và giá trị tối ưu hàm mục tiêu f(X*) = f(x(β ( q))).

1". Trong dòng xếp hạng Một 0 (β ( q)) có ít nhất một phần tử Một 0, j(β ( q))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x(β ( q)) - dưới mức tối ưu. Số được chọn tôi, tương ứng với một phần tử có điểm âm tối thiểu (tối đa về giá trị tuyệt đối):

tôi cột ma trận thứ MỘT trở thành dẫn đầu và phải được nhập vào cơ sở tiếp theo. Hãy chuyển sang điểm 2° của thuật toán.

2°. Xác định một cột bắt nguồn từ một cơ sở. Viết lại cột đầu một tôi từ cái bàn T 1 đến bảng hiện tại T 2 (q) . Theo công thức một tôi(β ( q)) = Δ -1 (β ( q))một tôiđiền vào cột tương ứng trong bảng T 2 (q) . Có hai lựa chọn:

2". Dành cho mọi người TôiО 1: thư(β ( q))<0. Người ta kết luận rằng tính không giới hạn của hàm mục tiêu và quá trình tính toán kết thúc.

2". Có ít nhất một chỉ mục TôiО 1: tôi, mà tôi, tôi(β ( q))>0. Theo quy tắc (1.27), vị trí được xác định r và số N r(β ( q)) cho một cột xuất phát từ cơ sở. Hãy chuyển sang điểm 3° của thuật toán.

3°. Tính toán lại tương ứng với cơ sở mới của các phần tử cột b Và ma trậnΔ -1. Chuyển sang cơ sở mới β ( q+1) , thu được bằng cách giới thiệu β ( q) cột một tôi và xuất ra một cột từ nó một r, được thực hiện theo các công thức tương tự như các công thức (1.28)-(1.31). Họ trông giống như:

Chúng tôi đặt số lần lặp hiện tại q: =q+l và đi đến điểm đầu tiên của thuật toán.

Tóm lại, chúng tôi nhấn mạnh rằng, do những ưu điểm trên nên phương pháp đơn giản cải tiến mới thực sự được sử dụng trong phần mềm, được thiết kế để giải quyết vấn đề kinh điển lập trình tuyến tính.

1.5.2. Ví dụ quyết định PPP phương pháp đơn giản sửa đổi. Chúng ta hãy trình bày lời giải của bài toán (1.34)-(1.35) đã xem xét trước đó, dựa trên việc sử dụng quy trình của phương pháp đơn hình sửa đổi. Bằng cách tương tự với phần 1.4.3, nó bắt đầu bằng việc lựa chọn cơ sở ban đầu hiển nhiên được hình thành bởi các cột (5,2,3). Với nó, Δ -1 (β ( q)) Và b(β ( q)), do đó hãy điền vào các bảng ban đầu T 1 và T 2(1) không khó.

Trong lần lặp đầu tiên chúng ta viết lại dòng số 0

từ T 2 (1) trong T 1 và nhân nó với ma trận MỘT, chúng ta nhận được một dòng xếp hạng

Bởi vì Một 0 (β (1)) chứa các phần tử âm thì ta kết luận rằng phương án tương ứng với cơ sở β (1) là không tối ưu và chọn ước lượng âm nhỏ nhất (-88), ta thu được số cột được nhập vào Điều cơ bản, tôi= 4.

Viết lại cột

từ cái bàn T 1 trong T 2 (1) và tính lại tọa độ của nó so với cơ sở hiện tại, tức là nhân ma trận Δ -1 (β ( q)), nằm trong bảng T 2 (1) ở bên trái, trên MỘT 4 .

Sau khi điền vào bảng T 2 (1) Với số liệu trên cột được nhập vào cơ sở mới, có thể tiến hành xác định số cột đầu ra. Quy trình này được thực hiện hoàn toàn tương tự với phương pháp đơn giản thông thường. Xét mối quan hệ của các phần tử tôi(β(1)) và tôi, tôi(β (1)) cho ( TôiО1: m| tôi, tôi(β (1))>0) và sau khi xác định mức tối thiểu của chúng, chúng ta thấy rằng r= 2. Do đó, cột có số N 2 (β ( q)) = 2 phải được suy ra từ cơ sở. Vì vậy, chúng ta có được một cơ sở có thể chấp nhận được khác cho vấn đề với N(β (2)) = (5, 4, 3). Yếu tố Một 2.3(β(1)) dẫn đầu (khoanh tròn). Áp dụng công thức (1.43)-(1.46), ta chuyển sang bảng đơn tương ứng với lần lặp thứ hai T 2 (2) và đặt chỉ mục của lần lặp hiện tại q = 2.

Lặp lại các bước tương tự (có thể dễ dàng theo dõi chúng từ các bảng được đưa ra ở đây) T 2 (2) và T 2(3), ở lần lặp thứ ba, ta thu được phương án tối ưu của bài toán và giá trị tối ưu của hàm mục tiêu được trích từ cột thứ hai của bảng T 2 (3) . Dễ dàng nhận thấy rằng trong quá trình giải chúng ta đã “trải qua” trình tự các phương án cơ bản được chấp nhận tương tự như đã gặp ở phần 1.4.3.

Hãy giải thích các phép tính a tôi , j ¢ sử dụng “quy tắc hình chữ nhật”. Cần phải lấy yếu tố kích hoạt ak, s và kết nối nó trong đầu với hệ số có giá trị mới mà bạn muốn tìm. Đường này phải được coi là đường chéo chính, trên đó có một hình chữ nhật, các cạnh là hàng và cột. Bạn cần vẽ một đường chéo phụ trong hình chữ nhật, khi đó giá trị của hệ số mới sẽ bằng giá trị ban đầu của nó, từ đó tích của các phần tử nằm trên đường chéo phụ chia cho phần tử phân giải sẽ bị trừ đi. Hãy để chúng tôi giải thích những hành động này trong sơ đồ (Hình 1.9). Trước khi điền vào bảng đơn, các phương trình ban đầu cần được biểu diễn dưới dạng (1.21).

	một k,j
			một tôi, j

Chúng ta hãy xem bản chất của các phép biến đổi của phương pháp đơn hình bằng ví dụ 1.4. Hãy nhớ lại các bất đẳng thức ràng buộc và hàm mục tiêu từ ví dụ này và tìm tối đa hàm mục tiêu sử dụng phương pháp trên:

F = 908X 1 + 676X 2 ® tối đa.

X 1 + X 2 14,

X 2 10,

10X1 + 8X2 120,

7X1 + 5X2 70,

4X 1 + 2X 2 28,

.

Hãy chuyển nó thành dạng chuẩn bằng cách giới thiệu các biến bổ sung Xj 0, và biến bất đẳng thức thành đẳng thức. Cần lưu ý rằng nếu có dấu “” trong bất đẳng thức, thì với biến tự do họ viết “-”, nếu không thì - “+”:

X 1 + X 2 = 14 - X 3,

X 2 = 10 - X 4,

10X1 + 8X2 = 120 - X 5,

7X 1 + 5 X 2 = 70 - X 6,

4X 1 + 2X 2 = 28 - X 7.

Để bắt đầu quy trình sử dụng phương pháp đơn hình, trước tiên bạn cần tìm nghiệm tham chiếu từ tập nghiệm cơ bản của hệ phương trình thu được. Khi tính đến điều này, có ba giai đoạn trong việc giải quyết vấn đề bằng phương pháp đơn hình:

Tìm nghiệm cơ bản ban đầu và lập bảng đơn ban đầu;

Xác định một giải pháp có thể chấp nhận được;

Xác định giải pháp tối ưu.

giai đoạn 1

Ban đầu giải pháp cơ bản hệ thống chúng tôi tìm thấy bằng cách giả sử các biến tự do X 1 Và X 2 .

Sau đó X 3 = 14 - X 1 - X 2,

X 4 = 10 - X 2,

X 5 =120 - 10X 1 - 8X 2,

X 6 = 70 - 10X 1 - 5X 2,

X 7 = 28 - 4X 1 - 2X 2,

F = 908X 1 + 676X 2 = 0.

Chúng ta hãy biến đổi các phương trình này thành nhìn bình thường:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0X 1 + X 2),

X 5 =120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908X1 + 676X2.

Ta viết hệ phương trình thu được dưới dạng bảng đơn ban đầu (Bảng 1.9). Trong bảng 1.9 không có thành viên miễn phí tiêu cực. Do đó, chúng ta đã thu được một nghiệm hỗ trợ (có thể chấp nhận được), vì một nghiệm có thể chấp nhận được là bất kỳ nghiệm không âm nào (trong đó > 0 ), nhưng nó không tối ưu.

Rõ ràng, nếu với tất cả các ẩn số trong hàm mục tiêu F Nếu các hệ số dương thì sẽ đạt giá trị tối đa F. Nó theo sau từ này dấu hiệu tối ưu của một giải pháp chấp nhận được: V. F- hàng của bảng đơn không được có hệ số âm.

Bảng 1.9

Biến cơ bản Xb	Thành viên miễn phí	Biến miễn phí
X 1	X 2
X 3
X4
X 5
X 6
X7
F		- 908	- 676

giai đoạn 2

Chúng ta hãy nhớ lại rằng hoạt động chính của phương pháp đơn giản về cơ bản là một số biến cơ bản được thay thế bằng một biến tự do. . Trong trường hợp này, thao tác thay thế được thực hiện với các điều kiện sau:

Giá trị hàm mục tiêu F giải pháp tham chiếu mới (được chấp nhận) phải lớn hơn giải pháp trước đó;

Giải pháp mới của hệ thống cũng phải mang tính tham khảo (có thể chấp nhận được).

Trong ví dụ của chúng tôi, điều kiện đầu tiên được thỏa mãn nếu phần tử kích hoạt là dương và được chọn trong cột hệ số âm F-dòng.

Điều kiện thứ hai được thỏa mãn nếu phần tử phân giải được tìm thấy ở dạng tỷ lệ dương tối thiểu của các phần tử của cột thành viên tự do với các phần tử tương ứng của cột phân giải.

Theo quy tắc đã nêu ở trên, để tìm ra lời giải có thể chấp nhận được, các biến cơ bản và biến tự do được hoán đổi cho nhau. Để thực hiện việc này, hãy tìm phần tử phân giải (nó được đóng khung trong Bảng 1.9). Trong trường hợp của chúng tôi, cột cho phép sẽ giống như X 1 , Vì thế X 2. Chia các biến tự do cho các giá trị tương ứng của chúng X 1 Và X 2 (trừ dòng F), ta tìm giá trị dương nhỏ nhất. Điều quan trọng cần lưu ý là đối với cột X 1 :

Điều quan trọng cần lưu ý là đối với cột X 2:

Tỷ lệ nhỏ nhất 28/4 xác định hàng phân giải và cột phân giải, giao điểm của cột phân giải và hàng phân giải là phần tử phân giải một lời cảm ơn= 4. Trong bảng. 1.9 chúng ta đánh dấu cột cho phép và hàng cho phép bằng mũi tên (®). Đã xác định một lời cảm ơn, xây dựng bảng sau, trong đó các biến có trong hàng và cột của phần tử phân giải được hoán đổi cho nhau ᴛ.ᴇ. chuyển đổi các biến cơ bản thành biến miễn phí và biến miễn phí thành biến cơ bản.

Trong ví dụ của chúng tôi, chúng tôi trao đổi các biến X 7 Và X 1 , ghi chú trong bảng 1,9 mũi tên. Các hệ số của bảng mới. 1,10 được tìm thấy từ các hệ số của bảng cũ. 1.9, sử dụng các biểu thức cho trong bảng. 1.8 và “quy tắc hình chữ nhật”. Trong bảng 1.10 một lần nữa chúng ta không có giải pháp tối ưu.

Bảng 1.10

Biến cơ bản Xb

Thành viên miễn phí B

Biến miễn phí

X7

X 2

X 3

- 1/4

1/2

X4

X 5

-5/2

X 6

-7/4

3/2

X 1

1/4

1/2

F

-222

Theo các quy tắc được mô tả ở trên trong bảng. 1.10, chúng tôi tìm phần tử phân giải 1 và xây dựng một bảng mới. 1.11 bằng cách thay cơ sở ( X4 Và X 2). Chúng tôi đặc biệt nhấn mạnh rằng để tìm phần tử phân giải chúng ta phải chọn giá trị dương nhỏ nhất, ᴛ.ᴇ. Chúng tôi không xem xét mối quan hệ tiêu cực của các số hạng tự do với các hệ số của cột độ phân giải.

giai đoạn 3

Hãy kiểm tra xem giải pháp tìm được có tối ưu hay không và trong ví dụ của chúng tôi - tối đa. Để làm điều này, chúng ta sẽ phân tích hàm mục tiêu F: F = 8576 + 227 X 7 + 222 X 4.

Hàm mục tiêu không chứa các hệ số âm và có giá trị cao nhất Trong bảng cuối cùng, chúng tôi đã thu được giải pháp tối ưu:

X 3 = 2; X2 = 10; X 5 = 20; X6 = 6; X 1 = 2; X7 = X4 = 0;

F tối đa = 8576.

Xin lưu ý rằng kết quả của việc giải phương pháp đơn hình và phương pháp đồ thị là như nhau.

Theo đúng trình tự đã xét, thuật toán phương pháp đơn hình phải có các khối sau:

1. Tìm lời giải cơ bản (tham khảo) ban đầu và lập bảng ban đầu.

2. Tìm phần tử giải quyết một lời cảm ơn(tìm số hạng tự do phủ định - tôi < 0 и минимального отношенияb i / a ij; Nếu không có hệ số âm trong hàng số hạng tự do âm thì bài toán không giải được).

3. Tính toán lại bảng mới theo công thức ở bảng. 1.8.

4. Kiểm tra sự có mặt của số hạng tự do âm. Nếu nó tồn tại thì chuyển sang bước 2. Việc không có số hạng tự do phủ định có nghĩa là đã thu được nghiệm tham chiếu (có thể chấp nhận được).

5. Tương tự như bước 2 - 4, bảng được tính toán lại khi tìm phương án tối ưu.

Giải bài toán LP bằng phương pháp đơn hình dạng ma trận

Bắt buộc phải giảm thiểu ,

dưới những hạn chế

Tại " x³ 0.

Hãy giới thiệu các vectơ:

C= (C 1 , ... , C n) - vectơ ước lượng,

X= (X 1 , ... , X n) - vectơ biến,

b= (B 1 , ... , B m) - vectơ giới hạn

và ma trận

MỘT=

size (mn) - ma trận các hệ số ràng buộc.

Khi đó bài toán LP sẽ có cách hiểu như sau:

giảm thiểu F=CX

trong những điều kiện AX = b, X 0.

Vấn đề này có thể được viết dưới dạng ma trận:

Hãy giới thiệu ký hiệu:

Một * = - đây là ma trận MỘT* kích thước (m+1)(n+1).

Theo phương pháp trên, phần tử phân giải được tìm thấy một lời cảm ơn.

Bước tiếp theo phương pháp đơn giản - một thủ tục loại bỏ Gaussian cho phép bạn thực hiện tất cả các hệ số trong S- cột m, ngoại trừ một lời cảm ơn, số không, một lời cảm ơn- bằng một.

Điều quan trọng cần lưu ý là đối với phương pháp đơn hình ở dạng ma trận, việc lặp lại phương pháp đơn hình tương đương với việc nhân phương trình ma trận bên trái với biểu thức sau Ma trận vuông:

(1.23)

, Ở đâu k 0; S 0.

Nếu tất cả các cột của ma trận MỘT chia thành cơ bản B và không cơ bản N, thì bài toán LP có thể được viết như sau:

,

Ở đâu Cb Và C N- thành phần vectơ tương ứng C, Xb, XN- các biến cơ bản và không cơ bản.

Để chọn các biến cơ sở ban đầu x b bạn nên nhân phương trình bên trái với ma trận:

Ở đâu R= C b B -1 .

Kết quả là chúng tôi nhận được

,

Ở đâu TÔI- ma trận đơn vị.

Theo đó, các ước tính tương đối cho các biến không cơ bản

c j = c j - C b B -1 a j = c j - Ra j .

Cơ sở sẽ được chấp nhận nếu số hạng tự do của các biến cơ sở không âm, ᴛ.ᴇ. B -1 b 0.

Nếu như cj³ 0 với , thì cơ sở là giải pháp tối ưu nhiệm vụ. Vectơ được gọi là vectơ giá hiện tại. Mỗi hàng được nhân với một vectơ R và được trừ khỏi đường hệ số chi phí để loại bỏ hệ số chi phí cho các biến cơ bản.

Nếu vấn đề LP không được chỉ định trong hình thức kinh điển, ᴛ.ᴇ.

giảm thiểu F=CX

trong những điều kiện AX b , X 0,

sau đó, đưa vào các biến yếu, chúng có thể được viết dưới dạng

Cách khử hàng của một ma trận tương đương với việc nhân ma trận đó từ bên trái với B-1, Ở đâu B- cơ sở ma trận con MỘT, Sau đó

,

ᴛ.ᴇ. ma trận thu được thay cho ma trận danh tính TÔI, sẽ là ma trận nghịch đảo cho cơ sở hiện tại. Điểm tương đối nằm phía trên ma trận nhận dạng sẽ là

,

vì là vectơ đơn vị.

Bởi vì F= Cb B -1 b = Rb, giá trị hiện tại của hàm mục tiêu bằng tích của vectơ giá hiện tại của ma trận MỘT tới vectơ ban đầu b.

Ví dụ.
Đăng trên ref.rf
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® phút

dưới những hạn chế

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,

3X 2 + 3X 4 + 6X 5 = 9,

.

Vì ví dụ này ma trận MỘT* sẽ trông giống như

.

Cho phép X 1 Và X 2- các biến cơ bản

Ma trận B giống như

.

Khi đó ma trận nghịch đảo B-1 Nó có lượt xem tiếp theo

.

Hãy để chúng tôi nhắc nhở bạn rằng , trong đó ma trận liên hợp gồm các phần tử đại số bổ sung b ikđịnh thức của ma trận B.

Định thức bằng:

= .

Do đó, ma trận B không đặc biệt.

phép cộng đại số các phần tử của định thức có ý nghĩa như sau:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; những thứ kia . .

Nhân với , ta tìm được ma trận nghịch đảo:

.

Vectơ của giá hiện tại sẽ là

R = C b B -1 = = .

Hãy để chúng tôi nhắc nhở bạn rằng Cb- thành phần vectơ cơ sở C:

Sau đó = .

Để chọn cơ sở ban đầu bạn cần một ma trận MỘT* nhân trái với ma trận

=

.

Phần tử phân giải nằm trong một hình vuông.

Việc lặp lại phương pháp đơn hình tương đương với bảng kết quả được nhân ở bên trái với ma trận sau:

.

Ma trận này thu được từ ma trận (1.23)

Đây aks = 2;

một 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a23 = 0;

a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; 33 = 1.

Sau đó chúng tôi có

=

(1.24)

Phần tử phân giải được đặt trong một hình vuông.

Lần lặp tiếp theo của phương pháp đơn hình tương đương với phép nhân trái với ma trận

.

=

.

Kể từ đây, Fmin =11; X4=7/3; X 5=1/3; X 1 = X 2 = X 3=0.

Phương pháp đơn giản sửa đổi (MSM) khác với phương pháp đơn giản thông thường (CM) bởi vì trong CM Tất cả các phần tử của bảng đơn được tính toán lại ở mỗi lần lặp và khi lấy được bảng tiếp theo, tất cả các bảng trước đó, kể cả bảng gốc, sẽ không được lưu. TRONG MSM bảng gốc được lưu và tại mỗi lần lặp lại, thông tin sau được xác định: một hàng ước tính tương đối Cđược nhập vào cơ sở và giá trị hiện tại của vectơ bên phải của các ràng buộc. Để xác định tất cả các thành phần của bảng sau j- lần lặp thứ CM, chỉ cần biết ma trận là đủ B-1, tương ứng với bảng này, ma trận gốc và chỉ số của các biến cơ bản hiện tại. Khi đó vectơ hiện tại R = C b B -1(các chỉ số của các biến cơ bản hiện tại xác định phần tử nào của vectơ ước lượng từ bảng nguồn được đưa vào vectơ C b); =B -1b, Ở đâu bđược lấy từ bảng gốc và bất kỳ cột nào của bảng mới = B-1Một j , Ở đâu Một j - cột của bảng nguồn.

Hãy để bảng nguồn bây giờ được đưa ra B-1, tương ứng với bảng Tôi lần lặp thứ. Để có được ma trận B-1, tương ứng (i+1)- lần lặp thứ, bạn cần xác định một cột không cơ sở Tôi bảng thứ cần được nhập vào cơ sở. Từ CM theo đó nó phải được đưa vào cơ sở nếu Cj<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить Cj Vì Tôi bảng thứ, hãy chọn trong số đó<0, а затем вычислить

Một S = B-1 và = B -1b (= Cj - Ra j ).

Sau khi tìm được phần tử phân giải và sử dụng các phần tử của vectơ và , ta tìm được ma trận B-1 cho bảng sau.

Ví dụ. Sử dụng phương pháp đơn giản đã sửa đổi để giảm thiểu

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® phút

với những hạn chế:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

Chọn làm biến cơ bản X 1 Và X 2, chúng tôi nhận được nhiệm vụ sau: F = 43 - 9/2X 3 - 12X 4 - 12X 5

Cơ quan Giáo dục Liên bang

Cơ sở giáo dục nhà nước về giáo dục chuyên nghiệp cao hơn

Đại học Kỹ thuật bang Perm

Chi nhánh Lysvensky

Khoa Kinh tế

Khóa học

trong bộ môn “Phân tích hệ thống và nghiên cứu vận hành”

về chủ đề: “Phương pháp đơn giản trong hình thức trình bày”

Hoàn thành bởi sinh viên nhóm VIVT-06-1:

Startseva N. S.

Giáo viên kiểm tra:

Mukhametyanov I.T.

Lysva 2010

Giới thiệu. 3

Lập trình toán học. 5

Phương pháp đồ họa. 6

Phương pháp đơn giản dạng bảng. 6

Phương pháp cơ sở nhân tạo. 7

Phương pháp đơn giản sửa đổi. 7

Phương pháp đơn giản kép. 7

Tổng quan về bài toán quy hoạch tuyến tính. 9

Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. mười một

Quy trình tính toán của phương pháp đơn hình. mười một

Định lý 1: 13

Định lý 2: 14

Định lý 3: 15

Định lý 4: 15

Định lý 5: 15

Chuyển sang một kế hoạch tham chiếu mới. 15

Nhiệm vụ kép. 17

Định lý 1 (định lý nhị nguyên thứ nhất) 18

Định lý 2 (định lý nhị nguyên thứ hai) 18

Phần kết luận. 20

Lời giải tối ưu cho bài toán quy hoạch tuyến tính nằm trong số các lời giải tham khảo. Ý tưởng của phương pháp đơn hình là, theo một quy tắc nhất định, các giải pháp tham chiếu được sắp xếp cho đến khi tìm thấy giải pháp tối ưu trong số đó. Về cơ bản, bằng cách sắp xếp qua các giải pháp tham chiếu, chúng ta đang sắp xếp các biến cơ bản khác nhau, nghĩa là , ở bước tiếp theo, một số biến được chuyển từ số biến cơ bản sang số biến cơ bản.

7x 1 +5x 2 → tối đa

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 sơ đồ tham chiếu ban đầu

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

Ở mức độ trực quan, rõ ràng là việc tăng x 1 là điều đương nhiên, vì hệ số của nó lớn hơn của x 2. Để x 2 = 0, ta có thể tăng cho đến khi x 3 , x 4 , x 5 , x 6 không âm.

x 1 =phút(19/2;13/2;∞;18/3)=6

Điều này có nghĩa là khi x 1 = 6, x 6 = 0, tức là x 1 là số lượng cái cơ bản và x 6 là số lượng cái tự do.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

Với một kế hoạch tham chiếu nhất định (6;0;7;1;15;0) x 2, chuyển từ các biến miễn phí sang các biến cơ bản:

x 2 =phút(∞;7/3;1/11;15/3)=1

Thể hiện x 2 đến x 4

x 2 =1+2/3 x 6 - x 4

Chúng tôi biểu thị các biến chưa biết và hàm mục tiêu theo các biến tự do:

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 là dương nên có thể tăng lên

x 6 =phút(18;∞;3;6)=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

Trong hàm mục tiêu, tất cả các hệ số của các biến đều âm, giá trị của hàm không thể tăng lên, ta biến đổi tương tự các biến còn lại, tìm phương án tham chiếu, từ đó xác định x 1, x 2.

1. Giao của các tập đóng, tập hợp các giới hạn không tầm thường.

2. Tập nghiệm của hệ bất đẳng thức và phương trình tuyến tính không chặt chẽ là tập đóng.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 +y 1, x 2 +y 2,… x n +y n)

Tọa độ tuyến tính X 1 ,X 2 ,…X n được gọi là điểm P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Đặt P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 for i= 1,…k n åR i =1, 1≤ i ≤k tổ hợp tuyến tính lồi của các điểm x 1 ,x 2,…x n . Nếu k=2 thì tập hợp này được gọi là một đoạn. X 1,X 2 – các đầu của đoạn. Điểm góc của một tập đóng là một điểm không phải là tổ hợp tuyến tính không tầm thường của các điểm trong tập hợp (điểm góc).

Tính không tầm thường có nghĩa là ít nhất một trong các λ khác 0 hoặc 1.

Bất kỳ giải pháp tham chiếu nào cho bài toán quy hoạch tuyến tính đều là điểm góc của vùng các giải pháp khả thi.

Nếu một bài toán quy hoạch tuyến tính có nghiệm duy nhất thì nó nằm trong số các điểm góc của ODP. Và nếu có nhiều hơn một nghiệm thì trong số các nghiệm đó có một số nghiệm góc, sao cho tập hợp tất cả các nghiệm là tổ hợp tuyến tính lồi của chúng.

Phương pháp đơn giản trước tiên bao gồm việc tìm ra một giải pháp tham chiếu nhất định cho vấn đề (phương án tham chiếu ban đầu), sau đó, chuyển từ phương án tham chiếu này sang phương án tham chiếu khác một cách có mục đích, tìm kiếm phương án tối ưu. Nếu có một vài trong số chúng, thì tất cả các góc đều được tìm thấy và tập hợp các giải pháp được biểu diễn dưới dạng tổ hợp tuyến tính của chúng.

Chuyển sang kế hoạch tham chiếu mới

F 1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 có thể được chứng minh, trong đó υ k là giá trị nhỏ nhất được xem xét ở trên, được xác định bằng cách đưa biến thứ k vào cơ sở, và Δ k =åс j x j ( 1) -С k, trong đó n ≤ j 1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) là ước lượng của biến thứ k , vậy nếu giải được bài toán cực đại thì giá trị ΔF 2 phải dương, Δk phải âm. Khi giải các bài toán tối thiểu thì ΔF 2 là âm, Δ k là dương. Các giá trị này được tính toán và nếu trong số ΔF 2 tất cả các giá trị đều không dương thì khi giải các bài toán tối thiểu thì ngược lại. Nếu khi giải tìm giá trị cực đại, có một số giá trị dương trong số ΔF 2, thì chúng ta đưa vào cơ sở vectơ mà tại đó giá trị này đạt giá trị cực đại và nếu bài toán được giải ở mức tối thiểu và trong số ΔF 2 thì có một số giá trị âm những cái đó, thì vectơ có giá trị nhỏ nhất ΔF 2 được đưa vào cơ sở, nghĩa là có giá trị tuyệt đối lớn nhất. Khi những điều kiện này được đáp ứng, sự thay đổi lớn nhất có thể có về giá trị của hàm sẽ được đảm bảo.

Lời giải của bài toán sẽ là duy nhất nếu với bất kỳ vectơ x k nào không có trong cơ sở, ước tính Δ k ≠0, nếu ít nhất một trong các vectơ này Δ k = 0 thì lời giải không phải là duy nhất, để tìm lời giải khác chúng ta chuyển sang một phương án tham chiếu khác, bao gồm cả cơ sở x k, trong đó Δ k = 0. Việc tìm kiếm qua tất cả các giải pháp hỗ trợ như vậy sẽ tạo thành một tổ hợp tuyến tính, đây sẽ là giải pháp cho vấn đề.

Nếu với bất kỳ Δ k nào đó, các hệ số của biến x k ≤ 0 mâu thuẫn với điều kiện tối ưu thì hệ hạn chế không bị giới hạn, tức là không có phương án tối ưu.

Vấn đề kép

Bài toán kép (DP) là một bài toán quy hoạch tuyến tính phụ được xây dựng bằng cách sử dụng các quy tắc nhất định trực tiếp từ các điều kiện của bài toán trực tiếp. Mối quan tâm đến việc xác định lời giải tối ưu cho một bài toán trực tiếp bằng cách giải bài toán kép của nó là do thực tế là các phép tính khi giải một DP có thể trở nên ít phức tạp hơn so với khi giải một bài toán trực tiếp (DP). Độ phức tạp của các phép tính khi giải LLP phụ thuộc nhiều vào số lượng ràng buộc hơn là vào số lượng biến. Để đi đến PD, điều cần thiết là PD phải được viết dưới dạng chính tắc chuẩn. Khi trình bày PP ở dạng chuẩn, các biến xj cũng bao gồm các biến dư thừa và biến dư.

Vấn đề kép có:

1. m biến tương ứng với số ràng buộc của bài toán trực tiếp;

2. n ràng buộc tương ứng với số biến của bài toán trực tiếp.

Bài toán kép thu được bằng cách biến đổi cấu trúc đối xứng các điều kiện của bài toán trực tiếp theo các quy tắc sau:

· Mỗi ràng buộc b i PD tương ứng với một biến y i PD;

· Mỗi biến x j PD tương ứng với một ràng buộc C j PD;

· Các hệ số x j trong ràng buộc PD trở thành các hệ số bên trái của ràng buộc PD tương ứng;

· Các hệ số Cj cho x j trong hàm mục tiêu của PD trở thành hằng số ở vế phải của ràng buộc PD;

· Các hằng số ràng buộc b i PD trở thành hệ số của hàm đích PD.

Hãy xem xét hai vấn đề sau:

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 +b 2 x 2 +... +b n x n →phút

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

Khóa học này đặt nền móng cho các phương pháp toán học để giải các bài toán quy hoạch tuyến tính. Vì vậy, người ta chú ý nhiều hơn đến các phần sau:

1. Cơ sở của các phương pháp toán học và ứng dụng của chúng;

2. Giải bài toán bằng phương pháp đơn hình.

3. Phương pháp đơn hình cải tiến

Loại phương pháp đơn hình này dựa trên các đặc điểm của đại số tuyến tính cho phép người ta làm việc với một phần của ma trận ràng buộc khi giải một bài toán. Đôi khi phương pháp này được gọi là phương pháp ma trận nghịch đảo.

Trong quá trình hoạt động của thuật toán, ma trận ràng buộc được đảo ngược tự phát theo từng phần tương ứng với các vectơ cơ sở hiện tại. Khả năng này làm cho việc thực hiện các phép tính của máy trở nên rất hấp dẫn do tiết kiệm bộ nhớ cho các biến trung gian và giảm đáng kể thời gian tính toán. Khả năng này tốt cho các tình huống trong đó số lượng biến n vượt quá đáng kể số lượng ràng buộc m.

Nhìn chung, phương pháp này phản ánh những đặc điểm truyền thống của cách tiếp cận tổng quát để giải các bài toán quy hoạch tuyến tính, bao gồm chuẩn hóa các điều kiện bài toán, tính sai phân đơn giản, xác minh các điều kiện tối ưu, ra quyết định trên cơ sở hiệu chỉnh và loại bỏ Jordan-Gauss. Các tính năng bao gồm sự hiện diện của hai bảng - bảng chính và bảng phụ, thứ tự điền chúng và một số tính đặc hiệu của các công thức tính toán.

Biết được phương án tối ưu cho bài toán này, dựa vào các quan hệ ta thu được phương án tối ưu cho bài toán ban đầu.

Như vậy, quá trình tìm lời giải cho bài toán quy hoạch phi tuyến bao gồm các bước sau:

1. Bài toán ban đầu được rút gọn thành bài toán quy hoạch tuyến tính.

2. Tìm lời giải cho bài toán tuyến tính

Sử dụng các mối quan hệ, phương án tối ưu cho bài toán ban đầu được xác định và tìm được giá trị lớn nhất của hàm mục tiêu của bài toán phi tuyến.

Giai đoạn 1: Nhận bài tập cho môn học

1. Toàn bộ dữ liệu số liên quan đến quá trình sản xuất, kinh tế đề xuất được lấy dựa trên mã sáu chữ số:

Dưới mỗi số các chữ cái a, b, c, d, e, f được viết dưới dạng sau:

từ hàng cuối cùng của bảng nhiệm vụ riêng lẻ, chúng ta tìm thấy các cột tương ứng với các chữ cái a, b, c, d, e, f. Khi đó dữ liệu số cần thiết để hoàn thành bài tập khóa học này sẽ là dữ liệu nằm trong a - cột đó ở dòng 9, b - cột đó ở dòng 5, c - cột đó ở dòng 5, d - cột đó ở dòng 8, e - cột đó ở dòng 7 và f – cột đó ở dòng 2.

Theo bảng nhiệm vụ ban đầu cho bất kỳ biến thể nào của nhiệm vụ trong cột a, người thực thi sẽ nhận được biến thể của nhiệm vụ đang được thực hiện. Trong trường hợp của tôi, số 9 tương ứng với lựa chọn 9.

Một nhà máy nhất định sản xuất ba loại sản phẩm và tiêu thụ hai loại tài nguyên. Hàm sản xuất của từng loại sản phẩm tại doanh nghiệp được mô tả bằng các đẳng thức:

trong đó C i và là các giá trị không đổi, i = 1, 2, 3;

X 1 – nguồn lao động tính bằng ngày công;

X 2 – nguồn lực tiền tệ và vật chất, tính bằng tenge;

Y i là sản phẩm thu được

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Tìm tất cả các nghiệm cơ bản không âm và xác định phương án tối ưu F = y 1 + y 2 + y 3.

Được biết, để sản xuất ra j – loại sản phẩm đó, một đơn vị ij của i – tài nguyên đó đã được sử dụng. Các chi phí này được trình bày trong bảng 3.9.1. – 3.9.10

Dữ liệu số tiếp theo chỉ được lấy từ bảng dữ liệu nguồn của tùy chọn tác vụ đã chọn, tức là. từ bảng số 3.9.11.

2. Theo cột bảng số 3.9.11 cho dòng 8, bảng chi phí ban đầu của các đơn vị tài nguyên sẽ là bảng số 3.9.4 tức là. bảng sau:

Tài nguyên sản phẩm
TÔI	8	4	6
II	160	240	200

3. Sử dụng cột c – ở dòng 3 ta tìm được 1 =6, α 1 =0,6

4. Sử dụng cột d – dòng 5 ta xác định được 2 =5, α 2 =0,5

5. Sử dụng cột e – dòng 4, chúng ta thiết lập được c 3 =8, α 3 =0,4.

6. Và cuối cùng, sử dụng cột f - ở dòng 1 ta tìm được T người ngày = 1000, P tenge = 280000

Đối với sản xuất có nguồn lao động T ngày công và nguồn tiền tệ P tenge.

Cần phải tìm ra phương án sản xuất tối ưu sao cho sản phẩm đầu ra là lớn nhất.

Giai đoạn thứ hai là xây dựng mô hình toán học của bài toán

1. Dựa trên dữ liệu ban đầu thu được ở giai đoạn đầu tiên và mô tả quy trình sản xuất nhất định, bảng sau được tổng hợp:

Tài nguyên sản phẩm
TÔI	8	4	6	1000
II	160	240	200	280000

Gọi X 1 là tài nguyên thuộc loại thứ nhất.

Gọi X 2 là tài nguyên loại II.

2. Chuyển sang các điều kiện của bài toán, chúng ta xác định tất cả các hạn chế có thể có, kết hợp chúng thành một hệ thống các hạn chế.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 280000

Như vậy, chúng ta có một bài toán quy hoạch phi tuyến. Những bài toán như vậy được gọi là bài toán quy hoạch phi tuyến.

Các bài toán quy hoạch phi tuyến được giải bằng cách quy chúng về các bài toán quy hoạch tuyến tính.

Để giải bài toán quy hoạch tuyến tính người ta sử dụng phương pháp đơn hình.

Giai đoạn thứ ba là lựa chọn phương pháp giải bài toán kết quả

1. Để giải các bài toán quy hoạch tuyến tính bằng phương pháp đơn hình, bài toán được rút gọn về dạng chính tắc:

8X 1 + 4X 2 + 6X 3 + X 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Các phương pháp đang được phát triển để tìm các giá trị cực trị của hàm mục tiêu trong tập hợp các giá trị có thể có của nó được xác định bởi các ràng buộc. Sự hiện diện của các hạn chế làm cho các bài toán lập trình toán học về cơ bản khác với các bài toán phân tích cổ điển về tìm giá trị cực trị của hàm. Các phương pháp giải tích toán học để tìm cực trị của hàm số trong bài toán...

Việc tìm điểm Kuhn-Tucker cung cấp lời giải tối ưu cho bài toán quy hoạch phi tuyến. Định lý 2 cũng có thể được sử dụng để chứng minh tính tối ưu của một giải pháp cho bài toán quy hoạch phi tuyến. Để minh họa, hãy xem lại ví dụ: Tối thiểu hóa dưới ràng buộc Sử dụng Định lý 2, chúng ta chứng minh rằng nghiệm là tối ưu. Chúng tôi có Vì vậy...

Các tia phát ra từ một điểm được gọi là hình nón lồi đa diện có đỉnh tại một điểm cho trước. 1.4 Cơ sở toán học để giải các bài toán quy hoạch tuyến tính bằng đồ họa 1.4.1 Bộ máy toán học Để hiểu sâu hơn mọi thứ, sẽ rất hữu ích nếu biết và hình dung cách giải thích hình học của các bài toán quy hoạch tuyến tính, có thể đưa ra cho các trường hợp n = 2 và n = ...

Nếu chúng ta đặt các biến cơ bản hiện tại vào một bảng đơn giản bằng Ai,0 và các biến tự do bằng 0 thì sẽ thu được giải pháp tối ưu. Thực tiễn sử dụng phương pháp đơn hình cho thấy số lần lặp cần thiết để giải một bài toán quy hoạch tuyến tính thường dao động từ 2m đến 3m, mặc dù đối với một số bài toán được xây dựng đặc biệt, các phép tính theo quy tắc của phương pháp đơn hình trở thành trực tiếp...