Hack your life

[선형대수] 선형계획법 Linear Programming 개론

선형계획법(linear programming 줄여서 LP라고도 한다.)은 한정된 자원(제한조건)을 효율적으로 할당하여 목적함수를 최대회하거나 최소화하는 문제를 다룬다.

선형계획법이 말은 어렵지만 중학교 수학에서도 나왔던 것으로 기억한다. 문제의 예를 들면, 어떤 회사가 계산기 A와 B 두 종류를 생산하는데, 생산하는데 각각 5시간과 2시간이 소요된다. 회사는 계산기를 생산하는데 1주일에 900시간을 사용할 수 있다. A와 B를 생산하는데 드는 비용은 각각 8만원, 10만원이며, 사용가능한 자금은 2800만원이다. 대 당 이익은 각각 3만원 2만원이다. 회사의 목표는 이익을 최대화 하는 것이다.

이러한 문제를 푸는 방법은 

1) 조건을 부등식으로 나타내고, 2) 제약조건을 그래프로 표현한 다음 3)가능한 영역에서 최적의 해를 찾는 것이다.

보통 부등식은 선형부등식이고 2개의 부등식 (x>0, y>0과 같은 기본 조건제외)로 이루어져있다.

이러한 부등식은 영역의 꼭짓점이나 모서리에서 최적해를 갖는다는 사실이 증명되어있다. *1)

꼭지점을 최적해로 갖는 경우엔 해가 1개이고 모서리의 모든 점을 최적해로 갖는 경우엔 많은 해를 가진다.

함수의 최소값

목적함수의 최소값을 결정하는 문제는 가능영역에서 -f, 즉 f의 음의 최대값을 구함으로써 풀 수 있다.

이러한 방법은 가능영역(부등식을 만족하는 영역)이 볼록(convex)한 모양인 경우이다.

볼록한 모양이라는 것은 영역을 이루는 형태가 안으로 들어가는 부분이 없다는 뜻이고, 영역 내에 빈공간이 없다는 뜻이다.

*1) 목적함수의 최대값이 한 꼭지점이나 모서리에 생기는 이유?

가능영역이 있고 목적함수가 있을 때, 목적함수 직선의 y절편을 어떻게 조절하느냐에 따라서 직선이 가능영역의 안 밖으로 평행하게 움직이게 된다.

그 중 값이 최대가 되려면 자연스럽게 목적함수 직선이 가능영역에 걸치는 형태가 되어야 한다.

가능한 경우는 아래 그림과 같이 꼭지점 또는 모서리 2가지 경우가 있다.

선형계획 문제를 해결하기 위해 소개된 위의 그래프 방법에는 한계가 있다. 세 개 이상의 변수를 포함하는 경우에 대해 기하학적 접근은 비현실적이기 때문에 많은 변수를 가진 문제애 대해서는 대수적인 방법인 심플렉스 방법(simplex method)를 사용한다.

Simplex method는 쉽게 컴퓨터 프로그램화 할 수 있는 장점도 있다.  최적해는 심플렉스 알고리즘이라 불리는 알고리즘에서 기본 행 연산들을 사용하여 열에 영을 만든다. 심플렉스 알고리즘에서도 축들을 선택하여 열의 원소들에 영을 만드는데 사용하지만, 가우스-요르단 소거와는 다른 기준을 적용한다.

심플렉스 알고리즘

1. 선형방정식계의 첨가행렬을 구성한다. 이것을 초기 심플렉스 표(inital simpex tableau)라고 한다.

2. 마지막 행에서 마지막 원소 이외의 크기가 가장 큰 음의 원소를 찾는다(만일 둘 혹은 그 이상의 원소가 이 성질을 갖는다면 이들 중 어떤 것을 선택해도 상관없다). 만일 그런 원소들이 모두 음이 아니라면 그 표는 최종 형태이다.

3. 이 음의 원소가 들어 있는 열의 각 원소에 대해, 원소가 양이면 이 원소로 마지막 열의 대응하는 원소를 나눈다.

4. 3에서 나눈 결과가 가장 작은 행을 선택한다. 이 행과 2에서 선택된 열에 해당하는 원소를 축 원소(pivot element)라고 한다. 

5. 행연산을 사용하여 축 위치에 1을 하나 만들고, 축 열의 다른 원소들은 모두 0으로 만든다.

6. 마지막 행에서 음의 원소들이 모두 없어질 때까지 단계 2-5를 반복한다. 최종 행렬을 최종 심플렉스 표(final simplex tableau)라고 하며, 이 표로부터 최적해를 얻을 수 있다.

예제

다음의 제약조건 하에서 의 최대값을 구하자.

첫 번째 부등식을 만족하는 각각의 x, y 에 대해서 다음을 만족하는 음이 아닌 변수 u의 값이 존재할 것이다. 마찬가지로 두번째 부등식도 아래와 같이 표현할 수 있다. 이러한 u와 v를 원래 변수들의 느슨한 부분을 메워준다고 해서 여유변수(slack variable)라고 한다.

그리고 목적함수는 다음과 같은 형태로 쓰여진다.

이제 원래 문제는 다음 선형방정식계에서 f가 가능한 큰 값이 되도록 해를 결정하는 문제가 되었다.

심플렉스 알고리즘을 적용해보면, 우선 900/5 < 2800/8 이므로 1행이 축이된다.(1행의 x계수 5를 1로 만들것이다.)

최종 심플렉스표가 만들어졌다. 마지막 행에서 음의 원소들은 모두 제거되었고, 이 표는 다음의 선형방정식계에 대응된다.

u와 v가 양수이므로, 마지막 방정식에서 u, v = 0 일 때 f가 최대값 700을 갖는다. u, v의 값 0 을 위의 식에 대입하면 x=100, y=200을 얻는다. 이 결과는 기하학을 사용하여 얻은 결과와 일치한다.

도움이 되셨으면 공감 한번  눌러주세요^^

[선형대수] 가우스-요르단 소거법

행렬을 사용하여 선형방정식계를 풀 때 가우스-요르단 방법을 사용한다.

그전에 몇 가지 용어 설명!

계수행렬과 첨가행렬

아래의 선형방정식계를 변수의 계수들로 구성되는 계수행렬과 계수와 우변의 상수를 함께 포함하는 첨가행렬로 나타낼 수 있다.

  (계수행렬)         (첨가행렬)

기본변환(Elemetary transformations)를 통해 선형방정식계를 다른 선형방정식계로 바꿀 수 있다.

이 변환은 행렬의 기본 행연산(elemetary row operation)을 이용하는게 편하다. 컴퓨터에서도 선형방정식계가 행렬로 입력되고 처리된다.

기본 행연산

1. 두 행을 교환한다.

2. 한 행에 영이 아닌 상수를 곱한다.

3. 한 행의 원소들의 상수배를 다른 행의 해당 원소들에 더한다.

이렇게 기본 행연산을 통해 만들어진 행렬을 행동등 행렬(row equivalent matrices)라고 부른다. 

기호 를 사용하여 동등관계를 나타낸다.

그러면 방정식계를 풀어보자.

이 식을 행렬로 만들면, 

그리고 기본 행연산을 이용해서 행렬을 조작한다.

여기서 계속 진행하기 위해서는 (2, 2) 위치에 0이 아닌 원소가 필요하다. 이를 위해 2행과 3행을 교환한다.

첨가행렬은 계수행렬 A와 상수항 B의 열로 구성된다. 이 행렬을 [A : B]로 쓴다.

행연산을 사용하여 첨가행렬을 한 열씩 ;단위행렬 과 같은 형태로 만들수 있다.

이 마지막 행렬 를 원래 첨가행렬의 기약 사다리형(reduced echelon form)이라고 부른다.

만약 [A : B]가 기약 사다리형으로 변환될 수 없으면 방정식계는 유일한 해를 갖지 않는다.

기약사다리형의 조건

1. 모든 원소가 영인 행은 모두 행렬의 바닥에 모여있다.

2. 그 외의 각 행에서 영이 아닌 첫 원소는 1이다. 이 원소를 선도 1이라고 부른다.

3. 첫 행 이후의 각 행에서 선도 1은 윗 행의 선도 1의 오른쪽에 위치한다.

4. 선도 1을 포함하는 열의 다른 원소는 모두 0이다.

많은 해를 갖는 경우?!

아래의 기약 사다리형의 경우

여기서 x3에 임의의 값 r을 넣으면 계의 일반해를 얻을 수 있다.

매개변수 r은 실수 집합이기 때문에 많은 해를 갖는다. r에 특정한 값을 넣어주면 특정한 해들이 얻어진다.

도움이 되셨으면 공감 한번  눌러주세요^^

[python] pip install - urlopen error [SSL: CERTIFICATE_VERIFY_FAILED]

When I installed egenix-mx-base package, urlopen error occurred like below.

I managed to find out the solution. It is not to upgrade pip...

You can see the download url in the picture. It starts with https://~, but you should modify this url to http://

So, "pip install http://downloads.egenix.com/python/egenix-mx-base-3.2.9-py2.7-win32-prebuilt.zip"

Then the package will be installed! 

[Tensorflow] 텐서플로우 자료형

텐서플로우에서는 일반적으로 파이썬에서 하듯이 x = 3 이렇게 변수를 정의하면 안된다.

텐서플로우의 자료형

상수형(Constant)

import tensorflow as tf

a = tf.constant([3], dtype=tf.float32)

b = tf.constant([5], dtype=tf.float32)

이런 식으로 tf.~로 정의하는데 짜증나는건 dtype도 float32가 아니라 tf.float32이다.

a의 타입을 찍어보면

print type(a)

>> <class 'tensorflow.python.framework.ops.Tensor'>

[Python] Virtualenv 가상환경 구성하기

virtualenv를 사용하는 이유는 라이브러리가 꼬이는걸 막고 각 프로젝트별로 개발환경을 분리시키기 위함입니다.

예를 들어, 새 프로젝트에는 구버전 라이브러리를 사용해야 하는 경우 패키지를 지웠다가 설치할 필요 없이 venv를 사용합니다.

1. pip install virtualenv 로 설치

2. 프로젝트를 만들  폴더를 만듭니다.

3. 해당 폴더로 이동하여 virtualenv venv를 치면 venv 폴더가 생깁니다.

4. 가상 환경을 activate 합니다.

   cd Scripts - activate

그러면 위의 사진과 같이 (venv)가 활성화 됩니다.

이 상태에서 라이브러리를 설치하면 패키지가 가상환경에만 설치됩니다.

비활성화 하는 방법은 deactivate 입니다.

[Docker] 윈도우 10에 Docker 설치 후 Tensorflow 환경 만들기(1)

VMware의 리눅스에 도커를 설치할지 윈도우에 설치할지 고민하다가 윈도우에 설치를 하기로 했다.

Docker란 가상 머신을 어플리케이션처럼 돌릴 수 있는 환경을 말한다.

Tensorflow를 실행하기 위한 방법으로 널리 사용되며, 이미지만 탑재해서 돌리면 개발환경이 만들어지기 때문에 개발환경 구축이 매우 간편하다.

1. 우선 도커 툴박스를 다운받는다. 

     https://www.docker.com/products/docker-toolbox

2. 설치를 쭉 하고 Docker Quickstart Terminal을 실행한다.

3. 처음에 자동으로 디폴트 가상머신이 만들어진다. 새로운 도커 가상머신을 만들려면 터미널에 아래와 같이 입력한다.

  $  docker-machine create vdocker -d virtualbox     

약간의 시간이 걸린다.

docker-machine --help라고 치면 도움말을 볼 수있다.

4.  $docker-machine ls라고 치면 만들어진 도커 가상머신을 볼 수 있다.

5. $docker-machine start vdocker를 입력하여 가상머신을 실행시킨다.

    그리고 $ docker run -it -p 8888:8888 --name tensorflow gcr.io/tensorflow/tensorflow:latest-devel

   를 입력해서 텐서플로우 이미지를 받는다.

   --name으로 이미지의 이름을 지을 수 있다.

이미지 다운로드가 완료되면 자동으로 접속된다.

exit를 치면 다시 컨테이너 밖으로 나올 수 있다.

6. $ docker ps -a 를 입력하면 컨테이너 목록을 볼 수 있다.

7. 조금전에 exit를 했기때문에 Status가 exit일 것이다.

   그래서 docker restart tensorflow(컨테이너 아이디 or 이름)을 하면 접속이 가능한 상태가 된다.

8. 접속하기

   $ docker exec -it tensorflow /bin/bash

[Django] Error: Import by filename is not supported

Django 프로젝트 생성 시 Importlib 에서 

Import by filename is not supported 이런 에러가 떴었다.

인터넷을 싹싹 뒤져도 해결을 못했다.

virenv를 만들어도 안됐었다. Django를 재설치해도 안됐었다. 기존에 만들어둔 프로젝트의 runserver도 같은 에러가 발생했다.

환경변수 - 시스템 변수에 DJANGO_SETTINGS_MODULE를 삭제 했더니 정상적으로 실행이 됐다.

아마 settings.py의 경로가 잘못 잡혔던것 같다.(내가 한거 아님)

문제를 해결해 버려서 스크린샷이 없다..ㅠ

[Python GUI PyQt4 vs WxPython]

Python으로 GUI Application을 만드는데에는 몇 가지 선택지가 있다.

Mobile이면 Kivy도 좋은 선택지라고 생각한다. 

Kivy는 터치가 가능한 어플리케이션을 만들기 좋고 멀티터치도 가능하다.

반면, Desktop Application을 만들거라면 PyQt4와 WxPython으로 좁혀진다.

둘 다 멋진 라이브러리이고, 만들고자하는 것의 대부분을 만족 시킬 수 있을 것이다.

나는 PyQt4를 먼저 사용해보고 WxPython으로 넘어간 케이스이다.

PyQt 이하 Qt를 사용하며 느낀점은, UI Component를 배치하는 방식이 쉽다. 복잡하고 정교하게도 가능하다. 

self.layout = QtGui.QGridLayout()
self.label_currentDB = QtGui.QLabel("Current Database : ")
self.label_currentDB.setFixedWidth(130)
self.label_newDB = QtGui.QLabel("New Database : ")
self.label_newDB.setFixedWidth(130)
self.Edit_currentDB = QtGui.QLineEdit()
self.Edit_currentDB.setFixedWidth(130)
self.Edit_currentDB.setText(ChangeDB.currentDB)
self.Edit_newDB = QtGui.QLineEdit()
self.Edit_newDB.setFixedWidth(130)
self.button_change = QtGui.QPushButton("Change")
self.button_change.clicked.connect(self.changeDB)
self.Edit_newDB.returnPressed.connect(self.changeDB)
self.button_cancel = QtGui.QPushButton("Cancel")
self.button_cancel.clicked.connect(self.close)
self.myQMenuBar = QtGui.QMenuBar(self)
self.layout.addWidget(self.label_currentDB, 0, 0, 1, 1)
self.layout.addWidget(self.label_newDB, 1, 0, 1, 1)
self.layout.addWidget(self.Edit_currentDB, 0, 1, 1, 1)
self.layout.addWidget(self.Edit_newDB, 1, 1, 1, 1)
self.layout.addWidget(self.button_change, 4, 0, 1, 1)
self.layout.addWidget(self.button_cancel, 4, 1, 1, 1)
self.setLayout(self.layout)

Wx는 느낌이 아래와 같이 Boxsizer라는 것을 사용해서 배치를 한다.
Qt도 레이아웃이라는 개념을 사용해서 레이아웃 안에 레이아웃과 같이 배치를 정교하게 할 수 있다. 
vbox = wx.BoxSizer(wx.VERTICAL)
box = wx.StaticBox(panel, -1, 'Change DB')
bsizer = wx.StaticBoxSizer(box, wx.VERTICAL)
nmbox = wx.BoxSizer(wx.HORIZONTAL)
fn = wx.StaticText(panel, -1, "Input IP :")
nmbox.Add(fn, 0, wx.ALL | wx.CENTER, 5)
self.nm1 = wx.TextCtrl(panel, -1, style=wx.ALIGN_LEFT)
nmbox.Add(self.nm1, 0, wx.ALL | wx.CENTER, 5)
bsizer.Add(nmbox, 0, wx.ALL | wx.CENTER, 10)
hbox = wx.BoxSizer(wx.HORIZONTAL)
okButton = wx.Button(panel, -1, 'Change')
hbox.Add(okButton, 0, wx.ALL | wx.LEFT, 10)
cancelButton = wx.Button(panel, -1, 'Cancel')
hbox.Add(cancelButton, 0, wx.ALL | wx.LEFT, 10)
vbox.Add(bsizer, 0, wx.ALL | wx.CENTER, 5)
vbox.Add(hbox, 0, wx.ALL | wx.CENTER, 5)
panel.SetSizer(vbox)
self.Centre()
panel.Fit()
self.Show()
okButton.Bind(wx.EVT_BUTTON, self.OnOk)
cancelButton.Bind(wx.EVT_BUTTON, self.OnCancel)

사용해본 바로는 내가 구현하고 싶은 방법으로 구현하는 데에는 Wx가 낫다고 평가하고 싶다.
Staticbox와 같은 컴포넌트나, 몇 가지 세부적인 UI 컴포넌트가 좀더 있었다.
그리고 dialog창에서 OK를 눌렀을 때 parent에서 어떻게 동작하는지 정하기도 그렇고,
Wx를 좀 더 깊게 파서 그런지 몰라도 나는 Wx가 더 풍부하게 활용 가능하다고 생각한다.

처음에 Qt를 사용할지 Wx를 사용할지 고민 많이하다가 둘다 사용해 본 바로는 Wx에 손을 들어주고 싶다.

[Python Windows Services] 파이썬으로 윈도우 서비스 만들기(2) 에러 해결

Error 1053 :  서비스가 시작이나 제어 요청에 빠르게 응답하지 않았습니다. 

서비스 파일을 작성한 후 서비스를 시작하려고 아래와 같이 커맨드를 입력하면 나타나는 에러가 있다.

이 에러를 해결하려고 정말 검색을 많이 했는데 해결방법은 생각보다 간단하다.

고급시스템 설정 - 환경변수 - 시스템 변수 - PATH에 다음과 같은 경로를 추가한다.

C:\Python27\Lib\site-packages\pywin32_system32

실제로 저런 경로가 없다면(패키지가 설치되어있지 않으면), pywin32를 설치해야한다. (pywin32-221.win-amd64-py2.7)

간혹 순서에 따라 에러가 해결되지 않는 경우가 있으므로, 맨 위로 올려준다.

Boolean Algebra의 제2 분배법칙

정보처리기사 시나공 책에는 해설이 되어있지않고 "이해하지 말고 그냥 외우세요."라고 되어있다.

이해가 잘 안되어 조금 더 생각해보았다.

A + BC = (A+B)(A+C)

일반적인 대수식에서는 성립되지 않는다.

하지만 참거짓의 값만 있는 Boolean Algebra에서는 성립한다.

우변을 분배법칙으로 풀면

= AA + AC + AB + BC , 여기서 AB=BA이다. 그리고 AA = A 이므로

= A(1 + C + B) + BC, 1+ C + B  = 1이므로

= A + BC