Основываясь на условии баланса запасов и  потребностей (1), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m + n -1, поэтому всегда останутся свободными (нулевыми) m*n - (m + n -1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (а_i^(q)= b_j^(q).). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

     Особенностью  допустимого плана, построенного методом  северо-западного угла, является то, что целевая функция на нем  принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения с_ij. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

  Метод наименьшей стоимости

     В методе северо-западного угла на каждом шаге потребности первого из оставшихся пунктов назначения удовлетворялись за счет запасов первого из оставшихся пунктов назначения. Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на планы перевозок, а именно: на каждом шаге следует выбирать  какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбрать любую из них), и рассмотреть пункты отправления и назначения, соответствующие выбранной клетке. Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом. Следует отметить, что этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла. Поэтому наиболее целесообразно опорный план транспортной задачи находить методом минимальных затрат.

     Сущность  метода состоит в следующем. Просматриваются тарифы транспортной таблицы, и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m + n – 1 загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 – « нуль-загрузка», условно считая такую клетку занятой, однако число 0 записывается в такие клетки, которые не образуют циклов с ранее занятыми клетками.

    Опорный план, составленный методом наименьшей стоимости, обычно более близок к оптимальному решению.

  Метод аппроксимации Фогеля

     При определении оптимального плана  транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой данная разность соответствует, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом.

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

    Если  клеток с минимальным тарифом  также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

     Таким образом, несмотря на то что, метод аппроксимации Фогеля является самым сложным, его применение позволяет получить либо опорный план, либо сам оптимальный план.

Решение открытой транспортной задачи

    В  предыдущих  случаях  мы  рассматривали  только  такую  задачу  о  перевозках, в  которой  сумма  запасов  ровна  сумме  заявок:

                    (где i=1,...,m; j=1,...,n)  (4)

Это  классическая  транспортная  задача, иначе называемая, закрытой транспортной  задачей. Встречаются  такие   варианты  транспортной  задачи,  где условие  (4)  нарушено. В  этих  случаях  говорят  об открытой транспортной  задаче.

    Баланс  транспортной  задачи  может  нарушаться  в  2-ух  направлениях:

      1. Сумма  запасов  в  пунктах   отправления  превышает  сумму   поданных  заявок

          ( где i=1,...,m ; j=1,...,n );

      2. Сумма  поданных  заявок  превышает   наличные  запасы

              (где i=1,...,m; j=1,...,n);

    Условимся  первый  случай  называть “Транспортной  задачей  с  избытком  запасов“, а  второй — “Транспортной  задачей  с  избытком  заявок”.

    Рассмотрим  последовательно  эти  два  случая:

    Транспортная  задача   с  избытком  запасов.

    В  пунктах  A₁, A₂, ... , A_m  имеются запасы груза a₁, a₂, ... , a_m;  пункты  B₁, B₂, ... , B_n   подали  заявки  b₁, b₂, ... , b_n, причём

 å а_i > å b_j ( где i=1..m ; j=1..n ).

    Требуется  найти  такой  план  перевозок (X), при котором все заявки  будут  выполнены, а  общая  стоимость  перевозок  минимальна.

    Поставленная  задача   может  быть  решена, например, обычным  симплекс-методом. Однако задачу  можно  решить  проще, если  искусственным  приёмом  свести  её  к  ранее  рассмотренной  транспортной  задаче  с  правильным  балансом.  Для  этого, сверх  имеющихся  n  пунктов назначения  В₁, B₂, ... , B_n, введём ещё   один, фиктивный, пункт назначения   B_n+1, которому   припишем фиктивную заявку, равную избытку запасов над заявками 

                    (где i=1,...,m; j=1,...,n) ,

    а  стоимость  перевозок  из  всех  пунктов  отправления  в  фиктивный  пункт  назначения  b_n+1  будем считать равным  нулю. Введением фиктивного  пункта  назначения  B _n+1  с его заявкой b _n+1  мы  сравняли  баланс транспортной задачи и теперь его можно решать как обычную  закрытую транспортную  задачу.

    Транспортная  задача  с  избытком  заявок .

    Эту задачу можно свести к обычной  закрытой транспортной задаче,  если  ввести  фиктивный пункт отправления A_m+1 с запасом a_m+1 равным недостающему запасу и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равным  нулю.

 

  Тестирование программы

    Имеется  m  пунктов отправления   А₁, А₂ , ..., А_{m ,}   в  которых  сосредоточены  запасы  каких-то  однородных  грузов  в  количестве  соответственно  а₁, а₂, ... , а_m  единиц. Имеется   n  пунктов назначения  В₁ , В₂ , ... , В_n  подавшие  заявки  соответственно  на  b₁ , b₂ , ... , b_n единиц  груза. Известны  стоимости С_i,j   перевозки  единицы   груза    от  каждого  пункта  отправления  А_i   до  каждого   пункта  назначения  В_j . Все числа С_i,j, образующие   прямоугольную таблицу заданы.

    Требуется составить такой план перевозок (откуда, куда и сколько единиц  поставить), чтобы все заявки  были  выполнены, а общая стоимость всех  перевозок  была  минимальна.

    Данная  программа предназначена для нахождения оптимального плана транспортной задачи. При этом рассматриваются три различных метода нахождения опорного плана поставок:

1. Метод Северо-Западного угла.
2. Метод минимальных затрат.
3. Метод аппроксимаций Фогеля.

    Рассмотрим решение стандартной задачи.

    При запуске программы на экране появляется  следующее окно: 

 

    Пользователь  может либо вручную ввести необходимые  данные либо загрузить сохраненные ранее (кнопка «Загрузить»). После загрузки данных пользователь может внести свои изменения в них.

    Пользователю  предоставляется возможность сохранить  исходные данные в файл (кнопка «Сохранить»).

    В случае если пользователю необходимо изменить исходные данные, то можно  очистить все поля (кнопка «Очистить»).

    После введения данных пользователь должен выбрать метод построения опорного плана и нажать на кнопку «Решить» под нужным методом.

    После чего появится новая форма, в которой будут показаны: исходные данные, матрица оценок Sij при нахождении оптимального плана при каждом шаге, матрица изменения плана поставок Xij при каждом шаге. 

 

    Хотелось  бы отметить, что путем подсчета количества итераций, необходимых для приведения опорного плана к оптимальному, удалось выяснить какой из представленных выше методов является в большинстве случаев наилучшим.

    Таким методом стал метод аппроксимаций Фогеля. Он выдавал наиболее близкий к оптимальному плану результат и, несмотря на то, что этот метод так же является самым сложным в вычислении, именно его можно рекомендовать к применению для вычисления опорного плана транспортной задачи. 

 

Заключение

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

      Алгоритм  и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи.

      Таким образом, важность решения данной задачи для экономики несомненна.

      В ходе выполнения курсовой работы были изучены: суть и общая математическая постановка транспортной задачи, сравнены методы нахождения первоначального распределения, разработано приложение в среде Delphi. На основе тестирования программы был сделан вывод о том, что наилучшим методом нахождения первоначального распределения является метод аппроксимаций Фогеля, так как он позволяет найти опорный план, наиболее близкий к оптимальному, а иногда и сам оптимальный план.

      Выбран  именно этот язык программирования, так  как Delphi, как никакая другая система программирования, удовлетворяет требованиям быстроты, простоты, эффективности, надежности. Действительно, приложения с помощью Delphi разрабатываются быстро, причем взаимодействие разработчика с интерактивной средой Delphi не вызывает внутреннего отторжения, а наоборот, оставляет ощущение комфорта. Эти приложения надежны и при эксплуатации обладают предсказуемым поведением.

      Программа имеет удобный и интуитивно понятный интерфейс.

 

Список  литературы

1. Кузнецов  А.В., Сакович В.А., Холод Н.И. ”Высшая  математика. Математическое программирование ”, Минск, Вышэйшая школа, 2001г.
2. Акулич И.Л. «Математическое программирование в примерах и задачах», Высшая школа, 1984г.
3. Ермаков В.И. “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
4. Канторович Л.В., Горстко А.Б. «Математическое оптимальное программирование  в экономике», Знание, 1968г.
5. Канторович Л.В., Горстко А.Б. «Оптимальные решения в экономике», Наука, 1972г.
6. Конюховский П.В. «Математические методы исследования операций в экономике», Питер, 2000г.
7. Кузнецов А.В., Новикова Г.И., Холод И.И. – «Сборник задач по математическому программированию». Минск, Высшая школа, 1985г.
8. Справочная система Delphi 7.
9. Ресурсы сети Internet.