Матричные транспортные задачи Мтз (примеры)

Наимен. Мастерских	Стоимость перевозок	Мощность заводов
Наимен. Заводов	B1	B2	B3
A1	1	3	2	25
A2	3	5	8	10
A3	2	7	4	30
A4	5	3	6	20
Потребности мастерских	30	40	15

Табл. 4.1

Матричные транспортные задачи

Пример 4.1. На четырех заводах A1,..., A4 изготавливают детали для станков, которые затем отправляют в три мастерские B1, B2, B3. Стоимость перевозок (в ед. е./шт.), мощность заводов и потребности мастерских (в тыс. шт.) приведены в табл. 4.1. Требуется так спланировать распределение деталей между мастерскими, чтобы расходы на перевозку были минимальными.

Построим математическую модель задачи. Обозначим через Xij, , количество деталей, отправляемых заводом Ai мастерской Bj. Как в §3, стоимость перевозок обозначается через Cij (данные приведены в табл. 4.1). Из постановки задачи следует, что требуется минимизировать общие расходы на перевозку

(4.1)

При следующих ограничениях: все детали из всех заводов должны быть вывезены

(4.2)

И спрос на детали всех мастерских должны быть удовлетворен

(4.3)

Кроме того, из физического смысла величин Xij следует:

Xij³0, , (4.4)

В (4.1) через X обозначим вектор X=(Xij, , ).

Соотношения (4.1)—(4.4) представляют математическую модель рассматриваемой задачи.

Пример 4.2. Рассмотрим задачу примера 4.1. Составим транспортную таблицу, исходя из данных табл. 4.1.

Заполняем клетку (1,1), поместив в нее перевозку X11=min{25,30}=25 и вычеркиваем первую строку. В уменьшенной таблице заменяем B1=30 на =30-25=5. Далее заполняем клетку (2,1) X21=min{10,5}=5 и вычеркиваем первый столбец, заменив A2=10 на =10-5=5, В уменьшенной таблице заполняем клетку (2,2) X22=min{5,40}=5 и вычеркиваем вторую строку, заменив B2=40 на =40-5=35, и т. д. В итоге получим базисный план перевозок с базисным множеством клеток UБ={(1,1), (1,2), (2,2), (3,2), (4,2), (4,3)}. При этом стоимость перевозок равна j=1×25+3×5+5×5+7×30+3×5+6×15=380 (д. е.).

Пример 4.3. Для задачи примера 4.1. построим начальный базисный план перевозок по правилу минимального элемента

Выбираем клетку с минимальной стоимостью . Такой является клетка (1,1). Помещаем в нее перевозку X11=min{25,30}=25 и вычеркиваем первую строку, уменьшив заменяем B1=30 на =30-25=5. В уменьшенной таблице опять выбираем клетку с минимальной стоимостью. Такой будет клетка (3,1). Заполняем ее: X31=min{30,5}=5. Затем заполняется клетка (4,2): X42=min{20,40}=20 и т. д. Базисное множество клеток UБ={(1,1), (2,2), (3,1), (3,2), (3,3), (4,2)} отличается от построенного в примере 4.2. Стоимость перевозок равна j=1×25+5×10+2×5+7×10+4×15+3×20=275 (д. е.), т. е. построенный базисный план перевозок намного лучше, чем в предыдущем случае, когда построение проводилось по правилу северо-западного угла.

Пример 4.4. Построим начальный базисный план перевозок для примера 4.1 по правилу двойного предпочтения.

В первой строке минимальный элемент (минимальная стоимость) расположена в клетке (1.1), во второй — в клетке (2,1), в третьей — в (3,1), в четвертой — в (4,2). Аналогично получаем, что в первом столбце минимальный элемент находится в клетке (1,1), во втором столбце — в клетках (1,2), (4,2), в третьем — в (1,3). Клетки (1,1), (4,2) оказались помеченными дважды. В них в первую очередь и помещаем перевозки: X11=min{25,30}=25, уменьшаем таблицу, вычеркиванием первой строки и заменой B1=30 на =30-25=5; X42=min{20,40}=20 уменьшаем таблицу вычеркиванием четвертой строки и заменой B2=40 на =40-5=35. В уменьшенной таблице остались помеченными один раз клетки (2,1), (3,1). По очереди заполняем их каждый раз выбирая клетку с минимальным элементом. В нашем случае сперва заполняем клетку (3,1), где стоимость C31=2<C21=3: X31=min{30,5}=5, Поскольку при этом вычеркивается первый столбец, то помеченная клетка (3,1) остается незаполненной, как оказались незаполненными и помеченные клетки (1,2), (1,3). Оставшуюся часть таблицы заполняем по правилу минимального элемента. В итоге получим клеток UБ={(1,1), (2,2), (3,1), (3,2), (3,3), (4,2)}.

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

Пример 4.5. Пусть имеются следующие данные

Ai : 80, 200, 180, 280;

Bj : 180, 180, 100, 80, 200;

Построим начальный базисный план перевозок по правилу минимального элемента и правилу двойного предпочтения.

Как видим в первом случае клеток SБ={(1,4), (2,1), (2,2), (3,4), (3,5), (4,2), (4,3), (4,5)}, во втором — SБ={(1,4), (2,1), (2,3), (2,4), (3,5), (4,2), (4,3), (4,5)}. Они отличаются друг от друга. При этом стоимость перевозок в первом случае равна j=3380, во втором — j=3360, т. е. план перевозок, построенный по правилу двойного предпочтения, лучше чем по правилу минимального элемента. Однако этот пример не гарантирует, что так будет всегда.

Отметим здесь одну особенность. При построении начального базисного плана перевозок в обоих случаях оказалось, что X14=A1=B4=80. При уменьшении таблицы вычеркиваем при этом лишь строку или столбец, но не одновременно (в таблицах удалена первая строка, а B4=80 заменено на ), чтобы потом заполнить нулем еще одну клетку. В итоге получились вырожденные планы перевозок.

Пример 4.6. Рассмотрим задачу примера 4.1. Используем для решения начальный базисный план перевозок, построенный по правилу минимального элемента или по правилу двойного предпочтения: в данном случае они одинаковы. Найдем потенциалы строк и столбцов. Поскольку наибольшее количество заполненных клеток в третьей строке, полагаем U3=0. Тогда остальные потенциалы определяются однозначно. Так из уравнений U3+V1=C31, U3+V2=C32, U3+V3=C33 находим V1=2, V2=7, V3=4. После этого из уравнений U1+V1=C11, U2+V2=C22, U4+V3=C43 находим U1=-1, U2=-2, U4=-4.

Подсчитываем потенциалы небазисных клеток. Значения записываем в правом нижнем углу клеток (I,J). Поскольку условия оптимальности не выполняются (D12=3>0, D13=1>0), то план перевозок не оптимален и переходим к построению нового базисного плана перевозок. Для этого добавим к базисным клеткам клетку (I0,J0)=(1,2) с максимальной оценкой D12=3. Образуется цикл {(1,2), (1,1), (3,1), (3,2), (1,2)}. Клетке (1,2) приписываем знак «+», а дальше чередуем со знаком «-». Из клеток со знаком «-» выбираем ту, в которой находится минимальная перевозка: . На следующей итерации в базисе будет клетка (I0,J0)=(1,2) вместо клетки (I*,J*)=(3,2). Новый базисный план перевозок получаем из старого добавлением =10 к перевозкам в клетках цикла со знаком «+» и вычитанием =10 из перевозок в клетках цикла со знаком «-». Остальные перевозки оставляем прежними.

Стоимость перевозок стала равной j1=245, т. е. уменьшилась на величину Dj=j-j1=275-247=30. Как показывают вычисления потенциалов и оценок для нового плана перевозок, он опять не оптимален: D13=1>0. Поэтому строим новый план, который является оптимальным: все . Стоимость перевозок равна: jmin=230.