Методы оптимальных решений. 6

Содержание

 

Задание 1.8 3

Задание 2.8 14

Задание 3.8 21

Задание 4.8 23

Задание 5.8 28

Список литературы 32

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 1.8

 

Методы сетевого планирования и управления

 

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

     Система СПУ  позволяет:

- формировать календарный  план реализации некоторого комплекса  работ;

- выявлять и мобилизовывать  резервы времени, трудовые, материальные  и денежные ресурсы;

- осуществлять управление  комплексом работ с прогнозированием  и предупреждением возможных  срывов в ходе работ;

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

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

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

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

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

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

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

Рисунок 1.1 – Сетевая модель

 

     Анализ сетевого  графика, представленного в графической или табличной (матричной) форме, позволяет:

- более четко выявить взаимосвязи этапов реализации проекта;

- определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ.²

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

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

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

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

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

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

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

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

     Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным.

     В экономике чаще всего используются два вида графов: дерево и сеть.

     Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.

     Сеть — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть». ³

     В сетевой модели имеется начальное событие (с номером  1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

     Cетевая модель имеют ряд характеристик, которые позволяют определить степень напряженности выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов.

     Перед расчетом СМ следует убедиться, что она удовлетворяет следующим основным требованиям:

     1. События правильно пронумерованы, т. е. для каждой работы (i, j) i <j (рис. 1.2. работы (4,3) и (3,2)). При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:

- нумерация событий начинается с исходного события, которому присваивается № 1;

- из исходного события вычеркивают все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2;

- затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;

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

     2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа (событие 5).

     3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа (событие 7).

    4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим (смотреть путь (2,4,3)).

Рисунок 1.2 – Неверно построенная сетевая модель

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

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

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

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

     Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв.

     Ранний срок  свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем t_р(1)=0, a t_р(N)=t_Kp(L):

t_р(j) = max{t_р(j)+(i,j)};   j=2,…, N

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

t_n(i) = min{t_n(i)-t(i,j)};  j=2,…, N-1

     Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения t_n(N) = t_p(N).

     Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i):

R(i) = t_n(i)-  t_p(i)

     Резерв показывает, на какой предельно допустимый срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ.  Для всех работ (i,j) на основе ранних и поздних сроков свершения всех событий можно определить показатели:

     Ранний срок  начала работы — минимальный из возможных моментов начала данной работы при заданных продолжительностях работ и заданном начальном моменте. Ранний срок начала работы совпадает с ранним сроком наступления ее начального события:

t_pn(i,j) = p(i)

     Ранний срок окончания работы — минимальный из возможных моментов окончания данной работы при заданных продолжительностях работ и заданном начальном моменте. Он превышает ранний срок ее начала на величину продолжительности этой работы:

t_po(i,j) = t_p(i) + t(i,j);

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

t_пн(i,j) = t_n(j) - t(i,j)

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

t_no(U) = t_n(j)

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

R_n(i,j) = t_n(j) - t_p(i) - t(i,j)

     Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие — начинаются в ранние сроки.

     Использование этого резерва не влияет на величину резервов времени других работ.⁵

R_н(i,j) = max{0; t_p(j) – t_n(i) - t(i,j)} = max{0;R_n(i,j) - R(i) - R(j)}.

     Путь характеризуется двумя показателями — продолжительностью и резервом. Продолжительность пути определяется суммой продолжительностей составляющих его работ.

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

     Перечисленные выше характеристики сетевой модели могут быть получены на основе приведенных аналитических формул, а процесс вычислений отображен непосредственно на графике, либо в матрице (размерности N*N), либо в таблице.⁶

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

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

 

 

где  t(L_max) - продолжительность максимального пути, проходящего через работу (i,j);

     t_кр - продолжительность (длина) критического пути;

     t_кр^` - продолжительность отрезка рассматриваемого (максимального пути, проходящего через работу ) пути, совпадающего с критическим путем;

     R_n(i,j) - полный резерв времени работы.

     Коэффициент напряженности K_n(i,j) может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). Чем ближе к 1 коэффициент напряженности, тем сложнее выполнить данную работу в установленные сроки. Чем ближе коэффициент напряженности к 0, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.

     На основе коэффициента напряженности все работы сетевого графика могут быть разделены на три группы:

- K_n(i,j) > 0,8 - критические (напряженные);

- 0,6 <= K_n(i,j) <= 0,8 – подкритические;

- K_n(i,j) < 0,6 – резервные.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2.8

 

     Имеется два вида корма (I и II), содержащих питательные вещества (витамины) S1, S2 и S3. Данные о содержании питательных веществ в 1 кг каждого вида корма и необходимом минимуме питательных веществ приведены в таблице.

Таблица 2.1

Исходные данные

Питательное вещество (витамин)	Необходимый минимум питательных  веществ	Число единиц питательных веществ в 1 кг корма
		I	II
S1	9	3	1
S2	8	1	2
S3	12	1	6

 

     Стоимость 1 кг кормов: вида I – 4 ден. ед., вида II – 6 ден. ед.

? Составьте дневной рацион, имеющий минимальную стоимость.

Постройте экономико-математическую модель задачи, дайте необходимые  комментарии к ее элементам и получите решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

 

     Решение:

 

     Составим экономико - математическую модель задачи:

     х1  - количество 1 вида корма

     х2 - количество 2 вида корма

     (3x1+x2) – фактическое содержание питательного вещества S1 во всем корме;

     (x1+2x2) – фактическое содержание питательного вещества S2 во всем корме;

     (x1+6x2) – фактическое содержание питательного вещества S3 во всем корме;

     F(x) = 4x1+6x2 - общая стоимость корма.

 

Модель задачи имеет вид:

min F(x) = 4x1+6x2

3x1+x2 >= 9

x1+2x2 >= 8

x1+6x2 >= 12

x1 >= 0

x2 >= 0

    

     Решение графическим методом

     Строим ОДР  системы ограничений.

     Строим прямые  и полуплоскости.

     1) 3x1+x2 >= 9

         3x1+x2 = 9 – строим прямую по точкам (3;0) и (2;3)

         3x1+x2 > 9

         подставим т. (0;0)

         0>9 – не верно, полуплоскость не содержит т. (0;0)

     2) x1+2x2 >= 8

         x1+2x2 = 8 – строим прямую по точкам (4;2) и (2;3)

         x1+2x2 > 8

         подставим т. (0;0)

        0>8 – не верно, полуплоскость не содержит т. (0;0)

     3) x1+6x2 >= 12

x1+6x2 = 12 – строим прямую по точкам (6;1) и (0;2)

x1+6x2 > 12

подставим т. (0;0)

0>12 – не верно, полуплоскость не содержит т. (0;0)

     4) x1 >= 0

x1 = 0 – прямая лежит на оси ОХ2

x1 > 0 – решением является правая от прямой полуплоскость

      5) x2 >= 0

x2 = 0 – прямая лежит на оси ОХ1

x2 > 0 – решением является верхняя от прямой полуплоскость

Нанесем найденные прямые на график и получим открытую область  с вершинами АВСD (рис. 2.1)

 

Рисунок 2.1 – ОДР системы ограничений

Строим вектор-градиент целевой функции по точкам (0;0) и (4;6). 

Строим  линию уровня:

4x1+6x2 = 0 – по точкам (-3; 2) т (0; 0)

Строим  график решения задачи.

Рисунок 2.2 - График решения  задачи

min F(x) находится в точке В – нижняя точка на графике. Она построена на пересечении 1 и 2 прямых:

3x1+x2=9

x1+2x2=8

х1=2

х2=3

В = (2; 3).

F(x) = 4*2+3*6 = 26.

     Вывод: стоимость  всего корма составит 26 тыс. руб., если использовать 2 кг корма 1 вида и 3 кг корма 2 вида.

     ОДР системы  ограничений не ограничена сверху, значит, на максимум решения нет.

 

Решение в MS Excel

     Заносим на  лист Excel исходные данные.

     Результат решения (изменяемые ячейки) будут помещены в ячейки В2:С2, оптимальное значение ЦФ – в ячейке С9.

Рисунок 2.3 – Исходные данные

 

Зададим формулу в ячейке ЦФ.

Курсор в ячейку С9 –  вставка – функция – Математические – СУММПРОИЗВ. (рис. 2.4)

Рисунок 2.4 – Диалоговое окно функции СУММПРОИЗ

 

     Введем формулу  в ячейки левой части.

     Курсор в  ячейку Е5 – вставка – функция  – Математические – СУММПРОИЗВ. (рис. 2.4)

     Массив 1 –  В2:С2, клавиша F4, чтобы закрепить ячейку.

     Массив 2 –  В5:С5

     Ок. Затем скопировать  формулу в ячейки Е6 и Е7.

Рисунок 2.5 - Введены формулы  в ячейки

 

     Команда Поиск решения.

     Задать ячейку ЦФ, указать адреса изменяемых ячеек, ввести ограничения. (рис. 2.6)

 

Рисунок 2.6 - Введены все  условия задачи

     Задать ПАРАМЕТРЫ:

V – линейная модель;

V – неотрицательные значения;

ОК.

Рис 2.7. Ввод параметров

 

     Команда ВЫПОЛНИТЬ. 

     В результате Поиска решения появляется исходная таблица с заполненными ячейками В2:С2 для значений и ячейка С9 с минимальным значением целевой функции (рис. 2.8).

Рис 2.8. Решение получено

 

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

 

 

Задание 3.8

 

Крупная юридическая фирма использует ежедневно в среднем 30 упаковок бумаги. Фирма работает 260 дней в году. Годовая стоимость хранения бумаги оценивается в 20 руб. за упаковку. Затраты на оформление и получение заказа составляют 120 руб. Доставка бумаги осуществляется в течение одного дня. В настоящее время менеджер офиса использует объем заказа в 200 упаковок.

? Определите:

а) объем заказа, который  обеспечит минимальные расходы;

б) период поставок;

в) точку заказа;

г) затраты на управление запасами за год.

Порекомендуете ли вы менеджеру  использовать оптимальный объем заказа вместо 200 упаковок?

 

     Решение:

     М – годовой спрос на бумагу.

     Сточный спрос  составляет 30 упаковок, количество  рабочих дней в году Т = 260 дней, значит годовой спрос М  составит:

     М = 30 * 260 = 7800 упаковок бумаги.

     h = 20 руб. – удельные издержки хранения

     К_опц = 120 руб. – фиксированные издержки производства

t = 1 день – время поставки

 

     а) Рассчитаем оптимальный объем заказа:

 

     б) Рассчитаем  период поставки:

_или

_{0,039*260 = 10 дней}

 

     _{в) Рассчитаем  точку заказа:}

 

     г) Рассчитаем  затраты на управление запасами за год:

     _{Рассчитаем годовые  затраты при размере  партии бумаги 200 упаковок:}

 

     _{Таким образом,  поставка товара осуществляется каждые 10 дней.}

     _{Каждый раз, когда на складе остается 30 упаковок бумаги, делается новый заказ на поставку из 306 упаковок бумаги.}

     _{Менеджеру выгодно  делать оптимальный объем заказа в количестве 306 упаковок вместо 200 упаковок, поскольку при оптимальном заказе годовые затраты будут ниже (6119 руб. вместо 6680 руб.).}

 

 

 

 

 

 

Задание 4.8

 

В бухгалтерии организации  в определенные дни непосредственно с сотрудниками работают два бухгалтера. Если сотрудник заходит в бухгалтерию для оформления документов (доверенностей, авансовых отчетов и пр.) в тот момент, когда оба бухгалтера заняты обслуживанием ранее обратившихся коллег, то он уходит из бухгалтерии, не ожидая обслуживания. Статистический анализ показал, что среднее число сотрудников, обращающихся в бухгалтерию в течение часа, равно 8 , а среднее время, которое затрачивает бухгалтер на оформление документа, – 10 мин.

Оцените основные характеристики работы данной бухгалтерии как СМО с отказами (указание руководства не допускать непроизводительных потерь рабочего времени!). Определите, сколько бухгалтеров должно работать в бухгалтерии в отведенные дни с сотрудниками, чтобы вероятность обслуживания сотрудников была выше 85%.

 

     Решение:

 

     1. Рассчитаем вероятность отказа в обслуживании по формуле:

Р_отк=Р_n=Р₀

,

P₀=

;

  - нагрузка на систему.

 

     2. Расчет нагрузки на систему (рис. 4.1);

Рисунок 4.1 - Расчет нагрузки на систему

 

     3. Расчет вероятности Р₀  ячейке В5 без степени -1, для 1 числа канала (рис. 4.2)

Рисунок 4.2 - Расчет вероятности

     4. Рассчитаем вероятность Р₀ для остальных каналов меняя в формуле 1 на ячейку выше, и скопируем для ячеек В6:В14 (рис. 4.3)

Рисунок 4.3 - Расчет вероятности  Р₀

     5. Рассчитаем вероятность Р₀ в ячейке С5 ставя ячейку В5 в степень -1, и скопируем формулу в ячейки С6:С14 (рис. 4.4);

Рисунок 4.4 - Расчет вероятности  Р₀

 

     6. Рассчитаем вероятность Р_отк в ячейке D5, и скопируем формулу в ячейки D6:D14 (рис. 4.5).