Xreferat.com » Рефераты по экономико-математическому моделированию » Методы линейного программирования для решения транспортной задачи

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

План реферата


Введение

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

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

3. Необходимое и достаточное условия разрешимости транспортной задачи

4. Свойство системы ограничений транспортной задачи

5. Опорное решение транспортной задачи

6. Методы построения начального опорного решения

6.1 Построение первоначального плана по способу северо-западного угла

6.2 Построение первоначального плана по способу минимального элемента

7. Переход от одного опорного решения к другому

8. Распределительный метод

9. Метод потенциалов

10. Особенности решения транспортных задач с неправильным балансом

11. Алгоритм решения транспортной задачи методом потенциалов

11.1 Предварительный шаг

11.2 Общий повторяющийся шаг

12. Транспортная задача с ограничениями на пропускную способность

13. Транспортная задача по критерию времени

14. Применение транспортной задачи для решения экономических задач

Заключение

Список использованной литературы

Введение


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

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

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

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

Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. [1]

Транспортная задача (transportation problem) - одна из наиболее распространенных задач математического программирования (обычно - линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот. [2]

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


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

Исходная информация:

Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k);

Nj - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

aij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

Методы линейного программирования для решения транспортной задачи - общая (суммарная) стоимость перевозок;

Методы линейного программирования для решения транспортной задачи - количество груза, вывозимого из i-ro пункта;

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

В простейшем случае должны выполняться следующие очевидные условия:


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

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

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


Таким образом, математической формулировкой транспортной задачи будет:

найти


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


при условиях


Методы линейного программирования для решения транспортной задачи;

Методы линейного программирования для решения транспортной задачи;

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


Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели.

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

Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

найти


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


при условиях


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

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

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


Ясно, что в этой задаче не предполагается, что весь груз, накопленный в i-м пункте, должен быть вывезен. [3]


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


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

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


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


Здесь показатели aij означают затраты на перевозку единицы груза от i-го поставщика (i=1,2,…,k) к j-тому потребителю (j=1,2,…,l), Mi - мощность i-того поставщика в планируемый период, Nj - спрос j-того потребителя на этот же период. Обозначим через xij поставку (количество груза), которая планируется к перевозке от i-того поставщика к j-тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции


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


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


Методы линейного программирования для решения транспортной задачи(1)


Если к этим ограничениям добавить еще одно:


Методы линейного программирования для решения транспортной задачи,(2)


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

Задачам, в которых ограничение (2) отсутствует, т.е.


Методы линейного программирования для решения транспортной задачи,


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

Отметим некоторые особенности экономико-математической модели транспортной задачи.

Система ограничений (1) сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

Матрица коэффициентов при переменных в системе (1) состоит только из единиц и нулей.

Система ограничений (1) включает k уравнений, связывающих поставки i-того поставщика с мощностью Mi (i=1,2,…,k) этого поставщика, и l уравнений, связывающих поставки j-тому потребителю со спросом Nj (j=1,2,…,l) этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число l - числу столбцов.

Число переменных xij, входящих в целевую функцию и в систему уравнений (1), равно произведению kl, т.е. числу клеток таблицы.

Таким образом, система ограничений (1) есть система из k+l уравнений с kl переменными.

Любое решение транспортной задачи (x11, x12,…, xkl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях.

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

В ходе решения задачи и нужно получить это оптимальное распределение поставок, которому соответствует какое-то допустимое базисное решение системы ограничений (1). [4]

3. Необходимое и достаточное условия разрешимости транспортной задачи


Ограничение (1) и условия неотрицательности переменных, исключающие обратные перевозки xij>0; i= 1, 2, …, k; j= 1, 2,., l.

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

Как видим, система ограничений задана в основном (k + l) уравнениями. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения.

Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим Методы линейного программирования для решения транспортной задачи. Сложим те же элементы по столбцам, каждый столбец дает Nj, и в сумме получим Методы линейного программирования для решения транспортной задачи. Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие


Методы линейного программирования для решения транспортной задачи.


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

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

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


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


Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи.

Просуммируем эти числа по индексу i:


Методы линейного программирования для решения транспортной задачи.


Но величины Nj, Методы линейного программирования для решения транспортной задачи от индекса i не зависят и их можно вынести за знак суммы. В результате

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

или


Методы линейного программирования для решения транспортной задачи, Методы линейного программирования для решения транспортной задачи


Следовательно, взятые числа удовлетворяют группе уравнений (1).

Просуммируем эти числа по индексу j:


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


Вынося постоянные Mi и Методы линейного программирования для решения транспортной задачи за знак суммы и имея в виду, что Методы линейного программирования для решения транспортной задачи, получаем


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


или в развернутом виде


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


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

Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи. [5]

4. Свойство системы ограничений транспортной задачи


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


Методы линейного программирования для решения транспортной задачи.


В этой системе ограничений уравнений закрытой транспортной задачи имеется k+l-1 линейно-независимых уравнений, т.е. ранг системы ограничений равен k+l-1. [6]

5. Опорное решение транспортной задачи


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

При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет - последовательно проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают снова за исходную точку и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся так называемый симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием "методы последовательного улучшения допустимого решения (МПУ)": метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и другие. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному. [2]

6. Методы построения начального опорного решения


6.1 Построение первоначального плана по способу северо-западного угла


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

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


6.2 Построение первоначального плана по способу минимального элемента


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

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

Этот способ заключается в следующем.

1. Располагаем все клетки таблицы в очередь по мере возрастания тарифов, начиная с минимального.

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

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

Полученный план будет ациклическим и будет состоять не более чем из k+l-1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. [5]

7. Переход от одного опорного решения к другому


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

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

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

Для свободной клетки с Методы линейного программирования для решения транспортной задачи строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение. [7]

8. Распределительный метод


Распределительный метод решения транспортной задачи отличается от метода потенциалов некоторым изменением вычислительного процесса и иным (по форме) критерием оптимальности.

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

1. Отыскиваем первоначальный ациклический план, содержащий (k+l-1) компонент (при недостатке компонент дописываем нули).

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

3. Проделываем указанную в п.2 операцию для каждой свободной клетки, строя всякий раз свой цикл пересчета. В результате в каждой свободной клетке появится число (положительное, отрицательное или нуль).

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

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

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

Для ручного счета более удобен метод потенциалов. Однако на распределительном методе основаны некоторые другие способы решения задач, что и вызывает необходимость его изучения. [5]

9. Метод потенциалов


Решение транспортной задачи любым способом производится на макете. Макет для применения метода потенциалов имеет следующий вид.


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


Основная часть макета выделена двойными линиями. Она содержит kl клеток. Каждая клетка в этой части обозначается символом (i, j). Например, клетка, стоящая во второй строке и первом столбце, будет обозначена (2, 1). Макет содержит в себе матрицу тарифов. Назначение строки vj и столбца ui будет выяснено в дальнейшем.

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

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

Пример цепи приведен в табл.2.


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


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

Если последняя клетка цепи расположена в одном ряду с первой, то такая замкнутая цепь называется циклом. Некоторые разновидности циклов показаны в табл.3.


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


Теорема. Пусть в макете (или матрице) из k строк и l столбцов произвольно отмечено k+l клеток, причем k+l  kl. В этом случае всегда можно построить цикл, вершины которого лежат в отмеченных клетках (может быть не во всех).

Замечание. Числа k и l целые, и для них не всегда будет выполнено неравенство k+l  kl. Если одно из этих чисел - единица, это неравенство не выполняется. Например, при k=3, l=1 имеем 3 + 1 > 3·1. Однако при k=2 и l=2 будет 2+2 = 2·2, а при k и l, одновременно больших двух, неравенство всегда выполняется.

Условие k+l  kl исключает случаи матриц с одной строкой или одним столбцом, в которых вообще цикла построить нельзя.

Доказательство. Рассмотрим минимальный возможный случай: k=2, l=2 (табл.4).


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


В макете надо выбрать k+l = 4, т.е. все 4 клетки. Для этого случая теорема справедлива: выбранные клетки образуют цикл.

Возьмем теперь любые k>2, l>2. Доказательство будем вести методом математической индукции.

Допустим, теорема справедлива для макета, у которого сумма строк и столбцов на единицу меньше взятых нами (k+l). Докажем, что при этом предположении теорема будет справедлива для принятых (k+l).

Первый случай. Среди отмеченных клеток имеется одна клетка, единственная в ряду (строке или столбце) (табл.5).


Методы линейного программирования для
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

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

Похожие рефераты: