Сущность алгоритма метода дифференциальных рент

  
 
 
 
 

Содержание

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

1. Формулировка транспортной задачи………………………………………3

2. Метод дифференциальных рент…………………………………………....4

3. Сущность алгоритма метода дифференциальных рент……………….......5

3.1 Сущность метода дифференциальных рент на  числовом примере…….6

Заключение…………………………………………………………………….15

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

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

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

1. Формулировка транспортной  задачи. 
 
Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,...,m, j=1,2,...,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. 
Исходные данные транспортной задачи обычно записываются в таблице  
 
Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(), вектора запросов потребителей  
В=() и матрицы стоимостей .  
 
В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п. 
 
2. Математическая модель транспортной задачи. 
Переменными (неизвестными) транспортной задачи являются i=1,2,,...,m, j=1,2,...,n - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок 
. 
Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид . 
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью: 
, i=1,2,...,m. 
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей: 
, j=1, 2, ... , n. 
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так: 
, (1) 
, i=1,2,...,m , (2) 
 
, j=1, 2, ... , n, (3) 
 
, i=1,2,,...,m, j=1,2,...,n (4) 
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. . 
Такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой. 
Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,...,m, j=1,2,...,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).  
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3): 
 
 
 
 
............................................................. 
А = (6). 
............................................................ 
 
 
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая - на (m+j)-м месте, т.е. 
 
Номер 
корди- 
наты 
= ; = .  
 
 
 
 

Обозначим через  вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом: 
, (7) 
=, (8) 
, i=1,2,,...,m, j=1,2,...,n (9)

2.Метод дифференциальных рент

      Этот метод создан советскими  учеными. В конце 50-х годов  А.Л.Лурье на основе

общих идей линейного  программирования, сформулированных Л.В.Канторовичем,

разработал метод  решения транспортных задач, который  назвал методом разрешающих

слагаемых. Затем  А.Л. Брудно, используя основные идеи метода А.Л.Лурье, разработал

оригинальный  алгоритм - алгоритм дифференциальных рент - и реализовал его в

машинной программе. В дальнейшем самими же авторами были предложены и другие

названия этих методов (первый называли - методом  приближения условно-оптимальными

планами, второй - алгоритмом вычеркивающей нумерации). Однако в литературе уже

утвердились старые названия, к тому же термин дифференциальных рент удачно

отражает экономическую  сущность алгоритма. Это будет видно  из дальнейшего

изложения.

      В этой главе нами будет  рассмотрена сущность алгоритма метода

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

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

3.Сущность алгоритма метода дифференциальных рент 

      Ранее были рассмотрены распределительный метод и его модификация - метод

потенциалов. Особенность  этих методов заключалась в том, что сначала определялся

некоторый опорный  план, какое-то неотрицательное решение  задачи, а затем шаг за

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

      Метод разрешающих слагаемых,  дифференциальных рент, венгерский  и

некоторые другие основаны на противоположном принципе; в них план с самого начала

соответствует критерию оптимальности, но должен проверяться  на допустимость.

Если план оказывается  недопустимым, т.е. если сумма поставок оказывается меньше (а

иногда и больше) мощностей поставщиков (или спросов  потребителей), а так именно и

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

доводится до допустимого. Как только это достигается, решение  считается

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

      Таким образом, до самого конца  решения план, удовлетворяя критерию

оптимальности, не является допустимым - он является условно оптимальным. Поэтому

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

планов.

      Основная идея метода дифференциальных  рент заключается в том, что

первоначально в каждом столбце отмечаются кружками или ( как в данном случае)

полужирным курсивом минимальные показатели сij и в  клетки с выделенными

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

окажется распределенной и спрос потребителей удовлетворен полностью, это

означает, что  получен оптимальный план. Если это условие не выполняется, начинается

итеративный процесс, в ходе которого матрица C = cij изменяется особым образом и

процесс распределения  поставок повторяется, но уже в соответствии с новой матрицей

стоимости поставок. При этом общее количество распределенной продукции

       
 
 

     m       n 

      ∑       ∑ x

       i =1i j =1j

                    
 

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

       Если на какой-то итерации оказывается  распределенной вся продукция, то на

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

оптимальным. 

      
 
 
 
 
 
 
 
 

  3.1 Сущность метода дифференциальных рент на  числовом примере

Рассмотрим сущность метода дифференциальных рент на небольшом  числовом

примере.

       Предположим, что имеются поставщики  А1, А2, А3 какого-то конкретного

сортимента         лесоматериалов,      потребителями        которого        являются

деревообрабатывающие  предприятия B1, B2, B3.

       В условии задачи известны: количества лесоматериалов (тыс.м3), предназначенных

деревообрабатывающим  предприятиям bj, а также себестоимость  производства и доставки к реализации (поставке) от каждого из поставщиков аi, потребности (спрос) в них по 

1м3 лесоматериалов  от любого из поставщиков к любому из потребителей. Эти данные

приведены в  табл. 4.1

      Табл. 4.1 

 Поставщики                             Объем                Потребители лесоматериалов

 лесоматериа-                       лесоматериалов,      В1               В2               В3

            лов                             предназначен-           Потребности (спрос), тыс.м3

                                               ных к поставке,     200              280              270

                                                 тыс.м3             Себестоимость производства и доставки 1 м3

                       А1                                 200             9               7                 8

                       А2                                 300             6               8                10

                       А3                                 250            11               9                12

 

1м3 лесоматериалов  от любого из поставщиков к  любому из потребителей. Эти данные

приведены в  табл. 4.1     Из данных, приведенных в табл.4.1 видно, что суммарный спрос на лесоматериалы

трех потребителей (750 тыс.м3) равен суммарному объему лесоматериалов,

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

 

      m                 n

 

     ∑ a = ∑b .

     i =1i j =1j

                              

           

                        (4.28)

 

     В  задаче необходимо найти оптимальный  план снабжения лесоматериалами

деревообрабатывающих  предприятий, при котором суммарные  затраты на производство и

доставку всех лесоматериалов были бы минимальными.

     Иными  словами, требуется найти матрицу  неотрицательных чисел хij:

      x11          x12           x13 a1 ,

    x 21          x 22          x 23 a 2 ,                                              (4.29)

     x31           x32            x33 a3 ,

     b1               b2               b3

 

которая минимизировала бы целую функцию

                 3      3

     F = ∑  ∑ cij xij .                                                                  (4.30)

                j =1 j =1

 

при условиях:

      3

 

     ∑x

     i =1

            ij   = ai               i = 1,2,3,                                           ( 4.31)

      3

 

     ∑x

     j =1

            ij   = bj               j = 1,2,3,                                           ( 4.32)

 

            x ij ≥ 0.

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

неизвестными.

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

последовательных приближений (итераций).

     Первая  итерация. Прежде представим исходные  данные в рабочей табл.4.13.

 

Затем в каждом столбце отметим минимальный  показатель затрат1 сij , по которым

каждый потребитель  мог бы получить лесоматериал, если бы мощности поставщиков,

связанных с  ними минимальными сij, не были ограничены.

     Если  в каком-либо столбце окажется  несколько одинаковых (наименьших) значений

себестоимости поставок, то отмечается только одна, причем безразлично какая. Далее

составляется  схема распределения лесоматериалов в соответствии с отмеченными

жирным шрифтом  минимальными затратами.

     Распределение  продукции по клеткам с выделенными  минимальными значениями

себестоимости начинается с первого столбца, при  этом в клетку записывается поставка

      xij = min(a i , b j ).                                             (4.33)

     Если  к моменту записи очередной  поставки исчерпана мощность  соответствующего

поставщика или  полностью удовлетворен спрос соответствующего потребителя, то в

клетку следует  записывать нулевую поставку. Проведем распределение лесоматериалов

применительно к рассматриваемому примеру: в клетку А2В1 записываем поставку

х21=min(300, 200)=200, в  клетку А1В2 - поставку х12=min(200, 280)=200. Поскольку

мощность первого  поставщика А1 оказалась исчерпаной, в клетку А1В3 записывается

поставка х13=0.

     По  окончании распределения схема  проверяется на допустимость, т.е.  исчерпаны ли

мощности поставщиков  и удовлетворен ли спрос потребителей. В нашем примере

целиком распределены лесоматериалы поставщика А1, как наиболее дешевые, и частично

лесоматериалы поставщика А2 (200 из 300 тыс.м3).

     1

       Числа, которые набраны жирным  курсивом.

     По  этой схеме полностью удовлетворяется  спрос лишь потребителя В1 и  частично

потребителя В2 (200 из 280 тыс.м3). Поэтому эта схема распределения не является

допустимым планом поставок, т.е. не является решением задачи. В связи с этим далее

необходимо произвести оценку каждого поставщика в следующем  порядке.

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

потребителей, отмеченных жирным шрифтом, не удовлетворен в полной мере, то такой

поставщик считается  недостаточным и оценкой его  служит недостаток, равный величине

неудовлетворенных запросов, со знаком минус. И, наоборот, если продукция поставщика

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

нераспределенная  часть продукции со знаком плюс.

     Если  в какой-либо строке нет ни  одного значения себестоимости,  отмеченного

кружком или  жирным шрифтом, то оценкой такого избыточного поставщика служит

число, равное его  мощности.

    

 
 
 
 
 
 
 
 
 
 
 
 

Данные оценки поставщика заносятся в последнюю  графу рабочей табл.4.2.

       Табл.4.2

 

Поставщики и  их                    Потребители и их спрос            Оценка                           мощности                   В1             В2            В3                  поставщиков

                                  200            280           270                                          

     А1           200        9                7             8               -350

                                                      200            0

     А2           300        6                8             10             +100

                                        200

     А3           250        11               9             12             +250

 

Разность

 себестоимости             -              1             2

                                                                

 
 

                                                                                 

 
 
 
 

     В  нашем примере поставщик          А1 является недостаточным, так  как спрос

потребителей  В2В3, связанных с ним минимальными себестоимостями, равен 280+270=550

тыс.м3, а мощность А1 только 200 тыс.м3. Поэтому его оценка будет - 350, величина,

которая характеризует  неудовлетворенную часть спроса потребителей В2 и В3.

     Поставщик  А2 является избыточным, поскольку  не вся его продукция распределена;

его оценка +100 (300 - 200).

     Продукция  поставщика А3 осталась полностью нераспределенной, следовательно, он

избыточный, его  оценка +250.

     Строчку  матрицы с избыточным поставщиком  принято называть положительной,  а с

недостаточным поставщиком - отрицательной.

     Здесь  следует заметить, что при правильной  оценке всех поставщиков

алгебраическая  сумма оценок всегда равна нулю.

     Поскольку  наиболее "дешевых" лесоматериалов  поставщика А1 в связи с его

ограниченными ресурсами недостаточно для удовлетворения всех потребностей

потребителей  В2 и В3 , приходится предусматривать использование свободных ресурсов

поставщиков А2 и А3. При этом сначала будут  использоваться лесоматериалы, затраты  на

которые отличаются от затрат на лесоматериалы, в данном случае поставщика А1, в

наименьшей мере.

     Для  этого в столбцах матрицы себестоимости поставок необходимо определить

разность между  наименьшей себестоимостью сij в одной  из положительных строк с

минимальной себестоимостью, отмеченной жирным шрифтом в этом столбце.

Полученные разности записываются в нижней строке таблицы.

     В  тех столбцах матрицы, где есть хотя бы одна себестоимость, отмеченная жирным

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

       В нашем примере в первом  столбце В1 минимальная себестоимость  с21=6=min

находится в  положительной строке А2, следовательно, для этого столбца В1 разность не

вычисляется. Во втором столбце В2 себестоимость  с12=7=min расположена в

отрицательной строке. Ближайший к ней по величине показатель одной из

положительных строк с22=8. Поэтому разность себестоимости  для данного столбца В2

равна 1 (8—7). Таким  же способом определяется разность себестоимости  и по другим

столбцам.

       Наименьшую из вычисленных разностей  принято называть промежуточной

рентой. В таблице ее следует отметить квадратом (заключить в него). В нашем примере

промежуточная рента равна 1 столбец В2.

       Вторая итерация заключается  в составлении новой таблицы-матрицы  (табл. 4.3)

транспортной  задачи и обработке данных, помещенных в ней. При ее составлении

себестоимости поставок по отрицательным строкам  увеличиваются на величину

исчисленной в  предыдущей итерации промежуточной  ренты. Себестоимости поставок по

положительным строкам переписываются в эту  новую таблицу без изменения. В нашем

примере на промежуточную ренту 1 следует увеличить себестоимости строки А1.

                                                                            Табл.4.3

 

  Поставщики  и их                   Потребители и их спрос                 Оценки

     мощности                В1              В2               В3         поставщиков

                            200             280              270

    А1     200         10               8              9                    -250

                                                0                  200

    А2     300         6                8              10                    -0

                                  200           100

 
 

                                                                                      177

 
 

    А3     250          11              9                12                    +250

 

       Разность           1             5                  3

    себестоимости            

 

        Последовательность выполнения  второй и последующих итераций  остается общей

— подобной первой итерации. Однако есть здесь и свои особенности.

        Сначала отмечаются кружками  или жирным шрифтом все минимальные

себестоимости поставок по столбцам, считая и повторяющиеся  по величине. Затем снова

по минимальным  для каждого потребителя затратам, отмеченным полужирным шрифтом,

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