Открытая транспортная задача

Date: 2015-10-07; view: 483.

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

1) . Задача сводится к закрытой задаче введением фиктивного поставщика с запасом груза = . Груз, соответствующий поставкам от , останется недополученным потребителями.

2) . Задача сводится к закрытой задаче введением фиктивного потребителя с потребностями в грузе = . Соответствующие ему значения в оптимальном плане будут означать оставшийся не отправленным груз поставщиков.

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

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

Прежде всего проверим, является ли поставленная задача закрытой.

50+70+60=180; 60+60+50=170, ,следовательно, это открытая задача второго типа. Введем фиктивного потребителя =В₄, потребность в грузе которого примем равной =180 –170=10, цены единичных перевозок от поставщиков фиктивному потребителю считаем равными нулю, т.е. . Задача становится закрытой, ей соответствует таблица 12.

Составим начальный план методом наименьшей стоимости.

Делаем поставку в клетку (1;3) x₁₃=50, исключаем из рассмотрения первую строку и третий столбец (можно было сделать эту поставку и в (2;4)). Для клетки (2;2) x₂₂=60, во

втором столбце ставим прочерк, у остается 10 единиц груза. Отдаем их , x₂₁=10. У остается потребность 50 единиц, запишем их в (1;1), x₃₁=50. Тогда оставшиеся 10

Таблица 12.

единиц у пойдут , x₃₄=10. Начальный план записан в таблице 13.

Таблица 13. План .

	— +	—	-50	—
	10 -	60	+0	—
		—	—
Vj				-2

F(Х₁)=

Проверим количество заполненных клеток. Для нашей задачи их число должно составлять 3+4–1=6, а в нашем плане только 5, т.е. план вырожден. Поставим 0 в любую пустую клетку, не образующую цикла с уже заполненными клетками, например в (2;3). (Нельзя заполнить нулем клетки (2;4), т.к. образуется цикл (2;4) (3;4) (3;1) (2;1) (2;4) или (2;3) цикл (3;2) (3;1) (2;1) (2;2) (3;2))

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

Определим потенциалы, полагая U₁ =0. Для заполненных клеток:

(1;3): , V₃=2;

(3;2): U₂+2= 2, U₂ = 0;

(2;2): 0+ V₂= 3, V₂= 3;

(2;1): 0+ V₁=4, V₁=4;

(3;1): U₃ +4= 6, U₃= 2;

(4;1): U₄+2 = 0, U₄= –2.

Найдем оценки пустых клеток:

Поскольку среди оценок есть отрицательная, план может быть улучшен.

Для клетки (1;1) строим цикл пересчета, расставляем знаки в вершинах цикла. Определяем =min{10;60}=10, прибавляем это значение к перевозкам в клетках, помеченных знаком «+», вычитаем из перевозок в клетках, имеющих знак «–». Получаем новый план X₂, представленный в таблице 14.

Таблица 14. План X₂.

	10 +	—	- 40	—
	—	60	10	—
	50 -	—	+ —
Vj				-3

= + =620+10(-1)=610.

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

Для заполненных клеток, считая U₁ =0, определяем потенциалы:

(1;1): 0+V₁=3, V₁=3;

(1;3): , V₃=2;

(3;2): U₂+2= 2, U₂ = 0;

(2;2): 0+ V₂= 3, V₂= 3;

(3;1): U₃ +3= 6, U₃= 3;

(4;1): U₄+3 = 0, U₄= –3.

Для пустых клеток найдем оценки:

Поскольку одна из оценок отрицательна, план может быть улучшен.

Строим цикл для клетки (3;3). =min{40;50}=40. План представлен в табл.15.

Таблица 15. План .

		—	—	—
	—	60	10	—
		—
Vj				-3

= + =610+40(-1)=570.

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

Найдем потенциалы: U₁ =0,

(1;1): 0+V₁=3, V₁=3;

(3;1): U₃ +3= 6, U₃= 3;

(3;3): 3+ V₃= 4, V₃= 1;

(3;4): 3+V₄=0, V₄=3;

(2;3): U₂+1=2, U₂=1;

(2;1): 1+V₂ = 3, V₂=2.

Оценки пустых клеток:

Для плана X₃ условие оптимальности (8) выполняется, следовательно, план X₃ является оптимальным.

Запишем ответ задачи:

X₃= .

Поскольку последний столбец оптимального плана соответствует фиктивному потребителю, из окончательного ответа он должен быть исключен. Отброшенное значение x₃₄=10 означает, что 10 единиц груза поставщика А₃ останутся нераспределенными. Окончательный ответ —

, F (X^*)=570.