Федеральне Державна освітня установа вищої професійної освіти
Пермська державна сільськогосподарська академія імені академіка Д.Н.Прянішнікова
Кафедра Інформаційних систем
Контрольна робота
з дисципліни:
«Економіко-математичні методи і моделі»
на тему:
«Мережеве планування та управління. Побудова мережевих моделей »
Варіант 21 (m=4, n=3)
Виконав:
студент 2 курсу заочного відділення
по спеціальності: 060800 «Економіка і
управління на підприємствах АПК »
шифр ЕКР - 2010-404 Стариков
Перевірив: О.Ю. Вшивка
Перм - 2015
Зміст
1. Мережеве планування та управління. Побудова мережевих моделей
. Завдання лінійного програмування
. Транспортна задача
Список використаної літератури
1. Мережеве планування та управління. Побудова мережевих моделей
Поняття графа (graph) зазвичай пов'язують з ім'ям великого математика Леонарда Ейлера, який у першій половині XVIII століття вирішив ряд завдань, пов'язаних з використанням цього поняття, і зокрема знамениту задачу про «кенігсберскіх мостах» (одна тисяча сімсот тридцять шість г.). Суть цього завдання полягає в тому, щоб пройти лише один раз по кожному з семи мостів, що з'єднують береги і два острови річки Прегель, на яких розташоване м Кенігсберг (нині м Калінінград), побувавши, таким чином, у всіх районах міста і повернувшись у вихідну точку.
Досліджуючи дану приватну задачу, Ейлер отримав ряд цікавих математичних результатів більш загального характеру, заклавши, тим самим, основи теорії графів. Як самостійна наукова математична дисципліна теорія графів сформувалася через два століття, в 1930-х рр. (термін «граф» вперше був введений Д. Кеніґом в 1936 р), і з того часу розвивається і знаходить широке застосування в багатьох галузях науки і техніки. Зокрема, теорія графів використовується при вирішенні ряду економіко-математичних завдань, пов'язаних з плануванням та управлінням розробкою складних проектів, завданням про призначення, завданням календарного планування і т.д.
Геометрично граф являє собою безліч точок (вершин графа), з'єднаних відрізками ліній (ребрами графа).
Математично структура графа може бути представлена ??за допомогою двох типів матриць - матриці суміжності і матриці інцидентності. Матриця суміжності використовується для опису структури як неорієнтованого, так і орієнтованого графа; матриця інцидентності - для опису структури, головним чином, орієнтованого графа.
Приклад зв'язного графа представлений на малюнку 1.
Рисунок 1 - Приклад зв'язного графа
Граф називається зв'язковим, якщо будь-які дві його вершини можна з'єднати ланцюгом.
Граф називається кінцевим, якщо безліч ребер його звичайно. Прикладом нескінченного графа може служити прямокутна сітка, задана на площині.
Граф, всі вершини якого пов'язані дугами, називається орієнтованим (Орграф). Приклад орієнтованого графа показаний на малюнку 2.
Малюнок 2 - Приклад орієнтованого графа
У орієнтованих графах можна розглядати як неорієнтовані ланцюги і цикли, не беручи до уваги орієнтацію ребер, так і орієнтовані, в яких всі ребра проходяться в напрямку їх орієнтації. Орієнтовану ланцюг називають в цьому випадку шляхом, а орієнтований цикл - контуром. Якщо контур утворений однією вершиною і однією дугою, він називається петлею.
Планування складних процесів потребував спеціальних методів мережевого планування і управління (СПУ). В основі методів СПУ лежить застосування мережевих графіків. Перші системи СПУ, що використовують мережеві графіки, з'явилися в кінці 1950-х років в США і нині відомі по абревіатур CPM (Critical Path Method - метод критичного шляху) і PERT (Program Evaluation and Review Technique - метод аналізу та оцінки програм).
Мережева модель - це план виконання деякого комплексу робіт, заданий у специфічній формі мережі (дугам поставлені у відповідність інтервали часу), графічне зображення якої називають мережевим графіком.
Головними елементами мережевої моделі є події і роботи.
Термін робота використовується в СПУ в широкому сенсі. По-перше, це дійсна робот...
