Phương pháp Dantzig. Bài toán kiểu truyền tải là một trường hợp đặc biệt của bài toán lập trình tuyến tính

1. Câu nào sai? Phương pháp Danzig

Trả lời: có thể được quy cho nhóm gradient

2. Phát biểu nào sau đây là đúng:

Trả lời: Một vấn đề LP với một hệ thống ràng buộc không nhất quán được gọi là một vấn đề mở.

3. Phương pháp nào sau đây không hoạt động

Trả lời: tỷ lệ vàng

4. Mệnh đề nào sau đây đúng:

Trả lời: nhiệm vụ của loại hình vận tải là trường hợp đặc biệt của nhiệm vụ lập trình tuyến tính

5. Phát biểu nào sau đây là đúng: Phương pháp bình phương tối thiểu

Trả lời: đi xuống giải hệ thống n Các phương trình tuyến tính khi tính gần đúng kết quả theo đa thức bậc n

6. Phương pháp nào sau đây không phải là phương pháp gradient

Trả lời: phương pháp simplex (phương pháp Nelder-Mead)

7. Phương pháp nào được chỉ ra cho phép tìm cực trị toàn cục của một hàm đa phương thức

Trả lời: quét

8. Phương pháp nào trong số các phương pháp được liệt kê là phương pháp tìm kiếm tọa độ

Trả lời: tiếp tuyến

9. Kiểm tra các câu đúng

Trả lời: không thể sử dụng phương pháp liệt kê đơn giản để tìm cực trị theo quy trình Gauss-Seidel.

10. Chỉ ra câu nói đúng

Trả lời: Một kế hoạch là bất kỳ giải pháp chấp nhận được nhiệm vụ

11. Chỉ ra phát biểu sai

Trả lời: một mặt phẳng có chứa ít nhất một điểm ở góc đa diện lồiđược gọi là mặt phẳng tham chiếu của khối đa diện này

12. Cho biết số phát biểu đúng

Trả lời: các bài toán kiểu vận chuyển không thể giải được bằng phương pháp Danzig, vì chúng liên quan đến các bài toán lập trình rời rạc (1). kế hoạch ban đầu trong phương pháp simplex, chúng tôi nhận được bằng không của tất cả các biến cơ bản (3)

13. Chỉ ra câu phát biểu đúng?

Trả lời: giải pháp cơ bản của bài toán LP là suy biến nếu ít nhất một trong các biến tự do bằng 0

14. Điều nào sau đây không đúng:

Trả lời: điểm bất kỳ trên đường thẳng là tổ hợp tuyến tính lồi của hai điểm mà đường thẳng này được vẽ.

15. Phát biểu nào dưới đây là đúng?

Trả lời: Bài toán nhân viên bán hàng lưu động thuộc lĩnh vực lập trình rời rạc.

16. Điều nào sau đây là đúng:

Trả lời: một trong những vấn đề tối ưu hóa chính là "vấn đề về chiều"

17. Điều nào sai trong các câu trên?

Trả lời: nếu hàm mục tiêu của bài toán LP đạt cực trị tại một số điểm, thì nó đạt cùng giá trị tại bất kỳ điểm nào là tổ hợp tuyến tính lồi của các điểm này.

18. Phát biểu nào sau đây không đúng?

Trả lời: Vấn đề LP có thể được giải quyết bằng quy trình chuyển đổi có thứ tự từ kế hoạch này sang kế hoạch khác.

19. Điều nào sau đây là đúng

Trả lời: bên trong miền các giải pháp có thể chấp nhận được của vấn đề LP không thể có cực trị

20. Điều nào sau đây là sai?

Trả lời: Để tìm điểm cực trị của một tuyến tính hàm mục tiêu sử dụng phương pháp simplex, cần thực hiện n-m lần lặp, n là số ẩn số của bài toán, m là số ràng buộc tổng quát

phương pháp gradient tìm kiếm hàm mục tiêu tối ưu dựa trên việc sử dụng hai Các tính chất cơ bản hàm gradient.

1. Gradient của một hàm là một vectơ, tại mỗi điểm thuộc miền của định nghĩa hàm
được hướng dọc theo pháp tuyến đến bề mặt bằng đi qua điểm này.

Phép chiếu Gradient
trên trục tọa độ bằng các đạo hàm riêng của hàm số
cho các biến tương ứng, tức là

. (2.4)

Các phương pháp gradient bao gồm: phương pháp thư giãn, gradient, dốc nhất và một số phương pháp khác.

Hãy xem xét một số phương pháp gradient.

phương pháp gradient

Trong phương pháp này, đường xuống được thực hiện theo hướng thay đổi nhanh nhất trong hàm mục tiêu, điều này tự nhiên tăng tốc độ tìm kiếm tối ưu.

Việc tìm kiếm cái tối ưu được thực hiện trong hai giai đoạn. Ở giai đoạn đầu tiên, các giá trị của đạo hàm riêng đối với tất cả các biến độc lập được tìm thấy, các giá trị này xác định hướng của gradient tại điểm được xem xét. Ở giai đoạn thứ hai, một bước được thực hiện theo hướng ngược lại với hướng của gradient (khi tìm kiếm cực tiểu của hàm mục tiêu).

Khi một bước được thực hiện, giá trị của tất cả các biến độc lập được thay đổi đồng thời. Mỗi người trong số họ nhận được một gia số tỷ lệ với thành phần tương ứng của gradient dọc theo trục đã cho.

Công thức của thuật toán có thể giống như sau:

,
. (2.5)

Trong trường hợp này, kích thước bước
ở một giá trị không đổi của tham số, h thay đổi tự động cùng với sự thay đổi trong giá trị gradient và giảm khi nó đạt đến mức tối ưu.

Một bản ghi công thức khác của thuật toán là:

,
. (2.6)

Thuật toán này sử dụng một vectơ gradient chuẩn hóa chỉ cho biết hướng thay đổi nhanh nhất trong hàm mục tiêu, nhưng không cho biết tốc độ thay đổi theo hướng này.

Trong chiến lược thay đổi cao độ
trong trường hợp này, nó được sử dụng để chuyển màu
và
khác nhau về hướng. Bước tìm kiếm được thay đổi theo quy tắc:

(2.7)

ở đâu
là góc quay của gradient ở bước thứ k, được xác định bởi biểu thức

,

,
là giới hạn cho phép của góc quay của gradient.

Bản chất của việc tìm kiếm giá trị tối ưu trong phương pháp gradient được thể hiện trong hình. 2.1.

Thời điểm kết thúc tìm kiếm có thể được tìm thấy bằng cách kiểm tra ở mỗi bước của mối quan hệ

,

ở đâu là lỗi tính toán đã cho.

Cơm. 2.1. Bản chất của chuyển động theo hướng tối ưu trong phương pháp gradient với kích thước bước lớn

Nhược điểm của phương pháp gradient là khi sử dụng nó, chỉ có thể tìm được cực tiểu cục bộ của hàm mục tiêu. Để tìm cực tiểu cục bộ khác của hàm, cần phải tìm từ các điểm xuất phát khác.

Một nhược điểm khác của phương pháp này là số lượng tính toán đáng kể, vì ở mỗi bước, giá trị của tất cả các đạo hàm riêng của hàm đang được tối ưu hóa đối với tất cả các biến độc lập được xác định.

Phương pháp đi xuống dốc nhất

Khi áp dụng phương pháp gradient, tại mỗi bước, cần xác định các giá trị của đạo hàm riêng của hàm được tối ưu hóa đối với tất cả các biến độc lập. Nếu số lượng biến độc lập là đáng kể, thì lượng tính toán tăng lên đáng kể và thời gian để tìm kiếm biến tối ưu tăng lên.

Giảm khối lượng tính toán có thể đạt được bằng cách sử dụng phương pháp dốc nhất.

Bản chất của phương pháp như sau. Sau khi tìm thấy gradient của hàm cần tối ưu hóa tại điểm ban đầu và do đó hướng giảm nhanh nhất của nó tại điểm xác định được xác định, một bước giảm dần được thực hiện theo hướng này (Hình 2.2).

Nếu giá trị của hàm đã giảm do kết quả của bước này, thì bước tiếp theo được thực hiện theo cùng một hướng, và cứ tiếp tục như vậy cho đến khi tìm thấy giá trị nhỏ nhất theo hướng này, sau đó gradient được tính và hướng mới của tốc độ nhanh nhất giảm trong hàm mục tiêu được xác định.

Cơm. 2.2. Bản chất của chuyển động theo hướng tối ưu trong phương pháp dốc nhất (-) và phương pháp gradient (∙∙∙∙)

So với phương pháp gradient, phương pháp dốc nhất có ưu điểm hơn do giảm lượng tính toán.

Một đặc điểm quan trọng của phương pháp giảm dần là khi nó được áp dụng, mỗi hướng chuyển động mới theo hướng tối ưu sẽ trực giao với hướng trước đó. Điều này là do chuyển động theo một hướng được thực hiện cho đến khi hướng chuyển động tiếp tuyến với bất kỳ đường nào có mức không đổi.

Như một tiêu chí để kết thúc tìm kiếm, điều kiện tương tự như trong phương pháp trên có thể được sử dụng.

Ngoài ra, người ta cũng có thể chấp nhận điều kiện chấm dứt tìm kiếm dưới dạng quan hệ

,

ở đâu
và
là tọa độ của điểm đầu và điểm cuối của đoạn cuối cùng của đường đi xuống. Cùng một tiêu chí có thể được sử dụng kết hợp với việc kiểm soát các giá trị hàm mục tiêu tại các điểm
và

.

Việc áp dụng chung các điều kiện để kết thúc tìm kiếm là hợp lý trong các trường hợp khi chức năng đang được tối ưu hóa có mức tối thiểu rõ rệt.

Cơm. 2.3. Theo định nghĩa của kết thúc tìm kiếm trong phương pháp dốc nhất

Là một chiến lược để thay đổi bước đi xuống, bạn có thể sử dụng các phương pháp được mô tả ở trên (2.7).

Chúng ta hãy xem xét vấn đề cực tiểu không điều kiện của một hàm phân biệt của một số biến. Trong phương pháp gradient được xem xét dưới đây, hướng đi xuống từ điểm được chọn trực tiếp. Do đó, theo phương pháp gradient

Hiện hữu nhiều cách khác nhau lựa chọn bước, mỗi bước trong số đó đặt biến thể nhất định phương pháp gradient.

1. Phương pháp xuống dốc nhất.

Hãy xem xét một hàm của một biến vô hướng và chọn làm giá trị mà đẳng thức

Phương pháp này, được đề xuất vào năm 1845 bởi O. Cauchy, ngày nay được gọi là phương pháp xuống dốc nhất.

Trên hình. 10.5 cho thấy một minh họa hình học của phương pháp này để tối thiểu hóa một hàm có hai biến. Từ điểm xuất phát, vuông góc với đường mức theo phương, tiếp tục đi xuống cho đến khi đạt giá trị nhỏ nhất của hàm số dọc theo tia. Tại điểm được tìm thấy, tia này chạm vào đường mức. Sau đó, một đường đi xuống được tạo ra từ điểm theo phương vuông góc với đường mức cho đến khi tia tương ứng chạm vào đường mức đi qua điểm này tại điểm, v.v.

Chúng tôi lưu ý rằng ở mỗi lần lặp, việc lựa chọn bước ngụ ý giải pháp của bài toán tối thiểu hóa một chiều (10,23). Đôi khi thao tác này có thể được thực hiện một cách phân tích, ví dụ, đối với hàm bậc hai.

Chúng tôi áp dụng phương pháp dốc nhất để giảm thiểu hàm bậc hai

với một ma trận A xác định dương đối xứng.

Do đó, theo công thức (10.8), trong trường hợp này, công thức (10.22) có dạng như sau:

thông báo rằng

Hàm này là một hàm bậc hai của tham số a và đạt cực tiểu tại một giá trị mà tại đó

Do đó, như được áp dụng cho việc tối thiểu hóa bậc hai

hàm (10,24), phương pháp giảm độ dốc lớn nhất tương đương với phép tính theo công thức (10,25), trong đó

Nhận xét 1. Vì điểm cực tiểu của hàm số (10,24) trùng với nghiệm của hệ, nên phương pháp dốc nhất (10,25), (10,26) cũng có thể được sử dụng như phương pháp lặp lại giải pháp của hệ thống tuyến tính phương trình đại số với ma trận xác định dương đối xứng.

Nhận xét 2. Lưu ý rằng đâu là quan hệ Rayleigh (xem § 8.1).

Ví dụ 10.1. Chúng tôi áp dụng phương pháp dốc nhất để giảm thiểu hàm bậc hai

Lưu ý rằng Do đó, chúng tôi đã biết trước giá trị chính xác của điểm tối thiểu. Hãy viết ra Chức năng nàyở dạng (10.24), trong đó ma trận và vectơ Như dễ thấy,

Chúng tôi lấy giá trị gần đúng ban đầu và chúng tôi sẽ thực hiện các phép tính bằng công thức (10,25), (10,26).

Tôi lặp lại.

II lần lặp.

Có thể chỉ ra rằng đối với tất cả các lần lặp, các giá trị sẽ nhận được

Lưu ý rằng với Như vậy,

trình tự thu được bằng phương pháp dốc nhất hội tụ với tốc độ cấp số nhân, mẫu số của ai

Trên hình. 10.5 cho thấy chính xác quỹ đạo đi xuống thu được trong ví dụ này.

Đối với trường hợp tối thiểu hóa một hàm bậc hai, điều sau đúng kết quả chung.

Định lý 10.1. Gọi A là ma trận xác định dương đối xứng và hàm số bậc hai (10.24) có cực tiểu. Sau đó, đối với bất kỳ lựa chọn nào về ước lượng ban đầu, phương pháp giảm dần dốc nhất (10,25), (10,26) sẽ hội tụ và ước tính sai số sau là đúng:

Ở đây và Lado là các giá trị riêng nhỏ nhất và lớn nhất của ma trận A.

Lưu ý rằng phương pháp này hội tụ với tốc độ của một cấp tiến hình học, mẫu số của nó, hơn nữa, nếu chúng gần nhau thì nó nhỏ và phương pháp này hội tụ khá nhanh. Ví dụ, trong Ví dụ 10.1, chúng ta có và, do đó, Nếu Asch, thì 1, và chúng ta nên mong đợi phương pháp đi xuống dốc nhất hội tụ chậm.

Ví dụ 10.2. Việc áp dụng phương pháp đi xuống dốc nhất để tối thiểu hóa hàm bậc hai ở giá trị gần đúng ban đầu đưa ra một chuỗi các phép gần đúng trong đó Quỹ đạo của đường đi xuống được thể hiện trong Hình. 10,6.

Chuỗi hội tụ ở đây với tốc độ của một tiến trình hình học, mẫu số của nó, tức là chậm hơn nhiều,

hơn trong ví dụ trước. Vì ở đây kết quả thu được hoàn toàn phù hợp với ước tính (10,27).

Nhận xét 1. Chúng tôi đã xây dựng một định lý về sự hội tụ của phương pháp dốc nhất trong trường hợp hàm mục tiêu là bậc hai. TẠI trường hợp chung, nếu hàm cực tiểu là hàm lồi và có điểm cực tiểu x thì, bất kể lựa chọn xấp xỉ ban đầu là bao nhiêu, dãy thu được bằng phương pháp này hội tụ về x tại. Trong trường hợp này, sau khi rơi vào vùng lân cận đủ nhỏ của điểm cực tiểu, sự hội tụ trở thành tuyến tính và mẫu số của cấp độ hình học tương ứng được ước lượng từ trên theo giá trị và ở đó cả giá trị nhỏ nhất và lớn nhất giá trị riêng Ma trận Hessian

Nhận xét 2. Đối với hàm mục tiêu bậc hai (10.24), lời giải của bài toán tối thiểu hóa một chiều (10.23) có thể được tìm thấy dưới dạng một công thức tường minh đơn giản (10.26). Tuy nhiên, đối với hầu hết những người khác chức năng phi tuyếnđiều này không thể được thực hiện và để tính toán theo phương pháp dốc nhất, người ta phải áp dụng phương pháp số các giảm thiểu một chiều của kiểu đã được thảo luận trong chương trước.

2. Vấn đề "khe núi".

Từ cuộc thảo luận ở trên, phương pháp gradient hội tụ khá nhanh nếu các bề mặt mức của hàm thu nhỏ gần với hình cầu (khi các đường mức gần với các đường tròn). Đối với các hàm như vậy, và 1. Định lý 10.1, Nhận xét 1, và kết quả của Ví dụ 10.2 chỉ ra rằng tốc độ hội tụ giảm mạnh khi giá trị của. Trong trường hợp hai chiều, phần nổi của bề mặt tương ứng giống với địa hình có khe núi (Hình 10.7). Do đó, các chức năng như vậy thường được gọi là gully. Dọc theo các hướng đặc trưng cho "đáy khe núi", chức năng của khe núi thay đổi không đáng kể, trong khi ở các hướng khác đặc trưng cho "độ dốc khe núi", một sự thay đổi rõ rệt về chức năng xảy ra.

Nếu điểm bắt đầu rơi trên "độ dốc khe núi", thì hướng của dốc xuống gần như vuông góc với "đáy khe núi" và điểm gần đúng tiếp theo rơi trên "độ dốc khe núi" ngược lại. Bước tiếp theo đối với "đáy khe núi" quay trở lại cách tiếp cận "độ dốc khe núi" ban đầu. Kết quả là thay vì di chuyển dọc theo “đáy khe núi” về phía điểm cực tiểu, quỹ đạo đi xuống làm cho những cú nhảy ngoằn ngoèo qua “khe núi”, gần như không tiếp cận được mục tiêu (Hình 10.7).

Để tăng tốc độ hội tụ của phương pháp gradient trong khi giảm thiểu các chức năng của khe núi, một số phương pháp "khe núi" đặc biệt đã được phát triển. Hãy đưa ra ý tưởng về một trong những phương pháp đơn giản nhất. Từ hai điểm xuất phát gần nhau, một dốc dốc được thực hiện đến "đáy của khe núi". Một đường thẳng được vẽ qua các điểm được tìm thấy, dọc theo đó một bước "khe núi" lớn được thực hiện (Hình 10.8). Từ điểm được tìm thấy theo cách này, một bước của gradient đi xuống điểm được thực hiện một lần nữa. Sau đó, bước "khe núi" thứ hai được thực hiện dọc theo đường thẳng đi qua các điểm. Kết quả là, chuyển động dọc theo "đáy khe núi" đến điểm cực tiểu được tăng tốc đáng kể.

Hơn thông tin chi tiết về vấn đề của phương pháp "khe núi" và "rãnh nước" có thể được tìm thấy, ví dụ, trong,.

3. Các cách tiếp cận khác để xác định bước đi xuống.

Nói một cách dễ hiểu, tại mỗi lần lặp, bạn nên chọn một hướng đi xuống gần với hướng mà chuyển động dẫn từ điểm đến điểm x. Thật không may, phản truyền tín hiệu (theo quy luật, là một hướng đi xuống không may. Điều này đặc biệt rõ ràng đối với các hàm khe núi. Do đó, có nghi ngờ về khả năng tư vấn của việc tìm kiếm kỹ lưỡng giải pháp cho vấn đề giảm thiểu một chiều (10,23) và có mong muốn chỉ thực hiện một bước như vậy theo hướng có thể cung cấp "sự giảm đáng kể" của chức năng. Hơn nữa, trong thực tế, đôi khi người ta hài lòng với việc xác định một giá trị chỉ đơn giản là làm giảm giá trị của mục tiêu hàm số.

Phương pháp Gauss-Seidel

Phương pháp này bao gồm việc luân phiên tìm điểm cực trị riêng của hàm mục tiêu cho mỗi yếu tố. Đồng thời, ở mỗi giai đoạn, các yếu tố (k-1) được ổn định và chỉ có một yếu tố thứ i thay đổi

Quy trình tính toán: trong vùng cục bộ của không gian nhân tố, dựa trên các thí nghiệm sơ bộ, một điểm được chọn tương ứng với kết quả tốt nhất và từ đó chúng bắt đầu hướng tới điều tối ưu. Bước chuyển động của mỗi yếu tố do nhà nghiên cứu đặt ra. Đầu tiên, tất cả các yếu tố được cố định ở cùng một mức và một yếu tố được thay đổi cho đến khi có sự tăng (giảm) trong hàm phản ứng (Y), sau đó yếu tố kia được thay đổi trong khi các yếu tố khác ổn định, v.v. cho đến khi chúng nhận được kết quả như ý(Y). Điều chính là chọn bước phù hợp cho từng yếu tố.

Phương pháp này là đơn giản nhất, mang tính minh họa cao nhất, nhưng quá trình di chuyển đến điểm tối ưu là lâu và phương pháp này hiếm khi dẫn đến điểm tối ưu. Hiện tại, nó đôi khi được sử dụng trong thí nghiệm máy.

Các phương pháp này cung cấp chuyển động đến mức tối ưu dọc theo một đường thẳng vuông góc với các đường của phản ứng bằng nhau, tức là theo hướng của gradient của hàm phản hồi.

Phương pháp Gradient có một số loại khác nhau về quy tắc chọn các bước biến thiên và các bước làm việc ở mỗi giai đoạn của chuyển động đến cực đại.

Bản chất của tất cả các phương pháp là như sau: ban đầu, trên cơ sở các thí nghiệm sơ bộ, điểm cơ bản. Sau đó, ở mỗi giai đoạn, các thí nghiệm thử nghiệm được tổ chức xung quanh điểm cơ sở tiếp theo, kết quả đánh giá hướng mới của gradient, sau đó một bước làm việc được thực hiện theo hướng này.

Phương pháp gradient (bình thường) được thực hiện theo sơ đồ sau:

a) chọn một điểm cơ sở;

b) lựa chọn các bước chuyển động cho từng yếu tố;

c) xác định tọa độ của các điểm kiểm tra;

d) tiến hành các thí nghiệm tại các điểm kiểm tra. Kết quả là, các giá trị của tham số tối ưu hóa (Y) nhận được tại mỗi điểm.

e) dựa trên kết quả của các thí nghiệm, các ước lượng của các thành phần của vectơ gradient tại điểm M được tính cho mỗi hệ số thứ i:

trong đó H i là bước chuyển động dọc theo X i.

X i - tọa độ của điểm làm việc trước đó.

g) tọa độ của điểm vận hành này được lấy làm điểm cơ sở mới, xung quanh đó các thí nghiệm được thực hiện tại các điểm thử. Gradient được tính toán, v.v., cho đến khi đạt được thông số tối ưu hóa mong muốn (Y). Việc điều chỉnh hướng chuyển động được thực hiện sau mỗi bước.

Ưu điểm của phương pháp: đơn giản, tốc độ di chuyển cao hơn đến mức tối ưu.

Nhược điểm: độ nhạy nhiễu cao. Nếu đường cong có hình dáng phức tạp, phương pháp có thể không dẫn đến tối ưu. Nếu đường cong phản ứng bằng phẳng, phương pháp này không hiệu quả. Phương pháp không cung cấp thông tin về sự tương tác của các yếu tố.

a) Phương pháp leo dốc (Box-Wilson).

b) Ra quyết định sau khi leo dốc.

c) Phương pháp tối ưu hóa đơn giản.

d) Ưu nhược điểm của các phương pháp.

5.7.3 Phương pháp leo dốc (Box-Wilson)

Phương pháp này là sự tổng hợp tính năng tốt nhất phương pháp gradient, phương pháp Gauss-Seidel và phương pháp PFE và DFE - như một phương tiện thu được mô hình toán học của quá trình. Lời giải của bài toán tối ưu bằng phương pháp này được thực hiện sao cho chuyển động bước được thực hiện theo chiều tăng (giảm) nhanh nhất của tham số tối ưu. Việc hiệu chỉnh hướng chuyển động (ngược lại với phương pháp gradient) không được thực hiện sau mỗi bước, mà khi đạt đến một điểm cực trị cụ thể của hàm mục tiêu. Hơn nữa, tại các điểm của một phần cực trị, một thử nghiệm giai thừa mới được thiết lập, một mô hình toán học và một lần nữa quá trình đi lên dốc được lặp lại cho đến khi đạt được mức tối ưu toàn cầu. Chuyển động dọc theo gradient bắt đầu từ điểm 0 (tâm của kế hoạch).

Phương pháp đi lên dốc liên quan đến việc di chuyển về phía tối ưu dọc theo một gradient.

Ở đâu vectơ đơn vị i, j, k theo hướng của các trục tọa độ tương ứng.

Quy trình tính toán.

Dữ liệu ban đầu là một mô hình toán học của quá trình thu được bằng bất kỳ phương pháp nào (PFE, DFE, v.v.).

Các phép tính được thực hiện theo thứ tự sau:

a) tốt hơn nên chuyển phương trình hồi quy về dạng tự nhiên bằng cách sử dụng các công thức mã hóa biến số:

ở đâu x i -giá trị được mã hoá của biến x i;

X i - giá trị tự nhiên của biến x i;

X i C - cấp trung tâm của nhân tố ở dạng tự nhiên;

l i - khoảng biến thiên của thừa số x i ở dạng tự nhiên.

b) Tính các bước chuyển động sao cho tối ưu cho từng yếu tố.

Để làm điều này, hãy tính tích các hệ số của phương trình hồi quy ở dạng tự nhiên theo các khoảng biến thiên tương ứng

B i * .l I ,

Sau đó, từ các sản phẩm thu được, mô đun lớn nhất được chọn và hệ số tương ứng với sản phẩm này được lấy làm hệ số cơ sở (B a l a). Đối với yếu tố cơ bản, bạn nên đặt bước chuyển động, được khuyến nghị đặt nhỏ hơn hoặc bằng khoảng sự biến đổi của hệ số cơ sở

Dấu của bước chuyển động l a ’phải trùng với dấu của hệ số của phương trình hồi quy ứng với hệ số cơ sở (B a). Giá trị của các bước cho các yếu tố khác được tính toán tương ứng với cơ sở một theo công thức:

Dấu của các bước chuyển động cũng phải phù hợp với dấu của các hệ số tương ứng của phương trình hồi quy.

c) hàm đáp ứng được tính toán ở trung tâm của kế hoạch, tức là, với các giá trị của các yếu tố bằng mức trung tâm của các yếu tố, vì chuyển động theo hướng tối ưu bắt đầu từ trung tâm của kế hoạch.

Tiếp theo, tham số tối ưu hóa được tính toán, tăng giá trị của các yếu tố bằng giá trị của bước chuyển động tương ứng, nếu bạn muốn Y max. Ngược lại, nếu cần lấy Y min, giá trị của các yếu tố sẽ giảm đi theo giá trị của bước chuyển động.

Quy trình được lặp lại, liên tiếp tăng số bước cho đến khi đạt được giá trị mong muốn của tham số tối ưu hóa (Y). Mỗi yếu tố sau g các bước sẽ quan trọng:

Nếu Y®max X i \ u003d X i c + gl i ''

nếu Y® tối thiểu. X i \ u003d X i c -gl i `.(5.36)

Phương pháp gradient và các phương pháp khác của nó là một trong những phương pháp phổ biến nhất để tìm cực trị của các hàm của một số biến. Ý tưởng của phương pháp gradient là di chuyển mỗi lần theo hướng tăng lớn nhất của hàm mục tiêu trong quá trình tìm kiếm điểm cực trị (để xác định điểm cực đại).

Phương pháp gradient liên quan đến việc tính toán các đạo hàm đầu tiên của hàm mục tiêu đối với các đối số của nó. Nó, giống như những cái trước, đề cập đến các phương pháp gần đúng và cho phép, như một quy luật, không đạt đến điểm tối ưu, mà chỉ để tiếp cận nó cho số giới hạn các bước.

Cơm. 4.11.

Cơm. 4.12.

(trường hợp hai chiều)

Đầu tiên hãy chọn điểm bắt đầu Nếu trong trường hợp một chiều (xem tiểu mục 4.2.6) từ nó thì có thể

chỉ di chuyển sang trái hoặc phải (xem Hình 4.9), khi đó trong trường hợp đa chiều, số lượng các hướng chuyển động có thể có là vô cùng lớn. Trên hình. 4.11, minh họa trường hợp hai biến, mũi tên xuất hiện từ điểm bắt đầu NHƯNG, hiển thị khác nhau hướng có thể. Đồng thời, việc di chuyển dọc theo một số sẽ làm tăng giá trị của hàm mục tiêu đối với điểm NHƯNG(ví dụ chỉ đường 1-3), và theo các hướng khác dẫn đến giảm (hướng 5-8). Xét rằng vị trí của điểm tối ưu là chưa biết, chiều mà hàm mục tiêu tăng nhanh nhất được coi là tốt nhất. Hướng này được gọi là dốc chức năng. Lưu ý rằng tại mọi điểm mặt phẳng tọa độ hướng của gradient vuông góc với tiếp tuyến của đường thẳng vẽ qua cùng một điểm.

TẠI phân tích toán học nó được chứng minh rằng các thành phần của vectơ gradient của hàm tại =/(*, x 2, ..., x n) là các dẫn xuất riêng của nó đối với các đối số, tức là

& ad / (x 1, x 2 ,.= (du / dhu, dy / dx 2, ..., dy / dx p). (4.20)

Do đó, khi tìm kiếm cực đại bằng phương pháp gradient, ở lần lặp đầu tiên, các thành phần của gradient được tính theo công thức (4.20) cho điểm bắt đầu và một bước làm việc được thực hiện theo hướng tìm được, tức là quá trình chuyển đổi được thực hiện để điểm mới -0)

Y "với tọa độ:

1§gas1 / (x (0)),

hoặc ở dạng vectơ

ở đâu X- vĩnh viễn hoặc tham số biến, xác định độ dài của bước làm việc,? i> 0. Ở lần lặp thứ hai, hãy tính lại một lần nữa

vectơ gradient đã cho một điểm mới. Y, sau đó, tương tự

công thức đi đến điểm x ^ > vân vân. (Hình 4.12). Cho tùy ý đến- lần lặp lại chúng tôi có

Nếu không phải là cực đại mà là cực tiểu của hàm mục tiêu được tìm kiếm, thì tại mỗi lần lặp, một bước được thực hiện theo hướng ngược lại với hướng của gradient. Nó được gọi là hướng chống gradient. Thay vì công thức (4.22), trong trường hợp này, nó sẽ là

Có nhiều loại phương pháp gradient, khác nhau về sự lựa chọn của bước làm việc. Chẳng hạn, có thể đi đến từng điểm tiếp theo tại giá trị hiện có x, và sau đó

Chiều dài của bước làm việc là khoảng cách giữa các điểm liền kề x ^

1 "của chúng - sẽ tỷ lệ với môđun của vectơ gradient. Ngược lại, bạn có thể chọn ở mỗi lần lặp lại X sao cho độ dài của bước làm việc không đổi.

Ví dụ. Nó được yêu cầu để tìm mức tối đa của hàm

y \ u003d 110-2 (lg, -4) 2 -3 (* 2 -5) 2.

Tất nhiên, sử dụng Điều kiện cần thiết cực hạn, chúng tôi ngay lập tức có được giải pháp mong muốn: X] - 4; x 2= 5. Tuy nhiên, về điều này ví dụ đơn giản nó là thuận tiện để chứng minh thuật toán của phương pháp gradient. Hãy tính toán gradient của hàm mục tiêu:

tốt nghiệp y \ u003d (du / dx-, dy / dx 2) \ u003d(4 (4 - *,); 6 (5 - x 2)) và chọn điểm bắt đầu

A * »= (x) °> = 0; 4 °> = O).

Giá trị của hàm mục tiêu cho điểm này, vì nó dễ tính, bằng y [x ^ j = 3. Để X= const = 0,1. Giá trị gradient tại một điểm

3c (0) bằng grad y | x ^ j = (16; 30). Sau đó, ở lần lặp đầu tiên, theo công thức (4.21), chúng ta thu được tọa độ của điểm

x 1)= 0 + 0,1 16 = 1,6; x ^ = 0 + 0,1 30 = 3.

y (x (1)) \ u003d 110 - 2 (1.6 - 4) 2 - 3 (3 - 5) 2 \ u003d 86.48.

Như bạn có thể thấy, nó lớn hơn đáng kể so với giá trị trước đó. Ở lần lặp thứ hai, chúng ta có công thức (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;