- 질문 게시판입니다.
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면 끝나고 아니라면.. 상황이 귀찮아집니다 :)
목록
번호 제목 이름 날짜 조회 추천
9674 교육고1 수학 문제를 못풀겠습니다. 10 귀차니스트 20/06/27 5231 0
9664 교육지금 학원 다니시는분 계신가요? 7 copin 20/06/26 4193 0
9655 교육9급 공무원 면접 무엇을 준비해야 하는지요? 9 [익명] 20/06/23 3488 0
9633 교육내일배움카드 써야하는데 1 [익명] 20/06/21 2687 0
9502 교육우리집으로 보내줘. 6 명월 20/05/29 3999 0
9445 교육영어 듣기 좋은 방법 5 [익명] 20/05/19 2987 0
9392 교육영어 문장 해석 질문입니다 5 [익명] 20/05/13 2920 0
9388 교육태블릿 pc 삭제된 어플 설치 내역 확인 방법 즐겁게 20/05/12 2679 0
9301 교육토익 part 7만 풀수 있는 문제집 없을까요? [익명] 20/04/30 2777 0
9292 교육관련 분야를 전공하지 않은 사람이 그 분야를 얼마나 깊이 알 수 있을까요? 39 소반 20/04/29 5985 0
9256 교육영어로 컨텐츠 소비 많이 하시는 분 어떤 거 보시나요? 27 조드 20/04/23 5187 0
9200 교육외국 대학 제출용 영문 성적표 발급 시 대표자 날인은? 1 [익명] 20/04/17 3289 0
9143 교육운전연수가 필요할까요? 20 OshiN 20/04/07 5474 0
9139 교육영어 초보를 위한 문답 사이트 없을까요? 15 활활태워라 20/04/07 4344 0
8990 교육대학교 사이버 강의 질문합니다 3 세무회계연습 20/03/16 3474 0
8874 교육영어 스피킹 실력에 때문에 불안합니다 24 이마트 20/02/27 4720 0
8856 교육공부에서 요령을 터득하는 방법은 무엇일까요? 26 Algomás 20/02/25 4611 2
8742 교육부등식이 너무 어렵습니다. 19 소반 20/02/07 3630 0
8672 교육좋은 중국어 글이 읽어보고 싶습니다. 8 [익명] 20/01/24 3412 0
8621 교육해외대학 여름학기 선택 7 한겨울 20/01/11 2826 0
8579 교육대학생의 공부법(?) 20 [익명] 20/01/02 3118 0
8561 교육대학생들 대상으로 뭔가를 홍보해야 하는데요. 10 [익명] 19/12/30 2561 0
8538 교육한국사능력검정시험(한능검)을 보려고 합니다. 32 CONTAXND 19/12/26 5031 0
8476 교육다들 책 한 권 완독 얼마나 걸리세요? 17 BBBvenr 19/12/14 6259 0
8393 교육한국어 발음 질문 39 원영사랑 19/12/02 6353 0
목록

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

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