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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

оптимальный выпуск инвестиция перевозка

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

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

, и - коэффициенты.

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

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

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

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

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

1. ОПТИМИЗАЦИЯ ДОРОЖНОЙ СЕТИ

Даны пункты А и Т, необходимо найти минимальное расстояние между ними. Имеется 2 пункта вверху и 4 внизу, между ними находится еще 10 пунктов.

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

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

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

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

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

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

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

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

этап) : О - Т (12);

этап) : К - О (8);

этап) : В - К (5);

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

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

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

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

.1 Исходные данные

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

Таблица 1

Вид продукцииТип оборудованияО1О2О3П10,210,160,24П20,200,140,19П30,300,110,14

В соответствие с производственным заданием продукции П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

Базисная переменнаяСвободные членыСвободные переменныех1х2х3у1250 11900,21 4,760,20 0,950,14 0,67у2300 -1900,16 -0,760,14 -0,150,11 -0,106у3320 -2850,24 -1,140,19 -0,230,14 -0,16W0 -95208 -38,087 -7,629 -5,33

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

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

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

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

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

Таблица 3

Базисная переменнаяСвободные членыСвободные переменныеу1х2х3х11190 17734,76 7,090,95 1,420,67 1,49у2110 -7,14-0,76 - 0,03-0,01 -0,0060,004 -0,006у335 -35,7-1,14 0,14-0,04 -0,03-0,02 0,03W-9520 -6688-38,08 -26,75-0,62 -5,343,77 -5,62

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

Таблица 4

Базисная переменнаяСвободные членыСвободные переменныеу1х2х3х111737,091,421,49у2102-0,79-0,016-0,002у30-1-0,010,01W-16208-64,83-5,96-5,62

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

и

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

тыс. руб.

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

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

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

Таблица 5

ABC1x1x2x32000

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

Таблица 6

АВС3T1T2T34=0,21*А2+0,20*В2+0,30*С2=0,16*А2+0,14*В2+0,11*С2=0,24*А2+0,19*В2+0,14*С2

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

Таблица 7

АВ5W=8*А2+7*В2+9*С2

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

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

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

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

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

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

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

Таблица 8

АВС1x1x2x32428,57200,00400,003T1T2T34250,00140,57196,865W8428,57

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

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

ПоставщикПотребителиОбозначениеЗапасD1D2D3D4B1b1=513 11 13 0B2b2=956550B3b3=186880Потребностьd1=41d2=69d3=51d4=3

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

Таблица 10

ПоставщикПотребителиОбозначениеЗапасD1D2D3D4B1b1=513 4111 10 13 0B2b2=956 5 595 360 B3b3=186 8 8 150 3Потребностьd1=41d2=69d3=51d4=3

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

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

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

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

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

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

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

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

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

Таблица 11

ПоставщикПотребителиОбозначениеЗапасD1D2D3D4B1U1=113 41 11 10 13 110 3B2U2=56 -35 59 5 36 0 7B3U3=86 08 88 15 0 3 ПотребностьV1=-8V2=0V3=0V4=-8

Для каждой свободной клетки вычислим сумму потенциалов поставщика и потребителя. Обозначим ее 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 единицы.

.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.

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

= -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;… x6 - объемы перевозок от предприятия В2 потребителям D1, D2,D3;… x9 - объемы перевозок от предприятия В3 потребителям D1, D2,D3;

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

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

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

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

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

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

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

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

Условие неотрицательности можно представить в виде следующей системы неравенств:? 0, x2 ? 0, x3? 0, x4? 0, x5 ? 0, x6 ? 0, x7? 0, x8? 0, x9 ? 0.

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

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

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

Таблица 15

ИП1П2ПЗП40000 010231320353530874640108585012107116014121014

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

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

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

Введем следующие обозначения:- остаточные средства на начало iго этапа;- количество средств, которые решено выделить i - предприятию;

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

Таблица 16

Xii== 4i== 3i= 2 U4П4U3П43U2П42101030303202050510630306061084040 808201050501101130126060140141014

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

Таблица 17

Шаг№3Шаг №2Шаг №1Uix-UiПЗП4П4ЗП2П4ЗП42П1П42 П4110010033032 10010 1303 20020055055 1010134336 200303505 30030066066 102015 6358 201033 6538 30040 4707 4004008 8088 103016 7369 202035 85510 301043 77310 40050 5808 500500111101111 104018 93811 203036 95611 302045 97512 401053 88311 50070 710010 60060014140141401414 105011112311 81421214 20403811581331013 3030461076138816 40205510851310616 501073101031312315 600100101201214014

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 18

123456ИнвестицииП1П2П3П40000010231320353530874640108585012107116014121014Размах6014121014Сред. Знач3076,4285714,2857146,714286Мин00000Макс6014121014Разность6013151611Среднеквадратическое отклонение17,078253,8119043,8119043,1943834,398516Медиана307,5746Mode-----Асимметрия0-0,05379-0,288590,5147340,23553Эксцесс-1,2-1,85422-0,55662-0,2059-0,46345Коэф. вариации0,5692750,5445580,5929630,7453560,655098

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

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

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

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

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

+ х2+ хЗ+ х4?max.

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

> 0 2,24+3,96x1> 0

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

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

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

(2,24+3,96x1) + (-3,49+5,21x2)+( 3,60+6,16x3)+( -0,24+4,50x4)= 60

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

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

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

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

Задание на курсовой проект по дисциплине "Моделирование и оптимизация автомобильных дорог" Исходные данные: 1.учебная сеть дорог; 2.ко

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