Построение сетевого графика

Поиск графическим способом максимального и минимального значения целевой функции при заданных ограничениях на переменные. Формирование пропускных особенностей ребер (одинаковые в обоих направлениях). Специфика формирования потока максимальной мощности.

Рубрика Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид контрольная работа
Язык русский
Дата добавления 04.12.2014
Размер файла 82,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. Найти графическим способом максимальное и минимальное значения целевой функции Z при заданных ограничениях на переменные

Решим задачу графически.

Строим в системе координат хоу прямые

Строим графическое решение:

Находим полуплоскости, определяемые системой. Так как неравенства системы выполняется для любой точки из соответствующей полуплоскости, то их достаточно проверить для какой-либо одной точки. Используем точку (0;0). Подставим её координаты в первое неравенство системы. Т.к. , то неравенство определяет полуплоскость, содержащую точку (0;0). Аналогично определяем остальные полуплоскости. Находим множество допустимых решений как общую часть полученных полуплоскостей- это заштрихованная область.

Строим вектор и перпендикулярно к нему прямую нулевого уровня. переменный поток мощность графический

(4)

Перемещая прямую (4) в направлении вектора и видим, что у области максимальная точка находится в точке пересечения прямой (2) и прямой (3) точке А.

Точку найдём из решения системы уравнений:

Функция z(x,y) достигает наибольшего значения при х=10, у=2. Наибольшее значение функции равно .

Перемещая прямую (4) в направлении, противоположном вектору и видим, что у области минимальная точка находится в точке В пересечения прямой (1) и прямой (3).

Точку найдём из решения системы уравнений:

Функция z(x,y) достигает наименьшего значения при х=2, у=4. Наименьшее значение функции равно .

2. Найти симплексным методом минимум целевой функции Z

Итак, математическая модель задачи имеет вид:

Перейдем к канонической форме задачи линейного программирования, введя дополнительные переменные х3, х45:

Решим полученную задачу линейного программирования симплексным методом. Составим начальную симплексную таблицу по данным модели.

БП

СБ

а0

х1

х2

х3

х4

х5

О

-3

4

0

0

0

x3

0

6

-1

2

1

0

0

-

x4

0

6

1

1

0

1

0

6

x5

0

3

1

-2

0

0

1

3

дельта

0

3

-4

0

0

0

Полученный план (0;0;6;6;3) является опорным решением, но не является оптимальным, т.к. в индексной строке есть положительные элементы. Наибольший положительный элемент (3) индексной строки указывает на то, что в новый базис следует ввести переменную х1. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

Запишем данные задачи в виде таблицы:

БП

СБ

а0

х1

х2

х3

х4

х5

О

-3

4

0

0

0

x3

0

9

0

0

1

0

1

-

x4

0

3

0

3

0

1

-1

1

x1

-3

3

1

-2

0

0

1

-

дельта

-9

0

2

0

0

-3

Наибольший положительный элемент (2) индексной строки указывает на то, что в новый базис следует ввести переменную х2. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

Запишем данные задачи в виде таблицы:

БП

СБ

а0

х1

х2

х3

х4

х5

-3

4

0

0

0

x3

0

9

0

0

1

0

1

x2

4

1

0

1

0

0,3333

-0,333

x1

-3

5

1

0

0

0,6667

0,3333

дельта

-11

0

0

0

-0,667

-2,333

Т. к. теперь все дельта меньше нуля, то дальнейшее уменьшение значения функции цели Z невозможно и мы получили оптимальный план:

Х=(5;1;9;0;0) . Тогда

3. Составить план перевозок однородной продукции из трех пунктов отправления в три пункта назначения. План должен обеспечить минимальные транспортные издержки и полностью удовлетворить спрос потребителей. Запасы , потребности и стоимости ( ) перевозки единицы продукции известны.

Запишем условие в таблице:

Поставщики

Потребители

Запас груза аi

В1

В2

В3

A1

2

5

125

25

A2

3

115

415

30

A3

1

35

5

6

5

40

Потребность в грузе вj

35

15

45

95

Загрузка начинается с клетки, которой соответствует наименьший тариф сij из всей матрицы тарифов. Пусть такая клетка (2;2) с22=1.В клетку (2;2) вписываем число х22=min(15;30)=15 и исключаем из дальнейшего рассмотрения второй столбец. Из оставшихся тарифов наименьший для клетки (1;3), с13=1. В клетку (1;3) вписываем min(45;25)=25. Исключаем из дальнейшего рассмотрения первую строку. Из оставшихся тарифов наименьший для клетки (3;1), с31=3. В клетку (3;1) вписываем min(35;40)=35. Исключаем из дальнейшего рассмотрения первый столбец. Из оставшихся тарифов наименьший для клетки (2;3), с23=4. В клетку (2;3) вписываем min(45-25;30-15)=15. Исключаем из дальнейшего рассмотрения третий столбец. Из оставшихся тарифов наименьший для клетки (3;3), с33=6. В клетку (3;3) вписываем min(40-35;45-25-15)=5. В результате полного распределения грузов получаем исходное опорное решение. В таблице получен невырожденный план, т.к. число загруженных клеток удовлетворяет условию и m+n-1=3+3-1=5.

Для определения потенциалов поставщиков и потребителей имеем систему уравнений:

Поскольку число уравнений системы на единицу меньше числа потенциалов ( система неопределённая), для её решения одному из потенциалов придаётся произвольное значение. Положим u1=0. Все остальные потенциалы определяются однозначно. Найденные потенциалы поставщиков и потребителей указаны справа и внизу в клетках таблицы:

35

15

45

25

2

5

125

0

30

3

115

415

3

40

1

35

5

6

5

5

-4

-2

1

Определяем оценки свободных клеток: д11=2-(0-4)=6, д12 =5-(0-2)=7,

Д321=6-(3-4)=7, д32=5-(5-2)=2.

Полученный план оптимален и единственный. Среди оценок не имеется отрицательных.

Для этого плана значение целевой функции

.

4. На заданной сети указаны пропускные особенности ребер (одинаковые в обоих направлениях). Сформировать на сети поток максимальной мощности, направленный из истока I в исток S

Размещено на http://www.allbest.ru/

Пропускные способности запишем в виде матрицы:

R

1

2

3

4

5

6

7

8

9

10

1

0

7

9

2

0

0

0

0

0

0

2

7

0

0

3

0

5

0

6

0

0

3

9

0

0

0

6

0

0

0

0

0

4

2

3

0

0

8

7

2

0

0

0

5

0

0

6

8

0

0

7

0

0

4

6

0

5

0

7

0

0

5

9

4

0

7

0

0

0

2

7

5

0

0

0

9

8

0

6

0

0

0

9

0

0

6

0

9

0

0

0

0

0

4

0

6

0

8

10

0

0

0

0

4

0

9

0

8

0

Сформируем начальный поток:

По пути L1: 1-3-5-7-10 пропустим 6 единиц (min(9,6,7,9)=6).

По пути L2: 1-4-7-10 пропустим 2 единицы (min(2,2,9)=2).

По пути L3: 1-2-8-9-10 пропустим 6 единиц (min(7,6,6,8)=6).

Потоки по ребрам:

Потоки по остальным ребрам равны нулю. Совокупность перечисленных потоков по ребрам составит поток Х0 по сети. Запишем его в виде матрицы:

Х0

1

2

3

4

5

6

7

8

9

10

1

0

6

6

2

0

0

0

0

0

0

14

2

-6

0

0

0

0

0

0

6

0

0

0

3

-6

0

0

0

6

0

0

0

0

0

0

4

-2

0

0

0

0

0

2

0

0

0

0

5

0

0

-6

0

0

0

6

0

0

0

0

6

0

0

0

0

0

0

0

0

0

0

0

7

0

0

0

-2

-6

0

0

0

0

8

0

8

0

-6

0

0

0

0

0

0

6

0

0

9

0

0

0

0

0

0

0

-6

0

6

0

10

0

0

0

0

0

0

-8

0

-6

0

0

0

0

0

0

0

0

0

14

Составляем матрицу R=X0,

ее элементы позволяют судить о насыщенности ребер.

R

1

2

3

4

5

6

7

8

9

10

1

0

1

3

0

0

0

0

0

0

0

2

13

0

0

3

0

5

0

0

0

0

3

15

0

0

0

0

0

0

0

0

0

4

4

3

0

0

8

7

0

0

0

0

5

0

0

12

8

0

0

1

0

0

4

6

0

5

0

7

0

0

5

9

4

0

7

0

0

0

4

13

5

0

0

0

1

8

0

12

0

0

0

9

0

0

0

0

9

0

0

0

0

0

4

0

12

0

2

10

0

0

0

0

4

0

17

0

14

0

Рассмотрим возможность пройти по ненасыщенным ребрам из вершины J в вершину S. Такой путь существует: 1-2-6-9-10, поток Х0 немаксимальный.

Находим величину на которую надо увеличить поток по ребрам (1,2), (2,6), (6,9), (9,10), чтобы получить более мощный поток.

Составляем поток Х1 и проверяем его на оптимальность матрицей

Х1

1

2

3

4

5

6

7

8

9

10

1

0

7

6

2

0

0

0

0

0

0

15

2

-7

0

0

0

0

1

0

6

0

0

0

3

-6

0

0

0

6

0

0

0

0

0

0

4

-2

0

0

0

0

0

2

0

0

0

0

5

0

0

-6

0

0

0

6

0

0

0

0

6

0

-1

0

0

0

0

0

0

1

0

0

7

0

0

0

-2

-6

0

0

0

0

8

0

8

0

-6

0

0

0

0

0

0

6

0

0

9

0

0

0

0

0

-1

0

-6

0

7

0

10

0

0

0

0

0

0

-8

0

-7

0

0

0

0

0

0

0

0

0

15

Составляем матрицу R1=X1,

ее элементы позволяют судить о насыщенности ребер.

R1

1

2

3

4

5

6

7

8

9

10

1

0

0

3

0

0

0

0

0

0

0

2

14

0

0

3

0

4

0

0

0

0

3

15

0

0

0

0

0

0

0

0

0

4

4

3

0

0

8

7

0

0

0

0

5

0

0

12

8

0

0

1

0

0

4

6

0

6

0

7

0

0

5

9

3

0

7

0

0

0

4

13

5

0

0

0

1

8

0

12

0

0

0

9

0

0

0

0

9

0

0

0

0

0

5

0

12

0

1

10

0

0

0

0

4

0

17

0

15

0

Такой путь отсутствует, значит, поток Х2 максимальный, его мощность .

Размещено на http://www.allbest.ru/

5. Для данного сетевого графика комплекса работ рассчитать

1. ранние сроки свершения событий;

2. поздние сроки свершения событий;

3. резервы времени событий;

4. время выполнения комплекса и критический путь.

Построим сетевой график, проложим критический путь и определим его длину (критическое время).

Размещено на http://www.allbest.ru/

Критическое время - минимально необходимое время.

Задача оптимизации сетевого графика комплекса работ сводится к сокращению критического пути. Этого можно добиться, во -первых, логической перестройкой сети так, чтобы работы, лежащие на нём, выполнялись не последовательно, а параллельно (совершенствование методов работы), во-вторых, сокращением продолжительности работ, лежащих на критическом пути (применение более совершенных технических средств, механизация, автоматизация процессов и т.д.). Первый путь требует организационных мер, второй - капитальных вложений.

В левом секторе исходного события 1 ставим ноль. Переходим ко второму событию. В него входит только работа (1,2) продолжительностью t12=9, поэтому в левом секторе второго события запишем 9 (9+0=9), в нижний записываем 0 (резерв времени).

Далее левые и нижние секторы событий будут заполнены по следующим формулам:

Ранние сроки свершения событий:

TEj=max(TEi+tij)

Поздние сроки свершения событий:

TLi=min(TLj-tij)

TE2=0+9=9;

TE3=max(0+4;9+8)=17;

TE4=3+9=12;

TE5=7+9=16;

TE6=17+6=23;

TE7=max(17+2;16+8)=24;

TE8= 12+7=19;

TE9=max(12+5;19+3;15+8)=22;

TE910=23+9=32;

TE11=max(22+1;16+5;24+2;23+4;32+7)=39;

Двигаясь по графу в обратном направлении, получим:

TL11=39

TL10=39-7=32

TL9=39-1=38

TL8=38-3=35

TL7=39-2=37

TL6=min(32-9;39-4)=23

TL5=39-5=34

TL4=min(35-7;38-5)=28

TL3=min(37-2;23-6)=17

TL2=min(17-8;34-7;28-3)=9

TL1=min(9-9;17-4)=0

Определение критического пути ведётся от последнего события сети. Необходимо иметь в виду тот факт, что события и работы, лежащие на критическом пути, не имеют резервов времени, и критический путь по определению выбирается как самый длинный из полных путей.

Критический путь: 1-2-3-6-10-11.

Его длина: Ткр.= TE911= TL11=39

Резерв времени Ri для событий, лежащих на критическом пути ,Ri=0, т.к. TEi=TLi.

Ri= TLi- TEi показывает, на какое время можно задержать событие, не изменяя общего срока выполнения процесса.

R1=0-0=0

R2=9-9=0

R3=17-17=0

R4=28-12=16

R5=34-16=18

R6=23-23=0

R7=37-24=13

R8=35-19=16

R9=38-12=16

R10=32-32=0

R11=39-39=0

Размещено на Allbest.ru


Подобные документы

  • Расчет параметров каналообразующего устройства и выбор метода модуляции. Построение структурной схемы каналообразующего устройства. Обмен данными в обоих направлениях. Предельное значение скорости передачи информации. Спектральная плотность мощности шума.

    курсовая работа [189,1 K], добавлен 13.12.2013

  • Расчет номинального значения петлевого усиления, параметров сглаживающих цепей и минимального значения отношения мощности сигнала к мощности помехи. Системы автоматической подстройки частоты на примере функциональной схемы супергетеродинного приемника.

    курсовая работа [211,3 K], добавлен 24.04.2009

  • Определение поля ХН и построение графика поляризации передающей антенны в плоскости падения без учета влияния земли. Расчет зависимости поля E(p) на трассе от усредненного угла наблюдения. Вычисление максимальной мощности на входе радиоприемника.

    контрольная работа [360,9 K], добавлен 20.09.2011

  • Формирование математической модели сигнала и построение ее графика. Спектральный состав сигнала. Исследования спектрального состава сигнала с помощью быстрых преобразований ряда Фурье. Построение графика обработанного сигнала. Верхняя граничная частота.

    курсовая работа [187,7 K], добавлен 14.08.2012

  • Принципы формирования трехмерной картинки и их использование в современных технологиях 3D-виденья. Основные понятия трехмерной графики. Сущность стереодисплея. Современные 3D-телевизоры: анализ конструктивных особенностей нескольких моделей ведущих фирм.

    реферат [21,7 K], добавлен 15.12.2013

  • Расчет количественных характеристик надежности невосстанавливаемых элементов, построение графика их зависимости от времени. Определение времени безотказной работы и восстановления системы после отказа. Расчет надежности триггера при заданных параметрах.

    контрольная работа [438,5 K], добавлен 10.02.2013

  • Усилитель звуковых частот. Расчёт оконечного каскада. Выбор транзисторов по допустимой мощности рассеяния на коллекторе и максимальной амплитуде коллекторного тока. Выбор входного транзистора, расчет входных элементов. Расчет мощности элементов схемы.

    курсовая работа [618,3 K], добавлен 12.03.2016

  • Способ определения сухости пара. Разработка топологии печатной платы. Технология программирования микроконтроллеров. Построение оптимизированного сетевого графика. Технология разработки работы по интерфейсу USB. Расчет сметной стоимости проектирования.

    дипломная работа [1,4 M], добавлен 12.12.2013

  • Определение затухания (ослабления), дисперсии, полосы пропускания, максимальной скорости передачи двоичных импульсов в волоконно-оптической системе. Построение зависимости выходной мощности источника оптического излучения от величины электрического тока.

    контрольная работа [352,3 K], добавлен 21.06.2010

  • Рассчитаем параметров малосигнальной модели биполярного транзистора. Определение минимального и максимального значений коэффициента передачи тока, емкости разделительных и блокировочного конденсаторов. Нахождение потенциалов эмиттеров транзисторов.

    контрольная работа [553,7 K], добавлен 17.06.2015

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.