Задачи линейного программирования транспортного типа

Содержание

Введение. 3

1. Теоретические основы задач выбора оптимального маршрута перевозки туристов 4

1.1 Линейное программирование. Основные понятия. 4

1.2 Задачи линейного программирования транспортного типа. 8

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

2. Решение задачи выбора оптимального маршрута перевозки туристов. 14

2.1 Постановка задачи оптимальной перевозки туристов. 14

2.2 Математическая модель задачи оптимальной перевозки туристов. 14

2.3 Решение задачи оптимальной перевозки туристов методом минимального элемента и методов потенциалов. 17

2.4 Разработка программного обеспечения для решения задач транспортного типа 19

Заключение. 22

Список используемых источников. 23

Приложение. 24

Введение

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

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

Целью данной курсовой работы является выбор оптимального маршрута перевозки туристов.

Для достижения цели следует решить следующие задачи:

1. ­Анализ задачи оптимальной перевозки туристов и рассмотрение методов решения.

2. Выбор метода оптимизации.

3. Рассмотрение алгоритма метода и решение практической задачи.

4. Создание программы для автоматического решения задачи выбора оптимального маршрута перевозки туристов.

Теоретические основы задач выбора оптимального маршрута перевозки туристов

Линейное программирование. Основные понятия

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов, в условиях рыночных отношений, приходится отыскивать наилучшие при ограничениях, налагаемых на природные, экономические и технологические возможности. Такие методы объединяются под общим названием – математическое программирование.

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

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

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

- целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант – из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д..

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

Один из разделов математического программирования – линейное программирование.

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

К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

- задача об оптимальном использовании ресурсов при производственном планировании;

- задача о смесях (планирование состава продукции);

- задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или " задача о рюкзаке");

- транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования. Кроме того выделяют: целочисленное, динамическое, нелинейное, параметрическое программирование. Это объясняется следующим:

- математические модели большого числа экономических задач линейны относительно искомых переменных;

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

- многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

- целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать;

- ограничения в виде системы линейных уравнений или неравенств;

- требование неотрицательности переменных.

В общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как:

(1.1)

При ограничениях:

(1.2)

(1.3)

(1.4)

Функция 1.1 называется целевой функцией или линейной формой задачи 1.1-1.4, а условие 1.2–1.4 – ограничениями данной задачи.

Стандартной или симметричной задачей линейного программирования называется задача, которая состоит в определении оптимального значения функции 1.1, при выполнении условий 1.2–1.4.

Канонической или основной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции 1.1 при выполнении условий 1.3–1.4.

Совокупность чисел удовлетворяющих ограничения 1.2–1.4 называется допустимым решением или планом.

План при котором целевая функция 1.1 достигает максимальное (минимальное), значение называется оптимальным.

Основная задача линейного программирования в векторной форме:

(1.5)

(1.6)

Где, , ,

, , , …,

План называется опорным планом основной задачи линейного программирования, если система векторов A_j входящих в размножение 1.6 с положительными коэффициентами X_j линейно независимо.

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

Задачи линейного программирования транспортного типа

Транспортная задача – математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов от поставщика к потребителям с минимизацией затрат на перемещение.

Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

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

Существует несколько типов транспортных задач. Имеются mпоставщиков однородной продукции с известными запасами этой продукции и nпотребителей этой продукции с заданными объёмами потребления. Известны также удельные затраты на перевозку. Если сумма объёмов запасов продукции A_i равна объёму потребления всех потребителей B_j, то такая задача называется закрытой транспортной задачей (то есть ), в противной случае открытой.

Открытую транспортную задачу можно преобразовать в закрытую следующим образом.

Пусть . В этом случае необходимо ввести фиксированного n+1 потребителя с объемом потребления . Удельные затраты на перевозку от поставщиков к фиксированному потребителю полагаются равными нулю, так как на самом деле такие перевозки осуществлять не будут и некоторая часть продукции останется и поставщиков.

Пусть . В этом случае необходимо ввести фиксированного m+1 поставщика с объёмом запасов . Удельные траты на перевозку от фиксированного поставщика к потребителям полагаются равными нулю, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

В закрытой транспортной задаче все ограничения записываются в виде уравнений:

; (1.7)

; (1.8)

; (1.9)

(1.10)

Закрытая транспортная задача всегда имеет решение. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то существует решение транспортной задачи, которое также будет целочисленным.