Моделирование и оптимизация автомобильных дорог
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?кте, а через 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го этапа;- колич?/p>