선형 완화 문제란?
선형 완화 문제란?
조합 최적화 에서의 혼합 정수 최적화 문제의 정수 제약을 없애고 할 수 있는 문제를 (혼합 정수 최적화 문제의) 선형 완화 문제라고 하며, 선형 최적화 문제가 됩니다.
원래 완화 문제 1이란?
원래 문제의 제약 조건의 일부 또는 전부를 삭제할 수 있는 새로운 문제를 원래 문제의 완화 문제라고 합니다.
특징
제약 조건이 없어져 실행 가능 영역이 넓어집니다. 따라서 다음과 같은 특징이 있습니다.
선형 완화란?
완화의 일종으로 정수 제약을 제거하는 것입니다.
(참고로) 라그랑주 완화 란 무엇입니까?
왜 완화하는가?
예를 들어 선형 완화는 분지 한정법에서 사용됩니다.
그 밖에도, 근사해를 얻거나, 감도 분석하거나, 쌍대 정리의 증명 등으로 사용됩니다.
덧붙여 곡선의 함수를 꺾은선으로 나타내는 것은, 구분선형 근사라고 불려 완화는 아닙니다.
예제 (Napsack 문제)로 확인
쉽고 쉽게 설명할 수 있도록 3가지 변수의 혼합 정수 최적화 문제 2인 냅삭 문제를 생각해 봅시다.
혼합 정수 최적화 문제의 공식화
최대화
$7x+8y+9z$
제약
$6x+7y+8z\le 14$
$x,y,z\in\{0,1\}$
혼합 정수 최적화 문제의 솔루션 공간 및 최적 솔루션 (빨간색 점)
혼합 정수 최적화 문제의 Python에 의한 구해
파이썬
from pulp import *
m = LpProblem(sense=LpMaximize) # 数理モデル
x,y,z = [LpVariable(c,cat=LpBinary) for c in 'xyz'] # 変数
m += lpDot([7,8,9], [x,y,z]) # 目的関数
m += lpDot([6,7,8], [x,y,z]) <= 14 # 制約条件
m.solve() # 求解
print([value(v) for v in [x,y,z]]) # 出力
>>>
[1.0, 0.0, 1.0]
선형 완화 문제의 공식화
최대화
$7x+8y+9z$
제약
$6x+7y+8z\le 14$
$x,y,z\ge 0, ~~\le 1$
선형 완화 문제의 해 공간과 최적 해 (빨간 점)의 그림
선형 완화 문제의 Python에 의한 구해
파이썬
from pulp import *
m = LpProblem(sense=LpMaximize) # 数理モデル
x,y,z = [LpVariable(c,lowBound=0,upBound=1) for c in 'xyz'] # 変数
m += lpDot([7,8,9], [x,y,z]) # 目的関数
m += lpDot([6,7,8], [x,y,z]) <= 14 # 制約条件
m.solve() # 求解
print([value(v) for v in [x,y,z]]) # 出力
>>>
[1.0, 1.0, 0.125]
이상
정식화된 물건을 모델이라고 부르면 완화 문제가 아니라 완화 모델이라고 하고 싶은 곳입니다. ↩
혼동이 적고 방법으로, 냅삭 문제는 정수 최적화 문제가 됩니다. 여기에서는, 보다 범용적인 혼합 정수 최적화 문제에 대해서 성립하는 설명이므로, 굳이 이렇게 하고 있습니다. ↩
Reference
이 문제에 관하여(선형 완화 문제란?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/SaitoTsutomu/items/45e72a14eb5c367ae62d텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)