Phương pháp đơn hình sửa đổi để giải các bài toán quy hoạch tuyến tính

PHƯƠNG PHÁP ĐƠN GIẢN SỬA ĐỔIPhương pháp đơn giản không phải là phương pháp hiệu quả nhất
thủ tục máy tính, vì nó tính toán và
lưu trữ thông tin không cần thiết cho hiện tại
lặp đi lặp lại và có thể không được sử dụng cho
đưa ra quyết định trong các lần lặp tiếp theo. Vì
hệ số của các biến không chính trong phương trình
(0), hệ số của các biến chính được giới thiệu
trong các phương trình khác và vế phải của phương trình tại
Mỗi lần lặp chỉ sử dụng cái có liên quan
thông tin. Vì vậy cần có một quy trình
có thể có được thông tin này một cách hiệu quả mà không cần
tính toán và lưu trữ tất cả các hệ số khác
(đây là phương pháp đơn giản đã được sửa đổi).

Nó tính toán và chỉ lưu trữ thông tin
cần thiết cho khoảnh khắc này, và dữ liệu quan trọng
truyền tải dưới dạng nhỏ gọn hơn.
Nó sử dụng các phép toán ma trận, vì vậy
cần phải mô tả bài toán bằng ma trận.
CHỮ HOA, được đánh dấu in đậm
biểu thị ma trận, chữ in hoa,
những người in đậm đại diện
vectơ.
Chữ nghiêng là đại lượng vô hướng, được đánh dấu bằng 0
(0) biểu thị vectơ 0 (các phần tử của nó bằng nhau
không, cả hàng và cột), không (0)
đại diện cho số 0 bình thường. Sử dụng
ma trận dạng chuẩn của mô hình tuyến tính
lập trình có dạng:

Tối đa hóa Z = c x,
dựa theo
A x ≤ b và x ≥ 0,
trong đó c là một vectơ hàng
vectơ cột x, b và 0

A - ma trận
Đối với dạng mở rộng, vectơ cột
biến giả:
Những hạn chế:
I = (m × m ma trận đồng nhất)
0 = (n + m phần tử của vectơ 0)

Tìm giải pháp cơ bản khả thi
Cách tiếp cận chung của phương pháp đơn giản là thu được
trình tự cải thiện các giải pháp OA lên đến
cho đến khi tìm được phương án tối ưu
giải pháp. Một trong những tính năng chính
đơn giản sửa đổi-phương pháp - nó như thế nào
tìm ra giải pháp OD mới sau khi xác định nó
chính (cơ bản) và không cơ bản (không cơ bản)
biến. Với các biến này, kết quả
nghiệm chính – nghiệm của phương trình m
Trong đó n biến không cơ bản từ n + m
yếu tố
được đặt bằng 0.

Loại bỏ n biến này bằng cách đặt chúng về 0,
ta thu được hệ phương trình m với m biến
(biến chính (cơ bản)):
đâu là vectơ của các biến cơ bản:
thu được bằng cách loại trừ không cơ bản (không cơ bản)
biến:

Và ma trận cơ sở
Kết quả thu được bằng cách loại trừ các cột tương ứng với
hệ số của các biến không cơ bản từ .
(Ngoài ra, các phần tử xB và cột B có vị trí khác nhau.
được rồi). Phương pháp đơn giản chỉ giới thiệu cơ bản
các biến sao cho B không suy biến, do đó
ma trận nghịch đảo B-1 sẽ luôn tồn tại.
Để giải B x B = b, cả hai vế đều được nhân với B-1:
B-1 B x B = B-1 b.

cB là một vectơ có các phần tử là hệ số
các hàm mục tiêu (bao gồm các số 0 cho giả
biến) cho các phần tử xB tương ứng.
Hàm mục tiêu của nghiệm cơ bản này là:

Ví dụ:
- Lặp lại 0
Vì thế
Vì thế

10.

- Lặp lại 1
Vì thế
Vì thế

11.

- Lặp lại 2
Vì thế
Vì thế

12. Dạng ma trận của tập phương trình hiện tại

Dạng ma trận cho một tập hợp các phương trình,
xuất hiện trong bảng đơn giản cho bất kỳ lần lặp nào
phương pháp đơn giản ban đầu. Đối với hệ thống nguồn
phương trình, dạng ma trận là:
Các phép tính đại số được thực hiện bằng phương pháp đơn hình (nhân phương trình với một hằng số và cộng
tích của phương trình này với phương trình khác) được biểu thị bằng
dạng ma trận, sau khi nhân cả hai phần
hệ phương trình ban đầu thành hệ phương trình tương ứng
ma trận

13.

14.

Ma trận này sẽ có các phần tử giống như ma trận danh tính
ma trận, ngoại trừ mỗi sản phẩm
đối với một phép toán đại số nhất định sẽ mất
không gian cần thiết để thực hiện thao tác này,
sử dụng phép nhân ma trận. Ngay cả sau loạt phim
các phép toán đại số qua nhiều lần lặp,
chúng ta vẫn có thể kết luận rằng ma trận này
nên dành cho toàn bộ loạt bài, sử dụng những gì chúng ta biết về
bên phải hệ thống mới phương trình. Sau bất kỳ
lần lặp, xB = B-1b và Z = cB B-1b, do đó vế phải
hệ phương trình mới có dạng

15.

Vì chúng ta thực hiện cùng một chuỗi
các phép toán đại số với cả hai vế
tập hợp ban đầu, để nhân bên phải và
ở phía bên trái, chúng tôi sử dụng cùng một ma trận.
Kể từ đây,
Dạng ma trận mong muốn của hệ phương trình
sau bất kỳ lần lặp nào:

16.

Ví dụ: dạng ma trận thu được sau lần lặp 2
cho bài toán nhà máy thủy tinh sử dụng B-1 và cB:

17.

Sử dụng các đại lượng xB = B-1 b và Z = cB B-1 b:

18.

Chỉ nhận B-1 để tính toán
tất cả các số của bảng đơn từ bảng gốc
tham số nhiệm vụ (A, b, cB). Bất kỳ số nào trong số này
có thể được lấy riêng lẻ như
Theo quy định, chỉ phép nhân vectơ được thực hiện
(một hàng trên mỗi cột) thay vì đầy đủ
Phép nhân ma trận. Số cần thiết cho
việc thực hiện các phép lặp của phương pháp đơn giản có thể
nhận khi cần thiết mà không cần chi tiêu
tính toán không cần thiết để có được tất cả các con số.

19. Tổng quan ngắn gọn về phương pháp đơn hình cải tiến

1. Khởi tạo: Như trong phương pháp đơn giản ban đầu.
2. Lặp lại: Bước 1 Xác định cơ bản (chính) đã nhập
biến: Như trong phương pháp đơn giản ban đầu.
Bước 2 Xác định các biến cơ sở đầu ra: Như ban đầu
phương pháp đơn giản, ngoại trừ việc chỉ đếm những gì cần thiết cho
của những con số này [hệ số của các biến cơ bản được giới thiệu trong
mỗi phương trình ngoại trừ phương trình. (0), và sau đó, với mỗi
hệ số dương phần bên phải phương trình này].
Bước 3 Xác định nghiệm OD mới: Lấy B-1 và đặt xB=B-1b.
3. Phân tích tối ưu: Như trong phương pháp đơn giản ban đầu, đối với
ngoại trừ việc chỉ đếm những con số cần thiết cho việc phân tích này,
tức là hệ số của các biến không cơ bản (không cơ bản) trong
Phương trình (0).
Ở bước 3 của lần lặp, có thể thu được B-1 mỗi lần sử dụng
tiêu chuẩn chương trình máy tínhđể đảo ngược (đảo ngược)
ma trận. Vì B (sau đó là B-1) thay đổi rất ít từ lần lặp này sang lần lặp khác.
khác, sẽ hiệu quả hơn nếu có được B-1 mới (ký hiệu là B-1 mới) từ
B-1 bật lần lặp trước(B-1 cũ). (Đối với giải pháp OA ban đầu). 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; một hình chữ nhật được xây dựng trên đó, các cạnh của nó là các 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 trình bày 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ì đối 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ó thuật ngữ tự do phủ định. 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.

Hiển nhiên, nếu với mọi ẩ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 X b	Thành viên miễn phí	Biến miễn phí
X 1	X 2
X 3
X 4
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 theo 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 phải là 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 X b

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

Biến miễn phí

X7

X 2

X 3

- 1/4

1/2

X 4

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ở ( X 4 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 trình tự đã xem xét, thuật toán phương pháp đơn giản phải có các khối sau:

1. Tìm nghiệm cơ bản ban đầu (tham khảo) 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= C b 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

.

Chúng ta hãy nhớ lại điều đó , 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 = = .

Chúng ta hãy nhớ lại điều đó 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 ; một 23 = 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; X 4=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ơ Cb); =B -1 b, Ở đâ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 -1 b (= 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

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 của 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 quan hệ, xác định phương án tối ưu cho bài toán ban đầu và tìm giá trị lớn nhất hàm mục tiêu vấ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 quyết bằng cách chuyển chúng thành 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 giải pháp 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 khi 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...

Gửi công việc tốt của bạn trong cơ sở kiến ​​thức rất đơn giản. Sử dụng mẫu dưới đây

Các sinh viên, nghiên cứu sinh, các nhà khoa học trẻ sử dụng nền tảng kiến ​​thức trong học tập và công việc sẽ rất biết ơn các bạn.

Tài liệu tương tự

Một phương pháp hình học để giải các bài toán quy hoạch tuyến tính tiêu chuẩn hai biến. Một phương pháp phổ quát để giải quyết vấn đề kinh điển. Ý tưởng chính của phương pháp đơn giản, thực hiện bằng một ví dụ. Thực hiện dạng bảng của một phương pháp đơn giản đơn giản.

tóm tắt, được thêm vào ngày 15/06/2010


Các loại bài toán quy hoạch tuyến tính và cách xây dựng bài toán. Bản chất của tối ưu hóa như một nhánh của toán học và đặc điểm của các phương pháp chính để giải quyết vấn đề. Khái niệm phương pháp đơn hình, bài toán ứng dụng thực tế. Thuật toán và các bước giải bài toán vận tải.

bài tập khóa học, được thêm vào ngày 17/02/2010


Giải các bài toán quy hoạch tuyến tính bằng phương pháp đồ họa và đơn giản. Giải pháp của vấn đề kép so với vấn đề ban đầu. Xác định phương án tối ưu để phân công người tiêu dùng vào các nhà cung cấp hàng hóa đồng nhất, đảm bảo giảm thiểu tổng quãng đường xe đi.

kiểm tra, thêm vào 15/08/2012


Sử dụng phương pháp đơn hình giải bài toán quy hoạch tuyến tính để tính khối lượng sản xuất hàng ngày. Kiểm tra phương án tối ưu. Tính toán lại bảng đơn bằng phương pháp Jordan-Gauss. Vẽ mô hình bài toán vận tải.

kiểm tra, thêm 18/02/2014


Mô hình toán kinh tế để đạt được lợi nhuận tối đa, giải pháp của nó bằng phương pháp đồ họa. Thuật toán giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. Vẽ ra một vấn đề kép và giải pháp đồ họa của nó. Giải pháp ma trận thanh toán.

kiểm tra, thêm vào 11/05/2014


Nguyên tắc cơ bản của mô hình toán học của các quá trình kinh tế. Đặc điểm chung của các phương pháp đồ thị và đơn hình để giải các bài toán quy hoạch tuyến tính trực tiếp và tuyến tính kép. Đặc điểm của công thức và phương pháp giải bài toán vận tải.

bài tập khóa học, được thêm vào ngày 12/11/2010


Xây dựng mô hình toán học của bài toán. Tính toán phương án vận chuyển tối ưu với chi phí tối thiểu bằng phương pháp thế năng. Lựa chọn tối ưu cho thiết bị di động đặc biệt để hỗ trợ kỹ thuật quản lý sản xuất.

kiểm tra, thêm vào ngày 01/06/2014

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

Trong phương pháp đã sửa đổi, ma trận

không được tính toán lại, chỉ có ma trận được lưu trữ và tính toán lại. Phần còn lại của thuật toán tương tự như mô tả ở trên.

1. Tính biến kép

2. Kiểm tra tính tối ưu. được chuyển đổi thành.

Việc kiểm tra bao gồm một phép tính cho tất cả các cột. Cột có giá trị< 0 можно вводить в базис.

Thường thì giá trị tối thiểu được chọn, nhưng điều này đòi hỏi phải lặp qua tất cả các cột.

Thông thường, giá trị nhỏ hơn một giá trị được chỉ định nhất định sẽ được chọn

Nếu không tìm thấy cột như vậy thì giá trị tuyệt đối lớn nhất được tìm thấy sẽ được lấy làm cột tương ứng và được nhập vào cơ sở.

3. Định nghĩa đầu ra.

Đặt là cột đầu vào tương ứng với biến Kế hoạch cơ bản là giải pháp của hệ thống Tăng.

Hãy nhân từ bên trái với, tức là

Đây là phương án cơ bản và là sự phân rã của cột đầu vào theo cơ sở.

Chúng tôi tìm thấy giá trị tối đa mà tại đó tất cả các giá trị không âm. Nếu nó có thể được lấy lớn như mong muốn thì giải pháp không bị giới hạn. Nếu không, một trong các phần tử sẽ về 0. Chúng tôi lấy được cột tương ứng từ cơ sở.

4. Tính toán lại phương án tham chiếu (cơ bản).

Chúng tôi tính toán sơ đồ tham chiếu mới bằng công thức đã cho với giá trị tìm được.

5. Chúng tôi tính toán lại nghịch đảo của cơ bản.

Hãy là cột đầu ra.

Ma trận B có thể được biểu diễn dưới dạng

ma trận cơ sở không có cột đầu ra ở đâu.

Sau khi thay cột, ma trận cơ sở sẽ có dạng

Chúng ta cần tìm ma trận sao cho

Bình luận.

Khi tính toán lại ma trận, các lỗi làm tròn sẽ tích lũy. Để tránh sai số lớn, ma trận được tính toán lại hoàn toàn theo thời gian. Quá trình này được gọi là "sự lặp lại".

Phiên bản nhân của phương pháp đơn giản

Ở dạng nhân, ma trận không được lưu trữ, chỉ lưu trữ các thừa số

Khi giải các bài toán kinh tế, ma trận ràng buộc thường thưa thớt, trong trường hợp đó, phương án nhân nhận được nhiều lợi thế hơn - bạn có thể lưu trữ các số nhân ở dạng nén (không lưu số 0).

Các tùy chọn khác cho phương pháp đơn giản

Để tránh tích lũy các lỗi làm tròn, có thể sử dụng phân tách LU của ma trận.

Với vô số hạn chế thuộc loại “bất bình đẳng”, nó có thể được sử dụng phương pháp cơ sở biến.

Phương pháp này dựa trên thực tế là ma trận cơ sở có thể được biểu diễn dưới dạng

Nghịch đảo của nó có dạng

Với kích thước ma trận tương đối nhỏ, phần còn lại của ma trận có thể không được lưu trữ.

Cách tiếp cận này có thể giải quyết các vấn đề với hàng chục triệu dòng ràng buộc (ví dụ, từ lý thuyết trò chơi).

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

Để thực hiện phương pháp đối ngẫu cần chuyển từ bài toán cực tiểu sang bài toán cực đại (hoặc ngược lại) bằng cách hoán vị ma trận hệ số. Khi chuyển từ bài toán về cực tiểu, hàm mục tiêu có dạng:

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

Định lý nhị nguyên. Nếu một trong cặp bài toán kép có phương án tối ưu thì bài toán kia có nghiệm và các giá trị cực trị của hàm tuyến tính của các bài toán này bằng nhau.

Nếu hàm tuyến tính của một trong các bài toán không bị chặn thì bài toán kia không có lời giải.