{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Simpleksna metoda\n", "\n", "Sledeči program po korakih izvaja simpleksno metodo." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def spremenljivke(n, zacetek=0, predpona=\"x\", ciljna=\"z\"):\n", " \"\"\"\n", " Nastavi želeno število spremenljivk s podano predpono.\n", " \"\"\"\n", " var(\" \".join(\"%s%d\" % (predpona, i) for i in range(zacetek, n+1)))\n", " var(ciljna)\n", "\n", "def izpisi_enacbe(enacbe):\n", " \"\"\"\n", " Uredi in ustrezno izpiše enačbe.\n", " \"\"\"\n", " enacbe.sort(key=lambda e: str(e.lhs()))\n", " for e in enacbe:\n", " r = e.rhs()\n", " c = r.subs([v == 0 for v in r.variables()])\n", " rr = r - c\n", " s = str(rr)\n", " if c == 0:\n", " c = znak = \"\"\n", " elif s[0] == \"-\":\n", " s = s[1:]\n", " znak = \" - \"\n", " else:\n", " znak = \" + \"\n", " print(\"%s == %s%s%s\" % (e.lhs(), c, znak, s))\n", " print(\"\")\n", " return enacbe\n", "\n", "def simpleksna_metoda(enacbe, *spremenljivke):\n", " \"\"\"\n", " Za podani začetni slovar izvaja podane zamenjave baznih in nebaznih spremenljivk.\n", " \"\"\"\n", " enacbe = izpisi_enacbe(enacbe)\n", " for vstopna, izstopna in spremenljivke:\n", " sol = next(e for e in enacbe if e.lhs() == izstopna).solve(vstopna)[0]\n", " enacbe = izpisi_enacbe([sol if e.lhs() == izstopna else e.subs(sol) for e in enacbe])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Funkcija `izpisi_enacbe` je pomožna. S funkcijo `spremenljivke` si pripravimo želeno število spremenljivk, funkcijo `simpleksna_metoda` pa uporabimo tako, da kot prvi argument podamo slovar enačb, za tem pa naštevamo pare vstopnih in izstopnih spremenljivk." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x4 == 5 - 2*x1 - 3*x2 - x3\n", "x5 == 11 - 4*x1 - 3*x2 - x3\n", "x6 == 8 - 3*x1 - 4*x2 - 2*x3\n", "z == 5*x1 + 4*x2 + 3*x3\n", "\n", "x1 == 5/2 - 3/2*x2 - 1/2*x3 - 1/2*x4\n", "x5 == 1 + 3*x2 + x3 + 2*x4\n", "x6 == 1/2 + 1/2*x2 - 1/2*x3 + 3/2*x4\n", "z == 25/2 - 7/2*x2 + 1/2*x3 - 5/2*x4\n", "\n", "x2 == 5/3 - 2/3*x1 - 1/3*x3 - 1/3*x4\n", "x5 == 6 - 2*x1 + x4\n", "x6 == 4/3 - 1/3*x1 - 2/3*x3 + 4/3*x4\n", "z == 20/3 + 7/3*x1 + 5/3*x3 - 4/3*x4\n", "\n" ] } ], "source": [ "spremenljivke(6)\n", "simpleksna_metoda([\n", " x4 == 5 - 2*x1 - 3*x2 - x3,\n", " x5 == 11 - 4*x1 - 3*x2 - x3,\n", " x6 == 8 - 3*x1 - 4*x2 - 2*x3,\n", " z == 5*x1 + 4*x2 + 3*x3\n", "], (x1, x4), (x2, x1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Preverite, ali so vaše rešitve pravilne. Prav tako lahko poizkušate, kaj se zgodi, če izberete napačno vstopno ali izstopno spremenljivko." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Dvofazna metoda\n", "\n", "Pri prvi fazi dvofazne metode ugotavljamo dopustnost problema z n spremenljivkami tako, da rešujemo problem z $n+1$ spremenljivkami. Če je $n = 2$, si povezavo med problemoma lahko tudi predstavljamo." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "nastavitve = {'plot_points': 1000, 'incol': 'lightblue', 'bordercol': 'gray'}" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "spremenljivke(5, 0, ciljna=\"w z\")\n", "omejitve = [\n", " x1 - x2 <= -1,\n", " -x1 - x2 <= -3,\n", " 2*x1 + x2 <= 4\n", "]\n", "pozitivnost = [x1 >= 0, x2 >= 0, x0 >= 0]\n", "meje = [(x1, -0.1, 3), (x2, -0.1, 7), (x0, 0, 3)]" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQsAAAJGCAYAAABMe6B9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGhdJREFUeJzt3X9wVOW9x/HPQhqikkTQLIZFIIUgQiTyq4JgGUVjU36I9+pMdtoay0xn0IgC09tC+087txac+0/tDGUEZ0Idh6QzhQSqAxamJFgRCwg1cmsMyhTKFC1Kk5BpwyWc+4cmEhOS79nds3vO7vs1wyib3T2PTHj7nGfPcxJyHMcRAAxiSKoHACAYiAUAE2IBwIRYADAhFgBMiAUAE2IBwMTTWDiOo7a2NnEpBxB8nsaivb1d+fn5am9v9/IwAJKA0xAAJsQCgAmxAGBCLACYEAsAJq5iMX78eIVCoT6/qqqqvBofAJ/IcvPkw4cPq6urq+f37777rh544AE9+uijCR8YAH9xFYuCgoJev9+wYYMmTJigBQsWJHRQAPwn5jWLS5cu6eWXX9by5csVCoUSOSYAPhRzLOrr6/XPf/5Tjz/+eAKHA8CvQrHeg/PBBx9Udna2fve7313zOW1tbcrPz1c4HFYoFFIkElEkEpEkRaNRRaPR2EYNIOlcrVl0++tf/6p9+/Zpx44dpue3tLQoLy8vlkMB8ImYTkOqq6sVDoe1aNGiRI8HgE+5jsWVK1dUXV2tyspKZWXFNDEBEECuY7Fv3z6dPn1ay5cv92I8AHwq5gVOi+4FztbWVtYsgIBjbwgAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAk6TEoqKiQkuXLlVNTU0yDgfAA1zuDcCE0xAAJsQCgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYEAsAJmxRB2DCFnUAJpyGADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMuJ8FABPuZwHAhNMQACbEAoAJsQBgQiwAmBALACbEAoAJsQBgQiwAmBALACbEAoAJsQBgQiwAmBALACZsUQdgwhZ1ACachgAwIRYATIgFABNiAcCEWAAwIRYATIgFABNiAcDEdSzOnj2rb3/727rpppt0/fXX684779TRo0e9GBsAH8ly8+QLFy5o3rx5uvfee7V7926Fw2F98MEHuvHGG70aHwCfcBWL5557Trfeequqq6t7Hhs/fnyixwTAh1ydhuzatUuzZs3So48+qnA4rOnTp2vLli1ejQ2Aj7iKxYcffqhNmzapuLhYr732mp544gk9/fTT+vWvf+3V+AD4hKtdp9nZ2Zo1a5YOHjzY89jTTz+tw4cP68033+zz/O5dp+FwWKFQSJFIRJFIRJIUjUYVjUYT8J8AIBlcrVkUFhZqypQpvR67/fbbtX379gFf19LSwhZ1IOBcnYbMmzdPzc3NvR57//33NW7cuIQOCoD/uIrF6tWrdejQIf385z/XyZMntW3bNm3evFlVVVVejQ+AT7i+U9Yrr7yidevWqaWlRUVFRVqzZo2+973v9ftc7pQFpA9uqwfAhL0hAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEz4KeoATLjcG4AJpyEATIgFABNiAcCEWAAwIRYATIgFABNiAcCEWAAwIRYATIgFABNiAcCEWAAwIRYATNiiDsCELeoATDgNAWBCLACYEAsAJsQCgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYcD8LACbczwKACachAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEzYog7AhC3qAEw4DQFgQiwAmBALACbEAoAJsQBgQiwAmBALACbEAoCJq1j85Cc/USgU6vXrlltu8WpsAHwky+0Lpk6dqn379vX8fujQoQkdEAB/ch2LrKwsZhNABnK9ZtHS0qLRo0erqKhIFRUV+vDDD70YFwCfcRWLu+66Sy+99JJee+01bdmyRefOndPdd9+tTz75xKvxAfCJuHaddnR0aMKECfrBD36gNWvW9Pl6967TcDisUCikSCSiSCQiSYpGo4pGo7GPHEBSuV6zuNoNN9ygO+64Qy0tLQM+r6WlhS3qQMDFdZ1FZ2en/vKXv6iwsDBR4wHgU65i8f3vf1+NjY06deqU3nrrLT3yyCNqa2tTZWWlV+MD4BOuTkP+9re/KRqN6vz58yooKNCcOXN06NAhjRs3zqvxAfAJbqsHwIS9IQBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBM+CnqAEy43BuACachAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQAT7mcBwIT7WQAw4TQEgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYEAsAJsQCgAmxAGBCLACYEAsAJsQCgAlb1AGYsEUdgAmnIQBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBM2KIOwIQt6gBMOA0BYEIsAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKASVyx2LBhg0KhkFatWpWo8QDwqZhjcfjwYb3wwguaNm1aIscDwKdiisXFixf1rW99S1u2bNGIESMSPSYAPhRTLKqqqrRo0SLdf//9iR4PAJ/KcvuC2tpavf322zp8+LAX4wHgU65icebMGT3zzDPau3evcnJyBn3+R+c/kSSNHz9e2dnZikQiikQikqRoNKpoNBrDkAGkgqst6vX19Xr44Yc1dOjQnse6uroUCoU0ZMgQdXZ29vran44d010zZmjt2rX675/9TFlXfQ1AsLiaWSxcuFBNTU29Hvvud7+ryZMn64c//GGvUEiSc+WLfz967M+6a9aM2EcKIKVcxSI3N1clJSW9Hrvhhht000039Xn8agUFBfrTm29o5vRSZhdAQHl8BednZzgT75ylTz/9VEeP/dnbwwHwjOtPQ76soaFh0Of83w35mlg8idkFEGBJ2xsSLpnB7AIIsKTFon1YniZO+mx2cbmrK1mHBZAgSd11Gp7K7AIIqqTGgtkFEFzJicVVl30xuwCCKek3v2F2AQRTSu6UxewCCJ6UxILZBRA8KbsHZ/fs4six46kaAgAXkhKLDf/1jNY/UanXX6nreax7dnH4zYPMLoAAiPtyb4u1//O8QiPCfR4PT52hk3W17EgFAiClPwqAtQsgOFL+c0P4ZAQIhpTHgtkFEAwpj4XE7AIIAl/EgtkF4H++iIXEdReA3/kmFlx3Afibb2IhsXYB+JmvYsHaBeBfvoqFxOwC8CvfxYLZBeBPvouFxCcjgB/5MhZ8MgL4jy9jIbF2AfhNyu5nMRjWLgB/Sen9LAbD/S4A//DtaYjE7ALwE1/HQmLtAvAL38eC2QXgD76PhcR1F4AfBCIWXHcBpF4gYiExuwBSLTCxYHYBpFZgYiExuwBSKVCxYHYBpI6nsXA8eE+uuwBSI1AzC4nrLoBUCVwsJGYXQCoEMhbMLoDk8+0W9cEwuwCSy9db1Ady9exi5vRSZQ0dmtD3B9BbIE9DunHdBZA8gY4F110AyRPoWEjMLoBkCXwsmF0AyRH4WEh8MgIkQ1rEgusuAO+lRSwk1i4Ar6VNLFi7ALyVNrGQWLsAvJRWsWDtAvBOWsVCYu0C8EraxYK1C8AbaRcLibULwAuB3aI+ENYugMQL7Bb1wfAT2IHESsvTEInZBZBoaRsLiU9GgERK61jwyQiQOGkdC4lPRoBESftYsHYBJEbax0JidgEkQkbEgtkFEL+MiIXEJyNAvFzFYtOmTZo2bZry8vKUl5enuXPnavfu3V6NLaH4ZASIj6tYjBkzRhs2bNDRo0d15MgR3XfffXrooYd04sQJr8aXUKxdALFzFYslS5bom9/8poqLizVp0iQ9++yzGj58uA4dOtT/C5zP/xmKc5QJwtoFELuY1yy6urpUW1urjo4OzZ07t9/nOD218A9mF0BsXMeiqalJw4cP17Bhw7RixQrV1dVpypQpXozNE8wugNiEHMdx9b//S5cu6fTp02ptbdVvf/tbvfjii2psbOw3GO+1fKDbJ01UXl6eQl/J1shRt+imUYWSpPmLlumexQ8n5r/CpdzONh2sq9U3Fi1hRypg5DoWX3b//fdrwoQJeuGFF/p8ra2tTfn5+frRj36kaaV3KvuOu+UM8centf96u0Gfnj+vJ558kp/ADhjE/TfXcRx1dnYO+JwHFy3W+83v6VLTQYWuXIn3kAnB2gXgjqub36xbt07l5eUaO3as2tvbVVtbq4aGBu3Zs2fA191ZMlXDh+fq1Z11miT5YoZx9drFzOmlzC6AQbj6G/vxxx/rscce02233aaFCxfqrbfe0p49e/TAAw8M+toZ00q06KFlvpphMLsA7OJesxhI95pFa2ur8vLyJElvv9OkV3fWa9Jtk30xw2DtArBJ+t/UGdPu8NUMg9kFYJOS/637KRhcdwHYpOwcwE/BYEcqMLiULhj4JRjsSAUGl/IrpPwSDNYugIGlPBaSP4LB2gUwMF/EQvJHMFi7AK7NN7GQUh8M1i6Aa/NVLKTUB4O1C6B/SYlFRUWFli5dqpqaGtPzUxkM1i6A/iX9cm83UnVpOPe7APry3WnI1VI1w2B2AfTl61hIqQsGaxdAb76PhZSaYDC7AHoLRCyk1ASD2QXwhcDEQkp+MJhdAF8IVCyk7mA8nLRgMLsAPhO4WEjJvUUfswvgM4GMhZTcUxJmF0CAYyEl75SE2QUQ8FhIyTslYXaBTBf4WEjJmWEwu0CmS4tYSMmZYTC7QCZLm1hI3i96MrtAJkurWEjen5Iwu0Cm8uX9LOLl5SkJswtkKl/fzyJeXt0Pg/tdIBOl3WnI1bxaw2B2gUyU1rGQvAsGaxfINGkfC8mbYDC7QKbJiFhI3gSD2QUyScbEQkp8MJhdIJNkVCykxAeDn2KGTJFxsZASGwx+ihkyRUbGQkrslZ6sXSATZGwspO4rPeMPRvuwPE0sZu0C6S2jYyEl7tLwcAlrF0hvGR8LKTGnJKxdIN0Ri88l4pSEtQukM2JxlXiDwXUXSGdpuUU9HvEGg+sukK7Seot6POLZ3v6vtxv06fnzeuLJJ5U1dKiHowSSh9OQa4hn0ZO1C6QjYjGAWE9JWLtAOiIWg4g1GMwukG6IhUEsweCqTqQbYmEUy5We3Vd1MrtAOiAWLrjdrcraBdIJsXDJ7ackrF0gXRCLGFx9StLZ9MaAwWB2gXRBLGLUfUrS0tw86AyD2QXSAbGIg3UNg9kF0gGxiJN1DYPZBYKOWCSA5WNVrrtA0BGLBLHMMLjuAkHGFvUEGuxKT9YuEGRsUffA2++8q1d31vW7vZ2fwI6g4jTEAwPNMFi7QFARC48MFAzWLhBExMJD1woGaxcIImLhsWsFo+e6i+PMLhAMxCIJ+gtGz9rFQWYXCAZikSRXB6N78xlrFwgSYpFE3cHo3nx28SvD+WQEgUEskuzLM4xRU6d/vnbxTqqHBgzIVSzWr1+v2bNnKzc3V+FwWMuWLVNzc7NXY0tbV88wzje/o69+dQKzC/ieq1g0NjaqqqpKhw4d0t69e3X58mWVlZWpo6PDq/GlrauDceHCp/r0k0/4ZAS+Ftfl3v/4xz8UDofV2Nior3/9632+nqmXe7txrOldvVJfpytXrmjEiBGqqqrSUH6KGXworjWL1tZWSdLIkSMTMphMNP2OEi1e9h+SpAsXLugIswv4VMyxcBxHq1ev1vz581VSUpLIMWWc6XdM1dL/fESS9L9NLHTCn7JifeFTTz2lpqYm/fGPfxz0ucXFxQqFQopEIopEIpKkaDSqaDQa6+HTzvSSqRpx4426/rrrUz0UoF8xrVmsXLlS9fX1OnDggIqKiq75PNYsgPThambhOI5Wrlypuro6NTQ0DBgKAOnFVSyqqqq0bds27dy5U7m5uTp37pwkKT8/X9ddd50nAwTgD65OQ0KhUL+PV1dX6/HHH+/zOKchQPpwfRoCIDOxNwSACbEAYEIsAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKACbEAYJKUWFRUVGjp0qWqqalJxuEAeCCue3AOho1kQPrgNASACbEAYEIsAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKACVvUAZiwRR2ACachAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEzYog7AhC3qAEw4DQFgQiwAmBALACbEAoAJsQBgQiwAmBALACbEAoAJsQBgQiwAmBALACbEAoAJsQBgwhZ1ACZsUQdgwmkIABNiAcCEWAAwIRYATIgFABNiAcCEWAAwIRYATFzH4sCBA1qyZIlGjx6tUCik+vp6L8YFwGdcx6Kjo0OlpaXauHGjF+MB4FNZbl9QXl6u8vJyL8YCwMdYswBgQiwAmLg+DYlFcXGxQqGQIpGIIpGIJCkajSoajSbj8AASICmxaGlpYYs6EHCchgAwcT2zuHjxok6ePNnz+1OnTun48eMaOXKkxo4dm9DBAfAP13fKamho0L333tvn8crKSm3durXXY9wpC0gf3FYPgAlrFgBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAk6TEoqKiQkuXLlVNTU0yDgfAA+wNAWDCaQgAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAE2IBwIRYADAhFgBMiAUAE7aoAzBhizoAE05DAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKACbEAYEIsAJgQCwAmxAKACbEAYEIsAJiwRR2ACVvUAZhwGgLAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhFgAMCEWAEyIBQATYgHAhC3qAEzYog7AhNMQACbEAoAJsQBgQiwAmBALACbEAoAJsQBgkrGx8OsFYn4dl+TfsTEud2IdF7HwGb+OS/Lv2BiXO8QCgKcSEot4CjrYawf6ejyvPXv2LONy+fWBxsa40mNcAyEWjMv89SB+8zMud+MaSJabJzuOo/b29j6PX758WW1tbX0e736sv68N9lrL1+N5reM4jMvl1wcaG+MK9rhyc3MVCoWu+RrJ5a7T7l2kANKLZWe4q1hca2ZxLW1tbbr11lt15swZtqgDPmaZWbg6DQmFQjH9pc/LyyMWQMDx0SkAE2IBwIRYADAhFgBMiAUAk7SNxa9+9SsVFRUpJydHM2fO1Ouvv37N527dulWhUKjPr3//+99JG++BAwe0ZMkSjR49WqFQSPX19b49dkNDQ79/Xu+9915Sxrt+/XrNnj1bubm5CofDWrZsmZqbm5Ny7FiPn8rvsU2bNmnatGk9n0rOnTtXu3fvdv0+aRmL3/zmN1q1apV+/OMf69ixY7rnnntUXl6u06dPX/M1eXl5+vvf/97rV05OTtLG3NHRodLSUm3cuDFpx4z32M3Nzb3+vIqLiz0aYW+NjY2qqqrSoUOHtHfvXl2+fFllZWXq6Ojw9fFT9T02ZswYbdiwQUePHtWRI0d033336aGHHtKJEyfcvZHjodbWVkeS09ra6uVh+vja177mrFixotdjkydPdtauXdvv86urq538/PxkDM1EklNXV+fbY+/fv9+R5Fy4cCFJoxrYxx9/7EhyGhsbfXt8v32PjRgxwnnxxRddvSbtZhaXLl3S0aNHVVZW1uvxsrIyHTx48Jqvu3jxosaNG6cxY8Zo8eLFOnbsmNdDDbzp06ersLBQCxcu1P79+1M2jtbWVknSyJEjfX18P3yPdXV1qba2Vh0dHZo7d66r16ZdLM6fP6+uri6NGjWq1+OjRo3SuXPn+n3N5MmTtXXrVu3atUs1NTXKycnRvHnz1NLSkowhB05hYaE2b96s7du3a8eOHbrtttu0cOHCAdeFvOI4jlavXq358+erpKTEt8dP9fdYU1OThg8frmHDhmnFihWqq6vTlClT3L2JJ3Ocz6XiNOTs2bOOJOeNN97o9fizzz7rTJo0yfQeXV1dTmlpqbNy5Uovhjgo+fw0pD+LFy92lixZ4sGIBvbkk08648aNc86cOZP0Y8dz/GR/j3V2djotLS3OkSNHnLVr1zo333yzc+LECVfvkXYzi5tvvllDhw7VRx991Ovxjz76SLfccovpPYYMGaLZs2czs3Bhzpw5Sf/zWrlypXbt2qX9+/drzJgxST12vMdP9vdYdna2Jk6cqJkzZ2r9+vUqLS3V888/7+o90i4W2dnZmjlzpvbu3dvr8b179+ruu+82vYfjODp+/LgKCwu9GGJaOnbsWNL+vBzH0VNPPaUdO3boD3/4g4qKipJy3EQeP9XfY47jqLOz09VrXO06jVVFRYWysrIUjUYVjUY9P96aNWv0ne98R7NmzdLcuXO1efNmnT59WitWrJAkPfbYY4pEIlq/fr0k6ac//anmzJmj4uJitbW16Ze//KWOHz+e1I8xL168qJMnT/b8/tSpUzp+/LhGjhypsWPHpvTY69at09mzZ/XSSy9Jkn7xi19o/Pjxmjp1qi5duqSXX35Z27dv1/bt2z0dZ7eqqipt27ZNO3fuVG5ubs9aVH5+vq677jpfHN9P32Pr1q1TeXm5xo4dq/b2dtXW1qqhoUF79uxx90aJPzv6Qqo+OnUcx9m4caMzbtw4Jzs725kxY0avj7UWLFjgVFZW9vx+1apVztixY53s7GynoKDAKSsrcw4ePJjU8XZ/HPnlX1ePM1XHrqysdBYsWNDz/Oeee86ZOHGik5OT44wYMcKZP3++8+qrr3o+zm79jVWSU11d7Zvj++l7bPny5T1/FwoKCpyFCxc6v//9712/j6ub37jVfWcty114APhb2q1ZAPCGpzML5/Pb8Flu2QXA3zyNBYD0wWkIABNiAcCEWAAwIRYATIgFABNiAcCEWAAwIRYATP4f4teFBMQhbxkAAAAASUVORK5CYII=\n", "text/plain": [ "Graphics object consisting of 2 graphics primitives" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "region_plot(omejitve + pozitivnost[:2], *meje[:2], **nastavitve)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n" ], "text/plain": [ "Graphics3d Object" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "implicit_plot3d(max_symbolic(*([e.lhs() - e.rhs() - x0 for e in omejitve] +\n", " [-e.lhs() for e in pozitivnost])), smooth=False, *meje)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "w == -x0\n", "x3 == -1 + x0 - x1 + x2\n", "x4 == -3 + x0 + x1 + x2\n", "x5 == 4 + x0 - 2*x1 - x2\n", "z == x1 + x2\n", "\n", "w == -3 + x1 + x2 - x4\n", "x0 == 3 - x1 - x2 + x4\n", "x3 == 2 - 2*x1 + x4\n", "x5 == 7 - 3*x1 - 2*x2 + x4\n", "z == x1 + x2\n", "\n", "w == -x0\n", "x2 == 3 - x0 - x1 + x4\n", "x3 == 2 - 2*x1 + x4\n", "x5 == 1 + 2*x0 - x1 - x4\n", "z == 3 - x0 + x4\n", "\n", "w == -x0\n", "x1 == 1 - 1/2*x3 + 1/2*x4\n", "x2 == 2 - x0 + 1/2*x3 + 1/2*x4\n", "x5 == 2*x0 + 1/2*x3 - 3/2*x4\n", "z == 3 - x0 + x4\n", "\n", "w == -x0\n", "x1 == 1 + 2/3*x0 - 1/3*x3 - 1/3*x5\n", "x2 == 2 - 1/3*x0 + 2/3*x3 - 1/3*x5\n", "x4 == 4/3*x0 + 1/3*x3 - 2/3*x5\n", "z == 3 + 1/3*x0 + 1/3*x3 - 2/3*x5\n", "\n" ] } ], "source": [ "simpleksna_metoda([x == e.rhs() + x0 - e.lhs() for x, e in zip([x3, x4, x5], omejitve)] +\n", " [w == -x0, z == x1 + x2],\n", " (x0, x4), (x2, x0), (x1, x3), (x4, x5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Za katere vrednosti parametra $a$ je sledeči problem dopusten? Pomagajte si z `@interact`.\n", "\n", "\\begin{align*}\n", "\\min &\\ x + y \\\\\n", "x + y &\\ge a \\\\\n", "2x + y &\\ge 1 \\\\\n", "x + 2y &\\le 1 \\\\\n", "x, y &\\ge 0\n", "\\end{align*}" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "03eb26105af242a291b8edbb415cd7d2", "version_major": 2, "version_minor": 0 }, "text/plain": [ "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIF8gYXQgMHg4NjgyYTZiYz4gd2l0aCAyIHdpZGdldHMKICBhOiBUcmFuc2Zvcm1GbG9hdFNsaWRlcih2YWx1ZT0wLjAsIGRlc2NyaXB0aW/igKY=\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "x, y = var(\"x y\")\n", "meje = [(x, 0, 2), (y, 0, 2)]\n", "\n", "@interact\n", "def _(a=slider(0, 2, default=0, step_size=0.01, label='$a$'),\n", " k=slider(0, 2, default=1, step_size=0.01, label='$k$')):\n", " show(region_plot([x + y >= a, 2*x + y >= 1, x + 2*y <= 1], *meje, **nastavitve) +\n", " implicit_plot(x + y - k, *meje))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Končnost simpleksne metode\n", "\n", "Pri izbiri vstopnih in izstopnih spremenljivk upoštevaj naslednji pravili:\n", "\n", "1. Vstopna spremenljivka naj bo tista, ki ima največji koeficient v vrstici, ki ustreza funkcionalu $z$.\n", "2. Če imamo več kandidatov za izstopno spremenljivko, izberemo prvo po leksikografski ureditvi ($x1 < x2 < x3 < x4 < x5 < x6 < x7$).\n", "\n", "Kaj opaziš?" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x5 == -1/2*x1 + 11/2*x2 + 5/2*x3 - 9*x4\n", "x6 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x4\n", "x7 == 1 - x1\n", "z == 10*x1 - 57*x2 - 9*x3 - 24*x4\n", "\n", "x1 == 11*x2 + 5*x3 - 18*x4 - 2*x5\n", "x6 == -4*x2 - 2*x3 + 8*x4 + x5\n", "x7 == 1 - 11*x2 - 5*x3 + 18*x4 + 2*x5\n", "z == 53*x2 + 41*x3 - 204*x4 - 20*x5\n", "\n", "x1 == -1/2*x3 + 4*x4 + 3/4*x5 - 11/4*x6\n", "x2 == -1/2*x3 + 2*x4 + 1/4*x5 - 1/4*x6\n", "x7 == 1 + 1/2*x3 - 4*x4 - 3/4*x5 + 11/4*x6\n", "z == 29/2*x3 - 98*x4 - 27/4*x5 - 53/4*x6\n", "\n", "x2 == x1 - 2*x4 - 1/2*x5 + 5/2*x6\n", "x3 == -2*x1 + 8*x4 + 3/2*x5 - 11/2*x6\n", "x7 == 1 - x1\n", "z == -29*x1 + 18*x4 + 15*x5 - 93*x6\n", "\n", "x3 == 2*x1 - 4*x2 - 1/2*x5 + 9/2*x6\n", "x4 == 1/2*x1 - 1/2*x2 - 1/4*x5 + 5/4*x6\n", "x7 == 1 - x1\n", "z == -20*x1 - 9*x2 + 21/2*x5 - 141/2*x6\n", "\n", "x4 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x6\n", "x5 == 4*x1 - 8*x2 - 2*x3 + 9*x6\n", "x7 == 1 - x1\n", "z == 22*x1 - 93*x2 - 21*x3 + 24*x6\n", "\n", "x1 == 3*x2 + x3 - 2*x4 - 2*x6\n", "x5 == 4*x2 + 2*x3 - 8*x4 + x6\n", "x7 == 1 - 3*x2 - x3 + 2*x4 + 2*x6\n", "z == -27*x2 + x3 - 44*x4 - 20*x6\n", "\n", "x1 == 1 - x7\n", "x3 == 1 - 3*x2 + 2*x4 + 2*x6 - x7\n", "x5 == 2 - 2*x2 - 4*x4 + 5*x6 - 2*x7\n", "z == 1 - 30*x2 - 42*x4 - 18*x6 - x7\n", "\n" ] } ], "source": [ "spremenljivke(7)\n", "simpleksna_metoda([\n", " x5 == -1/2*x1 + 11/2*x2 + 5/2*x3 - 9*x4,\n", " x6 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x4,\n", " x7 == 1 - x1,\n", " z == 10*x1 - 57*x2 - 9*x3 - 24*x4\n", "], (x1, x5), (x2, x6), (x3, x1), (x4, x2), (x5, x3), (x1, x4), (x3, x7))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Zgornji linearni program reši še s pomočjo Blandovega pravila (tako vstopne kot izstopne spremenljivke izbiraš glede na leksikografsko ureditev)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Celoštevilsko linearno programiranje\n", "\n", "* Poiščite optimalno rešitev sledečega problema:\n", "\n", "\\begin{align*}\n", "\\max \\ 3x_1 + 4x_2 \\\\\n", "2x_1 + x_2 &\\le 6 \\\\\n", "2x_1 + 3x_2 &\\le 9 \\\\\n", "x_1, x_2 &\\ge 0\n", "\\end{align*}\n", "\n", "* Nato poiščite še optimalno rešitev v primeru, da sta $x_1$ in $x_2$ celoštevilski spremenljivki.\n", "\n", "* Nazadnje poiščite isto optimalno rešitev še na roke, torej tako, da ne izkoristite tega, da zna Sage reševati tudi celoštevilske probleme." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "def problem(integer=False):\n", " p = MixedIntegerLinearProgram(maximization=True)\n", " x = p.new_variable(integer=integer)\n", " p.set_objective(3*x[1] + 4*x[2])\n", " p.add_constraint(2*x[1] + x[2] <= 6)\n", " p.add_constraint(2*x[1] + 3*x[2] <= 9)\n", " p.add_constraint(x[1] >= 0)\n", " p.add_constraint(x[2] >= 0)\n", " opt = p.solve()\n", " return (opt, p.get_values(x))" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(12.75, {1: 2.2499999999999996, 2: 1.5000000000000004})" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Linearni program\n", "problem(integer=False)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(12.0, {1: 0.0, 2: 3.0})" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Celoštevilski linearni program\n", "problem(integer=True)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "ed799fbc94484b33bf659c8b201a1d1b", "version_major": 2, "version_minor": 0 }, "text/plain": [ "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIF8gYXQgMHg4MDdlNWI4Yz4gd2l0aCAxIHdpZGdldAogIGs6IFRyYW5zZm9ybUZsb2F0U2xpZGVyKHZhbHVlPTAuMCwgZGVzY3JpcHRpb27igKY=\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "spremenljivke(2)\n", "meje = [(x1, 0, 3), (x2, 0, 3)]\n", "tocke = sum(circle((i, j), 0.02, fill=True, rgbcolor='red') for i in range(meje[0][1], meje[0][2]+1)\n", " for j in range(meje[1][1], meje[1][2]+1))\n", "\n", "@interact\n", "def _(k=slider(0, 15, default=0, step_size=0.01, label='$k$')):\n", " show(region_plot([2*x1 + x2 <= 6, 2*x1 + 3*x2 <=9], *meje, **nastavitve) + tocke +\n", " implicit_plot(3*x1 + 4*x2 - k, *meje))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 0-1 nahrbtnik\n", "\n", "Rešite problem 0-1 nahrbtnika z volumnom 10 in naslednjimi predmeti:\n", "\n", "| volumen | cena |\n", "| ------- | ---- |\n", "| 2 | 30 |\n", "| 4 | 60 |\n", "| 6 | 50 |\n", "| 3 | 40 |" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Volumen 1, rešitev {}, cena 0\n", "Volumen 2, rešitev {0}, cena 30\n", "Volumen 3, rešitev {3}, cena 40\n", "Volumen 4, rešitev {1}, cena 60\n", "Volumen 5, rešitev {0, 3}, cena 70\n", "Volumen 6, rešitev {0, 1}, cena 90\n", "Volumen 7, rešitev {1, 3}, cena 100\n", "Volumen 8, rešitev {1, 3}, cena 100\n", "Volumen 9, rešitev {0, 1, 3}, cena 130\n", "Volumen 10, rešitev {0, 1, 3}, cena 130\n" ] } ], "source": [ "V = 10\n", "v = [2, 4, 6, 3]\n", "c = [30, 60, 50, 40]\n", "\n", "resitev = [Set()] # seznam optimalnih rešitev pri dani omejitvi volumna\n", "cena = [0] # seznam cen optimalnih rešitev pri dani omejitvi volumna\n", "for i in range(1, V+1):\n", " r = resitev[-1]\n", " t = cena[-1]\n", " for j, (vj, cj) in enumerate(zip(v, c)):\n", " if vj > i or j in resitev[i - vj]:\n", " continue\n", " nova = cena[i - vj] + cj\n", " if nova > t:\n", " r = resitev[i - vj] | Set([j])\n", " t = nova\n", " resitev.append(r)\n", " cena.append(t)\n", " print(\"Volumen %d, rešitev %s, cena %d\" % (i, r, t))" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.3", "language": "", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 2 }