선형 프로그래밍, 다양한 제약 조건이 적용될 때 선형 함수가 최대화되거나 최소화되는 수학적 모델링 기술. 이 기술은 비즈니스 계획, 산업 공학 및 사회 과학 및 물리 과학의 정량적 결정을 안내하는 데 유용합니다.
최적화: 선형 프로그래밍
오늘날 일상적인 의사 결정 문제를 해결하기 위해 널리 사용되었지만 선형 프로그래밍은 1947 년 이전에는 비교적 알려지지 않았습니다.
선형 프로그래밍 문제의 솔루션은 선형 표현식의 최적 값 (문제에 따라 가장 크거나 작은)을 찾는 것으로 감소합니다 (목적 함수라고 함)
불평등으로 표현 된 일련의 제약 조건에 따라:
a, b 및 c는 문제의 용량, 요구, 비용, 이익 및 기타 요구 사항 및 제한에 의해 결정되는 상수입니다. 이 방법을 적용 할 때의 기본 가정은 수요와 가용성 간의 다양한 관계가 선형 적이라는 것입니다. 즉, x i 중 어느 것도 1 이외의 거듭 제곱으로 올라가지 않습니다.이 문제에 대한 해를 구하려면 선형 불평등 시스템의 해 (즉, n 값 집합)를 찾아야합니다. 모든 불평등을 동시에 만족시키는 변수 x i). 그런 다음 f를 정의하는 방정식에서 x i 값을 대입하여 목적 함수를 평가 합니다.
선형 프로그래밍 방법의 적용은 1930 년대 후반 소련 수학자 Leonid Kantorovich와 미국 경제학자 Wassily Leontief에 의해 제조 일정과 경제 분야에서 처음으로 심각하게 시도되었지만 수십 년 동안 그 작업은 무시되었습니다. 제 2 차 세계 대전 중에 선형 프로그래밍은 비용, 가용성과 같은 특정 제한 사항에 따라 자원의 운송, 예약 및 할당을 처리하는 데 광범위하게 사용되었습니다. 이러한 응용 프로그램은이 방법의 수용 가능성을 확립하기 위해 많은 노력을 기울였으며, 1947 년 미국의 수학자 George Dantzig의 심플 렉스 방법이 도입되면서 선형 프로그래밍 문제의 해결 방법을 크게 단순화시켜 더욱 자극을 받았습니다.
그러나 더 많은 변수를 포함하는 점점 더 복잡한 문제가 시도됨에 따라 필요한 작업 수가 기하 급수적으로 확장되어 가장 강력한 컴퓨터의 계산 용량을 초과했습니다. 그런 다음 1979 년에 러시아의 수학자 Leonid Khachiyan은 다항식 시간 알고리즘을 발견했습니다.이 계산 알고리즘은 계산 단계의 수가 기하 급수적 인 것이 아니라 변수의 수의 힘으로 증가하여 지금까지 접근 할 수없는 문제의 해결을 허용합니다. 그러나 Khachiyan의 알고리즘 (타원 법이라고 함)은 실제로 적용 할 때 단면 법보다 느 렸습니다. 1984 년 인도의 수학자 Narendra Karmarkar는 심플 렉스 방법과의 경쟁이 입증 된 또 다른 다항식 시간 알고리즘 인 내부 포인트 방법을 발견했습니다.
