3.1 Целевые задачи:

знать: формулировку транспортной задачи, методы отыскания опорных решений: «метод северо-западного угла», минимального элемента;

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

4. Краткие сведения из теоретического курса.

Имеются несколько пунктов (четыре) А₁, А₂, А₃,А₄ на которых имеются запасы определенного вида грузов в количествах а₁, а₂, а₃, а₄ единиц. Имеется также три пункта назначения в₁, в₂, в₃, заказавшие соответственно b₁, b₂, b₃ единиц груза. Общая сумма заявок на доставку равна сумме запасов: . Кроме того, известна стоимость перевозки единицы груза из каждого пункта отправленияА_i к каждому пункту назначения В_j, где i – номер пункта отправления, a j– номер пункта назначения. Стоимость перевозки из i-того пункта в j-й обозначим с_ij.

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

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

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

Допустим, что имеются, четыре пункта: А₁, А₂, А₃, А₄, на которых сосредоточены запасы определённого вида грузов в количествах а₁, а₂, а₃, а₄единиц. Имеется также три пункта назначения В₁, В₂, В₃, заказавшие соответственно 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₁;

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

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

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

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

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

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

Построение опорного плана

Сущность методов, получения опорного плана, заключается в выполнении m+n-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, заполнение этой клетки обеспечивает полностью либо удовлетворение потребности в грузе одного пункта назначения (того, в столбце которого находится заполненная клетка), либо вызов груза из одного пункта отправления (из того, в строке которого находится заполненная клетка). Рассмотрим эти методы.