Дипломная работа: Решение транспортной задачи линейного программирования в среде MS Excel

Потреб

ности

…

…

В случае превышения запаса над потребностью

>,

вводится фиктивный (n+1)-й пункт назначения с потребностью

=-

и соответствующие тарифы считаются равными нулю: =0 (i=1,…m). Полученная таким образом задача является транспортной задачей, для которой выполняется равенство (5).

Аналогично, при

<,

вводится фиктивный (m+1)-й пункт отправления с запасом груза

=-

и тарифы пологаются равными нулю: =0 (j=1,…m). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Число переменных в транспортной задаче с m пунктами отправления и пунктами назначения равно m n, а число уравнений в системах (2) и (3) равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше-то вырожденным.

Для определения опорного плана существует несколько методов. (Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом). Для определения оптимального воспользуемся средством Поиска решений , реализованного в Excel .

Допустим, что ваша фирма занимается переработкой некоторого сырья на нескольких заводах (потребители-З1,З2,…), расположенных в разных районах города. Сырье поставляется со складов (поставщики-П1,П2,…), расположенных в нескольких городах области. Стоимость сырья одинаковая, однако, перевозка со склада и завода. Потребность заводов в сырье различна, и запасы на каждом складе ограничены. Требуется определить: с какого склада, на какой завод поставлять, сколько сырья для минимизации общих затрат на перевозку.

В нашем примере обозначим заводы З1,З2,З3,З4, а склады П1,П2,П3,П4,П5. Стоимость перевозки измеряется в тенге на тонну груза, а потребность заводов и складские запасы - в тоннах.

ГЛАВА I Задачи линейного программирования

К классу линейного программирования относятся такие задачи однокритериальной оптимизации, в которых переменные являются непрерывными и неотрицательными, целевая функция является линейной функцией своих аргументов, а ограничения могут быть представлены в форме линейных неравенств и равенств. При этом на значения переменных не накладываются никакие дополнительные ограничения, такие как, например, ограничения целочисленности или булевости.

На формирование линейного программирования в качестве самостоятельного направления научно-прикладных исследований наибольшее влияние оказали американские ученые Дж. Данциг, Т. Купмас, Дж. фон Нейман и ученые из России Л.В. Канторович, А.С. Немировский, Л.Г. Хачиян и Д.Б. Юдин. Хотя необходимость создания специальных методов решения неклассических оптимизационных задач осознавалась и раньше, в частности, экономистами и военными специалистами во времена второй мировой войны, только в послевоенное время были разработаны теоретические основы линейного программирования и предложены специальные методы решения соответствующих практических задач.

Собственно термин «линейное программирование» впервые появился в 1951 году в работах Дж. Дангинца и лауреата Нобелевской премии по экономике Т. Купманса. Однако общепризнанно, что первые исследования по линейному программированию, связанные с формулировкой основной задачи, рассмотрением приложений, нахождением критерия оптимальности, экономической интерпретацией, были выполнены в конце 30-х годов ХХ в. в СССР лауреатом Нобелевской премии по экономике Л.В. Канторовичем. По поводу Дж. Данциг в одной из своих монографий отмечает, что «Конторовича Л.В. следует признать первым, кто обнаружил, что широкий класс важнейших производственных задач поддается четкой математической формулировке, которая, по убеждению, дает возможность подходить к задачам с количественной стороны и решать их численными методами…»