Вход

Транспортная задача. Метод потенциалов.

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 144142
Дата создания 2008
Страниц 29
Источников 5
Мы сможем обработать ваш заказ (!) 29 марта в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 520руб.
КУПИТЬ

Содержание

Введение
1. Общая постановка транспортной задачи
2. Построение математической модели
3. Методы решения транспортной задачи
3.1 Методы построения первоначального плана перевозок
3.1.1 Построение первоначального Т-плана методом северо-западного угла
3.1.2. Построение первоначального Т-плана методом наименьшей стоимости
3.2. Методы отыскания оптимального решения
3.2.1. Метод потенциалов
3.2.2. Распределительный метод
Заключение
Литература

Фрагмент работы для ознакомления

Потенциалы строк и столбцов внесем в таблицу 19. Вычислим оценки невыделенных клеток таблицы: (11=1>0; (14=7>0; (22=0; (23=0; (32=2>0; (34=1>0. Согласно требованиям данного метода можно утверждать, что данный Т-план является оптимальным.
Сделаем выводы:
Оптимальный план заключается в перевозке груза в пункт а со складов В и С в объеме 80 и 70 усл.ед соответственно; в пункт б со складов А и С в объеме 20 и 100 усл.ед.; 80 усл.ед в пункт с со склада А и 50 усл.ед. в пункт д со склада В.
Транспортные издержки при этом будут равны L=5*20+7*80+1*80+2*50+5*70+8*100=1990 ден.ед.
3.2.2. Распределительный метод
Содержание метода:
1). Для каждой невыделенной клетки построим замкнутый контур следующим образом:
начиная с невыделенной клетки по кратчайшему пути обходятся выделенные клетки по горизонтальному или вертикальному направлению;
всем клеткам в строгом чередовании присваиваются знаки (+) или (-), причем первой присвивают знак (+) невыделенной клетке, с которой было начато построение контура.
2). Будем считать величину поставки и стоимость перевозки положительными, если клетка отмечена знаком (+) и отрицательными, если клетка отмечена знаком (-).
3). Вычислим алгебраическую сумму стоимостей перевозки с учетом знака клетки для каждого построенного контура - оценку клетки. Обозначим ее через δij , где (i,j)- невыделенная клетка, с которой было начато построение замкнутого контура.
4). Если все δij≥0, то построенный Т-план считают оптимальным. Остается вычислить затраты на перевозку груза. В противном случае – план перевозок не оптимальный и необходимо составить улучшенный Т-план (п.5).
5). Для построения улучшенного Т-плана выберем клетку (и соответствующий ей контур) с отрицательной оценкой, которой соответствует наименьшая удельная стоимость. Найдем в отрицательных вершинах этого контура минимальную по абсолютному значению величину поставки. Пусть это будет поставка xlk. Тогда:
клетку (l,k) исключим из числа выделенных и обнулим соответствующую ей величину поставки;
величину поставки в положительных клетках контура увеличим на xlk, а в отрицательных клетках – уменьшим на xlk.
6). Получили новый Т-план (он отличается от предыдущего одной выделенной клеткой). Необходимо проверить его на оптимальность (начать с п.1).
Замечание 7: замкнутый контур, полученный при построении улучшенного Т-плана, содержит четное число вершин, причем число клеток со знаком (+) совпадает с числом клеток со знаком (-).
Замечание 8: Во избежание арифметических ошибок после построения нового Т-плана необходимо проверить совпадает ли сумма поставок в стоке с объемом груза, имеющегося в наличии у соответствующего поставщика. Также сумма поставок в столбце должна совпадать с объемом поставки, необходимой соответствующему потребителю.
Найдем оптимальный план перевозок для задачи (*), используя распределительный метод. Для этого необходимо взять любой первоначальный Т-план из двух построенных ранее. К примеру возьмем Т-план, построенный по методу наименьшей стоимости. Рассмотрим таблицу перевозок, полученную при этом (Табл.15).
Таблица 15
а б с д 150 120 80 50 А 100 3 5 7 11 20 80 В 130 1 4 6 2 130 С 170 5 8 12 7 40 80 50
1). Чтобы определить является ли найденный Т-план оптимальным рассчитаем оценки каждой невыделенной клетки. Для этого необходимо для каждой из них построить замкнутый контур (6 невыделенных клеток – 6 контуров).
Клетка (1,3): Клетка (1,4): Клетка (2,2):
с12=5
- (1,2) с13=7
+ (1,3) с12=5
- (1,2) с14=4
+ (1,4) с11=3
+ (1,1) с14=5
+ (1,2) с32=8
+ (3,2) с33=12
- (3,3) с32=8
+ (3,2) с34=7
+ (3,4) с32=1
+ (2,1) с34=4
+ (2,2) (13= с13 - с33+ с32 - с12 =7-12+8-5= -2 < 0 (14= с14 - с34+ с32 - с12 =4 -7+8 –5 = 0 (22= с22 - с12+ с11 - с21 =4 - 5+3 - 1=1 > 0 Клетка (2,3): Клетка (2,4):
с11=3
+ (1,1) с12=5
- (1,2) с11=3
+ (1,1) с12=5
- (1,2) с21=1
- (2,1) с23=6
+ (2,3) с21=1
- (2,1) с24=2
+ (2,4) с32=8
+ (3,2) с33=12
- (3,3) с32=8
+ (3,2) с34=7
- (3,4) (23= с23 - с33+ с32 - с12 + с11 - с21 =
6-12+8-5+3-1= -1 < 0 (24= с24 - с34+ с32 - с12 + с11 - с21 =
2 -7+8-5+3-1= 0
Клетка (3,1):
с11=3
- (1,1) с12=5
+ (1,2) с31=5
+ (3,1) с32=8
- (3,2) (31= с31 - с11+ с12 - с32 =
5-3+5-8= -1 < 0
Так как не все свободные клетки имеют неотрицательные оценки, то построенный Т-план нельзя считать оптимальным. Необходимо улучшить план перевозок.
2). Выберем клетку с отрицательной оценкой. Их три: клетка (1,3) с удельной стоимостью с13=7; клетка (2,3) где с23=6 и клетка (3,1) где с31=5. Минимальная удельная стоимость соответствует клетке (3,1). С нее начнем построение нового Т-плана.
3).Рассмотрим контур, соответствующий клетке (3,1):
с11=3; х11=20
- (1,1) с12=5; х12=80
+ (1,2) с31=5
+ (3,1) с32=8; х32=40
- (3,2)
Наименьший объем перевозки в отрицательных клетках контура соответствует клетке (1,1) и равен 20. Следовательно клетку (1,1) удалим из числа выделенных, выделим клетку (3,1) и присвоим значение х31=20, х12=80+20=100, х32=40-20=20. Получили новый Т-план (Табл.20):

Таблица 20
L=2200 а б с д 150 120 80 50 А 100 3 5 7 11 100 В 130 1 4 6 2 130 С 170 5 8 12 7 20 20 80 50
Проверим правильно ли был построен новый Т-план:
число выделенных клеток не изменилось;
1 строка: 100=100; 2 строка: 130=130; 3 строка: 170 = 20 + 20 + 80 +50; 1 столбец: 150=130+20; 2 столбец: 120=100+20; 3 столбец: 80=80; 4 столбец: 50=50.
- суммарная стоимость перевозок уменьшилась: (изначально L=2220) L=5*100+1*130+5*20+8*20+12*80+7*50=2200 ден.ед.
Новый Т-план построен правильно. Проверим его на оптимальность - вычислим оценки невыделенных клеток: (11= с11-с31 + с32 – с12=3-5+8-5=1>0; (13= с13-с33 + с31 – с11=7-12+8-5= -2<0;
(14= с14-с34 + с32 – с12= 4-7+8-5=0;
(22= с22-с32 + с31 – с21=4-8+5-1=0;
(23= с23-с33 + с31 – с21=6-12+5-1= -2<0;
(24= с24 - с34 + с31 – с21 = 2 -7+5-1= -1< 0.
Получили три клетки с отрицательной оценкой: (13, (23, (24. Это означает, что построенный Т-план также не является оптимальным. Наименьшая удельная стоимость соответствует клетке (2,4). С нее начнем построение нового Т-плана.
4). Рассмотрим контур, соответствующий клетке (2,4):
С21=1; х21=130
- (2,1) с24=2
+ (2,4) с31=5; х31=20
+ (3,1) с34=7; х34=50
- (3,4)
Наименьший объем перевозки в отрицательных клетках контура соответствует клетке (3,4) и равен 50. Следовательно клетку (3,4) удалим из числа выделенных, выделим клетку (2,4) и присвоим значение х24=50, х31=20+50=70, х21=130-50=80. Получили новый Т-план (Табл.21):
Таблица 21
L=2150 а б с д 150 120 80 50 А 100 3 5 7 11 100 В 130 1 4 6 2 80 50 С 170 5 8 12 7 70 20 80
Далее необходимо проверить правильно ли был построен новый план перевозки груза (Выполнение проверки упустим для краткости. Хотя на практике эта процедура обязательна!).
Проверим новый Т-план на оптимальность - вычислим оценки невыделенных клеток: (11= с11-с31 + с32 – с12=3-5+8-5=1>0;
(13= с13-с33 + с31 – с11=7-12+8-5= -2<0;
(14= с14-с24 + с21 – с31 + с32 - с12= 4-2+1-5+8-5=1>0;
(22= с22-с32 + с31 – с21=4-8+5-1=0;
(23= с23 - с33 + с31 – с21=6-12+5-1= -2<0;
(34= с34-с24 + с21 – с31=7 – 2 +1-5 =1> 0.
Получили две клетки с отрицательной оценкой: (13, (23. Это означает, что построенный Т-план также не является оптимальным. Наименьшая удельная стоимость соответствует клетке (2,3). С нее начнем построение нового Т-плана.
5). Рассмотрим контур, соответствующий клетке (2,3):
С21=1; х21=80
- (2,1) с23=6
+ (2,3) с31=5; х31=70
+ (3,1) с33=12; х33=80
- (3,3)
Наименьший объем перевозки соответствует обеим отрицательным клеткам контура и равен 50. Удалим из числа выделенных (3,3), так как ей соответствует наибольшая удельная стоимость перевозки. Выделим клетку (2,3) и присвоим значение х23=80, х31=70+80=150, х21=80-80=0. Получили новый Т-план (Табл.22):
Таблица 22
L=1990 а б с д 150 120 80 50 А 100 3 5 7 11 100 В 130 1 4 6 2 0 80 50 С 170 5 8 12 7 150 20
Далее необходимо проверить правильно ли был построен новый план перевозки груза.
Проверим новый Т-план на оптимальность - вычислим оценки невыделенных клеток: (11= с11-с31 + с32 – с12=3-5+8-5=1>0; (13= с13-с23 + с21 – с31+ с32 – с12=7-6+1-5+8-5=0; (14= с14-с24 + с21 – с31 + с32 - с12= 4-2+1-5+8-5=1>0; (22= с22-с32 + с31 – с21=4-8+5-1=0; (33= с33-с23 + с21 – с31=12 – 6 +1-5 =2>0; (34= с34-с24 + с21 – с31=7 – 2 +1-5 =1> 0.
Получили, что все клетки имеют неотрицательную оценку. Следовательно, построенный Т-план является оптимальным.
Сделаем выводы:
Оптимальный план заключается в перевозке груза в пункт а со склада С в объеме 150 усл.ед соответственно; в пункт б со складов А и С в объеме 100 и 20 усл.ед.; 80 усл.ед в пункт с со склада В и 50 усл.ед. в пункт д со склада В.
Транспортные издержки при этом будут равны L=5*100+1*0+6*80+2*50+5*150+8*20=1990 ден.ед.
Заключение

В данной работе мною были приведены основные способы и методики решения транспортной задачи, которая на сегодняшний день является одной из самых распространенных задач математического линейного программирования. Решение транспортной задачи позволяет получить наиболее эффективные способы и маршруты перевозки грузов, при этом максимально снижается или совсем устраняется количество дальних маршрутов, встречных и повторных перевозок. Все это приводит к сокращению времени доставки груза, уменьшению транспортных затрат различных организаций и увеличению прибыли данных предприятий.
Используя методику решения транспортной задачи можно получать решения некоторых экономических задач, которые не имеют ничего общего с процессами перевозки товаров. В этих задачах величины удельных стоимостей cij имеют различный смысл в зависимости от условий представленной задачи. Представим несколько типов подобных задач:
составление оптимального операционного плана работы станка. В данном типе задач cij является показателем производительности. В результате решения данной задачи определяется операционная и временная загруженность каждого станка для получения максимальной производительности. При этом значения cij берутся со знаком минус, так как в транспортной задаче происходит нахождение минимума функции;
составление оптимального плана работы станочного парка. Имеется несколько станков, которые выполняют несколько видов обработки с производительностью cij. В результате решения задачи определяется, какой станок и какой вид обработки будет производить, чтобы достичь максимальной производительности всего станочного парка;
повышение производительности автотранспорта вследствие снижения или исключения порожних рейсов. Снижение порожних рейсов уменьшит необходимое количество автомобилей, что приведет к увеличению их производительности;
поиск решения транспортной задачи с использованием способа запрещения перевозок. Этот метод применяется тогда, когда груз от некоторого отправителя вследствие каких-то причин не может быть доставлен одному из получателей. Данное условие можно учесть, присвоением соответствующей клетке более высокого значения удельной стоимости, это приведет к тому, что перевозки груза в этот пункт осуществляться не будут.
Исходя из всего вышеперечисленного следует, что правильное решение транспортной задачи представляет значительную ценность для экономики. Мы должны гордиться тем, что одним из первых у истоков возникновения математического линейного программирования стоял советский ученый – Леонид Витальевич Канторович.
Литература
Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993. 336 с.
Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Математические методы принятия решений: Учеб. пособие. Тамбов: Изд-во Тамб. гос. тех. ун-та, 2004. 124 с.
Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах.-М.:Высшая школа, 1999, 1ч.
Карманов В.Г. Математическое программирование. М.: Физматмет, 2000. 264 с.
Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические методы в планировании. - М.: Высшая школа, 1991.
6

Список литературы [ всего 5]


1.Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993.¬ 336 с.
2.Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Математические методы принятия решений: Учеб. пособие. Тамбов: Изд-во Тамб. гос. тех. ун-та, 2004. 124 с.
3.Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах.-М.:Высшая школа, 1999, 1ч.
4.Карманов В.Г. Математическое программирование. М.: Физматмет, 2000. 264 с.
5.Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические методы в планировании. - М.: Высшая школа, 1991.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.005
© Рефератбанк, 2002 - 2024