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

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

Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта (или взаимозаменяемых продуктов) из пунктов производства в пункты потребления.

Экономико-математическая модель транспортной задачи в общем виде может быть сформулирована следующим образом:

Имеется m пунктов производства однородного продукта и n пунктов потребления. Для каждого пункта производства i задан объем производства А_i, для каждого пункта потребления j известна потребность (спрос) В_j (в тех же единицах измерения). Известны издержки с_ij, связанные с перевозкой единицы продукта из пункта i в пункт j.

Требуется составить план перевозок, обеспечивающий наиболее экономным путем (т.е. при наименьших транспортных издержках) удовлетворение всех пунктов потребления за счет реализации всего продукта, произведенного пунктами производства. При этом предполагается, что суммарный спрос (В=å _jВ_j) равен суммарному объему производства (А=å _iА_i). Такие задачи называются закрытыми транспортными задачами.

Что такое план перевозок? План перевозок определяет:

Сколько единиц продукта перевозится от каждого пункта производства к каждому пункту потребления, т.е. план представляется набором чисел х_ij (всего таких чисел m´ n), где х_ij показывает, сколько единиц продукта должно быть перевезено от i-го производителя j-му потребителю. Отметим также, что в термин «транспортные издержки» (с_ij) не всегда вкладывается строгий экономический смысл. Это могут быть расстояния, тарифы, время, расход топлива и т.п. В каждой конкретной задаче оговаривается конкретный смысл коэффициентов с _ij.

Система ограничений примет вид

= А_i (i=1, 2, …, m), (2.3.1)

= В_j (j=1, 2, …n). (2.3.2)

Система (2.3.1) включает в себя уравнения баланса по поставщикам, а система (2.3.2) – по потребителям. Суммарные транспортные издержки выражаются в виде следующей линейной функции, которую необходимо минимизировать

F = à min (2.3.3)

Математическая модель транспортной задачи в общей постановке будет следующей: на множестве неотрицательных решений системы ограничений (2.3.1), (2.3.2) (мы будем называть такие решения допустимые) найти такое решение Х=(х₁₁, х₁₂, …, х_ij, …, х_mn), при котором значение целевой функции (2.3.3) минимально. Условия транспортной задачи весьма удобно представлять в табличной форме.

Таблица 2.3.1

Пункт произ- водства i	Объем произ- водства Аi	Пункты потребления j и их спрос Вj
		…	n
В1	В2	…	Вn
	А1	с11 х11	с12   х12	…	с1n   х1n
	А2	с21   х21	с22   х22	…	с2n   х2n
…	…	…	…	…	…
m	Аm	сm1   хm1	сm2   хm2	…	сmn   хmn

В левом верхнем углу произвольной клетки (i, j) (i – номер строки, j–номер столбца) стоит показатель транспортных затратс_ij, в правом нижнем – значения переменных х_ij(план перевозок). Любое решение Х=(х₁₁, х₁₂, …, х_ij, …, х_mn) системы ограничений (2.3.1) – (2.3.2) назовем распределением поставок.

Простой модификацией данной модели является модель процесса назначения. Речь идёт о назначении m различных специалистов на n мест работы при условии, что каждую работу должен выполнять лишь один специалист, и каждый специалист должен выполнять лишь одну работу. Приоритетная возможность i-го специалиста на получение j-й работы оценивается коэффициентами c_ij матрицы С. При моделировании таких процессов x_ij вводится как булевская переменная:

x_ij=

Правые части всех ограничений в этом случае равны 1.

А_i =1 (i=1, 2, …, m), В_j =1 (j=1, 2, …n).

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

Можно указать достаточно много практических задач, решение которых может быть сведено к решению задачи о назначениях (распределние самолетов по авиалиниям, распределение министерских портфелей и т.п.).

Многими математиками, начиная с Халмоша, предлагалось использовать задачу о назначениях для составления супружеских пар (MarriageProblem), трактуя коэффициенты c_ij как " меру счастья" будущего союза. Правда, постановка задачи выглядела несколько искусственной, так как каждый раз приходилось фантазировать, чтобы оправдать необходимость массовых бракосочетаний. Однако реальная жизнь оказалась богаче подобных фантазий и основатель " Церкви унификации" кореец Сон Мьюонг Мун (он же Мун Сон Мен или просто Мун) уже около пятидесяти лет каждый год решает подобную задачу для тысяч своих последователей.

Рассмотрим простейший числовой пример транспортной задачи (таб. 2.3.2).

Здесь параметры задачи принимают следующие значения:

с₁₁ =2, с₁₂ =1, с₁₃ =5, с₂₁ =3, с₂₂ =4, с₂₃ =3, с₃₁ =4, с₃₂ =6, с₃₃=6;

А₁ =50, А₂ =60, А₃ =70, В₁ =40, В₂ =85, В₃=55.

Таблица 2.3.2

	2 х11	1 х12	5 х13
	3 х21	4 х22	х23
	4 х31	х32	6 х33

Составим систему уравнений для этого примера.

Чтобы объем производства каждого поставщика был реализован, необходимо выполнение баланса по каждой строке таблицы, т.е.

х₁₁ + х₁₂ + х₁₃ =50

х₂₁ + х₂₂ + х₂₃ = 60 (2.3.4)

х₃₁ + х₃₂ + х₃₃= 70

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса выписываем для каждого столбца таблицы:

х₁₁ + х₂₁ + х₃₁ = 40

х₁₂ + х₂₂ + х₃₂ = 85 (2.3.5)

х₁₃ + х₂₃ + х₃₃= 55

Суммарные транспортные затраты F ( целевая функция ) выражаются через издержки и поставки следующим образом:

F = 2х₁₁ + х₁₂ +5х₁₃ +3х₂₁ +4х₂₂ +3х₂₃ +4х₃₁ +6х₃₂ +6х_33.

В этом примере шесть уравнений и девять переменных, система (2.3.4)–(2.3.5) имеет бесчисленное множество решений (допустимых поставок). Вот одно из них:

Таблица 2.3.3

	2	1	5
	3	4
	4	15	6

Суммарные транспортные затраты для данного распределения:

F = 2´ 40 +1´ 10 + 5´ 0 + 3´ 0 +4´ 60 + 3´ 0+4´ 0 + 6´ 15 + 6´ 55=750.

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

Вот еще одна допустимая поставка:

Таблица 2.3.4

	2	1	5
	3	4
	4	35	6

Суммарные транспортные затраты для данного распределения:

F = 1´ 50 + 3´ 40 +3´ 20 + 6´ 35 + 6´ 35=650.

Наша задача научиться находить оптимальное решение, т.е. такое, для которого целевая функция имеет наименьшее значение.

2.3.2. Исходный опорный план.

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

“Правило северо-западного угла” формулируется следующим образом:

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

х₁₁ =miní А₁, В₁ý.

2. Следующую максимально возможную поставку дать либо в клетку (1, 2), либо в клетку (2, 1), в зависимости от результата первого шага.

3. Продолжить этот процесс шаг за шагом от северо-западного до юго-восточного угла таблицы.

Таким образом, в нашем примере (см. табл. 2.3.3) процесс определения исходного плана происходит следующим образом:

В клетку (1, 1) даем максимально возможную поставку:

х₁₁ =miní 50, 40ý =40.

После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы выпадает из последующего рассмотрения. Переходим к клетке (1, 2) и даем в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 40 единиц своей продукции и у него осталось только 50 – 40 = 10 единиц, получим х₁₂ =miní 10, 85ý =10. После этого объемы 1-го производителя полностью реализованы и из рассмотрения выпадает первая строка таблицы. В оставшейся таблице снова находим «северо-западный угол» и т.д. В результате получаем исходное распределение поставок (см. табл. 2.3.3).

Число заполненных клеток в полученном распределении оказалось равным m+n–1=3+3–1 = 5. Это не случайно. Действительно, на каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец и строка.

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

Существенный недостаток метода “северо-западного угла” состоит в том, что он построен без учета значений транспортных издержек. Можно модифицировать данный метод, избавившись от этого недостатка: на каждом шаге максимально возможную поставку следует давать не в “северо-западную” клетку оставшейся таблицы, а в клетку с наименьшим значением транспортных издержек. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное методом “северо-западного угла”. Такой метод получения исходного плана называется методом наименьших затрат. Исходный план, полученный данным методом, приведен в табл. 2.3.4.

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться:

Популярное:

1. A. затраты АТП на выполнение перевозок в денежной форме, расчитанные на единицу транспортной продукции.
2. I. Составить схему транспортной классификации грузов.
3. II. Исходное состояние в области транспортной безопасности
4. II. Исходное состояние в области транспортной безопасности
5. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
6. Алгоритм решения транспортной задачи
7. Информационное обеспечение транспортной безопасности
8. ИСТОРИЯ ГИГИЕНЫ И ЭКОЛОГИЯ. 1. Гигиена и санитария. Цель, задачи.
9. Место транспортного обеспечения и транспортной логистики в коммерческой деятельности предприятия
10. Нахождение максимального потока в транспортной сети алгоритмом Форда-Фалкерсона.
11. Перспективы расширения транспортной системы в Казахстане
12. Понятие и виды финансового контроля, его принципы и задачи. Методы финансового контроля.