Integer Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Дано**\n",
    "\n",
    "* Бренд выпускает $m$ продуктов, $i=1 \\dots m$\n",
    "* Используется $n$ рекламных форматов, $j=1 \\dots n$\n",
    "* Для каждого продукта производится $х_{i,j}$ рекламных форматов\n",
    "* $c_j$ - стоимость производства единицы формата $j$\n",
    "* $q_j$ - максимальное ко-во формата $j$, которое может быть произведено\n",
    "* $B$ - общий месячный бюджет \n",
    "* $е_j$ - эффективность формата $j$, например ко-во собираемых лайков\n",
    "* $E_i$ - целевая еффективность для $i$ продукта \n",
    "\n",
    "**Необходимо найти**\n",
    "* Оптимальное $x_{ji}$\n",
    "  * Максимальную общую эффективность при фиксированном бюджете: \n",
    "    $B \\leq \\sum\\limits_{i=1}^m \\sum \\limits_{j=1}^n x_{i,j} c_j$\n",
    "  * Минимальный бюджет при заданной эффективности:\n",
    "    $E_i \\geq \\sum \\limits_{j=1}^n x_{i,j} e_j$\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cvxpy as cv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ценa единицы форматa\n",
      " [1300. 3200. 3500. 6600. 4900. 3300. 1000. 5300. 3900. 4200.]\n",
      "Максимальное ко-во единиц форматa\n",
      " [250. 190. 220.  70. 280. 160. 160. 100. 280.  40.]\n",
      "Эффективность формата\n",
      " [9200. 7200. 7600. 9900. 5500. 8400.  900. 9300. 8600. 3400.]\n",
      "\n",
      "Целевая эффективность для продукта\n",
      " [345000.  50000. 320000.  30000. 255000.]\n",
      "Бюджет 100000\n"
     ]
    }
   ],
   "source": [
    "# m продуктов\n",
    "m = 5\n",
    "# n форматов\n",
    "n = 10\n",
    "# Цена формата\n",
    "c = np.around(np.random.uniform(size=n)*100)*100\n",
    "# возможности продакшена/платформы по форматам\n",
    "q = np.around(np.random.uniform(size=n)*10)*30+10\n",
    "# эффективность формата (например ко-во лайков)\n",
    "e = np.around(np.random.uniform(size=n)*100)*100\n",
    "# Цель, которую необходимо достигнуть по каждому из продуктов\n",
    "E = np.around(np.random.uniform(size=m)*100)*5000\n",
    "# Бюджет\n",
    "B = 100000\n",
    "\n",
    "print(\"Ценa единицы форматa\\n\", c)\n",
    "print(\"Максимальное ко-во единиц форматa\\n\", q)\n",
    "print(\"Эффективность формата\\n\", e)\n",
    "print()\n",
    "print(\"Целевая эффективность для продукта\\n\", E)\n",
    "print(\"Бюджет\",B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Минимальный бюджет"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Итоговый минимальный бюджет: 465542.9\n",
      "Выпускаем форматы:\n",
      " [[7. 6. 6. 3. 3. 7. 2. 3. 6. 2.]\n",
      " [1. 1. 1. 1. 1. 1. 2. 1. 1. 1.]\n",
      " [6. 6. 6. 3. 2. 6. 2. 3. 6. 2.]\n",
      " [0. 0. 0. 0. 1. 0. 1. 0. 0. 1.]\n",
      " [5. 5. 5. 2. 2. 5. 2. 2. 5. 2.]]\n",
      "Форматов на продукт:\n",
      " [45.  8. 42.  5. 34.]\n",
      "Ко-во формата:\t [19. 18. 18.  9.  9. 19.  9.  9. 18.  8.]\n",
      "\tлимит:\t [250. 190. 220.  70. 280. 160. 160. 100. 280.  40.]\n",
      "Эффективность:\n",
      " [[64400. 43200. 45600. 29700. 16500. 58800.  1800. 27900. 51600.  6800.]\n",
      " [ 9200.  7200.  7600.  9900.  5500.  8400.  1800.  9300.  8600.  3400.]\n",
      " [55200. 43200. 45600. 29700. 11000. 50400.  1800. 27900. 51600.  6800.]\n",
      " [    0.     0.     0.     0.  5500.     0.   900.     0.     0.  3400.]\n",
      " [46000. 36000. 38000. 19800. 11000. 42000.  1800. 18600. 43000.  6800.]]\n",
      "\t [345000.  50000. 320000.  30000. 255000.]\n",
      "цель:\t [345000.  50000. 320000.  30000. 255000.]\n"
     ]
    }
   ],
   "source": [
    "# Искомое, ко-во форматов для каждого из продуктов\n",
    "# может быть только целым\n",
    "x = cv.Variable((m,n))\n",
    "\n",
    "# Условия\n",
    "cond = [\n",
    "    x>=0,              # ко-во публикаций должно быть больше нуля\n",
    "    x.T*np.ones(m)<=q, # ко-во форматов ограничено\n",
    "    x*e>=E,            # эффективность по каждому из продуктов должна быть больше или равна цели\n",
    "    cv.max(x.T*np.ones(m))-cv.min(x.T*np.ones(m)) <=10 # условие не дающе доминировать одному выгодному формату\n",
    "]\n",
    "\n",
    "# проблема, минимизруем суммарный кост\n",
    "prob = cv.Problem(cv.Minimize(cv.sum(x*c)), cond)\n",
    "result = prob.solve()\n",
    "\n",
    "print(\"Итоговый минимальный бюджет: %.1f\" % result)\n",
    "print(\"Выпускаем форматы:\\n\", np.around(x.value))\n",
    "print(\"Форматов на продукт:\\n\", np.around(np.dot(x.value, np.ones(n))))\n",
    "print(\"Ко-во формата:\\t\", np.dot(np.around(x.T.value), np.ones(m)))\n",
    "print(\"\\tлимит:\\t\", q)\n",
    "print(\"Эффективность:\\n\",e*np.around(x.value))\n",
    "print(\"\\t\", np.around(np.dot(x.value*e,np.ones(n))))\n",
    "print(\"цель:\\t\", E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}