목차
토마스 F. 러더퍼드, 콜로라도 대학교
요약
MILES는 비선형 상보성 문제 및 비선형 방정식 시스템에 대한 솔버입니다. MPSGE 또는 MCP 모델을 해결하기 위해 GAMS를 통해 솔버에 액세스할 수 있습니다. 이 문서에서는 솔루션 알고리즘, 사용자 옵션 및 솔버 출력을 문서화합니다. 이 문서의 목적은 MILES 사용자에게 솔버의 작동 방식에 대한 개요를 제공하여 효과적으로 사용할 수 있도록 하는 것입니다.
소개
MILES는 비선형 상보성 문제 및 비선형 방정식 시스템을 위한 Fortran 기반 솔버입니다. 해결 절차는 역추적 직선 탐색을 사용하는 일반화된 뉴턴 방법입니다. 이 코드는 경제적 균형 모델을 해결하기 위한 모델링 형식과 순차 방법을 제안한 Mathiesen(1985)이 조사한 알고리즘을 기반으로 합니다. 이 방법은 Robinson(1975), Hogan(1977), Eaves(1978) 및 Josephy(1979)가 제안한 알고리즘과 밀접한 관련이 있습니다. 이 구현에서 하위 문제는 상한과 하한이 암시적으로 표현되는 Lemke의 거의 상보적인 피벗 방식의 확장을 사용하여 선형 상보성 문제(LCP)로 해결됩니다. 선형 솔버는 Gill 등이 개발한 기저 인수분해 패키지 LUSOL을 사용합니다. (1991).
MILES가 적용될 수 있는 문제 클래스는 "일반화" 또는 "혼합" 상보성 문제라고 하며 다음과 같이 정의됩니다:
\[ \begin배열 rl \textrm주어진: & F:R^n \rightarrow R^n \ ,\ \ \ \ \ell ,u \in R^n \\ & \\ \textrm찾기: & z,w,v \in R^n \\ & \\ \textrm그러한 & F(z) = w - v \\ & \ell \leq z \leq u,\ \ w \geq 0,\ \ v \geq 0 \\ & w^T (z - \ell ) = 0\ , \ \ \ v^T (u-z) = 0. \\ \end배열
\(\ell=-\infty\) 및 \(u=\infty\) MCP가 비선형 방정식 시스템으로 축소될 때. \(\ell=0\) 및 \(u=+\infty\)인 경우 MCP는 비선형 상보성 문제입니다. 유한 차원 변이 부등식도 MCP입니다. MCP에는 특수한 경우로 부등식 제약이 있는 선형, 2차 및 비선형 프로그램이 포함되어 있지만 이러한 문제의 경우 표준 최적화 방법이 선호될 수 있습니다. 최적화 문제가 아닌 MCP 모델에는 다양한 종류의 흥미로운 수학 프로그램이 포함됩니다. MCP 공식의 구체적인 예는 여기에 제공되지 않습니다. 경제학에서 발생하는 MCP 공식에 대해서는 Rutherford(1992a)를 참조하십시오. 다른 예는 Harker와 Pang(1990) 및 Dirkse(1993)에서 제공됩니다.
MILES에 표시할 수 있는 GAMS 모델에는 두 가지 유형이 있습니다.
- MILES는 MPSGE가 GAMS 하위 시스템으로 생성한 계산 가능한 일반 평형 모델을 해결하는 데 사용될 수 있습니다. MPSGE 언어에서 모델 작성자는 GAMS 프로그램에 내장된 특수 표 형식 입력 형식을 사용하여 비선형 함수 클래스를 지정합니다. MPSGE는 벤치마크 수량과 가격을 사용하여 함수 계수를 자동으로 교정하고 비선형 방정식과 야코비 행렬을 생성합니다. 크고 복잡한 비선형 방정식 시스템은 MILES에 대한 이 인터페이스를 사용하여 매우 쉽게 구현 및 분석될 수 있습니다. GAMS/MPSGE를 사용한 일반 평형 모델링에 대한 소개는 Rutherford(1992a)에 의해 제공됩니다.
- MILES는 혼합 상보성 문제(MCP)에 대한 GAMS 솔버로 액세스할 수 있습니다. 둘 이상의 MCP 솔버를 사용할 수 있는 경우1)성명
옵션 MCP = 마일;GAMS에 MILES를 MCP 솔루션 시스템으로 사용하도록 지시합니다. MCP 형식을 사용하여 MILES에 문제가 제시되면 사용자는 GAMS 행렬 대수를 사용하여 비선형 함수를 지정하고 GAMS 컴파일러는 자동으로 야코비안 함수를 생성합니다. GAMS/MCP 모델링 형식에 대한 소개는 Rutherford(1992b)에서 제공합니다.
이 문서의 목적은 MILES 사용자에게 솔버 작동 방식에 대한 개요를 제공하여 프로그램을 보다 효과적으로 사용할 수 있도록 하는 것입니다. 섹션뉴턴 알고리즘뉴턴 알고리즘을 소개합니다. 섹션암시적 경계를 사용하는 Lemke의 방법선형 하위 문제를 해결하는 데 사용되는 Lemke 알고리즘의 구현을 설명합니다. 섹션옵션 파일옵션 파일을 사용하여 지정할 수 있는 스위치 및 허용 오차를 정의합니다. 섹션로그 파일 출력일반적으로 화면으로 전달되는 런타임 로그 파일을 해석합니다. 섹션상태 파일 출력상태 파일과 생성될 수 있는 자세한 반복 보고서를 해석합니다. 섹션해지 메시지비정상 종료 조건에 대한 해결 방법을 나열하고 제안합니다.
뉴턴 알고리즘
비선형 상보성 문제를 해결하기 위해 MILES 내에서 적용되는 반복 절차는 비선형 방정식에 대한 고전적인 뉴턴 알고리즘과 밀접하게 관련되어 있습니다. 이 섹션의 첫 번째 부분에서는 기존 절차를 검토합니다. 이러한 아이디어에 대한 철저한 소개는 Dennis와 Schnabel(1983)에 의해 제공됩니다. 실용적인 관점에 대해서는 Press et al. (1986).
비선형 방정식을 위한 뉴턴 알고리즘은 비선형 방정식 시스템의 국소(테일러 계열) 근사로 시작됩니다. \(\hatz\) 근처의 점 \(z\)에 대해 비선형 함수 시스템은 선형화됩니다.
\[ LF(z) = F( \barz ) + \nabla F( \barz ) (z - \barz ). \]
선형 시스템 \( LF(z) = 0 \)을 풀면 \( \barz \)로부터 뉴턴 방향이 제공되며 이는 \( d = - \nabla F^-1~F( \barz ).\)로 제공됩니다.
뉴턴 반복 \(k\)은 \(z^k\) 지점에서 시작됩니다. 먼저, \(z^k\)에서 형성된 선형 모델을 풀어 관련 "뉴턴"을 결정합니다.
방향", \( d^k\). 둘째, \(d^k\) 방향의 선 검색은 스칼라 스텝 길이와 후속 반복을 결정합니다: \( z^k+1 = z^k + \lambda d^k \). Armijo 또는 "역추적" 행 검색은 처음에 \(\lambda = 1\)을 고려합니다. \(\| F(z^z + \lambda d^k)\| \leq \| F(z^k) \| \)이면 단계 크기 \( \lambda \)가 채택되고, 그렇지 않으면 양의 계수 \(\alpha \), \(\alpha < 1\)가 곱해지고 수렴 테스트가 다시 적용됩니다. 이 절차는 개선 결과가 나오거나 \(\lambda < \underline\lambda \)가 될 때까지 반복됩니다. \(\underline\lambda = 0\)일 때 다음과 같은 경우 긍정적인 조치가 취해집니다.2):
\[ \fracd d \lambda \| F(z^k + \lambda d^k) \| < 0. \]
이 알고리즘에 대한 수렴 이론은 상당히 잘 발달되어 있습니다. 예를 들어 Ortega와 Rheinbolt(1970) 또는 Dennis와 Schnabel(1983)을 참조하세요. 역추적 선 탐색을 사용하는 뉴턴 방식의 가장 매력적인 측면은 잘 동작하는 고정점 근처에서 \(\lambda =1\)이 최적의 단계 길이이고 수렴 속도가 2차일 수 있다는 것입니다. 이 방법으로 해결책을 찾으면 매우 빠르게 해결됩니다.
비선형 상보성 문제에 뉴턴 방법을 적용하려면 검색 방향을 수정해야 합니다. 여기서 \(d\)는 a를 해결합니다.선형 상보성 문제(LCP)는 선형 방정식 시스템이 아닙니다. 반복 \(k\)의 경우 \(d\)는 다음을 해결합니다.
\[ F(z^k) + \nabla F(z^k) d - w + v = 0 \]
\[ \ell \leq d + z^k \leq u, \ \ w \geq 0,\ \ v \geq 0 \]
\[ w^T(d + z^k - \ell ) = v^T(u - d - z^k) = 0. \]
개념적으로 우리는 \(d\)를 풀고 있지만 실제로 MILES는 원래 변수 \(z = z^k + d\)의 관점에서 선형 문제를 해결합니다.
\[ F(z^k) - \nabla F(z^k) z_k + \nabla F(z^k) z = w - v \]
\[ \ell \le z \le u,\ \ w \geq 0,\ \ v \geq 0 \]
\[ w^T(z-\ell ) = 0\ ,\ \ \ v^T(u-z) = 0. \]
해법 \( z \)을 계산한 후 MILES는 \( d^k = z - z^k \)를 설정합니다.
선형 하위 문제는 모든 변수 또는 모든 변수의 상한 및 하한을 통합하여 반복 순서가 항상 경계 내에 유지되도록 보장합니다: ( \( \ell \le z^k \le u \)). 이는 종종 그렇듯이 \( F() \)가 일부 \( z \in R^n \)에 대해 정의되지 않은 경우 도움이 될 수 있습니다.
MCP에 적용된 뉴턴 알고리즘의 수렴은 세 가지 질문에 달려 있습니다:
- 선형화된 문제에는 항상 해결책이 있습니까?
- 선형화된 문제에 해결책이 있는 경우 Lemke의 알고리즘이 해결책을 찾습니까?
- 계산된 방향 \(d^k\)이 솔루션에 "개선"을 제공할 것임을 보여주는 것이 가능합니까?
제한된 기능 클래스 \(F()\)에 대해서만 세 가지 질문에 모두 긍정적으로 대답할 수 있습니다. 훨씬 더 큰 함수 클래스의 경우 알고리즘은 실제로 수렴하지만 수렴은 '증명 가능'하지 않습니다.3).
질문 3.에 대한 답은 개선을 측정하는 기준의 선택에 달려 있습니다. 경계 및 상보성 조건이 도입되면 오류 지수 계산이 더욱 복잡해집니다. MILES에서 후보 솔루션 \(z, \epsilon (z)\)과 관련된 편차는 \(z, w\) 및 \(v\)가 적용 가능한 상한 및 하한과 상보성 조건을 위반하는 정도에 대한 측정값을 기반으로 합니다.
수렴 평가
\(\delta^L_i \) 및 \(\delta^U_i \)를 \(z_i\)가 하한 또는 상한을 벗어났는지 여부에 대한 표시 변수로 둡니다. 이는 다음과 같이 정의됩니다.4):
\[ \delta^L_i = min(1, (z_i - \ell_i)^+) ~~\textrmand~~ \delta^U_i = min(1,(u_i-z_i)^+). \]
\(z\)가 주어지면 MILES는 \(F(z)\) 값을 사용하여 슬랙 변수 \(w\) 및 \(v\)를 암시적으로 정의합니다.
\[ w_i = F_i(z)^+\ ,\ \ \ v_i = \biggl(-F_i(z) \biggr)^+ . \]
인덱스 \(i\)와 관련된 오류 항에는 두 가지 구성 요소가 있으며, 그 중 하나는 \(z_i\)의 상한 및 하한 경계 위반에 해당합니다:
\[ \varepsilon_i^B = (z_i - u_i)^+ + (\ell_i - z_i)^+ \]
그리고 상보성 조건 위반에 해당하는 또 다른 것:
\[ \varepsilon_i^C = \delta_i^L w_i + \delta_i^U v_i. \]
그러면 z 지점에 할당된 오류가 발생합니다:
\[ \varepsilon (z) = \| \varepsilon^B(z) + \varepsilon^C(z) \| _p\]
미리 지정된 값 \(p = 1, 2\) 또는 \(+\infty \)에 대해.5).
암시적 경계를 사용하는 Lemke의 방법
혼합 선형 상보성 문제의 형식은 다음과 같습니다:
\[ \begin배열 rl \textrm주어진: & M \in R^n\times n, \ \ \ \ \ q,\ell ,u \in R^n \\ & \\ \textrm찾기: & z,w,v \in R^n \\ & \\ \textrm그러한 & 남 z + q = w - v , \\ & \ell \le z \le u,\ \ w \geq 0,\ \ v \geq 0, \\ & w^T (z - \ell ) = 0 \ ,\ \ \ v^T (u-z) = 0. \\ \end배열
반복 \(k\)의 뉴턴 하위 문제에서 LCP 데이터는 \(q = F(z^k) - \nabla F(z^k) z^k\) 및 \(M = \nabla F(z^k)\)로 제공됩니다.
일하는 Tableau
MILES에서 선형 문제를 해결하기 위한 피벗 방식은 다음 형식의 레이블이 다시 지정된 선형 시스템과 함께 작동합니다.
\f[ B x^B + N x^N = q , \f]
여기서 \( x^B \in R^n , \ \ \ x^N \in R^2n \) 이고 테이블 \([ B |N ]\)은 \([-M | \ I \ |-I ]\)의 등각 "상보 순열"입니다. 즉, \(B\)의 모든 열 \(i\)는 \(M, I\) 또는 \(-I\)의 \(i\)번째 열이어야 하며, \(N\)의 해당 열 \(i\) 및 \(i+n\)은 \(B\)에 대해 선택되지 않은 두 개의 열이어야 합니다.
\(z, w\) 및 \(v\)로 정의된 문제에서 \(x^B\) 및 \(x^N\)으로 정의된 문제로 이동하기 위해 다음과 같이 \(x^B\) 변수에 상한 및 하한을 할당합니다.
\[ \밑줄x _i^B = \왼쪽\ \begin배열 rcl \ell _i, & \texttt if & x_i^B = z_i \ \ \ \\ 0 , & \texttt if & x_i^B = w_i \texttt 또는 v_i , \end배열 \맞아. \]
\[ \overlinex _i^B = \왼쪽\ \begin배열 rcl u_i , & \texttt if & x_i^B = z_i \ \ \ \\ \infty,& \texttt if & x_i^B = w_i \texttt 또는 v_i \end배열 \맞아. \]
기본이 아닌 변수 \(x^N_i\) 및 \(x^N_i+n\)의 값은 \(x^B_i\) 할당에 의해 결정됩니다.
\[ x_i^B = \왼쪽\ \begin배열 rcl z_i & \오른쪽 화살표 & \왼쪽\ \begin배열 lcccl x_i^N & = & w_i & = & 0 \ \ \ \ \\ x_i+n^N & = & v_i & = & 0 \ \ \ \ \end배열 \right. \ \\ & & \\ w_i & \오른쪽 화살표 & \왼쪽\ \begin배열 lcccl x_i^N & = & z_i & = & \ell _i \ \ \ \ \\ x_i+n^N & = & v_i & = & 0 \ \ \ \ \end배열 \right. \\ & & \\ v_i & \오른쪽 화살표 & \왼쪽\ \begin배열 lcccl x_i^N & = & w_i & = & 0 \ \ \ \\ x_i+n^N & = & z_i & = & u_i . \end배열 \right. \end배열 \right . \]
즉, \(z_i\)가 기본이면 \(w_i\)와 \(v_i\)는 모두 0입니다. \(z_i\)가 하한에서 비기본이면 \(w_i\)는 0이 아닐 수 있고 \(v_i\)는 0에서 비기본입니다. \(z_i\)가 상한에서 비기본이면 \(v_i\)는 0이 아닐 수 있고 \(w_i\)는 0에서 비기본입니다.
개념적으로 우리는 다음 형식의 \(3^n\) 선형 시스템을 평가하여 LCP를 풀 수 있습니다.
\[ x^B = B^-1 \biggl( q - N x^N \biggr) . \]
Lemke의 피벗 알고리즘은 이러한 \(3^n\) 대체 선형 시스템의 일부(작은) 하위 집합을 순차적으로 평가하여 솔루션을 찾는 절차를 제공합니다.
초기화
\(B^0\)이 초기 기초 행렬을 나타냄6). 기본 변수의 초기 값은 다음과 같습니다.
\[ \hatx^B = (B^0)^-1 (q - N ~\hatx^N) . \]
만약 \(\underlinex^B \le \hatx^B \le \barx^B\) 이면 초기 기초가 가능하며 상보성 문제가 해결됩니다.7). 그렇지 않으면 MILES는 인공 변수 \(z_0\)와 인공 열 \(h\)를 도입합니다. 그러면 기본 변수는 다음과 같이 표현됩니다.
\[ x^B = \hatx^B - \tilde h z_0 , \]
여기서 \(\tilde h\)는 "변환된 인공 열"입니다(변형되지 않은 열은 \(h = B^0 \tilde h \)입니다). \(\tilde h\)의 계수는 다음과 같이 선택됩니다.
- "실행 가능한" 기본 변수의 값은 \(z_0\)의 영향을 받지 않습니다: ( \(\underlinex_i^B \le x_i^B \le \barx_i^B \Longrightarrow \tilde h_i = 0 \)).
- "가장 실현 불가능한" 기본 변수(\(i=p\))는 \(z_0 = 1\)일 때 상한 또는 하한으로 이동됩니다.
\[ \틸드 h_p = \왼쪽\ \begin배열 rcl \hatx_p^B - \barx_p^B ,& if & \tilde x_p^B > \barx_p^B \ \\ & & \\ \hatx_p^B - \underlinex_p^B ,& if & \tilde x_p^B < \underlinex_p^B \ . \end배열 \맞아. \]
- 기타 모두실행 불가능기본 변수는 \(z_0\)이 1로 증가할 때 상한과 하한 사이의 값을 가정합니다.
\[ x_i^B = \왼쪽\ \begin배열 rrrrrrrr 1 + \underlinex_i^B,& if & \underlinex_i^B > -\infty, & \barx_i^B = +\infty \ \ \\ \\ \frac \barx_i^B + \underlinex_i^B 2,& if & \underlinex_i^B > -\infty, & \barx_i^B < +\infty \ \ \\ \\ \barx_i^B - 1,&인 경우 & \underlinex_i^B = -\infty , & \barx_i^B < +\infty \ . \end배열 \맞아. \]
피버팅 규칙
\(z_0\)이 기저에 들어갈 때, 1의 값을 가정하고 이 시점에서(퇴화를 제외하고) 후속 피벗 순서가 완전히 결정됩니다. 한 번의 반복에서 입력 변수는 이전 반복에서 기존 기본 변수에 의해 결정됩니다. 예를 들어, \(z_i\)가 \(B^0\)에 있고 \(z_0\)을 도입하면 \(z_i\)가 하한으로 이동하고 후속 반복에서는 \(w_i\)가 도입됩니다. 반대로, \(w_i\)가 \(B^0\)에 있고 \(z_0\)으로 인해 \(w_i\)가 0으로 떨어지면 후속 반복에서는 \(\ell _i\)에서 \(z_i\)가 증가합니다. 마지막으로, \(v_i\)가 \(B^0\)에 있고 \(z_0\)의 도입으로 인해 \(v_i\)가 0으로 떨어지면 후속 반복감소\(z_i\)는 \(u_i\)에서.
표 1암시적 경계가 있는 Lemke 알고리즘의 피벗 시퀀스 규칙
| N | 변수 종료 중 | 변수 입력 중 | 기본이 아닌 값의 변경 |
|---|---|---|---|
| I | \(z_i\) 하한값 | \(w_i\)는 0에서 증가합니다. | \( x^N_i = z_i = \ell_i \) |
| II | \(z_i\) 상한 | \(v_i\)는 0에서 증가합니다. | \( x^N_i+n = z_i = u_i \) |
| III | \(w_i\) 0 | \(z_i\)는 \(\ell_i\)에서 증가합니다. | \( x^N_i = x^N_i+n = 0 \) |
| IV | \(v_i\) 0 | \(z_i\)는 \(u_i\)에서 감소합니다. | \( x^N_i = x^N_i+n = 0 \) |
피벗 규칙의 전체 집합은 표 1에 표시됩니다. 이 알고리즘과 원래 Lemke(유형 III) 피벗 방식(Lemke(1965), Garcia 및 Zangwill(1981) 또는 Cottle 및 Pang(1992) 참조) 간의 한 가지 차이점은 구조 변수(\(z_i\)'s)가 상한 값에서 기저에 들어가거나 나갈 수 있다는 것입니다. 따라서 알고리즘은 입력 변수가 하한에서 증가하는 피벗과 입력 변수가 상한에서 감소하는 피벗을 구별해야 합니다.
"일반적인" Lemke 피벗 절차와의 또 다른 차이점은 입력 구조 변수가 한 경계에서 다른 경계로 이동할 수 있다는 것입니다. 이런 일이 발생하면 후속 피벗에 해당하는 여유 변수가 도입됩니다. 예를 들어 기본 변수를 실행 불가능하게 유도하지 않고 \(z_i\)가 \(\ell _i\)에서 \(u_i\)로 증가하면 \(z_i\)는 \(u_i\)에서 비기본이 되고 후속 피벗은 \(v_i\)를 도입합니다. 이러한 유형의 피벗은 \(z_i\) 단일 단계에서 베이시스에 들어가고 나가는 것으로 해석될 수 있습니다.8).
이론적으로는 퇴화를 무시하는 것이 편리하지만 실제로는 퇴화를 피할 수 없습니다. 현재 알고리즘은 순환을 피하기 위해 사전 편찬 체계를 통합하지 않지만 둘 이상의 후보가 있는 경우 가장 안정적인 피벗에 우선 순위가 부여되도록 보장하는 비율 테스트 절차를 구현합니다. 허용되는 피벗 세트는 절대 피벗 허용오차(ZTOLPV) 및 상대 피벗 허용오차(ZTOLRP). 절대값이 \( min \)보다 작은 피벗이 없습니다. (ZTOLPV, ZTOLRP\(\| 브이 \|
) \)가 고려됩니다. 여기서 \(\| V\| \)는 들어오는 열의 표준입니다.
보조 광선 종료
Lemke의 알고리즘은 새로운 변수의 도입으로 \(z_0\)이 0이 될 때 정상적으로 종료됩니다. 이는 원하는 결과이지만 항상 그런 것은 아닙니다. 기본 변수가 들어오는 변수를 "차단"하지 않으면 알고리즘이 조기에 중단될 수 있습니다. 이 조건을 "보조 광선 종료"라고 합니다. 이러한 결과를 예상하여 MILES는 연속적인 반복에 대해 \(z_0\) 값에 대한 기록을 유지하고 가장 작은 관찰 값 \(z^*_0\)과 관련된 기본 정보를 저장합니다. (Lemke의 알고리즘에서 피벗 시퀀스는 \(z_0\)에 대한 영향을 고려하지 않고 결정되며 인공 변수의 값은 초기 값 1에서 최종 값 0까지 불규칙한(단조가 아닌) 경로를 따를 수 있습니다.)
MILES가 보조 광선을 발견하면 \(z^*_0\)과 관련된 기본 변수 세트가 다시 설치되는 재시작 절차가 호출됩니다. 이 기저(\(z_0\)를 대체하기 위해 비기본 삼중항의 한 열로 추가됨)는 \(B^0\) 역할을 하며 알고리즘이 다시 시작됩니다. 어떤 경우에는 이 절차를 통해 피벗 시퀀스가 솔루션으로 원활하게 계속되는 반면 다른 경우에는 다른 보조 광선으로만 이어질 수 있습니다.
옵션 파일
표준 GAMS 옵션(예:iterlim, 레스림)을 사용하여 MILES를 제어할 수 있습니다. 자세한 내용은 섹션을 참조하세요.GAMS 옵션을 통해 솔버 제어.
또한 솔버 옵션 파일을 사용하여 MILES 관련 옵션을 지정할 수 있습니다. 옵션 파일의 내용은 솔버마다 다르지만, 옵션 파일을 생성하고 솔버에게 이를 사용하도록 지시하는 방법에 대한 세부 정보는 그렇지 않습니다. 이 주제는 섹션에서 다룹니다.솔버 옵션 파일.
다음은 일반적인 MILES 옵션 파일입니다:
ITLIMT = 50 제어 = 1.0E-8 루시즈 = 16
이 섹션의 나머지 부분에서는 MILES 옵션을 설명하고 기본값을 제공합니다.
로그 파일 출력
로그 파일은 모니터링 진행을 허용하기 위해 화면에 표시하기 위한 것입니다. 상대적으로 적은 양의 출력이 생성됩니다.
샘플 반복 로그가 다음에 표시됩니다.표 2. 이 출력은 연속적으로 해결된 두 가지 사례에서 나온 것입니다. 이 출력과 후속 출력은 프로그램에서 나옵니다.TRNSP.FORMILES 라이브러리를 직접 호출합니다. (GAMS 내에서 MILES가 호출되면 한 번에 최대 하나의 사례가 처리됩니다.)
로그 출력의 첫 번째 줄은 MILES 프로그램 날짜 및 버전 정보를 제공합니다. 이 정보는 버그 신고에 중요합니다.
"작업 공간..."으로 시작하는 줄은 모델을 해결하기 위해 할당된 메모리 양을 보고합니다. 이 예에서는 10K입니다. 그 후 가장 큰 불균형(\(\epsilon ^B_i + \epsilon ^C_i \))과 관련된 변수 이름과 함께 초기 편차가 보고됩니다. 다음 줄은 수렴 허용 오차를 보고합니다.
0과 1로 시작하는 줄은 해당 반복에 대한 주요 반복 보고서입니다. 반복 번호 뒤의 숫자는 현재 편차이고 세 번째 숫자는 Armijo 단계 길이입니다. 관련 편차가 가장 큰 방정식을 보완하는 변수의 이름은 줄 끝에 괄호 안에 표시됩니다.
최종 반복 다음에는 반복, 리팩토링, 최종 편차에 대한 요약이 있습니다. 마지막 메시지는 솔루션 상태를 보고합니다. 이 경우 모델이 성공적으로 처리되었습니다('해결됨').
MILES(1993년 7월) Ver:225-386-02 토마스 F. 러더퍼드 경제학과 콜로라도대학교 이메일로만 기술 지원 제공: TOM@GAMS.COM 할당된 작업 공간 - 0.01Mb 초기편차...........3.250E+02 P_01 수렴 허용 오차 .... 1.000E-06 0 3.25E+02 1.00E+00 (P_01 ) 1 1.14E-13 1.00E+00 (W_02) 주요 반복 .............. 1 Lemke 피벗 ............. 10 리팩토링 ........ 2 편차 ............... 1.137E-13 해결되었습니다. 할당된 작업 공간 - 0.01Mb 초기 편차 ...........5.750E+02 W_02 수렴 허용 오차 .... 1.000E-06 0 5.75E+02 1.00E+00 (W_02) 1 2.51E+01 1.00E+00 (P_01) 2 4.53E+00 1.00E+00 (P_01) 3 1.16E+00 1.00E+00 (P_01 ) 4 3.05E-01 1.00E+00 (P_01) 5 8.08E-02 1.00E+00 (P_01) 6 2.14E-02 1.00E+00 (P_01) 7 5.68E-03 1.00E+00 (P_01) 8 1.51E-03 1.00E+00 (P_01) 9 4.00E-04 1.00E+00 (P_01) 10 1.06E-04 1.00E+00 (P_01) 11 2.82E-05 1.00E+00 (P_01) 12 7.47E-06 1.00E+00 (P_01) 13 1.98E-06 1.00E+00 (P_01) 14 5.26E-07 1.00E+00 (P_01) 주요 반복 .............. 14 Lemke 피벗 ............. 23 리팩토링 .............. 15 편차 ............... 5.262E-07 해결되었습니다.
상태 파일 출력
상태 파일은 로그 파일에 제공된 것보다 솔루션 프로세스에 관한 더 많은 세부 정보를 보고합니다. 일반적으로 이 파일은 디스크에 기록되고 문제가 발생할 경우에만 검사됩니다. GAMS 내에서 상태 파일은 GAMS 문 다음 목록에만 나타납니다.옵션 SYSOUT=ON;.
상태 파일에 대한 출력 수준은 솔버에 전달된 옵션에 따라 결정됩니다. 기본 구성에서 상태 파일은 모든 스위치 및 허용 오차의 세부 목록과 기저 분해 통계 보고서와 함께 로그 파일에 기록된 모든 정보를 수신합니다.
옵션 파일을 사용하여 출력 수준이 기본값에서 증가하면 상태 파일은 디버깅을 지원하기 위해 훨씬 더 많은 출력을 받을 수 있습니다.표 3 - 표 6생성된 상태 파일 표시LEVOUT=3(최대),PIVLOG=T및LCPECH=T.
상태 파일은 로그 파일과 동일한 헤더로 시작됩니다. 그 후 사용자 제공 옵션 파일이 제공되면 해당 파일이 완전히 에코 인쇄됩니다. 코어 할당 보고서 다음에는 현재 실행에 대해 지정된 제어 매개변수, 스위치 및 허용 오차에 대한 전체 에코 인쇄가 있습니다.
표 4상태 파일을 계속합니다. 변수 및 함수 값에 대한 반복별 보고서는 다음과 같이 생성됩니다.LEVOUT >= 2. 표 4에는 LCP 에코 프린트도 포함되어 있습니다. 이 보고서에는 $ROWS 및 $COLUMNS라는 두 개의 섹션이 있습니다. $ROWS 섹션의 숫자 열 4개는 상수 벡터( \(q\)), 관련 변수에 대한 수준 값의 현재 추정치( \(z\)), 하한 및 상한 벡터( \(\ell \) 및 \(u\))입니다. ROW와 \(Z\) 열 사이에 나타나는 문자 \(L\) 및 \(U\)는 각각 하한 및 상한에서 기본이 아닌 변수를 식별하는 데 사용됩니다. 이 예에서 모든 상한은 \(+\infty\) 이므로 상한에서 기본이 아닌 변수는 없습니다.
관례에 따라 상태 파일에는 변수(수식 이름은 아님)만 나타납니다. 방정식은 해당 변수로 식별됩니다. 따라서 행렬 echo-print의 $COLUMNS: 섹션에서 행 이름은 \(z\) 변수의 이름에 해당합니다. 변수 \(z_i\), \(w_i\) 및 \(v_i\)에 할당된 이름은 $COLUMNS 섹션에 표시된 대로 \(z - <\)name \(i>\), \(w - <\)name \(i>, \) 및 \(v - <\)name \(i> \)입니다. \(w -< >\) 및 \(v -< >\) 변수에 대한 0이 아닌 값은 \( -/+I \)로 간주되므로 표시되지 않습니다.
상태 파일 출력은 표 5에서 계속됩니다. 표의 전반부는 매트릭스 스케일링 절차의 출력을 보고하고 후반부는 Lemke 절차의 시작과 관련된 메시지를 보고합니다.
"lu6chk 경고"는 LUSOL 보고서입니다. 그 후 두 개의 인수분해 보고서가 있습니다. 여기서는 첫 번째 기저가 특이값이기 때문에 두 가지 인수분해가 수행되므로 프로그램은 초기 값 \(z\)로 정의된 행렬 대신 모든 하한 여유를 설치합니다.
두 번째 인수분해 보고서에 이어 표 5 하단에는 초기 피벗에 대한 요약이 있습니다. "3열에서는 불가능합니다." \(\tilde h\)에는 0이 아닌 요소가 3개 포함되어 있음을 나타냅니다. "최대 실행불가능성"은 구조 변수가 상한 또는 하한을 위반하는 최대량을 보고합니다. "3가지 요소를 갖춘 인공기둥." 이는 벡터 \(h = B^0 \tilde h\)에 3개의 요소가 포함되어 있음을 나타냅니다. (이 경우 초기 기초가 특이값이므로 \(B^0 = -I\)이므로 \(\tilde h\)와 \(h\)의 0이 아닌 개수가 동일하다는 점에 유의하세요.)
표 6상태 파일의 마지막 섹션을 표시합니다. 테이블 상단에는 Lemke 반복 로그가 있습니다. 열은 다음과 같이 해석됩니다.
ITER0으로 시작하는 반복 인덱스입니다.상태는 Lemke 경로의 효율성을 나타내는 통계입니다. 공식적으로 상태는 \(B_0\)에서 현재 베이시스까지의 최소 피벗 수를 실제 피벗 수로 나눈 비율입니다. 상태가 1이면 Lemke의 알고리즘은 직접 인수분해만큼 효율적으로 수행됩니다(기저 인수 업데이트의 오버헤드는 제외).Z%기본 열의 백분율이 "구조적"(\(z\)'s)임을 나타냅니다.Z0인공 변수의 값을 나타냅니다. 이 예에서 인공 변수는 초기 값인 1에서 단조롭게 감소합니다.오류은 인수분해 오류가 계산될 때 보고되는 열입니다. 이 실행에서는 ITCH=30이므로 인수분해 오류가 계산되지 않습니다.INFEAS은 인공 열(박스 노름을 사용하여 정의됨)에 의해 도입된 실현불가능성의 크기가 보고되는 열입니다. (MILES에서 커버 벡터 \(h\)는 1뿐만 아니라 0이 아닌 다양한 값을 포함합니다. 따라서 인공 변수의 크기와 유도된 실현불가능성의 크기 사이에 큰 차이가 있을 수 있습니다.피벗은 절대값(첫 번째 숫자)과 상대값(두 번째 숫자)으로 피벗 크기를 보고합니다. 상대 피벗 크기는 들어오는 열의 표준에 대한 피벗 요소의 비율입니다.입/출력모든 반복에 대해 들어오고 나가는 열의 인덱스(이름 아님)를 보고합니다. Lemke의 반복 로그는 기본을 종료하는 변수 \(z_0\)로 끝납니다.
반복 1에 대한 수렴 보고서는 로그 파일에 기록된 보고서와 다르지 않으며, 다음은 변수 및 함수 값에 대한 두 번째 보고서입니다. 여기서는 단일 하위 문제에 따라 솔루션이 얻어졌음을 알 수 있습니다. 이는 근본적인 문제가 실제로 선형적이기 때문입니다.
상태 파일(이 경우)은 로그 파일 보고서와 동일한 반복 요약과 전체 및 다양한 하위 작업 내에서 사용된 CPU 시간에 대한 요약으로 끝납니다. (마지막 5개 숫자의 합이 첫 번째 숫자에 합산되지 않더라도 놀라지 마십시오. 일부 주기는 정확하게 모니터링되지 않습니다.)
MILES(1993년 7월) 버전:225-386-02
토마스 F. 러더퍼드
경제학과
콜로라도대학교
이메일로만 기술 지원 제공: TOM@GAMS.COM
사용자 제공 옵션 파일:
>시작
> PIVLOG = .TRUE.
> LCPECH = .TRUE.
> 레브아웃 = 3
>끝
할당된 작업 공간 - 0.01Mb
NEWTON 알고리즘 제어 매개변수:
주요 반복 제한 ..(ITLIMT). 25
댐핑 팩터...........(DMPFAC). 5.000E-01
최소 스텝 길이 ....(MINSTP). 1.000E-02
편차의 표준 .....(NORM)... 3
수렴 내성 ..(CONTOL). 1.000E-06
LEMKE 알고리즘 제어 매개변수:
반복 제한 .......(ITERLIM). 1000
인수분해 빈도(INVFRQ). 200
타당성 공차 ..(ZTOLZE). 1.000E-06
계수 공차 ..(ZTOLDA). 1.483E-08
절대. 피벗 공차...(ZTOLPV). 3.644E-11
상대. 피벗 공차...(ZTOLRP). 3.644E-11
커버 벡터 공차 .(ZTOLZ0). 1.000E-06
매 반복마다 크기를 조정합니다...(SCALE). 티
재시작 한계 ..........(NRSMAX). 1
출력 제어 스위치:
LCP 에코 인쇄...........(LCPECH). 에프
LCP 덤프 ...........(LCPDMP). 티
Lemke 반전 로그 ......(INVLOG). 티
Lemke 피벗 로그 ....... (PIVLOG). 티
초기편차...........3.250E+02 P_01
수렴 허용 오차 .... 1.000E-06
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯
수렴 보고서, 반복 0
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
ITER 편차 단계
0 3.25E+02 1.00E+00 (P_01 )
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯반복 0 값.
행 ZF
-------- ------------ ------------
X_01_01L 0.00000E+00 -7.75000E-01
X_01_02 L 0.00000E+00 -8.47000E-01
X_01_03L 0.00000E+00 -8.38000E-01
X_02_01L 0.00000E+00 -7.75000E-01
X_02_02 L 0.00000E+00 -8.38000E-01
X_02_03L 0.00000E+00 -8.74000E-01
W_01 엘 0.00000E+00 3.25000E+02
W_02 엘 0.00000E+00 5.75000E+02
P_01 1.00000E+00 -3.25000E+02
P_02 1.00000E+00 -3.00000E+02
P_03 1.00000E+00 -2.75000E+02
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯
기능 평가, 반복: 0
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯
$행:
X_01_01 -2.25000000E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
X_01_02 -1.53000004E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
X_01_03 -1.61999996E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
X_02_01 -2.25000000E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
X_02_02 -1.61999996E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
X_02_03 -1.25999998E-01 0.00000000E+00 0.00000000E+00 1.00000000E+20
W_01 -3.25000000E+02 0.00000000E+00 0.00000000E+00 1.00000000E+00
W_02 -5.75000000E+02 0.00000000E+00 0.00000000E+00 1.00000000E+00
P_01 3.25000000E+02 1.00000000E+00 0.00000000E+00 1.00000000E+20
P_02 3.00000000E+02 1.00000000E+00 0.00000000E+00 1.00000000E+20
P_03 2.75000000E+02 1.00000000E+00 0.00000000E+00 1.00000000E+20
... 0.00000000E+00 0.00000000E+00 0.00000000E+00 0.00000000E+00
$열:
Z-X_01_01 W_01 -1.00000000E+00
P_01 1.00000000E+00
Z-X_01_02 W_01 -1.00000000E+00
P_02 1.00000000E+00
Z-X_01_03 W_01 -1.00000000E+00
P_03 1.00000000E+00
Z-X_02_01 W_02 -1.00000000E+00
P_01 1.00000000E+00
Z-X_02_02 W_02 -1.00000000E+00
P_02 1.00000000E+00
Z-X_02_03 W_02 -1.00000000E+00
P_03 1.00000000E+00
Z-W_01 X_01_01 1.00000000E+00
X_01_02 1.00000000E+00
X_01_03 1.00000000E+00
Z-W_02 X_02_01 1.00000000E+00
X_02_02 1.00000000E+00
X_02_03 1.00000000E+00
Z-P_01 X_01_01 -1.00000000E+00
X_02_01 -1.00000000E+00
Z-P_02 X_01_02 -1.00000000E+00
X_02_02 -1.00000000E+00
Z-P_03 X_01_03 -1.00000000E+00
X_02_03 -1.00000000E+00
... ... 0.00000000E+00LCP 데이터 확장
-------
최소 요소 최대 요소 최대 열 비율
0 이후 1.00E+00 1.00E+00 1.00
1 이후 1.00E+00 1.00E+00 1.00
2 이후 1.00E+00 1.00E+00 1.00
3 이후 1.00E+00 1.00E+00 1.00
확장 결과:
A(I,J) <= A(I,J) * R(I) / C(J)
행 행 Z 열 W 열 V 열
1 1.0000 1.0000 1.0000 1.0000
2 1.0000 1.0000 1.0000 1.0000
3 1.0000 1.0000 1.0000 1.0000
4 1.0000 1.0000 1.0000 1.0000
5 1.0000 1.0000 1.0000 1.0000
6 1.0000 1.0000 1.0000 1.0000
7 1.0000 1.0000 1.0000 1.0000
8 1.0000 1.0000 1.0000 1.0000
9 1.0000 1.0000 1.0000 1.0000
10 1.0000 1.0000 1.0000 1.0000
11 1.0000 1.0000 1.0000 1.0000
lu6chk 경고. 행렬은 특이 행렬인 것처럼 보입니다.
nrank = U의 8등급
n - nrank = 3등급 부족
nsing = 특이점 3개
jsing = 마지막 단수 열 10개
dumax = 1.00E+00 가장 큰 삼각형 대각선
dumin = 1.00E+00 가장 작은 삼각형 대각선
LUSOL 5.4 인수분해 통계
압축 0 메리트 0.00 LenL 0 LenU 14
0.00M 11 UT 11 D1 0 증가
L최대 0.0E+00 B최대 1.0E+00 U최대 1.0E+00 Umin 1.0E+00
성장 1.0E+00 LT 0 BP 0 D2 0
LUSOL 5.4 인수분해 통계
압축 0 메리트 0.00 LenL 0 LenU 11
0.00M 11 UT 11 D1 0 증가
L최대 0.0E+00 B최대 1.0E+00 U최대 1.0E+00 Umin 1.0E+00
성장 1.0E+00 LT 0 BP 0 D2 0
인공 기둥 건설
--- 3행에서는 불가능합니다.
--- 최대 실행 불가능성: 3.250E+02
--- 3가지 요소로 구성된 인공 기둥.
--- 행에서 피벗: 9를 열 20으로 대체
--- 피벗 요소: -3.250E+02LEMKE 피벗 단계
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
ITER 상태 Z% Z0 오류가 발생했습니다. ---- 피벗 ---- IN OUT
1 1.00 0 1.000 3.E+02 1.E+00 1 Z0 W 9
2 1.00 9 1.000 1.E+00 1.E+00 2 Z 9 W 1
3 1.00 18 0.997 9.E-01 9.E-01 1 Z 1 W 10
4 1.00 27 0.997 1.E+00 1.E+00 1 Z 10 W 2
5 1.00 36 0.996 9.E-01 4.E-01 1 Z 2 W 11
6 1.00 45 0.996 1.E+00 1.E+00 1 Z 11 W 6
7 1.00 55 0.479 2.E+00 1.E+00 1 Z 6 W 7
8 1.00 64 0.479 1.E+00 1.E+00 1 Z 7 W 4
9 1.00 73 0.000 1.E+00 1.E+00 2Z 4W 8
10 1.00 73 0.000 1.E-03 2.E-03 1V 8 Z0
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯
수렴 보고서, 반복 1
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
ITER 편차 단계
0 3.25E+02 1.00E+00
1 1.14E-13 1.00E+00 (W_02)
크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
반복 1 값.
행 ZF
-------- ------------ ------------
X_01_01 2.50000E+01 -8.32667E-17
X_01_02 3.00000E+02 -5.55112E-17
X_01_03L 0.00000E+00 3.60000E-02
X_02_01 3.00000E+02 -8.32667E-17
X_02_02L 0.00000E+00 8.99999E-03
X_02_03 2.75000E+02 2.77556E-17
W_01 1.00000E+00 -1.13687E-13
W_02 1.00000E+00 1.13687E-13
P_01 1.22500E+00 0.00000E+00
P_02 1.15300E+00 0.00000E+00
P_03 1.12600E+00 0.00000E+00
주요 반복 .............. 1
Lemke 피벗 ............. 10
리팩토링 ........ 2
편차 ............... 1.137E-13
해결되었습니다.
총 해결 시간: 0.6초
함수 및 야코비안..: 0.2초
LCP 용액 .......: 0.2초
리팩토링 ....: 0.1초
FTRAN ...............: 0.0초
업데이트 ..............: 0.1초해지 메시지
INVERT의 기본 인수분해 오류입니다.LUSOL이 예상치 못한 오류 코드를 반환했습니다. 이는 일반적으로 발생하지 않습니다. LUSOL의 메시지에 대한 상태 파일을 검사합니다.9)
수렴 실패.두 번의 연속 반복이 동일합니다. 뉴턴 검색 방향이 정의되지 않았습니다. 일반적으로 이런 일은 발생하지 않습니다.
일관되지 않은 매개변수ztolz0, ztolze. ztolz0커버 벡터 \(h\)에 로드된 가장 작은 값을 결정하는 반면ztolze는 Harris 피벗 선택 절차에 사용되는 타당성 허용 오차입니다. 만일ZTOLZ0 < -ZTOLZE, 초기 기초가 실현 가능하지 않기 때문에 Lemke의 알고리즘을 실행할 수 없습니다.
선형화를 위한 공간이 부족합니다.사용 가능한 메모리가 야코비 행렬에서 0이 아닌 값을 보관하는 데 부족합니다. 더 많은 메모리를 할당해야 합니다. Jacobi 행렬을 위한 공간이 충분하지 않으면 동일한 행렬의 LU 요소를 보유하기 위한 메모리가 너무 적습니다.
반전할 공간이 부족합니다.기본 요소에 더 많은 메모리를 할당해야 합니다. 값을 높이십시오.루사이즈옵션 파일에서 또는 더 큰 값을 할당<모델>.workspace.
반복 제한을 초과했습니다.이는 메이저(뉴턴) 또는 마이너(Lemke) 반복 제한을 초과한 결과일 수 있습니다. MILES가 GAMS에서 호출되면 누적 Lemke 반복 제한은 다음 명령문을 사용하여 설정할 수 있습니다.<모델>.iterlim = xx;. 뉴턴 반복 제한은 기본적으로 100이며, 다음을 통해서만 수정할 수 있습니다.itlimt옵션.
리소스 인터럽트.경과된 CPU 시간이 옵션 매개변수를 초과합니다.RESLIM. 이 한도를 늘리려면 다음 중 하나를 추가하세요.RESLIM= 옵션 파일의 xxx 또는 GAMS 문 추가<모델>.RESLIM = xxx;.
단일 행렬이 발견되었습니다.Lemke의 알고리즘은 열 교체 또는 리팩토링 중 기본 분해에서 발생하는 특이점으로 인해 중단되었습니다. 어떤 이유로 재시작이 불가능합니다.
보조 광선 종료.Lemke의 알고리즘이 보조 광선에서 종료되었습니다. 어떤 이유로 재시작이 불가능합니다.
알 수 없는 종료 상태.종료 상태 플래그가 설정되지 않았지만 코드가 중단되었습니다. 이전 메시지에 대한 상태 파일을 살펴보십시오. 이 종료 코드는 자주 발생하면 안 됩니다.
참고자료
K.J. Anstreicher, J. Lee 및 T.F. 러더퍼드 "최대치 충돌 무게 보완적 기초", 수학적 계획법. (1992)
A. Brooke, D. Kendrick 및 A. Meeraus "GAMS: 사용자 가이드", Scientific Press, (1987).
R.W. 코틀과 J.S. Pang "선형 상보성 문제", Academic Press, (1992).
J.E. Dennis 및 R.B. Schnabel "구속되지 않은 수치적 방법 최적화 및 비선형 방정식", Prentice-Hall(1983).
에스. Dirkse "혼합 상보성 문제의 강력한 솔루션", 위스콘신 대학교 컴퓨터 과학부(1992).
B.C. Eaves, "국소적으로 2차 수렴하는 알고리즘은 다음과 같습니다. 고정점 계산," Tech. 캘리포니아주 스탠포드 소재 스탠포드 대학교 운영 연구부 대표(1978).
P.E. 길, W. 머레이, M.A. 손더스, M.H. 라이트 "유지 일반 희소 행렬의 LU 요인", Linear Algebra and its Application 88/89, 239-270 (1991).
C.B. Garcia와 W.I. Zangwill "솔루션, 고정점, 및 균형", Prentice-Hall(1981)
P. 하커와 J.S. 팡 "유한차원 변이 불평등과 비선형 상보성 문제: 조사 이론, 알고리즘 및 응용", Mathematical Programme 48, pp. 161-220(1990).
W.W. Hogan, "프로젝트 독립성을 위한 에너지 정책 모델", Computation and Operations Research 2 (1975) 251-271.
N.H. Josephy, "일반화 방정식을 위한 뉴턴의 방법", 기술 요약 보고서 #1965, 수학 연구 센터, 위스콘신 대학교 - 매디슨(1979).
나. Kaneko, "n x 2n 'P'의 선형 상보성 문제- 행렬", 수학 계획법 연구 7, pp. 120-141, (1978).
C.E. Lemke "바이매트릭스 평형점과 수학적 프로그래밍", Management Science 11, pp. 681-689, (1965).
엘. Mathiesen, "수열에 의한 경제 균형 계산 선형 상보성 문제", 수학 계획법 연구 23(1985).
P.V. Preckel, "NCPLU 버전 2.0 사용자 가이드", 연구 보고서, 퍼듀 대학교 농업경제학과, (1987).
W.H. Press, B.P.Flannery, S.A. Teukolsky, W.T. Vetterling "수치적 레시피: 과학 컴퓨팅 기술", Cambridge University Press (1986).
J.M. 오르테가와 W.C. Rheinboldt, "비선형의 반복 솔루션 여러 변수의 방정식", Academic Press(1970).
S.M. Robinson, "일반에 대한 2차 수렴 알고리즘 비선형 계획법 문제", 수학 계획법 연구 3(1975).
T.F. Rutherford "변형 및 변형을 위한 GAMS 확장 경제 응용 분야의 상보성 문제 평형 분석", 콜로라도 대학교 경제학과 연구 보고서 92-7(1992a).
T.F. 러더퍼드(Rutherford)는 다음을 사용하여 일반균형 모형을 적용했습니다. GAMS 하위 시스템으로서의 MPS/GE", 콜로라도 대학 경제학과 연구 보고서 92-15(1992b).
표 7GAMS/MCP의 운송 모델(1/2 페이지)
*크레이지 슬롯>TRNSP.GMS
옵션 mcp=마일;
$TITLE 경제 균형으로 공식화된 LP 운송 문제
* 크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
* 이 파일에서 Dantzig의 원래 운송 모델은
* 선형 상보성 문제로 재구성되었습니다. 우리가 먼저
* 고정된 수요량과 공급량으로 모델을 해결하고,
* 그런 다음 양쪽에 가격 반응성을 통합합니다.
* 시장.
*
* T.Rutherford 3/91 (5/91 개정)
* 크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯크레이지 슬롯=
* 이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾는 문제입니다.
* 시장 요구사항 및 공장 공급품
*
* 참고자료:
* Dantzig, GB, 선형 계획법 및 확장
* 프린스턴 대학교 출판부, 뉴저지주 프린스턴, 1963년,
* 3-3장.
*
* 이 공식은 2장에서 자세히 설명됩니다.
* (Richard E. Rosenthal 작성) GAMS: 사용자 가이드.
* (A Brooke, D Kendrick 및 A Meeraus, The Scientific Press,
* 캘리포니아 레드우드 시티, 1988.
*
세트
I 통조림 공장 / 시애틀, 샌디에고 /
J 마켓 / NEW-YORK, CHICAGO, TOPEKA / ;
매개변수
A(I) 경우에 따른 공장i의 생산능력(가격이 단일일 때)
/ 시애틀 325
샌디에고 575 /,
(가격이 단일한 경우) 시장 j의 B(J) 수요
/ 뉴욕 325
시카고 300
토피카 275 /,
ESUB(J) 수요의 가격 탄력성(가격이 1과 동일할 때)
/ 뉴욕 1.5
시카고 1.2
토피카 2.0 /;
표 D(I,J) 거리(천 마일)
뉴욕 시카고 토피카
시애틀 2.5 1.7 1.8
샌디에고 2.5 1.8 1.4 ;
SCALAR F 화물(1,000마일당 케이스당 달러) /90/ ;
매개변수 C(I,J) 운송 비용은 케이스당 수천 달러입니다.
C(I,J) = F * D(I,J) / 1000 ;
PARAMETER PBAR(J) 수요 노드 J의 기준 가격;양수 변수
W(I) 공급 노드 i의 그림자 가격,
수요 노드 j의 P(J) 그림자 가격,
X(I,J) 케이스별 배송 수량;
방정식
SUPPLY(I) 공장 i의 공급 제한,
FXDEMAND(J)는 시장 j의 고정 수요,
PRDEMAND(J) 시장 j의 가격 반응 수요,
PROFIT(I,J) 영 이익 조건;
이익(I,J).. W(I) + C(I,J) =G= P(J);
SUPPLY(I).. A(I) =G= SUM(J, X(I,J));
FXDEMAND(J).. SUM(I, X(I,J)) =G= B(J);
PRDEMAND(J).. SUM(I, X(I,J)) =G= B(J) * (PBAR(J)/P(J))**ESUB(J);
* 방정식-변수 연관 사양을 포함하는 모델 선언:
모델 FIXEDQTY / PROFIT.X, SUPPLY.W, FXDEMAND.P/ ;
모델 평등 / PROFIT.X, SUPPLY.W, PRDEMAND.P/ ;
* 초기 추정치:
P.L(J) = 1; W.L(I) = 1;
PARAMETER REPORT(*,*,*) 요약 보고서;
MCP를 사용하여 FIXEDQTY를 해결합니다.
REPORT("고정됨",I,J) = X.L(I,J); REPORT("고정","가격",J) = P.L(J);
REPORT("FIXED",I,"가격") = W.L(I);
* 수요 함수를 교정합니다:
PBAR(J) = P.L(J);
* 고정 수요 균형을 재현:
MCP를 사용하여 평등을 해결합니다.
REPORT("EQUIL",I,J) = X.L(I,J); REPORT("균등","가격",J) = P.L(J);
REPORT("균등",I,"가격") = W.L(I);
"벤치마크 교정"을 표시하고 보고합니다.
* 반사실적 균형을 계산합니다.
C("시애틀","시카고") = 0.5 * C("시애틀","시카고");
MCP를 사용하여 FIXEDQTY를 해결합니다.
REPORT("고정됨",I,J) = X.L(I,J); REPORT("고정","가격",J) = P.L(J);
REPORT("FIXED",I,"가격") = W.L(I);
* 고정 수요 균형을 재현:
MCP를 사용하여 평등을 해결합니다.
REPORT("EQUIL",I,J) = X.L(I,J); REPORT("균등","가격",J) = P.L(J);
REPORT("균등",I,"가격") = W.L(I);
DISPLAY "시애틀-시카고 운송 비용 절감:", REPORT;
1)GAMS를 통해 사용할 수 있는 또 다른 MCP 솔버가 하나 있습니다: PATH(Ferris and Dirkse, 1992), 비교는 \ref UG_PATH_VS_MILES를 참조하세요.
2)α 그리고λ해당 사용자가 지정한 공차에 따라dmpfac그리고minstp각각.
3)Kaneko(1978)는 선형화된 하위 문제에 대한 일부 수렴 이론을 제공합니다.
4)다음에서x+= 최대(x,0)
5)매개변수p선택 가능 입력 매개변수 포함표준. 기본값은pis+무한대.
6)마일 단위로,B0초기에 할당된 값을 사용하여 선택됩니다. 에 대한z. 언제zI<= lI, 그럼xBI= wi'; 언제zI>= 당신I, 그럼xBI=vI; 그렇지 않으면xBI= zI
7)코드의 현재 버전은 단순히 설정합니다.B0= -I그리고xB= w사용자가 지정한 기준이 단수인 경우. 코드의 후속 버전에는 다음에 설명된 알고리즘이 통합됩니다. 특이점에 대처한 Anstreicher, Lee 및 Rutherford [1992].
8)모든 구조적 변수에 유한한 상한 및 하한이 적용되는 경우, 그럼 안돼zI변수는 동종 솔루션의 일부일 수 있습니다. 보조 광선에 인접해 있습니다. 그러나 이것이 2차 광선을 의미하는 것은 아닙니다. 모두 불가능합니다zI변수는 광선처럼 제한되어 있습니다. 그러면 다음으로 구성될 수 있습니다.wI그리고vI변수.
9)GAMS 내에 "OPTION SYSOUT=ON;" 줄을 삽입하세요. 해결 문 앞에 MILES 솔버 상태 파일을 통과시키기 위해 프로그램을 다시 제출하십시오. 목록에.