Определение транспортной задачи.

Лекция 3 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Определение транспортной задачи.

Решение задачи методом потенциалов

Методы решения задач особого вида

Определение транспортной задачи

Открытая транспортная задача

В открытой задаче сумма запасов не совпадает с суммой потребностей:

.

1. Если , то объем производства превышает объем потребления. Все потребители будут удовлетворены полностью. Еще останется часть невывезенных запасов. Для решения задачи вводят фиктивного потребителя, потребности которого:

.

Формальная постановки задачи в этом случае имеет следующий вид:

.

,

,

где , i = 1, 2, …, n, j = 1, 2, …, m+1.

2. Если , то объем потребления превышает объем производства. Не все потребители будут удовлетворены полностью. Все запасы вывозятся потребителям. Для решения задачи вводят фиктивного производителя, производство которого .

Формальная постановки задачи в этом случае имеет следующий вид:

.

,

,

где: , i = 1, 2, …, n+1, j = 1, 2, …, m.

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

Многопродуктовые транспортные задачи

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

Пример В каждом из двух таможенных терминалов находятся легковые автомобили двух марок. Количество машин j-й марки в i-м терминале равно . Необходимо перевезти на три автосалона. В каждом k-м салоне должно быть машин j-й марки. Затраты на перевозку j-й марки из i-го терминала в k-й автосалон равны . Необходимо найти план при минимальном расходе ресурсов. Исходные данные, необходимые для решения задачи приведены в табл.2, а сетевая модель задачи - на рис.2. Формально модель имеет вид

,

,

,

i = 1, 2, j = 1, 2, k = 1, 2, 3.

Таблица 2

Исходный терминал	марка	Конечный салон
марка	марка	марка	марка
			М		М		М
	М		М		М
			М		М		М
	М		М		М

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

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

Таблица 3 Таблица 4

терминалы	салоны		терминалы	салоны

Рис. 2. Сетевая модель многопродуктовой транспортной задачи

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

Методы решения транспортных задач особого вида

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

Лекция 3 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Определение транспортной задачи.

1234567Следующая ⇒

Поделиться:

Популярное:

1. G) определение путей эффективного вложения капитала, оценка степени рационального его использования
2. GUDEL roboLoop уникальный робот с нелинейной транспортной системой
3. I этап. Определение стратегических целей компании и выбор структуры управления
4. I. ОПРЕДЕЛЕНИЕ И ПРОБЛЕМЫ МЕТОДА
5. III. Определение посевных площадей и валовых сборов продукции
6. VII. Определение затрат и исчисление себестоимости продукции растениеводства
7. X. Определение суммы обеспечения при проведении исследования проб или образцов товаров, подробной технической документации или проведения экспертизы
8. Анализ платежеспособности и финансовой устойчивости торговой организации, определение критериев неплатежеспособности
9. Анализ показателей качества и определение полиграфического исполнения изделия
10. Б.1. Определение психофизиологии.
11. База восстания расширилась, тыл для наступления вверх по Волге был обеспечен. Можно было приступать к решению второй стратегической задачи.
12. Безопасность работы при монтаже конструкций. Опасные зоны при подъеме грузов. Определение габаритов опасных зон.