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

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

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

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).