- •Задание на курсовой проект по дисциплине «Моделирование и оптимизация автомобильных дорог»
- •Введение
- •1. Оптимизация дорожной сети
- •1.1 Исходные данные
- •1.2 Нахождение кратчайшего пути с использованием динамического программирования.
- •1.3 Решение с использованием пк
- •1.4 Выводы
- •2 Определение оптимального объема выпуска продукции
- •2.1 Исходные данные
- •2.2 Составление математической модели
- •2.3 Решение задачи симплекс-методом
- •2.4 Решение задачи с использованием пк
- •3 Оптимизация перевозок
- •3.1 Исходные данные
- •3.2 Составление математической модели
- •3.3 Оптимизация математической модели
- •3.4 Оптимизация математической модели с использованием пк
- •4 Оптимальное распределение инвестиций
- •4.1 Исходные данные
- •4.2 Оптимизация инвестиций
- •4.3. Решение задачи с использованием пк
- •4.4. Анализ параметров на их принадлежность к нормальному закону распределения
3.2 Составление математической модели
Обозначим через yi искомый объем выпуска продукции в i-ом пункте, а через xij – объем перевозок от i-го пункта к j-му потребителю. Ограничения на объемы производства продукции будут иметь вид:
yi ≤ bi, (i=1,2..m). (3.1)
Условие вывозки всей продукции запишется в виде:
(3.2)
Удовлетворение заявки каждого потребителя представим выражением:
(3.3)
Условие не отрицательности объемов производств е перевозок запишется в виде неравенств:
yi ≥ 0; xij ≥ 0; (i=1,2..m; j=1,2…n). (3.4)
Требования минимизации суммарных затрат на производство и перевозку реализуются целевой функцией вида:
→ min. (3.5)
Если в ограничениях и целевой функции этой модели заменить yi на , то модель открытой транспортной задачи имеет вид:
(3.6)
(3.7)
xij ≥ 0; (i=1,2..n) (3.8)
→ min. (3.9)
3.3 Оптимизация математической модели
Для оптимизации полученной модели сведем исходные данные в таблицу 6 и введем следующие обозначения:
В1, В2, В3 – данные поставщика с запасами груза b1, b2, b3;
D1, D2, D3 – данные потребителя с объемами заявок d1, d2, d3.
Таблица 6
Поставщик |
Потребитель |
|||
Обозначение |
Запас |
D1 |
D2 |
D3 |
В1 |
b1 = 50 |
4 |
10 |
8 |
В2 |
b2 = 101 |
5 |
4 |
4 |
В3 |
b3 = 13 |
5 |
10 |
7 |
Потребность в грузе |
d1 = 42 |
d2 = 71 |
d3 = 52 |
В верхнем правом углу клеток занесены стоимости перевозок i-го поставщика к j-му потребителю.
Сравнивая запасы груза с суммарным объемом заявок потребителей , убеждаемся, что это открытая транспортная задача (запасы груза у поставщика не равны потребностям в грузе потребителя). С избытком объема заявок
В этом случае заявки выполняются не полностью, поэтому равенство (3.7) заменяется неравенством:
Открытая транспортная задача сводится к закрытой введением (m+1)-го фиксированного поставщика с запасом груза равным:
Тогда имеем: b4= 165-164=1 единица.
Себестоимость перевозок от фиктивного поставщика к любому потребителю принимаем равной нулю, после этого получаем таблицу 7, в которой методом наименьшего элемента находим опорное решение задачи.
Таблица 7
Поставщик |
Потребитель |
|||
Обозначение |
Запас |
D1 |
D2 |
D3 |
В1 |
b1 = 50 |
4 42 |
10 |
8 8 |
В2 |
b2 = 101 |
5 |
4 71 |
4 30 |
В3 |
b3 = 13 |
5 |
10 |
7 13 |
B4 |
b4 =1 |
0 |
0 |
0 1 |
Потребность в грузе |
d1 = 42 |
d2 = 71 |
d3 = 52 |
Опорное решение проверяется на выраженность по формуле:
N=m+n-1
Где: N- количество клеток таблицы, занятых объемами грузов;
m- количество поставщиков;
n- количество потребителей.
N=4+3-1=6. Так как количество клеток в таблице 7 именно 6, то найденное опорное решение можно принять к рассмотрению.
Значение целевой функции будет иметь вид:
W = 42*(4+11) + 8*(8+11) +71*(4+11) +30(4+11) +13*(7+3)+1(0+0) = 2427
Оптимальное решение задачи находится методом потенциалов: каждому поставщику Bi ставятся в соответствие некоторая переменная Ui, называемая потенциалом данного поставщика. Каждому потребителю Dj ставятся в соответствие переменная Vj – потенциал этого потребителя.
Для отыскания значений этих переменных, т.е. потенциалов поставщиков и потребителей, составляется и решается система уравнений, каждой занятой объемами перевозок клетке соответствует уравнение вида:
Ui + Vj = Cij, (3.11)
где Cij – себестоимость перевозок единицы груза.
Для рассматриваемой задачи система уравнений будет иметь вид:
U1+ V1 = 4;
U1+ V3= 8;
U2+ V2 = 4;
U2+ V3 = 4;
U3+ V3 = 7;
U4+ V3 = 0;
Принимаем чаще всего встречающееся значение потенциала, равное V3 =0, получим:
U1 = 8; U2 = 4; U3 = 7; V1 = -4; V2 = 0; V3 = 0; U4=0.
Таблицу 8 с учетом найденных потенциалов запишем в следующем виде:
Таблица 8
Поставщик |
Потребитель |
|||
Обозначение |
Запас |
D1 |
D2 |
D3 |
В1 |
U1 = 8 |
4 42 |
10 8 |
8 8 |
В2 |
U2 = 4 |
5 0 |
4 71 |
4 30 |
В3 |
U3 = 7 |
5 3 |
10 7 |
7 13 |
B4 |
U4 =0 |
0 -4 |
0 0 |
0 1 |
Потребность в грузе |
V1 = -4 |
V2 = 0 |
V3 = 0 |
Для каждой свободной клетки вычислим сумму потенциалов поставщика и потребителя. Обозначим ее ZRS для R-го поставщика и S-го потребителя:
ZRS = UR + VS.
Определим для свободных от грузоперевозок клеток разность (δRS) себестоимости и величины ZRS:
δRS = Cij – ZRS.
Отсюда: δ12 = 10-8 = 2;
δ21 = 5-0 = 5;
δ31 = 5-3 = 2;
δ32 = 10-7 = 3;
δ41 = 0-(-4) = 4;
δ42 = 0-0 = 0.
Для всех свободных членов получены положительные разности. Следовательно, данное решение является оптимальным, и целевая функция имеет вид:
W = 42*(4+11) + 8*(8+11) +71*(4+11) +30(4+11) +13*(7+3)+1(0+0) = 2427
Анализ полученных результатов позволяет сделать вывод, что для минимизации затрат на производство и доставку продукции целесообразно разместить производство продукции следующим образом: в пункте В1 объемом 50 единиц для удовлетворения нужд потребителей – D1 (42 ед.), D3(8 ед); в пункте В2 объемом 101 единиц – D2 (71 ед.), D3 (30 ед.); в пункте В3 объемом 13 единиц – D3 (13 ед.),в пункте D4 объемом 1 единица – D3(1ед). При этом, учитывая, что суммарный объем выпускаемой продукции на предприятиях В1, В2, В3 равно суммарному объему потребности в продукции потребителей D1, D2, D3.
“Ручной” способ решения подобных задач является трудоемкой операцией, поэтому целесообразно использование компьютерных программ; применение программы “Statgraphics” для этих целей рассмотрим в следующем разделе.