Математична модель транспортної задачі

МЕТОДИ РОЗВ’ЯЗАННЯ ТРАНСПОРТНОЇ ЗАДАЧІ

ЗАВДАННЯ 3. У трьох пунктах виробництва А₁, А₂, А₃ зосереджений однорідний вантаж у кількостях відповідно рівних а₁, а₂, а₃ тонн. Даний вантаж споживається в чотирьох пунктах В1, В₂, В₃, В₄, а потреби в ньому в цих пунктах складають b₁, b₂, b₃, b₄, тонн відповідно. Відома матриця тарифів по перевезенню 1 тони вантажу з i ^го пункту виробництва до j ^го пункту споживання:

.

Скласти план перевезень:

,

при якому сумарні транспортні витрати будуть мінімальними.

Розв’язати поставлену транспортну задачу

3.1 методом потенціалів,

3.2 за допомогою інструмента «Поиск решения».

Розглянемо поставлену задачу для таких вихідних даних:

30т, 20т, 40т,

20т, 30т, 20т, 30т,

.

Запишемо їх у вигляді таблиці.

Таблиця 3.1

Пункти виробництва	Пункти споживання	Запаси
Потреби

До нижнього правого куту цієї таблиці занесемо значення сумарних потреб і сумарних витрат:

т, т.

У даному випадку , тому модель транспортної задачі є відкритою. Відповідно до теореми, для існування в транспортної задачі припустимого плану необхідно і достатньо, щоб її модель була закритою, тобто, щоб .

Збалансуємо дану задачу, уводячи фіктивний пункт виробництва з запасом вантажу =100-90=10(т). При цьому вартість перевезень із цього пункту в кожний із пунктів споживання дорівнює 0 (див. табл. 3.2).

Таблиця 3.2

Пункти виробництва	Пункти споживання	Запаси
Потреби

Складемо математичну модель даної задачі.

1. Змінні задачі: – планований обсяг перевезення (у тоннах) з ^го пункту виробництва в ^й пункт споживання (, ). Сукупність змінних утворить матрицю

.

2. Цільова функція задачі виражає транспортні витрати, які необхідно мінімізувати:

.

3. Обмеження задачі: на вивіз вантажу

, (9)

на задоволення потреб у вантажі

, (10)

невід’ємність змінних:

(, ). (11)

Сукупність змінних , що задовольняють обмеженням (9)-(11), утворюють припустимий опорний план. Матриця системи (9) ‑ (10) має ранг на 1 менший кількості рядків цієї системи, тобто на 1 менший від суми кількостей пунктів виробництва і пунктів споживання, у даному випадку це – 7. Це означає, що кількість базисних змінних повинна дорівнювати 7.

Дата добавления: 2014-12-08