주메뉴 바로가기 본문 바로가기 하단 바로가기

고객지원

기술문의

LP reduced cost 문의

  • 김희문
  • 2008.04.04
  • 조회수 1,534
아래는 concert 방식으로 입력된 lp 문제에 대한 결과입니다. optimal 이라고 나타내고 있는데도 불구하고 일부 변수에 대해서 reduced cost가 음수입니다. (목적식이 minimize 인 경우)
fesibility check 가 된 경우입니다.
===========================================================
Iteration log . . .
Iteration: 1 Dual infeasibility = 1267.468022
Iteration: 37 Dual objective = 107.410192
masterSolver.getStatus() = Optimal
1

ObjValue == 1748.12

route[8] = 1
[0, 5, 7, 0]
route[34] = 1
[0, 14, 16, 0]
route[43] = 1
[0, 5, 8, 17, 0]
route[54] = 1
[0, 14, 18, 0]
route[55] = 1
[0, 5, 19, 0]
route[182] = 1
[0, 23, 24, 25, 0]
route[220] = 1
[0, 9, 20, 1, 0]
route[270] = 1
[0, 2, 21, 22, 4, 0]
route[276] = 1
[0, 11, 10, 0]
route[287] = 1
[0, 15, 6, 0]
route[315] = 1
[0, 12, 3, 13, 0]
route[8] reduced cost -21.1937
route[33] reduced cost -1.42109e-014
route[54] reduced cost -1.42109e-014
route[55] reduced cost -9.33313
Optimal
===========================================================

마지막 부분에서 reduced cost 보면 두개의 변수 route[8], route[55]에서 더 계산이 되어야 함에도 불구하고 Optimal 이라고 결과를 보여주고 있습니다.
그리고 route[33], route[54]의 경우는 거의 0에 가까운데 이는 소수점 이하 부분 처리로 인해 나타난 것 같은데,
이러한 현상이 나타나는 이유와 해결 방법을 알고 싶습니다.

현재 결과를 보여준 code를 export 해서 도스창으로 돌려봤습니다. (첨부파일로 올렸음) 거기서도 음수의 reduced cost 가 나타나는 현상이 있습니다. 다운로드아이콘vrp.zip

댓글 2

  • 조한민2008-04-08
    안녕하십니까 KSTEC입니다.

    Reduced Cost 값이 변수값을 한단위 증가 시킬 때
    목적식에 주는 영향을 나타내는 값이라는 관점에서 볼때
    -value 가 출력되니 오해가 있을실 수 있겠습니다.

    그러나 변수가 Bound를 갖는경우 Reduced 값이 실제 목적식에 미치는 영향과 다를 수 있습니다. RC값은 제약에 의해 판단되어 지는 값인데 이에 변수의 바운드가 영향을 미치기 때문인 것으로 생각됩니다.

    보내주신 문제의 경우 변수의 바운드를 모두 제거 하고 같은 작업을 수행하시면 RC가 모두 양수인 것을 보실수 있습니다.

    또한 라우트도 11개 arc를 연결하는 것으로 정상 출력됩니다.

    원래 문제 역시 Optimal값을 찾은 것입니다.


    Variable Name Solution Value
    id64 1.000000
    id90 1.000000
    id98 1.000000
    id109 1.000000
    id111 1.000000
    id238 1.000000
    id276 1.000000
    id326 1.000000
    id332 1.000000
    id343 1.000000
    id371 1.000000
    Rgid53 11.000000
    All other variables in the range 1-324 are 0.

    CPLEX> display sol red -
    Variable Name Reduced Cost
    id55 1.000000
    id56 91.922425
    id57 10.418437
    id58 156.530745
    id59 12.275359
    id60 9.083333
    id61 3.192025
    id63 3.192025
    id66 12.630888
    id67 144.230456
    id68 147.422481
    id69 11.860597
    id70 11.860597
    id71 95.267664
    id72 160.684395
    id73 12.275359
    id74 9.083333
    id75 163.876420
    id76 27.839223
    id77 24.647198
    id78 27.839223
    id79 28.314536
    id80 28.314536
    id81 7.120813
    id82 7.120813
    id83 7.163338
    id84 12.413338
    id85 16.453939
    id86 151.601061
    id87 117.092018
    id88 119.844889
    id91 153.563582
    id92 156.755607
    id93 20.718411
    id94 17.526385
    id95 20.718411
    id96 21.193723
    id97 21.193723
    id100 9.333126
    id101 144.480249
    id102 156.755607
    id103 146.856300
    id104 146.856300
    id105 15.848643
    id106 15.848643
    id107 15.848643
    id108 4.178061
    id112 156.530745
    id113 159.722771
    id114 28.039853
    id115 28.039853
    id117 3.483617
    id118 12.300290
    id119 147.447412
    id120 159.777306
    id121 14.311800
    id122 15.145134
    id123 111.712279
    id124 6.707282
    id125 9.899308
    id126 9.899308
    id129 3.192025
    id131 159.722771
    id132 156.530745
    id133 3.192025
    id135 159.722771
    id136 31.611648
    id137 28.419623
    id138 31.611648
    id139 27.522691
    id140 27.522691
    id142 0.854853
    id143 13.036347
    id144 147.447412
    id145 159.722771
    id146 149.823463
    id147 149.823463
    id148 26.656449
    id149 26.656449
    id150 26.656449
    id151 30.941870
    id152 32.049062
    id153 30.941870
    id154 30.941870
    id155 19.801706
    id156 20.635039
    id157 153.015489
    id158 149.823463
    id159 9.899308
    id160 6.707282
    id161 9.899308
    id162 9.899308
    id165 3.192025
    id168 195.565283
    id169 42.226563
    id170 39.034537
    id171 164.389438
    id172 161.197412
    id173 12.275359
    id174 9.083333
    id175 198.757308
    id176 62.720111
    id177 59.528086
    id178 62.720111
    id179 63.195424
    id180 63.195424
    id181 44.681229
    id182 44.681229
    id183 39.034537
    id184 39.034537
    id185 51.334827
    id186 186.481949
    id187 198.757308
    id188 188.858000
    id189 188.858000
    id190 57.850344
    id191 57.850344
    id192 57.850344
    id193 64.912302
    id195 61.720277
    id196 64.912302
    id197 64.912302
    id198 51.334827
    id199 51.334827
    id200 192.050026
    id201 188.858000
    id202 48.933845
    id203 45.741819
    id204 48.933845
    id205 48.933845
    id206 39.034537
    id207 39.034537
    id208 42.226563
    id209 39.034537
    id210 39.034537
    id211 159.722771
    id212 156.530745
    id213 3.192025
    id215 159.722771
    id216 27.522691
    id217 27.522691
    id219 0.854853
    id220 13.036347
    id221 147.447412
    id222 159.722771
    id223 149.823463
    id224 149.823463
    id225 30.941870
    id226 30.941870
    id227 30.941870
    id228 153.015489
    id229 149.823463
    id230 9.899308
    id231 6.707282
    id232 9.899308
    id233 9.899308
    id236 3.192025
    id239 180.500930
    id240 27.162210
    id241 23.970184
    id242 183.692955
    id243 47.655758
    id244 44.463733
    id245 47.655758
    id246 48.131071
    id247 48.131071
    id248 26.937348
    id249 26.937348
    id250 23.970184
    id251 23.970184
    id252 153.695547
    id253 150.503522
    id254 153.695547
    id255 18.133663
    id256 18.133663
    id257 36.270474
    id258 171.417596
    id259 183.692955
    id260 173.793648
    id261 173.793648
    id262 42.785991
    id263 42.785991
    id264 42.785991
    id265 49.847950
    id266 46.655924
    id267 49.847950
    id268 49.847950
    id269 36.270474
    id270 36.270474
    id271 159.722771
    id272 156.530745
    id273 159.722771
    id274 24.160887
    id275 24.160887
    id278 12.300290
    id279 147.447412
    id280 159.722771
    id281 12.300290
    id282 12.300290
    id283 176.985673
    id284 173.793648
    id285 33.869492
    id286 30.677466
    id287 33.869492
    id288 33.869492
    id289 23.970184
    id290 23.970184
    id291 27.162210
    id292 23.970184
    id293 23.970184
    id294 13.610462
    id295 1.335104
    id296 13.610462
    id297 6.903180
    id298 6.082873
    id299 159.722771
    id300 28.371221
    id301 25.179196
    id302 28.371221
    id303 30.408988
    id304 30.408988
    id305 19.474266
    id306 147.447412
    id307 159.722771
    id308 149.823463
    id309 149.823463
    id310 19.101521
    id311 19.101521
    id312 19.101521
    id313 30.803839
    id314 31.911031
    id315 30.803839
    id316 30.803839
    id317 153.015489
    id318 149.823463
    id319 9.899308
    id320 6.707282
    id321 9.899308
    id322 9.899308
    id325 3.192025
    id328 12.275359
    id330 12.275359
    id331 5.568077
    id333 135.147122
    id334 147.422481
    id335 16.461375
    id336 16.461375
    id337 16.461375
    id340 145.148548
    id341 0.195377
    id342 3.192025
    id344 2.752871
    id347 163.876420
    id348 153.977112
    id349 153.977112
    id350 22.969456
    id351 22.969456
    id352 22.969456
    id353 30.031414
    id354 26.839389
    id355 30.031414
    id356 30.031414
    id357 16.453939
    id358 16.453939
    id359 157.169138
    id360 153.977112
    id361 14.052957
    id362 10.860931
    id363 14.052957
    id364 14.052957
    id365 4.153649
    id366 4.153649
    id367 7.345674
    id368 4.153649
    id369 4.153649
    id370 12.275359
    id372 12.275359
    id373 5.568077
    id374 4.747770
    id375 15.563864
    id376 27.839223
    id377 17.939916
    Rgid53 -14.257308
    All other reduced costs in the range 1-324 are 0.
    아이콘삭제
  • 비회원2017-07-31
    I simply could not go away your website before suggesting that I extremely enjoyed the standard info a person provide on your visitors? Is gonna be back conitnuously in order to check out new posts.
    아이콘삭제

댓글 입력