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

  
 
 
 
 

Содержание

Введение ……………………………………………………………………….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 .