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

 

Введение

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

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

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

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) и по уравнению прямой находим уравнение целевой функции:

x1=5x2 - 5; x1 - 5x2 + 5=0;

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

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

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

AB:

x1 + x2 ? 1

BC:

x1 - 3x2 ? -3

CD:

x1 - x2 ? -9

DE:

x1 +x2 ? -3

:1 ? 0

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

F = x1 - 5x2 +5 ? min1 + x2 ? 1

x1 - 3x2 ? -3

-2x1 - x2 ? -9

x1 +x2 ? -3

x1, x2 ? 0

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

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

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

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

F = x1 - 5x2 +5 ? min

x1 + x2 ? 1

x1 - 3x2 ? -3

x1 - x2 ? -9

x1 + x2 ? -3

x1, x2 ? 0

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

F = x1 - 5x2 +5 ? min

x1 + x2 - x3 = 1 x3 = -1 + x1 + x2

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

-2x1 - x2 - x5 = -9 ? x5 = 9 - 2x1 - x2

-x1 + x2 - x6 = -3 x6 = 3 - x1 + x2

xj ? 0, j = 1,6

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

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

x1 = 1 - x2 + x3

x4 = 5 - 5x2 + 2x3

x5 = 7 + x2 - 2x36 = 2 + 2x2 + x3= 6 - 6x2 + x3 ? min

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

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

x2 = 1 - 1/5x4 + 2/5x3

x1 = 0 + 1/5x4 - 8/5x3

x5 = 8 - 1/5x4 - 1/5x3

x6 = 4 - 2/5x4 - 7/5x3

F = 0 + 6/5x4 - 7/5x3

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

x3 = 5 - 11/8x4 - 5/8x5

x1 = 3 - 1/8x4 - 3/5x5

x2 = 3 - 1/4x4 - 1/4x5

x6 = 3 - 3/8x4 + 1/8x5

F = -7 + 7/5x4 + 7/8x5

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

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

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

F = x1 - 5x2 +5 ? min

x1 + x2 ? 1

x1 - 3x2 ? -3

-2x1 - x2 ? -9

x1 + x2 ? -3

x1, x2 ? 0

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

x3 = -1 - (-x1 - x2)

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

x5 = 9 - (2x1 + x2)

x6 = 3 - (x1 - x2)

F = 5 - (-x1 + 5x2)

bX1X2X3-1-1-11-2/31/3X43-231-2/31/3X5921-12/3-1/3X631-11-2/31/3F5-15-510/3-5/3

bX1X4X30-5/31/355/85/32X21-2/31/321/4-1/12X588/3-1/333/8-1/8X641/31/3-1-1/81/24F07/3-5/3-7-7/87/24

bX5X4X355/811/32X231/41/4X133/8-1/8X63-1/89/24F-7-7/8-33/24

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

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

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

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

F = x1 - 5x2 +5 ? min1 + x2 ? 1

x1 - 3x2 ? -3

-2x1 - x2 ? -9

x1 + x2 ? -3

x1, x2 ? 0

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

Е1 = 1 - x1 - x2 + x3

Е2 = 3 + 2 x1 - 3 x2 - x4

Е3 = 9 - 2 x1 - x2 - x5

Е4 = 3 - x1 + x2 - x6

F = x1 - 5x2 +5 ? min

Е1 = 1 - (x1 + x2 - x3)

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

Е3 = 9 - (2 x1 + x2 + x5)

Е4 = 3 - (x1 - x2 + x6)

F = x1 - 5x2 +5 ? min= 16 - (2x1 + 4 x1 - x3 + x4 + x5 + x6)

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

bX1X2X3X4X5X6E1111-1000111-1000E23-230100-3-3-33000E39213010-1-1-11000E431-10001111-1000f1624-1111-4-4-44000F5-150000-5-5-55000

bX1E1X3X4X5Х6X2111-100005/3-11/31/300E20-5-3310005/3-11/31/300E381-1101005/311/31/300Е4421-100105/3-11/31/300f12-2-43111053-1-300F0-6-55000025/355/35/300

bX1E1E2X4X5X6X212/311/31/30021/801/241/241/80X305/301/31/30055/805/245/245/80E388/301/31/31033/801/8003/8E441/301/31/30111/801/241/241/80f123-11-21163/401/41/43/40F07/305/35/300-77/807/247/247/80

bЕ3E1Е2X4X5X6X231/401/41/41/400000000Х355/8-11/81/85/800000000Х133/801/81/83/80000000E431/8003/83/81/81303/243/81/81f39/8-15/83/81/81-31/803/83/81/8-1F-77/8033/2433/247/800000000

bЕ3E1Е2X4X5Е4X231/401/41/41/40Х355/8-11/81/85/80Х133/801/81/83/80Х631/803/83/81/81f0-1-1-100-1F-77/8033/2433/247/80

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

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

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

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

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

ВариантПроектРасходы (млн. грн. в год)Прибыль (млн. грн)1-й год2-й год3-й год20176625284735399820468915547510Доступный капитал303030

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

F=25x1 + 35x2 + 20x3 + 15x4 + 10x5

x1 + 8x2 + 9x3 + 6x4 + 4x5 ? 30

x1 + 4x2 + 9x3 + 8x4 + 7x5 ? 30

x1 + 7x2 + 8x3 + 9x4 + 5x5 ? 30

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

x1x2x3x4x5Ф.О.123Ц.Ф.000000+++00000110+++100001015+++150001125+++250010020+++0010130+++300011035+++350011145+++450100035+++0100145+++0101050+++500101160+++600110070+++700110155+++0111070+++0111180+++801000025+++1000135+++1001040+++1001150+++1010045+++1010155+++1011060+++1011170+++1100060+++1100170+++1101075+++1101185+++851110080+++1110190+++901111095+++9511111105---105

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

1, 2, 3, 4

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

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

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

Ответ:

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

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

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

значение шага t0=0,5;

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

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

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

)

)

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

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

Требуется:

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

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

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

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

kakx1kxmkx2kbkf(x1)f(xm)f(x2)00.10.5751.051.52523.5163.815.25110.5750.8131.051.2871.5253.4843.814.420.8130.9311.051.1691.2873.6123.814.07430.9310.9911.051.1091.1693.7023.813.934

Заключение

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

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

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

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

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

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

(x) = 0

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

Х = 0.638, F(x) = 3.43.

Список литературы

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

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

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

Больше работ по теме: