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

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

Введение

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

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

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

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:

x₁ - 3x₂ ≥ -3

CD:

x₁ - x₂ ≥ -9

DE:

x₁ +x₂ ≥ -3

:₁ ≥ 0

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

F = x₁ - 5x₂ +5 → min₁ + x₂ ≥ 1

x₁ - 3x₂ ≥ -3

-2x₁ - x₂ ≥ -9

x₁ +x₂ ≥ -3

x₁, x₂ ≥ 0

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

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

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

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

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

x₁ + x₂ ≥ 1

x₁ - 3x₂ ≥ -3

x₁ - 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₃₆ = 2 + 2x₂ + x₃= 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

x₁ - 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)