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

Потенциалы строк и столбцов внесем в таблицу 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