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

Федеральное Государственное образовательное учреждение высшего профессионального образования

Пермская государственная сельскохозяйственная академия имени академика Д.Н.Прянишникова

Кафедра Информационных систем

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

по дисциплине:

«Экономико-математические методы и модели»

на тему:

«Сетевое планирование и управление. Построение сетевых моделей»

Вариант 21 (m=4, n=3)

Выполнил:

студент 2 курса заочного отделения

по специальности: 060800 «Экономика и

управление на предприятиях АПК»

шифр ЭКР-2010-404 Стариков

Проверил: О.Ю. Вшивков

Пермь-2015

Содержание

1. Сетевое планирование и управление. Построение сетевых моделей

. Задача линейного программирования

. Транспортная задача

Список использованной литературы

1. Сетевое планирование и управление. Построение сетевых моделей

Понятие графа (graph) обычно связывают с именем великого математика Леонарда Эйлера, который в первой половине XVIII века решил ряд задач, связанных с использованием этого понятия, и в частности знаменитую задачу о «кенигсберских мостах» (1736 г.). Суть этой задачи состоит в том, чтобы пройти лишь один раз по каждому из семи мостов, соединяющих берега и два острова реки Прегель, на которых расположен г. Кенигсберг (ныне г. Калининград), побывав, таким образом, во всех районах города и вернувшись в исходную точку.

Исследуя данную частную задачу, Эйлер получил ряд интересных математических результатов более общего характера, заложив, тем самым, основы теории графов. Как самостоятельная научная математическая дисциплина теория графов сформировалась спустя два столетия, в 1930-х гг. (термин «граф» впервые был введен Д. Кенигом в 1936 г.), и с того времени развивается и находит широкое применение во многих областях науки и техники. В частности, теория графов используется при решении ряда экономико-математических задач, связанных с планированием и управлением разработкой сложных проектов, задачей о назначениях, задачей календарного планирования и т.д.

Геометрически граф представляет собой множество точек (вершин графа), соединенных отрезками линий (ребрами графа).

Математически структура графа может быть представлена с помощью двух типов матриц - матрицы смежности и матрицы инцидентности. Матрица смежности используется для описания структуры как неориентированного, так и ориентированного графа; матрица инцидентности - для описания структуры, главным образом, ориентированного графа.

Пример связного графа представлен на рисунке 1.

Рисунок 1 - Пример связного графа

Граф называется связным, если любые две его вершины можно соединить цепью.

Граф называется конечным, если множество ребер его конечно. Примером бесконечного графа может служить прямоугольная сетка, заданная на плоскости.

Граф, все вершины которого связаны дугами, называется ориентированным (орграфом). Пример ориентированного графа показан на рисунке 2.

Рисунок 2 - Пример ориентированного графа

В ориентированных графах можно рассматривать как неориентированные цепи и циклы, не принимая во внимание ориентацию ребер, так и ориентированные, в которых все ребра проходятся в направлении их ориентации. Ориентированную цепь называют в этом случае путем, а ориентированный цикл - контуром. Если контур образован одной вершиной и одной дугой, он называется петлей.

Планирование сложных процессов потребовало создания специальных методов сетевого планирования и управления (СПУ). В основе методов СПУ лежит применение сетевых графиков. Первые системы СПУ, использующие сетевые графики, появились в конце 1950-х годов в США и ныне известны по аббревиатурам CPM (Critical Path Method - метод критического пути) и PERT (Program Evaluation and Review Technique - метод анализа и оценки программ).

Сетевая модель - это план выполнения некоторого комплекса работ, заданный в специфической форме сети (дугам поставлены в соответствие интервалы времени), графическое изображение которой называют сетевым графиком.

Главными элементами сетевой модели являются события и работы.

Термин работа используется в СПУ в широком смысле. Во-первых, это действительная работа - протяженный во времени процесс, требующий затрат ресурсов (например, сборка изделия, испытание прибора и т.п.). Каждая действительная работа должна быть конкретной, четко описанной и иметь ответственного исполнителя.

Во-вторых, это ожидание - протяженный во времени процесс, не требующий затрат труда (например, процесс сушки после покраски, отвердения бетона и т.п.).

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

Продолжительность фиктивной работы принимается равной нулю.

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

Таким образом, события имеют двойственный характер: для всех непосредственно ему предшествующих работ оно является конечным, а для всех непосредственно следующих за ним - начальным. При этом предполагается, что событие не имеет продолжительности и свершается как бы мгновенно. Поэтому каждое событие, включаемое в сетевую модель, должно быть полно, точно и всесторонне определено, его формулировка должна включать в себя результат всех непосредственно предшествующих ему работ.

Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, а завершающее - последующих работ и событий.

Сетевая модель графически представляется в виде ориентированного графа, вершины которого являются событиями, а дуги - работами. Пример элементарного фрагмента сетевого графика приведен на рисунке 3.

Рисунок 3 - Элементарный фрагмент сетевого графика

Необходимо отметить, что принцип построения сетевого графика может отличаться от описанного выше и основанного на сети вида «события-работы».

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

Следует отметить, что сетевой график «работы-связи» в отличие от графика «события-работы» обладает известными преимуществами: не содержит фиктивных работ, имеет более простую технику построения и перестройки, использует хорошо знакомое исполнителям понятие «работа», не включая менее очевидного понятия «событие». Вместе с тем сети без использования событий оказываются более громоздкими, так как событий обычно значительно меньше, чем работ (показатель сложности сети, равный отношению числа работ к числу событий, как правило, существенно больше. Поэтому эти сети менее эффективны с точки зрения управления комплексом работ и не получили достаточно широкого распространения.

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

При построении сетевых графиков необходимо соблюдать следующие правила:

1) В сетевой модели не должно быть «тупиковых» событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события.

2)      В сетевом графике не должно быть «хвостовых» событий, т.е. событий, которым не предшествует хотя бы одна работа, за исключением исходного.

)        В сети не должно быть контуров и петель, т.е. путей, соединяющих некоторые события с ними же самими.

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

)        В сети рекомендуется иметь одно исходное и одно завершающее событие.

2. Задача линейного программирования

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность a_ij i-го вида сырья на каждую единицу j-го вида продукции, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j-го вида продукции заданы таблицей:

Таблица 1

1.      Для производства двух видов продукции I и II с планом x₁ и x₂ единиц составить математическую модель, т.е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.

2.      Найти оптимальный план X*=(x₁, x₂) производства продукции, обеспечивающий максимальную прибыль F_max. Определить остатки каждого вида сырья. Задачу решить симплекс-методом.

.        Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим методом. Определить максимальную прибыль F_max.

.        Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z); найти оптимальный набор цен на сырьё Y*=(y₁, y₂, y₃), обеспечивающий минимум общих затрат на сырье Z_min.

.        Провести анализ первоначальных и дополнительных переменных исходной и двойственной задач, сделать выводы.

.        Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение:

Предположим, что будет использовано х₁ сырья А для изготовления продукции I, х₂ сырья для изделия II. Тогда общая прибыль составит 7х₁ + 4х₂.

Так как общее количество сырья А не может превышать 27 единиц, то должно выполняться следующее неравенство:

х₁+2х₂ ≤ 20.

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

х₁ + х₂ ≤ 10;

х₁ + 6х₂ ≤ 36.

При этом, так как количество изготовляемых изделий не может быть отрицательным, то:

х₁ ≥ 0, х₂ ≥ 0 (1)

Пусть F - прибыль предприятия, так как по условию необходимо составить план производства двух видов изделий, обеспечивающий максимальную прибыль, следовательно, функция F, при условии, что изготовлено х₁ единиц изделий I и х₂ единиц изделий II будет максимизироваться:

F = 7х₁ + 4х₂ → max

Таким образом, мы приходим к следующей математической задаче:

Дана система:

 (2)

трех линейных неравенств с двумя неизвестными х_i (i=1,2). И линейная функция относительно этих же переменных:

 = 7х₁ + 4х₂ (3)

требуется среди всех неотрицательных решений системы неравенств (2), найти такое, при котором функция (3) примет максимальное значение.

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

Прямые S1 - S3, изображены на рисунке 4.

Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой - нет. Определим искомую полуплоскость через точку О (0;0).

Пресечение полученных плоскостей определяет многоугольник решений данной задачи.

Рисунок 4 - Многоугольник решений

Как видно из рисунка 4, многоугольником решений является четырехугольник ОАВС.

Таким образом, среди точек четырехугольника ОАВС нам нужно найти такие, в которых функция F = 7х₁ + 4х₂ принимает максимальное значение. Для нахождения этих точек построим нулевую линию уровня (F₀) 7х₁ + 4х₂ = 0 и вектор N = (7;4).

Передвигая данную прямую параллельно самой себе в направлении вектора N, видим, что ее последней точкой с многоугольником решений задачи является точка C. Следовательно, в этой точке функция F принимает максимальное значение. Координаты точки С:

х₁ = 10 и х₂ = 0.

Таким образом, максимальное значение функции F_max = 7*10+4*0 = 70 + 0 = 70.

Решение симплекс-методом

Математическая модель задачи:

х₁, х₂ ≥ 0

F = 7х₁ + 4х₂

Запишем эту задачу в форме основной задачи ЛП:

Для этого перейдем от ограничений неравенств - к ограничениям равенствам.

Введем 3 дополнительные переменные, в результате чего ограничения запишутся в виде систем ограничений:

Преобразованную систему ограничений запишем в векторной форме:

Поскольку среди векторов Р₁-Р₅ имеются 3 единичных вектора, для данной задачи можно непосредственно записать опорный план.

Таковым является план Х = (0;0;0;20;10;36), определяемый системой трехмерных единичных векторов Р₃, Р₄, Р₅, которые образуют базис трехмерного векторного пространства.

Составим симплексную таблицу для I итерации (таб. 1), подсчитав значения F₀, z_i - c_i и проверяем исходный план на оптимальность.

₀ = (c, P₀); z₁ = (c, P₁) = 0; z₂ = (c, P₂) = 0; z₃ = (c, P₃) = 0;₄ = (c, P₄) = 0; z₅ = (c, P₅) = 0;₁ - c₁ = 0 -7 = -7; z₂ - c₂ = 0 - 4 = -4.

Для векторов базиса z_i - c_i = 0.

Таблица 1

Таким образом, по 4 строке таблицы 1 видно, что план не оптимален, т.к. значения z_i - c_i - отрицательны.

Далее определяем вектор, подлежащий исключению из базиса. Для этого находим Q_0min (b_i/a_i1) для a_i1>0 и Q_0min (b_i/a_i2) для a_i2>0.

Таким образом, Q_0min (b_i/a_i1) = min (20/2;10/1;36/2) = 20/2, а Q_0min (b_i/a_i2)= min (20/2;10/1;36/6) = 36/6.

Min (20/2;36/6) = 36/6.

Таким образом, мы нашли разрешающий элемент, находящийся на пересечении 2-ой строки и столбца вектора Р₂.

Следовательно, вектор Р₄ подлежит исключению из базиса.

Столбец вектора Р₂ и вторая строка являются направляющими.

Далее, составляем таблицу для итерации II (таб. 2).

Сначала заполняем строку вектора вновь введенного в базис. Элементы этой строки таб. 3 получаются из соответствующих элементов таб. 2 делением на разрешающий элемент.

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

Для определения остальных элементов таб. 2 применяем правило прямоугольника.

Данный цикл продолжается до тех пор, пока все значения z_i - c_i - не станут положительными.

Таким образом, в таб. 2 мы запишем все итерации вычислительного процесса.

Таблица 2

Итак, среди значений z_i - c_i нет отрицательных, следовательно, опорный план оптимален и F_max = 70.

Двойственная задача

Прямая задача имеет вид:

х₁, х₂ ≥ 0

F = 7х₁ + 4х₂

Хопт. = (7; 4).

Max F = 57.

Составим двойственную модель и с помощью теорем двойственности найдем оптимальное решение двойственной модели:

Двойственная модель:

 = 20y₁ + 10y₂ + 36y₃→ min

Так как мы уже нашли решение исходной задачи (таб. 2), следовательно, мы нашли и решение двойственной задачи:

y₁ = 3,6; y₂ = 0; y₃ = 0. (итерация III в симплекс-таблице 2).

Таким образом оптимальное решение двойственной задачи = y_опт(3,6;0;0).

Подставим компоненты оптимального решения двойственной задачи в функцию двойственной модели:

Z = 20*3,6+10*0+36*0 = 70+0+0 = 70

Итак, Z = F = 70.

Отчет по результатам:

Отчет по пределам:

Отчет по устойчивости:

3. Транспортная задача

На трех складах А₁, А₂ и А₃ хранится а₁=100, а₂=200, а₃=60+10n единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В₁, В₂ и В₃, заказы которых b₁=190, b₂=120, b₃=10m единиц груза, соответственно. Стоимости перевозок c_ij единицы груза с i-го склада j-му потребителю указаны в соответствующих клетках транспортной таблицы:

Таблица 3

.        Сравнивая суммарный запас и суммарную потребность  в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо закрыть, добавив фиктивный склад А₄ с запасом а₄=b-а в случае а<b или фиктивного потребителя В₄ с потребностью b₄=a-b в случае а>b и положив соответствующие им тарифы перевозок нулевыми.

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

.        Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план

,

обеспечивающий минимальную стоимость перевозок . Найти эту стоимость.

.        Решить задачу в MS Excel в режиме «поиск решения». Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение:

Потребность = 190+120+500 = 810

Возможности = 100+200+260 = 560

Таким образом, данная транспортная задача (ТЗ) - открытая.

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

Таблица 4

Составим первоначальный план по методу северо-западного угла (таблица 5).

Таблица 5

+m -1 =4+3-1 = 6 - соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z₁ = 100*4+90*2+110*5+10*6+250*+250*0 = 400+180+550+60+1500+0 = 2690

Проверим составленный план на оптимальность методом потенциалов.

Рассчитаем потенциалы, исходя из того, что потенциал строки А1 = 0 (таблица 6).

Таблица 6

Далее, рассчитаем теневые цены (таблица 7 - теневые цены выделены серым цветом).

Таблица 7

Наличие теневых цен означает не оптимальность имеющегося плана, следовательно, для улучшения плана намечаем маршрут с наименьшей отрицательной теневой ценой и для этого маршрута определяем цикл перераспределения. Объем перевозимого груза численно равен минимальному значению из тех объемов груза, которые указаны в клетках со знаком минус. Таким образом, min (100;110) = 100.

Итак, составляем новый план (таблица 8).

Данный цикл длится до тех пор, пока все теневые цены не станут положительными.

Таблица 8

+m -1 =4+3-1 = 6 - соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z₂ = 190*2+100*2+10*5+10*6+250*6+250*0 = 380+200+50+60+1500+0 = 2190

Таблица 9

+m -1 =4+3-1 = 6 - соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z₃ = 180*2+10*1+100*2+20*5+250*6+250*0 = 360+10+200+10+1500+0 = 2080

Таблица 10

сетевой модель линейный программирование

n+m -1 =4+3-1 = 6 - соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z₄ = 190*1+100*2+20*5+180*3+70*6+250*0 = 190+200+100+540+420+0 = 1450

Таблица 11

+m -1 =4+3-1 = 6 - соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z₅ = 190*1+100*2+20*0+200*3+70*6+230*0 = 190+200+0+600+420+0 = 1410

В таблице 11 все теневые цены - положительные, следовательно, план оптимален.

Решение задачи в MS Excel.

Исходными данными для решения транспортной задачи являются:

- матрица транспортных расходов;

- предложение поставщиков;

-        спрос потребителей.

Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи показан на рисунке 5.

Рисунок 5 - Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи

Рабочий лист EXCEL с размеченными блоками ячеек показан на рисунке 6.

Рисунок 6 - Рабочий лист EXCEL с размеченными блоками ячеек

Формирование элементов математической модели.

Элементами математической модели транспортной задачи являются следующие суммы:

фактически реализовано;

фактически получено.

Для нашей задачи m=4, n=3.

Рассмотрим процесс формирования этих сумм на рабочем листе EXCEL.

Вначале сформируем, в блоке «Фактически реализовано»

. Заполняем ячейки блока «Матрица перевозок» числом 0,01.

. Селектируем первую ячейку блока «Фактически реализовано»;

. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

. Нажимаем клавишу Delete;

. Селектируем первую строку блока «Матрица перевозок»;

. Нажимаем клавишу Enter;

. Копируем формулу из первой ячейки блока «Фактически реализовано» на все остальные ячейки этого блока.

Сформируем теперь - в блоке «Фактически получено».

Для этого выполните следующие действия:

. Селектируем первую ячейку блока «Фактически получено»;

. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

. Нажимаем клавишу Delete;

. Селектируем первый столбец блока «Матрица перевозок»;

. Нажимаем клавишу Enter;

. Копируем формулу из первой ячейки блока «Фактически получено» на остальные ячейки этого блока.

Для формирования целевой функции введем вначале формулы, отражающие транспортные расходы по каждому потребителю, т.е. формулы в ячейки блока «Транспортные расходы по потребителям».

Для ввода этих формул выполняем следующие действия:

. Селектируем первую ячейку блока «Транспортные расходы»;

. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

. Нажимаем клавишу Delete;

. Селектируем первый столбец блока «Матрица Транспортных расходов»;

. Нажимаем клавишу *;

. Селектируем первый столбец блока «Матрица перевозок»;

. Активируем строку формул, наведя на нее курсор и щелкнув затем левой клавишей мыши;

. Нажимаем одновременно три клавиши: «CTRL» + «SHIFT» + «ENTER»;

. Копируем формулу в остальные ячейки блока «Транспортные расходы»;

Сформируем теперь целевую функцию транспортной задачи, в ячейку «Итого расходы». Для этого:

Селектируем ячейку «Итого расходы»;

. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

. Нажимаем клавишу Delete;

. Селектируем блок ячеек «Транспортные расходы»;

. Нажимаем клавишу Enter;

После формирования элементов математической модели и целевой функции транспортной задачи рабочий лист EXСEL примет вид, показанный на рисунке 7.

Рисунок 7 - Формирования элементов математической модели и целевой функции транспортной задачи

Далее, приступаем к решению задачи с помощью программы «Поиск решения».

Параметры программы «Поиск решения» представлены на рисунке 8.

Рисунок 8 - Параметры программы «Поиск решения»

Результаты решения представлены на рисунке 9.

Рисунок 9 - Результаты решения транспортной задачи

Список использованной литературы

1)          Агальцов В.П. Математические методы в программировании. Учебник - 2 изд. Издательство: Форум, 2010.

2)      Математическое программирование. Учебник (изд:2). Балдин К.В., Брызгалов Н.А., Рукосуев А., Издательство: Дашков и К, 2012.

)        Шапкин А., Шапкин В. Задачи с решениями по высшей математике,теории вероятностей, математической статистике, математическому программированию. Учебное пособие для бакалавров. Издательство: Дашков и К, 2012.