Распределение емкостей телефонных станций между районами города
Экономико-математическая модель задачи, нахождение с помощью метода линейного программирования вариантов распределения емкостей телефонных станций между районами и минимизации затрат на строительство и эксплуатацию линейных сооружений телефонной сети.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 07.04.2014 |
| Размер файла | 99,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Контрольная работа
по дисциплине:
"Экономико-математические методы и модели в отрасли связи"
Вариант-2
2014
План
Задача 1
Задача 2
Задача 3
Задача 4
Литература
Задача 1
На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
Исходные данные:
Таблица 1.1 Незадействованные емкости телефонных станций
|
Возможности станций |
номеров |
|
|
QА |
1000 |
|
|
QБ |
1500 |
|
|
QВ |
500 |
Таблица 1.2 - Спрос на установку телефонов
|
Спрос районов |
номеров |
|
|
Q1 |
400 |
|
|
Q2 |
800 |
|
|
Q3 |
1200 |
|
|
Q4 |
600 |
Таблица 1.3 - Средние расстояния от станции до районов застройки, км
|
Станции |
Районы |
||||
|
1 |
2 |
3 |
4 |
||
|
А |
4 |
5 |
6 |
4 |
|
|
Б |
3 |
2 |
1 |
4 |
|
|
В |
6 |
7 |
5 |
2 |
Решение:
Проверим соотношения между суммарной возможностью поставщиков и суммарным спросом потребителей:
Получаем, что
то есть модель закрытая, вводим условную станцию, возможность которой равна
.
Составим экономико-математическую модель задачи в развернутом виде. Ограничивающая часть модели должна содержать ограничения по возможности станций
и по спросу потребителей
.
Функция цели задачи должна отражать искомый результат в соответствии с выбранным критерием оценки
.
Решим задачу распределительным методом. Построим исходный план способом "северо-западного угла" (Таблица 1.4).
Таблица 1.4 - Матрица для m-пунктов отправления (поставщиков) и n-пунктов назначения (потребителей).
|
Наименование поставщиков |
Наименование потребителей |
Возможности пунктов отправления |
||||
|
Q1 |
Q2 |
Q3 |
Q4 |
|||
|
QА |
400 |
600 |
- |
- |
1000 |
|
|
QБ |
- |
200 |
1200 |
100 |
1500 |
|
|
QВ |
- |
- |
- |
500 |
500 |
|
|
Потребности пунктов назначения |
400 |
800 |
1200 |
600 |
3000 |
Следует заметить, что при заполнении исходного плана способом "северо-западного угла" зачастую получается план, весьма далекий от оптимального.
Функция цели задачи должна отражать искомый результат в соответствии с выбранным критерием оценки
.
|
Наименование поставщиков |
Наименование потребителей |
Возможности пунктов отправления |
||||
|
Q1 |
Q2 |
Q3 |
Q4 |
|||
|
QА |
4 400 |
5 600 |
6 - |
4 - |
1000 |
|
|
QБ |
3 - |
2 200 |
1 1200 |
4 100 |
1500 |
|
|
QВ |
6 - |
7 - |
5 - |
2 500 |
500 |
|
|
Потребности пунктов назначения |
400 |
800 |
1200 |
600 |
3000 |
Рассчитаем затраты:
Z = (400*4)+(600*5)+(200*2)+(1200*1)+(100*4)+(500*2)=7600
То есть при данном исходном плане затраты составят 7600, согласно цели задачи сводим данное значение к min.
Далее начнем проверять исходный план на оптимальность с помощью характеристик, рассчитываемых для свободных мест плана.
Характеристики свободных мест определяются с помощью контуров. Контуры строятся из горизонтальных и вертикальных отрезков прямых по правилу: одна вершина контура должна находиться в свободной клетке, для которой считается характеристика, а все остальные вершины контура должны находиться в занятых местах. У вершины контура проставляются знаки: у вершины, находящейся в свободной клетке ставится всегда "+", а знаки других вершин чередуются "-", "+" и т.д.
Значение характеристики свободной клетки находится как алгебраическая сумма оценок Сij, стоящих у вершин контура. При этом оценки суммируются с учетом знаков, проставленных у вершин.
План считается оптимальным, если характеристики всех свободных мест плана окажутся положительными.
Строим контур для свободных клеток QБQ1,QВQ1, QАQ3,QВQ3,,QАQ4:
|
Наименование поставщиков |
Наименование потребителей |
Возможности пунктов отправления |
||||
|
Q1 |
Q2 |
Q3 |
Q4 |
|||
|
QА |
4 400 |
5 600 |
6 |
4 |
1000 |
|
|
QБ |
3 |
2 200 |
1 1200 |
4 100 |
1500 |
|
|
QВ |
6 |
7 |
5 |
2 500 |
500 |
|
|
Потребности пунктов назначения |
400 |
800 |
1200 |
600 |
3000 |
QБQ1=3-2+5-4=2
QВQ1=6-2+4-2+5- 4 = 7
QВQ3=7-2+4-2=7
QАQ3=6-5+2-1 = 2
QВQ3=5-2+4-1 = 6
QАQ4=4-5+2-4 = -3
Так как ячейка QАQ4 <0, следовательно, исходный план распределения требует улучшения.
Введение перевозки в направлении клетки с отрицательной характеристикой на каждую единицу перевозимого груза обеспечит снижение транспортных затрат в размере значения характеристики.
Пересчет поставок ведется следующим образом: среди поставок, стоящих у отрицательных вершин контура, находится наименьшая по значению и на эту величину в новом плане увеличиваются поставки, стоящие у вершин со знаком "+" и одновременно уменьшаются поставки у вершин со знаком "-".
В нашем случае, среди поставок, стоящих у отрицательных вершин контура, находится наименьшая по значению находится в клетке QБq1 со значением - 100.
Таким образом, величина, вводимая в клетку поставки QАq4 в новом плане берется равный минимум из поставок, стоящих у отрицательных вершин контура, построенного для этой клетки, то есть 100. На эту величину в новом плане увеличатся поставки, стоящие у положительных вершин и одновременно уменьшаем поставки, стоящие у отрицательных вершин данного контура на эту величину.
Все другие в данном контуре в новый план переносим без изменений.
Составляем новый откорректированный план:
|
Наименование поставщиков |
Наименование потребителей |
Возможности пунктов отправления |
||||
|
q1 |
q2 |
q 3 |
q 4 |
|||
|
QА |
4 400 |
5 500 |
6 |
4 100 |
1000 |
|
|
QБ |
3 |
2 300 |
1 1200 |
4 |
1500 |
|
|
QВ |
6 |
7 |
5 |
2 500 |
500 |
|
|
Потребности пунктов назначения |
400 |
800 |
1200 |
600 |
3000 |
Рассчитаем затраты после улучшения плана:
Z= (400*4)+(500*5)+(300*2)+(1200*1)+(100*4)+(500*2)=7300
Так же строим контур для свободных клеток:
QБQ1=3-2+5-4=2
QВQ1=6-2+4-4=4
QВQ2=7-2+4-5=4
QАQ3=6-5+2-1=2
QВQ3=5-2+4-1=6
QБQ4=4-4+5-2=3
Получаем, что все характеристики свободных мест являются положительными, следовательно, данный план распределения номерной емкости является наиболее оптимальным к внедрению. Затраты при новом плане так же снижены с 7600 до 7300.
Ответ: Данный план распределения номерной емкости является наиболее оптимальным к внедрению. Затраты при новом плане так же снижены с 7600 до 7300.
Задача 2
телефонный емкость затраты строительство
Необходимо оценить работу автоматической телефонной станции (АТС), которая имеет n линий связи. Моменты поступления вызовов на станцию являются случайными и независимыми друг от друга. Средняя плотность потока равна л вызовов в единицу времени. Продолжительность каждого разговора является величиной случайной и подчинена показательному закону распределения. Среднее время одного разговора равно tобс единиц времени.
Исходные данные:
Количество линий, n - 8;
плотность потока (вызовов), - 4;
среднее время разговора, tобс - 1
Решение:
Автоматические телефонные станции относятся к типу систем обслуживания с потерями (с отказами).
Для определения основных показателей работы АТС необходимо рассчитать значение поступающей нагрузки в Эрлангах Ш и вероятности Pk, что из n-линий k будет занято.
Формулы, которые служат для расчета вероятностей р, k =0,1, ...,n, в установившемся режиме, называются формулами Эрланга:
Ш = л* tобс, (1)
Где, Ш - входящая нагрузка в Эрлангах;
л - плотность потока, количество вызовов в единицу времени;
tобс - среднее время одного разговора.
Ш = 4 · 1= 4 Эрл.
Получим значение поступающей нагрузки равной 4 Эрл.
Далее найдем вероятность того, что k- линий из n будут заняты по формулам 2,3.
, (2)
(3)
P0 - вероятность того, что в системе нет ни одного требования.
Данные сведем в таблицу:
|
K (линии) |
Шk (поступающая нагрузка) |
K! |
Шk/k! |
|
|
1 |
4 |
1 |
4 |
|
|
2 |
16 |
2 |
8 |
|
|
3 |
64 |
6 |
10,667 |
|
|
4 |
256 |
24 |
10,667 |
|
|
5 |
1024 |
120 |
8,533 |
|
|
6 |
4096 |
720 |
5,689 |
|
|
7 |
16384 |
5040 |
3,251 |
|
|
8 |
65536 |
40320 |
1,625 |
|
|
Итого |
- |
- |
52,432 |
P0 = 1 / 52,432 = 0,019072
1. Вероятность отказа равна:
Получим: Pотк= (48 / 8!) • 0,019072 = 0,031
2. Среднее число занятых линий равно:
Получим:nзан ср = 0,019072*(41 / 0!+ 42 / 1!+43 / 2!+ 44 / 3!+ 45 / 4!+ 46 /5!+ 47 /6!+ 48 /7!) = 3,9523
3. Среднее число свободных линий равно:
nсвоб ср = nобщ. - nзан ср
Получим: nсвоб ср = 8 - 3,9523 = 4,0477
4. Коэффициент занятости линий:
Кзанят = nзан ср / n
Получим: Кзанят = 3.9523/ 8 = 0.494
5. Коэффициент простоя линий:
Кпрост = nсвоб ср / n
Получим: Ксвоб = 4.0477/ 8 = 0.5059
Ответ: Оценивая работу данной автоматической станции (АТС), было выявлено, что вероятность отказа в предоставлении вызова равна 0.031 при коэффициенте занятости линии 0.494, то есть около 3% позвонивших получат отказ в ответе, а загрузка линий составляет всего 49,4%, таким образом, среднее число занятых и свободных линий равно. Данные показатели неплохие для работы АТС, тем не менее коэффициент простоя больше 50%, а следовательно в это время возникают неоправданные затраты на обслуживание данной АТС.
Задача 3
В таблице 3.1 приведены затраты времени почтальона (в минутах) на проход между пунктами доставки на участке. Используя метод "ветвей и границ", найти маршрут почтальона, при котором затраты времени на его проход будут минимальными.
Таблица 3.1 - Исходные данные
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
- |
4 |
8 |
6 |
12 |
10 |
|
|
Б |
5 |
- |
5 |
15 |
9 |
14 |
|
|
В |
10 |
5 |
- |
10 |
5 |
5 |
|
|
Г |
7 |
14 |
8 |
- |
13 |
8 |
|
|
Д |
12 |
7 |
6 |
12 |
- |
10 |
|
|
Е |
11 |
10 |
4 |
10 |
8 |
- |
Задача решается методом теории графов, известным как метод "ветвей и границ".
Решение задачи начинается с приведения матрицы исходных данных. Матрица считается приведенной, если в каждой строке и каждом столбце содержит не менее одного нуля.
Для приведения исходной матрицы сначала в каждой строке находится наименьший элемент и вычитается из элементов своей строки, затем в приведенной по строкам матрице в каждом столбце находится наименьший элемент и вычитается из элементов своего столбца - получается приведенная матрица.
|
А |
Б |
В |
Г |
Д |
Е |
min |
||
|
А |
- |
4 |
8 |
6 |
12 |
10 |
4 |
|
|
Б |
5 |
- |
5 |
15 |
9 |
14 |
5 |
|
|
В |
10 |
5 |
- |
10 |
5 |
5 |
5 |
|
|
Г |
7 |
14 |
8 |
- |
13 |
8 |
7 |
|
|
Д |
12 |
7 |
6 |
12 |
- |
10 |
6 |
|
|
Е |
11 |
10 |
4 |
10 |
8 |
- |
4 |
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
- |
0 |
4 |
2 |
8 |
6 |
|
|
Б |
0 |
- |
0 |
10 |
4 |
9 |
|
|
В |
5 |
0 |
- |
5 |
0 |
0 |
|
|
Г |
0 |
7 |
1 |
- |
6 |
1 |
|
|
Д |
6 |
1 |
0 |
6 |
- |
4 |
|
|
Е |
7 |
6 |
0 |
6 |
4 |
- |
|
|
min |
0 |
0 |
0 |
2 |
0 |
0 |
Получается приведенная матрица С1:
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
- |
0 |
4 |
0 |
8 |
6 |
|
|
Б |
0 |
- |
0 |
8 |
4 |
9 |
|
|
В |
5 |
0 |
- |
3 |
0 |
0 |
|
|
Г |
0 |
7 |
1 |
- |
6 |
1 |
|
|
Д |
6 |
1 |
0 |
4 |
- |
4 |
|
|
Е |
7 |
6 |
0 |
4 |
4 |
- |
Параллельно с расчетами в матрицах рисуется "дерево маршрута". Исходной вершиной дерева является вершина "все циклы", определяющая все множество возможных вариантов построения кольцевого маршрута по объезду (обходу) заданных пунктов. Для вершин дерева считаются "нижние границы". Нижняя граница вершины "все циклы" равна сумме наименьших элементов строк и столбцов, в результате вычитания которых получена приведенная матрица.
4+5+5+7+6+4+2=33
"Нижняя граница" обозначает: необходимое время на обслуживание маршрута при условии включения заданных пунктов в маршрут в любой произвольной последовательности будет не менее значения "нижней границы" вершины.
Выбор конкретной связи между пунктами производится с помощью характеристик, рассчитываемых для всех нулей приведенной матрицы. Характеристика считается как сумма наименьших элементов строки и столбца приведенной матрицы, в которых находится ноль. Сам ноль, для которого в данный момент считается характеристика, во внимание не берется.
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
- |
0(0) |
4 |
0(3) |
8 |
6 |
|
|
Б |
0(0) |
- |
0(0) |
8 |
4 |
9 |
|
|
В |
5 |
0(0) |
- |
3 |
0(4) |
0(1) |
|
|
Г |
0(1) |
7 |
1 |
- |
6 |
1 |
|
|
Д |
6 |
1 |
0(1) |
4 |
- |
4 |
|
|
Е |
7 |
6 |
0(4) |
4 |
4 |
- |
Ноль с наибольшим значением характеристики указывает на связь между пунктами, к Самым тяжелым оказывается нуль в клетке (ВД) и (ЕВ).которую следует оценить - включать ее в маршрут (РiРj) или от нее следует отказаться.
1. Разобьём множество Д на две части: множество Д вд (все циклы, проходящие через дугу (ДВ)) и (все циклы, не проходящие через дугу (ВД)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С1,1, полученная вычёркиванием соответствующих строки (строку В) и столбца (столбец Д). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ? ; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из города В мы уже не можем проехать в город Д, поэтому в клетке (ДВ) ставим знак ?.
Матрица С1,1
|
А |
Б |
В |
Г |
Е |
||
|
А |
? |
0 |
4 |
0 |
6 |
|
|
Б |
0 |
? |
0 |
8 |
9 |
|
|
Г |
0 |
7 |
1 |
? |
1 |
|
|
Д |
6 |
1 |
? |
4 |
4 |
|
|
Е |
7 |
6 |
0 |
4 |
? |
Матрица С1,1 после приведения
|
А |
Б |
В |
Г |
Е |
||
|
А |
? |
0 |
4 |
0 |
5 |
|
|
Б |
0 |
? |
0 |
8 |
8 |
|
|
Г |
0 |
7 |
1 |
? |
0 |
|
|
Д |
? |
1 |
0 |
4 |
3 |
|
|
Е |
7 |
6 |
0 |
4 |
? |
Сумма констант приведения матрицы С1,1 здесь равна 1, поэтому
ц (Д)=ц=33+1=34
Сопоставим результат ц(Д) множеству Д (ДВ).
Множеству Д, в свою очередь, соответствует другая матрица С1,2, полученная заменой на ? элемент Свд, в матрице С1
Матрица С1,2
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
? |
0 |
4 |
0 |
8 |
6 |
|
|
Б |
0 |
? |
0 |
8 |
4 |
9 |
|
|
В |
5 |
0 |
? |
3 |
? |
0 |
|
|
Г |
0 |
7 |
1 |
? |
6 |
1 |
|
|
Д |
6 |
1 |
0 |
4 |
? |
4 |
|
|
Е |
7 |
6 |
0 |
4 |
4 |
? |
Матрица С1,2 после приведения
|
А |
Б |
В |
Г |
Д |
Е |
||
|
А |
? |
0 |
4 |
0 |
4 |
6 |
|
|
Б |
0 |
? |
0 |
8 |
0 |
9 |
|
|
В |
5 |
0 |
? |
3 |
? |
0 |
|
|
Г |
0 |
7 |
1 |
? |
2 |
1 |
|
|
Д |
6 |
1 |
0 |
4 |
? |
4 |
|
|
Е |
7 |
6 |
0 |
4 |
0 |
? |
Сумма констант приведения матрицы С1,2 здесь равна 4, поэтому
ц (Д)=ц=33+4=37
Теперь выберем наименьшее множество. В нашем случае из множеств, которому соответствует меньшее из чисел ц. (первое)
Поэтому дальнейшей разработке подвергнется множество Д (ДВ). Итак выделена определенная дуга (ДВ) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каком таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдет в искомый гамильтонов цикл, если данная ветвь будет продолжена до конца и иметь минимальный вес. Матрице С1,1,1 подсчитаем вес нулей
|
А |
Б |
В |
Г |
Е |
||
|
А |
? |
0(1) |
4 |
0(4) |
5 |
|
|
Б |
0(0) |
? |
0(0) |
8 |
8 |
|
|
Г |
0(0) |
7 |
1 |
? |
0(3) |
|
|
Д |
? |
1 |
0(1) |
4 |
3 |
|
|
Е |
7 |
6 |
0(4) |
4 |
? |
Самый тяжелый ноль с номером (АГ)
Проведем аналогичное преобразование С1,1,1
|
А |
Б |
В |
Е |
||
|
Б |
0 |
? |
0 |
8 |
|
|
Г |
? |
7 |
1 |
0 |
|
|
Д |
? |
1 |
0 |
3 |
|
|
Е |
7 |
6 |
0 |
? |
Преобразуем
|
А |
Б |
В |
Е |
||
|
Б |
0 |
? |
0 |
8 |
|
|
Г |
? |
6 |
1 |
0 |
|
|
Д |
? |
0 |
0 |
3 |
|
|
Е |
7 |
5 |
0 |
? |
Сумма констант приведения матрицы С1,1,1 здесь равна 1, поэтому
ц (ВД,АГ)=ц=34+1=35
Построим С1,1,2
|
А |
Б |
В |
Г |
Е |
||
|
А |
? |
0 |
4 |
? |
5 |
|
|
Б |
0 |
? |
0 |
8 |
8 |
|
|
Г |
0 |
7 |
1 |
? |
0 |
|
|
Д |
? |
1 |
0 |
4 |
3 |
|
|
Е |
7 |
6 |
0 |
4 |
? |
Приведем матрицу
|
А |
Б |
В |
Г |
Е |
||
|
А |
? |
0 |
4 |
? |
5 |
|
|
Б |
0 |
? |
0 |
4 |
8 |
|
|
Г |
0 |
7 |
1 |
? |
0 |
|
|
Д |
? |
1 |
0 |
0 |
3 |
|
|
Е |
7 |
6 |
0 |
0 |
? |
Сумма констант приведения матрицы С1,1,2 здесь равна 4, поэтому
ц (ВД,АГ)=ц=34+4=38
Сопоставим результат выбираем С1,1,1
|
А |
Б |
В |
Е |
||
|
Б |
0(7) |
? |
0(0) |
8 |
|
|
Г |
? |
6 |
1 |
0(4) |
|
|
Д |
? |
0(5) |
0(1) |
3 |
|
|
Е |
7 |
5 |
0(5) |
? |
Самый тяжелый ноль в БВ, рассмотрим аналогично 2 множества.
Получим С1,1,1,1
|
Б |
В |
Е |
||
|
Г |
6 |
1 |
0 |
|
|
Д |
0 |
0 |
3 |
|
|
Е |
5 |
0 |
? |
Преобразования не требуется, значит ц (ВД,АГ,БВ)=ц=35
Рассмотрим С1,1,1,2
|
А |
Б |
В |
Е |
||
|
Б |
? |
? |
0 |
8 |
|
|
Г |
? |
6 |
1 |
0 |
|
|
Д |
? |
0 |
0 |
3 |
|
|
Е |
7 |
5 |
0 |
? |
Преобразуем
|
А |
Б |
В |
Е |
||
|
Б |
? |
? |
0 |
8 |
|
|
Г |
? |
6 |
1 |
0 |
|
|
Д |
? |
0 |
0 |
3 |
|
|
Е |
0 |
5 |
0 |
? |
Сумма констант приведения матрицы С1,1,1,2 здесь равна 7, поэтому
ц (ВД,АГ,БВ)=ц=35+7=42
Выбираем С1,1,1,1
Д(ВД,АГ,БВ)
|
Б |
В |
Е |
||
|
Г |
6 |
1 |
0(4) |
|
|
Д |
0(5) |
0(0) |
3 |
|
|
Е |
5 |
0(5) |
? |
|
|
В |
Е |
|||
|
Г |
1 |
0 |
||
|
Е |
0 |
? |
Получаем Д(ВД,АГ,БВ,ДБ)
ц (ВД,АГ,БВ,ДБ)=ц=35
|
Б |
В |
Е |
||
|
Г |
6 |
1 |
0 |
|
|
Д |
? |
0 |
3 |
|
|
Е |
5 |
0 |
? |
Преобразуем
|
Б |
В |
Е |
||
|
Г |
1 |
1 |
0 |
|
|
Д |
? |
0 |
3 |
|
|
Е |
0 |
0 |
? |
Сумма констант приведения матрицы С1,1,1,1,2 здесь равна 5, поэтому
ц (Д)=ц=35+5=40
Выбираем С1,1,1,1,1
|
В |
Е |
||
|
Г |
1 |
0(1) |
|
|
Е |
0(1) |
? |
Берем ГЕ
ц (ВД,АГ,БВ,ДБ,ГЕ)=ц=35
|
В |
Е |
||
|
Г |
1 |
? |
|
|
Е |
0(1) |
? |
|
В |
Е |
||
|
Г |
0 |
? |
|
|
Е |
0 |
? |
ц (ВД,АГ,БВ,ДБ,ГЕ)=ц=36
Получаем ц (ВД,АГ,БВ,ДБ,ГЕ)=ц=35
Ответ: В-Д-А-Г-Б-В-Б-Б-Г-Е.
Задача 4
На сетевом графике (рис.4.1) цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.
В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.
Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.
Рисунок 4.1
Решение:
Рассчитаем временные характеристики событий:
|
Событие |
|
|
Ri |
|
|
1 |
0 |
0 |
0 |
|
|
2 |
2 |
8 |
6 |
|
|
3 |
5 |
5 |
0 |
|
|
4 |
6 |
14 |
8 |
|
|
5 |
12 |
12 |
0 |
|
|
6 |
8 |
16 |
8 |
|
|
7 |
18 |
18 |
0 |
- раннее время наступления события
- позднее время наступления события
Ri - резерв времени
Расчетные формулы:
Рассчитаем временные характеристики работ:
|
Код работы (i,j) |
|
|
|
|
Rij |
rij |
||
|
(1,2) |
2 |
0 |
2 |
6 |
8 |
6 |
0 |
|
|
(1,3) |
5 |
0 |
5 |
0 |
5 |
0 |
0 |
|
|
(1,4) |
6 |
0 |
6 |
8 |
14 |
8 |
0 |
|
|
(2,5) |
4 |
2 |
6 |
8 |
12 |
6 |
6 |
|
|
(3,5) |
7 |
5 |
12 |
5 |
12 |
0 |
0 |
|
|
(3,6) |
3 |
5 |
8 |
13 |
16 |
8 |
0 |
|
|
(4,6) |
2 |
6 |
8 |
14 |
16 |
8 |
0 |
|
|
(5,7) |
6 |
12 |
18 |
12 |
18 |
0 |
0 |
|
|
(6,7) |
2 |
8 |
10 |
16 |
18 |
8 |
8 |
Расчетные формулы
- раннее время начала работы
- раннее время окончания работы
- позднее время начала работы
- позднее время окончания работы
- резерв
- частный резерв
На основе данных о продолжительностях работ и частных резервах времени строится линейный календарный план работы по ранним срокам начала некритических работ.
|
Код работы |
tij |
rij |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
|
(1,2) |
2 |
0 |
8 |
8 |
|||||||||||||||||
|
(1,3) |
5 |
0 |
20 |
20 |
20 |
20 |
20 |
||||||||||||||
|
(1,4) |
6 |
0 |
12 |
12 |
12 |
12 |
12 |
12 |
|||||||||||||
|
(2,5) |
4 |
6 |
11 |
11 |
11 |
11 |
|||||||||||||||
|
(3,5) |
7 |
0 |
14 |
14 |
14 |
14 |
14 |
14 |
14 |
||||||||||||
|
(3,6) |
3 |
0 |
11 |
11 |
11 |
||||||||||||||||
|
(4,6) |
2 |
0 |
3 |
3 |
|||||||||||||||||
|
(5,7) |
6 |
0 |
18 |
18 |
18 |
18 |
18 |
18 |
|||||||||||||
|
(6,7) |
2 |
8 |
15 |
15 |
|||||||||||||||||
|
Число рабочих до корректировки |
40 |
40 |
43 |
43 |
43 |
48 |
28 |
28 |
29 |
29 |
14 |
14 |
18 |
18 |
18 |
18 |
18 |
18 |
Если просуммировать число рабочих на каждый день по всем работам и построить по этим данным график движения рабочих, то видно, что он имеет значительные колебания. Следовательно, сетевой график с точки зрения использования рабочей силы составлен неудовлетворительно и должен быть скорректирован с учетом имеющихся ограничений по численности рабочих.
Пользуясь имеющимися запасами времени по некритическим работам, можно изменить их продолжительность или передвинуть их начало, а также выполнить то и другое с таким расчетом, чтобы суммарное число рабочих на каждый день составляло 28 человек.
Шаги корректировки:
1) Первая работа остается без изменений.
2) Вторая (критическая) работа остается без изменений
3) Увеличиваем длительность работы 1-4 до 9 дней, тогда количество рабочих на ней сократится с 12 до 8. Также смещаем ее начало на 3 день.
4) Работу 2-5 растягиваем до 7 дней, сокращая количество рабочих до 6. Также сдвигаем срок ее начала на 6 день.
5) Работа 3-5 критическая, поэтому остается без изменений.
6) Начало работы 3-6 смещаем на 12 день и увеличиваем ее длительность до 4 дней. Тогда численность рабочих сократится до 8 человек
7) Работа 4-6 увеличивается на 1 день и становится 3 дня, тогда число рабочих, занятых на этой работе, сокращается с 3 до 2. Начало работы смещаем на 13 день.
8) Работа 5-7 критическая, поэтому остается без изменений.
9) Работа 6-7 увеличивается на 1 день и становится 3 дня, тогда число рабочих, занятых на этой работе, сокращается с 15 до 10. Начало работы смещаем на 16 день.
Результаты корректировки показаны в таблице
|
Код работы |
tij |
rij |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
|
(1,2) |
2 |
0 |
8 |
8 |
Подобные документы
Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).
контрольная работа [812,0 K], добавлен 29.09.2010Формулирование экономико-математической модели задачи в виде основной задачи линейного программирования. Построение многогранника решений, поиск оптимальной производственной программы путем перебора его вершин. Решение задачи с помощью симплекс-таблиц.
контрольная работа [187,0 K], добавлен 23.05.2010Решение задачи оптимального закрепления грузоотправителей (ГО) за грузополучателями (ГП) и распределения груза для минимизации транспортной работы методами линейного программирования с использованием MS Excel. Расчет кратчайшего расстояния между ГО и ГП.
курсовая работа [357,4 K], добавлен 06.03.2013Построение математической модели, максимизирующей прибыль фирмы от реализации всех сделок в виде задачи линейного программирования. Сущность применения алгоритма венгерского метода. Составление матрицы эффективности, коэффициентов затрат и ресурсов.
контрольная работа [168,7 K], добавлен 08.10.2009- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.
учебное пособие [316,8 K], добавлен 17.10.2010Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
дипломная работа [845,3 K], добавлен 06.08.2013Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Примеры решения задач линейного программирования в Mathcad и Excel. Нахождение минимума функции f(x1, x2) при помощи метода деформируемого многогранника. Построение многофакторного уравнения регрессии для решения экономико-статистической задачи.
курсовая работа [1,3 M], добавлен 17.12.2011Объявление торгов администрацией штата на определенное количество строительных подрядов для определенного количества фирм. Экономико-математическая модели для минимизации затрат. Определение количества песцов и лисиц для получения максимальной прибыли.
контрольная работа [18,2 K], добавлен 05.03.2010Планирование проведения кровельных работ промышленных зданий и сооружений наплавляемыми кровельными материалами силами набольшего количества рабочих. Разработка информационной системы, обеспечивающей решение задачи методом нелинейного программирования.
дипломная работа [2,8 M], добавлен 16.10.2009Транспортная задача линейного программирования, закрытая модель. Создание матрицы перевозок. Вычисление значения целевой функции. Ввод зависимостей из математической модели. Установление параметров задачи. Отчет по результатам транспортной задачи.
контрольная работа [202,1 K], добавлен 17.02.2010Нахождение оптимального значения целевой функции, позволяющей минимизировать себестоимость произведенной продукции. Оптимизационные задачи на максимум выручки от реализации готовой продукции. Экономико-математическая модель технологической матрицы.
контрольная работа [248,8 K], добавлен 25.10.2013Оптимальный план распределения денежных средств между предприятиями. Разработка плана для каждого предприятия, при котором прибыль от вложенных денежных средств примет наибольшее значение. Использование методов линейного и динамического программирования.
курсовая работа [332,2 K], добавлен 16.12.2013Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014
