Методические указания к заданию № 1

Контрольная работа № 2

Условия заданий

Задание №1

В хозяйстве необходимо за время уборки при заготовке силоса перевезти 4000 т зелёной массы с пяти поля (табл. 1) к четырём силосным траншеям (табл.2).

Количество зелёной массы, перевозимой с полей, т Таблица 1

Предпоследняя цифра шифра Поле
1-е 2-е 3-е 4-е 5-е

Вместимость силосных траншей зелёной массы, т Таблица 2

Последняя цифра шифра Силосная траншея
1-я 2-я 3-я 4-я

Оплата за тонну зелёной массы, перевозимую с полей к силосным траншеям, приведена в табл. 3.

Оплата перевозки тонны зелённой массы от полей до силосных траншей, руб.Таблица 3

Поля Приёмные пункты
1-ый 2-ой 3-ий 4-ый
1-е
2-е
3-е
4-е
5-е

Составить такой план перевозок, чтобы транспортные затраты на перевозку зелёной массы с полей до силосных траншей были минимальными. Опорный план найти методом наименьшего элемента. Оптимальный план найти методом потенциалов.

Задание №2

Рассматривается строительство животноводческого комплекса. Строительство комплекса предполагает выполнение работ, список которых задан: A,B,C,D,E,F,G,H,K,L,M,N. Последовательность выполнения работ определяется сетевым графиком (предпоследняя цифра шифра определяет номер рисунка). Для каждой работы задано время её выполнения (табл. 4).

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

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru Методические указания к заданию № 1 - student2.ru

Методические указания к заданию № 1 - student2.ru

Время выполнения работ Таблица 4

№ работы Работа Время выполнения работы, дни (последняя цифра шифра)
A
B
C
D
E
F
G
H
K
L
M
N

Методические указания по выполнению контрольной работы № 2

Методические указания к заданию № 1.

В хозяйстве необходимо за время уборки при заготовке силоса перевезти 3600 т зелёной массы с пяти поля к четырём силосным траншеям. Зелёная масса каждого поля равна: А1 =400, А2 =500, А3 =700, А4 =900, А5 =1100 т; вместимости силосных траншей равны: В1 =1200, В2 = 600, В3 =800, В4 =1000 т. Оплата за тонну зелёной массы, перевозимую с полей к силосным траншеям, приведена в табл. 5.

Расстояния между полями и приёмными пунктамиТаблица 5

Поля Приёмные пункты
1-ый 2-ой 3-ий 4-ый
1-е
2-е
3-е
4-е
5-е

Составить такой план перевозок, чтобы транспортные затраты были минимальными. Опорный план найти методом наименьшего элемента. Оптимальный план найти методом потенциалов.

Решение. Проверим баланс между общим объёмом А зелёной массы, вывозимой с полей и суммарной вместимостью В силосных траншей. A = a1+a2+a3+a4+a5 = 400+500+700+900+1100 = 3600,

В = b1+b2+b3+b4 = 1200+600+800+1000 =3600. Так как А = В, то задача является закрытой.

Остатки
5 6 2 2  
9 7 4 6  
7 1 600 4 5
5 2 2 4  
6 4 3 4  
Остатки        
Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 4  
6 4 3 4  
Остатки      

Определим опорный план методом наименьшего элемента. Среди всех оплат за перевозку тонны зелёной массы с полями к силосным траншеям выберем самое наименьшее. Это оплата перевозки между третьим полем и второй силосной траншеей с32=1. Осуществляем поставку в клетку (3;2).

Определим объём поставки в эту клетку как минимум из остатка объёма зелёной массы 3 поля и остатка вместимости 2 силосной траншеи. Так как зелёная масса ещё не распределялась, то остатки равны начальным значениям массы и вместимости: 700 и 600 тонн. Минимальным будет остаток 600 т. Поставляем в клетку (3;2) 600 т. Пересчитываем остатки: с 3-го поля осталось перевезти 700 – 600 = 100 т, а остаток вместимости 2-ой силосной траншеи стал равным 600 – 600 = 0. 2-ую силосную траншею вычёркиваем из дальнейшего рассмотрения. Как и во втором задании, будем нумеровать таблицы в левом верхнем углу. Выполненные действия отметим в таблице 1а.

Среди всех оплат за перевозку тонны зелёной массы с полей к силосным траншеям в оставшейся части таблицы выберем минимальное. Это оплаты перевозки с13=2, с14=2 и с43=2. Выбираем клетку (1;4). Определим объём поставки в эту клетку. Перевозки с 1-го поля к 4-той силосной траншее ещё не планировались, то остатки равны: для поля 400 т, для траншеи 1000 т. Минимальным будет остаток 400 т. Поставляем в клетку (1;4) 400 т. Пересчитываем остатки: для 1-го поля: 400 – 400 = 0 т, для 4-ой траншеи: 1000 – 400 = 600 т (табл. 1б). Вычёркиваем 1-ое поле из дальнейшего рассмотрения.

Опять среди всех оплат за перевозку тонны зелёной массы с полей к силосным траншеям в оставшейся части таблицы находим минимальное. Это оплаты перевозки с43=2. Выбираем клетку (4;3). Остатки равны: для поля – 900 т, для

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 800 4
6 4 3 4  
Остатки    

траншеи 800 – т. Минимальным будет остаток 800 т. Поставляем в клетку (4;3) 800 т. Пересчитываем остатки: для поля: 900 – 800 = 100 т, для траншеи: 800 – 800 = 0 т

(табл. 1в). 3-ий пункт вычёркиваем из дальнейшего рассмотрения.

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 800 4
6 4 3 4 600
Остатки   600, 0  
Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 100 2 2 800 4 100, 0
6 4 3 4 600
Остатки 600, 0  

Наименьшая оплата перевозки с44=4, с54=4. Выбираем клетку (5;4).Остатки равны: для поля 1100 т, для траншеи 600 т. Минимальным будет остаток 600 т. Пересчитываем остатки (табл. 1г): для поля 1100 – 600 = 500 т, для траншеи 600 – 600 = 0 т. Вычёркиваем 4-ый пункт.

Минимальная оплата перевозки с41=5. Выбираем клетку (4;1). Остатки равны: для поля–100 т, для траншеи – 1200 т. Минимальным будет остаток 100 т. Делаем поставку в клетку (4;1) в объёме100 т. Пересчитываем остатки: для поля 100 – 100 = 0 т, для траншеи 1200 – 100 =1100 т (табл. 1д).

4-ое поле вычёркиваем из дальнейшего рассмотрения.

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 100 2 2 800 4 100, 0
6 500 4 3 4 600 500, 0
Остатки 1100, 600 600, 0  

Оплата перевозки с51=6. Выбираем клетку (5;1). Остатки равны: поле 500 т, траншея – 1100 т. Минимальным будет остаток 500 т. Поставляем в клетку (5;1) 500 т. Остатки: 500 – 500 = 0 т для поля,

Остатки
5 6 2 2 400
9 7 4 6  
7 100 1 600 4 5 100, 0
5 100 2 2 800 4 100, 0
6 500 4 3 4 600 500, 0
Остатки 1100, 600,500 600, 0  

1100–500=600 т для траншеи

(табл. 1е). 5-ое поле вычёркиваем.

Оплата перевозки с31=7. Выбираем клетку (3;1). Остатки: поле – 100 , траншея – 600 т. Минимальный остаток 100 т. Поставка в клетку (3;1) в объёме 100 т. Пересчитываем

Остатки
5 6 2 2 400
9 500 7 4 6
7 100 1 600 4 5 100, 0
5 100 2 2 800 4 100, 0
6 500 4 3 4 600 500, 0
Остатки 1100, 600,500, 0 600, 0  

остатки: 100 т для поля, для траншеи 100–100 =500 т (табл. 1ж). вычёркиваем 3-е поле.

Осталась последняя клетка, которая не заполнялась, это клетка (2;1). Проверяем баланс остатков: для поля остаток 500, для траншеи 500 т. Баланс есть. Поставляем в клетку остатки зелёной массы и поля и траншеи в размере 500 т и вычёркиваем из рассмотрения и поле, и траншею(табл. 1з).

Мы получили опорный план, построенный методом наименьшего элемента (табл. 1).

Будем искать оптимальный план. Для этого применим метод потенциалов.

5 6 2 2 400
9 500 7 4 6
7 100 1 600 4 5
5 100 2 2 800 4
6 500 4 3 4 600

Методом потенциалов оптимальный план будем находить пошагово. На каждом шаге метода осуществляем переход от одного опорного плана к другому, выполняя следующие действия:

1) вычислим потенциалы полей и силосных траншей;

2) вычислим косвенные издержки для свободных клеток;

3) проверим признак оптимальности плана;

4) одну из свободных клеток выбираем для перераспределения зелённой массы;

5) для выбранной клетки строим цикл перераспределения зелёной массы;

6) пометим клетки цикла знаками «+» и «–»;

7) определим объём перераспределения зелёной массы;

8) строим новый опорный план.

Выполняем действие 1). Вычислим потенциалы полей и силосных траншей по заполненным и условно заполненным клеткам.

ui
5 6 2 2 400
9 500 7 4 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600  
vj        

Произвольно задаём значение одного из потенциалов, например, положим значение потенциала для первого поля u1 равным нулю.

Рассматриваем первую строку (табл. 2а).

В ней ищем нерассмотренные заполненные и условно заполненные клетки. Это клетка (1; 4).

По этой клетке определяем потенциал 4-ой

силосной траншеи: v4 = u1 + c14 = 0 + 2 = 2.

Больше нерассмотренных заполненных и условно заполненных клеток в первой строке нет. Переходим к последнему вычисленному потенциалу, к потенциалу v4 = 2. Это потенциал

ui
5 6 2 2 400
9 500 7 4 * 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600 -2
vj        

4-ой силосной траншеи.

Рассматриваем 4-ый столбец (табл. 2б). Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 4). По этой клетке определяем потенциал 5-ого поля: u5 = v4 – c54 = 2 – 4 = –2. Больше нерассмотренных заполненных и условно

заполненных клеток в четвёртом столбце нет. Переходим к последнему вычисленному потенциалу, к потенциалу u5 = –2. Это потенциал 5-ого поля.

ui
5 6 2 2 400
9 500 7 4 * 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600 -2
vj      

Рассматриваем 5-ую строку (табл. 2в). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 1). По этой клетке определяем потенциал 1-ой силосной траншеи: v1 = u5 + c51 = –2 + 6 = 4. Больше нерассмотренных заполненных и условно заполненных клеток в пятой строке нет.

Переходим к последнему вычисленному потенциалу, к потенциалу v1 = –2. Это потенциал 1-ой силосной траншеи.

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj      

Рассматриваем 1-ый столбец (табл. 2г). Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетки (2; 1), (3; 1) и (4; 1). По этим клеткам определяем потенциалы 2-ого, 3-его и 4-го полей: u2 = v1 – c21 = 4 – 9 = –5, u3 = v1 – c31 = 4 – 7 = –3, u4 = v1 – c41 = 4 – 5 = –1.

Больше нерассмотренных заполненных и условно заполненных клеток в четвёртом столбце нет. Переходим к последним вычисленным потенциалам, к потенциалам u2 = –5, u3 = –3 и

u4 = –1. Это потенциалы 2-ого поля, 3-его поля и 4-ого поля.

Сначала рассмотрим 2-ую строку (табл. 2д). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет.

Переходим к следующему вычисленному потенциалу, к потенциалу u3 = –3. Это потенциал 3-его поля.

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2    

Рассматриваем 3-ю строку (табл. 2д). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (3; 2). По этой клетке определяем потенциал 2-ой силосной траншеи: v2 = u3 + c32 = –3 + 1 = –2. Больше нерассмотренных заполненных и условно заполненных клеток в третьей строке нет.

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

Переходим к следующему вычисленному потенциалу, к потенциалу u4 = –1. Это потенциал 4-тьего поля.

Рассматриваем 4-ую строку (табл. 2е). Находим в этом строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (4; 3). По этой клетке определяем потенциал

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

3-ей силосной траншеи: v3 = u4 + c43 = –1 + 2 = 1. Больше нерассмотренных заполненных и условно заполненных клеток в четвёртой строке нет.

Мы вычислили все потенциалы. Результаты вычислений представлены таблицей 2.

Переходим к выполнению следующего пункта шага метода потенциалов.

2) вычислим косвенные издержки для свободных клеток, которые обозначим Δij .

Косвенные издержки для свободных клеток вычисляем по формуле: Δij = cij – ( vj – ui ).Δ11 =5–(4 – 0)=1 ; Δ12 =6–(-2–0) =8; Δ13 =2 – (1 – 0) = 1; Δ22=7 –(–2+5)=4;

Δ23 = 4 – (1+5) = – 2; Δ24 = 6–(2+5) = – 1; Δ33 = 4 – (1+ 3) = 0; Δ34 = 5 – (2+3)= 0; Δ42=2–( – 2+1) = 3; Δ44=4–(2+1)=1; Δ52 =4 – (–2+2) = 4; Δ53 = 3 – (1+2) = 0.

3) Проверяем признак оптимальности плана: если для всех свободных клеток косвенные издержки положительные (Δij ≥ 0), то опорный план является оптимальным.

План не оптимальный, так как Δ23 = – 2 < 0 и Δ24 = – 1 < 0.

4) Выбираем клетку для перераспределения зелённой массы. Это одна из клеток таблицы, для которой косвенные издержки строго отрицательные. Выбираем клетку (2;3).

5) Для выбранной клетки (2;3) строим цикл перераспределения зелёной массы.

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  
ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

Выбранную свободную клетку (2;3) включаем в цикл. Далее рассматриваем строку,

содержащую эту клетку. Это вторая строка. Во второй строке ищем заполненные и условно заполненные клетки (табл. 2ж). Такие клетки есть, это клетка (2;1). Так как она единственная, то её включаем в цикл (рис. 2а) и переходим к ней.

Рассматриваем столбец, содержащий включённую в цикл клетку (2;1). Это первый столбец. В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (3;1), (4;1) и (5;1) (табл. 2з). Выбираем любую из них, например клетку (3;1). Включаем её в цикл (рис. 2б). Переходим к ней.

Рассматриваем строку, содержащую эту клетку. Это третья строка. В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и). Такие клетки есть, это клетка (3;2). Так как она единственная, то её включаем в цикл (рис. 2в) и переходим к ней.

Методические указания к заданию № 1 - student2.ru

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

Рассматриваем столбец, содержащий клетку (3;2). Это второй столбец. В столбце находим нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет. Вычёркиваем клетку (3;2) из цикла и переходим к предыдущей клетке цикла, к клетке (3;1) (рис. 2г).

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

Опять рассматриваем третью строку. В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и). Клетки (3;1) и (3;2) уже рассматривались, других клеток нет. Вычёркиваем клетку (3;1) из цикла и переходим к предыдущей клетке цикла, к клетке (2;1) (рис. 2д). Снова рассматриваем столбец, содержащий клетку (2;1). В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (4;1) и (5;1), клетки (2;1) и (3;1) уже рассматривались (табл. 2з). Выбираем любую из них, например клетку (4;1). Включаем её в цикл (рис. 2е). Переходим к ней. Рассматриваем строку, содержащую клетку (4;1). Это четвёртая строка (табл. 2к). В этой строке есть заполненная клетка, которая располагается в том же столбце, что и начальная клетка цикла, клетка (2; 3). Это клетка (4; 3). Автоматически её включаем в цикл, и цикл замыкаем (рис. 2е).

Построенный цикл для свободной клетки (2; 3) изображён на рисунке 2ж.

6) Пометим клетки цикла знаками «+» и «–». Помечать клетки цикла начнём со свободной клетки цикла, клетки (2; 3). Её пометим знаком «+». Далее, двигаясь по циклу в направлении его построения, помечаем остальные клетки цикла, чередуя знаки (рис. 3). Методические указания к заданию № 1 - student2.ru Клетку (2; 1) пометим знаком «–», клетку (4;1) знаком «+», клетку (4;3) знаком «–». В клетки, помеченные знаком «+» зелёную массу будем добавлять, а из клеток, помеченных знаком «–» зелёную массу будем забирать. Клетками, откуда зелёная масса забирается, будут (2;1) и (4;3).

7) Определим объём перераспределения зелёной массы. Объём перераспределения зелённой массы ΔV равняется наименьшему из объёмов отрицательных клеток цикла. В клетке (2; 1) объём поставки зелёной массы равняется 500 т, а в клетке (4;3) – 800 т (рис. 5). Поэтому объём перераспределения зелёной массы ΔV равен: ΔV = min{500; 800}= 500 т.

Методические указания к заданию № 1 - student2.ru 8) Строим новый опорный план. Сначала пересчитываем объёмы зелёной массы для клеток цикла (табл. 3): для клетки (2; 3) новый объём равен

x23 = 0 + 500 = 500 т, для клетки (2; 1) новый объём равен

ui
5 6 2 2 400
9 7 4 500 6 -3
7 100 1 600 4 5 -3
5 600 2 2 300 4 -1
6 500 4 3 4 600 -2
vj -2  

x21 = 500 – 500 = 0 т, для клетки (4; 1) новый объём равен x41 = 100 + 500 = 600 т, для клетки (4; 3) новый объём равен x43 = 800 – 500 = 300 т. Объём клетки (2; 1) стал равным нулю, её переводим в ранг свободных, а клетку (2; 3) переводим в ранг заполненных. Объёмы остальных клеток таблицы, не вошедших в цикл, не меняются: x14 = 400, x31 = 100, x32 = 600, x51 = 500, x54 = 600 (табл. 3). Шаг метода потенциалов закончен. Переходим к новому шагу. В качестве опорного рассматриваем план, соответствующий таблице 3.

1) Вычислим потенциалы полей и силосных траншей (табл. 3).

2) Вычислим косвенные издержки для свободных клеток: Δ11 =5–(4–0)=1 ; Δ12 =6–(–2–0) =8;

Δ13 =2–(1–0)=1; Δ21 =9–(4+3) = 2; Δ22 =7–(–2+3)=6; Δ24=6–(2+3)=1; Δ33=4–(1+3)=0; Δ34=5–(2+3) =0; Δ42=2–(–2+1)=3; Δ44 =4–(2+1) =1; Δ52=4–(–2+2)=4; Δ53=3–(1+2) = 0.

3) Проверим признак оптимальности плана. План оптимальный, так как для всех свободных клеток косвенные издержки больше либо равны нуля (Δij ≥ 0).

По таблице 3 выписываем оптимальный план: X* = Методические указания к заданию № 1 - student2.ru .

Для оптимального плана рассчитываем суммарные транспортные издержки:

Zmin = 2∙400 +4∙500 +7∙100 +1∙600 +5∙600+ +2∙300 +6∙500 +4∙600 = 13100.

Выписываем ответ: X* = Методические указания к заданию № 1 - student2.ru ; Zmin= 13100.

Наши рекомендации