Info
이 질문은 마감되었습니다. 편집하거나 답변을 올리려면 질문을 다시 여십시오.
이 질문을 팔로우합니다.
- 팔로우하는 게시물 피드에서 업데이트를 확인할 수 있습니다.
- 정보 수신 기본 설정에 따라 이메일을 받을 수 있습니다.
Why does linprog generate a 7D optimal solution for 6D simplex problem
조회 수: 1 (최근 30일)
이전 댓글 표시
When running linprog with 6x18 constraint matrix (m=6,n=18) and 6x1 b vector, the "optimal" solution generated has 7 nonzero elements when it should only be 6. Why is this the case? I have my own implementation of simplex which comes up with a different solution (6 as apposed to 7 nonzero entries) but both have the same objective function value when evaluated at the solution point.
댓글 수: 10
Thomas Kirven
2019년 3월 18일
Sure! here's the code
A =[150 150 150 150 0 0 0 0 -150 -150 0 0 0 0 0 0 0 0;
0 -50 0 50 0 0 120 -120 -100 100 0 30 0 -30 0 0 0 0;
50 0 -50 0 -120 120 0 0 0 0 -30 0 30 0 -60 60 60 -60;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 60 -60 -60;
350 0 -350 0 -120 120 0 0 0 0 -120 0 120 0 -60 60 60 -60;
0 350 0 -350 0 0 -120 120 -150 150 0 -120 0 120 0 0 0 0];
b = [63, -23, -43, 29, -54, 20];
f = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];
lb = zeros(1,18);
linprog(f,[],[],A,b,lb)
%% result
ans =
0.1028
0.0838
0.1395
0.0938
0.1014
0.0000
0.0000
0.1958
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.4833
0.0000
0.0000
0.0000
The (non-matlab) solution I get has non zero elements 1,3,4,5,8,15 as follows
0.186667, 0.223333, 0.010000, 0.101389, 0.195833, 0.483333
Thomas Kirven
2019년 3월 18일
편집: Thomas Kirven
2019년 3월 18일
Actually upon second look the solutions have the same objective function value, but different soution values... interesting. I guess it isn't really specified that matlab should use only 6 entries of the solution vector, I guess my question is then: Is there a way to specify this constraint?
Matt J
2019년 3월 20일
편집: Matt J
2019년 3월 20일
Actually upon second look the solutions have the same objective function value, but different soution values
Your solution with 7 non-zeros doesn't really even seem to be a solution. It doesn't satisfy the equlaity constraints very well. Are you sure it comes from the exact code that you have posted?
Mary Fenelon
2019년 3월 20일
The default algorithm in R2016b is the interior-point-legacy solver; it was changed to dual-simplex in 17a. Simplex algorithms move from vertex to vertex of the feasible region but interior point algorithms move through the middle. When there are multiple optimal x vectors, the interior point algorithm may return a point in the middle. It will be a linear combination of some of the optimal vertex points.
Thomas Kirven
2019년 3월 20일
Matt J, yep this is the exact code and the solution. Also I checked the solution and it does seem to be correct:
A*linprog(f,[],[],A,b,lb)
gives
ans =
63.0000
-23.0000
-43.0000
29.0000
-54.0000
20.0000
which is b.
Thomas Kirven
2019년 3월 20일
편집: Thomas Kirven
2019년 3월 20일
Thank you very much Mary! I think this makes sense now! A linear combination of vertices on the simplex would totally explain why there are 7 non-zero values. In fact it looks like the solution the interior point comes up with is a linear combination of my independently obtained solution and the matlab dual simplex solution Matt provided. Cool!
이 질문은 마감되었습니다.
답변 (1개)
이 질문은 마감되었습니다.
참고 항목
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!오류 발생
페이지가 변경되었기 때문에 동작을 완료할 수 없습니다. 업데이트된 상태를 보려면 페이지를 다시 불러오십시오.
웹사이트 선택
번역된 콘텐츠를 보고 지역별 이벤트와 혜택을 살펴보려면 웹사이트를 선택하십시오. 현재 계신 지역에 따라 다음 웹사이트를 권장합니다:
또한 다음 목록에서 웹사이트를 선택하실 수도 있습니다.
사이트 성능 최적화 방법
최고의 사이트 성능을 위해 중국 사이트(중국어 또는 영어)를 선택하십시오. 현재 계신 지역에서는 다른 국가의 MathWorks 사이트 방문이 최적화되지 않았습니다.
미주
- América Latina (Español)
- Canada (English)
- United States (English)
유럽
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
아시아 태평양
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)