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

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

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

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

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 — ¼x₄ — ¼x₅

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 — (-2×1 + 3×2)

x5 = 9 — (2×1 + x2)

x6 = 3 — (x1 — x2)

F = 5 — (-x1 + 5×2)

Получено решение:

Х=(3,3,5,0,0,3) F=-7

1.5 Определение допустимого решения ЗЛП методом введения искусственного базиса

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

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

x₁ + x₂? 1

2x₁ — 3x₂? -3

— 2x₁ — x₂? -9

— x₁ + x₂? -3

x₁, x₂? 0

Вводим дополнительные переменные Е:

Е1 = 1 — x₁ — x₂ + x₃

Е2 = 3 + 2 x₁ — 3 x₂ — x₄

Е3 = 9 — 2 x₁ — x₂ — x₅

Е4 = 3 — x₁ + x₂ — x₆

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

Е1 = 1 — (x₁ + x₂ — x₃)

Е2 = 3 — (- 2x₁ + 3 x₂ + x₄)

Е3 = 9 — (2 x₁ + x₂ + x₅)

Е4 = 3 — (x₁ — x₂ + x₆)

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

f = 16 — (2x₁ + 4 x₁ — x₃ + x₄ + x₅ + x₆)

Решаем задачу с помощью симплекс-таблицы.

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

2. Целочисленное линейное программирование

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

Получено целочисленное решение: X^opt = < 0,1>, F = 4

3. Целочисленное линейное программирование с булевскими переменными

Составим математическую модель данной ЗЛП с булевскими переменными:

F=25x₁ + 35x₂ + 20x₃ + 15x₄ + 10x₅

7x₁ + 8x₂ + 9x₃ + 6x₄ + 4x₅? 30

6x₁ + 4x₂ + 9x₃ + 8x₄ + 7x₅? 30

6x₁ + 7x₂ + 8x₃ + 9x₄ + 5x₅? 30

Запишем вычисления в таблицу:

Максимальной прибыли предприятие достигнет при реализации проектов

1, 2, 3, 4

X = (1,1,1,1,0); F=95

4. Поиск глобального экстремума функции

Минимизировать функцию, где a = 4, b = 7. Начальная точка. Применить метод движения по симплексу. Начальные условия: размер стороны симплекса =2; коэффициент уменьшения стороны симплекса =10; критерий окончания поиска Ответ:

5. Метод градиентного спуска

Выполнить поиск минимума функции, где a = 4, b = 7 методом градиентного спуска.

Начальные условия:

— значение шага t₀=0,5;

— коэффициент уменьшения шага =2;

— критерий окончания поиска ;

— начальная точка

1)

2)

Так как критерий выполнен, то .

6. Одномерная минимизация

Требуется:

— выполнить поиск минимума заданной функции методом дихотомии (3 итерации);

— уточнить интервал поиска методом Фибоначчи (3−4 итерации);

— завершить поиск методом квадратичной аппроксимации.

Метод дихотомии

Заключение

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

Для задач линейного программирования были заданы одни и те же исходные данные, поэтому полученные ответы каждого пункта одинаковые. Оптимальный план для данной ЗЛП: Х = < 3, 3 5, 0, 0, 3>, значение целевой функции F=-7.

Для задачи целочисленного линейного программирования было получено следующее оптимальное целое решение: Х = <0,1>. F = 4.

Задача целочисленного линейного программирования с булевскими переменными была решена с помощью Метода Баллаша. Получили следующее решение: X = (1,1,1,1,0); F=95.

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

По методу градиентного спуска был найден экстремум функции и он составил:

F (x) = 0

Задача одномерной минимизации решена тремя методами: метод дихотомии (первые 4 итерации), метод Фибоначчи (вторые 4 итерации), и завершен поиск методом квадратичной аппроксимации. Получен ответ:

Х = 0.638, F (x) = 3.43.

программирование булевский градиентный транспортный

1. М.У. для выполнения курсового проекта по дисциплине «Прикладная математика»