.. _sphx_glr_api_gallery_optimization_linear_programming:

Linear programming
---------------------

Dantzig's simplex method and branch and bound for integer programs.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Maximize the profit 3x + 5y from two products subject to x + 2y \leq 40 labor-hours and 2x + y \leq 30 units of material. The simplex method starts at the vertex (0, 0) of the feasible polygon and pivots along its edges to an adjacent vertex with a higher profit, until no neighbour improves. The tableau pivots are written out below, and the answer is checked against linear_program.">

.. only:: html

  .. image:: /api/gallery/optimization/linear_programming/images/thumb/sphx_glr_plot_01_simplex_method_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/linear_programming/plot_01_simplex_method`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Dantzig's simplex method: walking the vertices of a production LP</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="The LP relaxation of an integer program can have a fractional optimum that rounding does not repair. Branch and bound (Land and Doig, 1960) finds the true integer optimum; here it is at a different vertex from the relaxation&#x27;s.">

.. only:: html

  .. image:: /api/gallery/optimization/linear_programming/images/thumb/sphx_glr_plot_02_branch_and_bound_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/linear_programming/plot_02_branch_and_bound`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Branch and bound: integer versus relaxed optimum</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/optimization/linear_programming/plot_01_simplex_method
   /api/gallery/optimization/linear_programming/plot_02_branch_and_bound