МИНИСТЕРСТВО  НАУКИ И ОБРАЗОВАНИЯ  РФ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

ДАГЕСТАНСКИЙ  ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 
 

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ СИСТЕМ 

КАФЕДРА «Моделирование и  математические методы в экономике»

КУРСОВАЯ  РАБОТА

 
 

по  дисциплине: 

«Математическая экономика» 

      на  тему:

«Математическая постановка транспортной задачи  линейного

 

программирования  и решение её различными методами».

 
 
 
 

                                           ВЫПОЛНИЛА: ст-ка 3 курса гр.и-711

                                            Бегова Илина Б.

 

                                          

                                            ПРОВЕРИЛ: к.ф.-м.н.доцент  

                                            Атагишиева Г.С.

 
 
 
 
 
 
 
 
 
 
 

Махачкала 2010

Содержание

Введение…………………………………………………………………………………….3

Глава 1. Постановка и модели транспортной задачи линейного программирования………………………………………………………………...………5

1.1. Постановка транспортной задачи и ее математическая модель………..5

1.2.  Закрытая модель транспортной задачи……………………………………..9

1.3. Открытая модель транспортной задачи…………………………………….10

Глава 2. Методы нахождения опорных и оптимальных  планов………………12

2.1. Определение оптимального  и опорного плана  транспортной задачи…..12

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

2.3. Метод минимального  элемента……………………………………………….16

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

2.5. Метод потенциалов………………………………………………………………21

Приложение……………………………………………………………………………..22

Заключение………………………………………………………………………………34

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

     Каждый  человек ежедневно, не всегда осознавая  это, решает проблему: как получить наибольший эффект, обладая ограниченными  средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий.

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

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

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

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Глава 1. Постановка и модели транспортной задачи линейного программирования.

1.1. Постановка транспортной задачи и ее математическая модель

     Транспортная  задача является частным типом задачи линейного программирования и формулируется  следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

  

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

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

  (1) 

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

, i 1, …, m  (2)

     Суммарное количество груза, доставляемого в  каждый пункт назначения из всех пунктов  отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:

, j 1, …, n  (3)

     Объемы  перевозок - неотрицательные числа, так как перевозки из пунктов  потребления в пункты производства исключены:

x_ij 0, i 1, ..., m; j 1, ..., n (4)

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

Определение 1.

     Всякое  неотрицательное решение системы  линейных уравнений

, j 1, …, n и  , i 1, …, m,

определяемое  матрицей X=(x_ij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.

 

Определение 2.

      План X*=(x*_ij)(i 1, …, m; j 1, ..., n), при котором функция

 

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

     Обычно  исходные данные записываются в виде таблицы 1.

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

,  (5)

то модель такой транспортной задачи называется закрытой.

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

, i 1, ..., m.

Введение  этого условия приводит к открытой транспортной модели.

 
 

Теорема 1.

     Любая транспортная задача, у которой суммарный  объем запасов совпадает с  суммарным объемом потребностей, имеет решение.

 
 
 
 
 
 
 
 
 

1.2.  Закрытая модель транспортной задачи

 

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

Доказательство. Пусть   = M > 0 . 

     Тогда   величины  x_ij = a_ib_j /M (i = 1,2,3, ... m; j = 1,2,3, ..., n)                                являются планом, так как они удовлетворяют системе ограничений

( 2 ) и  ( 3 ) .

 Действительно,  подставляя значения  в  (2) и  (3) , находим 

     = a_i ,

    = b_j .

     Выберем из значений  C_ij  наибольшее  C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты  на C¢  тогда, учитывая ( 2 ) , получим

   ,

     Выберем из значений C_ij  наименьшее C¢¢=min C_ij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем

 

Объединяя два последних неравенства в одно двойное, окончательно получаем

C¢¢M ? Z ? C¢ M,

т. е.  линейная функция ограничена на множестве  планов транспортной задачи.

 

1.3. Открытая модель транспортной задачи

 

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

1. суммарные запасы превышают суммарные потребности ;
2. суммарные потребности превышают суммарные запасы .

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

 Найти  минимальное значение линейной  функции

 при ограничениях

,    i = 1, 2, ..., m,                           (случай  а)

,    j = 1, 2, ..., n;

,    i = 1, 2, ..., m,                           (случай б)

,   j = 1, 2, ..., n,

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

     Открытая  модель решается приведением к закрытой модели.

 В  случае (а), когда суммарные запасы  превышают суммарные потребности,  вводится фиктивный потребитель  B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают

 

суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого a_m+1 = .

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

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

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

 
 
 
 
 
 
 
 
 

     Глава 2. Методы нахождения опорных и оптимальных планов.

     2.1. Определение оптимального и опорного плана транспортной задачи

 

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

      Число переменных X_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1  отличных от нуля неизвестных.

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

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

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

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

      Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Одна из них - метод потенциалов - рассматривается ниже.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

    Пример.

      
 
 
 
 
 
 

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

    Теперь  переходим к заполнению клетки для  неизвестного и т.д.

    Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными .

Опорный план имеет вид;

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.3. Метод минимального элемента

 

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

Пример 

     Составить первоначальный опорный план методом  минимального элемента для транспортной задачи вида:

 

Решение:

Задача  сбалансирована.

Строим  первоначальный опорный план методом минимального элемента.

1. Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта : , ;
4. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .

 

  

6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).  
    
   

Опорный план имеет вид:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 

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