[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3]

Экономико-математическая модель транспортной задачи.

Важным частным случаем задачи линейного программирования является транспортная задача.

Задача 7.1

Построить экономико-математическую модель следующей задачи. Имеются три поставщика и четыре потребителя. Мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик - потребитель" сведены в таблицу поставок Таблица 7.1 Поставщики Мощность поставщиков Потребители и их спрос 1 2 3 4 20 110 40 110 1 60 1    x11 2    x12 5    x13 3    x14 2 120 1    x21 6    x22 5    x23 2    x24 3 100 6    x31 3    x32 7    x33 4    x34 В левом верхнем углу произвольной (i, j)-клетки (i - номер строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика к j-му потребителю, например, в левом верхнем углу клетки (1,4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денежных единицы и т. д. Задача ставится следующим образом. Найти объемы перевозок для каждой пары "поставщик - потребитель " так, чтобы: 1) мощности всех поставщиков были реализованы; 2) спросы всех потребителей были удовлетворены; 3) суммарные затраты на перевозку были бы минимальны. Решение. Построим экономико-математическую модель данной задачи. Искомый объем перевозки от i-го поставщика к j-му потребителю обозначим через xij и назовем поставкой клетки (i, j). Например, x12 - искомый объем перевозки от 1-го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных xij. Так, например, объем груза, забираемого от 1-го поставщика, должен быть равен мощности этого поставщика - 60 единицам, т.е. x11 + x12 + x13 + x14 = 60 (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е. x11 + x12 + x13 + x14 = 60 x21 + x22 + x23 + x24 = 120 x31 + x32 + x33 + x34 = 100        (7.1) Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок: x11 + x21 + x31 = 20 x12 + x22 + x32 = 110 x13 + x23 + x33 = 40 x14 + x24 + x34 = 110        (7.2) Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что Xij >= 0 (i = 1,2,3; j = 1,2,3,4). Суммарные затраты Z на перевозку выражаются через коэффициенты затрат и поставки следующим*образом: Z = 1 x11 + 2 x12 + 5 x13 + 3 x14 + 1 x21 + 6 x22 + 5 x23 + 2 x24 + 6 x31 + 3 x32 + 7 x33 + 4 x34.         (7.3)

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу). На множестве неотрицательных решений системы ограничений (7.1) и (7.2) найти такое решение Х = (x₁₁, x₁₂, ..., x₃₃, x₃₄), при котором линейная функция (7.3) принимает минимальное значение.

Особенности экономико-математической модели транспортной задачи:
- система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме); - коэффициенты при переменных системы ограничений равны единице или нулю; - каждая переменная входит в систему ограничений два раза: один раз - в систему (7.1) и один раз - в систему (7.2)

Для математической формулировки транспортной задачи в общей постановке обозначим через c_ij коэффициенты затрат, через М_i - мощности поставщиков, через N_j - мощности потребителей, где i = 1, 2, ..., m; j= 1, 2, .... n; m - число поставщиков, n - число потребителей. Тогда система ограничений примет вид

       (7.4)

       (7.5)

Система (7.4) включает в себя уравнение баланса по строкам, а система (7.5) - по столбцам таблицы поставок. Линейная функция в данном случае

       (7.6)

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (7.4), (7.5) найти такое решение Х = (x₁₁, x₁₂, ..., x_ij,: x_mn), при котором значение линейной функции (7.6) минимально.
Произвольное допустимое решение Х = (x₁₁, x₁₂, ..., x_ij,: x_mn) системы ограничений (7.4), (7.5) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной x_ij и содержимое соответствующей клетки таблицы поставок будут отождествляться.
Транспортная задача, приведенная в примере 7.1, обладает важной особенностью: суммарная мощность поставщиков равна суммарной мощности потребителей, т.е.

       (7.7)

Такие транспортные задачи называются закрытыми (говорят также, что транспортная задача в этом случае имеет закрытую модель). В противном случае транспортная задача называется открытой (открытая модель транспортной задачи).
Рассмотрим закрытую транспортную задачу. Являясь задачей линейного программирования, транспортная задача может быть решена симплексным методом. Однако специфичная форма системы ограничений данной задачи позволяет существенно упростить обычный симплексный метод. Модификация симплексного метода применительно к транспортной задаче называется распределительным методом. По аналогии с общим случаем решение в нем осуществляется по шагам, и каждому шагу соответствует разбиение переменных на основные (базисные) и неосновные (свободные).
Число r основных переменных транспортной задачи равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).

Теорема 7.1
Ранг r системы уравнений (7.4), (7.5) при условии (7.7) равен m + n - 1

Основное следствие теоремы 7.1 -

число r основных (базисных) переменных закрытой транспортной задачи равно m + n - 1, где m - число поставщиков, n - число потребителей.

Каждому разбиению переменных x_ij задачи на основные (базисные) и неосновные (свободные) соответствует базисное решение и, как следствие, заполнение таблицы поставок, которое также назовем базисным. Иными словами,

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

Поскольку в дальнейшем мы используем исключительно базисные распределения поставок, то термины "базисная клетка" и "заполненная клетка" будут считаться равнозначными.
Подобно тому, как это было в симплексном методе, в распределительном методе решения транспортной задачи будем переходить от одного базисного распределения поставок к другому в сторону невозрастания целевой функции вплоть до оптимального решения. Для начала такого движения потребуется исходное базисное распределение поставок - так называемый опорный план.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [В начало страницы]