Тема: “ Определение оптимального плана

Лекция 11

транспортных задач,

имеющих некоторые усложнения в их постановке”

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

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

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

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

4. В некоторых транспортных задачах требуется найти оптимальный план перевозок при условии, что из пункта отправления в пункт назначения должно быть завезено не более заданного количества груза , т.е. . Столбец разбивается на два столбца: в первом столбце спрос принимается равным разности между действительным спросом и ограничением, во втором – равным ограничению. Затраты в обоих столбцах одинаковы и равны данным, но в первом столбце вместо истинного тарифа ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.

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

Пункты отправления	Пункты назначения	Запасы
Потребности

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

№

Запасы

 

2 М  

3 -

4 +

 

6 М  

+ 30

2 М   - 50

 

Спрос

Опорный план составлен по методу минимального элемента. Проверим его на оптимальность.

Составим разности для свободных клеток:

Среди оценок есть два положительных числа, соответствующих клеткам и , следовательно, план неоптимальный. Строим для клетки цикл пересчёта.

№						Запасы
		2 М
	6 М		+		2 М - 20
			- 100		+
Спрос

Проверим полученный план на оптимальность.

Составим разности для свободных клеток:

Среди оценок есть четыре положительных числа, соответствующих клеткам , , и , следовательно, план неоптимальный. Строим для клетки цикл пересчёта.

№						Запасы
		2 М
	6 М				2 М
Спрос

Проверим план на оптимальность.

Составим разности для свободных клеток:

Среди оценок нет положительных, следовательно, план оптимальный.

Дата добавления: 2014-01-11