Оптимизация транспортных перевозок

Определение допустимого решения задачи линейного программирования методом введения искусственного базиса. Целочисленное линейное программирование с булевскими переменными. Поиск минимума функции методом градиентного спуска. Одномерная минимизация.
Краткое сожержание материала:

Размещено на

Введение

В последние годы все большее значение приобретает математический подход к задачам планирования.

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

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

1. Линейное программирование

1.1 Построение математической модели ЗЛП

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

Получение уравнения целевой функции.

Для наглядности обозначим вершины буквами:

A (1,0); B (0,1); C (3,3); D (4,1); E (3,0); F (1,0); H (5,2)

Выбираем две точки прямой (0,2) (5,4) и по уравнению прямой находим уравнение целевой функции:

x₁=5x₂ - 5; x₁ - 5x₂ + 5=0;

Поскольку направление справочной стрелки и градиента не совпадают, то целевая функция имеет вид:



Получение системы линейных ограничений

Найдем уравнения прямых по формуле:

AB:

x₁ + x₂ ? 1

BC:

2x₁ - 3x₂ ? -3

CD:

-2x₁ - x₂ ? -9

DE:

- x₁ +x₂ ? -3

EA:

x₁ ? 0

Составим математическую модель ЗЛП:

F = x₁ - 5x₂ +5 > min

x₁ + x₂ ? 1

2x₁ - 3x₂ ? -3

-2x₁ - x₂ ? -9

- x₁ +x₂ ? -3

x₁, x₂ ? 0

1.2 Получение решения ЗЛП графическим методом

Как видно из графика, оптимальная точка области решений, при которой целевая функция стремится к минимуму - точка C (3,3). Значение целевой функции в этой точке: F = -7.

1.3 Решение ЗЛП алгебраическим методом

Имеем математическую модель ЗЛП:

F = x₁ - 5x₂ +5 > min

x₁ + x₂ ? 1

2x₁ - 3x₂ ? -3

-2x₁ - x₂ ? -9

- x₁ + x₂ ? -3

x₁, x₂ ? 0

Вводим дополнительные переменные и переходим к каноническому равенству:

F = x₁ - 5x₂ +5 > min

x₁ + x₂ - x₃ = 1 x₃ = -1 + x₁ + x₂

2x₁ - 3x₂ - x₄ = -3 x₄ = 3 + 2x₁ - 3x₂

-2x₁ - x₂ - x₅ = -9 - x₅ = 9 - 2x₁ - x₂

-x₁ + x₂ - x₆ = -3 x₆ = 3 - x₁ + x₂

x_j ? 0, j = 1,6

Базисными являются x3, x4, x5, x6; свободными - x1, x2.

Решением будет служить < 0, 0, -1, 3, 9, 3 >, являющееся недопустимым. Выведем x₃ из базисных в свободные переменные, а x₁ переведём в базисные, чтобы избавиться от недопустимости в значениях переменных. Тогда система уравнений примет следующий вид:

x₁ = 1 - x₂ + x₃

x₄ = 5 - 5x₂ + 2x₃

x₅ = 7 + x₂ - 2x₃

x₆ = 2 + 2x₂ + x₃

F = 6 - 6x₂ + x₃ > min

Полученное решение < 0, 9, 8, 24, 0, 12 > может быть выбрано в качестве опорного.

Переведем в базис переменную x₂, а в свободные - x₄:

x₂ = 1 - 1/5x₄ + 2/5x₃

x₁ = 0 + 1/5x₄ - 8/5x₃

x₅ = 8 - 1/5x₄ - 1/5x₃

x₆ = 4 - 2/5x₄ - 7/5x₃

F = 0 + 6/5x₄ - 7/5x₃

Переводим в базис переменную x₃, а в свободные - x₅:

x₃ = 5 - 11/8x₄ - 5/8x₅

x₁ = 3 - 1/8x₄ - 3/5x₅

x₂ = 3 - 1/4x₄ - 1/4x₅

x₆ = 3 - 3/8x₄ + 1/8x₅

F = -7 + 7/5x₄ + 7/8x₅

Решение < 3, 3, 5, 0, 0, 3>, F = -7 является допустимым и оптимальным (так как целевую функцию уже нельзя улучшить). Так как результат совпал с результатом, полученным при решении графическим методом, делаем вывод, что решение верно.

1.4 Решение ЗЛП методом симплекс-таблицы

Имеем математическую модель:

F = x₁ - 5x₂ +5 > min

x₁ + x₂ ? 1

2x₁ - 3x₂ ? -3

-2x₁ - x₂ ? -9

- x₁ + x₂ ? -3

x₁, x₂ ? 0

Выбираем подходящее опорное решение и преобразовываем его для создания симплекс-таблицы:

x3 = -1 - (-x1 - x2)

x4 = 3 - (-2x1 + 3x2)

x5 = 9 - (2x1 + x2)

x6 = 3 - (x1 - x2)

F = 5 - (-x1 + 5x2)

	b	X1	X2
X3	-1		-1		-1
		1		-2/3		1/3
X4	3		-2		3
		1		-2/3		1/3
X5	9		2		1
		-1		2/3		-1/3
X6	3		1		-1
		1		-2/3		1/3
F	5		-1		5
		-5		10/3		-5/3

	b	X1	X4
X3	0		-5/3		1/3
		5		... Другие файлы: Оптимизация в планировании перевозок Оптимизация расстояния перевозок грузов. Определение рациональной грузоподъемности транспортных средств. Распределение подвижного состава по маршрутам... Оптимизация процесса транспортных перевозок Необходимость организации транспортного хозяйства для обслуживания предприятия средствами по перемещению грузов. Определение понятия номенклатуры пере... Оптимизация материального потока Участники логистической цепочки и задачи, решаемые в процессе оптимизации материального потока. Маршрутизация перевозок с помощью метода совмещённых п... Организация транспортных перевозок Грузооборот морского транспорта, роль портов в экономике страны. Экономические показатели продукции транспорта, грузопотоки и грузооборот. Расчет коли... Перспективы развития международных перевозок в Республике Казахстан (на примере железнодорожного транспорта) Транспортный фактор в международных контрактах. Методика оценки инновационных технологий организации международных транспортных перевозок. Интеграция...