엔지니어링의 기본 솔루션 소개

엔지니어이거나 엔지니어링 학생이라면 최적화가 무엇을 의미하는지 알 수 있습니다.

최상의 결과를 얻으려면 작업을 수행하는 가장 좋은 방법을 찾는 것이 중요합니다.

선형 프로그래밍에서는 기본 솔루션을 사용하여 최상의 솔루션을 찾을 수 있습니다.

그러나 기본 솔루션이란 무엇이며 엔지니어가 기본 솔루션에 대해 아는 것이 왜 그렇게 중요합니까? 이 기사에서는 기본 솔루션이 무엇인지, 엔지니어링에서 왜 중요한지, 다양한 상황에서 최상의 결과를 얻기 위해 어떻게 사용할 수 있는지에 대해 설명합니다.

그러니 버클을 채우고 기본 솔루션의 세계로 뛰어들 준비를 하십시오. 여기서 제가 미스터리를 분석하고 이 기술이 얼마나 강력한지 보여드리겠습니다.

선형 계획법의 기본 솔루션

공식적인 정의:

n 변수의 m 방정식으로 구성된 선형 프로그램 모델에 대한 솔루션은 나머지 (nm) 변수의 관점에서 m 변수를 풀고 (nm) 변수를 0으로 설정하여 얻습니다.

선형 프로그래밍의 기본 솔루션은 특정 기술 요구 사항을 충족하는 선형 프로그래밍 문제를 해결하는 방법입니다.

특히 벡터 {ai : xi = 0}이 선형 독립인 경우 벡터 x는 다면체에 대한 기본 솔루션입니다.

이는 0이 아닌 변수 xi를 갖는 A의 열이 선형 독립임을 의미합니다.

음수가 아닌 성분을 가진 기본 솔루션을 기본 실행 가능 솔루션(BFS)이라고 합니다.

BFS는 다면체를 정의하는 모든 규칙을 충족합니다.

각 BFS는 기하학적 관점에서 실현 가능한 솔루션의 다면체 모서리입니다.

기본 솔루션을 찾으려면 기본이 아닌 nm 변수를 0으로 설정하고 기본인 m 변수를 풀어야 합니다.

서로 다른 기반이 동일한 기본 솔루션으로 이어질 수 있으며, 이는 동일한 문제를 해결하는 방법이 둘 이상일 수 있음을 의미합니다.

Simplex 방법은 최상의 BFS를 찾을 때까지 한 BFS에서 다음 BFS로 이동하는 반복 프로세스입니다.

Simplex 방법을 사용하여 BFS를 찾은 후 근처에 있는 다른 BFS가 목적 함수에 대해 더 나은 값을 제공하는지 확인하여 솔루션이 최상의 솔루션인지 알 수 있습니다.

그러한 BFS가 없으면 현재 BFS가 가장 좋습니다.

선형 프로그래밍 모델

선형 프로그래밍 모델에는 결정 변수, 목적 함수 및 제약 조건의 세 가지 주요 구성 요소가 포함됩니다.

목적 함수와 제약 조건은 모두 선형 함수여야 하며 결정 변수는 연속적이어야 합니다.

목적 함수는 이익, 비용, 제품 수 등을 나타내는 숫자를 늘리거나 줄이는 데 사용됩니다.

제약 조건은 의사 결정 변수의 성공 수준을 결정하는 작업을 수행하는 데 필요한 특정 리소스의 총량에 대한 제한 또는 제한입니다.

또한 일부 선형 프로그램에서는 모든 결정 변수가 음수가 아니어야 합니다.

선형 프로그래밍 모델에서는 정수 및 이진 변수도 사용할 수 있습니다.

이진 변수는 0 또는 1의 값만 가질 수 있으므로 0 또는 1의 값만 가질 수 있습니다.

심플렉스 방법

선형 프로그래밍 문제를 해결하는 데 가장 많이 사용되는 방법 중 하나는 Simplex Method입니다.

기본해는 실현가능영역의 꼭지점에 해당하기 때문에 심플렉스 방법에서 중요하며, 심플렉스 방법은 최적해를 찾을 때까지 한 모서리에서 다른 모서리로 이동합니다.

심플렉스 방법은 기본 솔루션의 속성을 사용하여 선형 프로그래밍 문제에 대한 최상의 답을 찾는 빠른 방법입니다.

심플렉스 방법을 사용하여 최상의 BFS를 찾으려면 제약 조건 행렬 A에 대한 기저 B를 찾고 기저 이외의 모든 변수를 0으로 설정하여 시스템 Ax = b를 풀어야 합니다.

기본 변수의 결과 값은 BFS를 형성합니다.

최적 솔루션이 존재한다면 최적의 BFS도 존재합니다.

Simplex 방법은 피벗 절차를 사용하여 최적의 BFS에 도달할 때까지 하나의 BFS에서 인접한 BFS로 이동합니다.

기본 솔루션과 실현 가능한 솔루션의 비교

기본 솔루션과 실행 가능한 솔루션의 차이점은 기본 솔루션은 어떤 조건도 충족할 필요가 없다는 것입니다.

특히 선형 독립이고 xi에 대해 0이 아닌 값을 갖는 벡터가 있어야 하며 x는 0보다 작아야 합니다.

반면에 실행 가능한 솔루션은 문제의 한계 내에 맞는 모든 지점입니다.

그러나 모든 실행 가능한 솔루션이 기본적인 실행 가능한 솔루션인 것은 아닙니다.

기본 실현 가능한 솔루션(BFS)은 실현 가능한 솔루션의 다면체 모서리와 일치하는 솔루션입니다.

기본으로 돌아가기: 엔지니어링에서 기본 솔루션의 성능 활용

아직도 이해하기 어렵나요? 관점을 조금 바꿔보겠습니다.

어려운 문제를 해결하기 위해 복잡한 방법과 알고리즘을 사용하는 데 지쳤습니까? 선형 프로그램 모델 문제를 처리하는 더 간단하고 간단한 방법이 있었으면 좋겠나요?

음, 걱정하지 마세요. 대답은 여기에 있습니다. 나머지 (nm) 변수에 대해 m 변수를 풀고 (nm) 변수를 0으로 설정합니다.

기본으로 돌아갈 수 있을 때 멋지게 들리는 알고리즘이 필요한 사람은 누구입니까? 그러니 계산기를 치우고 간단한 해결책에 대해 배우기 시작합시다.

좋아, 그건 그냥 TV 광고처럼 보이도록 만든 농담일 뿐이야.

이제 설명으로 돌아가 봅시다.

기본 솔루션 선형 계획법

팁: 필요한 경우 캡션 버튼을 켭니다. 구어에 익숙하지 않은 경우 설정 버튼에서 "자동 번역"을 선택하십시오. 좋아하는 언어를 번역할 수 있게 되기 전에 먼저 동영상의 언어를 클릭해야 할 수도 있습니다.

사용 사례

결론

결론적으로, 기본 솔루션의 아이디어는 엔지니어링 분야에서 매우 중요하며 다양한 방식으로 사용될 수 있습니다.

기본 솔루션이 무엇이고 선형 프로그래밍에서 무엇을 하는지 알면 솔루션을 개선하고 비용을 절감하며 보다 효율적으로 만들 수 있습니다.

그러나 기본 솔루션은 강력한 도구이기는 하지만 만병통치약 솔루션은 아니라는 점을 기억하는 것이 중요합니다.

최상의 결과를 얻으려면 각 문제를 주의 깊게 살펴보고 생각해야 합니다.

엔지니어로서 우리는 기본 솔루션과 기타 최적화 기술이 우리가 발전하고 새로운 아이디어를 내는 데 어떻게 도움이 되는지 계속 살펴봐야 합니다.

따라서 간단한 솔루션의 힘을 인식하고 새로운 기술과 전략을 사용하여 가능한 것의 한계를 계속 밀어붙이도록 합시다.

링크 및 참조

서적:

• Vasek Chvatal의 선형 계획법
• Jose M. Sallan의 R을 사용한 선형 계획법 모델링 및 해결