Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





Одной из характерных задач ЛП является так называемая транспортная задача. Она возникает при разработке наиболее рациональных способов и путей транспортирования товаров, устранение встречных, повторных и слишком дальних перевозок. А это сокращает время продвижения товаров и уменьшает затраты предприятий, осуществляющих процессы снабжения сырьём, топливом, оборудованием и т.д. Различают два вида транспортных задач: по критерию стоимости и по критерию времени.

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

Сформулируем транспортную задачу.

Определить оптимальный план перевозок некоторого однородного груза от m поставщиков A1, A2, …Am к n потребителям B1, B2, …Bn, причём стоимость перевозки 1 ед. груза (тариф) из пункта A i, в пункт B j равна cij.

Введём обозначения:

a i – запасы грузы в пункте отправления Ai

bj – величина заказа на этот груз в пункте назначения Bj

cij – тарифы перевозок из Ai в Bj

xij – количество груза, доставленного из Ai в Bj.

 

В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нём транспортные задачи могут быть закрытыми и открытыми.

Определение. Транспортная задача называется закрытой, если в противном случае задача называется открытой.

Условия транспортной задачи обычно задаются распределительной таблицей.

Математическая модель закрытой задачи имеет вид:

при ограничениях

т.е. от каждого поставщика будет вывезен весь груз в объёме данного ресурса,

т.е. каждому потребителю будет доставлен весь груз в объеме его потребности,

и условии

Оптимальным решением этой задачи является матрица , удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

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

Основные этапы решения транспортной задачи:

а) нахождение исходного опорного решения,

b) проверка этого решения на оптимальность,

c) переход от одного опорного решения к другому.

 

Нахождение исходного опорного плана.

Существует несколько способов нахождения исходного опорного плана: метод северо-западного угла, метод минимальной стоимости.

Опишем применение этих методов на примере транспортной закрытой задачи, заданной распределительной таблицей:

Табл.13

bj a i      
       
       
       


По методу северо-западного угла вначале получают значение перевозки x 11, которая расположена в северо-западной клетке матрицы перевозок. Причём x11 присваивается максимально возможное значение, . После этого вычеркивают соответствующий столбец (строку), так как остальные перевозки из этого столбца (строки) должны быть равны 0. Если a 1=b1, должны быть вычеркнуты и первый столбец, и первая строка. Затем корректируют запасы (потребности) невычеркнутой строки (столбца), и все повторяется для северо-западной клетки оставшейся матрицы. Исходное опорное решение представляется таблицей:

Табл. 14

bj a i      
  34 3 2
  13 45 4
  1 22 103

 

Значение целевой функции

По методу минимальной стоимости вначале заполняется перевозка xij с минимальной стоимостью cij. Если минимальных стоимостей несколько, выбирается произвольная переменная. Выбранной перевозке присваивается максимально возможное значение, xij=min(a i,bj). Затем вычеркивается соответствующий столбец (строка), корректируется потребность (запас) не вычеркнутого столбца(строки) и всё повторяется сначала. Тогда исходное решение представляется таблицей:

 

 

Табл. 15

bj a i      
  4 3 32
  3 5 54
  41 62 23

 

Очевидно, что полученные затраты на перевозки по плану, составленному методом наименьшей стоимости, ниже затрат по плану, составленному методом северо-западного угла.

Следовательно, второй план перевозок ближе к оптимальному.

 

Date: 2015-12-12; view: 385; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию