Транспортная задача с правильным балансом и неправильным балансом

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

Дадим транспортной задачи матричную формулировку:

Через обозначим количество груза, отправляемого из i-го пункта отправления , в j-ый пункт назначения

Неотрицательная переменная должна удовлетворять следующим условиям:

1. Суммарное количество груза направляемое из каждого пункта, оправляется во все пункты назначения, должно быть равно запасу груза в данном пункте.

() (3.14)

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

() (15)

3. Целевая функция – суммарная стоимость всех перевозок, должна быть минимальной.

(16)

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

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

1. Сумма запасов в пункте оправления превышает сумму поданных заявок.

2. Сумма поданных заявок превышает наличие запасов.