Моделирование и оптимизация автомобильных дорог
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
? дорожной сети найдено кратчайшее расстояние между двумя пунктами А и K (A - C - E - G - L - K) = 91.8 ед. Необходимо отметить, что оптимизация дорожной сети в ручную при большом объёме данных является долгим и трудоёмким процессом.
1.3 Решение с использованием ПК
В соответствующие графы вводят начало, конец и длину участков.
В столбец Вход(H2) вводят формулу:
=СУММЕСЛИ($C$2:$C$20;G2;$A$2:$A$20) и копируют на весь столбец.
В столбец Выход(I2): =СУММЕСЛИ($B$2:$B$20;G2;$A$2:$A$20)
В клетку B21 вводят формулу: =СУММПРОИЗВ(A2:A20;D2:D20)
Далее воспользуемся функцией Поиск Решения
Целевая функция: B21 -> min.
Изменяемые ячейки: A2-A20
Ограничения: Столбец J K ; $J$2:$J$13 $K$2:$K$13.
1.4 Выводы
Не смотря на то что в ходе решения задачи 2-мя способами кратчайшее расстояние получилось одинаковым, решение этой задачи на ПК значительно облегчает задачу. Особенно в условиях большого количества исходных данных, и сложности сети дорог.
2 ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ОБЪЕМА ВЫПУСКА ПРОДУКЦИИ
2.1 Исходные данные
Предприятие выпускает три вида продукции: П1, П2 , П3, при изготовлении которой используется оборудование трех типов О1, О2, О3. Нормы времени работы каждого типа оборудования при изготовлении продукции П1, П2, Пз приведены в таблице 1.
Таблица 1
Вид продукцииТип оборудованияО1О2О3П10,220,170,25П20,210,150,20П30,310,120,15
В соответствие с производственным заданием продукции П1 должно быть произведено не менее n1=151 ед., П2 - не менее n2=201 ед., П3 - не менее n3=401 ед. За изготовление единицы продукции П1, П2, П3 предприятие получает прибыль соответственно k1=9, k2=8, k3=10 тыс. руб. Ресурс рабочего времени оборудования О1 , О2 , О3 соответственно t1=251, t2=301, t3=321.
Требуется определить объем выпуска продукции каждого вида, при котором план по каждому виду продукции выполнен, ресурсы времени по всем типам оборудования не превышены, а прибыль от реализации продукции, максимальна.
2.2 Составление математической модели
Обозначим через x1 - количество единиц продукции П1 , x2 - П2, x3 - П3. Тогда требование выполнения производственного задания можно записать в виде неравенств:
х1 ? 151 х2? 201 х3> 401(1.1)
Найдем выражения для определения длительности работы каждого типа оборудования.
Оборудование О1 на изготовление продукции П1 затрачивает 0,22ч., на П2 - 0,21 ч., на П3 - 0,31 ч.
Перемножая эти цифры на соответствующие им объемы продукции видов П1, П2 и П3 получим общую продолжительность работы оборудования О1:
Т1 = 0,22* х1 + 0,21*х2 + 0,31*х3(1.2)
По аналогии для оборудования О2 и О3 получим следующие выражения:
Т2 = 0,17* х1 + 0,15*х2 + 0,12*х3(1.3)
Т3 = 0,25*х1 + 0,20*х2 + 0,15* х3(1.4)
Так как известен ресурс рабочего времени каждого типа оборудования, то необходимо записать:
1 ? 251 ; T2 ? 301; T3 ? 321(1.5)
Критерием оптимальности в данной задаче является прибыль, полученная от реализации продукции. Прибыль от реализации продукции П1 составит 9* х1; прибыль от П2 составит 8* х2; прибыль от П3 составит 10* х3. Поэтому целевая функция задачи имеет вид:
W = 9* х1 + 8* х2 + 10* х3 > max(1.6)
Таким образом, математическая модель данной задачи состоит из целевой функции (1.6) и ограничений (1.1) и (1.5), которые являются линейными функциями.
2.3 Решение задачи симплекс-методом
Математическая модель задачи имеет вид:
W = 9* х1 + 8* х2 + 10* х3 > max
- 0,22* х1 - 0,21*х2 - 0,31*х3 ? 0
301 - 0,17* х1 - 0,15*х2 - 0,12*х3 ? 0
321 - 0,25*х1 - 0,20*х2 - 0,15* х3 ? 0
Для упрощения расчетов ограничения (1.1) заменяем условием неотрицательных переменных: х1 ? 0; х2 ? 0; х3 ? 0.
Перейдем к минимизации целевой функции W, изменив знаки всех ее коэффициентов на противоположные, и к ограничениям в виде равенств, введя дополнительные переменные:
W = -9* х1 - 8* х2 - 10* х3 > min
y1 = 251 - 0,22* х1 - 0,21*х2 - 0,31*х3;
y2 = 301 - 0,17* х1 - 0,15*х2 - 0,12*х3;
y3 = 321 - 0,25*х1 - 0,20*х2 - 0,15* х3;
где х1, х2, х3, y1, y2, y3 - неотрицательны.
Сведем к задаче линейного программирования:
W = 0 - (9* х1 + 8* х2 + 10* х3)(1.7)
y1 = 251 - (0,22* х1 + 0,21*х2 + 0,31*х3);
y2 = 301 - (0,17* х1 + 0,15*х2 + 0,12*х3)(1.8)
y3 = 321- (0,25*х1 + 0,20*х2 + 0,15* х3);
Составим таблицу, состоящую из коэффициентов целевой функции (1.7) и системы ограничений (1.8).
Таблица 2
Базисная переменнаяСвободный членСвободные переменныех1х2х3y12510,220,210,31y23010,170,150,12y33210,250,200,15W09810
В качестве разрешающего столбца выбираем х2. В столбце найдем разрешающий элемент путем сравнения соотношений 251/0,21; 301/0,15; 321/0,20.
Наименьшее из соотношений (251/0,21 = 1195) будет определять разрешающий элемент. Им будет элемент 0,21 находящийся на пересечении столбца х2 и строки y1. Этот элемент обводится.
Затем вычисляем обратную величину разрешающего элемента ? = 1/0,21 = 4,76 и записывают её в нижней части той же ячейки, в которой находится разрешающий элемент. Все элементы разрешающей строки умножаем на ?. Затем все элементы разрешающей графы умножают на (-?), результаты записываются в нижней части соответствующих ячеек.
Подчеркивают в разрешающей строке все верхние числа (251, 0,22, 0,31), а в разрешающей графе - все нижние числа (-0,72, -0.95, -38.10) за исключением ?. Для каждого из элементов, не принадлежащих ни к разрешающей строке, ни к разрешающей графе, записывают в нижней части соответствующей ячейки произведения подчеркнутых чисел, стоящих в той же строке и в той же графе, что и данный элемент.
Таблица 3
Базисная переменнаяСвободный членСвободные переменныех1x2х3Y1251 11950,22 1,050,21 4,760