가우스-조던 방법. Gauss-Jordan 방법을 사용하여 선형 대수 방정식 시스템을 푸는 예. Excel의 Jordan-Gauss 변환 및 단순 방법

LP 문제를 해결하는 그래픽 방법에서 우리는 실제로 목적 함수의 값이 최대(최소)에 도달하는 정점을 불평등 시스템에 대한 해 집합의 경계에 속하는 정점 집합에서 선택했습니다. 변수가 두 개인 경우 이 방법은 완전히 직관적이며 문제에 대한 해결책을 빠르게 찾을 수 있습니다.

문제에 3개 이상의 변수가 있고 실제 경제 문제에서 이것이 바로 상황이라면 제약 시스템의 해결 영역을 시각화하기가 어렵습니다. 이러한 문제는 다음을 사용하여 해결됩니다. 단순 방법 또는 연속적인 개선 방법으로. 방법의 아이디어는 간단하며 다음과 같습니다.

특정 규칙에 따라 초기 참조 계획(제약 영역의 일부 꼭지점)을 찾습니다. 계획이 최적인지 확인합니다. 그렇다면 문제가 해결된 것입니다. 그렇지 않다면 또 다른 개선된 계획, 즉 또 다른 정점으로 넘어갑니다. 이 평면(이 꼭지점)의 목적 함수 값은 분명히 이전 것보다 더 좋습니다. 전환 알고리즘은 특정 계산 단계를 사용하여 수행되며, 이는 테이블 형식으로 편리하게 작성됩니다. 단순 테이블 . 정점의 수가 유한하기 때문에 유한한 수의 단계를 거쳐 최적의 솔루션에 도달합니다.

계획 작성 문제의 구체적인 예를 사용하여 단순 방법을 고려해 봅시다.

심플렉스 방법은 특수한 형태로 축소된 표준 LP 문제, 즉 기저, 양의 우변 및 비기본 변수로 표현된 목적 함수를 해결하는 데 적용 가능하다는 점을 다시 한 번 주목해 보겠습니다. 작업이 특별한 형태로 축소되지 않으면 추가 단계가 필요하며 이에 대해서는 나중에 설명하겠습니다.

이전에 모델을 구축하고 이를 특별한 형태로 가져온 생산 계획의 문제를 고려해 보겠습니다.

일.

제품 제조용 ㅏ그리고 안에창고는 80단위 이하의 원자재를 방출할 수 있습니다. 또한, 제품 생산을 위해 ㅏ 2개 단위가 소모되고, 제품은 안에- 원자재 1개 단위. 제품을 생산할 경우 최대의 이익이 보장되도록 생산계획을 세워야 한다. ㅏ 50개 이하의 제품을 생산해야 하며, 안에- 40개 이하 또한, 한 제품의 판매로 인한 이익은 ㅏ- 5루블부터 안에- 3 문지름.

다음을 나타내는 수학적 모델을 만들어 보겠습니다. 엑스계획에 있는 제품 A 수량 1개, 엑스 2 - 제품 수 안에. 그러면 제약 조건 시스템은 다음과 같습니다.

추가 변수를 도입하여 문제를 정식 형식으로 가져오겠습니다.

(3.10)

F = -5x 1 - 3x 2 → 최소.

이 문제는 특별한 형식을 갖습니다(기저를 사용하면 오른쪽이 음수가 아님). 심플렉스(Simplex) 방법을 사용하여 해결할 수 있습니다.

나단계.심플렉스 테이블에 문제를 기록합니다. 문제의 제약 조건 시스템(3.10)과 심플렉스 테이블 사이에는 일대일 대응이 있습니다. 테이블에는 제약 조건 시스템의 등식만큼 많은 행이 있고 자유 변수만큼 많은 열이 있습니다. 기본 변수는 첫 번째 열을 채우고, 자유 변수는 표의 맨 위 행을 채웁니다. 최종선은 인덱스 라인이라고 불리며, 목적 함수의 변수 계수가 그 안에 기록됩니다. 함수에 사용 가능한 멤버가 없으면 오른쪽 하단에 처음에 0이 기록됩니다. 있다면 반대 기호로 쓰십시오. 이 위치(오른쪽 하단)에는 한 테이블에서 다른 테이블로 이동할 때 절대값이 증가하는 목적 함수 값이 있습니다. 따라서 표 3.4는 제한 시스템에 해당하며 솔루션의 단계 II로 넘어갈 수 있습니다.

표 3.4

기초적인			무료

II단계. 최적성을 위한 참조 계획을 확인합니다.

이 표 3.4는 다음 참조 계획에 해당합니다.

(엑스 1 , 엑스 2 , 엑스 3 , 엑스 4 , 엑스 5) = (0, 0, 50, 40, 80).

자유변수 엑스 1 , 엑스 2는 0과 같습니다. 엑스 1 = 0, 엑스 2 = 0. 그리고 기본 변수 엑스 3 , 엑스 4 , 엑스 5 가치를 취하다 엑스 3 = 50, 엑스 4 = 40, 엑스 5 = 80 - 자유 용어 열에서. 목적 함수 값:

-에프 = - 5엑스 1 - 3엑스 2 = -5 0 - 3 0 = 0.

우리의 임무는 주어진 참조 계획이 최적인지 확인하는 것입니다. 이렇게 하려면 인덱스 라인, 즉 대상 기능 라인을 살펴봐야 합니다. 에프.

다양한 상황이 가능합니다.

1. 인덱스에서 에프- 문자열에 음수 요소가 없습니다. 이는 계획이 최적이며 문제에 대한 해결책을 기록할 수 있음을 의미합니다. 목적 함수는 반대 부호를 사용하여 오른쪽 하단 모서리에 있는 숫자와 동일한 최적 값에 도달했습니다. IV 단계로 넘어가겠습니다.

2. 인덱스 행에는 양수 요소가 없는 열의 음수 요소가 하나 이상 있습니다. 그런 다음 목적 함수는 다음과 같다고 결론을 내립니다. 에프→무한히 감소합니다.

3. 인덱스 행에는 해당 열에 하나 이상의 양수 요소가 있는 음수 요소가 있습니다. 그런 다음 다음 단계 III으로 넘어갑니다. 테이블을 다시 계산하여 참조 계획을 개선합니다.

III단계. 참조 계획 개선.

인덱스의 음수 요소에서 에프-행, 모듈러스가 가장 큰 것을 선택하고 해당 열 해결을 호출하고 ""로 표시합니다.

해결 행을 선택하려면 자유 용어 열의 요소 비율을 계산해야 합니다. 오직에게 긍정적인해결 열의 요소입니다. 얻은 관계에서 최소 하나를 선택합니다. 최소값에 도달하는 해당 요소를 분해라고 합니다. 사각형으로 강조하겠습니다.

우리의 예에서는 , 요소 2는 허용됩니다. 이 요소에 해당하는 라인을 분해라고도 합니다(표 3.5).

표 3.5

허용 요소를 선택하면 규칙에 따라 테이블을 다시 계산합니다.

1. 이전과 같은 크기의 새로운 테이블에서 해결 행과 열의 변수가 교체되는데, 이는 새로운 베이시스로의 전환에 해당합니다. 우리의 예에서는: 엑스대신 1이 기본에 포함됩니다. 엑스 5는 기본을 벗어나 이제 무료입니다(표 3.6).

표 3.6

기초적인			무료

2. 분해 요소 2 대신에 역수를 쓰십시오.

3. 해상도선의 요소를 해상도 요소로 나눕니다.

4. 해결란의 요소를 해결요소로 나누어 반대부호로 표기합니다.

5. 표 3.6의 나머지 요소를 채우기 위해 직사각형 규칙을 사용하여 다시 계산합니다. 위치 50에 있는 요소의 개수를 계산한다고 가정해 보겠습니다.

우리는 이 요소를 해결 요소와 정신적으로 연결하고, 곱을 찾고, 결과 직사각형의 다른 대각선에 있는 요소의 곱을 뺍니다. 그 차이를 해결 요소로 나눕니다.

그래서, . 50이 있던 곳에 10을 씁니다. 마찬가지로 :

, , , .

표 3.7

우리는 새로운 테이블 3.7을 가지고 있으며 기본 변수는 이제 변수 (x 3,x 4,x 1)입니다. 목적 함수의 값이 -200이 되었습니다. 즉, 감소했습니다. 이 기본 솔루션의 최적성을 확인하려면 다시 단계 II로 이동해야 합니다. 프로세스는 분명히 유한합니다. 중지 기준은 단계 II의 지점 1과 2입니다.

문제 해결을 완료해 보겠습니다. 이를 위해 인덱스 라인을 확인하고 그 안에 음수 요소가 있으면 해당 열 해결을 호출하고 단계 III에 따라 테이블을 다시 계산해 보겠습니다. 관계를 컴파일하고 그 중 최소 = 40을 선택한 후 해결 요소 1을 결정했습니다. 이제 규칙 2-5에 따라 재계산을 수행합니다.

표 3.8

기초적인			무료
	x 3 = 30, 엑스 2 = 40, 엑스 1 = 20. 자유 변수는 0, 엑스 5 = 0, 엑스 4 = 0. 목적 함수는 반대 기호가 있는 자유 항 열의 마지막 요소 값을 사용합니다. - 에프 = -220 에프 = 220, 이 예에서는 함수가 min에서 검사되었으며 처음에는 에프 max이므로 부호는 실제로 두 번 변경되었습니다. 그래서, 엑스* = (20, 40, 30, 0, 0), 에프* = 220. 문제에 대한 답: 생산 계획에 해당 유형의 제품 20개를 포함해야 합니다. ㅏ, B 유형의 제품 40개, 이익은 최대이며 220 루블과 같습니다. 이 섹션의 끝 부분에는 단계를 정확히 반복하는 단순 방법 알고리즘의 순서도가 제시되지만 화살표는 작업의 명확한 방향을 나타내기 때문에 일부 독자에게는 사용하기가 더 편리할 것입니다. 순서도의 상자 위에 있는 링크는 해당 변환 그룹이 속한 단계 또는 하위 지점을 나타냅니다. 초기 참조 계획을 찾는 규칙은 단락 3.7에서 공식화됩니다. 자제력을 위한 질문 1. 심플렉스 테이블은 어떻게 구성되나요? 2. 베이시스의 변화는 표에 어떻게 반영되나요? 3. 단순 방법에 대한 중지 기준을 공식화합니다. 4. 테이블 재계산을 구성하는 방법은 무엇입니까? 5. 테이블 재계산을 시작하는 것이 편리한 라인은 어디입니까?

. 심플렉스 방법 알고리즘

예제 5.1.심플렉스 방법을 사용하여 다음 선형 프로그래밍 문제를 해결합니다.

해결책:

나 반복:

x3, x4, x5, x6 x1,x2. 기본 변수를 자유 변수로 표현해 보겠습니다.

목적 함수를 다음 형식으로 줄여보겠습니다.

얻은 문제를 바탕으로 초기 심플렉스 테이블을 구성합니다.

표 5.3

원래 심플렉스 테이블

				평가 관계

기본 솔루션의 정의에 따르면 자유 변수는 0과 같고 기본 변수의 값은 자유 숫자의 해당 값과 같습니다. 즉:

3단계: PAP 제한 시스템의 호환성 확인.

이 반복(표 5.3)에서는 제약 시스템의 불일치 기호(부호 1)가 식별되지 않습니다(즉, 음의 자유 숫자가 있는 선이 없습니다(목적 함수의 선 제외). 적어도 하나의 음수 요소(즉, 자유 변수에 대한 음수 계수)여야 합니다.

이 반복(표 5.3)에서는 목적 함수의 무한성 기호(부호 2)가 식별되지 않았습니다(즉, 목적 함수 행에 음수 요소가 있는 열이 없습니다(자유 숫자 열 제외). ) 여기에는 적어도 하나의 긍정적 요소가 없습니다) .

발견된 기본 용액에는 부정적인 성분이 포함되어 있지 않으므로 허용됩니다.

6단계: 최적성 확인.

최적성 기준(부호 4)에 따라 목적 함수 라인에 음수 요소가 없어야 하기 때문에 발견된 기본 솔루션은 최적이 아닙니다(이 기준을 고려할 때 이 라인의 자유 개수는 고려되지 않습니다). 따라서 단순법 알고리즘에 따라 8단계로 넘어갑니다.

찾은 기본 솔루션이 허용되므로 다음 구성표에 따라 해결 열을 검색합니다. 목적 함수 행에서 음수 요소가 있는 열을 결정합니다(자유 숫자 열 제외). 표 5.3에 따르면 다음과 같은 두 개의 열이 있습니다. x1" 및 열 " x2" 이러한 열 중에서 대상 함수 행의 가장 작은 요소를 포함하는 열이 선택됩니다. 그녀는 허용적인 사람이 될 것입니다. 열 " x2"는 열과 비교하여 가장 작은 요소(-3)를 포함합니다. " x1

분해 선을 결정하기 위해 분해 열의 요소에 대한 자유 숫자의 양수 추정 비율을 찾습니다. 가장 작은 양수 평가 비율에 해당하는 선이 분해된 것으로 받아들여집니다.

표 5.4

원래 심플렉스 테이블

표 5.4에서 가장 작은 긍정적 평가 관계는 " x5"그러므로 허용됩니다.

활성화 열과 활성화 행의 교차점에 위치한 요소는 활성화로 승인됩니다. 이 예에서 이것은 "선의 교차점에 위치한 요소입니다. x5" 및 열 " x2».

해결 요소에는 새로운 "향상된" 기저 솔루션으로 이동하기 위해 심플렉스 테이블에서 교체해야 하는 하나의 기저와 하나의 자유 변수가 표시됩니다. 이 경우 변수는 다음과 같습니다. x5그리고 x2, 새로운 단순 테이블(표 5.5)에서 이를 교환합니다.

9.1. 해결 요소의 변환.

표 5.4의 분해능 요소는 다음과 같이 변환됩니다.

결과 결과를 표 5.5의 유사한 셀에 입력합니다.

9.2. 해상도 문자열 변환.

표 5.4의 해결 행 요소를 이 심플렉스 테이블의 해결 요소로 나눕니다. 결과는 새로운 심플렉스 테이블(표 5.5)의 유사한 셀에 맞습니다. 해상도 문자열 요소의 변환은 표 5.5에 나와 있습니다.

9.3. 해상도 열의 변환입니다.

표 5.4의 분해능 열의 요소를 이 심플렉스 테이블의 분해능 요소로 나누고 그 결과를 반대 부호로 취합니다. 얻은 결과는 새로운 단순 표(표 5.5)의 유사한 셀에 적합합니다. 해결 열 요소의 변환은 표 5.5에 나와 있습니다.

9.4. 단순 테이블의 나머지 요소 변환.

단순 테이블의 나머지 요소(즉, 해결 행과 해결 열에 위치하지 않은 요소)의 변환은 "직사각형" 규칙에 따라 수행됩니다.

예를 들어, "선의 교차점에 위치한 요소를 변환하는 것을 고려해 보십시오. x3" 및 열 "", 조건부로 표시하겠습니다 " x3" 표 5.4에서 우리는 정신적으로 직사각형을 그립니다. 그 중 하나의 꼭지점은 우리가 변환하는 값의 셀에 있습니다(즉, 셀 " x3"), 다른 하나(대각선 정점)는 해결 요소가 있는 셀에 있습니다. (두 번째 대각선의) 다른 두 정점은 고유하게 결정됩니다. 그런 다음 셀의 변환된 값 " x3"는 이 셀의 이전 값에서 분수를 뺀 값과 같습니다. 분모는 해결 요소(표 5.4 참조)이고 분자는 사용되지 않은 다른 두 정점의 곱입니다. 즉:

« x3»: .

다른 셀의 값도 비슷하게 변환됩니다.

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

이러한 변환의 결과로 새로운 단순 테이블이 얻어졌습니다(표 5.5).

II 반복:

1단계: 단순 테이블 작성.

표 5.5

심플렉스 테이블II 반복

				추정된 관계

2단계: 기본 솔루션 결정.

단순 변환의 결과로 새로운 기본 솔루션이 얻어졌습니다(표 5.5).

보시다시피, 이 기본 솔루션을 사용하면 목적 함수의 값이 15로 이전 기본 솔루션보다 큽니다.

표 5.5의 특징 1에 따른 제한 시스템의 불일치는 확인되지 않았습니다.

4단계: 목적 함수의 경계를 확인합니다.

표 5.5의 기준 2에 따른 목적 함수의 무한성은 밝혀지지 않았습니다.

5단계: 발견된 기본 솔루션의 허용 가능성을 확인합니다.

기준 4에 따라 발견된 기본 솔루션은 최적이 아닙니다. 왜냐하면 심플렉스 테이블(표 5.5)의 목적 함수 라인에 음수 요소가 포함되어 있기 때문입니다. -2(이 라인의 자유 개수는 이를 고려할 때 고려되지 않습니다.) 특성). 그러므로 8단계로 넘어갑니다.

8단계: 분해 요소 결정.

8.1. 해결 열의 정의.

발견된 기본 솔루션은 허용됩니다. 목적 함수 행에서 음수 요소가 있는 열을 결정합니다(자유 숫자 열 제외). 표 5.5에 따르면 다음과 같은 열이 하나만 있습니다. x1" 따라서 우리는 이를 허용된 것으로 받아들입니다.

8.2. 활성화 문자열의 정의입니다.

표 5.6에서 얻은 긍정적 평가 관계의 값에 따르면 최소값은 " x3" 따라서 우리는 이를 허용된 것으로 받아들입니다.

표 5.6

심플렉스 테이블II 반복

				추정된 관계
				3/1=3 – 최소

9단계: 단순 테이블의 변환.

단순 테이블(표 5.6)의 변환은 이전 반복과 동일한 방식으로 수행됩니다. 단순 표의 요소 변환 결과는 표 5.7에 나와 있습니다.

III 반복

이전 반복의 단순 변환 결과를 기반으로 새로운 단순 테이블을 구성합니다.

표 5.7

심플렉스 테이블III 반복

				추정된 관계

2단계: 기본 솔루션 결정.

단순 변환의 결과로 새로운 기본 솔루션이 얻어졌습니다(표 5.7).

3단계: 제한 시스템의 호환성 확인.

표 5.7의 특징 1에 따른 제한 시스템의 불일치는 확인되지 않았습니다.

4단계: 목적 함수의 경계를 확인합니다.

표 5.7의 기준 2에 따른 목적 함수의 무한성은 밝혀지지 않았습니다.

5단계: 발견된 기본 솔루션의 허용 가능성을 확인합니다.

기준 3에 따라 발견된 기본 솔루션은 음수 구성 요소를 포함하지 않으므로 허용됩니다.

6단계: 발견된 기본 솔루션의 최적성을 확인합니다.

기준 4에 따라 발견된 기본 솔루션은 최적이 아닙니다. 왜냐하면 심플렉스 테이블(표 5.7)의 목적 함수 라인에 음수 요소가 포함되어 있기 때문입니다: -3(이 라인의 자유 개수는 이를 고려할 때 고려되지 않습니다) 특성). 그러므로 8단계로 넘어갑니다.

8단계: 분해 요소 결정.

8.1. 해결 열의 정의.

발견된 기본 솔루션은 허용됩니다. 목적 함수 행에서 음수 요소가 있는 열을 결정합니다(자유 숫자 열 제외). 표 5.7에 따르면 다음과 같은 열이 하나만 있습니다. x5" 따라서 우리는 이를 허용된 것으로 받아들입니다.

8.2. 활성화 문자열의 정의입니다.

표 5.8에서 얻은 긍정적 평가 관계의 값에 따르면 최소값은 " x4" 따라서 우리는 이를 허용된 것으로 받아들입니다.

표 5.8

심플렉스 테이블III 반복

				추정된 관계
				5/5=1 – 최소

9단계: 단순 테이블의 변환.

단순 테이블(표 5.8)의 변환은 이전 반복과 동일한 방식으로 수행됩니다. 단순 표의 요소 변환 결과는 표 5.9에 나와 있습니다.

IV 반복

1단계: 새로운 단순 테이블 구성.

이전 반복의 단순 변환 결과를 기반으로 새로운 단순 테이블을 구성합니다.

표 5.9

심플렉스 테이블IV 반복

				추정된 관계
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2단계: 기본 솔루션 결정.

단순 변환의 결과로 표 5.9에 따라 새로운 기본 솔루션이 얻어졌으며 솔루션은 다음과 같습니다.

3단계: 제한 시스템의 호환성 확인.

표 5.9의 특징 1에 따른 제한 시스템의 불일치는 확인되지 않았습니다.

4단계: 목적 함수의 경계를 확인합니다.

표 5.9의 기준 2에 따른 목적 함수의 무한성은 밝혀지지 않았습니다.

5단계: 발견된 기본 솔루션의 허용 가능성을 확인합니다.

기준 3에 따라 발견된 기본 솔루션은 음수 구성 요소를 포함하지 않으므로 허용됩니다.

6단계: 발견된 기본 솔루션의 최적성을 확인합니다.

기능 4에 따라 발견된 기본 솔루션은 단순 테이블의 목적 함수 라인에 음수 요소가 없기 때문에 최적입니다(표 5.9)(이 기능을 고려할 때 이 라인의 자유 개수는 고려되지 않음). .

7단계: 솔루션의 대안성을 확인합니다.

발견된 해는 목적 함수의 라인에 0 요소가 없기 때문에 독특합니다(표 5.9)(이 특성을 고려할 때 이 라인의 자유 개수는 고려되지 않습니다).

답변: 고려중인 문제의 목적 함수의 최적 값 = 24에서 달성됩니다.

예제 5.2.목적 함수가 최소화되는 경우 위의 선형 계획법 문제를 해결하십시오.

해결책:

나 반복:

1단계: 초기 심플렉스 테이블의 형성.

원래의 선형 계획법 문제는 표준 형식으로 제공됩니다. 각 부등식 제약 조건에 음이 아닌 변수를 추가하여 정식 형식으로 만들어 보겠습니다.

결과 방정식 시스템에서 허용된(기본) 변수를 사용합니다. x3, x4, x5, x6, 그러면 자유 변수는 다음과 같습니다. x1,x2. 기본 변수를 자유 변수로 표현해 보겠습니다.

심플렉스 방법을 사용한 ZLP의 해법을 고려하고 이를 최대화 문제와 관련하여 제시해 보겠습니다.

1. 문제의 조건에 따라 수학적 모델이 컴파일됩니다.

2. 완성된 모델은 표준형식으로 변환됩니다. 이 경우 초기 참조 계획의 기반을 식별할 수 있습니다.

3. 문제의 정식 모델은 모든 자유항이 음수가 아니도록 단순표 형식으로 작성됩니다. 초기 참조 계획이 선택된 경우 5단계로 진행합니다.

심플렉스 테이블(Simplex table): 제약 방정식 시스템과 목적 함수가 초기 기준을 기준으로 해결된 표현식 형식으로 입력됩니다. 목적 함수 F의 계수가 기록되는 행을 F-행 또는 목적 함수 행이라고 합니다.

4. F-행 요소의 부호를 고려하지 않고 최소 단순 관계에 해당하는 양의 분해 요소를 사용하여 단순 변환을 수행하여 초기 참조 계획을 찾습니다. 변환 중에 자유항을 제외한 모든 요소가 0인 0행이 나타나면 문제에 대한 제약 방정식 시스템이 일관성이 없습니다. 자유 항 외에 다른 양수 요소가 없는 0행을 만나면 제한 방정식 시스템에는 음수가 아닌 해가 없습니다.

시스템 (2.55), (2.56)을 새로운 기반으로 줄이는 것을 단순 변환이라고 합니다. 단순 변환을 형식적인 대수 연산으로 간주하면 이 연산의 결과로 특정 선형 함수 시스템에 포함된 두 변수 사이에 역할이 재분배된다는 것을 알 수 있습니다. 즉, 한 변수는 종속 변수에서 독립 변수로 바뀌고 다른 변수는 종속 변수로 이동합니다. , 반대로 독립에서 종속으로. 이 연산은 대수학에서 조던 소거 단계(Jordan Elimination Step)로 알려져 있습니다.

5. 발견된 초기 지원 계획의 최적성을 검사합니다.

a) F-행에 부정적인 요소가 없으면(자유 기간은 계산하지 않음) 계획이 최적입니다. 0이 없으면 최적의 계획은 하나만 있습니다. 0이 하나 이상 있으면 최적 계획의 수는 무한합니다.

b) F-행에 양수가 아닌 요소의 열에 해당하는 음수 요소가 하나 이상 있는 경우<

c) F-행에 하나 이상의 음수 요소가 있고 해당 열에 하나 이상의 양수 요소가 있는 경우 최적의 항목에 더 가까운 새 참조 계획으로 이동할 수 있습니다. 이렇게 하려면 지정된 열을 해결 열로 지정하고 최소 단순 비율을 사용하여 해결 행을 찾아 단순 변환을 수행해야 합니다. 결과 참조 계획의 최적성을 다시 검사합니다. 설명된 프로세스는 최적의 계획이 얻어질 때까지 또는 문제의 해결 불가능성이 확립될 때까지 반복됩니다.

기저에 포함된 변수에 대한 계수 열을 해결이라고 합니다. 따라서 F-행의 음수 요소를 기반으로 기저에 도입된 변수를 선택(또는 해결 열 선택)함으로써 함수 F가 증가하도록 보장합니다.

기저에서 제외할 변수를 결정하는 것이 조금 더 어렵습니다. 이를 위해 해결 열의 양수 요소에 대한 자유 항의 비율(이러한 관계를 심플렉스라고 함)을 구성하고 그 중에서 가장 작은 것을 찾아 제외된 변수가 포함된 행(해석)을 결정합니다. 최소 단순 관계에 따라 기초에서 제외된 변수의 선택(또는 해결 선의 선택)은 이미 설정된 대로 새 참조 계획에서 기초 구성 요소의 긍정성을 보장합니다.

알고리즘의 3번 항목에서는 자유항 열의 모든 요소가 음수가 아닌 것으로 가정합니다. 이 요구 사항은 필수는 아니지만 충족되면 이후의 모든 단순 변환은 양수 분해 요소로만 수행되므로 계산이 편리합니다. 자유 조건 열에 음수가 있는 경우 해결 요소는 다음과 같이 선택됩니다.

1) 일부 음수 자유 항에 해당하는 행(예: t-행)을 살펴보고 그 안에 있는 일부 음수 요소를 선택하면 해당 열이 해결되는 것으로 간주됩니다(문제의 제약 조건이 일관적이라고 가정합니다).

2) 자유 용어 열의 요소와 동일한 부호를 갖는 해결 열의 해당 요소(단순 관계)와의 관계를 구성합니다.

3) 단순 관계 중 가장 작은 관계를 선택합니다. 이에 따라 활성화 문자열이 결정됩니다. 예를 들어 p-문자열이라고 가정해 보겠습니다.

4) 해결 열과 행의 교차점에서 해결 요소가 발견됩니다. y 행의 요소가 해결되는 것으로 판명되면 단순 변환 후 이 행의 자유 항이 양수가 됩니다. 그렇지 않으면 다음 단계는 t-문자열로 돌아갑니다. 문제를 해결할 수 있는 경우 특정 단계를 거친 후에는 자유 용어 열에 부정적인 요소가 남지 ​​않습니다.

초기 참조 계획 찾기, ZLP의 표준 보기

솔루션의 순차적 개선 아이디어는 선형 프로그래밍 문제를 해결하기 위한 보편적인 방법, 즉 단순 방법 또는 계획의 순차적 개선 방법의 기초를 형성했습니다.

단순 방법의 기하학적 의미는 제약 다면체의 한 꼭지점(초기 정점이라고 함)에서 인접한 정점으로의 순차적 전환으로 구성됩니다. 여기서 선형 함수는 다음과 관련하여 최상의(적어도 최악은 아님) 값을 취합니다. 문제의 목표; 최적의 솔루션을 찾을 때까지 - 목표 함수의 최적 값이 달성되는 정점입니다(문제에 최종 최적이 있는 경우).

단순 방법은 1949년 미국 과학자 J. Danzig에 의해 처음 제안되었지만 1939년에 이 방법의 아이디어는 러시아 과학자 L.V. 칸토로비치.

모든 선형 계획법 문제를 해결할 수 있는 심플렉스 방법은 보편적입니다. 현재는 컴퓨터 계산에 사용되지만 단순법을 사용한 간단한 예제는 수동으로 풀 수 있습니다.

단순 방법을 구현하려면(솔루션의 지속적인 개선) 세 가지 주요 요소를 숙지해야 합니다.

문제에 대한 초기의 실행 가능한 기본 솔루션을 결정하는 방법입니다.

최상의(더 정확하게는 나쁘지 않은) 솔루션으로의 전환 규칙

발견된 솔루션의 최적성을 확인하는 기준입니다.

단순법을 사용하려면 선형 계획법 문제를 정규 형식으로 줄여야 합니다. 즉, 제약 조건 시스템은 방정식의 형태로 표현되어야 합니다.

문헌에서는 초기 참조 계획(허용 가능한 초기 기본 솔루션) 찾기, 인공 기반 방법 사용, 최적 참조 계획 찾기, 심플렉스 테이블을 사용하여 문제 해결에 대해 충분히 자세히 설명합니다.

58. 단순 방법의 주요 정리.

???????????????????????????????????????????????????????????????????????

59. ZLP의 대안적 최적, ZLP의 퇴화.

선형 계획법 문제의 퇴화

단순법을 고려할 때 선형 계획법 문제는 퇴화되지 않는다고 가정했습니다. 즉, 각 지원 계획에는 정확히 m개의 양수 구성 요소가 포함됩니다. 여기서 m은 문제의 제약 조건 수입니다. 퇴화된 지원 계획에서 긍정적인 구성 요소의 수는 제한 사항의 수보다 적은 것으로 나타납니다. 주어진 지원 계획에 해당하는 일부 기본 변수는 0 값을 갖습니다. 가장 간단한 경우에 대한 기하학적 해석을 사용하면 n - m = 2(비기저 변수의 개수는 2)일 때 퇴화 문제와 비퇴화 문제를 쉽게 구별할 수 있습니다. 축퇴 문제에서는 조건 다면체의 한 꼭지점에서 두 개 이상의 직선이 교차하며 xi = 0 형식의 방정식으로 설명됩니다. 이는 조건 다각형의 하나 이상의 변이 점으로 축소됨을 의미합니다. 마찬가지로, 축퇴 문제의 n - m = 3인 경우, 3개 이상의 평면이 한 꼭지점 xi = 0에서 교차합니다. 문제가 축퇴되지 않는다는 가정하에

베이시스(베이시스에서 파생된 변수)에서 파생된 조건 벡터의 인덱스를 결정하는 값은 단 하나뿐이었습니다. 안에

퇴화 문제는 여러 인덱스에서 동시에(여러 행에 대해) 발생할 수 있습니다. 이 경우 발견된 참조 계획에서 여러 기본 변수는 0이 됩니다. 선형 계획법 문제가 퇴화된 것으로 판명되면 기초에서 파생된 조건 벡터를 잘못 선택하면 동일한 참조 계획의 기초를 따라 끝없는 이동이 발생할 수 있습니다. 이른바 루핑 현상이다. 실제 선형 프로그래밍 문제에서는 루핑이 매우 드물지만 그 가능성도 배제되지 않습니다. 축퇴를 다루는 방법 중 하나는 문제가 축퇴되지 않는 방식으로 양에 대한 제약 시스템의 우변의 벡터를 "사소하게" 변경하여 문제를 변환하는 것입니다. 따라서 이러한 변경은 문제의 최적 계획에 실제로 영향을 미치지 않습니다. 보다 일반적으로 구현되는 알고리즘에는 루프 발생 또는 극복 가능성을 줄이는 몇 가지 간단한 규칙이 포함됩니다. 변수 xj를 기본으로 만들어야 합니다. 고려해 봅시다

달성된 i로 구성된 인덱스 세트 E0. 이 조건이 E0에 의해 충족되는 인덱스 i의 집합을 나타냅니다. E0가 하나의 요소로 구성된 경우 조건 Ai의 벡터는 기저에서 제외됩니다(변수 xi는 비기본이 됩니다). E0이 두 개 이상의 요소로 구성되면 으로 구성된 집합 E1이 형성됩니다. E1이 하나의 인덱스 k로 구성되면 변수 xk는 기저에서 파생됩니다. 그렇지 않으면 집합 E2가 형성됩니다. 실제로 순환이 이미 감지된 경우 규칙을 사용해야 합니다.

ZLP의 대체 최적????????????????????????????

60. 인공적인 기초 방법. M-작업. 원래 문제의 해와 M-문제 사이의 연결에 관한 정리.

인공적인 기초 방법.

인위적 기저 방법은 조건에 등호 유형 제약 조건이 포함된 경우 선형 계획법 문제에 대해 허용되는 기저 해법을 찾는 데 사용됩니다. 문제를 고려해 봅시다:

최대(F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0).

소위 "인공 변수" Rj는 다음과 같이 제약 조건과 목표 함수에 도입됩니다.

∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj

인공기초법에서 인공변수를 목적함수에 도입할 때, 충분히 큰 계수 M을 할당하는데, 이는 인공변수 도입에 따른 페널티의 의미를 갖는다. 최소화의 경우 계수 M을 사용하여 목표 함수에 인위적인 변수가 추가됩니다. 인위적인 변수의 도입은 문제를 해결하는 과정에서 연속적으로 사라지는 경우 허용됩니다.

인위적인 기초 방법을 사용하여 풀이 과정에서 컴파일된 심플렉스 테이블을 확장 테이블이라고 합니다. 목표 함수에 대해 두 개의 라인이 포함되어 있다는 점에서 일반적인 것과 다릅니다. 하나는 구성 요소 F = ∑cixi에 대한 것이고 다른 하나는 구성 요소 M ∑Rj에 대한 것입니다. 특정 예를 사용하여 문제를 해결하는 절차를 고려해 보겠습니다.

예 1. 제한 사항에 따라 함수 F(x) = -x1 + 2x2 - x3의 최대값을 찾습니다.

x1≥0, x2≥0, x3≥0.

인공적인 기초 방법을 사용해 봅시다. 문제 제약 조건에 인공 변수를 도입해 보겠습니다.

2x1 + 3x2 + x3 + R1 = 3;

x1 + 3x3 + R2 = 2;

목적 함수 F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).

제한 시스템에서 합 R1 + R2를 표현해 보겠습니다. R1 + R2 = 5 - 3x1 - 3x2 - 4x3, F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .

첫 번째 심플렉스 테이블(표 1)을 컴파일할 때 원래 변수 x1, x2, x3은 비기본 변수이고 도입된 인공 변수는 기본 변수라고 가정합니다. 최대화 문제에서는 F 행과 M 행의 비기본 변수에 대한 계수의 부호가 반전됩니다. M라인의 상수값의 부호는 변하지 않습니다. 최적화는 M라인을 따라 먼저 수행됩니다. 선행 열과 행의 선택, 인공 기반 방법을 사용할 때의 모든 단순 변환은 일반적인 단순 방법과 마찬가지로 수행됩니다.

절대값의 최대 음수 계수(-4)는 선행 열과 기저에 들어갈 변수 x3을 결정합니다. 최소 단순 비율(2/3)은 표의 두 번째 행에 해당하므로 변수 R2는 기저에서 제외되어야 합니다. 주요 요소가 설명되어 있습니다.

인공기초법에서는 기저에서 제외된 인공변수는 더 이상 반환되지 않으므로 해당 변수의 요소들의 열은 생략된다. 테이블 2. 1열 감소. 이 테이블을 다시 계산하여 테이블로 이동합니다. 3. M 라인이 재설정된 경우 제거할 수 있습니다. 기저에서 모든 인위적 변수를 제거한 후 원래 문제에 대해 허용 가능한 기저 솔루션을 얻습니다. 이는 고려 중인 예에서 최적입니다.

x1=0; x2=7/9; F최대=8/9.

M-문자열을 제거할 때 솔루션이 최적이 아닌 경우 최적화 절차가 계속되고 일반적인 단순 방법을 사용하여 수행됩니다. 모든 유형에 제한이 있는 예를 고려해 보겠습니다. ≤,=,≥

작업

유형 A, B 및 C 제품에 대한 최적의 생산 값을 찾습니다. 생산 단위당 원자재 비용: A – 5, B – 2, C – 4. 원자재 양 – 2000개. 생산 단위당 장비 비용: A – 4, B – 5, C – 4. 장비 볼륨 – 1000개. 생산 단위 판매 이익: A – 10, B – 8, C – 12. 기준은 기업의 최대 이익입니다. 제품 A의 생산량은 100개 이상이어야 합니다. 제품 B의 생산량은 50개 이상이어야 합니다.

M 방법을 사용하여 단순 문제 해결

1) 최적의 생산계획 결정

x1, x2, x3을 각각 A, B, C 유형의 생산 제품 수량이라고 가정합니다. 그러면 문제의 수학적 모델은 다음과 같은 형식을 갖습니다.

F = 10 x1 + 8 x2 + 12 x3 –>최대

불평등을 평등으로 변환하기 위해 추가 변수 x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0을 도입합니다.

초기 기저를 선택하기 위해 인공 변수 x8 ≥ 0, x9 ≥ 0 및 매우 큰 수 M(M –> )을 도입합니다. M 방법을 사용하여 해결합니다.

F = 10 x1 + 8 x2 + 12 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7– M x8– M x9 –>최대

x4 = 2000을 기본으로 삼아 보겠습니다. x5 = 1000; x8 = 100; x9 = 50.

우리는 단순 테이블에 데이터를 입력합니다.

심플렉스 테이블 No.1

목적 함수:

0 2000 + 0 1000 + (– M) 100 + (– M) 50 = – 150M

다음 공식을 사용하여 추정치를 계산합니다.

Δ1 = 0 5 + 0 4 + (– M) 1 + (– M) 0 – 10 = – M – 10

Δ2 = 0 2 + 0 5 + (– M) 0 + (– M) 1 – 8 = – M – 8

Δ3 = 0 4 + 0 4 + (– M) 0 + (– M) 0 – 12 = – 12

Δ4 = 0 1 + 0 0 + (– M) 0 + (– M) 0 – 0 = 0

Δ5 = 0 0 + 0 1 + (– M) 0 + (– M) 0 – 0 = 0

Δ6 = 0 0 + 0 0 + (– M) (–1) + (– M) 0 – 0 = M

Δ7 = 0 0 + 0 0 + (– M) 0 + (– M) (–1) – 0 = M

Δ2 = 0 0 + 12 0 + 10 0 + 8 1 – 8 = 0

Δ3 = 0 0 + 12 1 + 10 0 + 8 0 – 12 = 0

Δ4 = 0 1 + 12 0 + 10 0 + 8 0 – 0 = 0

Δ5 = 0 (–1) + 12 1/4 + 10 0 + 8 0 – 0 = 3

Δ6 = 0 1 + 12 1 + 10 (–1) + 8 0 – 0 = 2

Δ7 = 0 · (-3) + 12 · 5/4 + 10 · 0 + 8 · (-1) – 0 = 7

부정적인 평가가 없으므로 계획이 최적입니다.

문제 해결 방법: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; F최대 = 2450

답: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450 즉, x1 = A 유형 제품 100단위, x2 = B 유형 제품 50단위, x3 = C 유형 제품 87.5단위를 생산해야 합니다. 이 경우 최대 이익은 Fmax입니다. = 2450개 단위.

원래 문제의 해와 M-문제 사이의 연결에 관한 정리.

???????????????????????

최적화 문제를 해결하는 방법 중 하나( 일반적으로 최소값 또는 최대값을 찾는 것과 관련됩니다.) 선형 계획법을 호출합니다. 단순법선형 계획법 문제를 해결하기 위한 전체 알고리즘 및 방법 그룹이 포함되어 있습니다. 소스 데이터를 기록하고 이를 특수 테이블에 다시 계산하는 방법 중 하나를 호출합니다. 표 형식 단순 방법.

솔루션의 예를 사용하여 표 형식 심플렉스 방법의 알고리즘을 고려해 보겠습니다. 생산과제, 이는 결국 최대 이익을 보장하는 생산 계획을 찾는 것으로 귀결됩니다.

단순법 문제에 대한 입력 데이터

이 회사는 4가지 유형의 제품을 생산하고 3대의 기계에서 처리합니다.

기계에서 제품을 처리하기 위한 시간 표준(분/개)은 매트릭스 A로 지정됩니다.

기계 작동 시간 기금(분)은 매트릭스 B에 지정됩니다.

각 제품 단위 판매로 인한 이익(RUB/개)은 매트릭스 C로 제공됩니다.

생산업무의 목적

기업의 이익을 극대화할 생산 계획을 수립합니다.

표 형식의 단순 방법을 사용하여 문제 해결

(1) 각 유형의 계획된 제품 수를 X1, X2, X3, X4로 표시하겠습니다. 그런 다음 원하는 계획: ( X1, X2, X3, X4)

(2) 방정식 시스템의 형태로 계획 제약 조건을 적어 보겠습니다.

(3) 그러면 목표 이익은 다음과 같습니다.

즉, 생산계획 이행에 따른 이익이 최대가 되어야 한다.

(4) 결과 조건부 극값 문제를 해결하기 위해 부등식 시스템에 음이 아닌 변수를 추가하여 선형 방정식 시스템으로 대체합니다( X5, X6, X7).

(5) 다음을 받아들이자 참고 계획:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) 데이터를 입력해보자 단순한 테이블:

마지막 줄에는 목적 함수의 계수와 그 값 자체를 반대 부호로 입력합니다.

(7) 마지막 줄에서 선택 가장 큰 (모듈로) 음수.

계산해보자 b = N / 선택된_열의_항목_

계산된 b 값 중에서 우리는 다음을 선택합니다. 최소.

선택한 열과 행의 교차점은 해결 요소를 제공합니다. 기저를 해결 요소에 해당하는 변수로 변경합니다( X5~X1).

• 해결 요소 자체가 1로 변합니다.
• 분해능 라인 요소의 경우 – a ij (*) = a ij / RE ( 즉, 각 요소를 해결 요소의 값으로 나누고 새로운 데이터를 얻습니다.).
• 해결 열의 요소는 단순히 0으로 재설정됩니다.
• 직사각형 규칙을 사용하여 테이블의 나머지 요소를 다시 계산합니다.

a ij (*) = a ij – (A * B / RE)

보시다시피, 현재 재계산 중인 셀과 확인 요소가 있는 셀을 사용합니다. 그들은 직사각형의 반대쪽 모서리를 형성합니다. 다음으로 이 직사각형의 다른 두 모서리 셀의 값을 곱합니다. 이 일 ( ㅏ * 비)를 분해요소( 답장). 그리고 다시 계산 중인 현재 셀에서 뺍니다( 에이 ij) 무슨 일이에요. 우리는 새로운 가치를 얻습니다 - ij (*).

(9) 마지막 줄을 다시 확인하세요( 씨) 에 음수의 존재. 거기에 없으면 최적의 계획을 찾은 것입니다. 문제 해결의 마지막 단계로 이동합니다. 있는 경우 계획이 아직 최적이 아니며 단순 테이블을 다시 계산해야 합니다.

마지막 줄에 다시 음수가 있으므로 계산의 새로운 반복을 시작합니다.

(10) 마지막 줄에 부정적인 요소가 없기 때문에 최적의 생산 계획을 찾았다는 의미입니다! 즉, "기본" 열(X1 및 X2)로 이동한 제품을 생산할 것입니다. 우리는 각 생산량 단위의 생산에서 발생하는 이윤을 알고 있습니다( 매트릭스 C). 제품 1과 2의 발견된 생산량에 1개당 이익을 곱하면 최종 ( 최고! ) 주어진 생산 계획에 대한 이익.

답변:

X1 = 32개, X2 = 20개, X3 = 0개, X4 = 0개

P = 48 * 32 + 33 * 20 = 2,196 문지름.

Galyautdinov R.R.

© 자료의 복사는 직접 하이퍼링크가 있는 경우에만 허용됩니다.

일반적으로 선형 방정식의 형식은 다음과 같습니다.

방정식에는 해결책이 있습니다. 즉, 미지수의 계수 중 하나 이상이 0과 다른 경우입니다. 이 경우 좌표를 대체할 때 방정식이 항등식이 되면 모든 차원 벡터를 방정식의 해라고 합니다.

해결된 방정식 시스템의 일반적인 특성

예제 20.1

방정식 시스템 설명.

해결책:

1. 모순되는 방정식이 포함되어 있나요?(계수인 경우 이 경우 방정식의 형식은 다음과 같습니다. 논란이 많은.)

• 시스템에 모순되는 내용이 포함되어 있으면 해당 시스템은 일관성이 없으며 해결책이 없습니다.

2. 허용되는 모든 변수 찾기. (미지의 것이 불린다허용됨연립방정식의 경우 계수가 +1인 시스템의 방정식 중 하나에 포함되어 있지만 나머지 방정식에는 포함되지 않은 경우(즉, 계수가 0인 경우에 포함됨)

3. 연립방정식이 풀렸나요? (방정식 시스템을 해결이라고 합니다., 시스템의 각 방정식에 해결된 미지수가 포함되어 있고 그 중 일치하는 방정식이 없는 경우)

시스템의 각 방정식에서 하나씩 취해진 해결된 미지수는 다음과 같습니다. 해결된 미지의 전체 세트시스템. (이 예에서는 이것이다)

전체 세트에 포함된 허용된 미지수도 호출됩니다. 기초적인(), 세트에 포함되지 않음- 무료 ().

일반적인 경우, 해결된 방정식 시스템은 다음과 같은 형식을 갖습니다.

이 단계에서 가장 중요한 것은 그것이 무엇인지 이해하는 것입니다. 해결됨 알 수 없음(기본에 포함되어 있으며 무료입니다).

일반 특정 기본 솔루션

일반 솔루션해결된 방정식 시스템은 자유 항과 자유 미지수를 통해 해결된 미지수의 표현 세트입니다.

사적인 결정자유변수와 미지수의 특정값에 대한 일반해로부터 구하는 해를 해라고 한다.

기본 솔루션는 자유 변수의 0 값에 대한 일반적인 해로부터 얻은 특정 해입니다.

• 기본 해(벡터)는 다음과 같습니다. 퇴화하다, 0이 아닌 좌표의 수가 허용되는 알 수 없는 수보다 작은 경우.
• 기본 솔루션이라고합니다 비퇴화, 0이 아닌 좌표의 수가 전체 세트에 포함된 시스템의 허용된 알 수 없는 수와 동일한 경우.

정리(1)

해결된 방정식 시스템은 항상 일관됩니다.(적어도 하나의 솔루션이 있기 때문입니다) 더욱이, 시스템에 자유로운 미지수가 없다면,(즉, 연립방정식에서는 허용되는 모든 것이 기저에 포함됩니다) 그러면 정의된다(독특한 솔루션이 있음) 자유 변수가 하나 이상 있으면 시스템이 정의되지 않은 것입니다.(무한한 수의 솔루션이 있습니다).

예 1. 방정식 시스템에 대한 일반, 기본 및 특정 솔루션을 찾습니다.

해결책:

1. 시스템이 승인되었는지 확인하고 있나요?

• 시스템이 해결되었습니다(각 방정식에 해결된 미지수가 포함되어 있으므로).

2. 허용된 미지수를 세트에 포함합니다(각 방정식에서 하나씩)..

3. 우리는 세트에 포함된 알려지지 않은 허용 항목에 따라 일반적인 솔루션을 기록합니다..

4. 민간 솔루션 찾기. 이를 위해 집합에 포함하지 않은 자유 변수를 임의의 숫자와 동일시합니다.

답변: 프라이빗 솔루션(옵션 중 하나)

5. 근본적인 해결책을 찾는다. 이를 위해 세트에 포함하지 않은 자유 변수를 0으로 동일시합니다.

선형 방정식의 기본 변환

선형 방정식 시스템은 기본 변환을 사용하여 동등한 해결 시스템으로 축소됩니다.

정리(2)

만약에 어떠한 시스템의 방정식에 0이 아닌 숫자를 곱합니다., 나머지 방정식은 변경하지 않고 그대로 둡니다. (즉, 방정식의 좌변과 우변에 같은 수를 곱하면 이와 같은 방정식이 나온다)

정리(3)

만약에 시스템의 방정식에 다른 방정식을 추가하십시오., 다른 모든 방정식은 변경하지 않고 그대로 둡니다. 우리는 이것과 동등한 시스템을 얻습니다. (즉, 두 개의 방정식을 추가하면(왼쪽과 오른쪽을 추가하여) 데이터와 동일한 방정식을 얻게 됩니다.)

정리의 추론(2와 3)

만약에 특정 숫자를 곱한 방정식에 다른 방정식을 추가합니다., 다른 모든 방정식은 변경하지 않고 그대로 둡니다. 그러면 우리는 이것과 동등한 시스템을 얻습니다..

시스템 계수를 다시 계산하는 공식

방정식 시스템이 있고 이를 해결된 방정식 시스템으로 변환하려는 경우 Jordan-Gauss 방법이 도움이 될 것입니다.

조던 변환해결 요소를 사용하면 숫자가 있는 방정식의 방정식 시스템에 대해 해결된 미지수를 얻을 수 있습니다. (예 2).

조던 변환은 두 가지 유형의 기본 변환으로 구성됩니다.

더 낮은 방정식의 미지수를 해결된 미지수로 만들고 싶다고 가정해 보겠습니다. 이렇게 하려면 로 나누어야 하므로 그 합은 가 됩니다.

예제 2 시스템 계수를 다시 계산해 보겠습니다.

숫자가 있는 방정식을 로 나눌 때 해당 계수는 다음 공식을 사용하여 다시 계산됩니다.

숫자가 있는 방정식에서 제외하려면 숫자가 있는 방정식에 을 곱하고 이 방정식에 더해야 합니다.

정리 (4) 시스템의 방정식 수를 줄이는 방법.

방정식 시스템에 사소한 방정식이 포함되어 있으면 시스템에서 제외될 수 있으며 원래 시스템과 동등한 시스템이 얻어집니다.

정리 (5) 방정식 시스템의 비호환성에 관한 것입니다.

방정식 시스템에 일관성 없는 방정식이 포함되어 있으면 일관성이 없는 것입니다.

Jordan-Gauss 방법 알고리즘

Jordan-Gauss 방법을 사용하여 방정식 시스템을 풀기 위한 알고리즘은 여러 유사한 단계로 구성되며, 각 단계에서는 다음 순서로 작업이 수행됩니다.

1. 시스템이 일관성이 없는지 확인합니다. 시스템에 일관성 없는 방정식이 포함되어 있으면 일관성이 없는 것입니다.
2. 방정식의 수를 줄일 가능성이 있는지 확인합니다. 시스템에 사소한 방정식이 포함되어 있으면 해당 방정식에 줄이 그어집니다.
3. 방정식 시스템이 해결되면 시스템의 일반 솔루션을 기록하고, 필요한 경우 특정 솔루션을 기록합니다.
4. 시스템이 해결되지 않으면 해결된 미지수가 포함되지 않은 방정식에서 해결 요소가 선택되고 이 요소를 사용하여 조던 변환이 수행됩니다.
5. 그럼 다시 1번 포인트로 돌아가서

예제 3 Jordan-Gauss 방법을 사용하여 연립방정식을 풉니다.

찾다: 두 가지 일반 솔루션과 두 가지 해당 기본 솔루션

해결책:

계산은 아래 표에 나와 있습니다.

표 오른쪽에는 방정식에 대한 작업이 있습니다. 화살표는 해결 요소가 포함된 방정식에 적절한 계수를 곱한 방정식을 나타냅니다.

표의 처음 세 행에는 미지수의 계수와 원래 시스템의 우변이 포함되어 있습니다. 분해 요소가 1인 첫 번째 조던 변환의 결과는 4, 5, 6행에 나와 있습니다. 분해 요소가 (-1)인 두 번째 조던 변환의 결과는 7, 8, 9행에 나와 있습니다. 세 번째 방정식은 사소하므로 생략할 수 있습니다.