Фиктивный поставщик

Пример 3. Решить транспортную задачу, заданную таблицей:

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

Запасы груза у поставщиков (40+40+80=160) меньше, чем потребности в нём (70+20+60+60=210) потребителей. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введём дополнительного «фиктивного» поставщика с запасами, равными 210-160=50 ед. Тарифы перевозки единицы груза из пункта ко всем потребителям полагаем равными нулю. В результате получаем закрытую модель транспортной задачи, опорный план перевозок которой получаем по методу минимального элемента.

№					Предложение
Спрос					-

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

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

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

.

- стоимость перевозок, соответствующая оптимальному плану; при этом первому потребителю необходимо дополнительно 30 ед. груза, а четвёртому потребителю 20 ед. груза.

Пример 4. Решить транспортную задачу, заданную следующей таблицей:

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

Составим транспортную таблицу:

№

Предложение

1 -

1 +

  *

  + 0

  - 50

+

-

  *

Спрос

-

Число заполненных клеток равно 5, т.е. данный план вырожденный. При заполнении таблицы одновременно зачёркнуты вторая строка и четвёртый столбец. Клетку (2,3) заполняем нулём. Занятая клетка нужна для того, чтобы можно было определить потенциалы. Нуль можно было также поставить в клетку (3,4) или (2,1), но в этом случае не образуется замкнутый цикл с занятыми клетками; клетку по этой причине заполнять нулём нельзя.

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

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

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

№					Предложение
Спрос					-

Новый план невырожденный. Проверим его на оптимальность.

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

Все разности отрицательные, следовательно, получен оптимальный план.

.

- стоимость перевозок, соответствующая оптимальному плану.

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