建模算法/约束优化/gurobi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2c2a8fd4-3ad8-4699-a549-5f63eb5259ad",
   "metadata": {},
   "source": [
    "## gurobi求解2019-f范例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "49ebb30b-bf0a-4b41-8d72-5d0992723bc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import gurobipy as grb"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "438f1099-2cad-4eff-a5fa-b2f048163725",
   "metadata": {},
   "source": [
    "## 一、读取excel表2的数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cf11a730-2d38-4d91-b87b-a6ab057737c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "D:\\Anaconda3\\envs\\mathmodel\\lib\\site-packages\\openpyxl\\worksheet\\_reader.py:312: UserWarning: Unknown extension is not supported and will be removed\n",
      "  warn(msg)\n"
     ]
    }
   ],
   "source": [
    "\n",
    "df=pd.read_excel('题目/附件1：数据集1-终稿.xlsx', engine='openpyxl',skiprows=[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4a08ef1c-0c76-4520-85ef-56e468fb35b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构建所有点坐标，0为起点，shape-1为终点； 第二列为x坐标，第三列为y坐标，第四列为z坐标\n",
    "coordinates = df.values[:, 1:4]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0774498b-8897-4560-856a-6a249d5fb95c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.0, 50000.0, 5000.0],\n",
       "       [33070.825830821, 2789.48076085272, 5163.5246804925],\n",
       "       [54832.8870194109, 49179.2191080384, 1448.30379093285],\n",
       "       ...,\n",
       "       [14870.6016822319, 95939.1733623643, 8248.83618468285],\n",
       "       [93009.5674461602, 4549.3332597056, 7882.60829650082],\n",
       "       [100000.0, 59652.3433795158, 5022.00116448164]], dtype=object)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coordinates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7ece9813-f687-42b0-985f-adb1a65937f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构建校正向量，1表示垂直校正点，0表示水平校正点，2表示起点，3表示终点\n",
    "correction_vector = list(df.values[:, 4])\n",
    "correction_vector[0] = 2\n",
    "correction_vector[612] = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d4ebd6c2-17a1-416b-a12c-616d8d73739b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 0,\n",
       " 0,\n",
       " 1,\n",
       " 3]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correction_vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9017ce54-55ee-415c-8ca4-4b9fc2700170",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# 计算欧式距离，用矩阵A标记\n",
    "A = np.zeros((613, 613))\n",
    "for i in range(613):\n",
    "    for j in range(613):\n",
    "        A[i, j] = np.sqrt(\n",
    "            (coordinates[i, 0] - coordinates[j, 0]) ** 2 + (coordinates[i, 1] - coordinates[j, 1]) ** 2 + (\n",
    "                        coordinates[i, 2] - coordinates[j, 2]) ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "7d1f520a-f11c-4914-ae19-a8da40d50bf2",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "613"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "118edddf-d479-42ec-9443-285a800a72e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 第一题的基本常量\n",
    "shape=len(A)\n",
    "alpha1 = 25\n",
    "alpha2 = 15\n",
    "beta1 = 20\n",
    "beta2 = 25\n",
    "delta = 0.001\n",
    "theta = 30"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "77a86491-ed39-43af-9d5d-c057aa7762cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 将A转化成tupledict类型\n",
    "dict_A = {}\n",
    "for i in range(shape):\n",
    "    for j in range(shape):\n",
    "        dict_A[i, j] = A[i, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "928f4a03-3e4b-4750-b160-d1637ed1ea13",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): 0.0,\n",
       " (0, 1): 57641.47281500988,\n",
       " (0, 2): 54953.92366444448,\n",
       " (0, 3): 79240.62746162385,\n",
       " (0, 4): 38627.495328737336,\n",
       " (0, 5): 35755.398430861416,\n",
       " (0, 6): 25043.323671058613,\n",
       " (0, 7): 51047.28532187423,\n",
       " (0, 8): 97618.0893733903,\n",
       " (0, 9): 30364.35679560231,\n",
       " (0, 10): 59914.0577682999,\n",
       " (0, 11): 58967.29509964733,\n",
       " (0, 12): 83631.21744805193,\n",
       " (0, 13): 34392.16821863199,\n",
       " (0, 14): 88594.97589355292,\n",
       " (0, 15): 38669.21677606868,\n",
       " (0, 16): 93777.85197558186,\n",
       " (0, 17): 77070.4522714437,\n",
       " (0, 18): 97313.84011083808,\n",
       " (0, 19): 21346.13667077411,\n",
       " (0, 20): 96316.60924291782,\n",
       " (0, 21): 99830.53528146358,\n",
       " (0, 22): 58568.13032575283,\n",
       " (0, 23): 62942.89830298805,\n",
       " (0, 24): 59925.15788430486,\n",
       " (0, 25): 45637.38272180045,\n",
       " (0, 26): 33387.17454854625,\n",
       " (0, 27): 50312.317748396235,\n",
       " (0, 28): 34792.28293104262,\n",
       " (0, 29): 17821.378276879175,\n",
       " (0, 30): 73384.4012085318,\n",
       " (0, 31): 52920.28619150555,\n",
       " (0, 32): 56485.25473427393,\n",
       " (0, 33): 49365.29712988649,\n",
       " (0, 34): 76128.59440860369,\n",
       " (0, 35): 71033.27797111483,\n",
       " (0, 36): 49765.40013565414,\n",
       " (0, 37): 40963.55975558387,\n",
       " (0, 38): 66410.24799222771,\n",
       " (0, 39): 90295.00862205793,\n",
       " (0, 40): 9350.105206995011,\n",
       " (0, 41): 81801.61011375942,\n",
       " (0, 42): 38008.97316194154,\n",
       " (0, 43): 91928.1866951597,\n",
       " (0, 44): 75270.03555724549,\n",
       " (0, 45): 51955.82259443058,\n",
       " (0, 46): 91849.67904942963,\n",
       " (0, 47): 26094.16300011167,\n",
       " (0, 48): 79163.53757573129,\n",
       " (0, 49): 41227.626556219664,\n",
       " (0, 50): 29275.33325305919,\n",
       " (0, 51): 46533.24308119314,\n",
       " (0, 52): 67415.78505500498,\n",
       " (0, 53): 76723.55032098424,\n",
       " (0, 54): 96917.60920522925,\n",
       " (0, 55): 27543.251013082616,\n",
       " (0, 56): 43738.45757108722,\n",
       " (0, 57): 21585.474196301006,\n",
       " (0, 58): 59309.24758797844,\n",
       " (0, 59): 77444.33027675065,\n",
       " (0, 60): 70027.70094813393,\n",
       " (0, 61): 45654.17682811901,\n",
       " (0, 62): 59471.551163639015,\n",
       " (0, 63): 56982.79612115473,\n",
       " (0, 64): 20940.621393720885,\n",
       " (0, 65): 52663.28656949745,\n",
       " (0, 66): 31832.639773853738,\n",
       " (0, 67): 81162.02056602528,\n",
       " (0, 68): 20644.445102772304,\n",
       " (0, 69): 21928.1920197599,\n",
       " (0, 70): 46727.79805466385,\n",
       " (0, 71): 4907.3727182857265,\n",
       " (0, 72): 84923.5152268263,\n",
       " (0, 73): 40591.177734689285,\n",
       " (0, 74): 40311.27927268877,\n",
       " (0, 75): 39133.9495830085,\n",
       " (0, 76): 22566.32989511535,\n",
       " (0, 77): 16157.905378656042,\n",
       " (0, 78): 49768.932407531756,\n",
       " (0, 79): 13781.472993660305,\n",
       " (0, 80): 28815.316145044653,\n",
       " (0, 81): 42991.92772433395,\n",
       " (0, 82): 23523.031307354224,\n",
       " (0, 83): 87277.81532788105,\n",
       " (0, 84): 99633.02066548594,\n",
       " (0, 85): 98702.09203314692,\n",
       " (0, 86): 51776.42186067825,\n",
       " (0, 87): 55933.90186336919,\n",
       " (0, 88): 75802.16628519187,\n",
       " (0, 89): 50006.60573687633,\n",
       " (0, 90): 30502.98083900326,\n",
       " (0, 91): 29765.99980276422,\n",
       " (0, 92): 17523.84043150187,\n",
       " (0, 93): 83217.87352961184,\n",
       " (0, 94): 68528.29869547914,\n",
       " (0, 95): 56707.88731371892,\n",
       " (0, 96): 57759.44958174491,\n",
       " (0, 97): 55534.624335258355,\n",
       " (0, 98): 49479.157463930824,\n",
       " (0, 99): 62376.816868368696,\n",
       " (0, 100): 64291.83977999484,\n",
       " (0, 101): 77876.55198317056,\n",
       " (0, 102): 45674.10554030941,\n",
       " (0, 103): 51519.11786880379,\n",
       " (0, 104): 85157.50990396216,\n",
       " (0, 105): 99521.11852257735,\n",
       " (0, 106): 50408.10132051996,\n",
       " (0, 107): 49812.727983446726,\n",
       " (0, 108): 34126.4186583224,\n",
       " (0, 109): 83684.02313689493,\n",
       " (0, 110): 79501.99539890638,\n",
       " (0, 111): 47285.643080918206,\n",
       " (0, 112): 30797.313186316464,\n",
       " (0, 113): 71724.85765302891,\n",
       " (0, 114): 33015.41414852359,\n",
       " (0, 115): 96596.76005217475,\n",
       " (0, 116): 91070.12391527522,\n",
       " (0, 117): 62732.41859174739,\n",
       " (0, 118): 62068.88363765652,\n",
       " (0, 119): 65354.925992991,\n",
       " (0, 120): 49708.52572408992,\n",
       " (0, 121): 70187.02131039475,\n",
       " (0, 122): 65635.44645568042,\n",
       " (0, 123): 27593.11460214197,\n",
       " (0, 124): 38578.266525936575,\n",
       " (0, 125): 20755.458376506256,\n",
       " (0, 126): 52829.03624791141,\n",
       " (0, 127): 58348.66475475814,\n",
       " (0, 128): 36485.565967498835,\n",
       " (0, 129): 99863.61226389543,\n",
       " (0, 130): 67237.58740543811,\n",
       " (0, 131): 95155.56123627773,\n",
       " (0, 132): 76253.62967993422,\n",
       " (0, 133): 70820.17227825314,\n",
       " (0, 134): 77300.65592098421,\n",
       " (0, 135): 90126.23424426495,\n",
       " (0, 136): 25535.378403706098,\n",
       " (0, 137): 62409.0385498555,\n",
       " (0, 138): 45763.700516297504,\n",
       " (0, 139): 48453.98942105421,\n",
       " (0, 140): 102753.33861776983,\n",
       " (0, 141): 77313.04037586378,\n",
       " (0, 142): 52763.041309585,\n",
       " (0, 143): 40209.57057196847,\n",
       " (0, 144): 78165.22667833454,\n",
       " (0, 145): 13458.468405922393,\n",
       " (0, 146): 41894.240146039156,\n",
       " (0, 147): 61020.955963906425,\n",
       " (0, 148): 38717.90728970901,\n",
       " (0, 149): 79167.57047693715,\n",
       " (0, 150): 70312.00719738824,\n",
       " (0, 151): 34696.69866050382,\n",
       " (0, 152): 31746.25647613047,\n",
       " (0, 153): 65292.88475737779,\n",
       " (0, 154): 62846.18683563113,\n",
       " (0, 155): 43581.79578779458,\n",
       " (0, 156): 94267.40667194263,\n",
       " (0, 157): 62459.74116290002,\n",
       " (0, 158): 97326.63388827484,\n",
       " (0, 159): 33842.599862871524,\n",
       " (0, 160): 62838.30090600474,\n",
       " (0, 161): 87009.1999021254,\n",
       " (0, 162): 21533.733899341147,\n",
       " (0, 163): 25819.333601421222,\n",
       " (0, 164): 72175.8818954138,\n",
       " (0, 165): 28287.507226806534,\n",
       " (0, 166): 70186.15845037177,\n",
       " (0, 167): 35614.510207129904,\n",
       " (0, 168): 81127.24925612264,\n",
       " (0, 169): 46643.83658517382,\n",
       " (0, 170): 40308.34624224131,\n",
       " (0, 171): 48321.55281662215,\n",
       " (0, 172): 69289.09204742477,\n",
       " (0, 173): 66102.22848683638,\n",
       " (0, 174): 100433.66910407395,\n",
       " (0, 175): 69649.27412153462,\n",
       " (0, 176): 23509.484920415198,\n",
       " (0, 177): 47817.02466957146,\n",
       " (0, 178): 33291.43953497644,\n",
       " (0, 179): 100738.09349144403,\n",
       " (0, 180): 9250.892879088546,\n",
       " (0, 181): 82625.3159809475,\n",
       " (0, 182): 85996.83615753941,\n",
       " (0, 183): 45950.97243721725,\n",
       " (0, 184): 84244.42256203784,\n",
       " (0, 185): 85039.84646400595,\n",
       " (0, 186): 65768.59878923818,\n",
       " (0, 187): 92786.3825040774,\n",
       " (0, 188): 70035.37719476038,\n",
       " (0, 189): 73776.90249556483,\n",
       " (0, 190): 53564.12795224931,\n",
       " (0, 191): 63558.064759164736,\n",
       " (0, 192): 43118.98116586174,\n",
       " (0, 193): 50628.180076595825,\n",
       " (0, 194): 59347.20150895861,\n",
       " (0, 195): 87066.57106601798,\n",
       " (0, 196): 84173.96650596592,\n",
       " (0, 197): 99973.3463210432,\n",
       " (0, 198): 61762.255655707246,\n",
       " (0, 199): 24413.42569104809,\n",
       " (0, 200): 13945.290180255244,\n",
       " (0, 201): 71777.9279841117,\n",
       " (0, 202): 12140.566910769916,\n",
       " (0, 203): 56507.46322875275,\n",
       " (0, 204): 95096.3986130928,\n",
       " (0, 205): 11680.462779343317,\n",
       " (0, 206): 61422.17684431717,\n",
       " (0, 207): 58583.02977924283,\n",
       " (0, 208): 48472.76941819862,\n",
       " (0, 209): 61532.01399008185,\n",
       " (0, 210): 22085.666099549748,\n",
       " (0, 211): 14022.879982622346,\n",
       " (0, 212): 44748.73694429737,\n",
       " (0, 213): 70792.33597502188,\n",
       " (0, 214): 74653.78696862489,\n",
       " (0, 215): 35920.65811152273,\n",
       " (0, 216): 44453.233387585045,\n",
       " (0, 217): 28785.527252281998,\n",
       " (0, 218): 42951.22950490496,\n",
       " (0, 219): 105925.5750751489,\n",
       " (0, 220): 84458.49695709885,\n",
       " (0, 221): 57543.22261034604,\n",
       " (0, 222): 53551.73786051548,\n",
       " (0, 223): 39362.70378927854,\n",
       " (0, 224): 58730.7100306859,\n",
       " (0, 225): 77270.08610040373,\n",
       " (0, 226): 89703.84545706166,\n",
       " (0, 227): 71880.47966883083,\n",
       " (0, 228): 69249.00203173517,\n",
       " (0, 229): 97846.78535854437,\n",
       " (0, 230): 90631.39067021664,\n",
       " (0, 231): 31758.150563092906,\n",
       " (0, 232): 60554.0642603454,\n",
       " (0, 233): 44244.150427680375,\n",
       " (0, 234): 37075.23482911055,\n",
       " (0, 235): 43996.60350393077,\n",
       " (0, 236): 68600.52033368197,\n",
       " (0, 237): 33440.75781784354,\n",
       " (0, 238): 25264.25154288751,\n",
       " (0, 239): 30313.055753962566,\n",
       " (0, 240): 98586.34961084095,\n",
       " (0, 241): 62061.28720688525,\n",
       " (0, 242): 71575.44116033331,\n",
       " (0, 243): 89021.52377929424,\n",
       " (0, 244): 41498.92408807348,\n",
       " (0, 245): 65185.52217393234,\n",
       " (0, 246): 51974.76174488788,\n",
       " (0, 247): 77464.71110117808,\n",
       " (0, 248): 81485.71134573092,\n",
       " (0, 249): 31660.764024278662,\n",
       " (0, 250): 60898.66986335383,\n",
       " (0, 251): 70755.6154252584,\n",
       " (0, 252): 42452.54647922443,\n",
       " (0, 253): 37361.20484339046,\n",
       " (0, 254): 98998.35420463885,\n",
       " (0, 255): 44101.423377111336,\n",
       " (0, 256): 47854.21323265002,\n",
       " (0, 257): 58248.728458035126,\n",
       " (0, 258): 86665.42261568706,\n",
       " (0, 259): 32752.669134003976,\n",
       " (0, 260): 40434.16628104614,\n",
       " (0, 261): 90996.20333868204,\n",
       " (0, 262): 70940.04316119027,\n",
       " (0, 263): 65621.02145431857,\n",
       " (0, 264): 70014.85427389106,\n",
       " (0, 265): 60285.77394894834,\n",
       " (0, 266): 90290.8734624559,\n",
       " (0, 267): 40268.70807847268,\n",
       " (0, 268): 85102.74265756861,\n",
       " (0, 269): 89250.68400402936,\n",
       " (0, 270): 74356.25301056827,\n",
       " (0, 271): 57516.20606847021,\n",
       " (0, 272): 79372.17782575486,\n",
       " (0, 273): 77462.48775314032,\n",
       " (0, 274): 16307.389716695327,\n",
       " (0, 275): 28217.578346523907,\n",
       " (0, 276): 92009.89221509722,\n",
       " (0, 277): 84807.58034433651,\n",
       " (0, 278): 50434.50365536519,\n",
       " (0, 279): 10579.338785527003,\n",
       " (0, 280): 98548.42883923385,\n",
       " (0, 281): 50375.81738436262,\n",
       " (0, 282): 47083.37638206175,\n",
       " (0, 283): 101743.80132982519,\n",
       " (0, 284): 69601.82323797698,\n",
       " (0, 285): 13360.525641834945,\n",
       " (0, 286): 77025.0634062089,\n",
       " (0, 287): 86505.25343176619,\n",
       " (0, 288): 60806.75910609426,\n",
       " (0, 289): 39044.17202887464,\n",
       " (0, 290): 29108.96358999374,\n",
       " (0, 291): 17964.66080430122,\n",
       " (0, 292): 84374.94324138775,\n",
       " (0, 293): 45400.846787494054,\n",
       " (0, 294): 22457.43845488257,\n",
       " (0, 295): 102364.58448869342,\n",
       " (0, 296): 63750.46593501822,\n",
       " (0, 297): 69106.34623255373,\n",
       " (0, 298): 15294.249736477528,\n",
       " (0, 299): 97377.61854660015,\n",
       " (0, 300): 43585.18087011436,\n",
       " (0, 301): 86806.35225651004,\n",
       " (0, 302): 94322.75076911208,\n",
       " (0, 303): 17674.22154479554,\n",
       " (0, 304): 93509.12426638063,\n",
       " (0, 305): 100857.04059512651,\n",
       " (0, 306): 49769.35202402985,\n",
       " (0, 307): 80557.379241013,\n",
       " (0, 308): 74190.11150773679,\n",
       " (0, 309): 64691.885010966114,\n",
       " (0, 310): 51008.76203564603,\n",
       " (0, 311): 24725.201280644902,\n",
       " (0, 312): 55449.23637695712,\n",
       " (0, 313): 89301.43406271907,\n",
       " (0, 314): 91230.67378651124,\n",
       " (0, 315): 64240.70838849007,\n",
       " (0, 316): 47352.14342973224,\n",
       " (0, 317): 71710.25844654403,\n",
       " (0, 318): 58798.44047556654,\n",
       " (0, 319): 94827.99114754761,\n",
       " (0, 320): 100481.31553378284,\n",
       " (0, 321): 72133.50212949427,\n",
       " (0, 322): 67909.40283634955,\n",
       " (0, 323): 90394.32247836654,\n",
       " (0, 324): 40505.117311328264,\n",
       " (0, 325): 82905.11456068791,\n",
       " (0, 326): 62787.83685663203,\n",
       " (0, 327): 49363.75970948809,\n",
       " (0, 328): 62178.273372150354,\n",
       " (0, 329): 48752.11946581596,\n",
       " (0, 330): 42953.818105335034,\n",
       " (0, 331): 32501.51003144476,\n",
       " (0, 332): 56144.37077130222,\n",
       " (0, 333): 46763.32352279551,\n",
       " (0, 334): 70043.78439045751,\n",
       " (0, 335): 65783.81958183539,\n",
       " (0, 336): 47941.90374286183,\n",
       " (0, 337): 33372.511727190315,\n",
       " (0, 338): 54734.34801598508,\n",
       " (0, 339): 86459.42107590062,\n",
       " (0, 340): 73223.42605875334,\n",
       " (0, 341): 81185.82521725504,\n",
       " (0, 342): 48005.01445125996,\n",
       " (0, 343): 31311.11207154491,\n",
       " (0, 344): 19770.568185442644,\n",
       " (0, 345): 49728.8883767061,\n",
       " (0, 346): 11257.591176917667,\n",
       " (0, 347): 74041.48133301234,\n",
       " (0, 348): 46407.99190941574,\n",
       " (0, 349): 47172.82349372452,\n",
       " (0, 350): 99486.25253028722,\n",
       " (0, 351): 37449.5282892962,\n",
       " (0, 352): 60193.50582355183,\n",
       " (0, 353): 72064.08617506287,\n",
       " (0, 354): 15724.570738259285,\n",
       " (0, 355): 55858.6073564695,\n",
       " (0, 356): 93450.95040814627,\n",
       " (0, 357): 15712.298956027176,\n",
       " (0, 358): 36313.22420836369,\n",
       " (0, 359): 73573.97555014507,\n",
       " (0, 360): 96616.70490133103,\n",
       " (0, 361): 58717.92538664712,\n",
       " (0, 362): 83445.73058994724,\n",
       " (0, 363): 55238.39072981401,\n",
       " (0, 364): 95854.48693597833,\n",
       " (0, 365): 19702.62637426088,\n",
       " (0, 366): 30483.194438809576,\n",
       " (0, 367): 26828.555846684445,\n",
       " (0, 368): 87984.87480241913,\n",
       " (0, 369): 61513.83638125051,\n",
       " (0, 370): 88827.48523688964,\n",
       " (0, 371): 39239.04783859337,\n",
       " (0, 372): 68743.78441049899,\n",
       " (0, 373): 89902.32704652243,\n",
       " (0, 374): 75318.74248009248,\n",
       " (0, 375): 54913.74846845579,\n",
       " (0, 376): 34870.690029791294,\n",
       " (0, 377): 56828.88325784291,\n",
       " (0, 378): 38916.95308226163,\n",
       " (0, 379): 63322.507660936506,\n",
       " (0, 380): 46906.44719726218,\n",
       " (0, 381): 87761.45766437103,\n",
       " (0, 382): 99613.53162129797,\n",
       " (0, 383): 88633.41474158943,\n",
       " (0, 384): 98865.15994375382,\n",
       " (0, 385): 27644.16338547357,\n",
       " (0, 386): 73093.04613545407,\n",
       " (0, 387): 52527.174907864064,\n",
       " (0, 388): 78591.36792736752,\n",
       " (0, 389): 79307.74590777115,\n",
       " (0, 390): 47914.03736300163,\n",
       " (0, 391): 77366.41361054416,\n",
       " (0, 392): 33703.67212576036,\n",
       " (0, 393): 14176.674829599824,\n",
       " (0, 394): 73269.45923038445,\n",
       " (0, 395): 90923.19270078464,\n",
       " (0, 396): 89730.04668731918,\n",
       " (0, 397): 83502.04414277367,\n",
       " (0, 398): 60232.08469763758,\n",
       " (0, 399): 44576.83348905422,\n",
       " (0, 400): 78432.21552265986,\n",
       " (0, 401): 29235.24487771623,\n",
       " (0, 402): 89433.50171702441,\n",
       " (0, 403): 71541.76846719286,\n",
       " (0, 404): 42986.36743235183,\n",
       " (0, 405): 85214.07847399086,\n",
       " (0, 406): 74685.08958656482,\n",
       " (0, 407): 72337.3893587014,\n",
       " (0, 408): 59374.42699664643,\n",
       " (0, 409): 42046.41960606153,\n",
       " (0, 410): 90596.76569134946,\n",
       " (0, 411): 79282.25956634048,\n",
       " (0, 412): 68510.28216030891,\n",
       " (0, 413): 49206.4773031992,\n",
       " (0, 414): 84619.41300774537,\n",
       " (0, 415): 96829.40893338877,\n",
       " (0, 416): 9672.6510324049,\n",
       " (0, 417): 18899.058101800496,\n",
       " (0, 418): 43567.90477593993,\n",
       " (0, 419): 50330.90231665263,\n",
       " (0, 420): 81862.07807006962,\n",
       " (0, 421): 94370.79598204752,\n",
       " (0, 422): 94148.37965640782,\n",
       " (0, 423): 87622.41864462396,\n",
       " (0, 424): 70647.13378134652,\n",
       " (0, 425): 84440.99346516159,\n",
       " (0, 426): 48541.54886029174,\n",
       " (0, 427): 66029.39264608169,\n",
       " (0, 428): 31758.950666653684,\n",
       " (0, 429): 27219.65195116208,\n",
       " (0, 430): 66888.17442807967,\n",
       " (0, 431): 16266.48519773969,\n",
       " (0, 432): 29227.541963838525,\n",
       " (0, 433): 31372.978687053317,\n",
       " (0, 434): 71159.74488712475,\n",
       " (0, 435): 90494.18215981429,\n",
       " (0, 436): 86080.23656199977,\n",
       " (0, 437): 102390.88380463375,\n",
       " (0, 438): 62930.3043857929,\n",
       " (0, 439): 67973.55658211245,\n",
       " (0, 440): 37042.0241215527,\n",
       " (0, 441): 54098.04966563245,\n",
       " (0, 442): 39138.00492270854,\n",
       " (0, 443): 97994.65300984062,\n",
       " (0, 444): 96300.76871487795,\n",
       " (0, 445): 89730.21998996065,\n",
       " (0, 446): 41376.818423403914,\n",
       " (0, 447): 70228.63640736144,\n",
       " (0, 448): 72736.34930110912,\n",
       " (0, 449): 103616.89510558388,\n",
       " (0, 450): 65290.779976387326,\n",
       " (0, 451): 41780.24062460727,\n",
       " (0, 452): 16749.254790531028,\n",
       " (0, 453): 53056.32374889186,\n",
       " (0, 454): 60076.8015684964,\n",
       " (0, 455): 66037.33719248782,\n",
       " (0, 456): 43718.74019131678,\n",
       " (0, 457): 67528.03847963814,\n",
       " (0, 458): 79165.98314758684,\n",
       " (0, 459): 39221.160532420334,\n",
       " (0, 460): 37894.55462879959,\n",
       " (0, 461): 50536.16478212919,\n",
       " (0, 462): 49901.10097357005,\n",
       " (0, 463): 65043.90987512757,\n",
       " (0, 464): 102045.91772171838,\n",
       " (0, 465): 72958.38394183514,\n",
       " (0, 466): 46775.95823567268,\n",
       " (0, 467): 37348.94357529806,\n",
       " (0, 468): 49472.55684026387,\n",
       " (0, 469): 73319.29150451215,\n",
       " (0, 470): 43236.31131478225,\n",
       " (0, 471): 64131.622171631825,\n",
       " (0, 472): 87557.51641446086,\n",
       " (0, 473): 74016.23799657538,\n",
       " (0, 474): 51406.95089729924,\n",
       " (0, 475): 78124.67032941461,\n",
       " (0, 476): 65469.82077148601,\n",
       " (0, 477): 100483.45058854982,\n",
       " (0, 478): 99494.42240968584,\n",
       " (0, 479): 91885.93684640144,\n",
       " (0, 480): 53425.65959190113,\n",
       " (0, 481): 80486.72640106223,\n",
       " (0, 482): 40742.06392216468,\n",
       " (0, 483): 82403.39477259359,\n",
       " (0, 484): 12122.747999705136,\n",
       " (0, 485): 77959.62956486913,\n",
       " (0, 486): 88121.39875984003,\n",
       " (0, 487): 52251.32360616239,\n",
       " (0, 488): 83219.2687866891,\n",
       " (0, 489): 108434.91741371594,\n",
       " (0, 490): 65646.95350323888,\n",
       " (0, 491): 92638.9016071942,\n",
       " (0, 492): 13974.20845397014,\n",
       " (0, 493): 99990.09377258946,\n",
       " (0, 494): 98280.71856629448,\n",
       " (0, 495): 39860.131401947925,\n",
       " (0, 496): 37768.15153082702,\n",
       " (0, 497): 95979.5065776013,\n",
       " (0, 498): 47620.37037190302,\n",
       " (0, 499): 52572.47987655249,\n",
       " (0, 500): 90244.35617829372,\n",
       " (0, 501): 92025.24268166545,\n",
       " (0, 502): 45073.5097509332,\n",
       " (0, 503): 13387.919852713356,\n",
       " (0, 504): 65575.95824501982,\n",
       " (0, 505): 23267.307290774428,\n",
       " (0, 506): 28807.951551514692,\n",
       " (0, 507): 50595.80642576171,\n",
       " (0, 508): 96148.63526608911,\n",
       " (0, 509): 24456.50971425636,\n",
       " (0, 510): 46238.15990019505,\n",
       " (0, 511): 44523.684902786066,\n",
       " (0, 512): 58944.79661953353,\n",
       " (0, 513): 72336.19523477848,\n",
       " (0, 514): 99312.00832165731,\n",
       " (0, 515): 69614.18406297678,\n",
       " (0, 516): 85613.43836477988,\n",
       " (0, 517): 102352.59104259228,\n",
       " (0, 518): 92432.00152481058,\n",
       " (0, 519): 61974.1048056608,\n",
       " (0, 520): 70176.82577051518,\n",
       " (0, 521): 9626.510211351939,\n",
       " (0, 522): 61713.67797958107,\n",
       " (0, 523): 107551.72894386694,\n",
       " (0, 524): 45065.394935222124,\n",
       " (0, 525): 65990.94673961164,\n",
       " (0, 526): 85542.52615768873,\n",
       " (0, 527): 12757.74623553506,\n",
       " (0, 528): 93683.14692157634,\n",
       " (0, 529): 17759.826574911895,\n",
       " (0, 530): 91360.7595274966,\n",
       " (0, 531): 58906.273587486045,\n",
       " (0, 532): 105408.96718382195,\n",
       " (0, 533): 61818.734122382026,\n",
       " (0, 534): 36721.050915143496,\n",
       " (0, 535): 61135.17216354946,\n",
       " (0, 536): 25463.939440620805,\n",
       " (0, 537): 36060.79074015002,\n",
       " (0, 538): 66890.15560582263,\n",
       " (0, 539): 49288.359991346355,\n",
       " (0, 540): 49484.22283482055,\n",
       " (0, 541): 56538.091163228666,\n",
       " (0, 542): 82378.22016252742,\n",
       " (0, 543): 54126.7415019357,\n",
       " (0, 544): 46984.50604000515,\n",
       " (0, 545): 28007.961049940663,\n",
       " (0, 546): 59634.72786437295,\n",
       " (0, 547): 75156.7201409886,\n",
       " (0, 548): 77855.67735095767,\n",
       " (0, 549): 44642.72288740935,\n",
       " (0, 550): 110786.5151063774,\n",
       " (0, 551): 82426.9155445603,\n",
       " (0, 552): 23791.05093094094,\n",
       " (0, 553): 47459.881834226944,\n",
       " (0, 554): 104351.7335869894,\n",
       " (0, 555): 78936.06845555404,\n",
       " (0, 556): 68184.9789425425,\n",
       " (0, 557): 25682.474577638222,\n",
       " (0, 558): 32503.57712300794,\n",
       " (0, 559): 80814.80133832437,\n",
       " (0, 560): 97709.09764983472,\n",
       " (0, 561): 68292.64523680654,\n",
       " (0, 562): 25060.705064308124,\n",
       " (0, 563): 19859.069861224878,\n",
       " (0, 564): 55832.072107223496,\n",
       " (0, 565): 63374.67083768892,\n",
       " (0, 566): 75305.80164361285,\n",
       " (0, 567): 78138.1646103196,\n",
       " (0, 568): 22696.76153060509,\n",
       " (0, 569): 25640.252784792152,\n",
       " (0, 570): 94222.90871732052,\n",
       " (0, 571): 31456.430556216383,\n",
       " (0, 572): 62732.35855662963,\n",
       " (0, 573): 36349.641200425045,\n",
       " (0, 574): 92434.2509665012,\n",
       " (0, 575): 81371.62890469882,\n",
       " (0, 576): 82421.25237615408,\n",
       " (0, 577): 58666.8530313825,\n",
       " (0, 578): 12010.738484984386,\n",
       " (0, 579): 44942.32978639257,\n",
       " (0, 580): 73538.00605673868,\n",
       " (0, 581): 48964.550660571564,\n",
       " (0, 582): 96178.19186677475,\n",
       " (0, 583): 80524.88389151807,\n",
       " (0, 584): 68609.72540455048,\n",
       " (0, 585): 75213.59882022836,\n",
       " (0, 586): 48425.03544036951,\n",
       " (0, 587): 101998.07821706892,\n",
       " (0, 588): 51859.6888683899,\n",
       " (0, 589): 84092.85859981472,\n",
       " (0, 590): 39475.727174826934,\n",
       " (0, 591): 22073.01102558376,\n",
       " (0, 592): 62019.18707248057,\n",
       " (0, 593): 91381.60505184394,\n",
       " (0, 594): 81307.48440359236,\n",
       " (0, 595): 52932.553004883346,\n",
       " (0, 596): 37826.77299973913,\n",
       " (0, 597): 71568.24037315989,\n",
       " (0, 598): 57836.44381340459,\n",
       " (0, 599): 70629.15319071164,\n",
       " (0, 600): 25178.461724256893,\n",
       " (0, 601): 74722.883192605,\n",
       " (0, 602): 104181.05286531542,\n",
       " (0, 603): 40466.67587404099,\n",
       " (0, 604): 96115.23565392265,\n",
       " (0, 605): 87052.66377776176,\n",
       " (0, 606): 53362.2460703184,\n",
       " (0, 607): 37756.55496141222,\n",
       " (0, 608): 54289.87988520121,\n",
       " (0, 609): 100483.939336794,\n",
       " (0, 610): 48395.22063348677,\n",
       " (0, 611): 103560.86217413499,\n",
       " (0, 612): 100464.76106957762,\n",
       " (1, 0): 57641.47281500988,\n",
       " (1, 1): 0.0,\n",
       " (1, 2): 51375.07175035866,\n",
       " (1, 3): 75914.61615819435,\n",
       " (1, 4): 83498.59959112221,\n",
       " (1, 5): 34708.893712827805,\n",
       " (1, 6): 77330.28838681053,\n",
       " (1, 7): 27097.614609195592,\n",
       " (1, 8): 53802.384552510724,\n",
       " (1, 9): 66543.4278309238,\n",
       " (1, 10): 4072.046522596452,\n",
       " (1, 11): 62596.15612546178,\n",
       " (1, 12): 70689.62468254437,\n",
       " (1, 13): 24884.826011332574,\n",
       " (1, 14): 88281.78954791039,\n",
       " (1, 15): 47958.70231737561,\n",
       " (1, 16): 68573.03905573825,\n",
       " (1, 17): 37510.57161863365,\n",
       " (1, 18): 84998.86115968837,\n",
       " (1, 19): 75702.11952030788,\n",
       " (1, 20): 49875.048425376524,\n",
       " (1, 21): 63411.89402839249,\n",
       " (1, 22): 17117.34784933396,\n",
       " (1, 23): 79019.91297666624,\n",
       " (1, 24): 32571.99416197715,\n",
       " (1, 25): 18581.55964910355,\n",
       " (1, 26): 86738.05047319081,\n",
       " (1, 27): 56846.70588798637,\n",
       " (1, 28): 58107.89281666623,\n",
       " (1, 29): 71085.13845724636,\n",
       " (1, 30): 41921.2608263878,\n",
       " (1, 31): 12861.292581056909,\n",
       " (1, 32): 31118.38260670671,\n",
       " (1, 33): 62080.52124081903,\n",
       " (1, 34): 36137.58447922647,\n",
       " (1, 35): 96053.14418015692,\n",
       " (1, 36): 49996.873157200025,\n",
       " (1, 37): 88483.28744704241,\n",
       " (1, 38): 15988.973952970768,\n",
       " (1, 39): 89981.41654601465,\n",
       " (1, 40): 53403.39036903595,\n",
       " (1, 41): 35316.3063124947,\n",
       " (1, 42): 33739.83708486877,\n",
       " (1, 43): 105467.09998208216,\n",
       " (1, 44): 86756.90030138886,\n",
       " (1, 45): 48697.410697489046,\n",
       " (1, 46): 79396.476245623,\n",
       " (1, 47): 69736.70374894014,\n",
       " (1, 48): 36728.205933440695,\n",
       " (1, 49): 69011.33640551167,\n",
       " (1, 50): 80169.04012306622,\n",
       " (1, 51): 15686.937158539802,\n",
       " (1, 52): 32991.689448645055,\n",
       " (1, 53): 75363.62632568086,\n",
       " (1, 54): 55835.71686753911,\n",
       " (1, 55): 35112.93369761209,\n",
       " (1, 56): 54660.028078927724,\n",
       " (1, 57): 36326.30953385605,\n",
       " (1, 58): 85755.40756420614,\n",
       " (1, 59): 67602.81663396063,\n",
       " (1, 60): 89811.32708042076,\n",
       " (1, 61): 56743.13854394286,\n",
       " (1, 62): 6701.875544715402,\n",
       " (1, 63): 11825.034727655315,\n",
       " (1, 64): 48154.20344941808,\n",
       " (1, 65): 84169.52328225577,\n",
       " (1, 66): 83268.70722744799,\n",
       " (1, 67): 72883.61723268735,\n",
       " (1, 68): 38640.53275534569,\n",
       " (1, 69): 58086.28063710643,\n",
       " (1, 70): 32575.389524118036,\n",
       " (1, 71): 55350.05555091938,\n",
       " (1, 72): 94007.28362584375,\n",
       " (1, 73): 17787.852596972927,\n",
       " (1, 74): 49723.45087826651,\n",
       " (1, 75): 59952.51385807148,\n",
       " (1, 76): 63509.449293408004,\n",
       " (1, 77): 43612.995508198896,\n",
       " (1, 78): 102112.21996191658,\n",
       " (1, 79): 65517.98091537589,\n",
       " (1, 80): 55006.48536925225,\n",
       " (1, 81): 21156.397984146544,\n",
       " (1, 82): 41647.45169012691,\n",
       " (1, 83): 85328.42939762856,\n",
       " (1, 84): 61231.958901199534,\n",
       " (1, 85): 70332.33144445055,\n",
       " (1, 86): 8214.273340884181,\n",
       " (1, 87): 76447.69815029335,\n",
       " (1, 88): 42218.779889529374,\n",
       " (1, 89): 58831.47232438025,\n",
       " (1, 90): 31655.204669508967,\n",
       " (1, 91): 56106.335304141474,\n",
       " (1, 92): 62668.543028979155,\n",
       " (1, 93): 57416.32955725337,\n",
       " (1, 94): 35707.76554005344,\n",
       " (1, 95): 92336.79754190177,\n",
       " (1, 96): 45875.04446772771,\n",
       " (1, 97): 42679.16986459037,\n",
       " (1, 98): 94788.26609362672,\n",
       " (1, 99): 71523.37590093819,\n",
       " (1, 100): 16571.888346775588,\n",
       " (1, 101): 58615.67111010549,\n",
       " (1, 102): 29350.157468085683,\n",
       " (1, 103): 77363.56614367067,\n",
       " (1, 104): 100582.54921457145,\n",
       " (1, 105): 96856.89478220319,\n",
       " (1, 106): 96110.05803855741,\n",
       " (1, 107): 95617.20872817992,\n",
       " (1, 108): 49642.63428797279,\n",
       " (1, 109): 102353.64359899721,\n",
       " (1, 110): 41660.56482630121,\n",
       " (1, 111): 20120.83778161908,\n",
       " (1, 112): 27364.853764053292,\n",
       " (1, 113): 73136.64173058953,\n",
       " (1, 114): 83141.08823424015,\n",
       " (1, 115): 97113.78000714646,\n",
       " (1, 116): 72430.54476626562,\n",
       " (1, 117): 29512.916427620257,\n",
       " (1, 118): 73847.32449826719,\n",
       " (1, 119): 84885.03792698559,\n",
       " (1, 120): 95174.53199427738,\n",
       " (1, 121): 20082.36230823622,\n",
       " (1, 122): 72903.39126755303,\n",
       " (1, 123): 59191.346110544684,\n",
       " (1, 124): 28234.465127391508,\n",
       " (1, 125): 72931.58162297426,\n",
       " (1, 126): 83599.90926351467,\n",
       " (1, 127): 86861.64251734581,\n",
       " (1, 128): 77677.25257721425,\n",
       " (1, 129): 108074.24180378724,\n",
       " (1, 130): 20218.308066482245,\n",
       " (1, 131): 53466.927430125674,\n",
       " (1, 132): 95519.96818656167,\n",
       " (1, 133): 54195.67222061495,\n",
       " (1, 134): 96256.57073625994,\n",
       " (1, 135): 105130.41346757219,\n",
       " (1, 136): 52487.197078362755,\n",
       " (1, 137): 47903.991478775526,\n",
       " (1, 138): 93436.45183782419,\n",
       " (1, 139): 97032.81176135513,\n",
       " (1, 140): 68058.42822290769,\n",
       " (1, 141): 67181.91288081226,\n",
       " (1, 142): 55872.94783846442,\n",
       " (1, 143): 71550.45673272091,\n",
       " (1, 144): 55534.641555352915,\n",
       " (1, 145): 66619.15540707631,\n",
       " (1, 146): 22138.228394683632,\n",
       " (1, 147): 8327.620919280042,\n",
       " (1, 148): 49990.44403526714,\n",
       " (1, 149): 52825.424540080305,\n",
       " (1, 150): 41017.40524122165,\n",
       " (1, 151): 59030.15090561996,\n",
       " (1, 152): 25994.696164157893,\n",
       " (1, 153): 41487.981898001395,\n",
       " (1, 154): 82367.21270777375,\n",
       " (1, 155): 54073.807088884896,\n",
       " (1, 156): 89770.5346979003,\n",
       " (1, 157): 22358.17672794326,\n",
       " (1, 158): 55050.22957881959,\n",
       " (1, 159): 60748.0792131985,\n",
       " (1, 160): 31943.57993721929,\n",
       " (1, 161): 93714.40125263525,\n",
       " (1, 162): 38538.86552277374,\n",
       " (1, 163): 67252.60598575299,\n",
       " (1, 164): 95581.45165334205,\n",
       " (1, 165): 35928.8376092137,\n",
       " (1, 166): 64355.83260535291,\n",
       " (1, 167): 63745.92883676221,\n",
       " (1, 168): 37515.943879328115,\n",
       " (1, 169): 19584.3239326305,\n",
       " (1, 170): 54525.240879896206,\n",
       " (1, 171): 37549.423100316926,\n",
       " (1, 172): 64467.01171123879,\n",
       " (1, 173): 38557.395546432606,\n",
       " (1, 174): 67541.89949535203,\n",
       " (1, 175): 92822.1046620803,\n",
       " (1, 176): 70741.55947221516,\n",
       " (1, 177): 11705.079650246907,\n",
       " (1, 178): 86027.7904729588,\n",
       " (1, 179): 60794.40145980735,\n",
       " (1, 180): 48400.004877404484,\n",
       " (1, 181): 87320.72591328491,\n",
       " (1, 182): 63784.410825428015,\n",
       " (1, 183): 60836.41117294272,\n",
       " (1, 184): 56780.912401788206,\n",
       " (1, 185): 101059.8504230139,\n",
       " (1, 186): 49815.32117063142,\n",
       " (1, 187): 63838.24872944896,\n",
       " (1, 188): 23338.807452480218,\n",
       " (1, 189): 92476.26574243628,\n",
       " (1, 190): 87704.65552790486,\n",
       " (1, 191): 33121.14492299111,\n",
       " (1, 192): 30808.60245513231,\n",
       " (1, 193): 62995.94479218422,\n",
       " (1, 194): 66246.27917694152,\n",
       " (1, 195): 88289.14724953473,\n",
       " (1, 196): 96069.33582238104,\n",
       " (1, 197): 57666.60666491661,\n",
       " (1, 198): 53380.95440513264,\n",
       " (1, 199): 45714.56551155425,\n",
       " (1, 200): 57885.71489895624,\n",
       " (1, 201): 90723.48070798352,\n",
       " (1, 202): 46568.88301492442,\n",
       " (1, 203): 92559.59530218906,\n",
       " (1, 204): 89981.64974840372,\n",
       " (1, 205): 48448.72737377765,\n",
       " (1, 206): 55557.12977210382,\n",
       " (1, 207): 78262.97235366925,\n",
       " (1, 208): 15372.906932198965,\n",
       " (1, 209): 16683.49792682746,\n",
       " (1, 210): 53327.24632773502,\n",
       " (1, 211): 43849.24530831512,\n",
       " (1, 212): 15785.191973977064,\n",
       " (1, 213): 27247.553753058255,\n",
       " (1, 214): 67299.80946964226,\n",
       " (1, 215): 38834.29601781062,\n",
       " (1, 216): 17897.502064392054,\n",
       " (1, 217): 69137.59797937336,\n",
       " (1, 218): 64176.62231796077,\n",
       " (1, 219): 108765.71419713707,\n",
       " (1, 220): 53339.96625828946,\n",
       " (1, 221): 5111.48706595321,\n",
       " (1, 222): 9891.943815587105,\n",
       " (1, 223): 29351.107440538945,\n",
       " (1, 224): 3390.201120718238,\n",
       " (1, 225): 82275.78607405163,\n",
       " (1, 226): 98583.17437723986,\n",
       " (1, 227): 86028.69550375985,\n",
       " (1, 228): 18655.649925731457,\n",
       " (1, 229): 102705.33262213523,\n",
       " (1, 230): 87668.1921766136,\n",
       " (1, 231): 83562.24257668026,\n",
       " (1, 232): 6069.808608805216,\n",
       " (1, 233): 59827.58725561945,\n",
       " (1, 234): 29352.48226198756,\n",
       " (1, 235): 21223.325460938275,\n",
       " (1, 236): 87570.32402830671,\n",
       " (1, 237): 55834.49662252215,\n",
       " (1, 238): 32810.2813982627,\n",
       " (1, 239): 49621.22508072649,\n",
       " (1, 240): 77978.45071508423,\n",
       " (1, 241): 83036.93824450874,\n",
       " (1, 242): 93023.32921159828,\n",
       " (1, 243): 44821.51959748152,\n",
       " (1, 244): 42190.84347683005,\n",
       " (1, 245): 73142.84679693596,\n",
       " (1, 246): 8084.904658317338,\n",
       " (1, 247): 46542.027708199945,\n",
       " (1, 248): 75840.70336869931,\n",
       " (1, 249): 78825.56102887742,\n",
       " (1, 250): 59182.25143637664,\n",
       " (1, 251): 84757.66539782262,\n",
       " (1, 252): 32627.20667724928,\n",
       " (1, 253): 66914.19214471708,\n",
       " (1, 254): 87577.76117043904,\n",
       " (1, 255): 16333.346359104904,\n",
       " (1, 256): 85115.1727916626,\n",
       " (1, 257): 6429.1164047071825,\n",
       " (1, 258): 54956.3360346624,\n",
       " (1, 259): 83611.78561032664,\n",
       " (1, 260): 17736.463282189758,\n",
       " (1, 261): 88515.83793673248,\n",
       " (1, 262): 71466.66976061589,\n",
       " (1, 263): 82931.53192151096,\n",
       " (1, 264): 28824.7206456723,\n",
       " (1, 265): 69280.99396795018,\n",
       " (1, 266): 66064.08020214071,\n",
       " (1, 267): 68315.96215827728,\n",
       " (1, 268): 55786.138964248814,\n",
       " (1, 269): 97998.07153751292,\n",
       " (1, 270): 91898.58248961146,\n",
       " (1, 271): 26561.662799248617,\n",
       " (1, 272): 50753.39382042122,\n",
       " (1, 273): 63429.72402879868,\n",
       " (1, 274): 65736.97198236808,\n",
       " (1, 275): 75359.77785645342,\n",
       " (1, 276): 71651.97083697234,\n",
       " (1, 277): 73308.59965772764,\n",
       " (1, 278): 55919.69821648558,\n",
       " (1, 279): 49480.48315236533,\n",
       " (1, 280): 106954.24001201945,\n",
       " (1, 281): 98236.88701963928,\n",
       " (1, 282): 60210.33401705442,\n",
       " (1, 283): 69690.41751228002,\n",
       " (1, 284): 53305.028492918056,\n",
       " (1, 285): 46257.52139437449,\n",
       " (1, 286): 73759.27167148587,\n",
       " (1, 287): 96568.33515725448,\n",
       " (1, 288): 69530.76687429896,\n",
       " (1, 289): 19517.400221985165,\n",
       " (1, 290): 71470.32635815401,\n",
       " (1, 291): 40648.564033575974,\n",
       " (1, 292): 50849.95542980623,\n",
       " (1, 293): 12931.147865252717,\n",
       " (1, 294): 55716.2376096153,\n",
       " (1, 295): 104356.02120449558,\n",
       " (1, 296): 88514.4184424363,\n",
       " (1, 297): 90634.0412669913,\n",
       " (1, 298): 44499.300808427026,\n",
       " (1, 299): 106060.73604908735,\n",
       " (1, 300): 19627.786509263253,\n",
       " (1, 301): 97019.8377652059,\n",
       " (1, 302): 83160.6180481005,\n",
       " (1, 303): 46986.22885394701,\n",
       " (1, 304): 71762.21047453137,\n",
       " (1, 305): 92804.42198594632,\n",
       " (1, 306): 51127.785482745094,\n",
       " (1, 307): 55498.7686696091,\n",
       " (1, 308): 37448.26058507283,\n",
       " (1, 309): 27670.818653464707,\n",
       " (1, 310): 92430.562159023,\n",
       " (1, 311): 64323.07966165762,\n",
       " (1, 312): 43742.88576993955,\n",
       " (1, 313): 103357.96297199106,\n",
       " (1, 314): 66090.22635080008,\n",
       " (1, 315): 66968.28481845146,\n",
       " (1, 316): 40373.35485545024,\n",
       " (1, 317): 45787.63957510203,\n",
       " (1, 318): 14686.96100838592,\n",
       " (1, 319): 70945.55681013,\n",
       " (1, 320): 58429.1488668396,\n",
       " (1, 321): 28795.637377237457,\n",
       " (1, 322): 34496.74956465653,\n",
       " (1, 323): 68962.6186155781,\n",
       " (1, 324): 26946.10592113028,\n",
       " (1, 325): 96907.00161687328,\n",
       " (1, 326): 43124.453272952815,\n",
       " (1, 327): 25558.86729917576,\n",
       " (1, 328): 73877.2500828091,\n",
       " (1, 329): 25788.462408297444,\n",
       " (1, 330): 86641.36045822727,\n",
       " (1, 331): 82687.73499306329,\n",
       " (1, 332): 89651.44398815342,\n",
       " (1, 333): 20310.578999032452,\n",
       " (1, 334): 95718.16280502336,\n",
       " (1, 335): 48767.96064732352,\n",
       " (1, 336): 17434.80023219377,\n",
       " (1, 337): 34391.47972060677,\n",
       " (1, 338): 54260.63129310855,\n",
       " (1, 339): 48758.1930138126,\n",
       " (1, 340): 63889.87034824926,\n",
       " (1, 341): 80928.95070738337,\n",
       " (1, 342): 88284.28874184306,\n",
       " (1, 343): 39205.31842745536,\n",
       " (1, 344): 39760.361686424876,\n",
       " (1, 345): 26731.65410086918,\n",
       " (1, 346): 60373.28268557058,\n",
       " (1, 347): 87708.49715170493,\n",
       " (1, 348): 76055.23653677634,\n",
       " (1, 349): 66103.82567874895,\n",
       " (1, 350): 101332.09035563235,\n",
       " (1, 351): 48447.14712235999,\n",
       " (1, 352): 4489.343677257931,\n",
       " (1, 353): 44589.27682082702,\n",
       " (1, 354): 58737.56686391586,\n",
       " (1, 355): 95067.15545389704,\n",
       " (1, 356): 57250.05632081888,\n",
       " (1, 357): 62926.14849863792,\n",
       " (1, 358): 82741.03417780277,\n",
       " (1, 359): 80171.89867312007,\n",
       " (1, 360): 109164.57677476929,\n",
       " (1, 361): 95079.94723605506,\n",
       " (1, 362): 50215.54673960946,\n",
       " (1, 363): 5509.328078110378,\n",
       " (1, 364): 82027.01470345959,\n",
       " (1, 365): 37983.92976000938,\n",
       " (1, 366): 48252.24506697494,\n",
       " (1, 367): 76743.79046628151,\n",
       " (1, 368): 79850.28877379427,\n",
       " (1, 369): 59083.699025257825,\n",
       " (1, 370): 75741.7991677391,\n",
       " (1, 371): 57193.357077440465,\n",
       " (1, 372): 84383.69363713061,\n",
       " (1, 373): 85326.40699269065,\n",
       " (1, 374): 95358.54406829267,\n",
       " (1, 375): 59052.8683801433,\n",
       " (1, 376): 82774.79204068863,\n",
       " (1, 377): 46515.91053215055,\n",
       " (1, 378): 19182.27472428128,\n",
       " (1, 379): 46919.528213898586,\n",
       " (1, 380): 94193.70537927728,\n",
       " (1, 381): 73505.66742585423,\n",
       " (1, 382): 72818.4617557155,\n",
       " (1, 383): 103026.18383497915,\n",
       " (1, 384): 62992.27382850302,\n",
       " (1, 385): 35086.57315143673,\n",
       " (1, 386): 94899.24428887373,\n",
       " ...}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dict_A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81bb703c-92b9-47b8-8182-01672f74b61e",
   "metadata": {},
   "source": [
    "## 二、剪枝过程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "aab65c24-0832-4426-83ba-a0466a550d5d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "\n",
    "# V为垂直校正点集合，H为水平校正点集合.共shape-2个点；起点1个，终点1个\n",
    "V = []\n",
    "H = []\n",
    "for i in range(shape):\n",
    "    if correction_vector[i] == 1:\n",
    "        V.append(i)\n",
    "    elif correction_vector[i] == 0:\n",
    "        H.append(i)\n",
    "    else:\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1e5ae416-2153-4b3e-9542-cd85e6e614ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "C = np.ones((shape, shape))\n",
    "for i in range(1, shape - 1):  # 不包含起点和终点\n",
    "    for j in V:\n",
    "        if A[i, j] > min(alpha1, alpha2) / delta:\n",
    "            dict_A[i, j] = 0\n",
    "            C[i, j] = 0\n",
    "    for j in H:\n",
    "        if A[i, j] > min(beta1, beta2) / delta:\n",
    "            dict_A[i, j] = 0\n",
    "            C[i, j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ab6d2e80-cdff-4168-8017-b87f37449fc5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 终点\n",
    "for i in range(shape - 1):\n",
    "    if dict_A[i, shape - 1] > theta / delta:\n",
    "        dict_A[i, shape - 1] = 0\n",
    "        C[i, shape - 1] = 0\n",
    "for i in range(shape):\n",
    "    C[i, i] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "67249cf2-510e-4254-a843-d106fa13531f",
   "metadata": {},
   "outputs": [],
   "source": [
    "edge = []  # 边集\n",
    "for i in range(shape):\n",
    "    for j in range(shape):\n",
    "        if dict_A[i, j] != 0:\n",
    "            edge.append((i, j))\n",
    "        else:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "4e3dc09d-65b0-4829-baee-eb87789106eb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31266"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 剪枝后剩余的边\n",
    "len(edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e2b68c2-6cd8-4c08-a306-b90fbbfe8f63",
   "metadata": {},
   "source": [
    "## 三、使用gurobi建立模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "f5bd48a1-da8a-4fd0-9858-5751e3ff9d2c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Academic license - for non-commercial use only - expires 2022-08-07\n",
      "Using license file C:\\Users\\GDZ\\gurobi.lic\n"
     ]
    }
   ],
   "source": [
    "# 建立模型\n",
    "model=grb.Model()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "2d78d652-c699-4914-baaa-9299a0df1363",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 添加变量\n",
    "# 添加新变量x[i,j],i=0 ~shape-1,j=0~shape-1\n",
    "x = model.addVars(shape, shape, vtype=grb.GRB.BINARY, name='x')\n",
    "# 添加新变量h[i],v[i],i=0 ~shape-1\n",
    "h = model.addVars(shape, vtype=grb.GRB.CONTINUOUS, name=\"h\")\n",
    "v = model.addVars(shape, vtype=grb.GRB.CONTINUOUS, name=\"v\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "07d5278f-fddf-4930-a19a-0935a74c24df",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 添加限制条件\n",
    "# x[i,j]==0 根据C矩阵的信息进行剪枝\n",
    "for i in range(shape):\n",
    "    for j in range(shape):\n",
    "        if C[i, j] == 0:\n",
    "            model.addConstr(x[i, j] == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "588cce35-e0e1-400e-929a-39b3f6817a5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 添加限制条件起始点，中间点，终点的出度入度条件\n",
    "test1 = [0] * shape  # 出度表达式\n",
    "test2 = [0] * shape  # 入度表达式\n",
    "# test1[i]表示i节点的出度，起点\n",
    "for (i, j) in edge:\n",
    "    test1[i] = test1[i] + x[i, j]\n",
    "# test2[i]表示i节点的入度，终点\n",
    "for (j, i) in edge:\n",
    "    test2[i] = test2[i] + x[j, i]\n",
    "for i in range(shape):\n",
    "    if i == 0:\n",
    "        #起点 一定是出度为1，入度为0\n",
    "        model.addConstr(test1[i] == 1)\n",
    "        model.addConstr(test2[i] == 0)\n",
    "    elif 0 < i < shape - 1:\n",
    "        #中间点 一定是出度和入度同时为0,或1         \n",
    "        model.addConstr(test1[i] == test2[i])\n",
    "    else:\n",
    "        model.addConstr(test1[i] == 0)\n",
    "        model.addConstr(test2[i] == 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "e88ad306-bae3-4f61-b7a7-fbeef594041a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 添加限制条件对h，v进行约束\n",
    "for (i, j) in edge:\n",
    "    #从i点到j点，水平误差应该满足     \n",
    "    model.addConstr(correction_vector[i] * h[i] + delta * A[i, j] - h[j] <= 10000 - 10000 * x[i, j])\n",
    "    #从i点到j点，垂直误差应该满足   \n",
    "    model.addConstr((1 - correction_vector[i]) * v[i] + delta * A[i, j] - v[j] <= 10000 - 10000 * x[i, j])\n",
    "# h,v代表飞行棋到达i点是误差校正前的水平偏移量和竖直偏移量\n",
    "for i in range(shape):\n",
    "    if i == 0:\n",
    "        model.addConstr(h[i] == 0)\n",
    "        model.addConstr(v[i] == 0)\n",
    "    elif 0 < i < shape - 1:\n",
    "        if correction_vector[i] == 1:\n",
    "            model.addConstr(h[i] <= alpha2)\n",
    "            model.addConstr(v[i] <= alpha1)\n",
    "        else:\n",
    "            model.addConstr(h[i] <= beta2)\n",
    "            model.addConstr(v[i] <= beta1)\n",
    "    else:\n",
    "        model.addConstr(h[i] <= theta)\n",
    "        model.addConstr(v[i] <= theta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "aabc2590-8be3-4ab8-b94e-7fd06e0a8b6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 添加目标函数\n",
    "# 设置罚函数系数\n",
    "dict_modify = {}\n",
    "for i in range(shape):\n",
    "    for j in range(shape):\n",
    "        dict_modify[i, j] = 10000\n",
    "dict_modify = grb.tupledict(dict_modify)\n",
    "dict_A=grb.tupledict(dict_A)\n",
    "model.setObjective(dict_A.prod(x) + 1 * dict_modify.prod(x), grb.GRB.MINIMIZE)\n",
    "model.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "940bb487-ab16-44af-89e7-f16b18e00e40",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)\n",
      "Thread count: 6 physical cores, 6 logical processors, using up to 6 threads\n",
      "Optimize a model with 408876 rows, 376995 columns and 565814 nonzeros\n",
      "Model fingerprint: 0x4f45c8bb\n",
      "Variable types: 1226 continuous, 375769 integer (375769 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+04]\n",
      "  Objective range  [1e+04, 1e+05]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+04]\n",
      "Presolve removed 372927 rows and 352712 columns\n",
      "Presolve time: 1.69s\n",
      "Presolved: 35949 rows, 24283 columns, 127155 nonzeros\n",
      "Variable types: 611 continuous, 23672 integer (23672 binary)\n",
      "\n",
      "Deterministic concurrent LP optimizer: primal and dual simplex\n",
      "Showing first log only...\n",
      "\n",
      "Concurrent spin time: 0.02s\n",
      "\n",
      "Solved with dual simplex\n",
      "\n",
      "Root relaxation: objective 1.646440e+05, 561 iterations, 0.17 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0 164643.952    0   17          - 164643.952      -     -    2s\n",
      "H    0     0                    224264.49714 164643.952  26.6%     -    2s\n",
      "H    0     0                    220936.20645 164643.952  25.5%     -    2s\n",
      "     0     0 172474.849    0   19 220936.206 172474.849  21.9%     -    2s\n",
      "H    0     0                    194869.71638 172474.849  11.5%     -    3s\n",
      "     0     0 172525.937    0   14 194869.716 172525.937  11.5%     -    3s\n",
      "     0     0 173050.786    0   17 194869.716 173050.786  11.2%     -    3s\n",
      "     0     0 173050.786    0   17 194869.716 173050.786  11.2%     -    4s\n",
      "     0     0 173050.786    0   15 194869.716 173050.786  11.2%     -    4s\n",
      "     0     0 173050.786    0   17 194869.716 173050.786  11.2%     -    4s\n",
      "     0     0 173116.647    0   14 194869.716 173116.647  11.2%     -    4s\n",
      "     0     0 173589.133    0   14 194869.716 173589.133  10.9%     -    4s\n",
      "     0     0 173616.588    0   14 194869.716 173616.588  10.9%     -    4s\n",
      "     0     0 173777.666    0   14 194869.716 173777.666  10.8%     -    4s\n",
      "     0     0 173793.465    0   14 194869.716 173793.465  10.8%     -    4s\n",
      "     0     0 173794.443    0   14 194869.716 173794.443  10.8%     -    4s\n",
      "     0     0 174035.473    0   17 194869.716 174035.473  10.7%     -    4s\n",
      "     0     0 174040.266    0   19 194869.716 174040.266  10.7%     -    4s\n",
      "     0     0 174450.844    0   16 194869.716 174450.844  10.5%     -    4s\n",
      "     0     0 174484.426    0   14 194869.716 174484.426  10.5%     -    4s\n",
      "     0     0 175117.775    0   15 194869.716 175117.775  10.1%     -    4s\n",
      "     0     0 175217.568    0   14 194869.716 175217.568  10.1%     -    4s\n",
      "     0     0 175691.501    0   20 194869.716 175691.501  9.84%     -    4s\n",
      "     0     0 175789.637    0   17 194869.716 175789.637  9.79%     -    4s\n",
      "     0     0 175795.165    0   20 194869.716 175795.165  9.79%     -    4s\n",
      "     0     0 176434.592    0   14 194869.716 176434.592  9.46%     -    4s\n",
      "     0     0 176439.668    0   14 194869.716 176439.668  9.46%     -    4s\n",
      "     0     0 177107.218    0   14 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   17 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   15 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   14 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   19 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   19 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   14 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   23 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177107.218    0   14 194869.716 177107.218  9.12%     -    5s\n",
      "     0     0 177129.040    0   14 194869.716 177129.040  9.10%     -    5s\n",
      "     0     0 178213.824    0   14 194869.716 178213.824  8.55%     -    5s\n",
      "     0     0 178527.945    0   21 194869.716 178527.945  8.39%     -    5s\n",
      "     0     0 179531.790    0   19 194869.716 179531.790  7.87%     -    5s\n",
      "     0     0 179824.445    0   18 194869.716 179824.445  7.72%     -    5s\n",
      "     0     0 182290.616    0   21 194869.716 182290.616  6.46%     -    5s\n",
      "     0     0 182290.616    0   21 194869.716 182290.616  6.46%     -    5s\n",
      "     0     0 182509.009    0   17 194869.716 182509.009  6.34%     -    5s\n",
      "     0     0 182509.009    0   15 194869.716 182509.009  6.34%     -    5s\n",
      "     0     0 182509.009    0   24 194869.716 182509.009  6.34%     -    5s\n",
      "     0     0 182509.009    0    8 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   21 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   15 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   14 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   14 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   15 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182509.009    0   15 194869.716 182509.009  6.34%     -    6s\n",
      "     0     0 182559.205    0   18 194869.716 182559.205  6.32%     -    6s\n",
      "     0     0 183698.482    0   15 194869.716 183698.482  5.73%     -    6s\n",
      "     0     0 184222.157    0   20 194869.716 184222.157  5.46%     -    6s\n",
      "     0     0 184473.302    0   19 194869.716 184473.302  5.34%     -    6s\n",
      "     0     0 184721.965    0   20 194869.716 184721.965  5.21%     -    6s\n",
      "     0     0 184728.432    0   18 194869.716 184728.432  5.20%     -    6s\n",
      "     0     0 184735.082    0   21 194869.716 184735.082  5.20%     -    6s\n",
      "     0     0 184746.666    0   16 194869.716 184746.666  5.19%     -    6s\n",
      "     0     0 184942.601    0   14 194869.716 184942.601  5.09%     -    6s\n",
      "     0     0 184942.601    0   18 194869.716 184942.601  5.09%     -    6s\n",
      "     0     0 184942.601    0   17 194869.716 184942.601  5.09%     -    6s\n",
      "     0     0 184942.601    0   19 194869.716 184942.601  5.09%     -    6s\n",
      "     0     0 184942.601    0   14 194869.716 184942.601  5.09%     -    6s\n",
      "     0     0 186923.322    0   19 194869.716 186923.322  4.08%     -    6s\n",
      "     0     0 187038.468    0   13 194869.716 187038.468  4.02%     -    6s\n",
      "     0     0 187220.748    0    4 194869.716 187220.748  3.93%     -    6s\n",
      "     0     0 187304.645    0   28 194869.716 187304.645  3.88%     -    6s\n",
      "     0     0 187304.645    0   28 194869.716 187304.645  3.88%     -    6s\n",
      "     0     0 189565.608    0   15 194869.716 189565.608  2.72%     -    6s\n",
      "     0     0 189565.608    0   17 194869.716 189565.608  2.72%     -    6s\n",
      "     0     0 189985.255    0    4 194869.716 189985.255  2.51%     -    6s\n",
      "     0     0 193552.546    0    4 194869.716 193552.546  0.68%     -    6s\n",
      "     0     0 193649.509    0   10 194869.716 193649.509  0.63%     -    6s\n",
      "H    0     1                    194861.06498 193649.509  0.62%     -    6s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 2\n",
      "  Implied bound: 1\n",
      "  Clique: 8\n",
      "  MIR: 2\n",
      "  Zero half: 1\n",
      "  RLT: 8\n",
      "  Relax-and-lift: 1\n",
      "\n",
      "Explored 1 nodes (4216 simplex iterations) in 6.57 seconds\n",
      "Thread count was 6 (of 6 available processors)\n",
      "\n",
      "Solution count 4: 194861 194870 220936 224264 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.948610649820e+05, best bound 1.948610649820e+05, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "fe9769c5-1eaa-4299-95cc-a707b9e35fbd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x[0,503]1\n",
      "x[91,607]1\n",
      "x[250,340]1\n",
      "x[277,612]1\n",
      "x[294,91]1\n",
      "x[340,277]1\n",
      "x[503,294]1\n",
      "x[540,250]1\n",
      "x[607,540]1\n",
      "Obj:194861\n"
     ]
    }
   ],
   "source": [
    "for s in model.getVars():\n",
    "    if s.x == 1:\n",
    "        print('%s''%g' % (s.varName, s.x))\n",
    "print('Obj:%g' % model.objVal)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86d9b590-beee-4868-bd95-dabd709ebcde",
   "metadata": {},
   "source": [
    "## 绘制3D图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "a74d3c75-1c46-4cd1-88ff-21c64623e5e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd\n",
    "from mpl_toolkits.mplot3d import Axes3D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "6c69ed83-1ada-43e6-b8a5-183d497611ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "node = [0, 503, 294, 91, 607, 540, 250, 340, 277, 612]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "aa764d52-0553-49bb-b00b-3ffe9cf02a70",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ed2b69bb1ef140a19e4cee0abdc3946b",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib widget\n",
    "fig = plt.figure(figsize=plt.figaspect(1)*1.7)\n",
    "ax = Axes3D(fig)\n",
    "# 起点，终点为黄色，中间点1为绿+，0为蓝^\n",
    "for i in range(613):\n",
    "    if i == 0:\n",
    "        ax.scatter(coordinates[i, 0], coordinates[i, 1], coordinates[i, 2], c='r', marker='^')\n",
    "    elif 0 < i < 612 and correction_vector[i] == 1:\n",
    "        ax.scatter(coordinates[i, 0], coordinates[i, 1], coordinates[i, 2], c='g', marker='.')\n",
    "    elif 0 < i < 612 and correction_vector[i] == 0:\n",
    "        ax.scatter(coordinates[i, 0], coordinates[i, 1], coordinates[i, 2], c='b', marker='.')\n",
    "    else:\n",
    "        ax.scatter(coordinates[i, 0], coordinates[i, 1], coordinates[i, 2], c='r', marker='^')\n",
    "        \n",
    "for i in range(len(node) - 1):\n",
    "    ax.plot([coordinates[node[i], 0], coordinates[node[i + 1], 0]],\n",
    "            [coordinates[node[i], 1], coordinates[node[i + 1], 1]],\n",
    "            [coordinates[node[i], 2], coordinates[node[i + 1], 2]], c='k', linewidth=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cdfbef3-1eda-482a-a870-885f442ce01b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "495810c1-0148-4bc8-b8be-f30943016b23",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}