엔지니어링에서 실행 가능한 기본 솔루션 소개

공대생이나 엔지니어라면 가능한 최상의 결과를 얻기 위해 시스템을 최적화하는 것이 무엇을 의미하는지 알고 있을 것입니다.

솔루션 최적화는 다리 건설에서 소프트웨어 제작에 이르기까지 모든 성공의 열쇠입니다.

기본적인 실행 가능한 솔루션에 대한 아이디어가 이 시점에서 나옵니다.

가능한 솔루션 세트 중 어떤 것이 가장 좋은지 알아낼 수 있는 것은 선형 프로그래밍의 기본 아이디어입니다.

하지만 왜 그렇게 중요합니까? 이 기사에서는 실현 가능한 기본 솔루션과 이러한 솔루션을 실제 세계에서 엔지니어링 문제를 해결하는 데 사용할 수 있는 방법에 대해 설명합니다.

나는 그것들을 찾는 방법, 그것들이 무엇으로 만들어졌는지, 그것들이 왜 중요한지에 대해 이야기할 것입니다.

따라서 경험이 풍부한 엔지니어든 이제 막 시작하는 학생이든 관계없이 실현 가능한 기본 솔루션의 세계로 들어가 선형 프로그래밍의 힘을 사용하는 방법을 보여드리겠습니다.

실행 가능한 기본 솔루션 이해

공식적인 정의:

모든 변수가 음수가 아닌 선형 프로그램 모델에 대한 기본 솔루션입니다.

기본 실행 가능한 솔루션(BFS)은 최상의 솔루션을 찾는 데 도움이 되는 선형 계획법의 핵심 아이디어입니다.

BFS는 0이 아닌 변수가 가능한 가장 적은 수의 솔루션입니다.

실현 가능한 솔루션의 다면체 모서리입니다.

즉, BFS는 음수가 아닌 제약 조건을 충족하고 실현 가능한 영역 또는 문제 영역에 있는 기본 솔루션입니다.

최적의 기본 실행 가능한 솔루션 찾기

최상의 BFS를 찾으려면 다음을 수행해야 합니다.

• 선형 시퀀스에 대한 표준 형식으로 프로그램을 작성하십시오.
• 부등식 시스템을 증강 행렬로 바꾸십시오.
• 기본 변수와 그렇지 않은 변수를 파악합니다.
• 다른 변수와 관련하여 기본 변수가 무엇인지 파악하십시오.
• 이러한 식을 목적 함수에 넣어 기본이 아닌 변수만의 함수를 얻습니다.
• 제약 조건을 위반하지 않고 증가할 수 있고 목적 함수를 더 좋게 만드는 기본이 아닌 변수를 찾습니다.

이 변수는 이제 기본 변수이며 다른 기본 변수 중 하나는 더 이상 기본 변수가 아닙니다.

최적의 솔루션이 있는 경우 솔루션이 가능한 영역의 끝 또는 정점 중 하나에 있어야 합니다.

따라서 LP에 최적 솔루션이 있는 경우 실현 가능한 집합의 극한 지점에서 최적 솔루션을 갖습니다.

또한 최적의 솔루션이 있으면 항상 최적의 BFS가 있습니다.

Simplex 방법을 사용하여 최적의 BFS 찾기

심플렉스 방법은 선형 계획법의 문제를 해결하기 위한 알고리즘입니다.

피벗 절차를 사용하여 하나의 BFS에서 "인접한" BFS로 이동합니다.

피벗 절차에서는 기본이 아닌 변수를 기본 변수로 선택하고 현재 BFS를 사용하여 새로운 기본 변수를 해결합니다.

목적 함수를 개선하기 위해 기본이 아닌 변수를 변경할 수 없으면 알고리즘이 완료된 것입니다.

기본 실행 가능한 솔루션이 복잡한 엔지니어링 문제를 해결하는 데 중요한 이유

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

어쨌든 간단하고 실행 가능한 답변이 필요한 사람은 누구입니까? 모든 것을 함께 던지고 최선을 다하십시오.

결국 혼돈이 훨씬 더 재미있을 때 최적화가 필요한 사람은 누구입니까? 모든 것이 제안에 불과하고 실패가 거의 확실한 음수가 아닌 변수의 세계에 오신 것을 환영합니다.

아니면?

실행 가능한 기본 솔루션의 기본 개념이 기본이 아닌 이유와 가장 복잡한 엔지니어링 문제를 해결하는 데 핵심이 될 수 있는 이유를 살펴보겠습니다.

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

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

실행 가능한 기본 솔루션 찾기

기본 실행 가능 솔루션(BFS)은 모든 제약 조건을 충족하고 0이 아닌 변수의 수가 가장 적은 선형 최적화 문제에 대한 솔루션입니다.

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

최상의 솔루션이 있으면 최상의 첫 번째 단계도 있어야 합니다.

이 기사에서는 초기 기본 실현 가능한 솔루션을 찾는 방법, 모든 기본 실현 가능한 솔루션을 찾는 방법 및 여유 변수가 없는 기본 실현 가능한 솔루션을 찾는 방법에 대해 설명합니다.

초기 기본 실행 가능한 솔루션 찾기

선형 최적화 문제에 대해 작동하는 초기 기본 솔루션을 찾기 위해 문제가 설정되는 방식에 따라 다른 방법을 사용할 수 있습니다.

한 가지 방법은 불평등에 대한 제약 조건에 여유 변수를 추가하고 다른 모든 변수를 0으로 설정하는 것입니다.

slack 변수는 기본 변수가 되고 나머지는 기본이 아닌 변수입니다.

2상 심플렉스 방법은 문제를 해결하는 또 다른 방법입니다.

이 방법은 실행 가능한 초기 기본 솔루션을 찾기 위해 추가 선형 계획법 문제를 해결하는 것을 포함합니다.

실행 가능한 초기 기본 솔루션이 발견되면 Simplex 방법을 사용하여 하나의 기본 실행 가능한 솔루션에서 다음 솔루션으로 이동한 다음 최상의 솔루션으로 이동할 수 있습니다.

모든 기본 실행 가능한 솔루션 찾기

선형 프로그램에 대해 작동하는 기본 솔루션이 두 개 이상 있을 수 있습니다.

여유 변수를 추가하여 시스템을 변경한 다음 새 시스템을 사용하여 선형 프로그램에 대한 모든 기본 실행 가능한 솔루션을 찾을 수 있습니다.

그런 다음 이러한 기본 실행 가능 솔루션을 사용하여 원래 문제에 대한 기본 실행 가능 솔루션을 찾습니다.

여유 변수가 없는 기본 실행 가능한 솔루션 찾기

여유 변수 없이 작동하는 기본 솔루션을 찾을 수 있도록 보다 작음 제약 조건을 없애기 위해 여유 변수를 사용해야 합니다.

여유 변수는 제약 조건의 오른쪽과 왼쪽 사이의 차일 뿐입니다.

예를 들어 첫 번째 제약 조건의 경우 슬랙 변수 x4 = 14 - 2x1 - x2 - x3을 정의합니다. 이 새로운 변수의 관점에서 첫 번째 제약 조건은 단순히 x4 ≥ 0과 동일하며, 이는 x4에 대한 양성 제약 조건입니다.

이러한 여유 변수를 추가하면 모든 제약 조건이 방정식이거나 무언가가 양수라고 말하는 제약 조건이라는 점을 제외하면 원래 프로그램과 동일한 선형 프로그램을 얻습니다.

기본 솔루션에서 0 이외의 값을 갖는 기본 변수 집합을 기저라고 합니다.

기본 솔루션에서 값이 0인 변수는 기본 변수가 아닙니다.

최상의 솔루션을 찾으려면 모든 규칙을 충족하고 목적에 대해 가장 큰 값 또는 가장 작은 값을 가져오는 벡터 x를 찾아야 합니다.

그러나 최적의 솔루션을 찾는 것은 작동하고 여유 변수가 없는 솔루션을 찾는 것보다 더 많은 단계를 거쳐야 합니다.

여유 변수가 없는 기본 솔루션을 찾는 것이 항상 가능한 것은 아닙니다. 특히 제약 조건이 작은 문제의 경우 더욱 그렇습니다.

실행 가능한 기본 솔루션을 찾으려면 심플렉스 방법 또는 다른 선형 프로그래밍 알고리즘을 사용하여 모든 제약 조건을 충족하고 0이 아닌 변수가 가장 적은 솔루션을 찾아야 합니다.

실행 가능한 기본 솔루션의 특성 및 의의

실행 가능한 기본 솔루션의 속성

기본 실행 가능한 솔루션에는 0이 아닌 최대 m개의 변수와 0인 최소 nm개의 변수가 있습니다. 여기서 n은 결정 변수의 수이고 m은 제약 조건의 수입니다.

BFS는 가능한 솔루션의 다면체 모서리이며 각 BFS에는 선형적으로 독립적인 n개의 활성 제약 조건이 있습니다.

최상의 솔루션이 있으면 최상의 첫 번째 단계도 있어야 합니다.

실행 가능한 기본 솔루션의 가장 중요한 점은 선형 프로그래밍 문제에 대한 볼록 솔루션 세트의 끝이라는 것입니다.

최상의 답을 찾기 위해 심플렉스 알고리즘은 일련의 BFS를 거칩니다.

Simplex Algorithm은 최상의 솔루션을 찾기 위해 조직적인 방식으로 가능한 모든 기본 솔루션을 검색합니다.

실현 가능한 기본 솔루션의 의의

가능한 기본 솔루션을 찾는 것은 선형 계획법 문제에 대한 최상의 답을 찾는 데 도움이 되므로 중요합니다.

또한 복잡한 알고리즘을 시작할 장소를 제공하고 선형 프로그램이 가능한지 여부를 파악하는 데 사용할 수 있습니다.

선형 프로그램에 대한 모든 기본 실현 가능한 솔루션을 찾으려면 여유 변수를 추가하여 시스템을 변경한 다음 변경된 시스템을 사용하여 모든 기본 실현 가능한 솔루션을 찾을 수 있습니다.

그런 다음 이러한 기본 실행 가능 솔루션을 사용하여 원래 문제에 대한 기본 실행 가능 솔루션을 찾습니다.

비디오: 실행 가능한 기본 솔루션

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

사용 사례

결론

실행 가능한 기본 솔루션에 대한 이 살펴보기가 종료됨에 따라 모든 엔지니어 또는 엔지니어링 학생에게 중요한 도구임이 분명해졌습니다.

복잡한 시스템을 구축하는 가장 좋은 방법을 파악하는 것부터 사용 가능한 리소스를 최대한 활용하는 것까지 기본 실행 가능한 솔루션은 가능한 최상의 결과를 얻기 위한 프레임워크를 제공합니다.

그러나 유용할 뿐만 아니라 수학이 얼마나 우아하고 아름다울 수 있는지 보여줍니다.

복잡한 문제를 간단한 방정식 세트로 요약한 다음 해당 방정식을 사용하여 실제 문제를 해결할 수 있다는 것은 놀라운 일입니다.

공학은 문제 해결에 관한 것이며 수학의 힘을 사용하면 한때 불가능하다고 생각했던 답을 찾을 수 있다는 사실을 일깨워주는 좋은 사례입니다.

따라서 엔지니어링에 대해 더 많이 배울 때 작동하는 간단한 솔루션에 대해 배운 내용을 기억하고 이를 사용하여 세상을 더 좋고 효율적인 곳으로 만드십시오.

링크 및 참조

서적:

• 선형 프로그래밍: 기초 및 확장
• 선형 계획법: 이론 및 응용