설명
이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 이 인스턴스
규모의 경제를 적용하여 볼록하지 않은 결과를 얻습니다.
목표. 이는 메가 슬롯의 trnsport 모델의 확장입니다.
모델 라이브러리.
원래의 비선형 항은 "sum((i,j), c(i,j)*sqrt(x(i,j)))"입니다.
우리는 sqrt(x)의 다음 이산화 f(x)를 사용합니다.
x<=50의 경우: f(x) = 1/sqrt(50)*x,
x>=400의 경우: f(x) = (sqrt(600)-sqrt(400))/200*(x-400) + sqrt(400)
그 사이에 점 사이의 선형 보간으로 이산화합니다.
이 이산화에는 다음과 같은 몇 가지 좋은 특성이 있습니다.
0) f(x)는 연속 함수입니다.
1) f(0)=0, 그렇지 않으면 사용되지 않은 연결에 대해서도 고정 비용을 지불하게 됩니다.
2) 합리적인 범위의 배송(50~400) 내에서 세밀한 표현
3) f(x)는 x=0에서 600까지의 영역에서 sqrt를 과소평가합니다. 과거는 sqrt를 과대평가합니다.
모델은 다음과 같이 구성됩니다.
1) NLP 솔버의 시작점을 설정하여 중단되도록 합니다.
전역 최적이 아닌 지역 최적이 됩니다.
2) 조각별 선형을 표현하기 위해 세 가지 공식을 사용합니다.
함수는 모두 동일한 이산화를 기반으로 합니다.
a) SOS2 변수를 사용한 공식. 이 공식은 주로
인접한 이웃의 볼록 결합을 기반으로
포인트. 또한, 이산화 영역은 다음과 같습니다.
무제한: (잠재적으로) 기울기를 할당할 수 있습니다.
무제한) 첫 번째 및 마지막 세그먼트.
b) 볼록 조합을 기반으로 한 SOS2 변수를 사용한 공식화
이웃 지점의. 이 공식에는 제한된
이산화를 위한 영역. 여기서는 0과 0 사이를 이산화합니다.
600.
c) 이진 변수를 사용한 공식. 이는 또한
영역은 제한되지만 볼록면에 의존하지 않습니다.
인접한 점의 조합. 다음과 같은 예가 있습니다.
이 공식은 공식 b)보다 훨씬 빠르게 해결됩니다.
이 예에서 x는 아래에서 0으로 명확하게 경계가 지정되어 있습니다.
위의 min(smax(i,a(i),smax(j,b(j)))이므로 공식 b와 c
충분하고 이 특정 모델에서 더 나은 성능을 발휘합니다.
인스턴스. 모델링 방법을 보여주기 위해 공식 a를 추가했습니다.
파생되지 않는 경우 무한한 이산화
경계. 제형 a는 수용하기 쉽게 조정될 수 있습니다.
이산화의 한쪽 끝에만 제한이 없는 문제입니다.
3) 이산화된 해로부터 비볼록 NLP를 다시 시작합니다.
모델을 만들고 NLP 솔버가 전역 솔루션을 찾길 바랍니다.
소형 메가 슬롯 유형 :MIP
카테고리 : 메가 슬롯 모델 라이브러리
메인 파일 : 메가 슬롯gms
$title 이산화된 규모의 경제로 인한 운송 문제 (TRNSPWL,SEQ=351)
$onText
이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 이 인스턴스
규모의 경제를 적용하여 볼록하지 않은 결과를 얻습니다.
목표. 이는 메가 슬롯의 trnsport 모델의 확장입니다.
모델 라이브러리.
원래의 비선형 항은 "sum((i,j), c(i,j)*sqrt(x(i,j)))"입니다.
우리는 sqrt(x)의 다음 이산화 f(x)를 사용합니다.
x<=50의 경우: f(x) = 1/sqrt(50)*x,
x>=400의 경우: f(x) = (sqrt(600)-sqrt(400))/200*(x-400) + sqrt(400)
그 사이에 점 사이의 선형 보간으로 이산화합니다.
이 이산화에는 다음과 같은 몇 가지 좋은 특성이 있습니다.
0) f(x)는 연속 함수입니다.
1) f(0)=0, 그렇지 않으면 사용되지 않은 연결에 대해서도 고정 비용을 지불하게 됩니다.
2) 합리적인 범위의 배송(50~400) 내에서 세밀한 표현
3) f(x)는 x=0에서 600까지의 영역에서 sqrt를 과소평가합니다. 과거는 sqrt를 과대평가합니다.
모델은 다음과 같이 구성됩니다.
1) NLP 솔버의 시작점을 설정하여 중단되도록 합니다.
전역 최적이 아닌 지역 최적이 됩니다.
2) 조각별 선형을 표현하기 위해 세 가지 공식을 사용합니다.
함수는 모두 동일한 이산화를 기반으로 합니다.
a) SOS2 변수를 사용한 공식. 이 공식은 주로
인접한 이웃의 볼록 결합을 기반으로
포인트. 또한, 이산화 영역은 다음과 같습니다.
무제한: (잠재적으로) 기울기를 할당할 수 있습니다.
무제한) 첫 번째 및 마지막 세그먼트.
b) 볼록 조합을 기반으로 한 SOS2 변수를 사용한 공식화
이웃 지점의. 이 공식에는 제한된
이산화를 위한 영역. 여기서는 0과 0 사이를 이산화합니다.
600.
c) 이진 변수를 사용한 공식. 이는 또한
도메인은 제한되지만 볼록에 의존하지 않습니다.
인접한 점의 조합. 다음과 같은 예가 있습니다.
이 공식은 공식 b)보다 훨씬 빠르게 해결됩니다.
이 예에서 x는 아래에서 0으로 명확하게 경계가 지정되어 있습니다.
위의 min(smax(i,a(i),smax(j,b(j)))이므로 공식 b와 c
충분하고 이 특정 모델에서 더 나은 성능을 발휘합니다.
인스턴스. 모델링 방법을 보여주기 위해 공식 a를 추가했습니다.
파생되지 않는 경우 무한한 이산화
경계. 제형 a는 수용하기 쉽게 조정될 수 있습니다.
이산화의 한쪽 끝에만 제한이 없는 문제입니다.
3) 이산화된 해로부터 비볼록 NLP를 다시 시작합니다.
모델을 만들고 NLP 솔버가 전역 솔루션을 찾길 바랍니다.
Dantzig, GB, 3.3장. 선형 프로그래밍 및 확장.
프린스턴 대학 출판부, 뉴저지주 프린스턴, 1963년.
키워드: 비선형 계획법, 혼합 정수 선형 계획법,
운송 문제, 일정 관리, 규모의 경제, 비볼록
대물렌즈, 특별 주문 세트
$offText
세트
i '통조림 식물' / 시애틀, 샌디에이고 /
j 'markets' / 뉴욕, 시카고, 토피카 /;
매개변수
a(i) '경우에 따라 식물 i의 용량'
/시애틀 350
샌디에이고 600 /
b(j) '경우에 따라 시장 j의 수요'
/ 뉴욕 325
시카고 300
토피카 275 /;
테이블 d(i,j) '거리(천 마일)'
뉴욕 시카고 토피카
시애틀 2.5 1.7 1.8
샌디에고 2.5 1.8 1.4;
스칼라 f '1,000마일당 케이스당 운임(달러)' / 90 /;
매개변수 c(i,j) '케이스당 운송 비용(단위: 수천 달러)';
c(i,j) = f*d(i,j)/1000;
변수
x(i,j) '케이스의 선적 수량'
z '총 운송 비용(천 달러)';
양수 변수 x;
방정식
비용 '목적 함수 정의'
Supply(i) '공장 i의 공급 제한을 준수합니다.'
수요(j) '시장 j의 수요를 충족';
비용.. z =e= sum((i,j), c(i,j)*sqrt(x(i,j)));
공급(i).. sum(j, x(i,j)) =l= a(i);
수요(j)..sum(i, x(i,j)) =g= b(j);
모델 운송 / 모두 /;
* 전역적으로 최적이 아닌 로컬 솔루션에서 로컬 NLP 솔버를 시작합니다.
x.l('시애틀','시카고') = 25;
x.l('시애틀','토피카') = 275;
x.l('샌디에고','뉴욕') = 325;
x.l('샌디에고','시카고') = 275;
Scalar localopt '전체적으로 최적이 아닌 지역 최적의 목표';
옵션 nlp = conopt;
z를 최소화하는 nlp를 사용하여 전송을 해결합니다.
localopt = z.l;
* 첫 번째 모델(공식 a)은 조각별 선형을 구현합니다.
* 인접 점의 볼록 결합을 기반으로 한 근사치
* 시작 부분에 무한한 세그먼트가 있는 SOS2 변수를 사용하고
* 이산화의 끝
세트
s 'SOS2 요소' / Slope0, s1*s6, SlopeN /
ss(s) '샘플 포인트' / s1*s6 /;
매개변수
p(s) '샘플 포인트의 x 좌표'
sqrtp(s) '샘플 포인트의 y 좌표'
엑스로우 / 50 /
엑스하이 / 400 /
x최대;
xmax = smax(i, a(i));
abort$(xmax < xhigh) 'xhigh가 너무 큼', xhigh, xmax;
abort$(xlow < 0) 'xlow가 0보다 작습니다.', xlow;
* 시작과 끝의 기울기를 갖는 sqrt 함수의 등거리 샘플링
p('기울기0') = -1;
p(ss) = xlow + (xhigh-xlow)/(카드(ss)-1)*ss.off;
p('기울기N') = 1;
sqrtp('slope0') = -1/sqrt(xlow);
sqrtp(ss) = sqrt(p(ss));
sqrtp('기울기N') = (sqrt(xmax)-sqrt(xhigh))/(xmax-xhigh);
SOS2 변수 xs(i,j,s);
양수 변수 sqrtx(i,j);
방정식 defsos1(i,j), defsos2(i,j), defsos3(i,j), defobjdisc;
defsos1(i,j).. x(i,j) =e= sum(s, p(s)*xs(i,j,s));
defsos2(i,j).. sqrtx(i,j) =e= sum(s, sqrtp(s)*xs(i,j,s));
defsos3(i,j).. sum(ss, xs(i,j,ss)) =e= 1;
defobjdisc.. z =e= sum((i,j), c(i,j)*sqrtx(i,j));
모델 trndiscA / 공급, 수요, defsos1, defsos2, defsos3, defobjdisc /;
옵션 optCr = 0;
mip를 사용하여 trndiscA min z를 해결합니다.
* 다음 모델(공식 b)은 다음의 볼록 조합을 사용합니다.
* 인접한 점이지만 이산화가 제한되어야 함
* (여기서는 0에서 xmax까지 이동합니다).
p('기울기0') = 0;
p(ss) = xlow + (xhigh - xlow)/(카드(ss) - 1)*ss.off;
p('기울기N') = xmax;
sqrtp(s) = sqrt(p(s));
* 모델 trndiscA만 사용할 수 있지만 첫 번째와
* 볼록 조합을 구성하는 세트 ss의 마지막 세그먼트입니다.
ss(들) = 예;
mip를 사용하여 trndiscA min z를 해결합니다.
* 다음 모델(공식 c)은
* 조각별 선형 함수. 도메인 지역이 다음과 같다고 가정해야 합니다.
* 제한되어 있습니다. 우리는 이전 공식에서와 동일한 이산화를 사용합니다.
g(s) '세그먼트' / 기울기0, s1*s6 / 설정;
매개변수
nseg(s) '세그먼트에서 x의 상대적 증가'
ninc(s) '세그먼트 내 sqrtx의 상대적 증가';
nseg(g(s)) = p(s+1) - p(s);
ninc(g(s)) = (sqrtp(s+1) - sqrtp(s));
변수
seg(i,j,s) '세그먼트 내 배송'
gs(i,j,s) '세그먼트 내 배송 표시';
바이너리 변수 gs;
양수 변수 세그먼트;
방정식
defx(i,j) 'x의 정의'
defsqrt(i,j) 'sqrt 정의'
defseg(i,j,s) '표시기가 켜져 있는 경우에만 세그먼트가 배송될 수 있습니다.'
defgs(i,j) '최대 하나의 세그먼트를 선택합니다';
defx(i,j).. x(i,j) =e= sum(g, p(g)*gs(i,j,g) + nseg(g)*seg(i,j,g));
defsqrt(i,j).. sqrtx(i,j) =e= sum(g, sqrtp(g)*gs(i,j,g) + ninc(g)*seg(i,j,g));
defseg(i,j,g).. seg(i,j,g) =l= gs(i,j,g);
defgs(i,j)..sum(g, gs(i,j,g)) =l= 1;
모델 trndiscB / 공급, 수요, defx, defsqrt, defseg, defgs, defobjdisc /;
mip를 사용하여 trndiscB min z를 해결합니다.
* 이제 이 대략적인 지점에서 로컬 솔버를 다시 시작합니다.
nlp를 사용하여 전송 최소 z를 해결합니다.
* 우리가 이전보다 더 나아졌는지 확인
abort$(z.l - localopt > 1e-6) '개선된 솔루션이 필요합니다';