Математическая модель

Допустим, что имеются, четыре пункта: А₁, А₂, А₃, А₄, на которых сосредоточены запасы определённого вида грузов в количествах а₁, а₂, а₃, а₄единиц. Имеется также три пункта назначения В₁, В₂, В₃, заказавшие соответственно b₁, b₂, b₃ единиц груза. Общая сумма заявок на доставку равна сумме имеющихся запасов:

b₁+ b₂+ b₃= а₁+ а₂+ а₃+ а₄.

Кроме того, известна стоимость перевозки единицы груза из каждого пункта отправления A_iк каждому пункту назначения B_j, где i – номер пункта отправления, а j – номер пункта назначения. Стоимость перевозки из i-го пункта в j-й обозначим c_ij.

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

Составим математическую модель этой задачи. Обозначим элементы решения: x_ij – количество единиц груза, отправленных из A_i –го пункта в B_j–й пункт назначения. Всего получится 12 переменных элементов решения:

х₁₁ х₁₂ х₁₃

х₂₁ х₂₂ х₂₃

х₃₁ х₃₂ х₃₃

х₄₁ х₄₂ х₄₃

Суммарная стоимость перевозок при таких решениях, очевидно, будет равна:

L=c₁₁x₁₁+ c₁₂x₁₂+ c₁₃x₁₃+ c₂₁x₂₁+ c₂₂x₂₂+ c₂₃x₂₃+ c₃₁x₃₁+ c₃₂x₃₂+ +c₃₃x₃₃+ c₄₁x₄₁+ c₄₂x₄₂+ c₄₃x₄₃.

Ограничения, налагаемые на элементы решения, будут двух родов:

во-первых, все заявки должны быть выполнены, т. е.

х₁₁+ х₂₁+ х₃₁+ х₄₁=b₁,

х₁₂+ х₂₂+ х₃₂+ х₄₂=b₁,

х₁₃+ х₂₃+ х₃₃+ х₄₃=b₁;

во-вторых, все имеющиеся грузы должны быть вывезены, т. е.

х₁₁+х₁₂+х₁₃=а₁,

х₂₁+х₂₂+х₂₃=а₂,

х₃₁+х₃₂+х₃₃=а₃,

х₄₁+х₄₂+х₄₃=а₄.

Транспортную задачу принято решать специальными методами. Рассмотрим методы получения опорного решения.