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

Задание на курсовой проект по дисциплине

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

Исходные данные:

1. учебная сеть дорог;

2. координаты предприятий поставщиков и потребителей;

3. запасы продукции у предприятийпоставщиков;

4. потребность в продукции у предприятийпотребителей;

5. ресурс рабочего времени оборудования;

6. необходимые объемы поставок продукции;

7. удельные затраты времени на производство продукции;

8. объем инвестиций предприятиям;

9. прибыли предприятий.

Содержание курсового проекта:

1. оптимизировать дорожную сеть;

2. составить оптимальную схему перевозок;

3. оптимизировать распределение продукции, используя алгоритм «транспортная задача» ;

4. оптимизировать распределение продукции, используя Excel;

5. произвести сравнительный анализ решения по алгоритму «транспортная задача» и в Excel;

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

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

Курсовой проект представляется:

1. Пояснительная записка с необходимыми расчетами и схемами;

2. Обоснование принимаемых проектных решений.

1. Оптимизация дорожной сети

2. Определение оптимального объема выпускаемой продукции

2.1 Исходные данные

2.2 Составление математической модели

2.3 Решение задачи симплекс-методом

2.4. Решение с использованием «Excel»

3. Оптимизация перевозок

3.1 Исходные данные

3.2 Составление математической модели

3.3 Оптимизация математической модели

3.4 Оптимизация математической модели с использованием ПК

4. Оптимальное распределение инвестиций

4.1 Оптимизация инвестиций

4.2 Решение задачи с использованием прикладной программы «Excel»

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

Где, и — переменные величины;

и — коэффициенты.

Условия функционирования объекта (ограничения) в задачах линейного программирования должны относиться к одному из следующих типов:

Где, , — коэффициенты;

, — постоянные величины.

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

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

1. ОПТИМИЗАЦИЯ ДОРОЖНОЙ СЕТИ Даны пункты, А и Т, необходимо найти минимальное расстояние между ними. Имеется 2 пункта вверху и 4 внизу, между ними находится еще 10 пунктов.

Задача разбивается на этапы:

1 этап) попадание одним способом через точки: Б, И, Н, О, П, Р, С;

2 этап) попадание двумя способами через точки: Е, К, Л, М;

3 этап) попадание тремя способами через точки: Г, З;

4 этап) попадание четырьмя способами через точку: Д, Ж;

5 этап) попадание через точку: В;

6 этап) попадание из точки: А.

Оптимальное решение попадания из точки, А в точку Т за 4 этапа:

1 этап): О — Т (12);

2 этап): К — О (8);

3 этап): В — К (5);

4 этап): А — В (4);

Кратчайший путь из точки, А в точку Т:

(А — В — К — О — Т) = 4+5+8+12= 29 км.

2. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ОБЪЕМА ВЫПУСКА ПРОДУКЦИИ

2.1 Исходные данные Предприятие выпускает три вида продукции: П1, П2, П3, при изготовлении которой используется оборудование трех типов О1, О2, О3. Нормы времени работы каждого типа оборудования при изготовлении продукции П1, П2, П3 приведены в таблице 1.

Таблица 1

В соответствие с производственным заданием продукции П1 должно быть произведено не менее 150 ед., П2 — не менее 200 ед., П3 — не менее 400 ед. За изготовление единицы продукции П1, П2, П3 предприятие получает прибыль соответственно 8, 7, 9 тыс. руб. Ресурс рабочего времени оборудования О1, О2, О3 соответственно 250, 300, 320.

Требуется определить объем выпуска продукции каждого вида, при котором план по каждому виду продукции выполнен, ресурсы времени по всем типам оборудования не превышены, а прибыль от реализации продукции, максимальна.

2.2 Составление математической модели Обозначим через х1 — количество единиц продукции П1, х2 — П2, х3 — П3. Тогда требование выполнения производственного задания можно записать в виде неравенств:

(1.1.)

Оборудование О1 на изготовление продукции П1 затрачивает 0,21 ч., на П2 — 0,20 ч., на П3 — 0,30 ч. Получим общую продолжительность работы оборудования О1:

(1.2.)

По аналогии для оборудования О2 и О3 получим следующие выражения:

(1.3.)

Так как известен ресурс рабочего времени каждого типа оборудования, то:

;; (1.4.)

Критерием оптимальности в данной задаче является прибыль, полученная от реализации продукции. Поэтому целевая функция имеет вид:

(1.5.)

2.3. Решение задачи симплекс-методом Математическая модель задачи имеет вид:

Для упрощения расчетов заменяем ограничения (1.1.) условием неотрицательности:

Перейдем к минимизации целевой функции, изменив знаки всех ее коэффициентов на противоположные:

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

(1.6.)

Составим таблицу, состоящую из коэффициентов целевой фикции и системы ограничений (1.6.):

Таблица 2

В качестве разрешающего столбца выбираем х3, разрешающий элемент 0,21 (он находится на пересечении столбца х1 и строки у1). Затем выполняются вычисление обратной величины разрешающего элемента:

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

Подчеркивают в разрешающей строке все верхние числа (250; 0,20; 0,14), а в разрешающей графе — все нижние числа (-0,76; -1,14; -38,08).

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

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

Таблица 3

Так как в строке W есть положительный элемент 3,77, то оптимальное решение еще не получено и поиск решения продолжается в вышеизложенной последовательности, начиная с отыскания разрешающего элемента. Разрешающим элементом будет 0,67, обмениваемые переменные — х2 и х1. Промежуточные расчеты приведены в табл. 4.

Таблица 4

Так как все элементы в строке W отрицательны, то оптимальное решение получено и имеет вид:

и

Значение целевой функции определяется подстановкой найденных значений переменных в выражение (1.5.):

тыс. руб.

Полученное значение есть максимальная величина прибыли, которую получит предприятие, если будет выпускать продукцию П1, при условии непревышения ресурсов времени по всем типам оборудования.

2.4 Решение с использованием Excel.

В ней линейные математические модели могут быть оптимизированы через надстройку «Поиск решения». Сначала задаем количество единиц продукции (см. табл. 5).

Таблица 5

Зададим выражения для определения длительности работы каждого типа оборудования (см. табл. 6).

Таблица 6

Далее задаем целевую функцию (см. табл. 7).

Таблица 7

Затем заходим в «сервис» > выбираем «поиск решения» > появляется окно поиска решения:

Установить целевую ячейку: задаем «$В$ 5»;

Равной: выбираем «максимальному значению»;

Изменяя ячейки: задаем «$A$ 2:$C$ 2»;

Ограничения: задаем

«$A$ 2>=150, $В$ 2>=200, $С$ 2>=400, $A$ 4<=250, $В$ 4<=300, $С$ 4<=320»

Далее нажимаем «Выполнить» > «Сохранить найденное решение» нажимаем «ок» и получаем значения (см. табл. 8).

Таблица 8

По таблице мы видим, что максимальное значение целевой функции (суммарная прибыль от реализации продукции) 8428,6 тыс. руб. Достигается при следующих объемах выпусках продукции: П1 = 429 ед., П2 = 200 ед., П3 = 400 ед. При этом соблюдены условия выполнения плана выпуска всех видов продукции и ограничения ресурсов рабочего времени оборудования. Сравнивая результаты, делаем вывод, что более точный результат выходит с использованием программы компьютера.

3. ОПТИМИЗАЦИЯ ПЕРЕВОЗОК

3.1 Исходные данные Имеется 3 пункта, производящих некоторую продукцию. Затраты на производство единицы продукции в iом пункте равна аi, а максимально возможный объем ее выпуска составляет bi единиц в год, i = 1, 2 … m. Изготавливаемая продукция должна быть распределена между потребителями. Доставка единицы продукции от iого пункта производства к jому потребителю обходится в cij руб. j = 1, 2… n.

(3.1.)

(3.2.)

Потребность в продукции для jого потребителя составляет di единиц в год. Требуется составить схему перевозок так, чтобы годовые затраты на производство и перевозку были минимальными.

3.2 Составление математической модели Обозначим через yi искомый объем выпуска продукции в iом пункте, а через xij — объем перевозок от iого пункта к jому потребителю. Ограничения на объемы производства продукции будут иметь вид:

(3.3)

Условие вывозки всей производимой продукции записывается:

(3.4)

Удовлетворение заявкам потребителей представим выражением:

(3.5)

Условие неотрицательности объемов производств и перевозок запишется в виде неравенств:

(3.6)

Требование минимизации суммарных затрат на производство и перевозку реализуются целевой функцией вида:

(3.7)

Если в ограничениях и целевой функции этой модели заменить yi на, то модель открытой транспортной задачи примет вид:

(3.8)

3.3 Оптимизация математической модели Для оптимизации полученной модели сведем исходные данные в таблицу 9.

Таблица 9

Так как, а, то эта задача является открытой. Далее методом наименьшего элемента находим опорное решение (см. табл. 10).

Таблица 10

Опорное решение проверяется на вырожденность по формуле:

Где N — количество клеток таблицы, занятых объемами грузов;

m — количество поставщиков;

n — количество потребителей.

Так как количество клеток равно 6, то найденное опорное решение можно принять к дальнейшему рассмотрению. Значение целевой функции для полученного опорного решения будет иметь вид:

Оптимальное решение задачи находится методом потенциалов: каждому поставщику Bi ставится в соответствие некоторая переменная Ui называемая потенциалом данного поставщика. Каждому потребителю Dj ставится в соответствие переменная Vj — потенциал этого потребителя.

Для отыскания значений этих переменных, то есть потенциалов поставщиков и потребителей, составляется и решается система уравнений, исходя из предпосылки, что каждой занятой объемами перевозок клетке соответствует уравнение вида:

Где Cij — себестоимость перевозок единицы груза.

Для рассматриваемой задачи система уравнений будет иметь вид:

Принимая чаще всего встречающееся значение потенциала, равное V2 = 0, получим:

В соответствии с полученными результатами перепишем таблицу 11.

Таблица 11

Для каждой свободной клетки вычислим сумму потенциалов поставщика и потребителя. Обозначим ее XRS для Rого поставщика и Sого потребителя:

Определим для свободных от грузоперевозок клеток разность (дRS) себестоимости и величины ZRS:

Отсюда:

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

Анализ полученных результатов позволяет сделать вывод, что для минимизации затрат на производство и доставку продукции целесообразно разместить производство продукции следующим способом: в пункте B1 объемом 51 единицы для удовлетворения нужд потребителей — D1 (41 ед.) и D2 (10 ед.); в пункте В2 объемом 95 единицы для удовлетворения потребителей — D2 (59 ед.) и D3 (36 ед.) и в пункте В3 объемом 18 единиц для удовлетворения нужд потребителя — D3 (15 ед.) и D4 (3ед.). При этом, учитывая, что суммарный объем выпускаемой продукции на предприятиях B1, В2, В3 на 3 единицы больше суммарной потребности в продукции потребителей D1, D2, D3, D4, псевдопотребитель D4 получит эти 3 единицы.

3.4 Оптимизация математической модели с использованием ПК Для решения задачи, используем программы «Excel», для этого целевая функция задачи, в соответствии с выражением (3.9), записывается следующим образом:

W = x1 *(11+3) + x2*(11+11)+ x3*(11+13)+ x4*(5+6)+ x5*(5+5)+ x6*(5+5)+ x7*(8+6) + x8*(8+8) + x9*(8+8) > min.

Запишем в другом виде:

W = -14* x1 — 22* x2 -24* x3 -11* x4 -10* x5 -10* x6 -14* x7 -16* x8 -16* x9 > max.

где x1 … x3 — объемы перевозок от предприятия В1 потребителям D1, D2, D3;

x4 … x6 — объемы перевозок от предприятия В2 потребителям D1, D2, D3;

x7 … x9 — объемы перевозок от предприятия В3 потребителям D1, D2, D3;

Ограничения по объемам выпускаемой продукции на предприятиях В1, В2, В3 имеет вид:

x1 + x2 + x3 + 0 + 0 + 0 +0 + 0 + 0 = 51,

0 + 0 +0 + x4 + x5 + x6 + 0 + 0 + 0 = 95,

0 + 0 + 0 +0 + 0 + 0 + x7 + x8 + x9 = 18.

Ограничения по потребностям в производимой продукции у потребителей следующее:

x1 + 0 + 0 + x4 + 0 + 0 + x7 + 0 + 0 = 41,

0 + x2 +0 + 0 + x5 + 0 + 0 + x8 + 0 = 69,

0 + 0 + x3 +0 + 0 + x6 + 0 + 0 + x9 = 51.

Условие неотрицательности можно представить в виде следующей системы неравенств:

x1? 0, x2? 0, x3? 0, x4? 0, x5? 0, x6? 0, x7? 0, x8? 0, x9? 0.

В результате решения получились такие же значения объемов перевозок, как и аналитическим методом.

4. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ

В состав объединения входят 4 предприятия. Сумма инвестиций для этих предприятий составляет 60 тыс. руб. Необходимо распределить их между предприятиями так, чтобы прибыль была максимальна. Кратность инвестиций равна 10.

Таблица 15

Где И — инвестиции;

Решение начинается с последнего шага. На каждом промежуточном шаге находим условно оптимальное решение. На последнем шаге получим окончательное решение.

4.1 Оптимизация инвестиций

Введем следующие обозначения:

Xi — остаточные средства на начало iго этапа;

Uj — количество средств, которые решено выделить i — предприятию;

Пi — прибыль, получаемая этим предприятием.

Таблица 16

Первые три колонки мы уже можем заполнить. Для заполнения других столбцов необходимо сделать промежуточные действия. Результаты этих действий приведены в таблице 4.1.2.

Таблица 17

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

U1 = 30 тыс. руб. прибыль составляет 8 единиц;

60−30 = 30

U2= 10 тыс. руб., прибыль составляет 3 единицы;

30−10 = 20

U3 = 0 тыс. руб. прибыль составляет 0 единиц;

20−0 = 20

U4 = 20 тыс. руб., прибыль составляет 5 единиц;

Проверка: 8 + 3 + 5 = 16 (верно)

При распределении инвестиций общая прибыль составит 16 единиц.

4.2 Анализ параметров на их принадлежность к нормальному закону распределения.

Для анализа используем программу Excel. Критериями принадлежности к нормальному закону являются:

— Average — среднеарифметическое значение;

— Standard deviation — среднеквадратическое отклонение;

— Median — значение ряда, чаще всего встречающееся;

— Skewness — асимметрия, характеризует смещения графика;

— Kurtosis — эксцесс, отклонение от вертикальной оси;

— Kv — коэффициент вариации, характеризует неоднородность выборки;

— Mode — мода, значение ряда, кот наход в его середине;

— Range — разность между max и min;

Критерии принадлежности к нормальному закону:

1) Медиана и мода должны быть близки по значению;

2) Среднеарифметическое значение примерно по середине между max и min;

3) Коэффициент вариации должен быть в диапазоне 0,08−0,4;

4) Асимметрия и эксцесс не должны превышать двух.

Таблица 18

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

4.3 Решение задачи с использованием прикладных программ

Используем программу «Exсel».

Выбираем анализ данных, регрессия, вводим исходные данные (значения прибыли и инвестиций). Получаем коэффициенты и составляем 4 уравнения: y1=2,24+3,96×1; y2=-3,49+5,21×2; y3=3,60+6,16×3; y4=-0,24+4,50×4.

Целевая функция:

xl + х2+ хЗ+ х4>max.

Вводим ограничения:

xl > 0 2,24+3,96×1> 0

х2> 0 -3,49+5,21×2> 0

х3>0 -3,60+6,16×3> 0

х4>0 -0,24+4,50×4> 0

(2,24+3,96×1) + (-3,49+5,21×2)+(3,60+6,16×3)+(-0,24+4,50×4)= 60

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Моделирование и оптимизация лесопромышленных процессов. Методические указания по выполнению расчетно-графических работ для студентов. Петрозаводск 1999 г.

2. Конспект лекций по предмету «Моделирование и оптимизация» за 2009 г.