Содержание 

 

 

Введение

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

     Остановимся на некоторых характерных особенностях транспортных задач. Прежде всего — проблема оптимальности. Что значит транспорт работает хорошо? Один из основных показателей работы транспорта — грузооборот — измеряется в тонно-километрах. Получается, если транспортная организация «выполнила» много тонно-километров, то она работала хорошо. А ведь оптимальная система перевозок, несомненно, приносящая пользу государству, ведет к сокращению этого показателя и тем самым ухудшает показатели работы организации. Можно, конечно, измерять качество работы по затратам при существующих тарифах и пытаться, планируя перевозки, минимизировать эти затраты. Но тогда сразу же возникает вопрос о правильном, научно обоснованном исчислении тарифов.

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

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

Кроме того, к задачам транспортного  типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

     Таким образом, тема курсовой работы является актуальной.

     Целью выполнения курсовой работы является разработка приложения для решения  транспортной задачи линейного программирования и сравнения методов нахождения первоначального распределения. Достижение указанной цели потребовало постановки и решения следующих задач:

1. Изучить суть и общую математическую постановку транспортной задачи.
2. Изучить и сравнить методы нахождения первоначального распределения.
3. Разработать приложение, которое позволяло бы решать вышеуказанные задачи.

 

Транспортная  задача: постановка и математическая модель

 

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

      Пусть имеются пункты производства A₁, А₂, ..,, А_n с объемами производства в единицу времени, равными соответственно а₁, а₂, ..., а_n, и пункты потребления B₁, В₂, ..., В_m с объемами потребления, равными b₁, Ь₂, ..., b_m соответственно. Будем предполагать, что производство и потребление сбалансированы — сумма объемов производства равна сумме объемов потребления, т. е.

             

     Предполагаются известными величины С_ij — затраты по перевозке единицы продукта из i-го пункта производства в j-й пункт потребления. Они могут быть выражены в стоимостной (денежной) форме или в натуре (например, в тонно-километрах). Требуется найти такой план перевозок, при котором были бы удовлетворены потребности в пунктах B₁, В₂, ..., В_m и при этом суммарные затраты на перевозку были бы минимальны.

     Обозначая через х_ij количество продукта, перевозимое из i-гo пункта производства в j-й пункт потребления, приходим к следующей математической формулировке задачи.

     Найти минимум

     

     (суммарные  затраты на транспортировку) при условиях

       , j 1, …,n  (1)

     (в  каждый пункт потребления завозится  требуемое количество продукта);

        , i 1, …, m  (2)

     (из  каждого пункта производства  полностью вывозится произведенный  продукт);

                       x_ij>0, i = 1,2,..., m; j = 1,2,..., n  (3)

     (перевозимый  объем продукта не может быть  отрицательным).

     Всякий  набор величин x_ij (j 1, …,n; i 1, …, m), удовлетворяющих условиям (1 - 3), называется допустимым планом перевозок. План, для которого суммарные затраты достигают минимума, называется оптимальным.

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

     (1) разность оценок пунктов потребления  и производства, между которыми запланированы перевозки, равна затратам по транспортировке единицы продукта между этими пунктами;

     (2) аналогичные разности для всех  остальных пар пунктов не превосходят  затрат по транспортировке.

     План  перевозок с указанием запасов  и потребностей удобно записывать в  виде следующей таблицы, называемой таблицей перевозок:

     Таблица №1

 

     Строки  транспортной таблицы соответствуют  пунктам производства (в последней клетке каждой строки указан объем запаса продукта а_i), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (x_ij=0), называют свободными, а ненулевые — занятыми (x_ij >0).

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

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

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

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

 

  Нахождение первоначального распределения

 

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

     Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

  Метод северо-западного угла

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

     По  аналогии с другими задачами линейного  программирования решение транспортной задачи начинается с построения допустимого  базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются а_i^(q), а текущих неудовлетворенных потребностей — b_j^(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем а_i⁽⁰⁾ = а_i, b_j^{(0) =} b_j. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: x_ij=min{ а_i^(q), b_j^(q).)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

     а_i^(q+1) = а_i^(q)- x_{ij ,} b_j^(q+1).= b_j^(q).- x_ij

     Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а_i^(q+1) =0 или _, b_j^(q+1).= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b_j^(q+1).= 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.