ТЗ с избытком заявок

В пунктах имеются запасы груза пункты подали заявки причем т. е. имеющихся запасов недостаточно для удовлетворения всех заявок.

Требуется составить такой план перевозок, при котором все запасы окажутся вывезенными, а стоимость перевозок — минимальной.

Очевидно, эту задачу также можно свести к обычной ТЗ с правильным балансом, если ввести в рассмотрение фиктивный пункт отправления с запасом равным недостающему запасу:

и положить стоимости перевозок из ПО в любой ПН равными нулю:. При этом какая-то часть заявок на каждом пункте останется неудовлетворенной; будем считать, что она как бы покрывается за счет фиктивного ПО

Таким образом, мы свели ТЗ с избытком заявок к ТЗ с правильным балансом. Заметим, что при этом мы вовсе не заботились о «справедливости» удовлетворения заявок, не налагали никаких условий на то, какую долю своей заявки должен получить каждый ПН — нас интересовали лишь расходы, которые нужно минимизировать.

Если поставить задачу по-иному, например, потребовать, чтобы все; ПН были удовлетворены в равной доле, задача снова сводится к ТЗ с правильным балансом. А именно, нужно поданные заявки «исправить», умножив каждую из них на коэффициент после чего решать ТЗ с правильным балансом.

Можно также поставить задачу о распределении грузов по пунктам назначения с учетом сравнительной важности каждого пункта. При этом доля заявки, которую получает каждый пункт, может быть не одинаковой, как в только что описанном способе, а различной. В этом случае задача также сводится к ТЗ с правильным балансом.

Таблица 13.1

Таблица 13.2

Таблица 13.3

Таблица 13.4

Таблица 13.5

Пример. Решить ТЗ с избытком запасов, условия которой заданы в табл. 13.1.

Решение.

разница ежду запасами и заявками равна

Введением фиктивного с заявкой сводим задачу к ТЗ с правильным балансом (см. табл. 13.2, 13.3, 13.4, 13.5).

План, представленный в табл. 13.5, является оптимальным, так как во всех свободных клетках псевдостоимости не превосходят стоимостей. Согласно этому плаиу, из 50 единиц груза, имеющихся в пункте не перевозятся 32, а остальные 18 направляются в пункт из 40 единиц, имеющихся в пункте не перевозятся, 1 отправляется в пункт и 33 — в пункт Все 20 единиц, имеющихся в пункте направляются в пункт