조건부 및 무조건부 최적화, 적용 분야. 무조건 및 조건부 최적화 방법 전문가 평가 방법
전체 옵션 세트에서 히스토그램을 작성하고, 좋은 옵션이 얼마나 자주 있는지 평가하고, 마지막으로 검색을 계속할지 또는 찾은 솔루션으로 자신을 제한할지 결정할 수 있습니다.
랜덤 프로빙 절차의 보편성과 단순성에도 불구하고 상당한 계산 복잡성으로 인해 제한될 수 없습니다. 따라서 방법 직접 검색솔루션.
4.5.3. 무조건 최적화 방법
위에서 고려한 모든 형태의 극값을 달성하는 데 필요한 조건은 매우 복잡하고 시간이 많이 걸리는 작업인 비선형 방정식 시스템의 솔루션으로 이어집니다(계산 수학에서도 비선형 방정식의 솔루션은 종종 일종의 최적화 문제). 따라서 실제로는 기능 최적화에 대한 다른 접근 방식이 사용되며 그 고려 사항은 소위 직접 방법으로 시작됩니다. 앞으로는 여기에서 최소화에 대해 이야기할 것이므로 극한이 최소입니다.
현재 무조건 및 조건부 최적화 문제 모두에 대해 많은 수치 방법이 개발되었습니다. 수치적 방법의 품질은 수렴 속도, 한 번의 반복 실행 시간, 방법을 구현하는 데 필요한 컴퓨터 메모리의 양, 해결해야 할 문제 등급 등 많은 요소로 특징지어집니다. 해결해야 할 문제 또한 매우 다양합니다. 차원이 높거나 낮을 수 있고, 단봉 및 다극단일 수 있습니다. 한 유형의 문제를 해결하는 데 효과적인 동일한 방법이 다른 유형의 문제에는 완전히 허용되지 않을 수 있습니다.
다음은 비선형 프로그래밍 문제를 해결하기 위한 주요 방법에 대한 개요입니다. 그러한 방법의 전체 목록은 매우 광범위하고 열려 있음을 명심해야 합니다. 또한 고려된 여러 방법에 대해 다양한 수정이 알려져 있습니다. 더 자세한 정보에서 얻을 수 있습니다
예를 들어 .
제약 조건이 없을 때 제약 없는 최적화의 직접적인 방법을 고려하는 것으로 시작하겠습니다.
무조건 최적화의 직접적인 방법의 의미는 점 X , X , ..., X 의 시퀀스를 구성하는 것입니다.
f(X)>f(X)>… …>f(X). 임의의 점을 X의 시작점으로 선택할 수 있지만 가능한 한 최소점에 가깝게 선택하는 경향이 있습니다. 점 X 에서 점 X , k =0,1,2,... 로의 전환(반복)은 두 단계로 구성됩니다.
– 한 지점에서 이동 방향 선택 X ;
– 이 방향을 따라 단계 정의.
이러한 시퀀스를 구성하는 방법은 함수의 더 큰 값에서 더 작은 값으로 전환되기 때문에 종종 하강 방법이라고합니다.
수학적으로 하강 방법은 다음 관계식으로 설명됩니다.
X =X + a k p , k =0,1,2,...,
여기서 p는 하강 방향을 결정하는 단위 벡터입니다.
k는 스텝 길이입니다.
서로 다른 하강 방법은 p와 k가 선택되는 방식이 서로 다릅니다. 실제로는 수렴이 있는 방법만 사용됩니다. 그들은 최소 포인트를 얻거나 그것에 충분히 가까워지기 위해 제한된 수의 단계를 허용합니다. 수렴 반복 방법의 품질은 수렴 속도로 평가됩니다.
이론적으로 하강 방법에서는 무한 반복으로 문제를 해결합니다. 실제로는 반복 프로세스를 중지하기 위한 특정 기준(조건)이 충족되면 계산이 중지됩니다. 예를 들어, 이것은 작은 자연의 조건일 수 있습니다.
논쟁 |
X[k] - X[k - 1] |
||||||
f(X[k]) - f(X[k-1])< γ . Здесь k – номер итерации; ε , γ – задан-
nye 문제 해결의 정확도 값.
X에서 X로의 전환 매개변수(이동 방향 및 단계 크기)가 점 X에서 사용할 수 있는 정보에 따라 고유하게 선택되는 경우 최소점을 찾는 방법을 결정론적이라고 합니다. 전환 중에 임의의 메커니즘이 사용되는 경우 검색 알고리즘을 임의 최소 검색이라고 합니다.
결정적 비제약 최소화 알고리즘은 사용된 정보 유형에 따라 클래스로 나뉩니다. 각 반복에서 최소화된 함수의 값만 사용되는 경우 이 방법을 0차 방법이라고 합니다. 또한 최소화되는 함수의 1차 도함수를 계산해야 하는 경우 1차 방법이 있습니다.
필요한 경우 2차 미분의 추가 계산 - 2차 방법.
비제약 최소화 문제를 풀 때 1차 및 2차 방법이 일반적으로 0차 방법보다 더 높은 수렴률을 갖는다는 점에 유의해야 합니다. 그러나 실제로는 변수가 많은 함수의 1차 미분과 2차 미분을 계산하는 것은 매우 힘든 일입니다. 경우에 따라 분석 함수의 형태로 얻을 수 없습니다. 각종 파생상품 수치적 방법그러한 방법의 사용을 제한할 수 있는 오류로 결정됩니다. 또한 최적성 기준은 명시적으로 지정되지 않고 방정식 시스템에 의해 지정될 수 있습니다. 이 경우 분석적으로 또는 수치적으로 도함수를 찾는 것이 매우 어렵고 때로는 불가능합니다. 따라서 여기서는 0차 방법이 가장 자세히 고려됩니다.
1차원 검색 방법. 1차원 검색 방법 목록 - 인수가 하나인 함수의 극한값에 대한 수치 검색에프엑스 ) 상당히 넓고 문헌에서 잘 다룹니다. 따라서 여기서는 저자의 경험에 따르면 가장 효과적인 "골든 섹션" 방법 중 하나인 한 가지 방법만 고려하도록 제한합니다.
이 방법의 아이디어는 불확실성 간격(원하는 최소 포인트를 포함하는 인수 x의 값 간격)을 초과하지 않는 길이로 일관되게 줄이는 것입니다.
허용 가능한 결과 오류 ε . 초기 간격으로 문제의 조건에 의해 지정된 인수의 허용 가능한 값 범위 또는 후자가 왼쪽 및 / 또는 오른쪽 경계가없는 경우 허용 가능한 영역 내부의 일부 영역 원하는 최소값은 예비 분석으로 표시되며 고려할 수 있습니다.
모든 구간 내에는 두 개의 점이 x = y 0 및 x = z 0 , "황금 섹션"을 수행합니다. 전체 구간의 길이에 대한 더 큰 부분의 비율이 작은 부분에서 큰 부분으로. 분명히 이 점들은 간격의 중심에 대해 대칭적으로 위치합니다(그림 26). "골든 섹션" 포인트의 좌표는 해당 비율에서 찾을 수 있습니다.
b - y0 |
y0-a |
= δ , |
z0-a |
b - z0 |
= δ, |
||||
b-a |
에 의해 |
b-a |
- |
||||||
여기서 δ = (1–δ)/δ를 쉽게 구할 수 있고 다음 방정식을 얻을 수 있습니다. δ 2 + δ –1=0. 결과적으로 간격의 "골든 섹션"을 결정하는 상대적 점유율(δ = 0.618, 1–δ = 0.382)을 얻습니다. 황금 비율은 중요한 재산: 포인트 y 0은 간격의 "골든 섹션" 포인트 중 하나이고 포인트 z 0은 간격의 "골든 섹션" 포인트 중 하나입니다. 이 죽이기에서
간단한 계산: 0.382/0.618 = 0.618 및 (0.618–0.382)/0.618 = = 0.382.
"골든 섹션" 방법을 기반으로 구축된 최소 검색 알고리즘은 감소된 간격의 경계 중 하나로 "골든 섹션"의 왼쪽 또는 오른쪽 지점의 각 반복에서 다음과 같은 방식으로 선택을 제공합니다. 원하는 최소값은 그 안에 남아 있습니다.
1. k =0, 초기 불확실성 구간 , 허용 가능한 결과 오류 ε 를 설정합니다.
2. "골든 섹션" 포인트의 좌표를 계산합니다.
y k \u003d a k +0.382 (b k - a k), z k \u003d a k +0.618 (b k - a k ).
3. 찾은 지점에서 목적 함수 값을 계산합니다.
f(yk) 및 f(zk).
4. f (y k) ≤ f (z k) (그림 26, 그러나) a k + 1 \u003d a k, b k + 1 \u003d z k, z k + 1 \u003d y k, y k + 1 \u003d a k + z k -y k, k = k+1. 그렇지 않으면 (그림 26, b) a k + 1 =y k, b k + 1 = b k, y k + 1 = z k, z k + 1 = y k + b k –z k, k = k +1.
5. 검색 완료 조건 충족 여부 확인
b k + 1 − a k + 1 ≤ ε . 충족되면 점 x = (y k + 1 + z k + 1 ) 2가 솔루션으로 선택됩니다. 그렇지 않으면 2단계로 이동합니다.
"골든 섹션" 방법의 계산 효율성은 각 반복에서 목적 함수 값의 단일 계산만 필요하다는 사실에 기인합니다.
직접 검색 방법(Hooke-Jeeves 방법). 일부
두 번째 시작점 X . 벡터 X의 구성 요소를 번갈아 변경하면서 이 점의 이웃을 조사한 결과 최소화된 함수 f(X)가 감소하는 방향을 결정하는 점(새 기준)을 찾습니다. 하강은 선택한 방향으로 수행되어 함수 값이 감소하는지 확인합니다. 이 절차는 허용된 정지 조건을 고려하여 하강 방향을 찾을 수 있을 때까지 주기적으로 반복됩니다.
가장 일반적인 형태의 직접 검색 방법의 알고리즘은 다음과 같이 공식화될 수 있습니다.
1. 좌표의 값으로 설정 x i , i= 1,2,…n , 시작점(k = 0), 좌표의 초기 증분 벡터
∆ X = (∆ x 1 , ∆ x 2 ,…, ∆ x n ) 근방을 측량하는 과정에서 ε 성분의 최소 허용값 ∆ X , 하강률을 결정하는 가속계수 λ ≥ 1, 스케일 팩터 d>1.
2. "오래된 기준"으로 X를 사용하십시오. X b \u003d X. 계산하다
값 에프(Xb).
3. 각 좌표를 번갈아 변경 x b i, i = 1,2, ... n,
포인트 X b 값 ∆ x i, 즉 x i \u003d x b i + ∆ x i를 취한 다음
x i \u003d x b i -∆ x i. 결과 테스트 포인트에서 f(X)의 값을 계산하고 f(Xb)의 값과 비교합니다. 만약 f(X)< < f
(X
б
), то соответствующая координата х
i
приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n
-й координаты f
(X
) 4. 그들은 후자를 통해 "이전" 기초에서 "신" 기초로 방향으로 하강합니다. 즉, 새 점의 좌표를 계산합니다. X: x i \u003d x i + λ (xi - x bi), i \u003d 1.2, ... n. f(X)의 값을 계산합니다. 조건 f(X) "새로운"기준은 "이전"기준으로 수락되고 (X b \u003d X, f (X b) \u003d f (X)) 5 단계로 이동합니다. 그렇지 않으면 xi \u003d xi, i \u003d 1.2, ... n . 5.
3항과 같이 점의 각 좌표를 번갈아 변경함수 f (X)의 해당 값을 4 단계에서 얻은 값 f (X)와 비교하여 X. 마지막 좌표를 변경 한 후 해당 값을 비교하십시오. 4단계에서 얻은 값 f(X b )를 사용하여 f(X ) 함수를 사용합니다. f(X ) 6. 모든 i ∆ x i에 대해<ε
, вычисления прекращаются. В противном случае уменьшают значения ∆
х
i
в d
раз и переходят к п. 3. 알고리즘의 작동은 그림에 설명되어 있습니다. 27. 표시된 라인 최소화된 함수 f(x 1 ,x 2 )의 수준, 즉 조건 f(x 1 ,x 2 )=f 1 =const, f(x 1 ,x 2 )=f 2 =const에서 얻은 라인 및 그래서 더. 여기서 f 1 >f 2 >f 3 . 실선은 단일 단계 실행 결과입니다. 3...5 (함수가 감소하는 방향을 찾아 하강) 점선이 다음 하강입니다. 직접 검색 방법의 장점은 컴퓨터 프로그래밍이 간단하다는 것입니다. 목적 함수에 대한 명시적인 지식이 필요하지 않으며 개별 변수에 대한 제한 사항과 검색 범위에 대한 복잡한 제한 사항도 쉽게 고려합니다. 직접탐색법의 단점은 고도로 길거나 휘어지거나 예리한 목적함수 준위선의 경우 분석방향의 한계로 인해 최소점까지 진척도를 제공하지 못할 수 있다는 점이다. 변형 가능한 다면체 방법(Nelder-Mead 방법) 그 기능을 최소화하기 위해 n 차원의 n 변수 f(X) 공간을 포함하는 다면체가 구성됩니다. N +1 탑. 분명히 각 정점은 어떤 벡터에 해당합니다.사이 . 목적 함수 값 계산 f(Xi), i=1,2,…, n +1, 다면체의 각 정점에서 이 값의 최대값과 해당 정점을 결정합니다. xh . 이 정점과 나머지 정점의 무게 중심을 통해 점이 위치한 돌출 선이 그려집니다. xq 상단보다 작은 목적 함수 값으로 Xh(그림 28, a ). 그런 다음 정점을 제거하십시오. xh . 나머지 정점과 점에서 xq 설명 된 절차가 반복되는 새 다면체를 만듭니다. 이러한 작업을 수행하는 과정에서 다면체의 크기가 변경되어 메서드 이름이 지정되었습니다. 다음 표기법을 소개합니다. X는 k번째 탐색 단계에서 다면체의 i번째 정점의 좌표 벡터, i= 1,2,…n +1, k= 1,2,…; h는 대상의 값이 있는 정점의 번호입니다. X를 제외한 타이어. 무게 중심의 좌표가 계산됩니다. xj[n + 2, k] = n+ 1 공식 ∑ xj[i, k] - xj[h, k] J= 1,2,…n. j=1 변형 가능한 다면체 방법에 대한 예시적인 알고리즘은 다음과 같습니다. 1.
반사 계수로 지정α, 장력 γ >1, 압축 β<1
, допустимой погрешностью определения координат 최소 ε 포인트. 원래 다면체 X , i= 1,2,…n +1, k= 1의 정점 좌표를 선택합니다. 2.
모든 정점에서 목적 함수 값 계산 f (X ), i = 1,2,…n +1, 점 X , X (그림 28에서 b 점은 각각 X 2 및 X 1 ) 및 X 를 찾습니다. 3.
포인트 투영 X의 중심을 통해 주석 : X \u003d X + α (X -X). 4. f(X) ≤ X이면 늘이기 작업을 수행합니다. 이온 : X \u003d X + γ (X -X). 그렇지 않으면 6단계로 이동합니다. 5.
새로운 다면체 만들기: if에프(X) X 를 X 로 교체하거나 X 를 X 로 교체합니다. k =k +1에 대해 항목 2로 계산을 계속합니다. 6. 모든 i에 대해 X >f(X)>X가 h와 같지 않으면, 압축 작업 수행: X =X +β (X – X). X를 X로 교체하여 새 다면체를 만들고 k =k +1에 대해 2단계부터 계산을 계속합니다. 7. f (X)>X이면 정점 X를 유지하면서 모든 모서리의 길이를 반으로 줄임으로써 현재와 유사한 새 다면체를 만듭니다. X \u003d X +0.5 (X -X) 및 k=k+1에 대해 2단계부터 계산을 계속합니다. 페이지에서 6, 7, 2단계로 진행하기 전에 조건에 따라 예를 들어 최소 검색을 완료하기 위한 조건의 충족 여부를 확인해야 합니다. 최대 보기 n ∑ + 1 (x j [ i ,k ] − x j [ n + 2,k ] ) 2< ε
2
. 나는 j = 1 에서 스트레칭 및 축소 작업을 통해 변형 가능한 다면체의 크기와 모양이 목적 함수의 지형에 맞게 조정됩니다. 결과적으로 다면체는 긴 경사면을 따라 늘어나고 구부러진 오목한 부분에서 방향이 바뀌며 고려되는 방법의 효율성을 결정하는 최소값 부근에서 수축됩니다. α =1, 2≤ γ ≤3, 0.4≤β ≤0.6. 좌표 회전 방법(Rosenbrock 방법). 그 본질은 목적 함수의 가장 빠른 감소 방향의 변화에 따라 좌표계의 연속적인 회전으로 구성됩니다 (그림 29). 출발지에서엑스 포인트로 내려오다엑스 좌표축에 평행한 방향으로. 다음 반복에서 축 중 하나는 다음 방향을 통과해야 합니다. x'1 = X–X, 나머지는 직각 방향으로 x'1 . 이 축을 따라 하강하면 지점으로 이어집니다.엑스 , 새로운 벡터를 구성할 수 있게 합니다. x''1 = X–X 이를 기반으로 새로운 검색 경로 시스템 X의 최소점. 에 다른 0차 방법과 달리 Rosenbrock 방법은 모든 방향의 고정 이동이 아니라 각 방향에서 최적의 점을 찾는 데 중점을 둡니다. 검색 프로세스의 단계 크기는 평평한 표면 지형에 따라 지속적으로 변경됩니다. 단계 제어와 좌표 회전의 조합은 복잡한 최적화 문제를 해결하는 데 Rosenbrock 방법을 효과적으로 만듭니다. 에 특히, 이 방법은 다른 많은 방법과 달리 소위 "협곡" 기능(매우 긴 레벨 표면 포함)을 최소화하는 데 효과적입니다. 결과 검색 방향이 "협곡" 축을 따라 위치하는 경향이 있기 때문입니다. 평행 접선 방법(Powell의 방법). 그 본질은 다음과 같이 목적 함수의 최소값에 대한 1차원 탐색을 순차적으로 수행하는 것입니다. n+1 방향 알려진 1차원 방법에서. 첫 번째 반복에서 첫 번째로 N 방향은 다음과 같이 선택된 좌표입니다.(n+1)번째 방향 중 첫 번째 방향이 사용됩니다(그림 30). 각 후속 반복에서 검색은 이전 반복의 두 번째 방향에서 각각 시작되며 방향의 수는 1씩 감소합니다.(n+1)번째 다음 반복의 방향은 벡터에 의해 제공됩니다. X–X[n+1] – 이전 반복의 첫 번째 단계에서 찾은 최소 지점에서 마지막 단계에서 찾은 최소 지점까지. 5.
다차원 최적화
선형 프로그래밍
최적화
적절한 조건에서 최상의 결과를 얻는 것으로 구성된 의도적인 활동입니다. 최적화되는 품질을 수량화하는 것을 호출합니다. 최적성 기준
또는 목적 함수
. 다음과 같이 작성할 수 있습니다. (5.1)
여기서 x 1 , x 2 , … 엑스엔최적화 개체의 일부 매개변수입니다. 무조건 및 조건의 두 가지 유형의 최적화 문제가 있습니다. 무조건 과제
최적화는 다음의 실제 함수(5.1)의 최대값 또는 최소값을 찾는 것으로 구성됩니다.N실제 변수 및 적절한 인수 값 결정. 조건부 최적화 문제
, 또는 제한이 있는 문제는 평등 또는 불평등의 형태로 인수의 값에 제한이 부과되는 형식의 문제입니다. 최적성 기준이 독립 변수의 선형 함수(즉, 이러한 변수를 1차까지 포함함)에 대한 선형 제약 조건이 있는 최적화 문제의 솔루션이 주제입니다. 선형 프로그래밍.
여기서 "프로그래밍"이라는 단어는 연구의 궁극적인 목표를 반영합니다. 최적의 계획 또는 최적의 프로그램을 결정하는 것입니다. 이에 따라 연구 중인 프로세스에 대한 많은 가능한 옵션 중에서 최상의 최적의 옵션이 선택됩니다. 예
그러한 작업은 원자재의 최적 분배 문제
최대 생산 비용으로 서로 다른 산업 사이. 두 가지 유형의 원료로 두 가지 유형의 제품을 만들 수 있습니다. 의미: x 1 , x 2 - 각각 첫 번째 및 두 번째 유형의 제품 단위 수 c1, c2 는 각각 첫 번째 유형과 두 번째 유형의 제품 단가입니다. 그러면 모든 제품의 총 비용은:
(5.2)
생산의 결과 총생산비용이 최대가 되는 것이 바람직하다.R(×1,×2 )는 이 문제의 목적 함수입니다. b1, b2 - 사용 가능한 첫 번째 및 두 번째 유형의 원료 양아이즈– 단위 수 나
한 단위를 생산하는 데 필요한 원재료의 유형제이제품 유형. 이 리소스의 소비가 총량을 초과할 수 없다는 점을 고려하여 리소스에 대한 제한 조건을 작성합니다. (5.3)
변수에 대하여 x1, x2 우리는 또한 그것들이 음수가 아니고 무한하다고 말할 수 있습니다.: (5.4)
불평등 시스템 (5.3) 및 (5.4)에 대한 솔루션 세트 중에서 그러한 솔루션을 찾는 것이 필요합니다 ( x1, x2 ), 기능아르 자형가장 높은 값에 도달합니다. 소위 운송 작업 (최소한의 운송 비용으로 다양한 창고에서 여러 목적지로 상품, 원자재 또는 제품을 배달하는 최적의 조직 작업) 및 기타 여러 작업이 유사한 형태로 공식화됩니다. 선형 프로그래밍 문제를 해결하기 위한 그래픽 방법입니다.
찾도록 요구하자 x1 및 x2 , 만족스러운불평등 시스템: (5.5)
및 조건 비음성:
(5.6)
~을 위한 어떤 기능 (5.
7
)
최대치에 도달합니다. 결정.
직교 좌표계를 구축합시다× 1 황소 2 문제에 대한 실행 가능한 솔루션 영역 (그림 11). 이를 위해 각 부등식(5.5)을 등식으로 대체하여 다음을 구성합니다. 관련 있는그에게 경계선: (나 = 1, 2, … ,
아르 자형)
쌀. 열하나 이 선은 전체 평면을 두 개의 반쪽 평면으로 나눕니다. 좌표용 x1, x2 어떤 지점 그리고하나의 반평면에서 다음과 같은 부등식이 성립합니다. 그리고 어떤 점의 좌표 에다른 반 평면, 반대 부등식: 경계선의 모든 점의 좌표는 다음 방정식을 충족합니다. 주어진 부등식에 해당하는 반평면이 경계선의 어느 쪽에 있는지 확인하려면 한 지점(가장 간단한 지점)을 "테스트"하면 됩니다. 영형(0;0)). 그 좌표를 부등식의 좌변에 대입하여 만족하면 반평면을 검사점 쪽으로 돌리고, 부등식을 만족하지 못하면 해당 반평면을 반대 방향으로 돌린다. 반평면의 방향은 해칭으로 도면에 표시됩니다. 불평등: 세로축의 오른쪽과 가로축 위에 위치한 반평면에 해당합니다. 그림에서 모든 부등식에 해당하는 경계선과 반평면을 구성합니다. 이 모든 반평면의 공통 부분(교차점)은 이 문제에 대한 실행 가능한 솔루션의 영역이 될 것입니다. 실행 가능한 솔루션의 도메인을 구성할 때 변수에 대한 특정 유형의 제약(부등식) 시스템에 따라 다음 네 가지 경우 중 하나가 발생할 수 있습니다. 쌀. 12. 실행 가능한 솔루션 영역이 비어 있으며 이는 불평등 시스템의 불일치에 해당합니다. 해결책 없음 쌀. 13. 허용 가능한 솔루션 영역은 시스템에 대한 유일한 솔루션에 해당하는 하나의 지점 A로 표시됩니다. 쌀. 14. 가능한 솔루션의 영역은 제한되어 있으며 볼록한 다각형으로 표시됩니다. 가능한 솔루션은 무궁무진합니다 쌀. 15. 허용되는 솔루션의 영역은 볼록한 다각형 영역의 형태로 무제한입니다. 가능한 솔루션은 무궁무진합니다 목적 함수의 그래픽 표현 고정된 값으로아르 자형직선을 정의하고 변경할 때아르 자형- 매개변수가 있는 평행선 계열아르 자형. 직선 중 하나에 있는 모든 점에 대해 함수 아르 자형하나의 명확한 값을 취하므로 이러한 라인을 호출합니다. 레벨 라인
R 함수의 경우. 그라데이션 벡터:
수직레벨 라인에, 증가 방향을 보여줍니다아르 자형.
부등식 시스템(5.5)에 대한 최적 솔루션을 찾는 문제는 목적 함수가아르 자형(5.7) 최대값에 도달하고 가능한 솔루션 영역에서 매개변수의 가장 큰 값에 해당하는 레벨 라인이 통과할 지점을 결정하도록 기하학적으로 감소합니다.아르 자형 쌀. 열여섯 실현 가능한 솔루션의 도메인이 볼록 다각형인 경우 함수의 극한값아르 자형
이 다각형의 정점 중 적어도 하나에 도달합니다. 극한값인 경우아르 자형두 정점에 도달하면 이 두 정점을 연결하는 세그먼트의 모든 지점에서 동일한 극단값에 도달합니다. 이 경우 작업에 다음이 있다고 합니다. 대체 최적
.
무한 영역의 경우 함수의 극한아르 자형존재하지 않거나 영역의 꼭짓점 중 하나에 도달하거나 대체 최적이 있습니다. 예.
값을 찾는 데 필요하도록 하십시오. x1 및 x2 , 불평등 시스템을 만족: 및 조건 비음성:
~을 위한 기능: 최대치에 도달합니다. 결정.
각 부등식을 등식으로 바꾸고 경계선을 구성해 보겠습니다. 쌀. 17 점(0;0)을 "테스트"하여 이러한 부등식에 해당하는 반평면을 결정하겠습니다. 고려 비음성 x1 및 x2 우리는 볼록 다각형의 형태로 이 문제에 대한 가능한 해결책의 영역을 얻습니다. OAVDE.
실현 가능한 솔루션 영역에서 기울기 벡터를 구성하여 최적의 솔루션을 찾습니다. 전시오름차순 방향아르 자형.
최적의 솔루션은 점에 해당합니다. 에, 좌표는 그래픽으로 또는 경계선 AB 및 VD에 해당하는 두 방정식의 시스템을 풀어서 결정할 수 있습니다. 답변:
× 1 = 2; 엑스 2 \u003d 6; Rmax = 22.
작업.
극한점의 위치와 목적함수의 극한값 찾기 주어진 제한 하에서. 표 9 익스트림 미디엄 도끼 최대 ;
;
;
;
최적화는 특정 기능의 극한값(전체 최대값 또는 최소값)을 찾거나 가능한 다양한 옵션 중에서 최상의(최적) 옵션을 선택하는 프로세스입니다. 최상의 옵션을 찾는 가장 신뢰할 수 있는 방법은 가능한 모든 옵션(대안)을 비교 평가하는 것입니다. 대안의 수가 많으면 일반적으로 수학적 프로그래밍 방법을 사용하여 최상의 대안을 찾습니다. 문제에 대한 엄격한 진술이 있는 경우 이러한 방법을 적용할 수 있습니다. 변수 집합이 설정되고 가능한 변경 영역이 설정되고(제한이 설정됨) 목적 함수의 유형(극한값이 있는 함수) 필요) 이러한 변수의 결정됩니다. 후자는 목표 달성 정도를 평가하기 위한 정량적 척도(기준)입니다. 제한 없는 최적화의 문제는 제한이 없는 상태에서 함수의 최소값 또는 최대값을 찾는 것입니다. 대다수라는 사실에도 불구하고 실용적인 작업최적화에는 한계가 있으므로 제약 없는 최적화 방법에 대한 연구는 여러 관점에서 중요합니다. 제약 조건이 있는 문제를 해결하기 위한 많은 알고리즘에는 문제를 제약 조건이 없는 최적화 문제 시퀀스로 줄이는 작업이 포함됩니다. 또 다른 종류의 방법은 적절한 방향을 찾고 이 방향을 따라 후속 최소화를 기반으로 합니다. 비제약적 최적화 방법의 정당성은 자연스럽게 제약 조건이 있는 문제를 해결하기 위한 절차의 정당성으로 확장될 수 있습니다. 조건부 최적화의 문제는 n차원 벡터 인수의 스칼라 함수 f(x)의 최소값 또는 최대값을 찾는 것입니다. 문제의 솔루션은 각 반복에서 증분 x1, ..., xn을 결정하기 위한 목적 함수의 선형 또는 2차 근사를 기반으로 합니다. 비선형 문제를 해결하기 위한 근사 방법도 있습니다. 이는 조각별 선형 근사법을 기반으로 하는 방법입니다. 솔루션을 찾는 정확도는 비선형 문제에 가능한 한 가까운 선형 문제에 대한 솔루션을 찾는 간격의 수에 따라 달라집니다. 이 방법을 사용하면 심플렉스 방법을 사용하여 계산을 수행할 수 있습니다. 일반적으로 선형 모델에서 목적 함수의 계수는 일정하며 변수 값에 의존하지 않습니다. 그러나 비용이 비선형적으로 볼륨에 따라 달라지는 문제가 많이 있습니다. 솔루션 알고리즘: 작업: 용량 최적화. 모래 저장을 위한 2750리터 컨테이너 제조 비용을 최소화합니다. Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5분; 여기서: X1 - 필요한 금속의 양, kg; C1 - 금속 비용, rub/kg; X2 - 필요한 전극의 질량, kg C2 - 전극 비용, rub/kg; X3 - 소비되는 전기량, kWh; C3 - 전기 비용, rub/kWh; X4 - 용접기 작업 시간, h; C4 - 용접기 관세율, rub/h; X5 - 리프트 작동 시간, h; C5 - 리프트 지불, 문지름 / h. 1. 용기의 최적 표면적 찾기: F = 2ab+2bh+2ah 분 (1) 여기서 V=2750리터. x1=16.331; x2=10.99 함수의 최소값은 Box 방법에 의한 최적화 과정에서 얻어졌습니다 - 1196.065 dm2 GOST 19903 - 74에 따라 다음을 허용합니다. h=16.50dm, b=10.00dm. (1)에서 a를 표현하고 다음을 얻습니다. 금속 시트의 최적 두께 계산 일반 탄소강 St2sp를 선택합시다 이 강 320MPa의 경우, ; 모래 덩어리. 가장 큰 면적의 탱크 벽에 가해지는 하중: 폭이 100cm인 시트의 1선형 센티미터당 하중을 계산합니다. 조건에 따라 벽 두께를 결정합니다. 여기서: l은 시트의 길이입니다(바람직하게는 떠나기 위해 가장 큰 것입니다. 추가 재고힘); q - 1선형 센티미터당 하중, kg/cm; 금속 시트의 두께, m 금속의 최대 허용 응력 N/mm2. (2)에서 벽 두께를 표현합니다. 320MPa = 3263kg/cm2라고 생각하면, 금속의 질량 여기서: F - 탱크 표면적, m2; 금속 벽 두께, m; 금속 밀도, kg/m3. St2sp 강철의 가격은 약 38 루블/kg입니다. 2. 용접 길이: 스테인레스 스틸 "UONI-13/45"용 전극을 사용하자 가격 88.66 루블 / kg; 여기서: Sweld - 용접 조인트의 단면적, m2; l은 용접 길이, m입니다. 증착된 금속의 밀도, kg/m3. 3. 용접 시간: 여기서 l은 용접 길이, m입니다. v - 용접 속도, m/h. 총 전력 소비: Рsum = 5 · 17 = 85kWh; 전기 비용은 5.7 루블 / kWh입니다. 4. 수동 아크 용접의 경우 작업장 서비스를 위한 보조, 준비 및 최종 시간과 시간의 비용은 평균 40~60%입니다. 평균값 50%를 사용하겠습니다. 총 시간: VI 카테고리 용접기 지불 - 270 루블 / 시간. 또한 환기가 잘 되지 않는 폐쇄된 공간에서 작업할 경우 17%의 관세 계수: 보조원의 급여는 용접공 급여의 60%입니다. 8055 0.6 = 4833 루블. 합계: 8055 + 4833 = 12888 루블. 5. 금속판을 용접, 적재 및 하역하는 동안 금속판과 완성된 용기 자체를 고정하려면 크레인이 필요합니다. 전체 구조를 "잡으려면" 용접기가 이음새의 약 30%를 적용해야 합니다. 크레인 지불 - 1000 루블 / 시간. 컨테이너의 총 비용입니다. CAD의 0차 최적화 방법 중 Rosenbrock 방법, 구성, 변형 가능한 다면체 및 무작위 검색 방법이 사용됩니다. 도함수를 사용하는 방법에는 최속강하법, 공액 기울기, 변수 메트릭 등이 있습니다. Rosenbrock의 방법은 좌표 하강법의 개선된 버전입니다. 좌표 하강 방법모든 좌표축을 따라 차례로 검색 방향을 선택하는 것을 특징으로 하는 단계는 1차원 최적화를 기반으로 계산되며, 검색 종료 기준 제어 매개변수. 제어된 매개변수의 2차원 공간의 예에 대한 좌표 방향 하강 궤적이 그림에 나와 있습니다. 1, 검색 궤적의 포인트는 제어 매개변수입니다. 목적 함수는 동일한 수준의 라인으로 표시되며 각 라인 근처에는 그에 해당하는 값이 기록됩니다. 분명히 최소 포인트가 있습니다. 쌀. 1. 좌표 하강 궤적 좌표 강하 방법을 사용할 때 검색이 극한 지점에서 멀리 떨어진 계곡 바닥에서 "고착"될 가능성이 높습니다. 무화과. 도 2는 계곡의 바닥에 위치한 지점을 친 후, 또는 의 방향으로만 추가 단계가 가능하지만 목적 함수의 열화로 이어진다는 것을 보여준다. 따라서 검색은 지점에서 끝납니다. 참고 1 협곡은 제어된 매개변수 공간의 일부로, 한 방향에서는 목적 함수의 도함수의 미약한 변화가 있고 다른 방향에서는 부호 변화와 함께 상당한 변화가 있습니다. 계곡 바닥에 속하는 지점에서 미분 부호가 변경됩니다. 쌀. 3. 좌표축 방향이 유리한 좌표 방향 하강 궤적 로젠브록 방법좌표축의 회전으로 구성되어 그 중 하나가 협곡 바닥과 준 평행하게 나타납니다. 이러한 회전은 일련의 좌표 하강 단계 후에 얻은 데이터를 기반으로 수행됩니다. 새 축의 위치는 이전 축의 선형 변환으로 얻을 수 있습니다. 축은 방향이 벡터와 일치합니다. 나머지 축은 서로 직교하는 조건에서 선택됩니다. 좌표 강하의 또 다른 성공적인 수정은 구성 방법(훅-지브스). 이 방법에 따르면, 좌표 강하의 일반적인 일련의 단계가 먼저 수행된 다음 그림 1과 같이 벡터 의 방향으로 추가 단계가 수행됩니다. 4, 벡터 방향으로 추가 단계가 수행되어 점으로 이어집니다. 쌀. 4. 구성 방법의 그림 극한값 찾기 변형 가능한 다면체 방법(Nelder-Mead)는 각 검색 단계에서 정점이 있는 다면체의 구성을 기반으로 합니다. 여기서 는 제어 매개변수 공간의 차원입니다. 검색 시작 시 이러한 꼭지점은 임의로 선택되며 이후 단계에서는 방법 규칙에 따라 선택됩니다. 이러한 규칙은 그림에 설명되어 있습니다. 2차원 최적화 문제의 예에서 5. 원래 삼각형의 정점이 선택됩니다: , , . 새로운 꼭짓점은 최악의 꼭짓점에서 가져온 광선에 있습니다(가 있는 꼭짓점에서 최고 가치목적 함수) 다면체의 무게 중심을 통해 , 와 같은 거리에서 선택하는 것이 좋습니다. 새로운 탑이 최악의 탑을 대체합니다. 다면체의 꼭짓점 중에서 목적함수의 값이 가장 좋은 것으로 밝혀지면 거리를 늘린다. 그림에서 이것은 정확히 상황이며 증가는 포인트를 제공합니다. 꼭지점이 있는 새 다면체에서 최악의 꼭지점은 입니다. 새 정점이 더 나쁜 것으로 판명되면 최상의 정점을 다면체에 유지하고 모든 가장자리의 길이를 예를 들어 반으로 줄여야 합니다(다면체를 최상의 정점으로 축소). 다면체의 크기를 일정 한계로 줄이는 조건이 충족되면 검색이 중지됩니다. 단계는 1차원 최적화를 사용하여 최적으로 선택됩니다. 최속강하법을 사용하는 경우 대부분의 다른 방법과 마찬가지로 협곡 상황에서 검색 효율성이 크게 떨어집니다. 수색 궤적은 협곡 바닥을 따라 극단을 향해 천천히 진행되는 지그재그 모양을 취합니다. 그라디언트 방법의 효율성을 높이기 위해 몇 가지 트릭이 사용됩니다. 에서 사용하는 방법 중 하나 켤레 기울기 방법(Fletcher-Reeves 방법이라고도 함)은 벡터의 접합 개념을 기반으로 합니다. 벡터 및 는 벡터의 크기와 같은 차수의 양의 정부정사각 행렬이고 (공액의 특수한 경우는 차수의 항등 행렬일 때 벡터의 직교성입니다) 행인 경우 -공액이라고 합니다. 벡터는 열 벡터입니다. 2차 목적 함수의 문제에서 에 대한 켤레 방향의 특징은 다음과 같습니다. 켤레 방향을 따라 연속적으로 1차원 최소화하면 극단점을 단 단계로 찾을 수 있습니다. 노트 2 Hessian 행렬은 제어 매개변수에 대한 목적 함수의 2차 편미분 행렬입니다. 인접 방향에서 검색을 사용하는 이유는 일반 형식의 함수()에 대해 2차 근사법을 적용할 수 있으며 실제로는 검색을 여러 단계로 수행하는 것으로 해석됩니다. 극값 검색은 공식에 따라 수행됩니다. 단계는 1차원 최적화 조건을 기반으로 계산되므로 먼저 관계 검색 알고리즘은 계산 종료 조건이 충족될 때까지 공식 (3)을 적용하는 것으로 축소됩니다. 계수를 결정하려면 (3)과 (2)의 값을 (4)에 대입하여 방정식 (2)-(7)의 시스템을 풉니다. 프로세스가 수렴하면 적은 수의 반복으로 솔루션에 도달하며 끝은 조건 충족입니다. 그러므로 경향이 있음을 보여줄 수 있습니다. 단계가 끝나면 다시 시작해야 합니다.
제한
; 
;
; ;
;
;
;
;
;
;
;
;
;
;
;
;
어디에 계수입니다. 또한 결합 조건이 고려됩니다.
또는
어디
(6)과 (7)을 고려하여
식 (10)은 선형 대수 방정식의 시스템입니다. 루트는 솔루션에 대한 또 다른 근사치입니다.
어디
