Размещено на http://www.allbest.ru/

БОУ Чувашской Республики СПО «Алатырский

сельскохозяйственный техникум»

Минобразования Чувашии

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

по дисциплине: «Математические методы»

Тема: Транспортная задача. Метод наименьших затрат.

2012 г.

Содержание

Введение

Раздел 1. Транспортная задача. Метод наименьших затрат

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

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

1.3 Метод наименьших затрат

Раздел 2. Практическая часть

2.1 Решение транспортной задачи методом наименьших затрат

Заключение

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

Введение

Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин. Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок). В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов (по видам и содержащимся в них питательным веществам). Задача о смесях может найти применение и в литейном производстве (состав металлургической шихты). Этим же методом решаются транспортная задача, задача рационального прикрепления предприятий-потребителей к предприятиям-производителям. Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу - значит выбрать из всех допустимо возможных (альтернативных) вариантов лучший, оптимальный. Важность и ценность использования в экономике метода линейного программирования состоят в том, что оптимальный вариант выбирается из весьма значительного количества альтернативных вариантов. При помощи других способов решать такие задачи практически невозможно. Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Транспортная задача (transportation problem) - одна из наиболее распространенных задач математического программирования (обычно - линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот.

Раздел 1. Транспортная задача. Метод наименьших затрат

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

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

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

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

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

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

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

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

- общая (суммарная) стоимость перевозок;

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

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

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

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

Найти

при условиях

;

;

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

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

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

Найти

при условиях

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

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

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

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

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

(1)

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

,(2)

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

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

,

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

Число переменных x_ij, входящих в целевую функцию и в систему уравнений (1), равно произведению kl, т.е. числу клеток таблицы. Таким образом, система ограничений (1) есть система из k+l уравнений с kl переменными. Любое решение транспортной задачи (x₁₁, x₁₂,…, x_kl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях. Оптимальному решению транспортной задачи соответствует оптимальное распределение поставок, при котором целевая функция достигает своего минимума. В ходе решения задачи и нужно получить это оптимальное распределение поставок, которому соответствует какое-то допустимое базисное решение системы ограничений.

1.3 Метод наименьших затрат

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

Алгоритм:

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

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

Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.

Раздел 2. Практическая часть

2.1 Решение транспортной задачи методом наименьших затрат

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

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 2 (26-24). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Занесем исходные данные в распределительную таблицу.

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

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

3. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(1;3): 0 + 7 > 4

(1;4): 0 + 4 > 3

Выбираем максимальную оценку свободной клетки (1;3):

4. Для этого в перспективную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

5.Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(2;1): 4 + 1 > 4

(3;1): 2 + 1 > 2

Выбираем максимальную оценку свободной клетки (2;1): Для этого в перспективную клетку (2;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3)=2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1=0.

2. 

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(3;1): 2 + 1 > 2

Выбираем максимальную оценку свободной клетки (3;1): 2

Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) =2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

3. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

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

Затраты составят:

F(x) = 4*6 + 4*2 + 3*6 + 2*2 + 3*8 + 0*2 = 78

Заключение

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

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

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

1. Юдин Д. В., Гольштейн К. Г., Линейное программирование, М., 1963.

2. Данциг Дж., Линейное программирование, его применения и обобщения, пер. с англ., М., 1966 .

3. Ашманов С. А., Линейное программирование, М., 1981. Е. Г. Голъштейн.

4. Кук Д., Бейз Г. Компьютерная математика. - М.: Наука, 1990.

Нечепуренко М.И. Алгоpитмы и пpогpаммы pешения задач на графах и сетях. - Новосибирск: Hаука, 1990.

Размещено на Allbest.ru