Last active
December 14, 2015 11:20
-
-
Save khalman-m/7e467055341b8e816537 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Симплекс-метод для решения задачи линейного программирования\n", | |
| "\n", | |
| "### Хальман Михаил. 2015" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**Симплекс метод**\n", | |
| "\n", | |
| "Один из самых первых методов оптимизации для задач линейного программирования.\n", | |
| "\n", | |
| "Любую задачу ЛП можно представить в *стандартной форме*:\n", | |
| "\n", | |
| "$$\\min \\; c^T x$$\n", | |
| "$$\\text{s.t.} \\quad Ax = b$$\n", | |
| "$$\\quad \\; \\; x \\geq 0$$\n", | |
| "\n", | |
| "Такое представление осуществляется с помощью добавления в каждое неравенство $a^Tx \\leq b$ slack-переменной:\n", | |
| "$$a^Tx + \\xi = b,$$\n", | |
| "$$\\xi \\geq 0.$$\n", | |
| "\n", | |
| "Для любой задачи линейного программирования возможны три случая:\n", | |
| "1. Не существует ни одной *допустимой* точки: $P = \\{Ax = b, x \\geq 0\\} \\; = \\; \\emptyset$;\n", | |
| "2. Задача неограничена: $\\inf_{x \\in P}c^T x \\; = \\; -\\infty$;\n", | |
| "3. Существует решение задачи $x^*$, доставляющее оптимум.\n", | |
| "\n", | |
| "Центральным фактом, используемом в сиплекс методе, является следующее **утверждение**:\n", | |
| "Пусть ЛП задача в стандартной форме ограничена. $x \\in P$ - произвольная допустимая точка. Тогда существует **вершина** $x^{'}$ множества $P$ такая, что $c^Tx^{'} \\leq c^T x$.\n", | |
| "\n", | |
| "Таким образом, если оптимум достигается в некоторой точке, то он по необходимости достигается в некоторой вершине **полиэдра** $P$.\n", | |
| "\n", | |
| "Симплекс метод в общем виде, начинает с некоторой выршины множества $P$, и на каждом шаге пытается перейти в соседнюю вершину, такую, значение функционала в которой не возрастает.\n", | |
| "\n", | |
| "Уточнений требует процедура выбора начальной точки, а также процедура перехода в соседнюю вершину.\n", | |
| "\n", | |
| "Удобным для вычислений является следующий **критерий угловых точек**:\n", | |
| "$$x \\in P - \\text{вершина} \\quad \\Leftrightarrow \\quad A_x \\; \\text{имеет линейно независимые столбцы},$$\n", | |
| "где $A_x$ - матрица, полученная вычёркиванием столбоцов матрицы $A$ с такими индексами $j$, для которых $x_j = 0$.\n", | |
| "\n", | |
| "Дополним столбцы $A_x$ до базиса, получим невырожденную квадратную матрицу $A_B$. Выразим *базисные* компоненты вектора *x* через остальные-*небазисные*:\n", | |
| "$$x_B \\; = \\; A_B^{-1}b \\, - \\, A_B^{-1}A_N x_N \\; \\geq \\; 0,$$\n", | |
| "значение целевого функционала:\n", | |
| "$$c^T x \\; = \\; c_BA_B^{-1}b \\, + \\, (c_N - c_B A_B^{-1} A_N) x_N.$$\n", | |
| "\n", | |
| "В угловой точке, по построению, $x_N = 0$, но теперь мы можем попробовать увеличить значение некоторой координаты в $x_N$, чтобы уменьшит значение целевого функционала. Единственное ограничение, которое у нас есть: $X_B \\geq 0$.\n", | |
| "\n", | |
| "Поэтому будем увеличивать некоторую координату $x_N$ до тех пор, пока все координаты $x_B$ будут неотрицательными. После этого, новую ненулевую координату из $x_N$ сделаем базисной, обменяв с некоторой нулевой координатой из $x_B$.\n", | |
| "\n", | |
| "Конкретная реализация симплекс метода зависит от того, как именно будет выбираться координаты. \n", | |
| "\n", | |
| "**Метод Блэнда:** выбирать всегда координаты с наименьшим номером. Для него доказано, что такой симплекс-метод никогда не зациклится, и найдёт минимум за конечное число шагов.\n", | |
| "\n", | |
| "**Выбор начальной точки:** запустившись из некоторой угловой точки, симплекс-метод всегда сможет решить задачу за конечное число шагов. Но, выбор начальной точки не совсем элементарная задача.\n", | |
| "\n", | |
| "Для этого, на так называемой *первой фазе* симплекс метода, решают вспомогательную линейную программу:\n", | |
| "\n", | |
| "$$\\min \\; \\xi $$\n", | |
| "$$\\text{s.t.} \\quad Ax - \\xi = b$$\n", | |
| "$$\\quad \\; \\; x \\geq 0$$\n", | |
| "$$\\quad \\; \\; \\xi \\geq 0$$\n", | |
| "\n", | |
| "Для неё легко указать допустимую угловую точку: $(\\xi_0, 0, 0, \\dots, 0)$, где $\\xi_0$ - минимальное число, чтобы все неравенства выполнялись.\n", | |
| "\n", | |
| "Решив вспомогательную ЛП задачу на первом шаге, если $\\xi < 0$, то исходная задача несовместна. Иначе мы получим допустимую угловую точку для второй нормальной фазы алгоритма.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 5, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import numpy as np\n", | |
| "from scipy.optimize import linprog" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def klee_minty(n):\n", | |
| " \"\"\"\n", | |
| " Generates an instance of Klee-Minty problem of dimension n\n", | |
| " in a form of\n", | |
| " \n", | |
| " max c^T x\n", | |
| " s.t. A x <= b\n", | |
| " \n", | |
| " Returns c, A, b\n", | |
| " \"\"\"\n", | |
| " c = -(10 ** np.arange(n))[::-1]\n", | |
| " A = np.zeros((2*n, n))\n", | |
| " b = np.zeros(2*n)\n", | |
| " \n", | |
| " for i in range(n):\n", | |
| " for j in range(i):\n", | |
| " A[i, j] = 2 * 10 ** (i-j)\n", | |
| " A[i, i] = 1\n", | |
| " b[i] = 100 ** i\n", | |
| " np.fill_diagonal(A[n:,:], -1)\n", | |
| " return c, A, b" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 28, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "c, A, b = klee_minty(n=n)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 45, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "table = dict(success=[], fun=[], nit=[], n=[])\n", | |
| "for n in range(2, 18):\n", | |
| " c, A, b = klee_minty(n=n)\n", | |
| " result = linprog(c, A_ub=A, b_ub=b, options={'maxiter': 50000})\n", | |
| " table['n'].append(n)\n", | |
| " table['success'].append(result.success)\n", | |
| " table['fun'].append(result.fun)\n", | |
| " table['nit'].append(result.nit)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 46, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import pandas as pd" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 49, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "df = pd.DataFrame.from_dict(table)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 54, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/html": [ | |
| "<div>\n", | |
| "<table border=\"1\" class=\"dataframe\">\n", | |
| " <thead>\n", | |
| " <tr style=\"text-align: right;\">\n", | |
| " <th></th>\n", | |
| " <th>n</th>\n", | |
| " <th>success</th>\n", | |
| " <th>nit</th>\n", | |
| " <th>fun</th>\n", | |
| " </tr>\n", | |
| " </thead>\n", | |
| " <tbody>\n", | |
| " <tr>\n", | |
| " <th>0</th>\n", | |
| " <td>2</td>\n", | |
| " <td>True</td>\n", | |
| " <td>3</td>\n", | |
| " <td>-1.000000e+02</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>1</th>\n", | |
| " <td>3</td>\n", | |
| " <td>True</td>\n", | |
| " <td>7</td>\n", | |
| " <td>-1.000000e+04</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>2</th>\n", | |
| " <td>4</td>\n", | |
| " <td>True</td>\n", | |
| " <td>15</td>\n", | |
| " <td>-1.000000e+06</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>3</th>\n", | |
| " <td>5</td>\n", | |
| " <td>True</td>\n", | |
| " <td>31</td>\n", | |
| " <td>-1.000000e+08</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>4</th>\n", | |
| " <td>6</td>\n", | |
| " <td>True</td>\n", | |
| " <td>63</td>\n", | |
| " <td>-1.000000e+10</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>5</th>\n", | |
| " <td>7</td>\n", | |
| " <td>True</td>\n", | |
| " <td>127</td>\n", | |
| " <td>-1.000000e+12</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>6</th>\n", | |
| " <td>8</td>\n", | |
| " <td>True</td>\n", | |
| " <td>255</td>\n", | |
| " <td>-1.000000e+14</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>7</th>\n", | |
| " <td>9</td>\n", | |
| " <td>True</td>\n", | |
| " <td>511</td>\n", | |
| " <td>-1.000000e+16</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>8</th>\n", | |
| " <td>10</td>\n", | |
| " <td>True</td>\n", | |
| " <td>1023</td>\n", | |
| " <td>-1.000000e+18</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>9</th>\n", | |
| " <td>11</td>\n", | |
| " <td>True</td>\n", | |
| " <td>2047</td>\n", | |
| " <td>-1.000000e+20</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>10</th>\n", | |
| " <td>12</td>\n", | |
| " <td>True</td>\n", | |
| " <td>4095</td>\n", | |
| " <td>-1.000000e+22</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>11</th>\n", | |
| " <td>13</td>\n", | |
| " <td>True</td>\n", | |
| " <td>8191</td>\n", | |
| " <td>-1.000000e+24</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>12</th>\n", | |
| " <td>14</td>\n", | |
| " <td>True</td>\n", | |
| " <td>16383</td>\n", | |
| " <td>-1.000000e+26</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>13</th>\n", | |
| " <td>15</td>\n", | |
| " <td>True</td>\n", | |
| " <td>32767</td>\n", | |
| " <td>-1.000000e+28</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>14</th>\n", | |
| " <td>16</td>\n", | |
| " <td>False</td>\n", | |
| " <td>50000</td>\n", | |
| " <td>-9.900010e+29</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>15</th>\n", | |
| " <td>17</td>\n", | |
| " <td>False</td>\n", | |
| " <td>50000</td>\n", | |
| " <td>-9.900010e+30</td>\n", | |
| " </tr>\n", | |
| " </tbody>\n", | |
| "</table>\n", | |
| "</div>" | |
| ], | |
| "text/plain": [ | |
| " n success nit fun\n", | |
| "0 2 True 3 -1.000000e+02\n", | |
| "1 3 True 7 -1.000000e+04\n", | |
| "2 4 True 15 -1.000000e+06\n", | |
| "3 5 True 31 -1.000000e+08\n", | |
| "4 6 True 63 -1.000000e+10\n", | |
| "5 7 True 127 -1.000000e+12\n", | |
| "6 8 True 255 -1.000000e+14\n", | |
| "7 9 True 511 -1.000000e+16\n", | |
| "8 10 True 1023 -1.000000e+18\n", | |
| "9 11 True 2047 -1.000000e+20\n", | |
| "10 12 True 4095 -1.000000e+22\n", | |
| "11 13 True 8191 -1.000000e+24\n", | |
| "12 14 True 16383 -1.000000e+26\n", | |
| "13 15 True 32767 -1.000000e+28\n", | |
| "14 16 False 50000 -9.900010e+29\n", | |
| "15 17 False 50000 -9.900010e+30" | |
| ] | |
| }, | |
| "execution_count": 54, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "df[['n', 'success', 'nit', 'fun']]" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 81, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import time\n", | |
| "n = 10\n", | |
| "c, A, b = klee_minty(n=n)\n", | |
| "f_star = -10 ** (2 *(n - 1))\n", | |
| "\n", | |
| "new_table = dict(f_val=[], x=[], time=[])\n", | |
| "\n", | |
| "start_time = time.time()\n", | |
| "def callback_fun(x, **kwargs):\n", | |
| " f = c.dot(x)\n", | |
| " new_table['f_val'].append(f)\n", | |
| " new_table['x'].append(x)\n", | |
| " new_table['time'].append(time.time() - start_time)\n", | |
| "\n", | |
| "result = linprog(c, A_ub=A, b_ub=b, options={'maxiter': 50000}, callback=callback_fun)\n", | |
| "new_table['f_val'] = np.array(new_table['f_val'])" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 73, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| " status: 0\n", | |
| " slack: array([ 1.00000000e+00, 1.00000000e+02, 1.00000000e+04,\n", | |
| " 1.00000000e+06, 1.00000000e+08, 1.00000000e+10,\n", | |
| " 1.00000000e+12, 1.00000000e+14, 1.00000000e+16,\n", | |
| " 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 0.00000000e+00, 1.00000000e+18])\n", | |
| " success: True\n", | |
| " fun: -1e+18\n", | |
| " x: array([ 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,\n", | |
| " 1.00000000e+18])\n", | |
| " message: 'Optimization terminated successfully.'\n", | |
| " nit: 1023" | |
| ] | |
| }, | |
| "execution_count": 73, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "result" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 83, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Populating the interactive namespace from numpy and matplotlib\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "[<matplotlib.lines.Line2D at 0x1084ae910>]" | |
| ] | |
| }, | |
| "execution_count": 83, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| }, | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEACAYAAAC57G0KAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAExdJREFUeJzt3X2QXXV9x/H3NwkYECFiBhJJnMQKQoUSBXzEdnGgpD4g\njh1E5anC6B8dpXZ8AMq4sZ1RwRLAMjJjQScySssAo4nISApZnzpFKwlGQghUaEVJokBQRCQP3/5x\nzybLctm9u3vPvXd/9/2aObPnnHvuvb/vsnz48jvn3BuZiSSpPDO6PQBJUj0MeEkqlAEvSYUy4CWp\nUAa8JBXKgJekQrUU8BExMyLWRsSqantZRDxc7VsbEUvrHaYkaaJmtXjc+cAG4EXVdgLLM3N5LaOS\nJE3ZuB18RCwA3gpcA8Tw7hHrkqQe1MoUzeXAx4FdI/Yl8OGIuDsiro2IObWMTpI0aWMGfES8Hdia\nmWt5dsd+NbAYWAI8AlxW2wglSZMSY30WTUR8BjgT2AHMBvYHbsrMs0YcswhYlZlHNXm+H3QjSZOQ\nmVOeBh+zg8/MizJzYWYuBk4H7sjMsyJi/ojD3gWsH+M1il0GBwe7PgZrsz7rK29pl1avooHGFM3w\nO18aEUdX2w8CH2rbiCRJbdFywGfmEDBUrZ9Z03gkSW3inaxTMDAw0O0h1Kbk2sD6prvS62uXMU+y\nTvnFI7LO15ekEkUEWfdJVknS9GXAS1KhDHhJKpQBL0mFMuAlqVAGvCQVyoCXpEIZ8JJUKANekgpl\nwEtSoQx4SSqUAS9JhTLgJalQBrwkFcqAl6RCGfCSVCgDXpIKZcBLUqEMeEkqlAEvSYUy4CWpUAa8\nJBXKgJekQhnwklSoWd0egKSJefxxeOaZxnrmnv0TXZ/q83vx/SLgyCPRsMysbaHxu3/uMjiYTQ0O\nerzH55Ytmd/7XuZD5zQ//sGzB3PNmty93HFHY/n5Wc2P/58zB3P16szVqzNvu23P8sAZzY+///2D\neeutmd/+9p7lllsyN72v+fH3vXcwV63KXLlyz/LNb2ZuPL358fe+ZzBvvjl3Lzfd1Fg2nNb8+J/9\n9WDecEPmDTdkLl+eue++mQcdlHnpvs2P//wLB3PevMz585+9/PN+zY+/7EWDuWBB5oIFmQsX7lmW\n79/8+MsPGMxFizIXLcpcvHjPcsWc5sdf+eLBfMUrcvdy6KGN5QsHNj/+X14ymIcfnruXI45oLFfN\n3XP8VXMH81Wvyt3LkUc2lmOPbf6nN900onnqGRyN16pHRGSdr68yffCDsGYNzJu3Z1/Ec9eb7Wtl\nfbLP65XXOPdcWLoUFSwiyMwY/8ixOUWjnvPHP8LFF8PZZ3d7JNL05klW9ZwdO2CWrYc0ZQa8es6O\nHTBzZrdHIU1/Brx6zs6ddvBSOxjw6jlO0UjtYcCr5zhFI7WHAa+e4xSN1B4tBXxEzIyItRGxqto+\nMCJWR8SmiLgtIubUO0z1E6dopPZotYM/H9gADN+1dAGwOjMPA26vtqW22LnTKRqpHcYN+IhYALwV\nuAYYvrPqFGBFtb4COLWW0akv2cFL7dFKB3858HFg14h9B2fmlmp9C3Bwuwem/mXAS+0x5r9GEfF2\nYGtmro2IgWbHZGZGxPN+4MyyZct2rw8MDDAw0PRlpN2colG/GRoaYmhoqO2vO+aHjUXEZ4AzgR3A\nbGB/4GbgOGAgMzdHxHxgTWYe3uT5ftiYJuyYY+BLX2r8lPpRuz5sbMwpmsy8KDMXZuZi4HTgjsw8\nE1gJDH8U1NnAN6Y6EGmYUzRSe0z0OvjhdvxzwEkRsQl4S7UttYVTNFJ7tNwnZeZ3ge9W648BJ9Y1\nKPU3O3ipPbyTVT3HgJfaw4BXz3GKRmoP+yTxyCNw1VWNzhn2fDlmu9dbPXbrVjt4qR3816gLdu6E\n886Dbdsa282CbqwQbPdjmzc3von+jW9s7It49veG1r0+et+JJ8Ihh7T++5TUnF+63QVPPglz58L1\n1ze2JxuQUw3YkdvHHQd77VVPvZImpl3XwRvwXbBtGyxatKeDl6SROnKjk+rhSURJnWDAd4GXAUrq\nBAO+C/xKOkmdYMB3gV9JJ6kTDPgucIpGUicY8F3gSVZJnWDAd4EdvKROMOC7wJOskjrBgO8CT7JK\n6gQDvgucopHUCQZ8F3iSVVInGPBdYAcvqRMM+C7wJKukTjDgu8CTrJI6wYDvAqdoJHWCAd8FnmSV\n1An2kW0y8mvxdu167vrIfU88YQcvqX59EzNPPgm/+U3z0B0rkEf/PO88uO++5z5v2IwZe74Ob+T6\n6O2zzure70JSf+ibgH/3u+Huu2GffZqHcKs/jz8efvKT5qEtSb2kbwL+97+HG29sBLQk9YO+Ocnq\niU1J/aZvAt5LEyX1GwNekgrVNwHvFI2kftM3AW8HL6nfGPCSVKi+CXinaCT1m74JeDt4Sf3GgJek\nQo0b8BExOyLujIh1EbEhIj5b7V8WEQ9HxNpqWVr/cCfPKRpJ/WbcnjYzn46IEzLzqYiYBfwgIo4H\nEliemctrH2Ub2MFL6jctTdFk5lPV6t7ATODxanvafMSWAS+p37QU8BExIyLWAVuANZl5T/XQhyPi\n7oi4NiLm1DbKNnCKRlK/abWD35WZS4AFwJ9HxABwNbAYWAI8AlxW1yDbwQ5eUr+ZUORl5hMRcQtw\nbGYODe+PiGuAVc2es2zZst3rAwMDDAwMTGacU2bAS+pVQ0NDDA0Ntf11I0d+HVGzAyLmAjsyc1tE\n7AN8B/g0cE9mbq6O+ShwXGa+b9Rzc7zX75QZMxohP6NvLgyVNF1FBJk55XOcrfS084EVETGDxpTO\ndZl5e0R8NSKW0Lia5kHgQ1MdTF127Wr8NNwl9ZNWLpNcD7ymyf6e+VbRu+6CH/6wEeQ7dz735/bt\nnmCV1H96flZ69WpYufLZgT16uf12eNvbYP/9G136zJmNZeT6lVd2uxJJ6qxx5+Cn9OJtmIM/91x4\n6il405v2hPXoZe5cOOkkv/haUhk6OQffVTt3wsknwznndHskkjS99PxpRy9vlKTJMeAlqVA9H/B+\nxIAkTU7PB7wdvCRNjgEvSYXq+YB3ikaSJqfnA94OXpImx4CXpEL1fMA7RSNJk9PzAW8HL0mTMy0C\n3g5ekiau5wN+5047eEmajJ4PeKdoJGlypkXAO0UjSRPX8wHvFI0kTU7PB7xTNJI0OdMi4J2ikaSJ\n62pvnNkI8GeeaSyPPgqnnw5btza+KHv7dnjiCdhvv26OUpKmp6528JdeCrNnw0EHwctf3vje1Te8\nAb7/fbjrLti4EbZtazwuSZqYrnbwv/41XHIJfOxj3RyFJJWpqx28J1AlqT5dD3hPoEpSPboa8F7j\nLkn16XoHb8BLUj26HvBO0UhSPZyikaRC2cFLUqG6HvB28JJUD6doJKlQXe/gnaKRpHp0PeDt4CWp\nHl2forGDl6R62MFLUqHGDPiImB0Rd0bEuojYEBGfrfYfGBGrI2JTRNwWEXMm8+YGvCTVZ8yAz8yn\ngRMycwnwZ8AJEXE8cAGwOjMPA26vtifMKRpJqs+4UzSZ+VS1ujcwE3gcOAVYUe1fAZw6mTe3g5ek\n+owb8BExIyLWAVuANZl5D3BwZm6pDtkCHDyZN/cySUmqz7j9c2buApZExAHAdyLihFGPZ0TkRN50\n0yZYt67xjU528JJUj5bjNTOfiIhbgGOALRExLzM3R8R8YOvzPW/ZsmW71596aoB99x3g6qsb3796\n4omN72KVpH42NDTE0NBQ2183Mp+/+Y6IucCOzNwWEfsA3wE+DZwMPJqZl0TEBcCczHzOidaIyOHX\n37WrMR3zqU/BoYfCGWe0vRZJKkJEkJkx5dcZJ+CPonESdUa1XJeZn4+IA4EbgJcBDwGnZea2Js/f\nHfDbt8M++zTm3SVJz68jAT/lFx8R8H/4A7z4xfD007W9nSQVoV0B37E7Wb3mXZI6q2MB7zXvktRZ\nHe3gDXhJ6pyOdvBO0UhS5zhFI0mF8iSrJBXKDl6SCuVJVkkqlCdZJalQTtFIUqGcopGkQjlFI0mF\nsoOXpEI5By9JhXKKRpIK5RSNJBWqIwH/2GNw8cUwe3Yn3k2SBB0I+E2b4LDDYNEiWLGi7neTJA2r\nfdJk82Z45Svha1+DmPIXUEmSWlV7B79jB+y9t+EuSZ1We8B7clWSuqMjHbwBL0md15EO3uvfJanz\n7OAlqVAdCXg7eEnqPE+ySlKhnKKRpEI5RSNJhXKKRpIKZQcvSYWyg5ekQnmSVZIK5RSNJBXKKRpJ\nKpQdvCQVyg5ekgo1bsBHxMKIWBMR90TEzyLiI9X+ZRHxcESsrZalzZ7/+OMGvCR1Q2Tm2AdEzAPm\nZea6iNgP+AlwKnAa8LvMXD7Gc/MlL0m+8hV4xzvaOWxJKldEkJlT/h68cXvrzNwMbK7Wn4yIe4FD\nhscx3vMXLDDcJakbJjQHHxGLgFcD/1Xt+nBE3B0R10bEnGbPOeqoKY1PkjRJLc+OV9MzNwLnV538\n1cA/Vg//E3AZcO7o561fv4xlyxrrAwMDDAwMTG3EklSYoaEhhoaG2v66487BA0TEXsC3gFsz84om\njy8CVmXmUaP257nnJtdc057BSlI/aNccfCtX0QRwLbBhZLhHxPwRh70LWN/s+V5BI0nd0Ur8vgk4\nA/hpRKyt9l0EvDcilgAJPAh8qOkbGPCS1BWtXEXzA5p3+re28gbexSpJ3VH7nax28JLUHbUHvB28\nJHWHHbwkFcqAl6RCOUUjSYWyg5ekQhnwklQop2gkqVB28JJUKDt4SSqUHbwkFcqAl6RCGfCSVKja\nA/7oo+t+B0lSM7UH/IIFdb+DJKkZp2gkqVBeJilJhbKDl6RC2cFLUqHs4CWpUHbwklSo2gM+ou53\nkCQ1U3vAS5K6w4CXpEIZ8JJUKANekgplwEtSoQx4SSqUAS9JhTLgJalQBrwkFcqAl6RCGfCSVCgD\nXpIKZcBLUqHGDfiIWBgRayLinoj4WUR8pNp/YESsjohNEXFbRMypf7iSpFa10sFvBz6ama8CXg/8\nbUQcAVwArM7Mw4Dbq+2+MjQ01O0h1Kbk2sD6prvS62uXcQM+Mzdn5rpq/UngXuAQ4BRgRXXYCuDU\nugbZq0r+Iyu5NrC+6a70+tplQnPwEbEIeDVwJ3BwZm6pHtoCHNzWkUmSpqTlgI+I/YCbgPMz83cj\nH8vMBLLNY5MkTUE0snmcgyL2Ar4F3JqZV1T7NgIDmbk5IuYDazLz8FHPM/QlaRIyc8pfeDprvAMi\nIoBrgQ3D4V5ZCZwNXFL9/EYdA5QkTc64HXxEHA98D/gpe6ZhLgR+BNwAvAx4CDgtM7fVNlJJ0oS0\nNEUjSZp+armTNSKWRsTGiLg/Ij5Zx3vUbTI3eEXEhVXNGyPiL7s3+tZExMyIWBsRq6rtkmqbExE3\nRsS9EbEhIl5XWH0XVn+b6yPi6xHxgulcX0R8OSK2RMT6EfsmXE9EHFP9Tu6PiCs7XcfzeZ76Pl/9\nfd4dETdHxAEjHmtPfZnZ1gWYCTwALAL2AtYBR7T7fepegHnAkmp9P+A+4AjgUuAT1f5PAp+r1v+0\nqnWvqvYHgBndrmOcGv8e+BqwstouqbYVwAeq9VnAAaXUV43x58ALqu1/p3EebNrWB7yZxiXY60fs\nm0g9w7MRPwJeW61/G1ja7drGqO+k4X8OwOfqqK+ODv61wAOZ+VBmbgf+DXhnDe9Tq5z4DV7vBK7P\nzO2Z+RCNfyiv7eigJyAiFgBvBa4Bhk+Gl1LbAcCbM/PLAJm5IzOfoJD6gN/SuMN834iYBewL/Ipp\nXF9mfh94fNTuidTzuupqvhdl5o+q475Kj9yA2ay+zFydmbuqzTuBBdV62+qrI+APAX4xYvvhat+0\n1eINXi+lUeuwXq/7cuDjwK4R+0qpbTHw64j4SkTcFRH/GhEvpJD6MvMx4DLg/2gE+7bMXE0h9Y0w\n0XpG7/8l06NOgA/Q6MihjfXVEfBFnbWd4g1ePfm7iIi3A1szcy17uvdnma61VWYBrwG+mJmvAX7P\nqM9Kms71RcSfAH9H43/fXwrsFxFnjDxmOtfXTAv1TFsR8Q/AM5n59Xa/dh0B/0tg4YjthTz7vzrT\nRnWD103AdZk5fJ3/loiYVz0+H9ha7R9d94JqXy96I3BKRDwIXA+8JSKuo4zaoPH39nBm/rjavpFG\n4G8upL5jgf/MzEczcwdwM/AGyqlv2ET+Hh+u9i8Ytb+n64yIc2hMlb5/xO621VdHwP83cGhELIqI\nvYH30Lgpalpp4QYvePYNXiuB0yNi74hYDBxK44RIz8nMizJzYWYuBk4H7sjMMymgNmicPwF+ERGH\nVbtOBO4BVlFAfcBG4PURsU/1d3oisIFy6hs2ob/H6p/7b6srpgI4kyY3YPaKiFhKY5r0nZn59IiH\n2ldfTWeM/4rGVScPABd2+wz2JGs4nsb89DpgbbUsBQ4E/gPYBNwGzBnxnIuqmjcCJ3e7hhbr/Av2\nXEVTTG3A0cCPgbtpdLgHFFbfJ2j8R2s9jROQe03n+mj8n+SvgGdonMP7m8nUAxxT/U4eAL7Q7brG\nqO8DwP3A/47Ily+2uz5vdJKkQvmVfZJUKANekgplwEtSoQx4SSqUAS9JhTLgJalQBrwkFcqAl6RC\n/T/Kuof9sLFGrQAAAABJRU5ErkJggg==\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x10848c890>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "%pylab inline\n", | |
| "\n", | |
| "plot(np.log(-new_table['f_val']))\n", | |
| "plot([0, 1000], [np.log(-f_star)] * 2, 'r--')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 84, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "[<matplotlib.lines.Line2D at 0x10931a590>]" | |
| ] | |
| }, | |
| "execution_count": 84, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| }, | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEACAYAAACj0I2EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAE+hJREFUeJzt3X2wXHV9x/H3Nw8QIJAQIwFCkAeNiCLIk7RYZ7FlRFQM\nWihFAavjYKcio1ZFp9Mb21qqLZHaB6Yjsab+UcZJNAYhhYBZLRXxKSASGMQhDKhEEYVAEshNvv1j\n93Iv4ebu2bt3n86+XzNn9pyzvz3nu5vNJ7/8zjl7IjORJPW/ad0uQJI0NQx0SSoJA12SSsJAl6SS\nMNAlqSQMdEkqiUKBHhHTI2JDRFxfX14aEY/U122IiLPaW6YkqZEZBdtdDmwE9q8vJ7AsM5e1pSpJ\nUtMa9tAj4jDgbOBaIEZWj5mXJPWAIkMunwM+Cuwasy6ByyLirohYHhFz21KdJKmwCQM9It4C/Coz\nN/D8Hvk1wJHACcAvgavaVqEkqZCY6LdcIuLvgYuAYWAWcACwKjMvHtPmCOD6zDxunNf7QzGSNAmZ\n2fSw9oQ99Mz8ZGYuyswjgQuAb2bmxRFxyJhm5wJ3T7CNvp2Ghoa6XsMg1m793Z+sv7vTZBU9ywVq\nQy4je/psRBxfX34QuHTSFUiSpkThQM/MKlCtz1/UpnokSZPklaITqFQq3S5h0vq5drD+brP+/jTh\nQdGWNx6R7dy+JJVRRJBTfVBUktQ/DHRJKgkDXZJKwkCXpJIw0CWpJAx0SSoJA12SSsJAl6SSMNAl\nqSQMdEkqCQNdkkrCQJekkjDQJakkDHRJKgkDXZJKwkCXpJIw0CWpJAx0SSoJA12SSsJAl6SSMNAl\nqSQMdEkqCQNdkkrCQJekkpjR7QIkTZ2nnoKnn67NZ46u77f5qdrevvvC0UczODKzbRO1z/aF09BQ\njmtoyPa2n/L2m949lN/6Vma1WpvWr69ND14yfvufXTSUt9ySuW7d6HTzzZkPvGv89j9951CuXZu5\ndm3mjTfWphtuyLz/wvHb33fBUK5Zk7lmTebXv16bVq/OvPdPxm+/8fyhXLUqc9WqzJUrR6d7zhu/\n/Wf3HcqDDso86KDMBQtGp3/cb/z2/zR7KA89NPPQQzMXLhydrtp//PbLDhjKww/PPPzwzJe8ZHT6\n3Jzx2189dyiPOirzqKMyjz56dPrnA8dv//l5Q7l4cebixZkvf/no9C8vGr/9v84fymOPzXzlK0en\nV70q899ePJSrjtvDd6XH1aK5+cyN2mvbIyKynduX9uTII2H+fJg1q7YcMfrcyPzuj1O9rhvbPflk\n+PjHUZ+LCDIzGrd8PodcVErPPAOrV8PChd2uROocD4qqlHbuhOnTu12F1FkGukrJQNcgMtBVSga6\nBpGBrlIy0DWIDHSVkoGuQWSgq5QMdA2iQoEeEdMjYkNEXF9fnhcR6yLi/oi4OSLmtrdMqTkGugZR\n0R765cBGYOQqoSuAdZm5GLi1viz1DANdg6hhoEfEYcDZwLXAyJVL5wAr6vMrgCVtqU6ahJFrwqc5\noKgBU+Qr/zngo8CuMesWZObm+vxmYMFUFyZN1q5dtTCPpi+clvrbhJf+R8RbgF9l5oaIqIzXJjMz\nIvb4gy1Lly59br5SqVCpjLsZaco43KJ+U61WqVarLW9nwh/nioi/By4ChoFZwAHAV4FTgEpmPhoR\nhwDrM/OYcV7vj3Op47Ztg3nzao9SP5rsj3NNOOSSmZ/MzEWZeSRwAfDNzLwIWANcUm92CbC62R1L\n7WIPXYOq2cNGI93tfwDOjIj7gTfUl6WeYKBrUPl76Cqdxx+Hl7609ij1o7YMuUj9yB66BpWBrtIx\n0DWovGORptwTT8CyZbB9e2157A0gJ1qeqrZbtxroGkwGep+78kr4/vcbh96e5ifzmkbzjz8OBx0E\nZ59dWxcxOk20PFVtAd7znuY/S6nfeVC0zx1/PFxySe2myBOF3njzzbRtdv7442G//ab+/UqDwJtE\nD6idO+HMM+G447pdiaRu86BonxsedrxYUo2B3ud27oQZ/j9LEgZ63/MUPUkjDPQ+NzxsD11SjYHe\n5+yhSxphoPc5D4pKGmGg9zkPikoaYaD3OYdcJI0w0PucQy6SRhjofc4hF0kjDPQ+55CLpBEGep9z\nyEXSCAO9j2XCrl0GuqQaA72P7dpV+6naaf4pSsJA72sOt0gay0DvY57hImks46BHjYyPT/T45JP2\n0CWNMtBbtHMnPPJILWTHC949zY883nYbfOITL3wORsfHxz7uvu7oo7v7/iX1DgO9RV/8Inz4wzB/\n/mjIjg3cPc2PPE6fDrfcAqed9sLglqRmGOgteuwx+MAH4Moru12JpEHnQdEWPfkkHHBAt6uQJAO9\nZU8+Cfvv3+0qJMlAb9mWLfbQJfUGA71FDrlI6hUGeosccpHUKwz0FjnkIqlXGOgtcshFUq8w0Fvk\nkIukXmGgt8ghF0m9omGgR8SsiLgjIu6MiI0RcWV9/dKIeCQiNtSns9pfbm/ZuRO2bYP99ut2JZJU\n4NL/zNweEWdk5taImAHcFhGvAxJYlpnL2l5lj9qyBWbP9ndXJPWGQkMumbm1PrsXMB34bX15oKPM\nA6KSekmhQI+IaRFxJ7AZWJ+Z99Sfuiwi7oqI5RExt21V9ijHzyX1kqI99F2ZeQJwGPD6iKgA1wBH\nAicAvwSualeRvcozXCT1kqZ+Pjczn4iIG4CTM7M6sj4irgWuH+81S5cufW6+UqlQqVQmU2dPcshF\n0lSoVqtUq9WWtxM5cnucPTWImA8MZ+bvImIf4CbgU8A9mflovc2HgFMy88LdXpuNtt/PVq6E666r\nPUrSVIkIMrPpY5RFeuiHACsiYhq1IZovZ+atEfFfEXECtbNdHgQubXbn/c4hF0m9pMhpi3cDJ46z\n/uK2VNRDfv5z+NrXauebj0y7do3O3347vOxl3a5SkmoG4hZ0y5bBpk3j37R5ouW77oLDD4fFi2v3\n/tx9OuUUOOecbr87SappOIbe0sZ7ZAx93jz42MdqFwHtftPmiZZnzoS3vhX23rvb70DSIJnsGPpA\nBPoBB8DDD8OcOd2uRJIam2ygD8SPc+3cCTMGYnBJ0iAbiEAfHjbQJZWfgS5JJVH6QB85Y2Va6d+p\npEFX+pjbubN2iqE/cSup7Eof6A63SBoUBroklYSBLkklUfpAHxlDl6SyK32g20OXNCgMdEkqCQNd\nkkqi9IHuGLqkQVH6QLeHLmlQGOiSVBIGuiSVxEAEumPokgZBz/ZdM59/U+aR+33uvu6ZZ+Dd74YH\nH3z+DZxHpmefhZNO6va7kaT269lAP+88+OpXR2/IPG3a6OPY+enTYckSuPba8W/kPH067Ltvt9+N\nJLVfzwb65s1QrcLrX9/tSiSpP/TsGPqOHbDXXt2uQpL6R88G+rPPGuiS1AwDXZJKwkCXpJIw0CWp\nJAx0SSqJng30HTtg5sxuVyFJ/aNnA90euiQ1x0CXpJIw0CWpJHoy0HfurD36K4mSVFxPBrq9c0lq\nXs8Gume4SFJzJgz0iJgVEXdExJ0RsTEirqyvnxcR6yLi/oi4OSLmTmVR/jCXJDVvwkDPzO3AGZl5\nAvBq4IyIeB1wBbAuMxcDt9aXp4xDLpLUvIZDLpm5tT67FzAd+C1wDrCivn4FsGQqizLQJal5DQM9\nIqZFxJ3AZmB9Zt4DLMjMzfUmm4EFU1mUgS5JzWt4x6LM3AWcEBFzgJsi4ozdns+IyFYLue222l2K\nnn0WNm0y0CWpWYVvQZeZT0TEDcBJwOaIODgzH42IQ4Bf7el1S5cufW6+UqlQqVTYsQOuuQa2bKnd\n5PkXv4CbboJTT60F+V57wfve18K7kqQ+Uq1WqVarLW8nMvfcuY6I+cBwZv4uIvYBbgI+BbwR+E1m\nfiYirgDmZuYLDoxGRI63/fvug9NPh/e/H/beuzaddx4cdVTL70eS+l5EkJnR7Osa9dAPAVZExDRq\n4+1fzsxbI2ID8JWIeC+wCTi/mZ1u2waLFsGnP91suZKkPZkw0DPzbuDEcdY/DvzRZHe6fTvMmjXZ\nV0uSxtOVK0W3b4d99unGniWpvLoW6PbQJWlqGeiSVBJdCfRt2wx0SZpq9tAlqSQ8KCpJJWEPXZJK\nwkCXpJLwoKgklYQ9dEkqCQ+KSlJJ2EOXpJIw0CWpJAx0SSoJz3KRpJLwoKgklURHA/2hh+DMM+GO\nO2D27E7uWZLKr2OBftllcMwxcNJJ8J3vwGtf26k9S9JgaHRP0SmzcSOsXAlvfnOn9ihJg6VjPfQd\nOxxmkaR26migz5zZqb1J0uAx0CWpJDoW6MPDMKNjI/aSNHjsoUtSSRjoklQSBroklYSBLkkl4UFR\nSSoJe+iSVBIGuiSVhIEuSSXR0TF0A12S2qcjgZ7pQVFJareOBPrwMEyfDhGd2JskDaaOBLrj55LU\nfga6JJVEw0CPiEURsT4i7omIn0TEB+vrl0bEIxGxoT6dtadtbNlSC3VJUvtEZk7cIOJg4ODMvDMi\nZgM/BJYA5wNbMnPZBK/NbduSc8+tLa9dO1VlS1J5RQSZ2fRRx4bnnWTmo8Cj9fmnIuJeYOHIfhu9\n/nvfg9tvh4cearY0SVIzmhpDj4gjgNcA362vuiwi7oqI5RExd7zXPPMMnHwyzJnTUp2SpAYKnxle\nH25ZCVxe76lfA/xN/em/Ba4C3rv76770paVs2gRLl0KlUqFSqbRctCSVSbVapVqttrydhmPoABEx\nE/gGsDYzrx7n+SOA6zPzuN3W5+rVyfLlsGZNy7VK0kCY7Bh6kbNcAlgObBwb5hFxyJhm5wJ3j/d6\nT1mUpM4oMuRyOvAu4McRsaG+7pPAn0bECUACDwKXjvdiA12SOqPIWS63MX5PvtBJiP4olyR1Rtuv\nFLWHLkmdYaBLUkkY6JJUEga6JJWEgS5JJWGgS1JJGOiSVBIGuiSVhIEuSSVhoEtSSRjoklQSBrok\nlUTbA33rVgNdkjqh0A0uJr3xiDzwwORHP4IjjmjbbiSpVCZ7g4u2B/rs2cmWLW3bhSSVTtvuWNQq\nh1skqTMMdEkqibYH+owiN7mTJLXMHroklYQ9dEkqCXvoklQSBroklYRDLpJUEvbQJakkDHRJKgmH\nXCSpJOyhS1JJGOiSVBIOuUhSSdhDl6SSMNAlqSQccpGkkrCHLkkl0fZAP+ywdu9BkgQduKdoO7cv\nSWXUtnuKRsSiiFgfEfdExE8i4oP19fMiYl1E3B8RN0fE3MkULkmaGkWGXHYAH8rMVwKnAX8REa8A\nrgDWZeZi4Nb6cqlUq9VulzBp/Vw7WH+3WX9/ahjomfloZt5Zn38KuBdYCJwDrKg3WwEsaVeR3dLP\nX4p+rh2sv9usvz81dVA0Io4AXgPcASzIzM31pzYDC6a0MklSUwoHekTMBlYBl2fmlrHP1Y98evRT\nkrqo0FkuETET+AawNjOvrq+7D6hk5qMRcQiwPjOP2e11hrwkTcJkznJpeB1nRASwHNg4EuZ1a4BL\ngM/UH1dPRUGSpMlp2EOPiNcB3wZ+zOiwyieA7wFfAQ4HNgHnZ+bv2lapJGlCbb2wSJLUOS1f+h8R\nZ0XEfRHx04j4+B7afL7+/F0R8ZpW9zmVGtUfEcdExO0RsT0iPtKNGidSoP531j/3H0fE/0XEq7tR\n554UqP9t9fo3RMQPI+IN3ahzT4p8/+vtTomI4Yh4eyfra6TA51+JiCfqn/+GiPirbtQ5noLZU6nX\n/ZOIqHa4xAkV+Oz/csznfnf9+zPxBZyZOekJmA48ABwBzATuBF6xW5uzgRvr868FvtvKPqdyKlj/\ni4GTgb8DPtLtmidR/+8Bc+rzZ/Xh57/fmPnjgAe6XXcz9Y9p901qJxa8o9t1N/n5V4A13a51krXP\nBe4BDqsvz+923c1+d8a0fwtwS6PtttpDP7X+F2xTZu4ArgPetlub5y5Aysw7gLkR0SvnrDesPzN/\nnZk/oHbFbK8pUv/tmflEffEOoJd+Lq1I/U+PWZwNPNbB+hop8v0HuAxYCfy6k8UVULT+Xjy5oUjt\nFwKrMvMRgMzsx+/OiAuB/2600VYDfSHw8JjlR+rrGrXplVApUn8va7b+9wI3trWi5hSqPyKWRMS9\nwFrggx2qrYiG9UfEQmp/Ua+pr+qlg1ZFPv8Efr8+7HVjRBzbseomVqT2lwHz6r9F9YOIuKhj1TVW\n+O9uROwLvJHadUATavX2E0W/nLv/C98rX+peqWOyCtcfEWcA7wFOb185TStUf2auBlZHxB8AXwZe\n3taqiitS/9XAFZmZ9VOAe6m3W6T+HwGLMnNrRLyJ2unJi9tbViFFap8JnAj8IbAvcHtEfDczf9rW\nyoppJnveCtyWBc4ibDXQfw4sGrO8iNq/NBO1Oay+rhcUqb+XFaq/fiD0C8BZmfnbDtVWRFOff2b+\nb0TMiIgXZeZv2l5dY0XqPwm4rpblzAfeFBE7MnNNZ0qcUMP6c8xV4Zm5NiL+PSLmZebjHapxT4p8\n9g8Dj2XmNmBbRHwbOB7ohUBv5rt/AQWGW4CWD4rOAH5GbWB/LxofFD2N3joo17D+MW2X0nsHRYt8\n/odTO/hyWrfrnWT9RzN6eu2JwM+6Xfdkvj/19v8JvL3bdTf5+S8Y8/mfCmzqdt1N1H4McAu1A5D7\nAncDx3a79ma+O8Ac4DfAPkW221IPPTOHI+IDwE31D215Zt4bEZfWn/+PzLwxIs6OiAeAp4E/a2Wf\nU6lI/RFxMPB94ABgV0RcTu1L8VTXCq8rUj/w18CBwDX1XuKOzDy1WzWPVbD+dwAXR8QO4ClqvZWe\nULD+nlWw/j8G/jwihoGt9MjnXzB77ouI/6F2UeQu4AuZubF7VY9q4ruzBLgpa//LaMgLiySpJNp+\nT1FJUmcY6JJUEga6JJWEgS5JJWGgS1JJGOiSVBIGuiSVhIEuSSXx/0K7HD+fes/lAAAAAElFTkSu\nQmCC\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x10931a110>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plot(new_table['time'], np.log(-new_table['f_val']))\n", | |
| "plot([new_table['time'][0], new_table['time'][-1]], [np.log(-f_star)] * 2, 'r--')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [] | |
| } | |
| ], | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 2", | |
| "language": "python", | |
| "name": "python2" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 2 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython2", | |
| "version": "2.7.10" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 0 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Симплекс метод
Один из самых первых методов оптимизации для задач линейного программирования.
Любую задачу ЛП можно представить в стандартной форме:
Такое представление осуществляется с помощью добавления в каждое неравенство$a^Tx \leq b$ slack-переменной:
$$a^Tx + \xi = b,$$
$$\xi \geq 0.$$
Для любой задачи линейного программирования возможны три случая:
Центральным фактом, используемом в сиплекс методе, является следующее утверждение:$x \in P$ - произвольная допустимая точка. Тогда существует вершина $x^{'}$ множества $P$ такая, что $c^Tx^{'} \leq c^T x$ .
Пусть ЛП задача в стандартной форме ограничена.
Таким образом, если оптимум достигается в некоторой точке, то он по необходимости достигается в некоторой вершине полиэдра$P$ .
Симплекс метод в общем виде, начинает с некоторой выршины множества$P$ , и на каждом шаге пытается перейти в соседнюю вершину, такую, значение функционала в которой не возрастает.
Уточнений требует процедура выбора начальной точки, а также процедура перехода в соседнюю вершину.
Удобным для вычислений является следующий критерий угловых точек:
$$x \in P - \text{вершина} \quad \Leftrightarrow \quad A_x ; \text{имеет линейно независимые столбцы},$$ $A_x$ - матрица, полученная вычёркиванием столбоцов матрицы $A$ с такими индексами $j$ , для которых $x_j = 0$ .
где
Дополним столбцы$A_x$ до базиса, получим невырожденную квадратную матрицу $A_B$ . Выразим базисные компоненты вектора x через остальные-небазисные:
$$x_B ; = ; A_B^{-1}b , - , A_B^{-1}A_N x_N ; \geq ; 0,$$
$$c^T x ; = ; c_BA_B^{-1}b , + , (c_N - c_B A_B^{-1} A_N) x_N.$$
значение целевого функционала:
В угловой точке, по построению,$x_N = 0$ , но теперь мы можем попробовать увеличить значение некоторой координаты в $x_N$ , чтобы уменьшить значение целевого функционала. Единственное ограничение, которое у нас есть: $x_B \geq 0$ .
Поэтому будем увеличивать некоторую координату$x_N$ до тех пор, пока все координаты $x_B$ будут неотрицательными. После этого, новую ненулевую координату из $x_N$ сделаем базисной, обменяв с некоторой нулевой координатой из $x_B$ .
Конкретная реализация симплекс метода зависит от того, как именно будет выбираться координаты.
Метод Блэнда: выбирать всегда координаты с наименьшим номером. Для него доказано, что такой симплекс-метод никогда не зациклится, и найдёт минимум за конечное число шагов.
Выбор начальной точки: запустившись из некоторой угловой точки, симплекс-метод всегда сможет решить задачу за конечное число шагов. Но, выбор начальной точки не совсем элементарная задача.
Для этого, на так называемой первой фазе симплекс метода, решают вспомогательную линейную программу:
Для неё легко указать допустимую угловую точку:$(\xi_0, 0, 0, \dots, 0)$ , где $\xi_0$ - минимальное число, чтобы все неравенства выполнялись.
Решив вспомогательную ЛП задачу на первом шаге, если$\xi < 0$ , то исходная задача несовместна. Иначе мы получим допустимую угловую точку для второй нормальной фазы алгоритма.