{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 정수 계획법\n", "\n", "정수 계획법(integer programming)\n", "\n", "## Example 6-4\n", "\n", "**이강우 & 김정자. (2012). _EXCEL 2010 경영과학_. 한경사, 380.**\n", "\n", "**Table 6-1**는 배낭에 넣어 갖고 갈 수 있는 3개의 상이한 품목에 대한 품목별 무게와 효용 및 배낭의 보관능력을 나타내고 있다. 배낭의 보관능력 제약을 만족하면서 배낭에 넣어 갖고 갈 수 있는 품목의 효용을 최대화하는 정수계획모형을 작성한 후 최적 정수해를 구하라. 단, 같은 품목을 중복으로 배낭에 넣을 수 없다.\n", "\n", "|Item|Weight|Value|\n", "|:-:|:-:|:-:|\n", "|1|3|6|\n", "|2|4|8|\n", "|3|2|3|\n", "\n", "단일품목 배낭문제를 0-1정수계획모형으로 정식화하기 위해서는 배낭에 넣을 수 있는 품목 $j$를 결정변수 $X_{j}$라고 정의하고 $X_{j}$가 0과 1 중에서 하나의 값만 갖도록 하여야 한다. 왜냐하면 배낭에 넣어 갖고 갈 수 있는 품목은 단일품목 배낭문제의 성격상 그 품목을 선택하거나 또는 선택하지 않기 때문이다. 따라서 $X_{j}$가 1의 값을 가질 때는 품목 $j$가 선택되고, 0의 값을 가질 때는 품목 $j$가 선택되지 않는다고 하자. 만일 각 품목에 대해 전체가 아닌 일부분의 선택이 가능하다면 이 문제는 분할성의 가정이 성립하므로 선형계획문제로 정식화할 수 있다.\n", "\n", "$$X_{j} = \\begin{cases}\n", "1, \\text{ 배낭에 품목 $j$를 넣는 경우 $(j=1,2,3)$}\\\\\n", "0, \\text{ 배낭에 품목 $j$를 넣지 않는 경우 $(j=1,2,3)$}\\\\\n", "\\end{cases}$$" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status Optimal\n", "Z = 11.0\n", "X1 = 0.0\n", "X2 = 1.0\n", "X3 = 1.0\n" ] } ], "source": [ "from pulp import *\n", "\n", "prob = LpProblem(name='0-1 Knapsack Problem', sense=LpMaximize)\n", "\n", "x1 = LpVariable(name='X1', lowBound=0, cat='Binary')\n", "x2 = LpVariable(name='X2', lowBound=0, cat='Binary')\n", "x3 = LpVariable(name='X3', lowBound=0, cat='Binary')\n", "\n", "prob += 7*x1 + 8*x2 + 3*x3\n", "\n", "prob += 3*x1 + 4*x2 + 2*x3 <= 6\n", "\n", "# Solving problem\n", "prob.solve()\n", "print('Status', LpStatus[prob.status])\n", "\n", "print('Z = {}'.format(value(prob.objective)))\n", "for i in prob.variables():\n", " print('{} = {}'.format(i.name, i.varValue))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Multiple Knapsack Problem\n", "\n", "### Example 6-5\n", "\n", "**이강우 & 김정자. (2012). _EXCEL 2010 경영과학_. 한경사, 389.**\n", "\n", "

Table 6-3는 트럭에 적재할 수 있는 3개의 상이한 품목에 대하여 이들 품목별 단위당 무게, 적재가능 수량, 단위당 수익 및 트럭의 적재능력을 나타내고 있다. 트럭의 적재능력의 제약을 만족하면서 트럭에 품목들을 적재하여 최대의 수익을 얻을려고 한다. 트럭의 수익을 최대로 하는 적재 품목의 수량을 결정하기 위한 정수계획 모형을 작성하고 최적해를 구하라. 단, 트럭에 적재하는 품목의 수량은 정수단위로 결정해야 한다.

\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Table 6-1. 단일품목 배낭문제의 자료
품목단위당 무게(kg)적재가능수량(개)단위당 수익(천원)적재능력(kg)
130100706
24020080
32030030
" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status Optimal\n", "Z = 21000.0\n", "x1 = 100.0\n", "x2 = 175.0\n", "x3 = 0.0\n" ] } ], "source": [ "from pulp import *\n", "\n", "prob = LpProblem(name='Knapsack Problem', sense=LpMaximize)\n", "\n", "x1 = LpVariable(name='x1', lowBound=0, cat='Integer')\n", "x2 = LpVariable(name='x2', lowBound=0, cat='Integer')\n", "x3 = LpVariable(name='x3', lowBound=0, cat='Integer')\n", "\n", "prob += 70*x1 + 80*x2 + 30*x3\n", "\n", "prob += 30*x1 + 40*x2 + 20*x3 <= 10000\n", "prob += x1 <= 100\n", "prob += x2 <= 200\n", "prob += x3 <= 300\n", "\n", "# Solving problem\n", "prob.solve()\n", "print('Status', LpStatus[prob.status])\n", "\n", "print('Z = {}'.format(value(prob.objective)))\n", "for i in prob.variables():\n", " print('{} = {}'.format(i.name, i.varValue))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example: Bin Packing Problem\n", "\n", "$$\\begin{split}\n", " & \\text{minimize } &Z=&\\sum_{i=1}^{n}y_{i} & &\\\\[1ex]\n", " & \\text{subject to } & &\\sum_{j=1}^{n}w_{j}x_{ij} \\le cy_{i},\\quad &i \\in N = \\{1,...,n\\},&\\\\[1ex]\n", " & & &\\sum_{i=1}^{n}x_{ij} = 1, &j \\in N,&\\\\[1ex] \n", " & & &y_{i} = 0 or 1, &i \\in N,&\\\\[1ex] \n", " & & &x_{ij} = 0 or 1 &i \\in N, j \\in N,&\\\\[1ex] \n", "\\end{split}$$" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Solved in 0.05406332015991211 seconds.\n", "Bins used: 5.0\n", "0: ['a', 'b', 'e', 'i', 'm', 'n']\n", "1: ['c', 'g', 'h', 'l']\n", "12: ['d']\n", "13: ['f']\n", "7: ['k']\n" ] } ], "source": [ "from pulp import *\n", "import time\n", "\n", "#\n", "# A list of item tuples (name, weight) -- name is meaningless except to humans.\n", "# Weight and Size are used interchangeably here and elsewhere.\n", "#\n", "items = [(\"a\", 5),\n", " (\"b\", 6),\n", " (\"c\", 7),\n", " (\"d\", 32),\n", " (\"e\", 2),\n", " (\"f\", 32),\n", " (\"g\", 5),\n", " (\"h\", 7),\n", " (\"i\", 9),\n", " (\"k\", 12),\n", " (\"l\", 11),\n", " (\"m\", 1),\n", " (\"n\", 2)]\n", "\n", "itemCount = len(items)\n", "\n", "# Max number of bins allowed.\n", "maxBins = 32\n", "\n", "# Bin Size\n", "binCapacity = 32\n", "\n", "\n", "\n", "# Indicator variable assigned 1 when the bin is used.\n", "y = pulp.LpVariable.dicts('BinUsed', range(maxBins),\n", " lowBound = 0,\n", " upBound = 1,\n", " cat = pulp.LpInteger)\n", "\n", "# An indicator variable that is assigned 1 when item is placed into binNum\n", "possible_ItemInBin = [(itemTuple[0], binNum) for itemTuple in items\n", " for binNum in range(maxBins)]\n", "x = pulp.LpVariable.dicts('itemInBin', possible_ItemInBin,\n", " lowBound = 0,\n", " upBound = 1,\n", " cat = pulp.LpInteger)\n", "\n", "# Initialize the problem\n", "prob = LpProblem(\"Bin Packing Problem\", LpMinimize)\n", "\n", "# Add the objective function.\n", "prob += lpSum([y[i] for i in range(maxBins)]), \"Objective: Minimize Bins Used\"\n", "\n", "#\n", "# This is the constraints section.\n", "#\n", "\n", "# First constraint: For every item, the sum of bins in which it appears must be 1\n", "for j in items:\n", " prob += lpSum([x[(j[0], i)] for i in range(maxBins)]) == 1, (\"An item can be in only 1 bin -- \" + str(j[0]))\n", "\n", "# Second constraint: For every bin, the number of items in the bin cannot exceed the bin capacity\n", "for i in range(maxBins):\n", " prob += lpSum([items[j][1] * x[(items[j][0], i)] for j in range(itemCount)]) <= binCapacity*y[i], (\"The sum of item sizes must be smaller than the bin -- \" + str(i))\n", "\n", "# Write the model to disk\n", "\n", "# Solve the optimization.\n", "start_time = time.time()\n", "prob.solve()\n", "print(\"Solved in %s seconds.\" % (time.time() - start_time))\n", "\n", "\n", "# Bins used\n", "print(\"Bins used: \" + str(sum(([y[i].value() for i in range(maxBins)]))))\n", "\n", "# The rest of this is some unpleasent massaging to get pretty results.\n", "bins = {}\n", "for itemBinPair in x.keys():\n", " if(x[itemBinPair].value() == 1):\n", " itemNum = itemBinPair[0]\n", " binNum = itemBinPair[1]\n", " if binNum in bins:\n", " bins[binNum].append(itemNum)\n", " else:\n", " bins[binNum] = [itemNum]\n", "\n", "for b in bins.keys():\n", " print(str(b) + \": \" + str(bins[b]))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 3" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pulp import *\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob = LpProblem(name='Profit maximising problem', sense=LpMaximize)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x1 = LpVariable(name='x1', lowBound=0, cat='Integer')\n", "x2 = LpVariable(name='x2', lowBound=0, cat='Integer')\n", "\n", "prob += 30000*x1 + 45000*x2, 'Profit'\n", "\n", "prob += 3*x1 + 4*x2 <= 30\n", "prob += 5*x1 + 6*x2 <= 60\n", "prob += 1.5*x1 + 3*x2 <= 21" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob.solve(solver=GUROBI())\n", "\n", "print(LpStatus[prob.status])\n", "\n", "# Print our decision variable values\n", "print('Production of Car x1 = {}'.format(x1.varValue))\n", "print('Production of Car x2 = {}'.format(x2.varValue))\n", "\n", "# Print our objective function value\n", "print(value(prob.objective))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Knapsack Problem" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pulp import *" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "model = LpProblem('knapsack problem', LpMaximize)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x1 = LpVariable('x1', lowBound=0, upBound=1, cat=LpInteger)\n", "x2 = LpVariable('x2', lowBound=0, upBound=1, cat=LpInteger)\n", "x3 = LpVariable('x3', lowBound=0, upBound=1, cat=LpInteger)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "model += 7*x1 + 8*x2 + 3*x3\n", "model += 3*x1 + 4*x2 + 2*x3 <= 6" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "model.solve(GUROBI())\n", "\n", "print('Status', LpStatus[model.status])\n", "print(value(model.objective))\n", "for v in model.variables():\n", " print(v.name, '=', v.varValue)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Knapsack Problem II" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pulp import *" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "items = ['A', 'B', 'C']\n", "weights = [3, 4, 2]\n", "values = [7, 8, 3]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob = LpProblem('knapsack problem', LpMaximize)\n", "\n", "# Define decision variables\n", "decision_variables = []\n", "for num, i in enumerate(items):\n", " var_str = str('x' + str(num))\n", " variables = LpVariable(str(var_str), lowBound=0, upBound=1, cat='Integer')\n", " decision_variables.append(variables)\n", "print(decision_variables)\n", "\n", "# Define objective function\n", "objective_function = ''\n", "for u, uf in enumerate(values):\n", " for d, dv in enumerate(decision_variables):\n", " if u == d:\n", " objective_function += uf * dv\n", " \n", "prob += objective_function\n", "print(objective_function)\n", "\n", "# Define constraint\n", "capacity = 6\n", "constraint = ''\n", "for w, wt in enumerate(weights):\n", " for d, dv in enumerate(decision_variables):\n", " if w == d:\n", " constraint += wt * dv\n", " \n", "prob += constraint <= capacity\n", "print(constraint)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob.solve(GUROBI())\n", "\n", "print('Status', LpStatus[prob.status])\n", "print(value(prob.objective))\n", "for v in prob.variables():\n", " print(v.name, '=', v.varValue)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pulp import *" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "data = {\n", " (\"SMITH\"): [6,8,30,6,20], (\"JOHNSON\"): [6,8,50,0,24], \n", " ('WILLIAMS'): [6,8,30,0,24], ('JONES'): [6,8,30,0,24], \n", " ('BROWN'): [6,8,40,0,24], ('DAVIS'): [6,8,50,0,24],\n", " ('MILLER'): [6,8,45,6,18], ('WILSON'): [6,8,30,0,24], \n", " ('MOORE'): [6,8,35,0,24], ('TAYLOR'): [6,8,40,0,24], \n", " ('ANDERSON'): [2,3,60,0,6], ('THOMAS'): [2,4,40,0,24],\n", " ('JACKSON') :[2,4,60,8,16], ('WHITE'): [2,6,55,0,24], \n", " ('HARRIS'): [2,6,45,0,24], ('MARTIN'): [2,3,40,0,24], \n", " ('THOMPSON'): [2,5,50,12,24], ('GARCIA'): [2,4,50,0,24],\n", " ('MARTINEZ'): [2,4,40,0,24], ('ROBINSON'): [2,5,50,0,24]\n", "}\n", "\n", "required = [1,1,2,3,6,6,7,8,9,8,8,8,7,6,6,5,5,4,4,3,2,2,2,2]\n", "\n", "time = 24" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "employee = list(data.keys())\n", "mins, maxs, costs, avs, ave = splitDict(data)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x = {}\n", "for d in employee:\n", " for i in range(time):\n", " for j in range(i+1, time+1):\n", " x[d,i,j] = LpVariable(name='x_%s%d%d'%(d,i,j), cat='Binary')\n", " \n", "staff_number = {}\n", "for t in range(time):\n", " staff_number[t] = LpVariable(name='staffNumber_%d'%t, cat='Integer', lowBound=required[t])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob = LpProblem('Work Schedule', LpMinimize)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "prob += lpSum(lpSum(lpSum((j-i) * x[d,i,j] * costs[d] for j in range(i+1,time+1)) \\\n", " for i in range(time)) for d in employee)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for d in employee:\n", " prob += (lpSum(lpSum(x[d,i,j] for j in range(i+1,ave[d]+1)if min[d] <= \\\n", " (j-i) <= max[d]) for i in range(avs[d],ave[d])) <= 1)\n", " \n", " prob += (lpSum(lpSum(x[d,i,j] for j in range(i+1,time+1)) for i in range(time)) <= \\\n", " lpSum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1) if min[d] <= (j-i) <= \\\n", " max[d]) for i in range(avs[d],ave[d])))\n", "\n", " \n", " \n", "for d in employee:\n", " m.addConstr(quicksum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1)if min[d] <= (j-i) <= max[d])for i in range(avs[d],ave[d]))<=1)\n", " m.addConstr(quicksum(quicksum(x[d,i,j] for j in range(i+1,t+1))for i in range(t))<=quicksum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1)\n", " if min[d] <= (j-i) <= max[d])for i in range(avs[d],ave[d])))\n", " \n", " \n", "for c in range(t):\n", " m.addConstr(quicksum(quicksum(quicksum(x[d,i,j] for j in range(i+1,t+1)if i <= c