Курсовая на тему Усложненные транспортные задачи

Содержание


Введение 3
Глава 1. Постановка транспортные задачи линейного программирования 4
Глава 2. Методы решения транспортной задачи 7
2.1. Определение исходного допустимого решения 7
2.2. Перераспределение перевозок. Цикл перерасчета 8
2.3. Распределительный метод нахождения оптимального решения транспортной задачи 9
2.4. Метод потенциалов нахождения оптимального решения транспортной задачи 9
Глава 3. Усложненные и видоизмененные постановки транспортной задачи 12
3.1. Транспортная задача с вырожденным опорным планом 12
3.2. Открытые модели транспортной задачи 13
3.3. Транспортная задача с ограниченными возможностями транспортных средств и коммуникаций 16
3.4. Нелинейная модель транспортной задачи 19
3.5. Ламбда-задача 23
Заключение 26
Список используемой литературы 28

Введение

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

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков) по n потребителям этих ресурсов.
На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:
прикрепление потребителей ресурса к производителям;
привязка пунктов отправления к пунктам назначения;
взаимная привязка грузопотоков прямого и обратного направлений;
отдельные задачи оптимальной загрузки промышленного оборудования;
оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.
Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1, a2, …, am.
Известна потребность в грузах b1, b2, …, bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту
.
Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-й пункт назначения (до потребителя) xij с минимальными транспортными издержками.
В общем виде исходные данные представлены в табл. 1.

Таблица 1. Исходные данные



Транспортная задача называется закрытой, если суммарный объем отправляемых грузов
равен суммарному объему потребности в этих грузах по пунктам назначения
:
(1)
Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, т. е.:
(2)
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из i пунктов должны быть отправлены, т. е.:
(3)
Все j пункты (потребители) должны быть обеспечены грузами в плановом объеме:
(4)
Суммарные объемы отправления должны равняться суммарным объемам назначения:
(5)
Должно выполняться условие неотрицательности переменных:
. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):
(6)
В модели (3) – (6) вместо матрицы стоимостей перевозок
могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (5), уравнение баланса является обязательным условием решения транспортной задачи.
Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если:
потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправ