Транспортная задача

 

Склад	Магазин										Запасы
		20		23		20		15		24	320
	90						230
		29		15		16		19		29	280
			140		110				30
		6		11		10		9		8	250
	60								190
Потребности	150		140		110		230		220

 

Целевая функция (транспортные расходы) . Значение целевой функции изменилось на 180 единиц по сравнению с предыдущим этапом. Проверим полученный план на оптимальность. Подсчитаем потенциалы.

 

 

 ,  

 

Определяем значения оценок для всех свободных клеток:

 

 

 

 

Имеем клетку  с отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.

 

 

Склад	Магазин										Запасы
	⊕	20		23		20		15		24	320
	90						230
		29		15		16	⊕	19		29	280
			140		110				30
		6		11		10		9	⊕	8	250
	60								190
Потребности	150		140		110		230		220

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

Склад	Магазин										Запасы
		20		23		20		15		24	320
	120						200
		29		15		16		19		29	280
			140		110		30
		6		11		10		9		8	250
	30								220
Потребности	150		140		110		230		220

 

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

 

 

 

 

Определяем значения оценок для всех свободных клеток:

 

 

 

    

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке приращение целевой функции равно разности двух сумм: = , где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком  «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком  «-».

В клетках, отмеченных знаком  «+», величины груза прибавляются, что приводит к увеличению значения целевой функции , а в клетках, отмеченных  знаком  «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки меньше нуля, т.е. <0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z( ) на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками , для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие    =0.           (13)

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину = . В результате получится новое опорное решение.

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

Пример 5.

Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице:

Возможности поставщиков

Решение

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

Строю начальный опорный план перевозок методом минимальной стоимости. Начинаю с клетки исключаю из рассмотрения первую строку и первый столбец. Перехожу к клетке Исключаю из рассмотрения вторую строку. Далее выбираю клетку Исключаю из рассмотрения второй столбец. Перехожу к ячейке Закончила построение таблицы.

Возможности поставщиков
	20 «-»		0 «+»
	«+»	30 «-»
		10 «+»	40 «-»

Затем вычислю значение целевой функции на нем:

Так как число заполненных клеток меньше то добавляем в ячейку .

Нахожу цикл для свободной клетки  таблицы, он включает клетки . Вычисляем оценку . Так как  переходим к следующей свободной клетке . Для нее цикл таков:  . Оценка . Так как , определяем величину груза, перераспределяемого по циклу,  = . Приращение целевой функции . Получим новое опорное решение X2 . Значение целевой функции на нем  

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

Возможности поставщиков
			20
	20	10 «-»	«+»
		30 «+»	20 «-»

 

Вычисляем  , Оценки можно вычислять до первой отрицательной. Так как, осуществляем сдвиг по циклу   на величину  = . Приращение целевой функции . Получаем третье опорное решение X3. Значение целевой функции на нем  

 

 

 

Возможности поставщиков
			20
	20 «-»		10 «+»
	«+»	40 «+»	10 «-»

 

Вычисляем оценки для свободных клеток  ,  . Так как  , осуществляем сдвиг по циклу , на величину  = . Приращение целевой функции . Получаем четвертое опорное решение X4 Значение целевой функции на нем . 

Возможности поставщиков
			20
	10 «-»	«+»	20
	10 «+»	50 «-»	0

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

Возможности поставщиков
			20
	0	10	20
	20	40

Значение целевой функции на нем    Вычисляем оценки для свободных клеток . Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

 

1. Е. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 1993.
2. И. Л. Акулич, В. Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000.
3. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
4. Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003