4. Задача о перевозках.
Имеются 
складов:
и 
пунктов потребления:
(см. рис. 2.1).
Рис. 2.1
Речь идет о составлении плана перевозок со складов 
в пункты 
некоторого товара. На складах 
имеются запасы товара в количествах
единиц. Пункты потребления 
подали заявки соответственно на
единиц товара. Заявки выполнимы, т. е. сумма всех заявок не превосходит суммы всех имеющихся запасов:
Склады 
связаны с пунктами потребления 
какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара со склада С; в пункт 
равна 
Требуется составить план перевозок, т. е. указать, с какого склада в какие пункты и какое количество товара нужно направлять так, чтобы заявки были выполнены, а общие расходы на все перевозки были минимальными.
Обозначим 
— количество единиц товара, направляемое со склада 
в пункт 
(если с этого склада в этот пункт товары не направляются, 
).
Решение (план перевозок) состоит из 
чисел 
образующих прямоугольную таблицу (матрицу). Сокращенно будем обозначать ее 
. Требуется выбрать такие неотрицательные значения переменных 
, чтобы были выполнены следующие условия:
1. Емкость складов не должна быть превышена, т. е. общее количество товара, взятое с каждого склада, не должно превышать имеющихся на нем запасов:
или, короче,
2. Заявки, поданные пунктами потребления, должны быть выполнены:
или, короче,
Общая стоимость перевозок L будет равна
или, гораздо короче,
Требуется так выбрать план перевозок 
, чтобы стоимость L этих перевозок обратить в минимум.
Снова возникает задача, аналогичная рассмотренным ранее: выбрать неотрицательны значения переменных 
так, чтобы при выполнении условий (1.14), (1.15) линейная функция этих переменных (1.16) достигала минимума.
Некоторая особенность этой задачи, по сравнению с ранее рассмотренными, состоит в том, что не все ограничения, наложенные на переменные, являются линейными неравенствами; а именно, условия (1.15) записаны в виде линейных равенств.
В дальнейшем мы будем встречаться с задачами линейного программирования, в которых ограничительные условия имеют как вид линейных неравенств, так и равенств, и научимся с легкостью переходить от одних к другим и обратно.
Заметим, что при некоторой постановке задачи о перевозках все условия-ограничения задачи становятся равенствами. А именно, если сумма всех заявок равна сумме всех запасов
то неизбежно с каждого склада будет вывезено все, что на нем имеется, и неравенства (1.14), так же как (1.15), превратятся в равенства.
Такая задача о перевозках называется транспортной задачей, и ею мы будем специально заниматься в дальнейшем (см. § 9—14 данной главы).
