새 노트

- 문제는 영어로 이름이 되다.

할당 과제 할 때 똑같은 어사인먼트 할당 문제는 1:1 대응 문제야 1:1 대응 문제는 매칭 문제야

매칭은 우리나라로 하면 짝짓기 문제야. 짝이 뭔지 알아? 짝이?

작은 초등학교 교실. 초등학교 교실은 선생님 앞에 서있고, 선생님 앞에 있는게 있고, 그 다음에 초등학교 교실을 클래스룸에 이렇게 책상이 되어 있다.

두 사람씩 앉지? 그럼 여기 남학생 하나 앉고 여학생 하나 앉고 이렇게 앉혀요. 그렇게 같이 앉아있는 학생 둘이 짝이야. 알겠어요? 네. 바로 옆에 앉아있는 사람이 짝이다 이거지. 참.

짝짓기고 뭔 소리냐 여기 지금 왼쪽에 기계가 있고 오른쪽에 파트들이 있어 왼쪽에 있는 기계들이 생긴거 다 비슷비슷하게 생겼어 이게 뭐 만드는 기계야 기계 1 기계 2 사안에서 이 기계 1 2 3 4 4 4가지를 다 만들 수 있어 일본이 부품 1

부품 1도 만들 수 있고 부품 2도 만들 수 있고 이것도 만들 수 있고 이것도 만들 수 있어. 오케이? 두 번째 기계도 네 가지 부품을 다 만들 수 있어. 네 개 기계가 다 오른쪽에는 네 가지 부품을 다 만들 수 있는 거야.

중분 한방 기계를 여러개를 만드는게 아니라 한 기계가 한가지 부품만 만들기로 하자 하나의 기계가 한가지 부품만 만든다 그 얘기는 뭐냐 하나의 부품은 하나의 기계로만 만든다 다시 말하면

1번 기계가 이것만 만든다 그러면 얘는 이거로만 만든다 이거야. 여기서 이렇게 2번도 이거 만들고 이렇게 하면 안 된다 이거지. 얘도 하나만 고르고 얘도 하나만 고르고 그게 1:1 one to one 매칭이에요.

1:1 수학에서 중요한 개념은 1:1 매칭이 여러분 함수 배울 때 1:1 대응 지금 얘기하지 말고 어쨌든 여기 이런 비용표가 주어져 있어요 할당 문제는 이 표가 사실 할당 문제가 아니라 운송문제에서도 똑같이 이런 표가 주어졌었지 발전소에서 도시로 가는 비용 그런데 발전소 용량도 다르고 도시마다 수요도 달랐단 말이야 이번에는 공급 용량이

여기서 하나만 만든다는게 아니라 한개 부품은 만든다. 발전소 하나가 도시 하나만 딱 책임진다 이런식의 개념이라는 말이지. 도시 하나는 발전소 한군데에서만 전기를 받는다. 이 개념이다 이거야. 여기가 전부 다 1111이다 이거야. 이게 무슨 얘기인고 하니

기계 1은 부품기, 여기 잡이라고 되어있는데 이 4중에 하나만 고르라 이거야. 쉽죠? 네. 어떻게? 이 비용이 여기 준비 비용이라고 되어있는데 이 준비 비용은 용어로 셋업 포스트에요. 셋업 포스트에 합의 미니마이저에

총 준비 비용을 최소화한다. 미리 말해줘야 돼. 그냥 코스트하냐. 썸 없애로 코스트지. 자 그러면은 자 고너스 점수 여학생 4명하고 남학생 4명이 미팅을 하는데 짝짓는 방법.

16가지 공식으로 하면 4 팩토리얼이에요. 24가지야 우리 베트남 학생들 팩토리얼이 뭔지 알아요? 느낌 벽이요

이거 이거

1대1 대응의 방법의 수. 우리나라는 방법이라고 적용의 수. 작업이 남자고 부품이 여자라고 생각하고자 이거야.

남자 4명하고 여자 4명이 있는데 남자 넷하고 여자 넷을 1대1로 대응시키는 방법 하면 4의 팩토리얼이에요. 왜? 일단 남자 1번부터 순서는 바꿔서 상관없죠. 남자 1번부터 선택하기에는 몇 가지를 고를 수 있어요. 4명을 고를 수 있어요. 여자 4명 중 하나를 고를 수 있어요.

하나 빠지면은 두 번째 남자는 나머지 3명의 여자 중에 하나를 뽑을 수 있어요. 그 다음에 그 다음은 두 밖에 안 넘어요. 마지막은 선택권이 없죠. 4x3x2x1 이런 식으로 되는 겁니다. 5대 5명끼리 한다? 그러면 5 팩토리얼. 10명이면 10 팩토리얼 이렇게 되는 거예요. 자 이 문제는

4대 4대 있는 상황에서 1대1 짝짓기 2리라지 좀 다 해 볼 수 있어 어렵지 않아 근데 우리가 원하는 것은 그런 전수 조사가 아니고 전수조사 영어 토탈 인유로 의지 어 일단 대표적인 방법이 뭐 하여서

음 수걸대가 방법이 있는데 한 가지 방법 그 중의 하나는 뭡니까 1번이 1 2번이 2 3 2 3 4 4 이렇게 연결해 대학선 1번은 1 2번은 2 3번은 3 4번은 4 그러면 총 비용이 어떻게 돼요 요거 요거 요거 요거 더하면 되는 거야 딱 봐도 숫자가 크지

네. 좋은 매칭이 아니라 이 말이에요. 좋은 어셋먼트가 아니에요. 또 다른 방법은 1번은 4번, 2번은 3번은 2번은 4번은 1번. 이렇게 하면 어때요? 숫자가. 아까보다 숫자가 작지. 네. 이게 아까보다는 좀 비용이 더 저렴한 1:1 매칭이 된다 이거야. 이런 식으로 해서 24가지 다 따져볼 수 있는데 그렇게 안 하고 효율적으로 하는 방법은 제가. 뭐 효율적으로 안 하고 그냥 포뮬레이션 해서

어플 수도 있고 이 문제를 부실게 보는 건 이걸 선용 모형으로 엑셀 풀자 도 딱 그냥 표만 갖고서도 풀 수 있어 표만 갖고 표만 갖고서 푸는 방법에 대해서 잠깐 생각해요. 이거 학기마다 내 기분에 따라서 표만 갖고 푸는 방법을 하기도 하고 안 하게 돼요. 이번 학기는 뭐 해 볼만 할 것 같아요. 만약에 반행별로 안 좋은 것은 안 하는데

어쨌든 이거를 운송문제로 운송문제의 관점에서 본다 그러면 모형이 어떻게 만들어지나? 모형이요? 선형 모형, 선형 최적한 모형. 운송문제의 특별한 키스라고 그랬잖아. 아까 운송모형의 프레임웍을 따른다 이 말이야.

아까 배송 문제 안에 운송 문제 트랜스포티션 트랜스포티션 안에 이 어사이먼트 문제가 있다고 그랬죠? 네 운송 문제 관점에서 발전소 도시 관점을 보면 공급마디가 몇 개야? 4개 수요마디는? 4개 마디가 총? 8개 8개 그럼 가지는? 16개

가지가 16개야 아까 말씀드린 대로 그러면 선형모형의 변수는 16개 가지수만큼 16개가 변수가 나오고 제약은 8개 해서 나와요 이게 다음 스프라이드에 있죠 이게 할당 문제의 선형모형이야

근데 보면은 저 목적함수에 있는 숫자들 어디서 왔어? 그 비용 비용표에서 왔지 그 다음에 이제 밑에를 보면은 제약직이 8개인데 위에 4개는 기계제약이고 밑에 4개는 부품제약이야 저거를 쫙 늘었으면 어떤 모양일건지 상상이 돼요? 엑셀로 엑셀표가 있나?

엑셀표가 없는데 이걸 엑셀에다 딱 넣는다 그러면은 어떤 모양이 되느냐 엑스 원 원 원 투 원 트리 원 포 그 다음에는 투 원 투 투 투 트리 투 포 그 다음에 트리 원 트리 트리 트리 포가 나오고 그 다음에 포 원에서 포 포 이렇게 나와요

이게 공급제약이야. 그 다음에 수요제약은 어떻게 되겠어요? 이쪽 품품제약은 X11, 21, 31, 41. 이렇게? 그래서 어떤 모양이 돼? 이건 대각선으로 내려오죠. 1, 2, 1, 3

1, 4, 2, 2, 3, 2, 4, 3, 2, 3, 2, 3, 4, 4, 2, 4, 3, 4, 4, 2, 3, 4, 4, 2, 3, 4, 4. 이런 모양이 된다고 지나면 한번 했었죠? 네. 그리고 오른쪽은 전부 다?

1 우빈 전부는 1이야 공급제약, 수료제약 근데 이거 정수제약 안 써도 돼요? 정수제약 안 써도 돼요 그러면 무조건 정수는 나와 이 실질적은 뭐예요? 05-1이야

할당을 하는 거니까 일단 마이너스는 될 수 없죠. 그러니까 보내는 거라고. 하나를 보내고 하나를 받는 거니까 절대로 변수가 마이너스는 될 수 없어. 0보다 큰 건 당연한 거고. 1보다 커도 안 돼. 일단 1보다 크게 내보낼 수도 없고 1보다 크게 받을 수도 없어. 그래서 모든 변수들은 전부다 0에서 1 사이인데 실질적으로 풀어보면 0안이 미니나고.

아 아 오케이 아 예를 들면 아 이래서 이런 경우 없습니까 아 여기 이쪽 일본에서 1로 0.5 보내고 뭐 이를 해서 이쪽으로도 0.5 보내고

10.5, 10.5. 이거 가능하지 않냐. 어차피 1이 나가는 거니까 쪼개서 2군데로 보내고 받는 것도 2군데서 0.5씩 받아서 합쳐서 1이 되죠? 네. 만약 이게 비용이 취소가 된다고 그러면 그냥 1, 이쪽으로 보낸 거랑 똑같아 가세요.

굳이 0.5씩 나가는 것이 없습니다. 정수 제약 없이 여기서 사실 정수가 이진변수가 되는건데 이진변수 제약 없이 무조건 솔로시 0개도 나옵니다. 0.5 쪼개져서 나오지 않아요. 자 그건 이제 더 복잡한 이론적인 배경이 있는데 그다 구시하고

결국 그림을 그리면 이렇게 되는 겁니다.

이렇게 드는거에요. 자 이걸 한겁니다. 마디는 4+4=8개 가지는 4+3=16개 마디가 제약

가지가 변수 자 이게 됐고 이집 변수 제약들 주로 소르신은 항상 0도에 있는 가운데 그리고 일단 방법의 수는 n 팩토리아이고 4 팩토리아는 20, 20대인 가지

솔루션 피의적으로 솔루션이죠

스몰네이비가 다르다. 자, 근데 이 문제를 푸는 방법을 할당 문제 해법이라고 하는데 영어 이름이 있어. assignment method가 아니고, hungarian method이에요. hungarian은 나라 이름이죠. hungarian은 동유럽에 있는 나라 이름인데 이쪽 동네 사람들이 이런 수학을 특별히 잘하는 건 아니지만 많이 해. 이런 수학이 어떤 쪽이냐? discrete method라고 해요.

디스크이 통계가 나오는데 디스크이 뭐지? 우리나라 수학과가 이산수학이라는게 있어 컴퓨터사이언스에서도 배우고 지속기를 구하는 방법을 헝가리아 수학자가 개발한 것 같은데 이게 아주 대단한거면 사람 이름을 붙여줄텐데 그렇게 대단한건 아닌것 같아요 어쨌든 이른바 이름이 헝가리아 메스라고 붙었어 자 아이디어를 보면은

나름 기반은 아이디어예요. 여기에도 절차가 있습니다. 절차가 있는데 이 절차는 뭐 그냥 처음 보면 무슨 말인지 볼 때니까 직접 바로 예제로 들어갈게요. 자, 공간에 배송도 뭐라고? 할당 문제에 최적기를 구하는 해법이에요. 근데 그거를 엑셀이나 뭐 이렇게 해서 하지 않고 이 표만 갖고 비용 표만 갖고서 최적기를 구하는 방법이다 이거지.

어떻게 하느냐? Step 1a. Step을 차차차. 내가 살 건데. 기본적으로 알고리즘이 다 그렇지만, 동일한 그런 과정을 반복하는 겁니다. 어떤 과정? 그 중에서 제일 첫 번째 뭐냐? 각 행에서 최소각 차감. 어려운 얘기 아니죠. 각 행에서.

행이 몇 개 있어? 4개 있어. 1번부터 시작해서 첫번째 행부터 시작해서 취계속 값을 차감하라. 어떤 취계속 값? 그 행에서 가장 작은 값을 차감하라. 빼라 이거야. 어디서? 그 행들 각각 원소들이 있어. 그럼 1행에 14, 5, 8, 7이 있는데 이 4개의 숫자에서 가장 작은 값을 찾고 가장 작은 값을 4개의 숫자에서 빼주라 이거야. 그럼 어떻게 돼요?

일단 가장 작은 것은 5야. 14에서 5를 빼면 9. 5에서 5빼면 0. 8에서 5빼면 37에서 5빼면 2. 오케이? 알겠어요? 외국 학생들. 이렇게 공들이면 시험이 나오는 겁니다. 제가 신경써서요. 두 번째는 똑같이. 두 번째 가장 작은 것은

2를 다 빼 뺐더니 0, 14 상태에서 오케이? 네 3행에서 가장 짜는 3이야 3을 다 빼 4행에서 가장 짜는 2야 2를 다 빼 여기 새로운 테이블이 나왔어요 이게 뭐였어? 이게 무슨 테이블이었어?

비용. 비용표였어. 이걸 숫자를 바꿨어. 숫자를 바꿔도 되나? 이게 지금 뭐라는 건가? 여러분들이 연립방정식의 해법을 공부를 했으면 무슨 말인지 훨씬 이해가 쉬울 텐데.

-무늬한 식물을 잘 안 넣어. -무늬한 식물을 잘 안 넣어. -무늬한 식물을 잘 안 넣어.

선영대 수가 아예 아이고 하는데도 그런 어 성대서 매우 중요합니다. 우리가 이 방법에서 필요한 것만은 이제 정보가 돼요. 100% 행렬, 11방정지, 그 다음에 보면 이게 자꾸 크게 나와요. 로우 에셀럿 폼, 가오시안 엘리미네이션, 리니어 디펜던스, 매트릭 인걸스, 솔루션, 이렇게 나와 있는데 이 부분을 지금 잠깐 볼 거란 말이에요. 이 부분은 시스템을 포함하고, 로우 에셀럿 폼, 가오시안 엘리미네이션, 이렇게 나와 있는데

으 널리 깡 정식을 푸는게 바로 고 밑에 나와 있는 그 절차가 하는 겁니다 10 방정식 풀이 절차야 뭐 에서 어 가오쎄 내내 되시오 가오스는 정규 분투어 5를 발견한 사람으로 유명한데 어떤 것 같아요

여러분들 고등학교에서 열일 방정식 풀 때 무슨 법? 무슨 법? 배웠다고 기억나요? 무슨 법? 무슨 법? 소거법? 소거법? 대입? 대입법? 하나 더? 과강법 없었어요? 있었어요? 아 어쨌든 그런 그런 적 있지. 모른다 잊어라. 고등학교에서 병원 다 잊어버리고 이렇게 풀면 돼요 무조건

일단 열린 방정식이 주어졌을 때 열방 중계자 쪽이 이제 밑에 열방 중계 지금 이 대결 방정식이 될까요? 어떻게 된다? 여기 있을 수 있다. 왼쪽에 AATRIX가 그 기술 행렬이고 그 다음에 X가 변수 벡터 그 다음에 오른쪽에 이제 무별 상수 행렬

네 자 지금 x1부터 xn까지 있는 변수들은 일단 문제를 푸는데는 아무런 쓸모가 없어 x1이 뭐, x2가 뭐 값을 결정할 건데 문제를 푸는 데는 뭐하고 뭐가 필요하냐 a하고 d만 필요해요 a는 뭐? 기회수행렬 d는 무비한 상수값 그것만 있으면 돼요 그래서 그 두 개를

이렇게 하나의 행렬을 나타낸 걸 augmented matrix라고 해요 기타나 피아노나 무슨 뭐 배워서 코드 같은 거 배웠으면 augmented code라는 게 있는데 반을 올린 거 모두 반을 올린 걸 augmented라고 해요 A라는 행렬에다가 열을 하나 더 붙였다 이거예요 증축을 했다 이거 증축을 그래서 이걸 augmented matrix라고 해요 저 augmented matrix만 있으면 이제 열립방정식 풀 수 있다 이거예요 밑에 그 예전 무시하고 밑에 걸 무시하고 자 여기 열립방정식 나왔고

열 방식을 푸는 거로 빨라 보니까 풀다 푸는 거로 넘어 볼게요 자 여기 지금 2 곱하기 2 열린방식 2 곱하기 2라고 하면 행의 숫자가 2개고 식의 숫자가 2개 그 다음에 변수의 숫자가 미지수의 숫자가 2개라는 겁니다 앞에 게 행의 수 그 다음에 두 번째 게 열의 수인데

행위 시계수고 여리 검수 수요 자 2호 파기에서 기술 행정만 왼쪽에 있는 게 x는 말고 에서 앞에 계획해서 1 1 1 - 2 뽑아낸 거예요 그게 대문자 A 행정 무력까지 붙여 놓게 지금 오면이 매일 3 2 4를 붙였어 그 사이에다가 줄을 하나 더 더 더 안고 좋아 자 그러면 저것만 갖고서 솔루션을 구할 수 있다 그랬는데

이걸 갖고 여러분들이 그냥 보답필때 했던 식으로 뭐 가감법 베이버 소음법 해도 되는데 우리가 하는 건 뭐냐 여기 나와있는 이 고급된 매트릭스를 매트릭스 특히 요 부분 A행렬 부분을 우리가 원하는 모양으로 바꿀거에요 우리가 원하는 모양이 어떤 모양이냐 솔루션을

결정할 수 있는 모양으로 상태로 바꾼 거고 그게 이제 아까 말했던 로우 애슐런드 폼이라는 거예요. 로우 애슐런드 폼을 하면은 솔리스를 금방 읽을 수 있는데 어떻게 하느냐 기본적으로 행조작이라는 걸 할 거야. 행조작은 영어로 로우 오프레이션이라고 해요. 로우 오프레이션은 뭐냐? 행 단위로

숫자를 곱하고 그 다음에 어떤 행에다 숫자를 곱해서 다른 행에다가 더하거나 빼고 이게 행 조작입니다. 그러면 이 숫자들이 막 바뀌겠지. 그렇잖아요. 숫자를 어떤 행에다 숫자를 곱한다거나 아니면 어떤 행에서 숫자를 곱해서 다른 행에다가 더하거나 빼고 숫자가 바뀔 거 아니에요. 여기서 중요한 건 그렇게 해도 솔루션이 바뀌지 않는다.

그래서 솔루션이 바뀌지 않는다는 말은 변경되기 전에 고그멘틴 매트릭스나 행 조작을 한 다음에 얻은 고그멘틴 매트릭스나 솔루션이 똑같은 얘기인데 그렇게 솔루션이 똑같은 고그멘틴 매트릭스 또는 연립방정식입니다. Equivalent System이라고 생각해요.

이 퀴벌트는 뭐야? 뭐 대등하다 동등하는 말이지. 솔루션이 같은 시스템이에요. 일단 우리가 원하는 모양은 이런 모양입니다. 원래는 이런 모양이 있잖아요. 저렇게. 네모 직사각형. 왼쪽도 직사각형. 왼쪽이 직사각형 모양이 있잖아요. 제가 어떤 모양을 바꿀고 하니?

이런 모양을 바꾸겠다 얘가 어떤 모양? 삼각형 삼각형 또는 역삼각형 모양으로 바꾸겠다 얘가 있지 이 아랫부분이 전부 다 0이 된다 얘가 돼야 계수 행렬에서 아니면 저 윗부분을 0으로 가지고 아랫부분만 남겨도 되고 그럼 뭐가 좋아요? 그 밑에부터 계산하면 밑에서부터 계산을 하나씩 하나씩 미술을 결정하는 과정을 우리가 백 섭스티투션 이름을 그렇게 붙였어 밑에서부터 섭스티투션 해가지고 미시스카스 결정에서 거꾸로 올라와라.

가능하죠. X4 결정하면 그걸로 3결정하고 X3, X2 결정하고 2, 3, 4가 1결정하고 이게 100%디지이냐. 그래서 저런 모양으로 바꾸는 트라이블로폼이라고 그러는데 삼각형 모양으로 만드는 게 그게 바로 가우시안 엘리미니션이라고 하는 절차다.

어떻게 그 안쪽에 있는 숫자들을 다 0으로 만들어라. 그게 값의 일리미니에이션이에요. 어떻게? 세 가지. 여기 보시면 좀 전에 봤던 똑같은 전리방정신인데, 얘나 얘나 얘나 얘나

다 이퀴블럭 시스템이야. 무슨 말이냐? 만약에 내가 4개의 영입방송이 다 이퀴블럭하다. 그 얘기는 뭐냐? 솔루션이 똑같다는 얘기예요. 4가지가. 그러면 첫 번째 걸 주고서 솔루션을 찾으라고 하는 거라 이거 주고서 솔루션을 찾으라고 어떤 게 더 쉬워요? 제 거요. 이게 쉽지. 이거 딱 X1, X2, X2를 말해서 쉽지. 이건 어때? 이것도 어렵지 않지? X2, 1.

그 다음에 백성 스튜션에서 X2가 X2가 결정할 수 있잖아요. 저거를 이런 모양으로 바꾸는 걸 우리가 이제 가오시안 엘리미니에이션이라고 하고 바꿀 때 구체적으로 어떤 절차를 쓰느냐가 그게 로우 오프레이션 행조작이라고 하는 거예요. 행조작이 뭐냐? 어떤 세 가지가 있어요. Three operations on the system will not change the solution set. 솔루션 셋이라고 부르는데 이 솔루션 셋을 바꾸지 않는다 이거지

우리가 지금 제가 구체적인 내용 잠깐 스킵하고 다시 돌아가서 여기서 각 행에서 최소값을 차감하면 새로운 비용표가 나오는데 새로운 비용표가 나와도 원래 문제의 솔루션이 바뀌지 않는다

오케이 이 문제를 풀어서 얻는 그 1대1 짝짓기 매칭 결과나 이거를 비용표라고 생각하고 풀었을 때 없는 1대1 짝짓기가 똑같다 단 비용은 달라지지 막 숫자를 지금 뺐으니까 이 비용은 짝기지 하지만 여기서 비용을 뺄 때 숫자를 잘 기록해 두거나 아니면 이걸 가지고 여기서 쏘는 줄 알았어 원래 문제 돌아서 짝짓기 해갖고 거기서 비용을 결정하면 돼

우리가 우리가 원하는 어떤 기계가 어떤 부품을 생산한다는 것만 해야지 그렇게 짝짓기야 비용이 최소화된다는 것만 차지면 되는 거니까 그 다음에 그걸 찾았으면 원래 문제로 돌아가서 비용을 계산하면 된다는 말이야 근데 그걸 쉽게 솔루션을 찾기 위해서 이렇게 행해서 최소값을 빼고 그리고 열어서 최소값을 빼고 솔루션은 달라지지 않아

오케이? 네. 생각해보세요. 어쨌든 행에서 체수가 있을 때가, 열어서 체수가 있을 때가. 왜 열어서 체수가 있을 때가. 이런 경우에 있죠. 왜, 여기 행마다 영웅이 다 있죠. 왜, 근데 왜 영웅을 만들까?

최소값을 빼서. 계산하기 쉽게. 응? 뭘 계산하기 쉬워? 변수. 어? 변수 확정 내기 쉽게. 변수? 확정 내기. 어떻게 확정 내기? 근데 열에서는 왜 빼는 거예요? 최소값을?

그래서 왜 지금 빼가 이걸 한거 보다 이거 품기 십더 좀 전에 그 열리방정식 돌아가서 3각 정보의 걸 바꾸면 솔루션 절정에 십다 그랬는데 이거에 상하 쪽으로 만드는 건 아닌데 좀 전에 그런 비율 비교해서 아 그 좀 전에 왼쪽에 있는거

풀게 수 어렵고 딱 봐서는 쏠지 쉽게 결제할 때 이쪽 끝에 빠진 딱 맞았단 말이지 지금 그런 걸 하려면 이걸 봐서 다 모르겠는데 이쪽도 아직 완성되지 않았지 이따가 더 고치면은 소르실 결제가 훨씬 쉬어진다

무슨 논리? 해답할 수 있어. 미리 강의를 공부해야. 연습을 했으면은. 비용이 최소화되는 어사이니컨트를 찾고 싶은 건데.

숫자를 저렇게 바꿨을 때 찾기가 쉬워지네 이 말이야 목적항수의 일부 개수들이 0이 된다는 거죠 그러면 개수가 0이 되면 그 변수는 없어지는데 그렇잖아 변수가 없어지면 쉬워요? 어떻게 쉬워져?

자네는 다시 봐보세요. 어? 지금 여기에서 14, 5, 8, 7, 2, 12, 6, 5, 7, 8, 3, 9, 2, 1, 6, 10 이렇게 되는데 저 숫자가 바뀐 거야 지금. 위에 4개는 전부 다 5를 빼서 9, 0, 3, 2가 되고 그 다음 거는 0, 14, 3 이런 식으로 되고

그 목점에서 변수가 없어져 버리고 변수가 없어지면은 변수가 있는지도 없는지도 물론 물론 밑에는 남아있지 왜 씌워지지? 차이가 확 나서 차이가 확 나서? 그건 좀 약간 교양있는 대답은 아니다 교양은 아니고

좀 약간 인텔리지한 대답은 아니다. 그러니까 그 결국에는 행에서의 최소값들을 기준으로 나아가야 되는 건데 그래서 행에서의 최소값과 다른 값들의 차이를 좀 더 확고히 보기 위해서 그래서 어떻게 하자는 거야? 어떻게 쏘는지를 찾겠다? 그래서 그 4개의 행에서 결국에는 0이 나오는 것들이 하나씩 있을 거 아니에요?

근데 거기서 겹치지 않으면 그걸 확정을 짓고 만약에 이번에 보면 2행과 4행이 첫 번째 열로 겹치는데 그래서 그 겹치는 것들 다음으로 최소값을 찾아서 그 최소값이 더 작은 거를

만약 겹치지 않는다 그러면 그냥 캐소값을 최적해 솔루션을 쉽게 찾을 수 있다는 얘긴데 네 왜? 네? 왜? 겹치지 않으면 왜 최적기를 금방 찾을 수 있어? 그게 가장 미니마이징 하는 방법이니까 좀 더 풀어서?

결국에는 저희가 값을 최소화 시켜야 되는 거니까 비용의 합이지 네 근데 그러기 위해서는 결국엔 행에서의 최소값들을 기준으로 더 나아가야 되는데 만약에 겹치게 된다면 겹치지 않는다면 어떻게 해야 돼요? 총비용이 겹치지 않는다면 그 행으로 확정을 내야지

값이 최소가 되니까 얼마를 최소가 되요? 네? 아 이거 아직 좀 먹을 때 하고 명확하지 않은 것 같아요 자 다른 사람으로 해볼게 자 이 숫자 이것만 이 표를 갖고서는 소로시를 찾기 쉽지 않다 아까 아까 그렇게 물론 이게 딱 뭐 완전한 그 이유는 아니지만

저걸 보면 솔루션을 잘 모르겠는데 이걸 보면 솔루션을 쉽게 알 수 있을 것 같다는 말이야. 완전히 또 이걸 이렇게 했을 때 뭐야. 아주 명쾌한 비유를 안 했지만 대략 그냥 그런 비슷한 시큐에이션인데 이걸 보면 명확하지 않은데 물론 저걸 보수도 할 수 있어. 근데 이걸 딱 보면 확실한 말이지.

지금 우리가 하려고 이렇게 비슷해요. 저쪽 걸 보면 확실하게 보이겠는데 여기서 몇 단계 거치면 솔루션을 확실하게 최적이라고 내가 어? 확실을 가질 수 있을 것 같다. 이 말이에요. 어떤 근거로. 아까는 열리방정식 푸는 건데 한 행에 하나씩 해서 엑스원은 얼마? 엑스원은 얼마? 뭐 이거 당연한 얘기잖아. 근데 여기서.

이게 좀 다른 문제이긴 한데 이렇게 계속해서 몇 번 더 이 절차를 스텝을 몇 번 더 밟아서 비용표를 얻었는데 그걸 보면은 여기서 좀 더 나가는 확실하게 솔루션을 최적할땅이 뭐다라고 알 수 있을 것 같다는 거지. 어려운 문제 아닌데.

총비용의 합은 아무리 작아도 얼마? 최소값의 합 총비용의 합 네 아무리 작아도 얼마야? 각각 행들의 최소값들의 합 뭐 대충 잡아도?

응 근데 0을 왜 안 넣을까? 0이 기준이니까 응? 0이 기준이니까 0이 기준이니까 어 비스 좀 더 그걸 최소값을 해야 되는 거니까 비용을 최소값 각각의

행의 최소값을 기준으로 더 나아가야 되는데 근데 만약에 겹치지 않으면 그게 결국에는 비용을 최소화하는 것 중에 최소값이니까 어떻게? 총 비용 얼만데? 그러니까 다 계산한 거야? 15 그렇게 하면 안 되고 그러니까 네 그러니까 그래서 M1이랑 M3는 5랑 3으로 확정을 지어요 먼저

아 아직 아 그렇게 났습니다 자 결론만 얘기하며 자 이 비용 표랑 2급 숫자는 다르기 때문에 연속에 가서 도안당했다고 해봐요 1번 1번을 가고 2번 2번 어떻게 이런 기계 국립 1 기계 2분 2년 대각선 할당했을 때 총려 얼마라고

30 정도. 30 얼마 되지? 이거는. 그것보다 줄어들었지. 숫자를 뺐으니까. 똑같은 문제인데 숫자가 줄어들었어. 그러니까 우리가 원하는 건 최적해. 어떤 기계가 어떤 부품을 맡아서 하게 된다는 그 결정만 하면 찾으면 되는 거고 그다음에 원래 문제로 돌아가서 비용을 계산하면 되는 거야. 근데 0이 많아잖아.

값이 0이 되는 걸 찾죠. 값이 0이 되는 솔루션을 찾으면 되는 거예요. 근데 여기서 이것을 갖고서 찾을 수 있어? 이것만 갖고? 근데 이게 겹치니까 네. 0, 0, 0, 0 해서 4개를 찾아서 할당이 되면 총 비용이 얼마? 0이지 0, 0, 0, 0으로 하면. 그러니까 그 보다 더 비용이 저렴해질 수는 없지.

그가 우리가 확실히 가질 수 있다고 이게 비용을 주장으로 주니까 물론 총 비용이 영원 아니야 실제 좀 더 원래는 여기로 원래 표로 돌아가서 다시 이제 어떻게 했을 때 옆으로 얼마 되는지 계산해야 되는데 솔루션이 최적해 나는 것은 이 바뀐 표를 보고서 알 수 있다 이거지 근데 현재로는 여기 좀 모질라 0이 좀 더 있으면

0들만 가지고서 1대1 매칭이 되는지 안되지만 차지면 된다 이 말이야 자 그래서 하는게 행해서 최소값이 차감해서 0을 만드는거야 최소값 차감하면 그게 0이 되잖아 최소값이 0이 된다고 그 다음에 0만 갖고 1대1 매칭이 되느냐 보니까 안되지 이게 있어서 그래서

요게 여기로 봐 있으면 딱 되지. 여기가 0이면 그렇지? 근데 여기는 0이 아니고 0이 한 1, 2개가 있으니까 0을 더 만들어야 된단 말이에요. 일단 당장 어디서 만들어? 여기 열에 0이 있어야 되잖아. 그래야지 우리가 확신을 가질 수 있을 거야. 그래서 어떻게 알고? 이번에는 행에서 최소값을 빼서 행마다 0을 만드는 걸 했고 그 다음 단계는

얼마나 0이 있는지 확인해서 없는 데는 0을 만들어줘야 되는데 어떤 어떻게? 여기서 가장 작은 값을 빼서 또 0을 만들어줄 거예요. 아 마음대로 그렇게 숫자를 빼서 됩니까? 솔루션이 달라지 않는다는 걸 증명할 수가 있어요. 이걸 가지고서? 이걸 가지고서.

자 잘 보시면 첫 번째 행에서 5555 빼면 어떻게 되나 14x1이 9x1이 되지 그러면서 5x1만큼 남잖아 옆으로 빼 그 다음에 1x2도 옆으로 빼 그 다음에 5x1도 옆으로 빼 7x1 빼지 5x1도 다 5씩 빼

5 곱하기 x11, 12, 13, 14 합친게 있는데 그 합친거 값이 얼마야? 밑에 제약식이에요. 1이지. 그럼 그 얘기는 뭐냐? 저 숫자를 그냥 14, 5, 8, 7을 9, 0, 3, 2 바꾸고 그 다음에 더하기 5 해주면 된다는 얘기야.

문제를 새로 풀고 거기다가 총 비용은 5만 더해주면 된다. 오케이? 네. 아직도 모르겠어도 상관없어요. 자, 행위에서 최소가 빼고 스텝 1B. 열에서도 최소가수를 빼는데 1열, 2열, 3열은 다 0이 있으니까 할 거 없고 4열만...

0이 없으니까 최소값 2를 빼준다 이거야. 이걸 빼준다 이거지. 이렇게 여기 써줘야 돼. 그래서 이렇게 해야 되는 거죠. 그러면서 얘가 이제 0이 됐지. 이제 자 그럼 이것만 갖고서 솔루션을 구할 수 있나? 아니요. 이 부분이 이제 이렇게 됐는데.

여기서 1:1 대응이 나와요 안 나와요? 안 나와요. 0은 지금 5개가 있어. 잘하면 나올 수도 있어. 왜 안 나와? 그 J1에 두 개가 있었어. 일단 하나만, 어떤 행위에 하나만 있으면 반드시 그걸 해야지. 얘 같은 경우는.

이것을 반드시 해야 하는 것. 여기서 이것 밖에 없으면 이것을 반드시 해야 하고. 여기도 이것 밖에 없으면 반드시 해야 하고. 여기서 겹치잖아요. 이것과 이것은 안 겹치죠. 이것은 이 세 개가 두 개가 되는데, 이것은 이 세 개가 하나 밖에 안 나와요. 어떻게 해야 해요? 이것을 더 만들어야 해요. 이것은 이것이 복잡해져요.

일단 현재 상태에서 지만이 아니라 제 어떤 알고심도 마찬가지인데 알고리는 어떤 이틀에서 하지 말아야 되겠냐 그만해도 되느냐 판단하는 게 이제 아 그 스탑핑룰이라고 하고 여기서는 기말이 테스트합니다. 최적계를 얻었느냐 최적계가 나왔느냐 안 나왔느냐를 판정하는 건데

아 뭐 여러가지 방법이 있는데 그냥 아 좀 전에 우리가 봤던 것처럼 어 영의 하나만 있는 행위를 열 가지고서 일단 할당하고 그 할당이 되는지 보는거고 1대 대행이 되는지 보는거고 좀 전에 보니깐 안된다는거죠 또 다른 방법은 최소한의 직선을 사용해서 0 0 0이 있는걸 다 치고 0을

행위들 열을 만들어서 지우는데 이때 반드시 여기 지금 4급하기 3 문제는 반드시 4개를 써야 된다 그래야 0을 다칠 수 있다 그러면 거기 짝짓게 나오는 거야 근데 4개를 안 쓰고도 0을 다칠 수 있다 그러면 0이 모자란다 이 상태에서 3개만 거둬 직선 3개 로 0이 다 지워지죠 그렇기 때문에 0이 모자란다 이 반드시

4개의 복사에 집안 영원가 커서 할 수 있지만 그런 것과 작용을 만들 필요 없어. 1:1 잡지. 자 그럼 이 상황에서 3개가 극구속 고도영이 나죠. 아직 0이 모지란 추가로 0을 더 만들어야 돼 어떻게 만드냐. 똑같이 형조장 12장 하는 거예요. 근데 아까보다는 좀 더 신경을 써서 해야 돼. 여기서 뭐 약간 해석은 달라질 수 있지만 원래 똑같아요. 역을 더 만들려면 어떻게 만들겠어요

직선으로 커버되지 않은 숫자들을 잘 보면 1, 4, 10, 2, 4, 6이 있어요 얘네들을 0으로 만들어야 돼요 얘네 중에서 0이 나와야 되는 거야 가장 작은 게 1이죠? 그러면 이걸 0으로 만드는 방법은 일단 두 가지가 있어 여기서 1을 빼주든지 여기서 1을 빼주든지

여기서 1을 빼주면 이게 마이너스가 되고 여기서 1을 빼주면 얘가 마이너스가 되죠? 그러면 얘가 마이너스 된다. 그러면 얘가 여기서 1을 쫙 빼줬는데 얘가 마이너스 된다. 여기는 1을 더 해주든지 해야 돼. 여기서 1 빼고 다시 1 더하고 원상복귀가 되잖아. 제자리잖아. 그러니까 그렇게 하면 안 되고 여기서 1을 쫙 빼서 마이너스 1, 9, 3, 0 되면 0이 하나 만들어서 오케이. 오케이. 그 다음에 얘 마이너스 1은 다시 복구를 해줘야 되니까 여기다가 1을 더해. 이걸 더해줘야 되지. 난 방법복귀가 되니까 제자리이고.

무슨말인지 알겠죠? 네 그럼 어떻게 돼? 여기서 1 빼서 -1 됐다가 이거 1 더해주면 10때도 상관없지 네 이거 5때도 상관없지 0 제자리에 돌아오니까 오케이 이거 1 되는데 이거는 뭐 없어도 상관없어 어? 무슨말인지 알겠죠?

4 아이온 여기서 이걸 여기서 1을 빼고 그럼 5 3 0 -1 되는데 이 행에다 더해줘도 돼 뭐 방법 하여튼 행단 위로 숫자를 빼주거나 10단 위로 숫자를 빼서 더해 그러니까 빼거나 더하면 그렇게 해서 0을 자꾸 만드는 거야 지금 한 거예요

여기서 1 빼고 그 다음에 여기서 1 빼 밑에서도 그럼 얘도 마이너스, 얘도 마이너스 됐죠 다 숫자 줄어들어, 시키실 수 다 줄었지 그 다음에 여기다 1 더 해 그러면 0,0 그대로 있는 상태에서 얘가 0,1 더 생겼잖아 그럼 이제 3개 갖고서 3개로 다 0을 놓치고 0이 몇 개야? 하나, 다음 수가에 놓으면

으 으 여기는 지금 여기다가 2행에서 -1 그 다음에 이 역당 승강의는 2행 -1 4행도 -1 그 다음 슬라이드에서 어떻게 되느냐 1년에

더하기 1 오케이? 행이나 열 단위로 더하거나 빼는 거예요 그렇게 하면 솔루션이 안 바뀌는 거예요 그래서 나온 숫자가 나온 게 이 모양이야 지금 자 그래서 0 있고 0 0 0 0 이렇게 있는 거예요 지금 왼쪽을

응? M1, J2에도 하나 더. 0이 지금 5개, 이거 솔루션 얻을 수 있어요? 하나 더 있어요. M1, J2. 아, 여기 오케이. 쏘리 쏘리. 6개. 여기 솔루션 나와 이제. 0이 하나만 있는 데부터 먼저 선택해야 돼. 다른 방법이 없으니까. 하나만 있는 데가 어디야? 얘 하나밖에 없죠. 얘 반드시 해야 되지.

그 다음에 또 하나만 있는거 예 반드시 해야 되지 그 나머지 두개 갖고 이런식으로 되잖아 그러니까 일단 m3 j3 먼저 하고 그 다음에 m4 j1 다음에 하고 그 다음에 나머지가 하고 이제 m2는 j4 그 다음에 m1은

제2 이렇게 자 그래서 나온게 이거 이거 이렇게 그렇게 하고 이제 원래 문제로 돌아가서 토탈 코스트가 얼마인지 계산 토탈 코스를 계산하는 원래 문제로 돌아가서 해도 좋고 그동안 뺀 거를 쭉 기록을 해도 돼요

그동안 뺀 거를 쭉 더 해도 원래 문제를 돌아오면

원래 문제로 돌아와서 지금 솔로셜 보기 때문에 지금 솔로셜인데 원래 문제로 돌아와서 비용 계산하면 2, 3, 5 5 총 비용? 10

이렇게 계산하면 된다 이 말이야 15가 된다 이 말이지 그런데 이 15를 어떻게 계산할 수 있는 거 아니 스텝 1에서 여기서 얼마를 뺐어요? -5 -2

-3 -2 얼마야 이게? 12 12의 토탈 스텝 1A에서 12를 차감했고 1B에서 얼마 차감? 2 부적

14 14가 되는거고 그 다음에 여기서 1로 넘어갈 때 1, 1 두 번 차감했고 1 더했죠? 결국 1 차감한 세분이야 그 부적은 -2+1에서

15차감. 그래서 15가 되는 겁니다. 비용이. 마지막 표에서는 다 더해서 총 비용은 0이지. 하지만 여기에 총 비용은 0인데 여기에다가 그동안 누적한 거 차감.

1 5 란 말이야 그래서 총 2 5 시원해 예는 0 이지만 누적 차감이 10원 말이지 좀 배우시고 자 시험에는 운영을 있다 나올 수 있지만 그 보다는 제 여기 왜 이게 비용을 차감에도 달라지지 않은지 좀 설명하는 거예요 지금

-끝내요. -끝내요.

11부터 14 더하기 뭐라고 해요? 이게 1이다 이거야.

되겠습니까? 네.

앞에 똑같은 문제에요. 똑같은 문제인데 취소와 관리가 취재야. 여기서 큰 문제는 진짜 재미있는거죠. 이익을 최대한 비용이 아니라 이익이다 이거야. 그러면은 이렇게 할당하는게 이렇게 할당하는거보다

더 좋은 거지. 숫자의 합이 커지게. 네. 뭐 하려고 하는지 알겠죠? 그럼 이 문제 어떻게 풀 거야? 최대값을 빼서 각 행의 최대값을 빼서 음수로 만든 다음에 각 행의 최대값을 빼서 음수로 만든 다음에

결국 최대값 총 이익이 0이 되게 하면

두가지 방법이 있어요. 두가지 방법이 있는데 자 일단 최소화 문제를 비유를 하면 이런거에요. 최소화 문제는 이게 어떤 솔루션인데 이게 목적함수값 총비용 총비용이 0이 아니고 이렇게 된단 말이지. 이렇게.

0보다 커 총비용이 이걸 어떻게 끌어내려서 총비용이 0이 되게 총비용이 0이 되게 하면서 이 솔루션을 결정한단 말이야 그리고 원래 문제로 돌아가서 다시 비용 재계산 했잖아 그러면 최대한 문제는 어떻게 돼?

최대 문제는 이걸 찾는 거란 말이에요. 이제는 최대한 이걸 찾아야 되는 거야. 이걸 찾으면 어떻게 되냐. 두 가지 접근 방법이 있어요. 우리 학생의 말한 대로 끄집어 내려갔고 그래갖고 최대가 0이 되게. 이런 식으로 방법을

이거를 알고 싶은데 전부다 끌어내려는 여기로 내려 보내고 싶은 거야 일단 다 왕창 내려오고 있기 일단 이만큼 내린 다음에 다시 이거를 울리는 거지 이 방법을 하는 겁니다 이렇게 이걸 한번에 일단 여기서 한번 여기서 이렇게 바로 오면 좋은데 그게 쉬지 않기 때문에 일단 확 내린 다음에 그 다음에 여기서 일루가는 건 뭐예요?

홍가림배 썼다고 비슷하잖아. 아래에 뒤집으면. 이게 지금 1, 2, 3, 4인데 2에서 4로 가는 거는 4로 가는 거는

수정에서 뚫는다 이거야. 같은 방식이야. 근데, 이거 뭐 같다 이거 유사한 방식이지. 다음 시간에 자세한 거 하고. 근데 두 번째는 이거예요. 여기다가 곱하기 마이너스를 해. 대칭, 대칭 이래서 이건 대칭이 너무.

이렇게 하는거고 여기는 대칭이 아니라 이래서 차감해서 평행이동한 다음에 끌어올리는 방법이 있고 대칭이동시킨 다음에

그 다음에 2~3은 끌어올리는거야. 그리고 3~4는 오리지날 헌가리암에서들. 끌어내리는거니까. 이거를 끌어내리는거니까. 자, 이 두가지 방법이 되서 다음시간에 살펴보도록 하고 이거는 기반것의 한 20절부터 될거입니다.