Примеры решений Метод Гомори Симплекс-метод Метод Фогеля Транспортная задача Задача о назначениях Распределительный метод Метод потенциалов Задача коммивояжера Открытые и закрытые задачи

Экономические задачи, сводящиеся к транспортной модели

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

Пример. В пунктах отправления А1, А2, А3 находится однородный груз в количестве a1, а2, а3, соответственно, который необходимо перевезти в пункты назначения В1, В2, В3, потребность каждого из которых составляет b1, b2, b3. Известно расстояние между пунктами перевозок (оценки).
Определить такой план перевозок, при котором общее количество тонно-километров будет минимальной.
Входные данные согласно варианту приведены в таблице 3.



1

2

3

Запасы

1

10

15

22

50

2

16

20

11

85

3

18

16

33

52

Потребности

62

81

43

Указание: Составить соответствующую задачу математического программирования, привести ее к закрытому типу и решить методом потенциалов.

Математическая модель транспортной задачи:
F=∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
xij ≥ 0
Запишем экономико-математическую модель для нашей задачи. Переменные:
x11 – количество груза из 1-го склада в 1-й магазин; x12 – количество груза из 1-го склада в 2-й магазин; x13 – количество груза из 1-го склада в 3-й магазин; x21 – количество груза из 2-го склада в 1-й магазин; x22 – количество груза из 2-го склада в 2-й магазин; x23 – количество груза из 2-го склада в 3-й магазин; x31 – количество груза из 3-го склада в 1-й магазин; x32 – количество груза из 3-го склада в 2-й магазин; x33 – количество груза из 3-го склада в 3-й магазин
Ограничения по запасам:
x11 + x12 + x13 ≤ 50 (для 1 базы)
x21 + x22 + x23 ≤ 85 (для 2 базы)
x31 + x32 + x33 ≤ 52 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 62 (для 1 магазина)
x12 + x22 + x32 = 81 (для 2 магазина)
x13 + x23 + x33 = 43 (для 3 магазина)
Целевая функция: 10x11 + 15x12 + 22x13 + 16x21 + 20x22 + 11x23 + 18x31 + 16x32 + 33x33 → min

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

  1. При некоторых реальных условиях перевозки груза из определенного пункта Ai в пункт назначения Bj не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт Bj является сколь угодно большой величиной М и при этом условии известными методами находят решение транспортной задачи. Такой подход к нахождению решения ТЗ называется запрещением перевозок.
  2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в Bj требуется обязательно перевезти aij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки Ai и столбца Bj, записывают указанное число aij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.
  3. Иногда требуется найти решение ТЗ, при котором из Ai в Bj должно быть перевезено не менее заданного количества груза aij. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности Bj меньше фактических на aij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Модель без дефицита

В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.
Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице:

Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = ∑ai - ∑bj. Затраты на единицу продукции в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.
Так как задолженность в модели не допускается, то для каждого этапа k в нее необходимо включить ограничение, состоящее в том, что накопленный спрос не должен превышать соответствующего общего объема произведенной продукции, т.е. ∑ (ari + ati) ≥ ∑bj , k = 1,2,...,N.
Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i+1, i+2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.

Модель с дефицитом

Рассмотрим обобщение описанной выше модели при условии, что допускается дефицит. Предполагается, что задолженный спрос должен быть удовлетворен к концу N-этапного горизонта планирования. Таблицу 1 можно легко модифицировать, чтобы учесть влияние задолженности, введя соответствующие удельные издержки в заблокированные маршруты.
Так, например, если pi – удельные потери от дефицита (т.е. на единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i+1, то удельные расходы, соответствующие ячейкам RN,1 и TR,1, составляют: {cN + p1 + p2 + … + pN-1} и {dN + p1 + p2 + … + pN-1}соответственно.
Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.

Экономические задачи, сводящиеся к транспортной модели

Оптимальное распределение оборудования
Формирование оптимального штата фирмы
Задача календарного планирования производства
Оптимальное исследование рынка
Оптимальное использование рабочих агентов
Задача размещения производства
Задача о назначениях
Военно-прикладная задача линейного программирования
Пусть имеется m различных типов средств поражения (А1, А2,…, Аm) и n различных типов целей (В1, В2,…, Вn) и пусть известна вероятность поражения Pij средством Ai цели Bj. Требуется так распределить средства поражения по целям, чтобы получить максимальное значение математического ожидания числа уничтоженных целей.
Данная задача представляет собой классическую транспортную задачу с целевой функцией на максимум.
Инвестиции с JetLend

Удобный сервис для инвестора и заемщика. Инвестируйте в лучшие компании малого бизнеса по ставкам от 16,9% до 37,7% годовых.
Подробнее
Онлайн-университет
Профессии с трудоустройством. Наши направления:
√ Программирование и Дизайн
√ Маркетинг и Управление
√ Игры и Мультимедиа
Программа курсов
Редактор формул онлайн
Удобный редактор формул для Word, Latex и Web.
Редактор формул онлайн
Подробнее
Курсовые на заказ