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

Размещено на 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Д₃₂₁=6-(3-4)=7, д₃₂=5-(5-2)=2.

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

T_Ej=max(T_Ei+t_ij)

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

T_Li=min(T_Lj-t_ij)

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

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

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

Его длина: Т_кр.= T_E911= T_L11=39

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

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

R₁=0-0=0

R₂=9-9=0

R₃=17-17=0

R₄=28-12=16

R₅=34-16=18

R₆=23-23=0

R₇=37-24=13

R₈=35-19=16

R₉=38-12=16

R₁₀=32-32=0

R₁₁=39-39=0

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