4. Задача о перевозках.

Имеются складов:

и пунктов потребления:

(см. рис. 2.1).

Рис. 2.1

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

единиц. Пункты потребления подали заявки соответственно на

единиц товара. Заявки выполнимы, т. е. сумма всех заявок не превосходит суммы всех имеющихся запасов:

Склады связаны с пунктами потребления какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара со склада С; в пункт равна

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

Обозначим — количество единиц товара, направляемое со склада в пункт (если с этого склада в этот пункт товары не направляются, ).

Решение (план перевозок) состоит из чисел

образующих прямоугольную таблицу (матрицу). Сокращенно будем обозначать ее . Требуется выбрать такие неотрицательные значения переменных , чтобы были выполнены следующие условия:

1. Емкость складов не должна быть превышена, т. е. общее количество товара, взятое с каждого склада, не должно превышать имеющихся на нем запасов:

или, короче,

2. Заявки, поданные пунктами потребления, должны быть выполнены:

или, короче,

Общая стоимость перевозок L будет равна

или, гораздо короче,

Требуется так выбрать план перевозок , чтобы стоимость L этих перевозок обратить в минимум.

Снова возникает задача, аналогичная рассмотренным ранее: выбрать неотрицательны значения переменных так, чтобы при выполнении условий (1.14), (1.15) линейная функция этих переменных (1.16) достигала минимума.

Некоторая особенность этой задачи, по сравнению с ранее рассмотренными, состоит в том, что не все ограничения, наложенные на переменные, являются линейными неравенствами; а именно, условия (1.15) записаны в виде линейных равенств.

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

Заметим, что при некоторой постановке задачи о перевозках все условия-ограничения задачи становятся равенствами. А именно, если сумма всех заявок равна сумме всех запасов

то неизбежно с каждого склада будет вывезено все, что на нем имеется, и неравенства (1.14), так же как (1.15), превратятся в равенства.

Такая задача о перевозках называется транспортной задачей, и ею мы будем специально заниматься в дальнейшем (см. § 9—14 данной главы).