- 질문 게시판입니다.
Date 20/02/07 13:55:24수정됨
Name   소반
Subject   부등식이 너무 어렵습니다.
x + 2y >= 10
3x + 5y >= 20
미지수가 모두 0 이상의 정수일 때 x+y가 최소가 되는 x, y의 값을 구하라.

3x + 2y + 3z >= 50
2x + y + 2z >= 70
3x + 3y + z >= 80
미지수가 모두 0 이상의 정수일 때 x+y+z가 최소가 되는  x, y, z의 값을 구하라.

위 두 문제가 있는데 푸는 방법을 모르겠습니다 -_-;;

예전에 배운 수학을 다 까먹어가지고... 풀다가 안 돼서 도움을 구하고자 이렇게 글 올려봅니다.

도움 주실 분들께 미리 감사드립니다.



0


헬리제의우울
아무도 도움을 주지 못햇다고 한다
회색사과
저는 공간에 그리고 문제가되는 면을 이동시켜서 만나는 점을 찾겠습니다.
1
십자 긋고 그래프 3개 영역 맹글어서 선 긋는 건 할 수 있을 것 같은데 면의 이동도 손으로 그릴 수 있을까요?? 시도해본 적이 없어 여쭤봅니당
3개 미지수는 귀찮고.. 1번은 5네요
와... 이것도 툴이 있었군요 치팅 역시 최고야 너무 멋있어..

혹시 Cutting-plane method처럼 변수와 부등식이 4개, 5개, ...n개일 때도 해결할 수 있는 풀이법이 있을까요?
네 저건 n개일때 확장되는 방법이에요

https://en.m.wikipedia.org/wiki/Simplex_algorithm
마술사
simplex method는 정수제약이 없는 Linear programming에만 적용가능합니다
본문처럼 정수제약이 있는경우엔 사용못하죠
운좋게 LP해가 IP해랑 같은경우는 있겠습니다만..
예 격자점이면 심플렉스는 안되고 커팅플레인만 되긴 하겠네요
정수제약(IP)문제는 n개일때 풀수있는 Polynomial한 일반적 방법론이 없어요. 발견하신다면 수학 7대난제 (P=/=NP) 를 무너뜨릴수 있는 중대발견이 될겁니다.
예 커팅플레인은 근처 격자점들 위에서 조합 개수만큼 봐야 하니까 NP겠죠. 헷갈렸습니다
바나나코우
첫번째 문제에서 두번째 부등식은 있으나마나한 조건 아닌가요?
1
CONTAXND
지나가던 이과생입니다.

마저 지나가겠습니다.
5
사이시옷
지나가는중입니다.
1
아나키
여백이 부족하여...
이웃집개발자
여기가 그 아무튼 뭐 이과생들 지나가는 명소라면서요
Integer Programming 문제네요. 제가 대학원에서 관련 전공을 했었고 대학원 조교할때 대학원생들에 관련 수업도 했었죠. 미지수 2개일땐 그래프그려서 풀면되고 수십 수백개 이하정도면 branch and bound 알고리즘으로 풀면되지만 branch and bound 풀려면 LP솔루션이 있어야하는지라...이 댓글만으론 설명이 어렵습니다. 한마디로 일반적으로 풀수있는 방법론이 있는 문제는 아니란거죠
왠지 어렵더라니... 저한테만 어려운 게 아니었군요!
별바라기
그냥 Enumeration해도 되고요.
사실 그걸 다 하긴 너무 어려우니까..
마술사님께서 말씀하신 branch and bound 같은 방법이 나오게 됩니다.

저 문제에서 정수제약을 제거한 문제를 풀어보시겠어요? 만약 그 문제의 optimal solution이 integer point면 끝나고 아니라면.. 상황이 귀찮아집니다 :)
목록
번호 제목 이름 날짜 조회 추천
공지 질문 게시판 이용 규정 11 토비 15/06/19 24497 4
16677 체육/스포츠첫 런닝 관련 초보 질문 사항 3 아재 25/04/16 161 0
16676 기타차단기 문제 7 왕킹멍 25/04/15 262 0
16675 체육/스포츠초 6 여아 극기체험용 등산가방추천부탁드립니다. 5 FTHR컨설팅 25/04/15 261 0
16674 의료/건강왼쪽 오른쪽 시력차이가 엄청 크네요 5 OneV 25/04/15 327 0
16672 기타소형차 중고 가격및 유지비 질문드립니다 5 셀레네 25/04/14 304 0
16671 IT/컴퓨터중국산 로봇청소기 사생활 위험 어떻게 보시나요 8 당근매니아 25/04/14 435 0
16670 가정/육아매트리스 추천을 부탁드립니다 :) 9 Broccoli 25/04/14 253 0
16669 법률양도세 계산 관련하여 질문 있습니다. 8 [익명] 25/04/14 297 0
16668 기타서울 남쪽에 아버지 모시고 식사할 곳 찾는 중입니다. 4 퍼그 25/04/14 271 0
16667 기타인터넷 질문입니다 5 김치찌개 25/04/14 212 0
16666 의료/건강건강보험 3자행위 신고 질문입니다. 2 [익명] 25/04/13 351 0
16665 기타1500 이하로 살 수 있는 중고 suv 추천해주십시오 11 개백정 25/04/13 629 0
16664 IT/컴퓨터컴퓨터 정리 프로그램 추천부탁드립니다. 홍차넷 선생님들!! 13 Mandarin 25/04/11 518 0
16663 기타일본여행 항공권 선택장애 질문드립니다 28 쉬군 25/04/10 656 0
16662 법률내용증명 보내는데 주소를 몰라요! 8 유니브로 25/04/10 616 0
16661 체육/스포츠튼튼한 수영복 브랜드 무엇이 좋나요? 16 열한시육분 25/04/10 531 0
16660 기타리클라이너 의자 추천 18 노는꿀벌 25/04/10 503 0
16659 의료/건강신경과? 신경외과? 어디 가야 할까요? 2 키위 25/04/10 437 0
16658 의료/건강신체에 왼편만 불편함을 느끼고 있습니다 어떤 병원을 가야하나요? 5 [익명] 25/04/09 554 0
16657 IT/컴퓨터맥북이 갑지기 먹통이되었습니다 3 FTHR컨설팅 25/04/08 288 0
16656 게임디비전류 게임 추천해주십시오 4 린디합도그 25/04/08 274 0
16655 여행해외(일본) 여행을 처음 가보려합니다 11 JUFAFA 25/04/08 478 0
16654 IT/컴퓨터현재 데스크탑을 델 미니pc가 대체할 수 있겠죠..? 29 even&odds 25/04/07 755 0
16653 IT/컴퓨터컴퓨터가 글씨큰모드?로 부팅됩니다 ㅜㅜ 18 even&odds 25/04/07 399 0
목록

+ : 최근 2시간내에 달린 댓글
+ : 최근 4시간내에 달린 댓글

댓글
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기