Автор работы: Пользователь скрыл имя, 02 Октября 2011 в 19:02, контрольная работа
Дано: Для производства двух видов продукции А и В можно используется сырьё трёх видов. При этом на изготовление единицы изделия А расходуется 2 ед. сырья первого вида, 4 – ед. 2-го и 3 – ед. 3-го вида. На изготовление единицы изделия В расходуется 3 ед. сырья 1-го вида, 2 – ед. 2-го вида, 5 – ед. 3-го вида сырья. На складе фабрики имеется сырья 1-го вида 35 ед., 2-го – 42, 3-го – 49 ед. От реализации единицы готовой продукции А фабрика имеет прибыль 3 тыс. руб., а от продукции В прибыль составляет 3 тыс. руб.
СОДЕРЖАНИЕ
1.Симплексный метод в линейном программировании.
2.Двойственность в линейном программировании.
3.Транспортная задача.
4.Сетевое планирование и управление. Расчёт основных показателей.
Библиографический список.
План не оптимален т.к. Е21<0. Z=1580-70=1510
Θmin(40;90)=40 ,Δz=-1*40=-80. Получим следующий план:
|
План является оптимальным т.к. все характеристики Eij≥0, но не единственным есть еще три оптимальных решения т.к. E13, E25, E43=0, но
zmin = 1470.
Ответ: Минимальные транспортные расходы равны 1470. Оптимальный план представлен выше.
Дано:
Задана следующая последовательность
работ с их временными характеристиками:
Работа | (1,2) | (1,3) | (1,4) | (2,4) | (2,5) | (3,4) | (3,6) | (4,5) | (4,6) |
Продолжительность | 8 | 9 | 10 | 11 | 12 | 11 | 8 | 13 | 10 |
(4,7) | (5,7) | (5,8) | (6,7) | (6,9) | (7,8) | (7,9) | (7,10) | (8,10) | (9,10) |
11 | 13 | 13 | 16 | 17 | 10 | 13 | 17 | 15 | 11 |
Найти: Построить сеть. Определить временные характеристики ее работ и событий, критический путь и его длину.
Решение:
Построим сетевой график:
2
5
8 11 13 13 10 15
1 10 4 11 7 17 10
9 11 10 16 13 11
3
Самыми распространенными методами расчета временных параметров сетевой модели являются табличный и матричный. Исходную информацию следует привести к табличной либо матричной форме. Как табличный, так и матричный метод расчета временных параметров сетевой модели основывается на следующих соотношениях, вытекающих из определений временных параметров:
Составим матрицу, число столбцов и строк равно числу событий, в нашем случае 10.
Сначала заполняем числители. События [i] и [j] соединяются работой, продолжительность этой работы tij заносим в числители двух клеток: клетки, лежащей на пересечении i-й строки и j-го столбца, и клетки лежащей на пересечении j-й строки и i-го столбца. Числители остальных клеток, кроме клеток, лежащих на главной диагонали матрицы, заполняем нулями или вообще не заполняются, как в нашем случае.
Раннее время наступления исходного события сетевой модели равно 0, заносим его в числитель первой клетки главной диагонали.
Затем заполняем знаменатели клеток, лежащих справа (или над) главной диагональю, чьи числители > 0. Значения, которые проставляем в знаменатели, вычисляем как сумму числителя клетки данной строки, лежащей на главной диагонали, и числителя заполняемой клетки, т.е. мы подсчитываем раннее время окончания соответствующей работы.
Далее определяем числитель диагональной клетки второй строки, это значение соответствует раннему времени наступления события 2. Раннее время некоторого события, являющегося конечным для нескольких работ, равно моменту раннего окончания самой поздней из работ, которые заканчиваются данным событием. Значит, смотрим знаменатели клеток столбца 2 сверху вниз до главной диагонали и выбираем максимальное значение, заносим его.
Повторяем процедуры до тех пор, пока не будет найден числитель последней диагональной клетки.
Дойдя до последней диагональной клетки, получили значение раннего времени наступления завершающего события сетевой модели, которое определяет продолжительность критического пути. Для завершающего события, раннее время равно позднему времени его наступления, т.е. знаменатель этой клетки будет равен ее числителю. Запишем это.
Получив значение знаменателя последней диагональной клетки, вычисляем значения знаменателей клеток (чьи числители больше 0), находящихся в той же строке слева (ниже) от главной диагонали. Они равны разнице значения знаменателя соответствующей диагональной клетки и значения числителя клетки, для которой производится расчет, что соответствует позднему времени начала работы.
После
подсчета всех знаменателей в последней
строке находим знаменатель в диагональной
клетке на предпоследней строке. Оно будет
равно минимальному значению из знаменателей
всех клеток, лежащих в данном столбце
ниже главной диагонали, т.е. позднему
времени наступления
события. Заполняем матрицу до конца
и получим.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
1 | 0 | 8 | 9 | 10 | ||||||
0 | 8 | 9 | 10 | |||||||
2 | 8 | 8 | 11 | 12 | ||||||
9 | 9 | 19 | 20 | |||||||
3 | 9 | 9 | 11 | 8 | ||||||
0 | 9 | 20 | 17 | |||||||
4 | 10 | 11 | 11 | 20 | 13 | 10 | 11 | |||
10 | 9 | 9 | 20 | 33 | 30 | 31 | ||||
5 | 12 | 13 | 33 | 13 | ||||||
21 | 20 | 33 | 46 | 46 | ||||||
6 | 8 | 10 | 30 | 16 | 17 | |||||
22 | 20 | 30 | 46 | 47 | ||||||
7 | 11 | 13 | 16 | 46 | 10 | 13 | 17 | |||
35 | 33 | 30 | 46 | 56 | 59 | 63 | ||||
8 | 13 | 10 | 56 | 15 | ||||||
43 | 46 | 56 | 71 | |||||||
9 | 17 | 13 | 59 | 11 | ||||||
43 | 47 | 60 | 70 | |||||||
10 | 17 | 15 | 11 | 71 | ||||||
54 | 56 | 60 | 71 |
Из заполненной матрицы нетрудно увидеть не только продолжительность критического пути (числитель или знаменатель последней диагональной клетки), но также сам критический путь. Он проходит через события, у которых раннее и позднее время наступления равны, т.е. через события, у которых в соответствующих диагональных клетках совпадают числители и знаменатели. В нашем примере это будут события 1, 3, 4, 5, 6, 7, 8, 10. И его длительность равна 71. (5,6,7=5-7)
В соответствии с формулами резервов приведенных выше, полный резерв времени выполнения работы, находящейся между событиями i и j, определяется разностью значений знаменателя диагональной клетки j-j и знаменателя клетки j в строке i выше главной диагонали.
Свободный резерв времени выполнения работы, находящейся между событиями i и j, необходимо из числителя диагональной клетки j-j вычесть числитель диагональной клетки i-i и числитель клетки i-j.
Независимый резерв времени выполнения работы, находящейся между событиями i и j, необходимо из числителя диагональной клетки j-j вычесть знаменатель диагональной клетки i-i и числитель клетки i-j.
Резервы
времени событий вдоль
Временные характеристики работ.
Работа | TS | FS |
(1,2) | 1 | 0 |
(1,3) | 0 | 0 |
(1,4) | 10 | 10 |
(2,4) | 1 | 1 |
(2,5) | 13 | 13 |
(3,4) | 0 | 0 |
(3,6) | 13 | 13 |
(4,5) | 0 | 0 |
(4,6) | 0 | 0 |
(4,7) | 15 | 15 |
(5,7) | 0 | 0 |
(5,8) | 10 | 10 |
(6,7) | 0 | 0 |
(6,9) | 13 | 12 |
(7,8) | 0 | 0 |
(7,9) | 1 | 0 |
(7,10) | 8 | 8 |
(8,10) | 0 | 0 |
(9,10) | 1 | 1 |